A Study on Traffic Characteristics in Multi-hop Wireless Networks 2010 3 Yoichi Yamasaki ( )

21 Local Area Network (LAN) LAN LAN LAN (AP, Access Point) LAN AP LAN AP AP AP (MWN, Multi-hop Wireless Network) MWN AP MWN MWN MWN MWN (CP, Congestion Propagation) MWN TCP i

Master Thesis - Year 2009 A Study on Traffic Characteristics in Multi-hop Wireless Networks Yoichi Yamasaki Abstract Multi-hop Wireless Networks (MWNs) are expected to expand the area of communication networks easier than wired networks because MWNs consist of wireless-enabled nodes. MWNs are actively researched and developed in recent years for building up various networks covering urban and rural areas. However, MWNs still have issues for providing good quality of service. A significant issue is that traffic characteristics on MWNs are not clarified. In this research, therefore, I investigate the traffic characteristics of MWNs based on congestion propagation phenomenon (CP), which has been reported in wired networks, between wireless nodes. Through computer simulations, I show the impact of the CP on network performance in various network parameters. Furthermore, I analyze the developmental process of the CP in MWNs and discuss the method to improve the network performance in MWNs. Keywords: Multi-hop Wireless Network, Congestion Propagation, Transmission Control Protocol ii

1 1 2 4 2.1............................... 5 2.2................................. 6 2.3.............................. 7 2.4................................... 8 3 9 3.1...................................... 10 3.1.1 Tahoe............................. 11 3.1.2 Reno............................. 12 3.1.3 Sack............................. 13 3.2......................... 14 3.2.1 CP.................. 15 4 17 4.1 ACK..................................... 17 4.2 Queue Management with Transmission Record................ 18 5 19 5.1............. 20 5.2.............. 20 iii

6 23 6.1.............................. 23 6.1.1 WAN............................... 23 6.1.2 WMN............................... 32 6.2 ACK............................. 35 6.2.1 ACK WAN........................ 35 6.2.2 ACK WMN........................ 38 6.3 QMTR............................... 41 6.3.1........................... 42 6.3.2........................... 42 7 46 48 49 iv

1 Local Area Network (LAN) LAN LAN LAN LAN LAN 1.1 LAN LAN 1.1 (Multihop Wireless Netrowk MWN) MWN MWN 1

1.1: MWN MWN MWN MWN (CP, Congestion Propagation) [1, 2] 1.2 1 1 2 4 9 1 2

1.2: 2 4 9 3 5 6 8 10 11 2 4 9 6 7 6 CP CP MWN 2 3 4 5 6 CP 3

2 4

2.1 Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) 2.1 S1 D S2 D D S2 CSMA/CA S1 D S2 CSMA/CA S1 S1 S2 S2 D S1 S2 2 CSMA/CA 2 A B A B CSMA/CA B 5

2.1: 2.2 2.2 2.2 6

2.2: MWN [4] 2.3 MWN MWN CP MWN CP 7

MWN 2.4 MWN 8

3 [5] TCP CPU 9

TCP 3.1 TCP Transmission Control Protocol TCP TCP TCP TCP TCP TCP Tahoe Tahoe Reno Selective Acknowledgement(Sack) TCP 10

3.1.1 Tahoe TCP (ACK, Acknowledgement) ACK ACK Advertised Window awnd Congestion Window cwnd ACK awnd cwnd Tahoe 2 cwnd ssthreshold ACK 1 cwnd 2 ACK 2 cwnd 4 ACK 4 cwnd 8 ACK cwnd cwnd ssthreshold cwnd ACK 1 cwnd cwnd = segment size segment size cwnd (3.1) segment size cwnd cwnd 11

cwnd Tahoe cwnd 1 cwnd ACK TCP Round Trip Time RTT TCP TCP cwnd ACK cwnd 1 ACK 3 4 cwnd 1 Tahoe TCP Reno Sack 3.1.2 Reno Reno Tahoe Reno Reno ACK 3 cwnd 12

ACK ssthreshold cwnd cwnd = ssthreshold + 3 segment size (3.2) ACK cwnd ACK cwnd 1 ACK cwnd ssthreshold Reno ACK cwnd ssthreshold ACK cwnd 1 ACK ACK Sack 3.1.3 Sack Sack[6] TCP Reno Sack Sack Reno Reno Sack Sack 1 13

Simplex wired Link 0 N 1 i i 2 i 1 TCP Connection 3.1: ACK 4 Tahoe Reno Sack 3 TCP 3.2 CP[3] [3] 3.1 3.1 CP 3.1 i i 1 TCP 14

3.1: 10 TCP 10 [Mb/s] 31 [ms] 300 [packet] 552 [Byte] DropTail TCP Tahoe i i 1 i 1 i 2 3.2.1 CP CP [3] CP 10 [Mb/s] 1 [Mb/s] CP 3 15

31 [ms] 55 [ms] 600 [packet] CP CP TCP 0 0.1 [s] CP TCP CP TCP CP DropTail Random Early Detection (RED) CP TCP TCP TCP TCP Tahoe TCP Vegas TCP TCP [3] CP CP CP 16

4 6 CP CP CP CP TCP ACK TCP CP TCP 2 4.1 ACK ACK ACK ACK ACK ACK 17

4.2 Queue Management with Transmission Record First In First Out (FIFO) FIFO (QMTR, Queue Management with Transmission Record) 3 5 2 18

5 CP CP CP NS2[7, 8] NS3[9] CP (WAN, Wireless Ad hoc Network) (WMN, Wireless Mesh Network) WAN NS2 (version 2.1b9a with TENS) WMN NS3 (version 3.7) 2 NS-3 (NIC) NS-3 TCP NIC TCP NS2 WAN 19

5.1 WAN WMN 5.1 5.1: IEEE 802.11b RTC/CTS TCP 20 [m] DropTail 200 [packet] TCP Sack 1460 [Byte] 5.1 TCP 7 WAN WAN WMN MWN CP 5.2 WMN WMN 20

Wireless Link 0 7 1 6 2 5 3 4 TCP Connection 5.1: WAN WMN 5.1 5.2 0 7 8 15 WMN 5.1 WAN WMN 5.2 21

5.2: WMN TCP 100 [Mb/s] 5 [ms] DropTail 400 [packet] TCP Sack 1460 [Byte] 8 Simplex Wireless Link 15 7 0 1 9 Duplex Wired Link 14 6 2 10 5 3 13 4 11 12 TCP Connection 5.2: 22

6 WAN WMN 6.1 WAN WMN [3] CP 6.1.1 WAN WAN CP WAN CP WAN CP 5.1 WAN [3] 3.1 5.1 6.1 6.1(a) 6.1(b) TCP 300 800 500 6.1 23

6.1(a) 6.1(b) 6.1(a) 6.1(b) Kb/s 6.1(a) 320 7 6 6 5 CP [3] 6.1(a) 6.1(a) 6.1(b) cwnd 6.1 6.1(b) 10 WAN 24

6.1: WAN [Kb/s] 0 701 1 1019 2 739 3 750 4 696 5 737 6 709 7 871 778 25

Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 200 180 160 140 120 100 80 60 40 20 0 (a) Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 2500 2000 1500 1000 500 0 (b) 6.1: WAN 26

6.2 5.1 6.2 B A TCP A B A B ACK B ACK B A TCP C ACK B A C A B ACK ACK 2 A B ACK 0.26 ms B C TCP 1.35 ms ACK 5 1500 Byte ACK 40 Byte B ACK B ACK cwnd ACK ACK cwnd 27

6.2: CP CP CP 6.3 6.3 4 WAN 4 WAN 6.3 TCP 4 TCP 28

0 3 0 3 TCP 3 1 2 3 3 TCP 1 6.3 TCP 3 6.3 2 3 2 2 cwnd 2 cwnd 2 1 TCP 2 1 1 2 6.4 cwnd 2 1 TCP 0.5 1 2 1 1 cwnd 1 0 TCP 6.5 0 1 0 0 0 cwnd 3 0 6.6 29

6.3: 0 6.4: 1 30

6.5: 2 6.6: 3 31

6.1.2 WMN WAN WMN 6.8 6.8(a) 6.8(b) 6.8(a) CP 350 450 7 0 6.8(b) 350 450 WAN WMN 6.7 WMN 5.2 100 Mb/s 11 Mb/s ACK A S ACK 20 % A B B S ACK S B ACK A S S C ACK B S WAN WMN CP 6.2 WAN 32

6.2: WMN [Kb/s] 0 741 1 679 2 814 3 814 4 689 5 722 6 806 7 830 760.2 760.2 Kb/s WAN 2.3 % 6.7: 33

Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 200 180 160 140 120 100 80 60 40 20 0 (a) Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 2000 1800 1600 1400 1200 1000 800 600 400 200 0 (b) 6.8: WMN 34

6.2 ACK ACK WAN WMN 6.2.1 ACK WAN ACK WAN WAN ACK 6.10(a) CP WAN 6.1(a) ACK CP 6.10(b) ACK ACK 100 X 100 X 50 ACK 50 ACK 50 ACK ACK ACK 14.1 % 6.3 ACK ACK ACK WAN CP 35

CP 6.3: WAN ACK [Kb/s] 0 602 1 867 2 859 3 728 4 804 5 750 6 744 7 957 789 36

Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 200 180 160 140 120 100 80 60 40 20 0 (a) Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 2000 1800 1600 1400 1200 1000 800 600 400 200 0 (b) 6.9: ACK WAN 37

6.2.2 ACK WMN ACK WMN WMN 6.10 6.10(a) 6.10(b) 6.10(a) CP WMN 6.8(a) ACK ACK 6.4 ACK 2.1 % 14.3 % ACK CP WAN WMN ACK 38

6.4: WMN ACK [Kb/s] 0 770 1 875 2 757 3 809 4 802 5 785 6 660 7 756 776.6 39

Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 200 180 160 140 120 100 80 60 40 20 0 (a) Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 1600 1400 1200 1000 800 600 400 200 (b) 6.10: ACK WMN 40

6.3 QMTR QMTR WMN CP QMTR WMN QMTR 3 5 QMTR QMTR 6.11(a) QMTR 3 6.11(b) 5 1 6.11(c) QMTR 6.11(b) 3 6.5 3 QMTR 3 87 % 5 QMTR 5 27 % 3 i 6.5: QMTR QMTR 138192.8 3 18057.8 5 100327.8 41

6.3.1 i i TCP i s i 3 QMTR i i s 4 1 5 QMTR i s 6 1 i s 5 i s 6.3.2 i i 5 i s 3 i s 6.11(c) 3 QMTR 6.12 5 QMTR 6.13 6.12(a) 3 CP CP 5 6.13(a) CP CP 5 CP CP 42

(a) QMTR (b) 3 QMTR (c) 5 QMTR 6.11: QMTR 43

Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 200 180 160 140 120 100 80 60 40 20 0 (a) Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 1600 1400 1200 1000 800 600 400 200 0 (b) 6.12: 3 QMTR 44

Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 200 180 160 140 120 100 80 60 40 20 0 (a) Node number 7 6 5 4 3 2 1 0 300 400 500 600 700 800 Time [s] 1400 1200 1000 800 600 400 200 0 (b) 6.13: 5 QMTR 45

7 MWN, Multi-hop Wireless Network MWN 2 WAN, Wireless Ad hoc Network WMN, Wireless Mesh Network 2 CP, Congestion Propagation MWN CP CP CP ACK QMTR Queue Management with Transmission Record ACK WAN WMN WAN WMN ACK WMN ACK 2.1 % 46

QMTR WMN 3 87 % 5 CP CP 87 % QMTR QMTR 47

48

[1] K. Fukuda, H. Takayasu, and M. Takayasu, Spatial and temporal behavior of congestion in Internet traffic, Fractals, vol. 7, no. 1, pp. 23 31, Mar. 1999. [2] J. Steger, P. Vaderna, and G. Vattay, On the propagation of congestion waves in the Internet, Physica A, vol. 359, pp. 784 792, Jan. 2006. [3] K. Sugiyama, H. Ohsaki, and M. Imase, Congestion propagation among routers in the Internet, SPECTS 2007, pp. 145-150, Jul. 2007. [4] A. Raniwala and T. Chiueh, Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network, Proc. IEEE INFOCOM2005, pp. 2223 2234, Mar. 2005. [5] A. Tanenbaum( ), ( ), 4, BP,, 2003. [6] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow, TCP selective acknowledgement options, IETF RFC2018, Oct. 1996. [7] Network Simulator2, http://www.isi.edu/nsnam/ns/. [8] The Enhanced Network Simulator (TENS), http://www.cse.iitk.ac.in/users/braman/tens/. [9] Network Simulator3, http://www.nsnam.org/. 49