12/12/06 CS/ECE 438 - UIUC, Fall 2006 1TCP12/12/06 CS/ECE 438 - UIUC, Fall 2006 2TCP Adaptive RetransmissionAlgorithm - Original Theory Estimate RTT Multiply by 2 to allow for variations Practice Use exponential moving average (A = 0.1 to 0.2) Estimate = (A) * measurement + (1- A) * estimate Problem Did not handle variations well Ambiguity for retransmitted packets Was ACK in response to first, second, etc transmission?12/12/06 CS/ECE 438 - UIUC, Fall 2006 3TCP Adaptive RetransmissionAlgorithm – Karn-Partridge Algorithm Exclude retransmitted packets from RTTestimate For each retransmission Double RTT estimate Exponential backoff from congestion Problem Still did not handle variations well Did not solve network congestion problems aswell as desired12/12/06 CS/ECE 438 - UIUC, Fall 2006 4TCP Adaptive RetransmissionAlgorithm – Jacobson Algorithm Estimate variance of RTT Calculate mean interpacket RTT deviation to approximate variance Use second exponential moving average Deviation = (B) * |RTT_Estimate – Measurement| + (1–B) * deviation B = 0.25, A = 0.125 for RTT_estimate Use variance estimate as component of RTT estimate Next_RTT = RTT_Estimate + 4 * Deviation Protects against high jitter Notes Algorithm is only as good as the granularity of the clock Accurate timeout mechanism is important for congestion control12/12/06 CS/ECE 438 - UIUC, Fall 2006 5TCP ConnectionEstablishment 3-Way Handshake Sequence Numbers J,K Message Types Synchronize (SYN) Acknowledge (ACK) Passive Open Server listens forconnection from client Active Open Client initiates connectionto server12/12/06 CS/ECE 438 - UIUC, Fall 2006 5TCP ConnectionEstablishment 3-Way Handshake Sequence Numbers J,K Message Types Synchronize (SYN) Acknowledge (ACK) Passive Open Server listens forconnection from client Active Open Client initiates connectionto serverClient ServerTime flows downlisten12/12/06 CS/ECE 438 - UIUC, Fall 2006 5TCP ConnectionEstablishment 3-Way Handshake Sequence Numbers J,K Message Types Synchronize (SYN) Acknowledge (ACK) Passive Open Server listens forconnection from client Active Open Client initiates connectionto serverSynchronize (SYN) JClient ServerTime flows downlisten12/12/06 CS/ECE 438 - UIUC, Fall 2006 5TCP ConnectionEstablishment 3-Way Handshake Sequence Numbers J,K Message Types Synchronize (SYN) Acknowledge (ACK) Passive Open Server listens forconnection from client Active Open Client initiates connectionto serverSynchronize (SYN) JSYN K,acknowledge (ACK) J+1Client ServerTime flows downlisten12/12/06 CS/ECE 438 - UIUC, Fall 2006 5TCP ConnectionEstablishment 3-Way Handshake Sequence Numbers J,K Message Types Synchronize (SYN) Acknowledge (ACK) Passive Open Server listens forconnection from client Active Open Client initiates connectionto serverSynchronize (SYN) JSYN K,acknowledge (ACK) J+1ACK K+1Client ServerTime flows downlisten12/12/06 CS/ECE 438 - UIUC, Fall 2006 6TCP Connection Termination Message Types Finished (FIN) Acknowledge (ACK) Active Close Sends no more data Passive close Accepts no more data12/12/06 CS/ECE 438 - UIUC, Fall 2006 6TCP Connection Termination Message Types Finished (FIN) Acknowledge (ACK) Active Close Sends no more data Passive close Accepts no more dataClient ServerTime flows down12/12/06 CS/ECE 438 - UIUC, Fall 2006 6TCP Connection Termination Message Types Finished (FIN) Acknowledge (ACK) Active Close Sends no more data Passive close Accepts no more dataFinished (FIN) JClient ServerTime flows down12/12/06 CS/ECE 438 - UIUC, Fall 2006 6TCP Connection Termination Message Types Finished (FIN) Acknowledge (ACK) Active Close Sends no more data Passive close Accepts no more dataFinished (FIN) JACK J+1Client ServerTime flows down12/12/06 CS/ECE 438 - UIUC, Fall 2006 6TCP Connection Termination Message Types Finished (FIN) Acknowledge (ACK) Active Close Sends no more data Passive close Accepts no more dataFinished (FIN) JACK J+1Client ServerTime flows downFIN K12/12/06 CS/ECE 438 - UIUC, Fall 2006 6TCP Connection Termination Message Types Finished (FIN) Acknowledge (ACK) Active Close Sends no more data Passive close Accepts no more dataFinished (FIN) JACK J+1ACK K+1Client ServerTime flows downFIN K12/12/06 CS/ECE 438 - UIUC, Fall 2006 7TCP Connection Management (cont)TCP clientlifecycleTCP serverlifecycle12/12/06 CS/ECE 438 - UIUC, Fall 2006 8TCP State DescriptionsWait for network to discard related packetsTIME_WAITConnection closed by both sides simultaneouslyCLOSINGConnection closed locally and ACK’dFIN_WAIT_2Connection closed locallyFIN_WAIT_1Connection closed by peer, closed locally, await ACKLAST_ACKConnection closed by peerCLOSE_WAITConnection ready for data transportESTABLISHEDConnection request sentSYN_SENTConnection request receivedSYN_RCVDWaiting for incoming connectionLISTENDisconnectedCLOSED12/12/06 CS/ECE 438 - UIUC, Fall 2006 8TCP State DescriptionsWait for network to discard related packetsTIME_WAITConnection closed by both sides simultaneouslyCLOSINGConnection closed locally and ACK’dFIN_WAIT_2Connection closed locallyFIN_WAIT_1Connection closed by peer, closed locally, await ACKLAST_ACKConnection closed by peerCLOSE_WAITConnection ready for data transportESTABLISHEDConnection request sentSYN_SENTConnection request receivedSYN_RCVDWaiting for incoming connectionLISTENDisconnectedCLOSEDWait for network to discard related packetsTIME_WAITConnection closed by both sides simultaneouslyCLOSINGConnection closed locally and ACK’dFIN_WAIT_2Connection closed locallyFIN_WAIT_1Connection closed by peer, closed locally, await ACKLAST_ACKConnection closed by peerCLOSE_WAITConnection ready for data transportESTABLISHEDConnection request sentSYN_SENTConnection request receivedSYN_RCVDWaiting for incoming connectionLISTENDisconnectedCLOSED12/12/06 CS/ECE 438 - UIUC, Fall 2006 8TCP State DescriptionsWait for network to discard related packetsTIME_WAITConnection closed by both sides simultaneouslyCLOSINGConnection closed locally and ACK’dFIN_WAIT_2Connection closed locallyFIN_WAIT_1Connection closed by peer, closed locally, await ACKLAST_ACKConnection closed by peerCLOSE_WAITConnection ready for
View Full Document