Reliable stream service--TCPSlide 2Slide 3Data link protocolsHDLC data link controlSlide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Point-to-Point protocolSlide 15A Typical ScenarioError Detection and Correction (Chapter 3)Odd error detection using parity bitTwo-dimension parity checksInternet ChecksumCRC (Cyclic Redundancy Check) (chapter 3.9.4)Slide 22How to compute CRCSlide 24Slide 25Typical standard CRC polynomialsSlide 27Slide 28The error detection capabilities of CRCs1Reliable stream service--TCP1. TCP accepts byte stream, so segmenting2. It is over IP, so out-of-sequence is very common--lost or error frame results in out-of-sequence-- It is not “wirelike”, even there is a TCP connection between sender and receiver, but this connection has logical meaning and is not a real physical path, i.e., packets ultimately travel along different routes, so out-of-sequence3. Because of not “wirelike”, it is possible for old packets from previous connections to arrive at a receiver. The old packets will confuse the new packets with the same SN. TCP solves it by 1. using long (32 bit) SNs and selecting a random initial SN during connection setup;2. set a timer at end of a connection to clear old packets. So accepting an very old packet is very unlikely.4. TCP uses Selective Repeat ARQ with a mechanism to advertise receive window size for flow control. Moreover, window size is not based on number of packets, but number of bytes5. TCP can also be used for congestion control.CIS, IUPUI 2byte streamSend bufferSegmentsReceive bufferbyte streamApplicationApplicationACKsTransmitterReceiverFigure 5.32TCP preview—reliable stream service3TransmitterSlastSlast + Ws – 1 ...Send WindowSrecentoctetstransmitted& ACKed......Slast + Wa-1Slast oldest unacknowledged byteSrecent highest-numbered transmitted byteSlast+Wa-1 highest-numbered byte that can be transmittedSlast+Ws-1 highest-numbered byte that can be accepted from the applicationReceiverReceive WindowRnextRlastRlast + WR – 1 Rlast highest-numbered byte not yet read by the applicationRnext next expected byteRnew highest numbered byte received correctlyRlast+WR-1 highest-numbered byte that can be accommodated in receive bufferRnewWa=WR-(Rnew-Rlast), Srecent-Slast<=WaAdvertised window:CIS, IUPUI 4Data link protocols•Framing: indicate the boundaries of frames•Error control: ensure reliable transmission•Flow control: prevent sender from overrunning receiver•Addressing information: is required when the channel carries information for multiple users.•Assumption: data link is “wirelike”.•Two protocols: HDLC and PPP.CIS, IUPUI 5HDLC data link control•Was set by ISO•Is connection-oriented: set up connection first, then transfer frames using one of three ARQs, finally tear down the connection (Note: LAN generally provides unacknowledged connectionless service)•HLDC configurations and transfer modes•HDLC frame format•Typical frame exchangeCIS, IUPUI 6PhysicalLayerData LinkLayerData LinkLayerNetworkLayerDLSDU DLSDUNetworkLayerPhysicalLayerDLPDUNLPDU“packet”“frame”DLSAPDLSAPFigure 5.32Data link layer7Primary SecondaryCommandsResponsesUnbalanced Point-to-point linkPrimaryCommandsResponsesSecondarySecondarySecondaryUnbalanced Multipoint linkPrimarySecondaryCommandsResponsesBalanced Point-to-point link between Combined StationsPrimarySecondaryCommandsResponsesFigure 5.33HDLC configurations and transfer modesNRM:NormalResponseModeABM: Asynchronous Balance Mode8Flag FlagAddress Control Information FCSFigure 5.35HDLC frame format1. Framing: Flags at both ends define the frame boundaries. Flag value is 011111102. Addressing: indicate the destination address3. Control: various control fields to indicate different frames4. Information: user information by bits, generally no length limit.5. FCS: Frame Check Sum, using 16-or 32-bit CRCQuestion: flag value 01111110 may appear in frame, what to do? Solution: bit stuffing, a technique to prevent occurrence of flag. sender inserts an extra 0 after each instance of five consecutive 1s. receiver looks for five consecutive 1s, if followed by 0, then this 0 was stuffed and is removed; if followed by 10, then flag found.Example: 0110111111111100 011011111011111000 where 0 is stuffed 011011111-11111-00 where –: removed stuff 090 N(S)N(R)P/F12-456-8Information Frame or I-frameN(R)P/FSupervisory Frame or S-frameUnnumbered Frame or U-frame10S SP/F11M M MMMControl field format: three types of framesP/F bit: Poll/Final bit. If set, the frame is a poll frame from primary or the last I-frame of all transmitted frames.N(S): sender SN of I-frame, N(R): piggybacked ACKWindow size: 23 –1 = 7 for Stop-and-Wait and Go-back-N, 4 for Selective-Repeat(in extended control field) 27 –1 = 127 for the first two ARQs, 64 for the last ARQ10N(R)P/FSupervisory Frame or S-frameUnnumbered Frame or U-frame10S SP/F11M M MMMFigure 5.36Control field format: S-frame and U-frameFour types of S-frames:SS=00: RR (Receive Ready) frame used when no I-frame for piggybackSS=01: REJ (Reject) frame, i.e., NAK frameSS=10: RNR (Receive Not Ready) frame, indicate unable to receive any more.SS=11: SREJ (Selective Reject) frame, indicate the retransmission of specified frameU-frames for setup or release of connection: SABM (Set Asynchronous Balance Mode) SNRM (Set Normal Response Mode)SABME: SABM Extended SNRME: SNRM Extended DISC (DISConnect) UA (Unnumbered acknowledgment) FRMR (Frame Reject)CIS, IUPUI 11SABMUAUADISCDatatransferFigure 5.37Typical frame exchange—for connection setup and release12Primary ASecondaries B, CB, RR, 0, PB, I, 0, 0B, I, 1, 0B, I, 2, 0,FXB, SREJ, 1C, RR, 0, PC, RR, 0, FB, SREJ, 1,PB, I, 1, 0B, I, 3, 0B, I, 4, 0, FB, I, 0, 5Figure 5.38Typical frame exchange— using normal response mode(Des.-IP, frame-type, N(S) (for I-frame), N(R), P/F) What ARQ?Selective repeatCIS, IUPUI 13Combined Station ACombined Station BB, I, 0, 0A, I, 0, 0B, I, 1, 0B, I, 2, 1A, I, 1, 1A, I, 2, 1XB, REJ, 1B, I, 3, 2B, I, 4, 3B, I, 1, 3B, I, 2, 4B, I, 3, 4A, I, 3, 1B, RR, 2B, RR, 3Figure 5.39Typical frame exchange— using asynchronous balanced modeWhat ARQ? Go-back-N14Point-to-Point protocol•Used to connect:–Router to router, or home PC to ISP.•HDLC-like frame format•Information by bytes, so char-stuffing in case a flag byte appears in information•Support multiple network protocols simultaneously, e.g, IP, IPX( Novell NetWare)