山東大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)英語課件03The Data Link Layer

1、The Data Link LayerChapter 3CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Data Link Layer Design IssuesError Detection and CorrectionElementary Data Link ProtocolsSliding Window ProtocolsExample Data Link ProtocolsRevised: August 2011The Data Link LayerCN5E by

2、Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Responsible for delivering frames of information over a single linkHandles transmission errors and regulates the flow of dataPhysicalLinkNetworkTransportApplicationData Link Layer Design IssuesCN5E by Tanenbaum & Wetherall,

3、 Pearson Education-Prentice Hall and D. Wetherall, 2011Frames Possible services Framing methods Error control Flow control FramesCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Link layer accepts packets from the network layer, and encapsulates them into frames t

4、hat it sends using the physical layer; reception is the opposite processActual data pathVirtual data pathNetworkLinkPhysicalPossible ServicesCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Unacknowledged connectionless serviceFrame is sent with no connection / er

5、ror recoveryEthernet is exampleAcknowledged connectionless serviceFrame is sent with retransmissions if neededExample is 802.11Acknowledged connection-oriented serviceConnection is set up; rareFraming MethodsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Byte co

6、unt Flag bytes with byte stuffing Flag bits with bit stuffing Physical layer coding violationsUse non-data symbol to indicate frameFraming Byte countCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Frame begins with a count of the number of bytes in itSimple, but

7、difficult to resynchronize after an errorErrorcaseExpectedcaseFraming Byte stuffingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Special flag bytes delimit frames; occurrences of flags in the data must be stuffed (escaped)Longer, but easy to resynchronize after

8、 errorStuffingexamplesFrameformatNeed to escape extra ESCAPE bytes too!Framing Bit stuffingCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Stuffing done at the bit level:Frame flag has six consecutive 1s (not shown)On transmit, after five 1s in the data, a 0 is a

9、ddedOn receive, a 0 after five 1s is deleted Transmitted bitswith stuffingData bitsError ControlCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Error control repairs frames that are received in errorRequires errors to be detected at the receiverTypically retransm

10、it the unacknowledged framesTimer protects against lost acknowledgementsDetecting errors and retransmissions are next topics.Flow ControlCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Prevents a fast sender from out-pacing a slow receiverReceiver gives feedback

11、on the data it can acceptRare in the Link layer as NICs run at “wire speed”Receiver can take data as fast as it can be sent Flow control is a topic in the Link and Transport layers.Error Detection and CorrectionCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Erro

12、r codes add structured redundancy to data so errors can be either detected, or corrected.Error correction codes:Hamming codes Binary convolutional codes Reed-Solomon and Low-Density Parity Check codesMathematically complex, widely used in real systemsError detection codes:Parity Checksums Cyclic red

13、undancy codes Error Bounds Hamming distance CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Code turns data of n bits into codewords of n+k bitsHamming distance is the minimum bit flips to turn one valid codeword into any other valid one. Example with 4 codewords

14、 of 10 bits (n=2, k=8): 0000000000, 0000011111, 1111100000, and 1111111111 Hamming distance is 5Bounds for a code with distance:2d+1 can correct d errors (e.g., 2 errors above)d+1 can detect d errors (e.g., 4 errors above)Error Correction Hamming codeCN5E by Tanenbaum & Wetherall, Pearson Education-

15、Prentice Hall and D. Wetherall, 2011Hamming code gives a simple way to add check bits and correct up to a single bit error:Check bits are parity over subsets of the codewordRecomputing the parity sums (syndrome) gives the position of the error to flip, or 0 if there is no error(11, 7) Hamming code a

16、dds 4 check bits and can correct 1 errorError Correction Convolutional codesCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Operates on a stream of bits, keeping internal stateOutput stream is a function of all preceding input bitsBits are decoded with the Viterb

17、i algorithmPopular NASA binary convolutional code (rate = ) used in 802.11 1 1 10 1 11 0 1Error Detection Parity (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Parity bit is added as the modulo 2 sum of data bitsEquivalent to XOR; this is even parityEx: 11100

18、00 11100001 Detection checks if the sum is wrong (an error)Simple way to detect an odd number of errorsEx: 1 error, 11100101; detected, sum is wrongEx: 3 errors, 11011001; detected sum is wrongEx: 2 errors, 11101101; not detected, sum is right!Error can also be in the parity bit itselfRandom errors

19、are detected with probability Error Detection Parity (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Interleaving of N parity bits detects burst errors up to N Each parity sum is made over non-adjacent bitsAn even burst of up to N errors will not cause it to f

20、ail Error Detection Checksums CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Checksum treats data as N-bit words and adds N check bits that are the modulo 2N sum of the wordsEx: Internet 16-bit 1s complement checksumProperties:Improved error detection over parit

21、y bitsDetects bursts up to N errorsDetects random errors with probability 1-2NVulnerable to systematic errors, e.g., added zerosError Detection CRCs (1) Adds bits so that transmitted frame viewed as a polynomial is evenly divisible by a generator polynomialCN5E by Tanenbaum & Wetherall, Pearson Educ

22、ation-Prentice Hall and D. Wetherall, 2011Start by adding 0s to frame and try dividing Offset by any reminder to make it evenly divisibleError Detection CRCs (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Based on standard polynomials:Ex: Ethernet 32-bit CRC

23、is defined by:Computed with simple shift/XOR circuitsStronger detection than checksums:E.g., can detect all double bit errorsNot vulnerable to systematic errorsElementary Data Link ProtocolsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Link layer environment Ut

24、opian Simplex Protocol Stop-and-Wait Protocol for Error-free channel Stop-and-Wait Protocol for Noisy channel Link layer environment (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Commonly implemented as NICs and OS drivers; network layer (IP) is often OS sof

25、twareLink layer environment (2)Link layer protocol implementations use library functionsSee code (protocol.h) for more detailsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011GroupLibrary FunctionDescriptionNetwork layerfrom_network_layer(&packet)to_network_layer(

26、&packet)enable_network_layer()disable_network_layer()Take a packet from network layer to sendDeliver a received packet to network layerLet network cause “ready” eventsPrevent network “ready” eventsPhysical layer from_physical_layer(&frame)to_physical_layer(&frame)Get an incoming frame from physical

27、layerPass an outgoing frame to physical layerEvents & timerswait_for_event(&event)start_timer(seq_nr)stop_timer(seq_nr)start_ack_timer()stop_ack_timer()Wait for a packet / frame / timer eventStart a countdown timer runningStop a countdown timer from runningStart the ACK countdown timerStop the ACK c

28、ountdown timerUtopian Simplex ProtocolCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011An optimistic protocol (p1) to get us startedAssumes no errors, and receiver as fast as senderConsiders one-way data transferThats it, no error or flow control Sender loops blas

29、ting framesReceiver loops eating framesStop-and-Wait Error-free channelCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Protocol (p2) ensures sender cant outpace receiver:Receiver returns a dummy frame (ack) when readyOnly one frame out at a time called stop-and-w

30、aitWe added flow control! Sender waits to for ack after passing frame to physical layerReceiver sends ack after passing frame to network layerStop-and-Wait Noisy channel (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011ARQ (Automatic Repeat reQuest) adds error

31、controlReceiver acks frames that are correctly deliveredSender sets timer and resends frame if no ack)For correctness, frames and acks must be numberedElse receiver cant tell retransmission (due to lost ack or early timer) from new frameFor stop-and-wait, 2 numbers (1 bit) are sufficientStop-and-Wai

32、t Noisy channel (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Sender loop (p3):Send frame (or retransmission)Set timer for retransmissionWait for ack or timeoutIf a good ack then set up for the next frame to send (else the old frame will be retransmitted)Sto

33、p-and-Wait Noisy channel (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Receiver loop (p3):Wait for a frameIf its new then take it and advance expected frameAck current frameSliding Window ProtocolsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hal

34、l and D. Wetherall, 2011Sliding Window concept One-bit Sliding Window Go-Back-N Selective Repeat Sliding Window concept (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Sender maintains window of frames it can sendNeeds to buffer them for possible retransmissio

35、nWindow advances with next acknowledgementsReceiver maintains window of frames it can receiveNeeds to keep buffer space for arrivalsWindow advances with in-order arrivalsSliding Window concept (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011A sliding window ad

36、vancing at the sender and receiverEx: window size is 1, with a 3-bit sequence number. At the startFirst frame is sentFirst frame is receivedSender gets first ackSenderReceiverSliding Window concept (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Larger windows

37、 enable pipelining for efficient link useStop-and-wait (w=1) is inefficient for long linksBest window (w) depends on bandwidth-delay (BD)Want w 2BD+1 to ensure high link utilizationPipelining leads to different choices for errors/bufferingWe will consider Go-Back-N and Selective RepeatOne-Bit Slidin

38、g Window (1)Transfers data in both directions with stop-and-waitPiggybacks acks on reverse data frames for efficiencyHandles transmission errors, flow control, early timersCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011. . .Each node is sender and receiver (p4):

39、Prepare first frameLaunch it, and set timerOne-Bit Sliding Window (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011. . .If a frame with new data then deliver itWait for frame or timeout(Otherwise it was a timeout)If an ack for last send then prepare for next da

40、ta frameSend next data frame or retransmit old one; ack the last data we receivedTwo scenarios show subtle interactions exist in p4:Simultaneous start right causes correct but slow operation compared to normal left due to duplicate transmissions.TimeNormal caseCorrect, but poor performanceOne-Bit Sl

41、iding Window (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Notation is (seq, ack, frame number). Asterisk indicates frame accepted by network layer .Go-Back-N (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Receiver on

42、ly accepts/acks frames that arrive in order:Discards frames that follow a missing/errored frameSender times out and resends all outstanding framesGo-Back-N (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Tradeoff made for Go-Back-N:Simple strategy for receiver

43、; needs only 1 frameWastes link bandwidth for errors with large windows; entire window is retransmittedImplemented as p5 (see code in book)Selective Repeat (1)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Receiver accepts frames anywhere in receive windowCumula

44、tive ack indicates highest in-order frameNAK (negative ack) causes sender retransmission of a missing frame before a timeout resends windowSelective Repeat (2)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Tradeoff made for Selective Repeat:More complex than Go-

45、Back-N due to buffering at receiver and multiple timers at senderMore efficient use of link bandwidth as only lost frames are resent (with low error rates)Implemented as p6 (see code in book)Selective Repeat (3)CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011For

46、correctness, we require:Sequence numbers (s) at least twice the window (w)OriginalsOriginalsRetransmitsRetransmitsError case (s=8, w=7) too few sequence numbersCorrect (s=8, w=4) enough sequence numbersNew receive window overlaps old retransmits ambiguousNew and old receive window dont overlap no ambiguityExample Data Link ProtocolsCN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011Packet over SONET PPP (Point-to-Point Protocol) ADSL (Asymmetric Digital Subscriber Loop) Packet over SONETCN5E by Tanenbaum & Weth