數(shù)據(jù)鏈路控制

1、Computer NetworksChapter 9:Data Link Control數(shù)據(jù)鏈路控制數(shù)據(jù)鏈路控制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(捎帶技術(shù)捎帶技術(shù))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: 重傳次數(shù)fpftttE2) 12(1)2(aNttNtErfprf1111)1 (iirPPiPNli

21、nk utilizationz Selective Repeat z Go back Nz Nr: 重傳次數(shù)1212aWttWtEfpf) 12()2(aNWttNWtErfprf1111)1 (iirPPiPNHigh-level Data Link ControlzHDLC:高級數(shù)據(jù)鏈路控制協(xié)議高級數(shù)據(jù)鏈路控制協(xié)議zISO 33009, ISO 4335z最重要最重要z其它重要數(shù)據(jù)鏈路控制協(xié)議的基礎(chǔ)其它重要數(shù)據(jù)鏈路控制協(xié)議的基礎(chǔ)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(非平衡設(shè)置非平衡設(shè)置)yOne primary and one or more secondary stationsySupports full duplex and half duplexHDLC Link Configurations 2zBalanced(平衡設(shè)置平衡設(shè)置)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正常響應(yīng)模式正常響應(yīng)模式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異步響應(yīng)模式異步響應(yīng)模式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-監(jiān)控監(jiān)控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-輪詢輪詢/ /結(jié)束位結(jié)束位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-協(xié)議操作協(xié)議操作

33、zExchange of information, supervisory and unnumbered frameszThree phasesyInitialization-初始化初始化yData transfer-數(shù)據(jù)傳輸數(shù)據(jù)傳輸yDisconnect-斷開連接斷開連接初始化初始化z任何一方都可以通過六個置位方式命任何一方都可以通過六個置位方式命令之一請求初始化。令之一請求初始化。z它通知對方請求初始化。它通知對方請求初始化。z它指出請求的是三種方式它指出請求的是三種方式(NRM,ABM,ARM)？z它指出使用的是它指出使用的是3位還是位還是7位的序號。位的序號。數(shù)據(jù)傳送，鏈路控制，錯誤恢

34、復(fù)。數(shù)據(jù)傳送，鏈路控制，錯誤恢復(fù)。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