1、College of Computer Science Chongqing University,Contents,3.0 Definition and Concept3.1 Data Link Layer Design Issues3.2 Error Detection and Correction3.3 Elementary Data Link Protocols3.4 Sliding Window Protocols and ARQS3.5 Example Data Link Protocols3.6 Summary,3.0 Definition and Concept,The data
2、 link layer provides the functional and procedural means to transfer data between network entities and might provide the means to detect and possibly correct errors that may occur in the physical layer,especially to transfers data between adjacent network nodes in a wide area network or between node
3、s on the same local area network segment.,Originally,this layer was intended for point-to-point and point-to-multipoint media,characteristic of wide area media in the telephone system,(1)Data Link Layer Definition:(No ISO Definition)Purpose:,(2)Link:Physical Link,3.0 Definition and Concept,Node:host
4、s,switches,bridges,routersLink:communication channels that connect adjacent nodes along communication path are linkswired linkswireless linksLANs,data-link layer has responsibility of transferring datagram from one node to adjacent node over a link,(3)Data Link:Logical Link,(4)Frame:Header+Payload(D
5、ata From Upper Layer),Data Link/Logical Link=(Physical)Link+Data Link Layer Protocol,3.0 Definition and Concept,3.0 Definition and Concept,Placement of the data link paotocol,3.1 Data Link Layer Design Issues,3.1.1 Services provided to The Network Layer,Unacknowledged connectionless service Acknowle
6、dged connectionless service Acknowledged connection-oriented service,Concept(1)Acknowledged vs.Unacknowledged(2)Connection-oriented vs.Connectionless,Features:(1)No Connection Between Sender and Receiver(2)Receiver doesnt send back the reply messages when received the frame(3)The upper layer deals w
7、ith the transmission errorsUsages:(1)Appropriate when the error rate is very low(2)Appropriate for real-time traffic,such as real-time voice(3)most LANS,Unacknowledged connectionless service,Features:(1)Unacknowledged connectionless service+Acknowledged Service(2)Receiver sends back the reply messag
8、es when received the frame(3)Sender adopts the timeout mechanism to deal with the reply messages sender sends the frame again if it doesnt receive the reply messages in time Usages:(1)unreliable channels with not high reliability(2)Wireless systems,Acknowledged connectionless service,Features:(1)1st
9、 step:establish a connection between sender and receiver(2)2nd step:keep connect,transmit the frames between sender and receiver Receiver sends back the reply messages when received frame sender adopts the timeout mechanism to handle the reply messages(3)3rd step:release connection Service Primitive
10、s:(1)DL-CONNECT.request,DL-CONNECT.indication,DL-CONNECT.response,DL-CONNECT.confirm(2)DL-DATA.request,DL-DATA.indication(3)DL-DISCONNECT.request,DL-DISCONNECT.indication,Usages:A reliable bit stream,Acknowledged connection-oriented service,Methods of breaking the bit stream up into a frame:(1)Time
11、Gaps(2)Character count(3)Flag bytes with byte stuffing(4)Starting and ending flags with bit stuffing(5)Physical layer coding violation(6)Hybrid method:Ethernet,802.11,3.1.2 Framing,Character Count,Example:DDCMP(Digital data Communication Message Protocol,(a)A frame delimited by flag bytes.(b)Four ex
12、amples of byte sequences before and after stuffing.,Flag Bytes with Byte Stuffing,Example:BSC(Binary Synchronous Communication,Bisync,IBM)PPP(Point-to Point Protocol,IETF,SLIP),Bit stuffing(a)The original data(b)The data as they appear on the line(c)The data as they are stored in receivers memory af
13、ter destuffing,Starting and Ending Flags with Bit stuffing,Example:SDLC(Synchronous Data Link Control protocol,IBM)HDLC(High-level Data link Control,ISO),Flash,Physical layer coding violation,(1)Manchester Code,(2)4B/5B Code,Violation Code,Starting Flag/Ending Flag,Violation Code 00001:Starting Flag
14、 10000:Ending Flag,3.1.3 Error Control,Error-Detecting damaged(Error-Detecting Codes)out of order(sequence numbers)Duplicated(Sequence numbers)Lost(timer at sender,timeout mechanism)Error-Correcting Retransmission:Automatic Repeat reQuest(ARQ),Other Error-Correction Codes(FEC Forward Error Correctio
15、n),Two approachesFeedback-based flow control(used at DLL)Rate-based flow control(not suitable for DLL),3.1.4 Flow Control,A set of procedures to coordinate the amount of data to send/receive(1)the processing speed at receiver is limited(2)the buffer of receiver has a limited size(3)the receiver must
16、 be able to inform the sender to halt or slowdown the sending(4)the sender must follow the indication from the receiver to control its sending,Figure,Single-bit error,Burst errors,3.2 Error Detection and Correction,Bit errors mode Isolated errors/Burst errors,multiple-bit errors,block coding,(2)Stru
17、cture of the reliable communication system,(3)Error-detecting codesParity checkChecksumsConstant Ratio CodePositive and negative coding CRC(Cyclic Redundancy Check)(4)Error-correcting codes Hamming codesBinary convolutional codesReed-Solomon codesLow-density Parity Check Codes,Error-detecting/correc
18、ting Codes,(5)Parity Checks,Odd number errors can be detected if errors occur in some line(row/column)Odd number errors can be corrected if errors occur in some line(row/column),except 4,8,12.error places locat at vertexes can be used to detect the burst errors,Even parity Check:Cn-1Cn-2C00Odd parit
19、y Check：Cn-1Cn-2C01,Odd number errors can be detectedEven number errors cant be detected,Two Dimension Parity Checks,Simple Parity Check,(6)Checksum,The message is divided into 16-bit wordsThe value of the checksum word is set to 0All words including the checksum are added using ones complement addi
20、tion,(4)The sum is complemented and becomes the checksumThe checksum is sent with the data,To treat bit strings as representations of polynomials with coefficients of 0 and 1 only.A k-bit frame is regarded as the coefficient list for a polynomial with k terms,ranging from x(k-1)to 1(x0).For example,
21、110001 x5+x4+1.Polynomial arithmetic is done modulo 2,according to the rules of algebraic field theory.There are no carries for addition or borrows for subtraction.Both addition and subtraction are identical to exclusive OR.,(7)Polynomial code or CRC(Cyclic Redundancy Check),身份证,Let r be the degree
22、of G(x).Divide the bit string corresponding to G(x)into the bit string corresponding to M(x)xr,using modulo 2 division,i.e.r(x)=M(x)xr/G(x)Subtract the remainder from the bit string corresponding to M(x)xr using modulo 2 subtraction.The result is the checksummed frame to be transmitted.Call its poly
23、nomial T(x)=.M(x)xr+r(x)Clearly,T(x)is divisible(modulo 2)by G(x).,Polynomial code or CRC(Cyclic Redundancy Check),When the receiver gets the checksummed frame represented by T(X),it tries dividing it by G(x).If there is a remainder,there has been a transmission error,Polynomial code or CRC,errors d
24、etection ability-CRC16=17 burst errors:99.9969%16 burst errors:100%,Hamming distance between two pairs of words,d(000,011)=2d(10101,11110)=3,Hamming Distance,Minim Hamming Distance,(8)Hamming Distance and Hamming Code,dmin=s+1,the detection of up to s errors in all cases,dmin=2t+1,The correction of
25、up to t errors in all cases,dmin s+t,dmin=s+t+1(st),The detection of up to s errors and the correction of up to t errors in all cases,Hamming Code,Let m be the length of transmitted messages Let r be the number of check bits or the redundancy bitsThen,the length of code is m+r,2r m+r+1,To design a c
26、ode with m message bits and r check bits that will allow all single errors to be correctedThen,there is,m=4,r=3m=11,r=4,r1=bits 1,3,5,7,9,11r2=bits 2,3,6,7,10,11,r4=bits 4,5,6,7r8=bits 8,9,10,11,Hamming Code,Hamming Code,3.3 Stop-and-Wait Data Link Protocol,An Unrestricted Simplex Protocol(Utopian S
27、implex Protocol)A Simplex Stop-and-Wait Protocol for Error-free Channel(Error-Free Channel+Rate Matching)A Simplex Protocol for a Noisy Channel(Noisy Channel+Rate Matching)A Stop-and-Wait Protocol for Actual applicationPerformance Analysis of the Simplex Stop-and-Wait ARQ Protocol,3.3.1 An Unrestric
28、ted Simplex Protocol,Data are transmitted in one direction onlyBoth the transmitting and receiving network layers are always ready Processing time can be ignoredInfinite buffer space is available The communication channel between the data link layers never damages or loses frames,No Flow ControlNo E
29、rror Control,3.3.2 A Simplex Stop-and-Wait Protocol,Data are transmitted in one direction onlyThe communication channel between the data link layers never damages or loses framesBut receivers processing rate is slower than the senders,and has finite buffer space,How to prevent the sender from floodi
30、ng the receiver?The sender insert a delay to slow itself downThe receiver provide feedback to the sender(stop-and-wait),No Error Control+Flow Control,3.3.3 A Simplex Protocol for a Noisy Channel,Frame is damaged in transit Frame is lost Acknowledgement frame is lost,ARQ protocol,Are all problems res
31、olved?(No.the sequence.),Error Control+Flow Control,Frame Error,Normal,Error,Frame is damaged in transit Frame is lost Acknowledgement frame is lostDuplicated Data Frame,Error Control Flow ControlDual Communication,3.3.4 A Stop-and-Wait Protocol for Actual Application,Frame Lost,Frame Lost:retransmi
32、ssion,ACK Lost:retransmission,Necessary,why?,R=0,Delayed ACK,ACK must be numbered,why?,Bidirectional transmission,Flash,SenderReceiver,Receiversender,SenderReceiver,Receiversender,Piggybacking:Dual Communication,Problem:How long should the data link layer wait for a packet onto which to piggyback th
33、e acknowledgement,Simplex transmission full-duplex transmission,3.3.4 5 Performance analysis,tf=Lf/C tout=tp+tpr+ta+tp+tpr(Usually,tpr tp,ta tp)tout=2tp tT=tf+tout=tf+2 tp,Assuming error-free transmission of ACK and NAKframes,and assuming independence for each frame transmissionThen the probability
34、of requiring exactly k attempts to successfully receive a given frame is pk=pk(1-p),k=1,2,3,(where p is the frame error probability)The average number of transmissions Nt that are required before a frame is accepted by the receiver is then given by,The average overall transmission time Tv for an acc
35、epted frame,is then given by,The average number of retransmissions Nr for an accepted frame is Nt-1,which is,Propagation time delay:Path length/Propagation RateTransmission time delay:The Frame Size/Transmission Rateto send the 1000bit frame by a 50kbps satellite channel with a 500msec round-trip pr
36、opagation time delay Td:Total time delay of one frame transmitted successfully by the Stop-and-Wait protocol Td=1000/50K*1000+500=520At t=0 msec:sending the first frame.At t=20 msec:the frame being completely sent.At t=270 msec:the frame arrived at the receiver.At t=520 msec:the acknowledgement arri
37、ved back at the sender Transmission Efficiency Rate=20/520 Conclusion:The long round-trip time can have important implications for the efficiency of the bandwidth utilization,The Stop-and-Wait Protocol is not suitable for satellite channel,ARQ:Automatic Repeat reQuest PAR:Positive Acknowledgement wi
38、th Retransmission A one-bit Sliding Protocol:Stop-and-Wait Protocol Continual ARQ Protocol:Go-Back-N Selective ARQ,(2)Sliding Window Protocol be used to describe and implement the ARQs Protocol if WT=1,WR=1 then Sliding Window Protocol=one-bit Stop-and-Wait Protocol if WT 1,WR=1 then Sliding Window
39、Protocol=Continual ARQ if WT 1,WR 1 then Sliding Window Protocol=Selective ARQ,3.4 Sliding Window Protocol and ARQs,3.4.1 Sliding Window Protocols,Basics of sliding window protocol:The Sending Window At any instant of time,the sender maintains a set of sequence numbers corresponding to frames it is
40、permitted to send.These frames are said to fall within the sending windowThe Receiving Window Similarly,the receiver also maintains a receiving window corresponding to the set of frames it is permitted to accept,Allow multiple frames to be in transitReceiver has buffer W longEach frame is numberedAC
41、K includes number of next frame expectedSequence number bounded by size of field(k)Frames are numbered modulo 2k,Figure,Sending Window,The sequence numbers within the senders window represent frames sent but as yet not acknowledged.Used for retransmission.A new packet Updates the upper edge of the s
42、ending window.A new acknowledgement Updates the lower edge of the sending window.If the sending window ever grows to its maximum size,the sending data link layer must disable the network layer until another buffer becomes free.,The receiving data link layers window corresponds to the frames it may a
43、ccept.Any frame falling outside the window is discarded without comment.When a frame whose sequence number is equal to the lower edge of the window is received,it is passed to the network layer,an acknowledgement is generated and the window is rotated by one.The receiving window always remains at it
44、s initial size.,Receiving Window,Flash,The size of sending window is 3 the size of receiving window is 1 2-bit sequence number,Example 1:Sliding Window,WT3；WR1,WT5；WR1;3-bit sequence number,Sending window,Receiving window,Example 2:Sliding Window,3.4.2 Continual ARQ Protocol:Go-Back-N,Senders rule o
45、f actionkeeps transmitting frames continuouslyIf any frames is not acknowledged Tout after the frame is transmitted(or receives its NAK),assume that the frame is lost and retransmit all frames from the lost frameReceivers rule of action Transmits an acknowledge frame to the sender whenever a frame i
46、s delivered without any error If duplicated frame arrives,assume that the previous acknowledgement for the frame is lost(3)Sender must set a timer for each outstanding frame,ACK3,ACK4,Example 1:A Continual ARQ Protocol,(lost or damaged),example in book usually,ack i should be is ack i+1(page 254),Re
47、ceiver receives the data in order,Example 2:A Continual ARQ Protocol,Wt=7 Wr=1,ACK7,sliding the window,waiting,waiting,Go back to 4,sending frame 4,5,6 again,Receiver receives the data in order,Example 3:A Continual ARQ Protocol,Maximum size of the sending window:wt=2n-1,Receiver receives the data i
48、n order,3.4.3 Selective ARQ Protocol,Senders rule of actionkeeps transmitting frames continuouslyIf any frames is not acknowledged Tout after the frame is transmitted(or receives its NAK),assume that the frame is lost and retransmit only the lost frameReceivers rule of action Does the same action as
49、 in the Stop-and-Wait ARQ,but never discard all frames delivered without errors and has the capability to reorder them in the correct order(3)Sender must set a timer for each outstanding frame(4)Wt=Wr,Frame 2 is transmitted only,Frames accepted and acknowledged,time,usually,ack i should be ack i+1(p
50、age 254),Frame 2,3,4,5,6 will passed to layer network in order,Buffered frames,Maximum size of the sending window:wt m/2=2n-1,Example 1:Selective ARQ Protocol,Example 2:Selective ARQ Protocol,3.4 Example Data Link Protocol,Data Link Protocols,Asynchronous Protocols,Synchronous Protocols,XModem,YMode