Slide 1Lecture 27Requirements of application level-processes.Best-effort networksUDPUDP portsUDP headerReliable service - TCPEnd-to-end issuesEnd-to-end issues (cont’d)Segment FormatThe state transition diagram of a TCP connectionConnection establishment and terminationOpen a connectionSlide 15Close a connectionSliding-window revisitedFlow controlFlow control (cont’d)Protecting against wraparoundKeeping the pipe fullSlide 22Adaptive retransmission –original algorithmSlide 24Jacobson/Karels algorithmCongestion control and resource allocationCongestion control and resource allocationCongestion control and resource allocationSlide 29Slide 30Slide 31Slide 32Slide 33TCP congestion controlAdditive Increase/Multiplicative DecreaseSlide 36Slide 37Slow startSlide 39Fast retransmit and fast recoverySlide 41Congestion avoidance mechanismsCOT 4600 Operating Systems Fall 2009Dan C. MarinescuOffice: HEC 439 BOffice hours: Tu-Th 3:00-4:00 PM222222Lecture 27ScheduleTuesday November 24 - Project phase 4 and HW 6 are due Tuesday December 1st -Research projects instead of final exam presentationThursday December 3rd - Class reviewLast time: More on SchedulingNetwork properties - (Chapter 7) - available online from the publisher of the textbookLayersData Link LayerToday:Transport protocols; end-to-end problemsNext Time: Project discussionRequirements of application level-processes.The transport protocols are expected to:Guarantee message deliveryDeliver messages in the same order they are sentDeliver at most one copy of each messageSupport arbitrarily large messagesSupport synchronization between sender and receiverAllow the receiver to apply flow control to the senderSupport multiple application processes on each hostBest-effort networks Services provided by best-effort networksDrop messagesRe-order messagesDeliver duplicate copies of a given messageLimit messages to some finite sizeDeliver messages after an arbitrarily long delayChallenges  develop algorithms that turn the less-than-desirable properties of the underlying network into the high level services required by application programs.UDPProvides a process-to-process transport service.Unreliable and unordered datagram service No flow controlMultiplexingPseudo-header: fields from the IP header (1)+(2)+(3)(1) protocol number(2) source IP address(3) destination IP addressUDP length fieldUDP Checksum optional in IPv4 but mandatory in IPv6pseudo header + udp header + dataUDP portsEndpoints identified by ports. servers run at well-known ports (e.g. Web server at port 80, Domain Server at port 53)see /etc/services on UnixUDP headerReliable service - TCPConnection-orientedByte-streamsending process writes some number of bytesTCP breaks into segments and sends via IPreceiving process reads some number of bytesFull duplexFlow control: keep sender from overrunning receiverCongestion control: keep sender from overrunning networkEnd-to-end issues TCP is based on sliding window protocol used at data link level, but the situation is very different.Potentially connects many different hosts need explicit connection establishment and terminationPotentially different RTT need adaptive timeout mechanismPotentially long delay in network  need to be prepared for arrival of very old packetsPotentially different capacity at destination need to accommodate different amounts of bufferingPotentially different network capacity  need to be prepared for network congestionEnd-to-end issues (cont’d)At a link level congestion is visible in the queue of packets at the sender. Network congestion much tougher to cope with, detect and then prevent.TCP uses the sliding window algorithm on an end-to end basis to provide reliable/ordered delivery.X.25 uses the sliding window protocol on a hop-by-hop basis.A sequence of hop-by-hop guarantees does not add up to an end-to-end guarantee.End-to-end argument: a function should not be provided at a lower levels of a system unless it can be completely and correctly implemented at that level.Yet for performance optimization a function may be incompletely provided at a low level. E.g. error detection is provided on a hop by hop basis. Why send all the way a corrupted packet?Segment FormatEach connection identified with 4-tuple:<SrcPort, SrcIPAddr, DstPort, DstIPAddr>Sliding window + flow controlAcknowledgment, SequenceNum, AdvertisedWindowFlags: SYN, FIN, RESET, PUSH, URG, ACKChecksum: pseudo header + tcp header + dataThe state transition diagram of a TCP connectionTwo types of events trigger a transition:a segment arrives from the peerthe local application process invokes and operation on TCPLecture 27 12Connection establishment and terminationConnection establishment is an asymmetric activity:A server does a passive open.A client does an active open The two parties have to agree upon on a set of parameters the starting numbers the two sides plan to use for their respective byte streams.Three-Way HandshakeConnection termination is symmetric, each side has to close the connection independently. One side can do a close, meaning that it can no longer send the data, but the other side may keep the other half of the connection open and continue sending data.Open a connectionThe information exchanged during the three-way handshakeSN - initial sequence number the client wants to useSN - initial sequence number the server wants to useSYN  flag indicating a sequence number is sent SYN+ACK  flags indicating a sequence number is sent and the next sequence number expected (ACK).The three-ways handshake:a client does an active open, sends a SYN and moves to SYN_SENT state.when SYN arrives at server, the server moves to SYN_RECVD state and sends a segment with SYN+ACK flags on.when the client receives the segment with SYN+ACK flags on it moves to ESTABLISHED stateLecture 27 15Close a connectionThree combinations of transitions to close a connection:This side closes first: ESTABLISHED FIN_WAIT_1FIN_WAIT_2 TIME_WAITCLOSEDThe other side closes first: ESTABLISHEDCLOSE_WAITLAST_ACKCLOSEDBoth sides close at the same time: ESTABLISHEDFIN_WAIT_1CLOSINGTIME_WAITCLOSINGIt takes twice the maximum