Data Link Control ProtocolsOverviewFlow ControlSpace-Time DiagramsStop and Wait Flow ControlUtilization: ExamplesEfficiency PrincipleSliding Window ProtocolsSliding Window DiagramSliding Window ExampleSliding Window Protocol EfficiencyEffect of Window SizePiggybackingError ControlStop-and-Wait ARQGo-Back-N ARQGo-back-N (Cont)Selective Reject ARQSelective Reject: Window SizePerformance: Maximum UtilizationPerformance ComparisonHDLC FamilyHDLCHDLC Frame StructureBit StuffingBit Stuffing (Cont)HDLC FramesHDLC Commands and ResponsesHDLC Commands and Responses (cont)Examples of HDLC OperationExamples of Operation (Cont)SummaryReading Assignment7-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. LouisOverviewOverviewFlow ControlEffect of propagation delay, speed, frame sizeError RecoveryHDLC7-3©2005 Raj JainCSE473sWashington University in St. LouisFlow ControlFlow ControlFlow Control Goals: 1. Sender does not flood the receiver, 2. Maximize throughputSender throttled until receiver grants permission7-4©2005 Raj JainCSE473sWashington University in St. LouisSpace-Time DiagramsSpace-Time 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: Examples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.12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.98 Note: The textbook uses B for tprop and L for tframe7-7©2005 Raj JainCSE473sWashington University in St. LouisEfficiency PrincipleEfficiency Principle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 ProtocolsWindow = Set of sequence numbers to send/receiveSender windowSender window increases when ack received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+1 1 if W>2+17-12©2005 Raj JainCSE473sWashington University in St. LouisEffect of Window SizeEffect of Window SizeU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 ControlError Control = Deliver frames without error, in the proper order to network layerError control Mechanisms:Ack/Nack: Provide sender some feedback about other endTime-out: for the case when entire packet or ack is lostSequence numbers: to distinguish retransmissions from originalsTimeout7-15©2005 Raj JainCSE473sWashington University in St. LouisStop-and-Wait ARQStop-and-Wait ARQAutomaticRepeatreQuest(ARQ)7-16©2005 Raj JainCSE473sWashington University in St. LouisGo-Back-N ARQGo-Back-N ARQReceiver does not cache out-of-order framesSender has to go back and retransmit all frames after the lost frameRcvrSender1Nack 110122337-17©2005 Raj JainCSE473sWashington University in St. LouisGo-back-N (Cont)Go-back-N (Cont)All possible scenarios are handled:1. Damaged Frame:Frame received with errorFrame lostLast frame lost2. Damaged Ack:One ack lost, next one makes itAll acks lostDamaged Nack:Maximum Window = 2n -1with n-bit sequence numbers7-18©2005 Raj JainCSE473sWashington University in St. LouisSelective Reject ARQSelective Reject ARQReceiver caches out-of-order frames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 UtilizationStop and Wait Flow Control: U = 1/(1+2)Window Flow Control: Stop and Wait ARQ: U = (1-P)/(1+2)Go-back-N ARQ:Selective Reject ARQ:U = 1 W> 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 FamilySynchronous Data Link Control (SDLC): IBMHigh-Level Data Link Control (HDLC): ISOLink Access Procedure-Balanced (LAPB): X.25Link Access Procedure for the D channel (LAPD): ISDNLink Access Procedure for modems (LAPM): V.42Link Access Procedure for half-duplex links (LAPX): TeletexPoint-to-Point Protocol (PPP): InternetLogical Link Control (LLC): IEEEAdvanced Data Communications Control Procedures (ADCCP): ANSIV.120 and Frame relay also use HDLC7-23©2005 Raj JainCSE473sWashington University in St. LouisPrimary station: Issue commandsSecondary Station:Issue responsesCombined Station: Both primary and secondaryUnbalanced Configuration: One or more secondaryBalanced