计算机网络第五版英文版概要1

《计算机网络第五版英文版概要1》由会员分享，可在线阅读，更多相关《计算机网络第五版英文版概要1（61页珍藏版）》请在装配图网上搜索。

1、The Data Link LayerChapter 3TopicsDesign IssuesFramingReliable Transmission1.Error Control2.Flow Control3.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

2、 a 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 sen

4、t 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 is a

5、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 number of charac

6、ters 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 anymore.3.1.2 Fr

7、aming(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 easy to resynchronize

8、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 stuffingafter destuffing3.1.3 Err

9、or 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 ControlPrevents a fast sender from out-paci

10、ng 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 structured redundancy to data so err

11、ors 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 DistanceThe Hamming distance between

12、 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 necessary that the Hamming distance between

13、 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 retransmission.Error ControlSuppose something w

14、ent 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 and RetransmissionWhat if a frame was transmitted

15、 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 reliable channels,such as fiberIn link layer and higher l

16、ayersForward 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(error-correcting codes),to enable the receiver to deduce what

17、 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 are computed solely as a function of mExamples of block codes

18、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 function of the m data bitsExclusive OR(XOR)or modulo 2 addition is a l

19、inear 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 codewordCode rateThe proportion of the data-stream that is useful(non-redu

20、ndant),namely m/nWriting Report(2)1.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-detecting Codes(3)CRCs(1)Algorithm(1)设：m位信息位对应于一个(m1)次多项式M(x)，r位冗余位对应于一个(r-1)次多项式R(x)

21、，生成多项式G(x)是一个r次多项式，码字长n位，n=m+r，对应于一个(n-1)次多项式T(x)。由CRC算法可知，xrM(x)=G(x)Q(x)+R(x)由于R(x)是xrM(x)除以G(x)的余数，所以记为 xrM(x)/G(x)=R(x)发送方在信道上传输：T(x)=xrM(x)+R(x)3.2.2 Error-detecting Codes(4)CRCs(2)Algorithm(2)接收端收到T(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。假设传输中产生错误

22、E(x)，于是，(T(x)+E(x)/G(x)=T(x)/G(x)+E(x)/G(x)=E(x)/G(x)假设E(x)/G(x)0，那么检测出错误，E(x)/G(x)=0，那么漏检。CRCThree International Standards Generator Polynomials3.2.2 Error-detecting Codes(10)CRCs(8)CircuitsComputed with simple shift/XOR circuitsStronger detection than checksumsE.g.,can detect all double bit errors

23、Not 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 software3.3.1 Link layer environment(2)AssumptionsThe layers are independent processesHave set up connection between

24、 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 implementations use library functionsSee code()for more detailsGroupLibrary FunctionDescriptionNetwork layerfrom_netw

25、ork_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 cause“ready”eventsPrevent network“ready”eventsPhysical layer from_physical_layer(&frame)to_physical_layer(&frame)Get a

26、n 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()Wait for a packet/frame/timer eventStart a countdown timer runningStop a countdown timer from runningStart the ACK coun

27、tdown 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 one-way data transferThe essence of this protocol(p1)Sender loops blasting frames,and receiver loops eating frames.Thats it,no err

28、or 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 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 ph

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

30、ectness,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 sufficientSet timer for retransmissionIf a good ACK then set up for the next frame to send(else the old frame will be retransmitted)Wait f

31、or 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(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

32、(1)Sender maintains window of frames it can sendNeeds to buffer them for possible retransmissionWindow advances with next acknowledgementsReceiver maintains window of frames it can receiveNeeds to keep buffer space for arrivalsWindow advances with in-order arrivalsAt the startFirst frame is sentSend

33、er gets first ACKSenderReceiverFirst frame is received3.4.1 Sliding Window concept(2)A sliding window advancing at the sender and receiverEx:window 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 ineffic

34、ient 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 Repeat3.4.2 One-Bit Sliding Window(1)Transfers data in both directions with stop-and-waitPiggy

35、backs ACKs on reverse data frames for efficiencyHandles transmission errors,flow control,early timersEach node is sender and receiver(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 tim

36、eout)If an ACK for last send then prepare for next data frameSend next data frame or retransmit old one;ACK the last data 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

37、 to duplicate transmissionsTimeNormal caseCorrect,but poor performanceNotation is(seq,ack,frame number).Asterisk indicates 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 r

38、esends all outstanding frames3.4.3 Go-Back-N(2)Tradeoff made for Go-Back-NSimple strategy for receiver;needs only 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)发送窗口大小的上界(1)定理：对于帧序号位数为n的退后n帧协议，其

39、发送窗口大小wT必满足wT2n-1。证：设接收窗口大小为wR，由退后n帧协议 可 知，wR=1。帧序号为n 帧序号空间是mod 2n 显然，在wT范围内序号不应重叠，否那么产生二义性。3.4.3 Go-Back-N(3)发送窗口大小的上界(2)证续：又 当且仅当对发送窗口上限帧序号确实认帧正在返回途中时，总存在wR+wT覆盖范围最大，且wR+wT范围内帧序号不重叠。于是，wR+wT 2n 当wR=1时，有 wT2n 1 成立 证毕3.4.4 Selective Repeat(1)Receiver accepts frames anywhere in receive windowCumulati

40、ve ACK indicates highest in-order frameNAK(negative ACK)causes sender retransmission of a missing 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 o

41、f link bandwidth as only lost frames are resent(with low error rates)Implemented as p6(see 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 a

42、nd 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

43、 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 R

44、epeat(4)滑动窗口大小的上界(1)定理：设发送窗口大小wT，接收窗口大小wR。对于帧序号位数为n的选择重发协议，其接收窗口的最大值wR必满足wRwT2n-1。证：帧序号为n 帧序号空间是mod 2n 显然，在wT范围内序号不应重叠，否那么产生二义性。又 当且仅当对发送窗口上限帧序号确实认帧正在返回途中时，总存在wR+wT覆盖范围最大，且wR+wT范围内帧序号不重叠。3.4.4 Selective Repeat(5)滑动窗口大小的上界(1)证续：于是，wR+wT2n 又 wRwT无意义 至多wR=wT 不失一般性，令wR=wT 故有wRwT2n/2=2n-1 成立 证毕Problems:2

45、1,23,26,283.5 Example Data Link Protocols3.5.1 Packet over SONET(1)Packet over SONET is the method used to carry IP packets over SONET optical fiber links Uses PPP(Point-to-Point Protocol)for framingProtocol stacksPPP frames may be split over SONET payloads3.5.1 Packet over SONET(2)PPP(1)PPP(Point-t

46、o-Point Protocol)is a general method for delivering packets across linksFraming uses a flag(0 x7E)and byte stuffing“Unnumbered mode(connectionless unacknow-ledged service)is used to carry IP packetsErrors are detected with a checksumIP packet0 x21 for IPv43.5.1 Packet over SONET(3)PPP(2)A link contr

47、ol protocol brings the PPP link up/downFinite state machine for link control3.5.2 ADSL(1)Widely used for broadband Internet over local loopsADSL runs from modem(customer)to DSLAM(ISP)IP packets are sent over PPP and AAL5/ATM(over)3.5.2 ADSL(2)PPP data is sent in AAL5 frames over ATM cellsATM is a link layer that uses short,fixed-size cells(53 bytes);each cell has a virtual circuit identifierAAL5 is a format to send packets over ATMPPP frame is converted to a AAL5 frame(PPPoA)AAL5 frame is divided into 48 byte pieces,each of which goes into one ATM cell with 5 header bytes EndChapter 3