DataCommunications

《DataCommunications》由会员分享，可在线阅读，更多相关《DataCommunications（58页珍藏版）》请在装配图网上搜索。

1、Data CommunicationsData Link ControlWhat Is Data Link Control?The Data Link layer of a model typically has the following responsibilities:1.Creates a frame2.Creates an error-free logical connectionError controlFlow control3.Makes sure the receiver stays synchronized with the incoming data streamFlow

2、 ControlEnsuring the sending entity does not overwhelm the receiving entityPreventing buffer overflowTransmission timeTime taken to emit all bits into mediumPropagation timeTime for a bit to traverse the linkModel of Frame TransmissionStop and WaitSource transmits frameDestination receives frame and

3、 replies with acknowledgementSource waits for ACK before sending next frameDestination can stop flow by not send ACKWorks well for a few large framesStop and Wait Link UtilizationStop and Wait Link UtilizationTF=tprop+tframe+tproc+tprop+tack+tprocTproc and tack negligible,soT=n(2tprop+tframe)U=(n*tf

4、rame)/n(2tprop+tframe)=tframe/(2tprop+tframe)With a=tprop/tframe,U=1/(1+2a)Stop and Wait Link UtilizationFurthermore,a=tprop/tframe=Propagation Time/Transmission Time=(d/V)/(L/R)=Rd/VLWhere:D=distance of linkV=velocity of propagation(air=speed of light(3 x 108 m/s);fiber=same;copper=0.67 x speed of

5、light)L=length of frame in bitsR=data rate in bpsStop and Wait Link Utilization ExampleConsider a WAN using ATM,2 stations 1000 km apart,ATM frame size=424 bits,standard data rate=155.52 MbpsTransmission Time(L/R)=424/155.52 x 106=2.7 x 10-6 secondsAssume optical link:Propagation Time(d/V)=106 m/3 x

6、 108 m/sec=0.33 x 10-2 secondsStop and Wait Link Utilization ExampleThus,a=0.33 x 10-2/2.7 x 10-6=1222U=1/(1+2a)=1/(1+2x1222)=0.0004 ouch!Another example:A LANV=2 x 108 m/sL=1000 bitsR=10 MbpsD=0.1 km=100 mStop and Wait Link Utilization ExampleThus,a=(d/V)/(L/R)=0.005U=1/(1+2a)=0.99No ouch!Sliding W

7、indows Flow ControlAllow multiple frames to be in transitReceiver has buffer W longTransmitter can send up to W frames without ACKEach frame is numberedACK includes number of next frame expectedSequence number bounded by size of field(k)Frames are numbered modulo 2kSliding Window DiagramExample Slid

8、ing WindowSliding Window EnhancementsReceiver can acknowledge frames without permitting further transmission(Receive Not Ready)Must send a normal acknowledge to resumeIf duplex,use piggybackingIf no data to send,use acknowledgement frameIf data but no acknowledgement to send,send last acknowledgemen

9、t number again,or have ACK valid flag(TCP)Sliding Window PerformanceU=1 if W=2a+1 where W=window sizeThus,Utilization=1(100%)where ACK for frame 1 reaches A before A has exhausted its windowU=W/(2a+1)if W 2a+1 Utilization=W/(2a+1)where A exhausts its window at t=W.Sliding Window PerformanceExample:W

10、hat is U for a 1000-bit frame on a 1 Mbps satellite link with 270 ms delay with a window size of 127?a=Prop/Tran=.270 sec/(1000/1000000)a=2702a+1=541Is W 2a+1?Yes,so U=W/(2a+1)U=127/541=0.23Error ControlDetection and correction of errorsLost framesDamaged framesAutomatic repeat requestError detectio

11、nPositive acknowledgmentRetransmission after timeoutNegative acknowledgement and retransmissionAutomatic Repeat Request(ARQ)Stop and waitGo back NSelective reject(selective retransmission)Stop and WaitSource transmits single frameWait for ACKIf received frame damaged,discard itTransmitter has timeou

12、tIf no ACK within timeout,retransmitIf ACK damaged,transmitter will not recognize itTransmitter will retransmitReceive gets two copies of frameUse ACK0 and ACK1Stop and Wait-DiagramSimpleInefficientGo Back NBased on sliding windowIf no error,ACK as usual with next frame expectedUse window to control

13、 number of outstanding framesIf error,reply with rejectionDiscard that frame and all future frames until error frame received correctlyTransmitter must go back and retransmit that frame and all subsequent framesGo Back N-Damaged FrameReceiver detects error in frame iReceiver sends rejection iTransmi

14、tter gets rejection iTransmitter retransmits frame i and all subsequentGo Back N-Lost Frame(1)Frame i lostTransmitter sends i+1Receiver gets frame i+1 out of sequenceReceiver sends reject iTransmitter goes back to frame i and retransmitsGo Back N-Lost Frame(2)Frame i lost and no additional frames se

15、ntReceiver gets nothing and returns neither acknowledgement nor rejectionTransmitter times out and sends acknowledgement frame with P bit set to 1Receiver interprets this as command which it acknowledges with the number of the next frame it expects(frame i)Transmitter then retransmits frame iGo Back

16、 N-Damaged Acknowledgement/RejectionReceiver gets frame i and sends acknowledgement(i+1)which is lostAcknowledgements are cumulative,so next acknowledgement(i+n)may arrive before transmitter times out on frame iIf transmitter times out,it sends acknowledgement with P bit set as beforeThis can be rep

17、eated a number of times before a reset procedure is initiatedGo Back N-DiagramSelective RejectAlso called selective retransmissionOnly rejected frames are retransmittedSubsequent frames are accepted by the receiver and bufferedMinimizes retransmissionReceiver must maintain large enough bufferMore co

18、mplex login in transmitterSelective Reject-DiagramHigh Level Data Link ControlOne of the more popular data link control protocolsSimilar to IBMs SDLC but more flexibleMany data link protocols are based on HDLC thus if you learn HDLC,you will understand many others,such as all the LAP standardsHDLC S

19、tation TypesPrimary stationControls operation of linkFrames issued are called commandsMaintains separate logical link to each secondary stationSecondary stationUnder control of primary stationFrames issued called responsesCombined stationMay issue commands and responsesHDLC Link ConfigurationsUnbala

20、ncedOne primary and one or more secondary stationsSupports full duplex and half duplexBalancedTwo combined stationsSupports full duplex and half duplexHDLC Transfer Modes(1)Normal Response Mode(NRM)Unbalanced configurationPrimary initiates transfer to secondarySecondary may only transmit data in res

21、ponse to command from primaryUsed on multi-drop linesHost computer as primaryTerminals as secondaryHDLC Transfer Modes(2)Asynchronous Balanced Mode(ABM)Balanced configurationEither station may initiate transmission without receiving permissionMost widely usedNo polling overheadHDLC Transfer Modes(3)

22、Asynchronous Response Mode(ARM)Unbalanced configurationSecondary may initiate transmission without permission form primaryPrimary responsible for lineRarely usedFrame StructureSynchronous transmissionAll transmissions in framesSingle frame format for all data and control exchangesFrame Structure Dia

23、gramFlag FieldsDelimit frame at both ends-01111110May close one frame and open anotherReceiver hunts for flag sequence to synchronizeBit stuffing used to avoid confusion with data containing 011111100 inserted after every sequence of five 1sIf receiver detects five 1s it checks next bitIf 0,it is de

24、letedIf 1 and seventh bit is 0,accept as flagIf sixth and seventh bits 1,sender is indicating abortBit StuffingExample with possible errorsAddress FieldIdentifies secondary station that sent or will receive frameUsually 8 bits longMay be extended to multiples of 7 bitsLSB of each octet indicates tha

25、t it is the last octet(1)or not(0)All ones(11111111)is broadcastControl FieldDifferent for different frame typeInformation-data to be transmitted to user(next layer up)Flow and error control piggybacked on information framesSupervisory-ARQ when piggyback not usedUnnumbered-supplementary link control

26、First one or two bits of control field identify frame typeControl Field DiagramPoll/Final BitUse depends on contextCommand frameP bit1 to solicit(poll)response from peerResponse frameF bit1 indicates response to soliciting commandInformation FieldOnly in information and some unnumbered framesMust co

27、ntain integral number of octetsVariable lengthFrame Check Sequence FieldFCSError detection16 bit CRCOptional 32 bit CRCHDLC OperationExchange of information,supervisory and unnumbered framesThree phasesInitializationData transferDisconnectExamples of Operation(1)Examples of Operation(2)Other DLC Pro

28、tocols(LAPB,LAPD)Link Access Procedure,Balanced(LAPB)Part of X.25(ITU-T)Subset of HDLC-ABMPoint to point link between system and packet switching network nodeLink Access Procedure,D-ChannelISDN(ITU-D)ABMAlways 7-bit sequence numbers(no 3-bit)16 bit address field contains two sub-addressesOne for dev

29、ice and one for user(next layer up)Other DLC Protocols(LLC)Logical Link Control(LLC)IEEE 802Different frame formatLink control split between medium access layer(MAC)and LLC(on top of MAC)No primary and secondary-all stations are peersTwo addresses neededSender and receiverError detection at MAC laye

30、r32 bit CRCDestination and source access points(DSAP,SSAP)Other DLC Protocols(Frame Relay)(1)Streamlined capability over high speed packet witched networksUsed in place of X.25Uses Link Access Procedure for Frame-Mode Bearer Services(LAPF)Two protocolsControl-similar to HDLCCore-subset of controlOth

31、er DLC Protocols(Frame Relay)(2)ABM7-bit sequence numbers16 bit CRC2,3 or 4 octet address fieldData link connection identifier(DLCI)Identifies logical connectionMore on frame relay laterOther DLC Protocols(ATM)Asynchronous Transfer ModeStreamlined capability across high speed networksNot HDLC basedF

32、rame format called“cell”Fixed 53 octet(424 bit)Details laterProtocol Specification and VerificationBy creating a finite state model,it is possible to determine which states are reachable and which are not(reachability analysis)Incompleteness If it is possible for a certain frame to occur in a certai

33、n state and the model does not say what to do nextDeadlock If there exists a set of states from which there is no exit or no progressExtraneous transition Model tells how to handle an event in a state in which the event cannot occurProtocol Specification and VerificationMany different“tools”for prot

34、ocol specification and verificationPackages such as SPINFinite state graphsPetri NetsBisync(BSC)Review Questions1.What is the utilization of stop and wait flow control?(Two stations 20 km apart,1000 byte frames,256 Kbps,UTP)2.What is the utilization of a sliding window system where stations are 100

35、km apart,500 byte frame,1 Mbps,microwave,window size=255?3.Why is the window size always 2n 1?4.What are differences between go-back-n and selective reject?Review Questions5.Ten frames sent,5th frame is lost.What happens with go-back-N?With selective reject?6.What is normal response mode in HDLC?7.How does bit stuffing work?8.What is the difference between HDLC and SDLC?