7-1©2005 Raj JainCSE473sWashington University in St. LouisData Link Control Data Link Control ProtocolsProtocolsRaj Jain Washington UniversitySaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse473-05/7-2©2005 Raj JainCSE473sWashington University in St. LouisOverviewOverviewq Flow Controlq Effect of propagation delay, speed, frame sizeq Error Recoveryq HDLC7-3©2005 Raj JainCSE473sWashington University in St. LouisFlow ControlFlow Controlq Flow Control Goals: 1. Sender does not flood the receiver, 2. Maximize throughputq Sender throttled until receiver grants permission7-4©2005 Raj JainCSE473sWashington University in St. LouisSpaceSpace--Time DiagramsTime DiagramsSpaceTime7-5©2005 Raj JainCSE473sWashington University in St. LouisStop and Wait Flow ControlStop and Wait Flow ControlDataAckAckDatatframetprop=12α + 1U=2tprop+tframetframeα =tproptframe=Distance/Speed of SignalBits Transmitted /Bit rate=Distance × Bit rateBits Transmitted × Speed of SignalLight in vacuum= 300 m/μsLight in fiber = 200 m/μsElectricity = 250 m/μs7-6©2005 Raj JainCSE473sWashington University in St. LouisUtilization: ExamplesUtilization: Examplesq Satellite Link: Propagation Delay tprop= 270 msFrame Size = 500 Bytes = 4 kbData rate = 56 kbps ⇒ tframe= 4/56 = 71 msα = tprop/tframe= 270/71 = 3.8U = 1/(2α+1) = 0.12q Short Link: 1 km = 5 μs, Rate=10 Mbps, Frame=500 bytes ⇒ tframe= 4k/10M= 400 μsα=tprop/tframe=5/400=0.012 ⇒ U=1/(2α+1)=0.98Note: The textbook uses B for tpropand L for tframe7-7©2005 Raj JainCSE473sWashington University in St. LouisEfficiency PrincipleEfficiency Principleq For all protocols, the maximum utilization (efficiency) is a non-increasing function of α.αMaxUtilizationNot PossibleProtocol 1Protocol 2Best possibleα =tproptframe=Distance × Bit rateBits Transmitted ×Speed of Signal7-8©2005 Raj JainCSE473sWashington University in St. LouisSliding Window ProtocolsSliding Window Protocolsq Window = Set of sequence numbers to send/receiveq Sender windowq Sender window increases when ack receivedq Packets in sender window must be buffered at source7-9©2005 Raj JainCSE473sWashington University in St. LouisSliding Window DiagramSliding Window Diagram7-10©2005 Raj JainCSE473sWashington University in St. LouisSliding Window Example Sliding Window Example7-11©2005 Raj JainCSE473sWashington University in St. LouisSliding Window Protocol EfficiencySliding Window Protocol EfficiencyDataAcktframetpropU=W tframe2tprop+tframe=W2α+11 if W>2α+17-12©2005 Raj JainCSE473sWashington University in St. LouisEffect of Window SizeEffect of Window SizeαUq Larger window is better for larger α7-13©2005 Raj JainCSE473sWashington University in St. LouisPiggybackingPiggybackingDataData+AcktframetpropHeader Ack DataHeader Data7-14©2005 Raj JainCSE473sWashington University in St. LouisError ControlError Controlq Error Control = Deliver frames without error, in the proper order to network layerq Error control Mechanisms:q Ack/Nack: Provide sender some feedback about other endq Time-out: for the case when entire packet or ack is lostq Sequence numbers: to distinguish retransmissions from originalsTimeout7-15©2005 Raj JainCSE473sWashington University in St. LouisStopStop--andand--Wait ARQWait ARQAutomaticRepeatreQuest(ARQ)7-16©2005 Raj JainCSE473sWashington University in St. LouisGoGo--BackBack--N ARQN ARQq Receiver does not cache out-of-order framesq Sender has to go back and retransmit all frames after the lost frameRcvrSender1Nack 110122337-17©2005 Raj JainCSE473sWashington University in St. LouisGoGo--backback--N (Cont)N (Cont)All possible scenarios are handled:1. Damaged Frame:q Frame received with errorq Frame lostq Last frame lost2. Damaged Ack:q One ack lost, next one makes itq All acks lost3. Damaged Nack:q Maximum Window = 2n-1with n-bit sequence numbers7-18©2005 Raj JainCSE473sWashington University in St. LouisSelective Reject ARQSelective Reject ARQq Receiver caches out-of-order framesq Sender retransmits only the lost frameRcvrSender1Nack 110124357-19©2005 Raj JainCSE473sWashington University in St. LouisSelective Reject: Window SizeSelective Reject: Window Size012345670AckSequence number space > 2 window sizeWindow size <2n-1Timeout7-20©2005 Raj JainCSE473sWashington University in St. LouisPerformance: Maximum UtilizationPerformance: Maximum Utilizationq Stop and Wait Flow Control: U = 1/(1+2α)q Window Flow Control:q Stop and Wait ARQ: U = (1-P)/(1+2α)q Go-back-N ARQ:q Selective Reject ARQ:U = 1W>2α+1 W/(2α+1) W< 2α+1{U = (1-P)/(1+2αP) W> 2α+1 W(1-P)/[(2α+1)(1-P+wP)] W< 2α+1{U = (1-P) W> 2α+1 W(1-P)/(2α+1) W< 2α+1{7-21©2005 Raj JainCSE473sWashington University in St. LouisPerformance ComparisonPerformance Comparison1.00.80.60.40.20.00.1 1 10 100 1000αUtilizationStop-and-waitW= 127 Go-back-NW=7 Go-back-N & W= 7 Selective-rejectW= 127 Selective-rejectMore bps or longer distance7-22©2005 Raj JainCSE473sWashington University in St. LouisHDLC FamilyHDLC Familyq Synchronous Data Link Control (SDLC): IBMq High-Level Data Link Control (HDLC): ISOq Link Access Procedure-Balanced (LAPB): X.25q Link Access Procedure for the D channel (LAPD): ISDNq Link Access Procedure for modems (LAPM): V.42q Link Access Procedure for half-duplex links (LAPX): Teletexq Point-to-Point Protocol (PPP): Internetq Logical Link Control (LLC): IEEEq Advanced Data Communications Control Procedures (ADCCP): ANSIq V.120 and Frame relay also use HDLC7-23©2005 Raj JainCSE473sWashington University in St. Louisq Primary station: Issue commandsq Secondary Station:Issue responsesq Combined Station: Both primary and secondaryq Unbalanced Configuration: One or more secondaryq Balanced Configuration: Two combined stationq Normal Response Mode (NRM): Response from secondaryq Asynchronous Balanced Mode (ABM): Combined Stationq Asynchronous Response Mode (ARM): Secondary may respond before commandHDLCHDLC7-24©2005 Raj JainCSE473sWashington University in St. LouisHDLC Frame StructureHDLC Frame StructureFrameFormatControl Field FormatExtended Address FieldExtended Control Field......0 N(S) P/F N(R)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 81 0 S 0 0 0 0 P/F N(R)InformationSupervisoryN(S)= Send sequence number N(R)= Receive sequence number S= Supervisory function bits