( )

Transcription

1 NAIST-IS-MT TCP

2 ( )

3 TCP 3 TCP TCP 1 1 TCP UNIX TCP,, SACK,, 3, NAIST-IS- MT , i

4 Improving TCP Throughput by Using Split-and-Control Concept 3 Motohiro Yakura Abstract Since the Internet has come into wide use, the trac on the Internet has been increasing alarmingly in recent years. Although the bandwidth of the Internet is becoming larger and larger, the trac in the Internet consumes the bandwidth. So it is very dicult to eliminate congestion completely from the Internet. TCP is the transport layer protocol used by the most of applications. TCP works poorly in the high bandwidth networks where packet loss occurs. In this paper, our goal is to transfer large data eectively on the Internet. We propose a new method of congestion control which splits a TCP connection into sub-connections and apply existing TCP algorithms to each sub-connection. By splitting a TCP connection, TCP can grasp the network conditions better and the congestion control mechanism works more eciently in data transfer than existing methods. All we need to do is that we modify a TCP stack ofserver machines. We implemented and evaluated proposed method. We observed improvement of thoughput on the network environment where packet loss occurs. Keywords: TCP, congestion control, SACK, bandwidth-delay product, sub-chanel 3 Master's Thesis, Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, NAIST-IS-MT , February 14, ii

5 TCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : : TCP Reno : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : SACK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : SACK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30 iii

6 4.2.3 : : : : : : : : : : : : : : : : : : : : : : : : : NACK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : SACKed : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : ACK : : : : : : : : : : : : : : : : : : : : : : SACK : : : : : : : : : : : : : : : : : : : : : Fast Retransmit : : : : : : : : : : : : : : : : : : : : : : : : Fast Recovery : : : : : : : : : : : : : : : : : : : : : : : : : Fast Recovery : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Fast Recovery : : : : : : : : : : : : FACK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : TCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49 iv

7 4.6.4 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Fast Retransmit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Fast Retransmit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Fast Retransmit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : v

8 6.1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : FACK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : vi

9 1 TCP : : : : : : : : : : : : : : : 6 2 TCP : : : : : : : : : : : : : : : 6 3 : : : : : : : : : : : 7 4 IP TCP : : : : : : 8 5 TCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 6 : : : : : : : : : : : : : : : : : : : 12 7 TCP cwnd : : : : : : : : : : : : : : : : 15 8 SACK PERMIT : : : : : : : : : : : : : : : : : : : : : 20 9 SACK : : : : : : : : : : : : : : : : : : : : : : : : : : : A : : : : : : : : : : : : : : : : : : : : : FreeBSD TCP : : : : : : : : tcpcb : : : : : : : : : : : : tcpcb : : : : : : : : : : : : : : : : itcp subcb : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : % : : : : : : : : : : : : : : : : : : % : : : : : : : : : : : : : : : : : : % : : : : : : : : : : : : : : : : : : % (standard) : : : : : : : : : : : % (proposed) : : : : : : : : : : (proposed) : : : : : : : : : : : : : : : : : : : : : : : : : : : (proposed) : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 80 vii

10 1 : : : : : : : : : : : : : : : : : S : : : : : : : : : : : : : % 512k fast retransmit : : : : : : : : : : : : : : : : : : : : : : : : : : : % 512k fast retransmit : : : : : : : : : : : : : : : : : : : : : : : : : : : % 512k [%] : : : : : : : % 512k [%] : : : : : : : 66 7 (proposed) : : 68 8 (no FACK) : 68 9 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Fast Retransmit : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 78 viii

11 1. World Wide Web ( WWW ) ATM Fast Ethernet WWW TCP TCP TCP TCP TCP TCP TCP [1] TCP 2 1 1

12 TCP 2 TCP fast retransmit fast retransmit TCP 1 1 TCP TCP fast retransmit TCP 2 TCP fast retransmit 2 TCP TCP 1 TCP TCP fast retransmit 2

13 2 TCP

14 TCP TCP TCP TCP(Transmission Control Protocol) TCP ( ) TCP IP (Internet Protocol) TCP TCP IP TCP IP TCP IP TCP UDP (User Datagram Protocol) UDP TCP 4

15 TCP TCP TCP WWW WWW SYN FIN TCP connect() listen() accept() close() TCP 5

16 Active Open connect() SYN N Passive Open listen() ack N+1 SYN M accept() ack M+1 Established 1 TCP Active Close Passive Close close() FIN N ack N +1 FIN M close() ack M +1 2 TCP 6

17 Application Layer Transport Layer Network Layer Link Layer TCP 3 OSI OS 2. IP 3. TCP UDP 4. Telnet FTP 7

18 IP datagram TCP segment IP header TCP header TCP data 20 bytes 20 bytes MSS MTU 4 IP TCP TCP IP TCP IP TCP IP 4 IP TCP (Max Segment Size MSS ) MTU MSS MTU 20 IP 20 TCP MSS = MTU 0 40 MTU 1500 Ethernet MTU MSS TCP TCP 20 TCP 40 1 TCP (Kind) (Length) TCP 40 8

19 bit source port number 16bit destination port number 32bit sequence number 32bit acknowledgement number 4bit header length reserved (6bits) 6bit TCP flags 16bit window size 16bit TCP checksum 16bit urgent pointer options (if any) (MAX 40bytes) data (if any) 5 TCP TCP TCP TCP 1 TCP 9

20 (ACKnowledgement ACK ) TCP ACK ACK ACK ACK ACK ACK ACK ACK 3 TCP TCP TCP ACK ACK ACK ACK ACK ACK 2MSS ACK ACK RFC1122 [2] 500ms 200ms FreeBSD 200ms FreeBSD 2MSS 2MSS ACK ACK ACK 10

21 window update ACK TCP 1 TCP TCP TCP ( ) RFC1323 [3] ( ) SYN TCP [4] TCP TCP TCP 11

22 Kind=3 Length=3 Shift Count TCP Tail Drop RED [5] 1 2 LAN TCP 12

23 TCP TCP (Congestion Window cwnd ) TCP cwnd cwnd TCP TCP cwnd cwnd cwnd cwnd cwnd cwnd cwnd cwnd TCP cwnd TCP RFC2581 [6] slow start congestion avoidance fast recovery 3 slow start congestion avoidance cwnd cwnd slow start threshold( ssthresh ) ssthresh slow start congestion avoidance Slow Start slow start TCP 13

24 slow start ACK cwnd ssthresh TCP cwnd 1 2 ACK 1 cwnd 1 cwnd cwnd TCP cwnd ssthresh cwnd ssthresh congestion avoidance Congestion Avoidance congestion avoidance ACK TCP cwnd ssthresh ACK cwnd 1/cwnd cwnd ACK 3 fast retransmit fast recovery ssthresh cwnd cwnd ssthresh congention avoidance cwnd 7 TCP cwnd cwnd MSS MSS Mbps RTT 30ms ns [7] cwnd slow start 14

25 Time vs. Cwnd Cwnd [MSS] cwnd Time [s] 7 TCP cwnd cwnd 230MSS fast retransmit fast recovery cwnd congestion avoidance congestion avoidance cwnd congestion avoidance cwnd 157MSS cwnd slow start cwnd 230MSS slow start TCP TCP ACK 15

26 TCP ACK cwnd ACK ACK ACK ACK fast retransmit ACK fast retransmit fast retransmit fast recovery ACK TCP (Round Trip Time RTT ) RTT ACK RTT TCP RTT RTT RTT ACK 2 16

27 Fast Retransmit ACK 3 ACK fast retransmit ACK 3 3 cwnd ( ) fast retransmit Fast Recovery ACK 3 fast retransmit fast retransmit fast recovery ssthresh congestion avoidance ACK slow start fast recovery 17

28 3 ACK ssthresh cwnd 2 1 cwnd ssthresh 3MSS ACK ACK cwnd MSS cwnd ACK cwnd ssthresh congestion avoidance ACK fast retransmit ACK ACK fast retransmit fast recovery congestion avoidance fast retransmit fast recovery 18

29 2.2 TCP Reno TCP 1980 (UCB) 4.2BSD UNIX BSD 1988 TCP Tahoe slow start congestion avoidance fast retransmit 1990 TCP Reno fast recovery TCP TCP TCP Reno [8] TCP TCP Reno TCP Reno TCP Reno TCP MicroSoft Windows Winsock Linux TCP TCP Reno TCP Reno 4.4BSD Lite2 UCB BSD BSDI BSD/OS BSD OS FreeBSD NetBSD OpenBSD FreeBSD 3.3 Release 2.3 SACK SACK(Selective ACKnowledgement ) RFC2018 [9] TCP ACK ACK SACK TCP SACK TCP SACK PERMIT 8 SACK 9 19

30 Kind=4 Length=2 8 SACK PERMIT 3 SYN SACK SACK PERMIT SACK SYN ACK SACK PERMIT TCP ACK TCP TCP 40 4 RFC1323 RTT 12 SACK 3 1 SACK ACK SACK ACK SACK ACK SACK SACK SACK ACK SACK SACK SACK SACK 20

31 Kind=5 Length Left Edge of 1st Block Right Edge of 1st Block Left Edge of nth Block Right Edge of nth Block 9 SACK 21

32 SACK SACK SACK Microsoft Windows 98 Windows 2000 SACK OS Windows SACK SACK TCP RFC SACK fast retransmit 1 SACK ACK slow start 2 congestion avoidance 1 SACK TCP L.Rizzo SACK [10] SACK SACK RFC2018 fast retransmit ACK 3 fast retransmit SACK 3 SACK RFC2018 RFC2018 SACK SACK SACK 3 22

33 1 [%] [Mbps] TCP TCP TCP 2 1 Mathis [1] TCP BW = MSS RT T 2 C p 1 2 BW p fast retransemit fast recovery TCP C =1:22 RTT 20ms MTU 1500byte BW 1 TCP 2 1 cwnd cwnd cwnd 23

34 fast retransemit fast recovery TCP TCP Reno 1500ms TCP Reno 500ms cwnd TCP TCP cwnd TCP 1. fast retransmit TCP TCP [4] 3 24

35 TCP

36 Brakmo [11] TCP TCP Vegas TCP Vegas TCP Awadallah [12] TCP RTT cwnd TCP BFA RTT TCP Vegas TCP TCP 3.2 NewReno RFC2582 [13] NewReno fast recovery fast retransmit A ACK A NewReno SACK NewReno TCP TCP Reno 26

37 3.3 SACK Mathis [14] FACK(Forward ACKnowledgement) FACK SACK SACK fast recovery TCP Reno + SACK FACK SACK TCP FACK 3.4 RFC2140 [15] [16] TCP TCP 1 TCP 1 27

38 3.5 fast retransmit SACK SACK fast recovery 3.1 TCP 28

39 4. TCP 4.1 TCP TCP TCP TCP TCP TCP API IP 29

40 TCP WWW TCP TCP 1 A S 1;111;n S 1;111;n TCP 1 1 TCP TCP 1TCP 1 30

41 TCP n TCP n n 1 TCP 1TCP 1 n NACK SACK SACK SACK NACK NACK NACK NACK TCP cwnd( sc cwnd ) ssthresh( sc ssthresh ) ownd( sc ownd ) cwnd ( ) { MSS { ACK ACK 31

42 { ACK sc cwnd { idle ICMP source quench ( ) cwnd = MSS { : cwnd = 6 sc cwnd sc cwnd ( ) { congestion window { MSS { ACK sc cwnd < sc ssthresh slow start 1MSS ACK 1MSS sc cwnd sc ssthresh congestion avoidance 1MSS ACK MSS 2 =sc cwnd { idle ICMP source quench sc cwnd = MSS ssthresh ( ) { ( ) { ssthresh = 6sc ssthresh sc ssthresh ( ) { slow start threshold { ( ) /n { sc ssthresh = max(sc cwnd=2; 2MSS) (MSS ) ownd ( ) { 0 32

43 { ownd = 6sc ownd sc ownd ( ) { { 0 { { ACK SACK ACK { { { NACK TCP 33

44 fast retransmit fast recovery SACKed SACK SACK SACK SACKed n 1 34

45 128k k MTU ACK n sc cwnd 1MSS ACK sc cwnd 2MSS 1MSS sc cwnd TCP 1 min(sc cwnd,so-so snd.sb cc)-scownd MSS 35

46 sc ownd ownd ACK ACK ACK ACK fast recovery fast recovery sc cwnd fast recovery 1MSS ACK sc cwnd sc ssthresh slow start 1MSS sc cwnd sc ssthresh congestion avoidance (MSS 2 )=sc cwnd fast recovery sc cwnd sc ownd ACK SACK SACK SACK ACK SACK ACK SACK SACKed SACK sc ownd 36

47 sc ownd SACK SACKed SACK SACK SACK fast recovery fast recovery SACK NACK SACK NACK Fast Retransmit fast retransmit fast retransmit ACK SACK ACK FreeBSD ACK NACK NACK fast retransmit 37

48 fast retransmit NACK fast retransmit sc cwnd 2 1 ssthresh fast recovery fast recovery Fast Recovery fast recovery fast recovery fast retransmit fast retransmit fast recovery fast recovery ACK SACK ACK FreeBSD ACK NACK NACK NACK 38

49 fast recovery fast recovery fast recovery Fast Recovery fast recovery fast recovery fast retransmit fast recovery fast recovery ACK SACK fast recovery sc cwnd = sc ssthresh congention avoidance ACK 1 39

50 TCP n n TCP 1 TCP n n n m ( n m) n cwnd cwnd = nx i=1 cwnd i 0 mx i=1 1 2 cwnd i cnwd i cwnd 1 2 nx i=1 cwnd i 1 n n TCP API 40

51 n TCP slow start n slow start [17] 4MSS conservative ACK ACK ACK 1 2 ACK TCP WWW NACK 3 NACK 3 41

52 TCP ACK TCP fast retransmit fast recovery fast retransmit fast recovery fast retransmit fast recovery TCP SACK NACK A A SACK A SACK A 3 A A 3 SACK A 3 A A 42

53 time B+3 B+2 B+1 A B trigger segment retransmitted segment Sender Receiver 10 A A A TCP B A B A B 10 B SACK A SACK A 3 3 A B 3 SACK A 3 A A Fast Recovery TCP fast recovery cwnd ssthresh( cwnd 2 1) + ACK 2 MSS ACK cwnd 43

54 1MSS cwnd NewReno partial ACK ACK cwnd cwnd ACK NewReno partial ACK ACK 2 1 fast recovery cwnd ownd FACK ACK SACK SACK FACK FACK SACK NewReno fast recovery NACK NewReno FACK

55 4.6.1 TCP FreeBSD 3.3 Release TCP 11 FreeBSD TCP FreeBSD BSD UNIX socket TCP TCP socket() socket socket socket() inpcb TCP tcpcb inpcb socket tcpcb tcpcb TCP 12 tcpcb TCP tcp output() tcp output() 1 itcp get next() 45

56 fo_read fileops{} fo_write fo_ioctl fo_select fo_close vnode{} file{} f_type f_ops f_data file{} f_type f_ops f_data proc{} p_fd filedesc{} fd_ofileflags fd_ofiles DTYPE_VNODE DTYPE_SOCKET **ifaddr{} ifaddr{} ifaddr{} inpcb{} route{} inpcb{} route{} TCP ifa_ifp ifa_link TCP/IP Data Structures(FreeBSD 3.1R) radix_node_head{} radix_node{} radix_node{} radix_node{} *file{}[] tcp_input() tcp_usrreq() tcp_init() sockaddr_dl{} sockaddr_dl{} sockaddr_dl{} sockaddr_dl{} ifa_ifp ifa_next ver old_attach() old_send() inpcb{} inp_list inpcb{} inp_hash dom_next dom_protosw localdomain: tcp_usr_attach() tcp_usr_send() UDP tcpcb{} t_inpcb seg_next socket{} so_snd so_proto so_pcb so_rcv inetdomain: dom_next dom_protosw tcb: domains: *domain{} inpcbhead{} ifnethead{} ifnet: ifnet_addrs: in_ifaddr{} ifa_ifp ifa_next ia_next in_ifaddr{} ifa_ifp ifa_next ia_next MT_DATA MT_DATA mbuf{} mbuf{} MT_DATA MT_DATA mbuf{} mbuf{} pr_usrreqs{} tcp_usrreqs: pr_usrreqs{} pru_oldstyle: sb_mb sb_mb inpcb{} inp_socket inp_route.ro_rt inp_pcbinfo inp_ppcb char[] rt_tables[] 2:AF_INET by M.Yakura motohi-y@is.aist-nara.ac.jp ifnet{} loif[0]: ( ) ( ) left right rtentry{} rt_ifa rt_ifp radix_node{} radix_node{} rtentry{} rt_ifa rt_ifp radix_node{} radix_node{} mbuf{} cluster ti_next ti_prev mbuf{} cluster ti_next ti_prev protosw{}[] inetsw: fileops{} socketops: soo_read soo_write soo_ioctl soo_poll soo_close tcbinfo: inpcbinfo{} listhead hashbase port hashbase hashtbl{} ed_softc[0]: ed_softc{} if_link if_addrhead if_link if_addrhead *in_ifaddr{} in_ifaddrhead: inpcbport{} phd_pcblist phd_port phd_hash inpcbport{} phd_pcblist phd_port phd_hash inpcb{} inp_port list 11 FreeBSD TCP 46

57 inpcb{} inp_list inpcb{} inp_hash tcpcb{} t_inpcb seg_next socket{} so_snd so_proto so_pcb so_rcv tcb: inpcbhead{} MT_DATA MT_DATA mbuf{} mbuf{} MT_DATA MT_DATA mbuf{} mbuf{} sb_mb sb_mb inpcb{} inp_socket inp_route.ro_rt inp_pcbinfo inp_ppcb mbuf{} cluster ti_next ti_prev mbuf{} cluster ti_next ti_prev tcbinfo: inpcbinfo{} listhead hashbase port hashbase hashtbl{} inpcbport{} phd_pcblist phd_port phd_hash inpcbport{} phd_pcblist phd_port phd_hash inpcb{} inp_port list 12 tcpcb 47

58 tcp output() itcp calc len() tcp output() IP ACK ACK tcp input() ACK itcp ack recieved() SACK SACK tcp input() TCP tcp dooptions() tcp dooptions() itcp sack recieved() fast retransmit fast recovery fast retransmit fast recovery tcp input() itcp fast rnr() itcp fast rnr2() fast recovry fast recovry itcp ack recieved() itcp sack recieved() itcp fastrnr end() itcp cwnd update() itcp cwnd update() itcp ack recieved() itcp sack recieved() 48

59 4.6.3 itcp subcb netinet/tcp var.h struct itcp_subcb { TAILQ_ENTRY(itcp_subcb) sc_list; TAILQ_HEAD(sndlist_head_name, itcp_sndlist_el) sndlist_head; u_long u_long u_long int int sc_cwnd; sc_ssthresh; sc_ownd; sc_flags; sc_id; struct tcpcb *tp; struct itcp_sndlist_el *fastrxmt_sl; }; TAILQ ENTRY(itcp subcb) sc list tcpcb TAILQ HEAD(sndlist head name, itcp sndlist el) sndlist head itcp sndlist el u long sc cwnd cwnd 49

60 u long sc ssthresh ssthresh u long sc ownd ownd int sc flags int sc id struct tcpcb *tp tcpcb struct itcp sndlist el *fastrxmt sl fast recovery fast retransmit fast recovery itcp sndlist el netinet/tcp var.h struct itcp_sndlist_el { TAILQ_ENTRY(itcp_sndlist_el) TAILQ_ENTRY(itcp_sndlist_el) tcp_seq beg, end, rxmt; sndlist; all_sndlist; struct itcp_subcb *sc; short nacks, flags; }; 50

61 TAILQ ENTRY(itcp sndlist el) sndlist itcp subcb TAILQ ENTRY(itcp sndlist el) all sndlist tcpcb tcp seq beg tcp seq end tcp seq rxmt struct itcp subcb *sc itcp subcb short nacks NACK short flags tcpcb tcpcb netinet/tcp var.h TAILQ_HEAD(itcp_subcb_head_name, itcp_subcb) itcp_subcb_head; TAILQ_HEAD(itcp_subcb_wait_head_name, itcp_subcb) itcp_subcb_wait_head; TAILQ_HEAD(itcp_sndlist_head_name, itcp_sndlist_el) itcp_sndlist_head; u_long ownd; 51

62 int itcp_para_sc; struct itcp_subcb *itcp_cur_sc; int int itcp_sc_refcnt; itcp_recent_sacked; TAILQ HEAD(itcp subcb head name, itcp subcb) itcp subcb head TAILQ HEAD(itcp subcb wait head name, itcp subcb) itcp subcb wait head TAILQ HEAD(itcp sndlist head name, itcp sndlist el) itcp sndlist head u long ownd int itcp para sc struct itcp subcb *itcp cur sc int itcp sc refcnt int itcp recent sacked ACK SACK 13 tcpcb 14 id 0 itcp subcb 13 id 52

63 tcpcb itcp_sndlist_head F(0) E(2) D(0) C(3) B(1) A(0) 13 tcpcb #0 itcp_subcb sndlist_head F(0) D(0) A(0) 14 itcp subcb itcp get next() itcp calc len() itcp ack recieved() ACK itcp sack recieved() SACK 53

64 itcp fast rnr() itcp fast rnr2() fast retransmit fast recovery itcp fastrnr end() fast recovery itcp cwnd update() sc cwnd cwnd sc ownd ownd 54

65 TCP TCP(standard) (proposed) FACK (no FACK) 3 FACK FACK fast retransmit

66 100Mbps Ether Sender Router 155Mbps ATM 25ms 155Mbps D ATM Delayer Router S1 R1 R2 100Mbps Ether R Receiver S2 Sender 100Mbps Ether S1 S2 R R1 R2 S1 S2 R1 R2 R PC 1 R1 R2 D D ATM R1 R2 ATM D 25ms RTT 50ms S1 S2 R1 R R2 100Mbps Ethernet R1 D R2 D 155Mbps ATM MTU R1 R2 ATM 155Mbps S1 R 32k 64k 128k 512k S1 0% 3% 5% CPU Pentium2 450MHz 128M R1 R2 OS FreeBSD3.2- Release S1 S2 R OS FreeBSD 3.3-Release 3.3-Release 56

67 TCP 128k 2 n 1 S MSS S S[k ] n 1 S 2 128k 32 S 4K MSS TCP TCP n n 1 n 1 TCP n n TCP n

68 OS TCP ACK cwnd 2 TCP ACK ACK ACK ACK FreeBSD 3.3 Release libkern/random.c random() random() Park and Miller tcp output() IP ip output() random() cwnd [18] 58

69 % 17 5% proposed standard proposed cwnd proposed standard 5% standard no FACK proposed FACK k

70 Time [s] x Size vs. Time(no Loss) Para=1 proposed Para=2 proposed Para=4 proposed Para=8 proposed Para=16 proposed Para=1 no FACK Para=2 no FACK Para=4 no FACK Para=8 no FACK Para=16 no FACK Para=1 standard Para=2 standard Para=4 standard Para=8 standard Para=16 standard Size [kbyte] 16 0% 60

71 Time [s] Size vs. Time(Loss 3%) Para=1 proposed Para=2 proposed Para=4 proposed Para=8 proposed Para=16 proposed Para=1 no FACK Para=2 no FACK Para=4 no FACK Para=8 no FACK Para=16 no FACK Para=1 standard Para=2 standard Para=4 standard Para=8 standard Para=16 standard Size [kbyte] 17 3% 61

72 Time [s] Size vs. Time(Loss 5%) Para=1 proposed Para=2 proposed Para=4 proposed Para=8 proposed Para=16 proposed Para=1 no FACK Para=2 no FACK Para=4 no FACK Para=8 no FACK Para=16 no FACK Para=1 standard Para=2 standard Para=4 standard Para=8 standard Para=16 standard Size [kbyte] 18 5% 62

73 5.2.2 Fast Retransmit 3 3% 512K fast retransmit 4 5% 512k fast retransmit ( ) /(fast retransmit ) 3 4 proposed no FACK standard proposed 1 no FACK FACK FACK fast recovery ACK ACK SACK fast recory TCP ACK NACK 5% standard proposed no FACK fast retransmit standard fast retransmit cwnd standard fast retransmit proposed no FACK fast retransmit fast retransmit

74 3 3% 512k fast retransmit standard no FACK proposed / / / / / / / / / / / / / / / % 512k fast retransmit standard no FACK proposed / / / / / / / / / / / / / / /

75 % 512K 6 5% 512k proposed no FACK FACK proposed FACK FACK fast retransmit fast recovery TCP 5%

76 5 3% 512k [%] standard no FACK proposed % 512k [%] A B C

77 k 7 FACK

78 7 (proposed) 3% 5% (no FACK) 3% 5%

79 % TCP 512k 20 3% 4 512k ACK seq fast retransmit 19 TCP fast retransmit cwnd fast retransmit sc cwnd 2 1 cwnd

80 Seq or Ack x Time vs. Seq and Ack seq1047 ack Time 19 3% (standard) 70

81 21 20 fast retransmit 1 71

82 Seq or Ack x Time vs. Seq and Ack seq1033 ack Time 20 3% (proposed) 72

83 Seq[byte] x 10 3 Time vs. Seq seq (0) seq (1) seq (2) seq (3) Time[s] 21 (proposed) 73

84 ACK ACK sc cwnd ACK ACK FACK ACK NACK fast retransmit 74

85 Seq or Ack [byte] x 10 3 Time vs. Seq and Ack seq1033 ack Time [s] x (proposed) 75

86 ppp ppp (64kbps) RTT 100ms 500ms k ( 3 )

87 ACK

88 RTT RTT cwnd RTT RTT Fast Retransmit fast retransmit fast 10 Fast Retransmit Fast Retransmit retransmit % % cwnd 78

89 Seq or Ack [byte] x 10 3 Time vs. Seq and Ack seq1055 ack Time [s] 23 79

90 Seq or Ack [byte] x 10 3 Time vs. Seq and Ack seq1701 ack Time [s] 24 80

91 tail drop n TCP n TCP TCP 2 1 n n 4 8 RTT Fast Retransmit TCP fast retransmit FACK fast recovery fast retransmit 81

92 5.5.3 TCP tail drop

93 sc cwnd sc cwnd [19] ACK cwnd cwnd ACK cwnd cwmd 83

94 6.4 FACK FACK fast recovery ACK ACK SACK fast recory TCP ACK NACK 6.5 TCP TCP TCP ns 6.6 BSD UNIX FreeBSD 3.3-Release BSD UNIX TCP 84

95 4 4 tcp input() tcp output() 85

96 7. TCP TCP fast retransmit 2 2 TCP TCP TCP 1 UNIX TCP TCP n TCP 1 TCP fast retransmit TCP fast retransmit 2 1 fast 86

97 retransmit fast retransmit fast recovery 87

98 88

99 [1] M.Mathis, J.Semke, J.Mahdavi, and T.Ott. "The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm". In Computer Communication Review, July [2] R. Braden. "Requirements for Internet Hosts { Communication Layers". RFC 1122, October [3] V. Jacobson, R. Braden, and D. Borman. "TCP Extensions for High Performance". RFC 1323, May [4] V.Jacobson. "Congestion Avoidance and Control". In Computer Communication Review Vol.18, no.4, August [5] S.Floyd and V.Jacobson. "Random Early Detection gateways for Congestion Avoidance". In IEEE/ACM Transactions on Networking, V.1 N.4, August [6] M.Allman, V.Paxson, and W.Stevens. "TCP Congestion Control". RFC 2581, April [7] UCB/LBNL/VINT. [8] Vern Paxson. "Automated Packet Trace Analysis of TCP Implementations". In Proceedings of SIGCOMM '97, [9] M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow. "TCP Selective Acknowledgment Options". RFC 2018, October [10] Luigi Rizzo. luigi/sack.html. [11] L.S.Brakmo and L.L.Peterson. "TCP Vegas: End to End Congestion Avoidance on a Global Internet". In IEEE Journal on Selected Areas in Communication Vol 13, No. 8, October

100 [12] A.A.Awadallah and C.Rai. "TCP-BFA: Buer Fill Avoidance". In IFIP HPN'98, Sep [13] S.Floyd and T.Henderson. "The NewReno Modication to TCP's Fast Recovery Algorithm". RFC 2582, April [14] M.Mathis and J.Mahdavi. "Forward Acknowledgement: Rening TCP Congestion control". In ACM SIGCOMM 96, August [15] J. Touch. "TCP Control Block Interdependence". RFC 2140, April [16]. "TCP ". Master's thesis,, [17] Mark Allman, Chris Hayes, and Shawn Ostermann. "An Evaluation of TCP with Larger Initial Windows". In ACM Computer Communication Review, Vol.28, No.3, July [18] M.Allman. "TCP Byte Counting Renements". In ACM Computer Communication Review, July [19]. "TCP ". Master's thesis,,