TCP for MANET 김동균 경북대학교컴퓨터공학과 dongkyun@knu.ac.kr 1
발표내용 기존 TCP 적용의문제점해결방안들 TCP-Feedback ELFN-based Approach ATCP TCP-BuS Fixed RTO TCP DOOR 결론 2
Transmission Control Protocol Reliable End-to-end Transport Protocol Congestion Control Slow Start Congestion Avoidance Variants of TCP TCP-Tahoe, TCP-Reno, TCP-SACK, TCP- Vegas, etc 3
Slow-start and Congestion Avoidance Congestion Window size (segments) 14 12 10 8 6 4 2 0 Congestion-avoidance Slow-start 0 1 2 3 4 5 6 7 8 Time (round trips) 4
Timeout Mechanism Congestion window (segments) 25 20 15 10 5 0 0 3 ssthreshold = 8 6 9 12 cwnd = 20 timeout 15 20 22 ssthreshold = 10 25 Time (round trips) 5
Fast Recovery Window size (segments) 10 8 6 4 2 0 0 2 4 6 8 10 12 14 Time (round trips) 6
Internet TCP Wired Network 에적합하도록설계 Low BER (Bit Error Rate) Loss 는대부분 Congestion 으로인해발생 Connection 이진행되는동안에경로는대부분고정되어있음 7
MANET 에기존 TCP 적용의문제점 Link 계층에서의문제 MAC 계층으로인한 TCP 영향 높은 BER Network 계층에서의문제 잦은경로변화 Network Partition 발생 Multi-path Routing 으로인한 Out-of-order Message 전송 8
MAC 계층으로인한 TCP 영향 A-B 간의데이터전송에 Interference 발생가능성 Hidden Terminal or Exposed Problem Carrier Sensing Range : 200 m Interference Range : 550 m 9
Hidden and Exposed Nodes RTS Transmission 1 2 3 4 5 Sender Hidden Receiver Forward data segment 전달에영향을주는경우 Transmission 1 2 3 4 5 Sender RTS : no transmission Exposed Backward ACK segment 전달에영향을주는경우 Receiver 10
높은 BER 로인한영향 Bit Error 가패킷들이 Corrupted 되어 Dropped 되게함 TCP 세그먼트나 ACK 의손실유발 Fast Retransmit 혹은 RTO 발생가능성 계속적인 Error 는송신노드의 Congestion Window 값을작게만들어처리율감소를일으킴 11
Network Partitioning 영향 송신노드와수신노드가노드들의이동으로인해서로다른 Partition 에위치하게된다. 연속적인 Timeouts 발생 At time t 0 S D At time t 1 S D 12
경로변화로인한영향 새로운경로를찾는시간이 TCP 송신노드의 RTO 값보다더클수가있다 또한경로변화로인해 packets들이순간적으로수신노드에 out-of-order 로도착할수있다. Time t 0 S A Time t 1 S A B D B D 13
Multi-path Routing 의영향 Some routing protocols (such as TORA) maintain multiple routes between source destination pairs This sometimes results in a significant number of out-of-sequence packets This may trigger the fast retransmit mechanisms. 14
TCP-Feedback 두가지상태존재 : Active and Snooze RFN (Route Failure Notification) Message makes the sender switch into snooze state. Stopping sending further messages and freezing all values like retransmission timers and congestion window size RRN (Route Reestablishment Notification) Message makes the sender come into normal active state Resume all timers and variables. 15
동작예 (1/4) Source Source Dest FP Dest 16
동작예 (2/4) Source RFN FP Dest Source Discard RFN Reroute packets FP Dest 17
동작예 (3/4) Source RFN Dest Source Stop sending further packets Freeze all timers, window Starts a route failure timer Dest 18
동작예 (4/4) Source RRN Dest Source Restarts timers from frozen values Resumes transmission Dest 19
ELFN-based approach Explicit Link Failure Notification message Stand-by mode similar to snooze state of TCP-Feedback Instead of using RRN, a packet is sent periodically to probe the network to see if a route has been established. 좀더정확한 Probe interval 값요구 20
Probe timer 선택 The smaller the gap between packets, the better the throughput 21
Probe packets 사용 Intuitive - Send the first packet in window Optimistic - Send the packet with lowest sequence number among the packets signaled as lost No significant difference observed 22
ATCP (Ad hoc TCP) 표준 TCP 수정없이지원 A thin layer, ATCP between TCP and IP Network 계층의 feedback 존재 : ICMP: The Destination Unreachable ICMP message indicates route disruption ECN: Indicates network congestion With ECN enabled, time out and 3 dup ACKs are assumed to no longer be due to congestion 23
ATCP in the TCP/IP protocol stack Sender Receiver TCP A-TCP IP Link layer TCP IP Link layer 24
High BER 일경우 : ATCP 특징 Retransmits lost segments without shrinking the congestion window. 경로변화혹은 partition 으로인한지연 : Stops transmitting and resumes when a new route is found. Multi-path 를이용하는경우 : On receipt of dup ACKs, TCP sender should not invoke congestion control, because multi-path routing shuffles the order in which segments are received. 25
TCP/ATCP Behavior RTO 발생혹은 3 rd dup ACK 수신시 : Retransmits unacked segments ECN flag 를가진 ACK 수신시 : Invokes congestion control Destination Unreachable ICMP message 수신시 : Stops transmission Wait until a new route is found resume transmission ATCP monitors TCP state and spoofs TCP in such a way to achieve the above behaviors 26
State Transition Diagram Receive Destination Unreachable ICMP CWND 1 TCP transmits a segment Disconnected Normal Start here Receive dup ACK or packet from receiver New ACK ATCP retransmits segments in TCP s buffer Congested Loss Receive ECN RTO about to expire OR 3 dup ACKs TCP Sender is put in persist mode 27
1 st RTT 동작예 Plain TCP 1 ACK1 1 st RTT 1 ACK1 ATCP 2 nd RTT 4 lost 2 nd RTT 4 lost 3 rd RTT 4 th RTT ACK7 4 3 rd RTT 4 th RTT 5 th RTT 5 th RTT After 5 RTTs, 9 segs. transmitted After 5 RTTs, 15 segs. transmitted 28
TCP-BuS (BUffering capability and Sequence information) Explicit notification, Selective Retransmission, Extending timeout values, Avoiding unnecessary request for fast retransmission Taking advantage of Buffering Effect at Intermediate Nodes 주로 intermediate node 에서의 route extension 하는 routing protocol 에적합 ( 예, ABR) 29
Fixed RTO Route failure recovery 가 Routing algorithm 에의해서최대한빨리이루어진다고가정함 불필요한 long recovery 지연을발생할가능성있는 Exponential Backoff 방법회피 Timeout 발생시 TCP sender 는 RTO 를일단두배로증가. 만약 missing packet 이새로운 RTO 시간안에도착하지않으면해당 packet 이계속해서재전송되지만 RTO 는더이상증가안됨. 경로가새롭게발견되고재전송된 packet 이 acknowledged 될때까지고정됨. 30
TCP-DOOR (Detection of Out-of- Order and Response) TCP Code 수정을요구하지만중간노드들의 cooperation 이필요없음. Out-of-order (OOO) packets 수신을통한 Link failure 감지 TCP 수신노드가 OOO 감지시송신노드에게 ACK 패킷의 OOO bit 를통해통보 Temporarily Disabling Congestion Control OOO 통보를받은후 T1 시간동안 RTO 와 CWND 와같은 state variable 를 keep Instant Recovery during Congestion Avoidance OOO 통보를받은후 TCP 송신노드는지난 T2 시간에 Congestion Control Mechanism 이발생했는지여부를조사. 만약 Congestion Control 수행했다면 Congestion 때문이아니라 Route change 로인한결과임을숙지하고 Congestion Control 이전의 state variable 을그대로사용 31
결론 Reliable transport protocol TCP 수정요구 (Route Failure, High BER, Network Partition,.) 중간노드의도움을받는방법 vs. End-toend 로해결가능한방법 TCP-F, TCP-ELFN, ATCP and TCP-BuS vs. Fixed RTO and TCP-DOOR 기존 TCP 수정필요 vs. 수정없이지원 ATCP 32
참고자료 Nitin H. Vaidya Tutorial 자료 http://www.crhc.uiuc.edu/~nhv K. Chandran et. al., A Feedback-based scheme for improving TCP Performance in ad hoc wireless networks, IEEE Personal Comm. Magazine, Feb., 2001. T.D.Dyer, R.V.Boppana, A Comparision of TCP Performance over three routing protocols for Mobile Ad Hoc Networks, ACM MOBIHOC, 2001. G. Holland and N. Vaidya, Analysis of TCP Performance over mobile ad hoc networks, ACM MOBICOM 99, 1999. J. Liu and S. Singh, ATCP: TCP for mobile ad hoc networks, IEEE JSAC, July, 2001. D. Kim, C.-K. Toh and Y.Choi, TCP-BuS: Improvement of TCP Performance in Mobile Ad Hoc Networks, Journal of Communication Networks, 2001. F.Wang and Y.Zhang, Improving TCP Performance over Mobile Ad Hoc Networks with Out-of-Order Detection and Response, ACM MOBIHOC, 2002. 33