5 3.% % 9.5% 1

1

5 3.% % 9.5% 1

1 5 7.1.......................... 7........................3........................... 1 3 13 3.1......................................... 13 3.......................................... 13 3..1................................. 13 3......................... 17 3..3.............................. 17 3................................... 1 3..5 3................. 1 7 3

1.................................. 9 [1]...................... 9 3 ([1])....................... 11...................... 1 5.................................... 1 1 Mbps......................... 15 7 A(1)= Mbps, A()= Mbps....... 1 A(1)= Mbps, A()= Mbps....... 1 9.1 Mbps................ 19 1.1 Mbps...... 11..................... 1 1 Mbps......................... 3 13................................... 1 3................... 5

1 PSP [] [3] [, 5] [] [7] [, 9] [1, 11] [1] [, 13-9] 5

[1] 3

.1 Pathload [13] pathchirp [1] 1.. 3.. 1 3 K k (1 k K) t k t k D k = t k t k k (k + 1) t k t k D k D k = D k+1 D k = (t k+1 t k+1) (t k t k) = (t k+1 t k ) (t k+1 t k ) = t k t k (1) (1) (1) (1) (1) 7

..1 1 N j j j C(j) A(j).1 j A(j) j min A(k) A(j)(1 j N) () 1 k j 1 () j [3] [1] [1] 1 1 5 Mbps Mbps K

区 間 1 区 間 区 間 n-1 区 間 n 1: 計 測 パケット 送 信 端 末 計 測 パケット 受 信 端 末 1 [Mbps] 1 段 目 のリンク 段 目 のリンク 1 [Mbps] 1 [Mbps] 1 [Mbps] 1 [Mbps] 1 [Mbps] 1 [Mbps] 1 [Mbps] 背 景 トラヒック 送 信 端 末 1 背 景 トラヒック 送 信 端 末 背 景 トラヒック 受 信 端 末 1 背 景 トラヒック 受 信 端 末 : [1] 9

1 5 Mbps Mbps () 3 K Mbps.3 [1] ( ) (i) (ii) (ii) x bps y(x) bps C Mbps A Mbps 1

3: ([1]) 11

x y(x) = Cx x+(c A) x A x > A (3) (3) A 1. K (P 1, P,..., P K ). K K (P i,..., P i+k 1) x i y i (K K + 1) (x 1, y 1 ), (x, y ),..., (x K K +1, y K K +1) 3. R C(j)/R l (1 l C(j)/R ) G l = {(x, y) (l 1)R x < lr } (). ( ˆx l, ŷ l ) (1 l C(j)/R ) 5. (3) Ā(j) e(a(j)) = ˆx i A(j) Ā(j) = arg min e(a(j)) (5) A(j) (ŷ i ˆx i ) + ˆx i >A(j) ( ŷ i ) C(j) ˆx i () ˆx i + (C(j) A(j)) 1

3 3.1 5 PC OS Ubuntu Desktop 1. 3bit OS Ubuntu Server 11.1 3bit OS Ubuntu Server 11.1 3bit PC Linux ethtool [31] 17 byte iperf [3] 1 1 1 1 1 i i A(i) Mbps 3. 3..1 1 Mbps R.1 Mbps A(1) K,,, 1, 3, 95% 1 Mbps 1 Mbps 1. Mbps 1 A() A(1) K A() 7 A(1)= Mbps A()= Mbps A() (3) 13

流 出 レート y (i) (ii) 計 測 サンプル (x, y) 誤 差 e y= 流 入 レート x : 区 間 1 区 間 イーサネットスイッチ イーサネットスイッチ 計 測 パケット 送 信 端 末 ルータ1 ルータ 計 測 パケット 受 信 端 末 背 景 トラヒック 送 信 端 末 1 背 景 トラヒック 送 信 端 末 5: 1

1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (a) A(1)= Mbps (b) A(1)= Mbps 1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (c) A(1)= Mbps (d) A(1)= Mbps : 1 Mbps 15

1 1 outgoing rate [Mbps] outgoing rate [Mbps] A(1)= Mbps, A()= Mbps, K= 1 incoming rate [Mbps] A(1)= Mbps, A()= Mbps, K= 1 incoming rate [Mbps] (a) K= (b) K= 1 1 outgoing rate [Mbps] outgoing rate [Mbps] A(1)= Mbps, A()= Mbps, K=1 1 incoming rate [Mbps] A(1)= Mbps, A()= Mbps, K=3 1 incoming rate [Mbps] (c) K=1 (d) K=3 7: A(1)= Mbps, A()= Mbps 1

A(1) A() A() 1 Mbps A(1)= Mbps, A()= Mbps A() Mbps Mbps A(1)= Mbps A()= Mbps 1 Mbps 1 Mbps Mbps 3.. 3..1 A() 1 Mbps 1 Mbps.1 Mbps 9 9 1 A(1)= Mbps A()= Mbps 1 Mbps 7 (3) 3..3 (3) 7 1 17

1 1 outgoing rate [Mbps] outgoing rate [Mbps] A(1)= Mbps, A()= Mbps, K= 1 incoming rate [Mbps] A(1)= Mbps, A()= Mbps, K= 1 incoming rate [Mbps] (a) K= (b) K= 1 1 outgoing rate [Mbps] outgoing rate [Mbps] A(1)= Mbps, A()= Mbps, K=1 1 incoming rate [Mbps] A(1)= Mbps, A()= Mbps, K=3 1 incoming rate [Mbps] (c) K=1 (d) K=3 : A(1)= Mbps, A()= Mbps 1

1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (a) A(1)= Mbps (b) A(1)= Mbps 1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (c) A(1)= Mbps (d) A(1)= Mbps 9:.1 Mbps 19

1 1 outgoing rate [Mbps] outgoing rate [Mbps] A(1)= Mbps, A()= Mbps, K= 1 incoming rate [Mbps] A(1)= Mbps, A()= Mbps, K= 1 incoming rate [Mbps] (a) K= (b) K= 1 1 outgoing rate [Mbps] outgoing rate [Mbps] A(1)= Mbps, A()= Mbps, K=1 1 incoming rate [Mbps] A(1)= Mbps, A()= Mbps, K=3 1 incoming rate [Mbps] (c) K=1 (d) K=3 1:.1 Mbps

(3) 11 1% 9 3.. 1 1 Mbps R 1 Mbps 1 Mbps 1 Mbps Mbps 1 Mbps 1 Mbps 1 Mbps 1. Mbps 1 1 1 Mbps 3..5 3 3 13 3 3 3 1 Mbps.1 Mbps 3..3 1(a) 1 3 3 Mbps 7 Mbps 3 Mbps 1(b) 7 Mbps 3 Mbps 7 Mbps K 3 1

1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (a) A(1)= Mbps (b) A(1)= Mbps 1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (c) A(1)= Mbps (d) A(1)= Mbps 11:

1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (a) A(1)= Mbps (b) A(1)= Mbps 1 1 K= K= K= K=1 K=3 K= 1 K= K= K= K=1 K=3 K= 1 (c) A(1)= Mbps (d) A(1)= Mbps 1: 1 Mbps 3

区 間 1 区 間 区 間 3 イーサネットスイッチ イーサネットスイッチ イーサネットスイッチ 計 測 パケット 送 信 端 末 ルータ1 ルータ 計 測 パケット 受 信 端 末 背 景 トラヒック 送 信 端 末 1 背 景 トラヒック 送 信 端 末 背 景 トラヒック 送 信 端 末 3 13:

1 K= K= K= K=1 K=3 K= Actual value of available bandwidth Available bandwidth [Mbps] 1 3 Hop count (a) A(1)=3 Mbps A()=7 Mbps A(3)=3 Mbps 1 K= K= K= K=1 K=3 K= Actual value of available bandwidth Available bandwidth [Mbps] 1 3 Hop count (b) A(1)=7 Mbps A()=3 Mbps A(3)=7 Mbps 1: 3 5

7

[1] K. Koitani, An Available Bandwidth Measurement Method for Arbitrary Parts of Endto-End Path, Master s thesis, Osaka University, February 13. [] SONY, PSP R. available at http://www.jp.playstation.com/psp/. [3] R. H. Zakon, Hobbes Internet Timeline 11. available at http://www.zakon.org/ robert/internet/timeline/. [] M. Jain and C. Dovrolis, Pathload: A Measurement Tool for End-to-End Available Bandwidth, in Proceedings of PAM, March. [5] T. Oetiker, Tobi Oetiker s MRTG - The Multi Router Traffic Grapher. available at http://oss.oetiker.ch/mrtg/. [] G. Hasegawa and M. Murata, TCP Symbiosis: Congestion Control Mechanisms of TCP Based on Lotka-Volterra Competition Model, in Proceedings of Workshop on interdisciplinary systems approach in performance evaluation and design of computer and communications systems (Inter-Perf ), vol. 11, October. [7] R. Wang, M. Valla, M. Y. Sanadidi, and M. Gerla, Adaptive Bandwidth Share Estimation in TCP Westwood, in Proceedings of Globecom, November. [] E. K. Lua,, J. Crowcroft, M. Pias, and R. Sharma, A Survey and Comparison of Peerto-Peer Overlay Network Schemes, Communications Surveys and Tutorials, vol. 7, no., pp. 7 93, July September 5. [9] J. Ding, I. Balasingham, and P. Bouvry, Management of Overlay Networks: A Survey, in Proceedings of UBICOMM 9, pp. 9 55, October 9. [1] A. Ghodsi, L. O. Alima, and S. Haridi, Low-Bandwidth Topology Maintenance for Robustness in Structured Overlay Networks, in Proceedings of HICSS 5, p. 3a, January 5. [11] Y. Zhu, C. Dovrolis, and M. Ammar, Dynamic Overlay Routing Based on Available Bandwidth Estimation: A Simulation Study, Computer Networks: The International Journal of

Computer and Telecommunications Networking - Overlay distribution structures and their applications, vol. 5, no., pp. 7 7, April. [1] R. Wang, G. Pau, K. Ymada, M. Sanadidi, and M.Gerla, TCP Startup Performance in Large Bandwidth Networks, in Proceedings of INFOCOM, vol., pp. 79 5, March. [13] M. Jain and C. Dovrolis, End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP Throughput, IEEE/ACM Transactions Networking, vol. 11, no., pp. 537 59, August 3. [1] V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, and R. Baraniuk, Multifractal Cross-Traffic Estimation, in Proceedings of ITC-SS 13, September. [15] L. T. M. Cao, Inline Network Measurement : TCP Built-in Techniques for Inferring Endto-End Bandwidth. PhD thesis, Osaka University, January 7. [1] R. S. Prasad, M. Murray, C. Dovrolis, and K. Claffy, Bandwidth Estimation: Metrics, Measurement Techniques, and Tools, IEEE Network, vol. 17, no., pp. 7 35, November December 3. [17] R. L. Carter and M. E. Crovella, Server Selection Using Dynamic Path Characterization in Wide-Area Networks, in Proceedings of INFOCOM 97, p. 11, April 1997. [1] V. J. Ribeiro, R. H. Reidi, R. G. Baraniuk, J. Navratil, and L. Cortrell, pathchirp: Efficient Available Bandwidth Estimation for Network Paths, in Proceedings of PAM 3, April 3. [19] L. T. M. Cao, H. Go, and M. Masayuki, ICIM: An Inline Network Measurement Mechanism for Highspeed Networks, in Proceedings of the EEMON, pp. 73, April. [] N. Hu and P. Steenkiste, Evaluation and Characterization of Available Bandwidth Probing Techniques, IEEE Journal on Selected Areas in Communications, vol. 1, no., pp. 79 9, August 3. [1] J. Navratil and R. L. Cottrell, ABwE: A Practical Approach to Available Bandwidth Estimation, in Proceedings of PAM 3, pp. 1 5, April 3. [] E. Bergfeldta, S. Ekelinb, and J. M. Karlssona, Real-time Available-Bandwidth Estimation using Filtering and Change Detection, Computer Networks, vol. 53, no. 15, pp. 17 5, October 9. 9

[3] M. Jain and C. Dovrolis, End-to-End Estimation of the Available Bandwidth Variation Range, in Proceedings of SIGMETRICS 5, pp. 5 7, June 5. [] L. Lao, C. Dovrolis, and M. Y. Sanadidi, The Probe Gap Model can Underestimate the Available Bandwidth of Multihop Paths, ACM SIGCOMM Computer Communication Review, vol. 3, no. 5, pp. 9 3, October. [5] X. Hei, B. Bensaou, and D. H. K. Tsang, Model-based End-to-End Available Bandwidth Interference using Queueing Analysis, Computer Networks, vol. 5, no. 1, pp. 191 1937, August. [] A. Shriram, M. Murray, Y. Hyun, N. Brownlee, A. Broido, M. Fomenkov, and K. claffy, Comparison of Public End-to-End Bandwidth Estimation Tools on High-Speed Links, in Proceedings of PAM 5, pp. 3 3, March 5. [7] C. Tang and P. K. McKinley, On the Cost-Quality Tradeoff in Topology-Aware Overlay Path Probing, in Proceedings of ICNP 3, pp. 79, November 3. [] S. Ekelin, M. Nilsson, E. Hartikainen, A. Johnsson, J. E. Mangs, B. Melander, and M. Bjorkman, Real-Time Measurement of End-to-End Available Bandwidth using Kalman Filtering, in Proceedings of IEEE/IFIP NOMS, pp. 73, April. [9] N. Hu, L. E. Li, Z. M. Mao, P. Steenkiste, and J. Wang, Locating Internet Bottlenecks: Algorithms, Measurements, and Implications, in Proceedings of ACM SIGCOMM, pp. 1 5, September. [3] C. Dovrolis, P. Ramanathan, and D. Moore, What Do Packet Dispersion Techniques Measure?, in Proceedings of INFOCOM 1, vol., pp. 95 91, April 1. [31] ethtool - Utility for Controlling Network Drivers and Hardware. available at https: //www.kernel.org/pub/software/network/ethtool/. [3] Iperf - The TCP/UDP Bandwidth Measurement Tool. available at http://iperf.fr/. 3