計算機網(wǎng)絡(luò)第五版(英文版) 概要1

1、The Data Link LayerChapter 3TopicsDesign IssuesFramingReliable Transmission Error Control Flow Control Six ProtocolsProtocols of data link layerHDLCPPPDesign Issues of Data Link Layer Services Provided to the Network LayerFramingError ControlFlow ControlFunctions of the Data Link Layer1. Providing a

2、 well-defined service interface to the network layer.2. Dealing with transmission errors.3. Regulating the flow of data so that slow receivers are not swamped by fast senders.Actual data pathVirtual data pathNetworkLinkPhysical3.1 The Data Link Layer Design IssuesResponsible for delivering frames of

3、 information over a single linkHandles transmission errors and regulates the flow of data3.1.1 Service Provider to the Network Layer Possible ServicesUnacknowledged connectionless serviceFrame is sent with no connection / error recoveryEthernet is exampleAcknowledged connectionless serviceFrame is s

4、ent with retransmissions if neededAcknowledged connection-oriented serviceConnection is set up; rare3.1.2 FramingThe physical layer doesnt do much: it just pumps bits from one end to the other. But things may go wrongThe data link layer needs a means to do retransmissions. The unit of retransmission

5、 is a frame (which is just a fixed number of bits).Four methods for breaking up a bit stream into frames: Byte count , Flag bytes with byte stuffing, Starting and ending flags with bit stuffing and Physical layer coding violations. Byte countThis method uses a field in the header to specify the numb

6、er of characters in the frame. When the data link layer at the destination sees the byte count, it knows how many characters follow and hence where the end of the frame is. The trouble with this algorithm is that the count can be garbled by a transmission error.The byte count method is rarely used a

7、nymore. 3.1.2 Framing (1)Byte count Frame begins with a count of the number of bytes in itSimple, but difficult to resynchronize after an errorErrorcaseExpectedcase3.1.2 Framing (2)Byte stuffing Special flag bytes delimit frames; occurrences of flags in the data must be stuffed (escaped)Longer, but

8、easy to resynchronize after errorStuffingexamplesFrameformatNeed to escape extra ESCAPE bytes too!3.1.2 Framing (3)Bit stuffingFrame flag has six consecutive 1s (not shown)On transmit, after five 1s in the data, a 0 is addedOn receive, a 0 after five 1s is deletedData bitsTransmitted bitswith stuffi

9、ngafter destuffing3.1.3 Error ControlTwo kinds of error control strategiesARQ (Automatic Repeat reQuest)Use error-detecting codesSent ACK/NAK on the two-way channelConfigure fame buffer and timer on the senderFEC (Forward Error Correction)Use error-correcting codesProblems: 13.1.4 Flow ControlPreven

10、ts a fast sender from out-pacing a slow receiverFeedback-based flow control: receiver gives feedback on the data it can acceptDiscuss in the Link layerRate-based flow control: the protocol has a built-in mechanismDiscuss in the Transport layer3.2 Error Detection and Correction (1)Error codes add str

11、uctured redundancy to data so errors can be either detected, or correctedError correction codesHamming codesBinary convolutional codesReed-Solomon and Low-Density Parity Check codesMathematically complex, widely used in real systemsError detection codesParityChecksumsCyclic redundancy codesHamming D

12、istanceThe Hamming distance between two frames a and b is the number of bits at the same position that differ.To detect all sets of d or fewer errors, it is necessary and sufficient that the Hamming distance between any two frames is d+1 or more.To correct all sets of d or fewer errors, it is necess

13、ary that the Hamming distance between any two frames is 2d+1 or moreError Detection and Correction (2)Error Detection and Retransmission: to include only enough redundancy to allow the receiver to deduce that an error occurred, but not which error (error-detecting codes), and have it request a retra

14、nsmission. Error ControlSuppose something went wrong during frame transmission. How do we actually notice that somethings wrong, and can it be corrected by the receiver? = Acknowledgment, Error Detection and Error CorrectionSuppose the packet was lost on the way. How do the sender notice it? =Timers

15、 and RetransmissionWhat if a frame was transmitted multiple times? =Sequence Numbers for every frame.3.2 Error Detection and Correction (2)Two types of error control mechanismAutomatic Repeat reQuest (ARQ) or Positive Acknowledgement with Retransmission)Use error detection codesBe used on highly rel

16、iable channels, such as fiberIn link layer and higher layersForward Error Correction (FEC)Use error correction codesBe used on noise channels, such as wireless linkIn physical layer and link layerForward Error Correction: to include enough redundant information along with each block of data sent (er

17、ror-correcting codes), to enable the receiver to deduce what the transmitted data must have been. 3.2.1 Error-Correcting Codes (1)A frame consists of m data bits and r redundant bitsBlock codeBlock codes refers to the large and important family of error-correcting codes that encode data in blocks r

18、are computed solely as a function of mExamples of block codes are ReedSolomon codes, Hamming codes, and etc.These examples also belong to the class of linear codes, and hence they are called linear block codes 3.2.1 Error-Correcting Codes (2)Linear codeThe r check bits are computed as a linear funct

19、ion of the m data bitsExclusive OR (XOR) or modulo 2 addition is a linear functionExamples of block codes are parity codes, hamming codes, ReedSolomon codes, low-density parity-check codes, and etc.3.2.1 Error-Correcting Codes (3)CodewordLet the total length of a block be n (n=m+r)Referred as n-bit

20、codewordCode rateThe proportion of the data-stream that is useful (non-redundant), namely m/nWriting Report (2)Detail describe convolutional code, Reed-Solomon (RS) code, and Low-Density Parity Check (LDPC), including their mathematic foundations, encoding and decoding methods, etc.CRC3.2.2 Error-de

21、tecting Codes (3)CRCs (1)Algorithm (1) 設(shè)：m位信息位對應(yīng)于一個(m1)次多項式M(x)，r位冗余位對應(yīng)于一個(r-1)次多項式R(x)，生成多項式G(x)是一個r次多項式，碼字長n位，n=m+r，對應(yīng)于一個(n-1)次多項式T(x)。 由CRC算法可知， xrM(x)=G(x)Q(x)+R(x) 由于R(x)是xrM(x)除以G(x)的余數(shù)，所以記為 xrM(x)/G(x)=R(x) 發(fā)送方在信道上傳輸：T(x)=xrM(x)+R(x)3.2.2 Error-detecting Codes (4)CRCs (2)Algorithm (2) 接收端收到T(

22、x)后除以G(x)，即 T(x)=xrM(x)+R(x) =G(x)Q(x)+R(x)+R(x) =G(x)Q(x) 顯然，T(x)能被G(x)整除，記為T(x)/G(x)=0。 假設(shè)傳輸中產(chǎn)生錯誤E(x)，于是， (T(x)+E(x)/G(x)=T(x)/G(x)+E(x)/G(x) =E(x)/G(x) 假設(shè)E(x)/G(x)0，那么檢測出錯誤，E(x)/G(x)=0，那么漏檢。CRCThree International Standards Generator Polynomials3.2.2 Error-detecting Codes (10)CRCs (8)CircuitsCompu

23、ted with simple shift/XOR circuitsStronger detection than checksumsE.g., can detect all double bit errorsNot vulnerable to systematic errorsProblems: 363.3 Elementary Data Link Protocols3.3.1 Link layer environment (1)Commonly implemented as NICs and OS drivers; network layer (IP) is often OS softwa

24、re3.3.1 Link layer environment (2)AssumptionsThe layers are independent processesHave set up connection between machine A and B, and machine A has an infinite supply of data ready to sendThe machines do not crashThe checksum is done in hardware3.3.1 Link layer environment (3)Link layer protocol impl

25、ementations use library functionsSee code () for more detailsGroupLibrary FunctionDescriptionNetwork layerfrom_network_layer(&packet)to_network_layer(&packet)enable_network_layer()disable_network_layer()Take a packet from network layer to sendDeliver a received packet to network layerLet network cau

26、se “ready” eventsPrevent network “ready” eventsPhysical layer from_physical_layer(&frame)to_physical_layer(&frame)Get an incoming frame from physical 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

27、()Wait for a packet / frame / timer eventStart a countdown timer runningStop a countdown timer from runningStart the ACK countdown timerStop the ACK countdown timer3.3.2 Utopian Simplex ProtocolAn optimistic protocol (p1) to get us startedAssumes no errors, and receiver as fast as senderConsiders on

28、e-way data transferThe essence of this protocol (p1)Sender loops blasting frames, and receiver loops eating frames.Thats it, no error or flow control, so it is unrealistic3.3.3 Stop-and-Wait Error-free channelProtocol (p2) ensures sender cant outpace receiverReceiver returns a dummy frame (ACK) when

29、 readyOnly one frame out at a time called stop-and-waitThe essence of this protocol (p2)Sender waits to for ACK after passing frame to physical layer, and receiver sends ACK after passing frame to network layerWe added flow control! But no error control.3.3.4 Stop-and-Wait Noisy channel (1)ARQ (Auto

30、matic Repeat reQuest) adds error controlReceiver ACKs frames that are correctly deliveredSender sets timer and resends frame if no ACKFor 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

31、 bit) are sufficientSet timer for retransmissionIf a good ACK then set up for the next frame to send (else the old frame will be retransmitted)Wait for ACK or timeoutSend frame (or retransmission)3.3.4 Stop-and-Wait Noisy channel (2)Sender loop (p3)3.3.4 Stop-and-Wait Noisy channel (3)Receiver loop

32、(p3)Wait for a frameIf its new then take it and advance expected frameAck current frameProblems:183.4 Sliding Window Protocols3.4.1 Sliding Window concept (1)Sender maintains window of frames it can sendNeeds to buffer them for possible retransmissionWindow advances with next acknowledgementsReceive

33、r maintains window of frames it can receiveNeeds to keep buffer space for arrivalsWindow advances with in-order arrivalsAt the startFirst frame is sentSender gets first ACKSenderReceiverFirst frame is received3.4.1 Sliding Window concept (2)A sliding window advancing at the sender and receiverEx: wi

34、ndow size is 1, with a 3-bit sequence number3.4.1 Sliding Window concept (3)Larger windows 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

35、 choices for errors/bufferingWe will consider Go-Back-N and Selective Repeat3.4.2 One-Bit Sliding Window (1)Transfers data in both directions with stop-and-waitPiggybacks ACKs on reverse data frames for efficiencyHandles transmission errors, flow control, early timersEach node is sender and receiver

36、 (p4). . .Prepare first frameLaunch it, and set timer3.4.2 One-Bit Sliding Window (2). . .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 data frameSend next data frame or retransmit old one; ACK the last data

37、 we received3.4.2 One-Bit Sliding Window (3)Two scenarios show subtle interactions exist in p4Simultaneous start right causes correct but slow operation compared to normal left due to duplicate transmissionsTimeNormal caseCorrect, but poor performanceNotation is (seq, ack, frame number). Asterisk in

38、dicates frame accepted by network layer .3.4.3 Go-Back-N (1) Receiver only accepts/acks frames that arrive in orderDiscards frames that follow a missing/errored frameSender times out and resends all outstanding frames3.4.3 Go-Back-N (2)Tradeoff made for Go-Back-NSimple strategy for receiver; needs o

39、nly 1 frameWastes link bandwidth for errors with large windows; entire window is retransmittedImplemented as p5 (see code in book)Problems: 203.4.3 Go-Back-N (3)發(fā)送窗口大小的上界 (1) 定理：對于幀序號位數(shù)為n的退后n幀協(xié)議，其發(fā)送窗口大小wT必滿足wT2n-1。 證：設(shè)接收窗口大小為wR，由退后n幀協(xié)議 可 知， wR=1。 幀序號為n 幀序號空間是mod 2n 顯然，在wT范圍內(nèi)序號不應(yīng)重疊，否那么產(chǎn)生二義性。3.4.3 Go-

40、Back-N (3)發(fā)送窗口大小的上界 (2)證續(xù)：又 當(dāng)且僅當(dāng)對發(fā)送窗口上限幀序號確實認(rèn)幀正在返回途中時，總存在wR+wT覆蓋范圍最大，且wR+wT范圍內(nèi)幀序號不重疊。 于是， wR+wT 2n 當(dāng)wR =1時，有 wT2n 1 成立 證畢3.4.4 Selective Repeat (1)Receiver accepts frames anywhere in receive windowCumulative ACK indicates highest in-order frameNAK (negative ACK) causes sender retransmission of a mis

41、sing frame before a timeout resends window3.4.4 Selective Repeat (2)Tradeoff made for Selective RepeatMore complex than Go-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

42、 code in book)3.4.4 Selective Repeat (3)For correctness, we requireSequence numbers (s) at least twice the window (w)OriginalsOriginalsRetransmitsRetransmitsNew receive window overlaps old retransmits ambiguousNew and old receive window dont overlap no ambiguityError case (s=8, w=7) too few sequence

43、 numbersCorrect (s=8, w=4) enough sequence numbersOriginalsOriginalsRetransmitsRetransmitsNew receive window overlaps old retransmits ambiguousNew and old receive window dont overlap no ambiguityError case (s=8, w=7) too few sequence numbersCorrect (s=8, w=4) enough sequence numbersOriginalsOriginalsRetransmitsRetransmitsNew receive window overlaps old retransmits ambiguousNew and old receive window dont overlap no ambiguityError case (s=8, w=7) too few sequence numbersCorrect (s=8, w=4) enough sequence numbers3.4.4 Selective Repeat (4)滑動窗口大小的上界 (1) 定理：設(shè)發(fā)送窗口大小wT ，接收窗口大小wR。對于幀序號位數(shù)為n的選擇重發(fā)協(xié)議，其接