数据链路控制

1、Computer NetworksChapter 9:Data Link Control数据链路控制数据链路控制Data Link LayerApplicationPresentationSessionTransportNetworkData LinkPhysical 1.Line discipline2.Flow control3.Error controlData Link Layer FunctionsLine Discipline Categoriespeer-to-peer primary-secondaryENQ/ACK ConceptENK/ACK coordinates whi

2、ch device may start a transmission and whetheror not the intended recipient is ready and enabled.In both half-duplex and full-duplex transmission ,the initiating deviceestablishes the session.ENQ/ACK-How it worksinitiatorMultipoint Discipline AddressingPoll/select protocols identify each frame as be

3、ing either to or from a specific device on the link. Selectthis mode is used whenever the primary device has something to send. Pollthe polling function is used by the primary device to solicit transmissions from the secondary devices.SelectPollFlow Control:流量控制流量控制 zEnsuring the sending entity does

4、 not overwhelm the receiving entityyPreventing buffer overflowzTransmission time（传输时间）传输时间）yTime taken to emit all bits into mediumzPropagation time（传播时间）传播时间）yTime for a bit to traverse the linkModel of Frame Transmission流量控制类型流量控制类型Stop and Wait (停等式停等式)zSource transmits 1 frame zDestination recei

5、ves frame and replies with acknowledgementzSource waits for ACK before sending next framezDestination can stop flow by not send ACKzWorks well for a few large framesStop and WaitStop and Wait Link Utilization图：停等式链路利用率（传输时间图：停等式链路利用率（传输时间=1=1；传播时间；传播时间= =a a）Stop and wait link utilizationzThe total

6、time to send n frames,T, can be expressed as T=n*Tf ,zTf, time to send one frame and receive an ack.zTf=tframe+tprop+ tproc + tack +tprop+tproczT=n (2tprop+tframe)tframe:time to transmit a frametprop:propagation time tproc:processing time at each station to react to an incoming eventtack:time to tra

7、nsmit an acknowledgeStop and wait link utilizationzU=n X tframe/n(2tprop+tframe)z =1 / (1+2a)z a=tprop/tframez LvRdRLvda/FragmentationzLarge block of data may be split into small framesyLimited buffer sizeyErrors detected sooner (when whole frame received)yOn error, retransmission of smaller frames

8、is neededyPrevents one station occupying medium for long periodszStop and wait becomes inadequateSliding Windows Flow Controlz Allow multiple frames to be in transitz Receiver has buffer W longz Transmitter can send up to W frames without ACKz Each frame is numberedz ACK includes number of next fram

9、e expectedz Sequence number bounded by size of field (k)yFrames are numbered modulo 2kSliding Window Diagram-Sender 6 7Sliding Window Diagram-receiver 6 7Example Sliding WindowSliding Window ExampleSender Receiver Sliding Window EnhancementszReceiver can acknowledge frames without permitting further

10、 transmission (Receive Not Ready:RNR x)zMust send a normal acknowledge to resumezIf duplex, use piggybacking(捎带技术捎带技术)yIf no data to send, use acknowledgement frameyIf data but no acknowledgement to send, send last acknowledgement number again, or have ACK valid flag (TCP)source seq numberack seq nu

11、mberError Control：差错控制差错控制zDetection and correction of errorszLost frameszDamaged frameszAutomatic Repeat reQuestyError detectionyPositive acknowledgmentyRetransmission after timeoutyNegative acknowledgement and retransmissionAutomatic Repeat Request (ARQ)zStop and waitzGo back NzSelective reject (s

12、elective retransmission)Stop and WaitzSource transmits single framezWait for ACKzIf received frame damaged, discard ityTransmitter has timeoutyIf no ACK within timeout, retransmitzIf ACK damaged,transmitter will not recognize ityTransmitter will retransmityReceive gets two copies of frameyUse ACK0 a

13、nd ACK1Damaged FrameLost FrameLost ACKStop and Wait -DiagramStop and Wait - Pros and ConszSimplezInefficientSliding Window Sliding Window ARQzThe sending device keeps copies of all transmitted frames until they have been acknowledged.zIn addition to ACK frames,the receiver has the option of returnin

14、g a NAK frame if the data have been received damaged.zThe sending device in sliding window ARQ is equipped with a timer to enable it to handle lost acknowledgments.Go Back N (1)-返回返回N ARQzBased on sliding windowzIf no error, ACK as usual with next frame expectedzUse window to control number of outst

15、anding frameszIf error, reply with rejectionyDiscard that frame and all future frames until error frame received correctlyyTransmitter must go back and retransmit that frame and all subsequent framesGo Back N - Damaged FramezReceiver detects error in frame izReceiver sends rejection-izTransmitter ge

16、ts rejection-izTransmitter retransmits frame i and all subsequentDamaged FrameGo Back N - Lost Frame (1)zFrame i lostzTransmitter sends i+1zReceiver gets frame i+1 out of sequencezReceiver send reject izTransmitter goes back to frame i and retransmitsGo Back N - Lost Frame (2)zFrame i lost and no ad

17、ditional frame sentzReceiver gets nothing and returns neither acknowledgement nor rejectionzTransmitter times out and sends acknowledgement frame with P bit set to 1zReceiver interprets this as command which it must acknowledges with the number of the next frame it expects (frame i )zTransmitter the

18、n retransmits frame iLost FrameGo Back N - Damaged AcknowledgementzReceiver gets frame i and send acknowledgement (i+1) which is lostzAcknowledgements are cumulative, so next acknowledgement (i+n) may arrive before transmitter times out on frame izIf transmitter times out, it sends acknowledgement w

19、ith P bit set as beforezThis can be repeated a number of times before a reset procedure is initiatedLost ACKGo Back N - Damaged RejectionzAs for lost frame (2)Go Back N - Diagram RR=ACK REJ=NAKSelective Reject-有选择拒绝有选择拒绝zAlso called selective retransmissionzOnly rejected frames are retransmittedzSub

20、sequent frames are accepted by the receiver and bufferedzMinimizes retransmissionzReceiver must maintain large enough bufferzMore complex logic in transmitterSelective Reject -DiagramSelective Rejectlink utilizationz Stop and wait（no error） : z Nr: 重传次数fpftttE2) 12(1)2(aNttNtErfprf1111)1 (iirPPiPNli

21、nk utilizationz Selective Repeat z Go back Nz Nr: 重传次数1212aWttWtEfpf) 12()2(aNWttNWtErfprf1111)1 (iirPPiPNHigh-level Data Link ControlzHDLC:高级数据链路控制协议高级数据链路控制协议zISO 33009, ISO 4335z最重要最重要z其它重要数据链路控制协议的基础其它重要数据链路控制协议的基础zAll are bit-oriented, use bit stuffing for data transparency.zGeneral introductio

22、nHDLC Station Types：站点类型站点类型zPrimary station：主站主站yControls operation of linkyFrames issued are called commandsyMaintains separate logical link to each secondary stationzSecondary station：从站从站yUnder control of primary stationyFrames issued called responseszCombined station：混合站混合站yMay issue commands a

23、nd responsesHDLC Link Configurations 1zUnbalanced(非平衡设置非平衡设置)yOne primary and one or more secondary stationsySupports full duplex and half duplexHDLC Link Configurations 2zBalanced(平衡设置平衡设置)yTwo combined stationsySupports full duplex and half duplexHDLC Transfer Modes (1)zNormal Response Mode (NRM)y

24、Unbalanced configurationyPrimary initiates transfer to secondaryySecondary may only transmit data in response to command from primaryyUsed on multi-drop linesyHost computer as primaryyTerminals as secondary正常响应模式正常响应模式HDLC Transfer Modes (2)zAsynchronous Balanced Mode (ABM)yBalanced configurationyEi

25、ther station may initiate transmission without receiving permissionyMost widely usedyNo polling overhead异步平衡模式异步平衡模式HDLC Transfer Modes (3)zAsynchronous Response Mode (ARM)yUnbalanced configurationySecondary may initiate transmission without permission form primaryyPrimary responsible for line manag

26、ementyrarely used异步响应模式异步响应模式Modes of CommunicationFrame StructurezSynchronous transmissionzAll transmissions in frameszSingle frame format for all data and control exchangesFrame Structure DiagramFlagAddress ControlInformationFCSFlag8bits8extendable8/16variable816 / 32trailerFrame CheckSumFlag Fiel

27、ds-标志域标志域z Delimit frame at both endsz 01111110z May close one frame and open anotherz Receiver hunts for flag sequence to synchronizez Bit stuffing used to avoid confusion with data containing 01111110（比特填充）比特填充）y0 inserted after every sequence of five 1syIf receiver detects five 1s it checks next

28、bityIf 0, it is deletedyIf 1 and seventh bit is 0, accept as flag(标志标志)yIf sixth and seventh bits 1, sender is indicating abort(异常中止异常中止)Flag FieldsBit Stuffingz Example with possible errorsBit Stuffing011111?011111101111100111111001111111Address Field-地址域地址域zIdentifies secondary station that sent o

29、r will receive framezUsually 8 bits longzMay be extended to multiples of 7 bitsyLSB of each octet indicates that it is the last octet (1) or not (0)zAll ones (11111111) is broadcast地址域地址域Control Field-控制域控制域zDifferent for different frame typeyInformation - data to be transmitted to user (next layer

30、up)-信息信息xFlow and error control piggybacked on information framesySupervisory - ARQ when piggyback not used-监控监控yUnnumbered - supplementary link control-无编号无编号zFirst one or two bits of control filed identify frame typezRemaining bits explained laterFlagAddress ControlInformationFCSFlagControl Field

31、DiagramControl Field DiagramI-framePoll/Final Bit-轮询轮询/ /结束位结束位zUse depends on contextzCommand frameyP bity1 to solicit (poll) response from peerzResponse frameyF bity1 indicates response to soliciting commandS-frameS-frameAcknowledgement framenegative acknowledgement frameas RR, butstop sendingOnly

32、 retrans. frame specifiedU-framelink controlU-frameU frame control fieldInformation Field-信息字段信息字段zOnly in information and some unnumbered frameszMust contain integral number of octetszVariable lengthFrame Check Sequence FieldzFCSzError detectionz16 bit CRCzOptional 32 bit CRCHDLC Operation-协议操作协议操作

33、zExchange of information, supervisory and unnumbered frameszThree phasesyInitialization-初始化初始化yData transfer-数据传输数据传输yDisconnect-断开连接断开连接初始化初始化z任何一方都可以通过六个置位方式命任何一方都可以通过六个置位方式命令之一请求初始化。令之一请求初始化。z它通知对方请求初始化。它通知对方请求初始化。z它指出请求的是三种方式它指出请求的是三种方式(NRM,ABM,ARM)？z它指出使用的是它指出使用的是3位还是位还是7位的序号。位的序号。数据传送，链路控制，错误恢

34、复。数据传送，链路控制，错误恢复。z序列号：序列号：N(S) , Nz接收就绪：接收就绪：RR iz接收未准备就绪接收未准备就绪：RNR Iz接收拒绝：接收拒绝：REJ iz有选择拒绝：有选择拒绝：SREJ Iz拆链：拆链：DISCz无编号确认：无编号确认：UAz置位（扩展）方式（置位（扩展）方式（3种）种）zSNRM/SNRME;SARM/SARME;SABM/SABMES-frameU-framePollingExampleSelecting ExamplePeer-to-Peer ExamplecontinuedPeer-to-Peer ExampleExamples of Operation (1)Examples of Operation (2)Other DLC Protocols (LAPB,LAPD)zLink Access Procedure, Balanced (LAPB)yPart of X.25 (ITU-T)ySubset of HDLC - ABMyPoint to point link between system and packet switching network nodezLink Access Procedure, D-ChannelyISDN (ITU-D)yAB