單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,1,The Data Link Layer,(,數(shù)據(jù)鏈路層,),Chapter 3,2,3.1 Data Link Layer Design Issues,Services Provided to the Network Layer,為網(wǎng)絡(luò)層提供的效勞,Framing幀,Error Control過失控制,Flow Control流量控制,3,3.1.1,Services provided to the network layer,Unacknowledged connectionless service無確認(rèn)的無連接效勞,Acknowledged connectionless service 有確認(rèn)的無連接效勞,Acknowledged connection-oriented service 有確認(rèn)的面向連接的效勞,4,Functions of the Data Link Layer,Provide service interface to the network layer,Dealing with transmission errors,Regulating data flow,Slow receivers not swamped by fast senders,5,Functions of the Data Link Layer (2),Relationship between packets and frames.,6,Services Provided to Network Layer,(,a),Virtual communication.,(b),Actual communication.,7,Services Provided to Network Layer (2),Placement of the data link protocol.,8,數(shù)據(jù)鏈路層的簡單模型,局域網(wǎng),廣域網(wǎng),主機,H,1,主機,H,2,路由器,R,1,路由器,R,2,路由器,R,3,網(wǎng),局域網(wǎng),主機,H,1,向,H,2,發(fā)送數(shù)據(jù),鏈路層,應(yīng)用層,運輸層,網(wǎng)絡(luò)層,物理層,鏈路層,應(yīng)用層,運輸層,網(wǎng)絡(luò)層,物理層,鏈路層,網(wǎng)絡(luò)層,物理層,鏈路層,網(wǎng)絡(luò)層,物理層,鏈路層,網(wǎng)絡(luò)層,物理層,R,1,R,2,R,3,H,1,H,2,從層次上來看數(shù)據(jù)的流動,9,數(shù)據(jù)鏈路層的簡單模型( 續(xù),局域網(wǎng),廣域網(wǎng),主機,H,1,主機,H,2,路由器,R,1,路由器,R,2,路由器,R,3,網(wǎng),局域網(wǎng),主機,H,1,向,H,2,發(fā)送數(shù)據(jù),H,1,H,2,僅從數(shù)據(jù)鏈路層觀察幀的流動,鏈路層,應(yīng)用層,運輸層,網(wǎng)絡(luò)層,物理層,鏈路層,應(yīng)用層,運輸層,網(wǎng)絡(luò)層,物理層,鏈路層,網(wǎng)絡(luò)層,物理層,鏈路層,網(wǎng)絡(luò)層,物理層,鏈路層,網(wǎng)絡(luò)層,物理層,R,1,R,2,R,3,10,3.1.2 Framing,Framing method(成幀的方法): 3,1character count字符計數(shù)法 -see fig 3-3,2Starting and ending character,with character stuffing 帶字符填充的首尾界符法 -see fig 3-4,Frame flags: DLE STX(Start Text), DLE ETX(End Text),DLE in data(between flags): DLE->DLE DLE, so that: DLE ETX-> DLE DLE ETX,3Starting and ending flags,with bit stuffing帶位填充的首尾界符法 . -01111110-see fig 3-5,Physical layer coding violation 1->高-低電平對，0->低-高電平對,11,Framing (2),A character stream.,(a),Without errors.,(b),With one error.,12,Framing (3),(,a),A frame delimited by flag bytes.,(b),Four examples of byte sequences before and after stuffing.,13,Framing (4),Bit stuffing,(a),The original data.,(b),The data as they appear on the line.,(c),The data as they are stored in receiver,s memory after destuffing.,14,3.1,DATA LINK LAYER DESIGN ISSUES,3.1.3 Error Control過失控制,Error detection,Error correction,Repeated data frame,Lost frame,Timer,3.1.4 Flow Control流量控制,To solve the problem that a sender wants to transmit frames faster than the receiver can accept them.,Feedback-based flow control,Rate-based flow control,15,3.2 Error Detection and Correction,Error-Correcting Codes糾錯碼,codeword 碼字,Hamming distance (10001001,10110001=>00111000,3),parity bit,糾正d比特錯,需距離為2d+1比特的編碼,Error-Detecting Codes檢錯碼,polynomial codecyclic redundancy code，CRC code,檢測d比特錯,需距離為d+1比特的編碼,16,3.2.1 Error-Correcting Codes (*),Use of a Hamming code to correct burst errors.,17,3.2.2 Error-Detecting Codes,Calculation of the polynomial code checksum,多項式編碼,循環(huán)冗余碼，CRC碼,生成多項式 G(x),計算校驗和的算法：,-see page 197,CRC-12 = x12+x11+x3+x2+x1+1,CRC-16 = x16+x15+x2+1,CRC-CCITT = x16+x12+x5+1,結(jié)論：,具有r檢測位的多項式能夠檢,測所有長度<=r的突發(fā)錯誤,長度大于r+1的錯誤逃脫的,概率為1/2r.,Data,CRC,除法器,余數(shù),0,accept,Not 0,refuse,Data,CRC,Data,000,除法器,CRC,n,位,n+1,位,余數(shù),n,位,Receiver,Sender,CRC,產(chǎn)生器和校驗器,將一個n位的0串追加到數(shù)據(jù)單元,n的值為預(yù)先約定的除數(shù)位數(shù)減1，即除數(shù)為n+1位。,用除數(shù)去除組成的新數(shù)，除的方法是二進制除法，所得的余數(shù)即為CRC。,將由第二步得出n位的CRC替換數(shù)據(jù)單元末尾追加的n個0。,數(shù)據(jù)單元的數(shù)據(jù)局部先到達接收方，然后 是CRC到達。接收方將這些都看作是一個字串并用找出CRC余數(shù)所用的同一個除數(shù)去除這個字串。,如果到達的字串沒有過失，那么CRC校驗器產(chǎn)生的余數(shù)為0，數(shù)據(jù)單元通過。如果在傳送的過程中字串發(fā)生改變，相除的結(jié)果就產(chǎn)生一個非0的余數(shù)，數(shù)據(jù)單元就不能通過。,20,1101010110,Q,商,除數(shù),P,2,n,M,被除數(shù),110101,111011,110101,111010,110101,111110,110101,101100,110101,110010,110101,01110,R,余數(shù),循環(huán)冗余檢驗的原理說明,21,3.3 Elementary Data Link Protocols,An Unrestricted Simplex Protocol一種無限制的單工協(xié)議,A Simplex Stop-and-Wait Protocol一種單工的停-等協(xié)議,A Simplex Protocol for a Noisy Channel有噪聲信道的單工協(xié)議,進程(process)、分組(packet)和幀(frame),wait_for_event(&event), 3 events:,frame_arrival: Received correct frame,cksum_err: Received frame with checksum error,timeout: Timeout when waiting acknowledgement,An Unrestricted Protocol,A simplex Stop-and-Wait Protocol,Premise：Error free and traffic simplex,Sender：,1Get data frame from host；,2send to buffer of data link；,3forward the data frame；,4waiting；,5Acknowledge from receiver, get new data frame from host, then go to step2。,Receiver：,1Waiting；,2get the data frame from sender, put it into receiving buffer;,3transfer data frame to host；,4send a message to sender, tell it the data frame has been forwarded to the host,5go to step(1)。,A simplex protocol for a Noisy Channel,A positive stop-and-wait protocol,sender：,1get data frame from host to buffer。,2V(S)0。發(fā)送狀態(tài)變量初始化,3N(S)V(S)；將發(fā)送狀態(tài)變量的數(shù)值寫入發(fā)送序號,4send it on its way。,5initialize timer。選擇適當(dāng)?shù)某瑫r重傳時間tout ,6waiting等待以下3個事件中最先出現(xiàn)的一個,7if get the ACK，then：,get a new frame from the host ；,V(S)1 V(S)；更新發(fā)送狀態(tài)變量，變?yōu)橄乱粋€序號,go to step(3)。,8if get the NAK，then go to step(4)。重傳數(shù)據(jù)幀,9if time out，then go to step(4)。重傳數(shù)據(jù)幀,receiver：,1V(R)0。 接收狀態(tài)變量初始化，其數(shù)值等于欲接收的數(shù)據(jù)幀的發(fā)送序號,2waiting。,3if frame arrives, then chsum-error當(dāng)收到一個數(shù)據(jù)幀，就檢查有無產(chǎn)生傳輸過失(如用CRC)。,if no mistake，continue；,otherwise go to step(8)。,4if N(S) = V(R)，then continue； 收到發(fā)送序號正確的數(shù)據(jù)幀,otherwise lost the frame，go to step(7)。,5Pass the date to the host。,6V(R)1 V(R)。 更新接收狀態(tài)變量，準(zhǔn)備接收下一個數(shù)據(jù)幀,7send a ACK to sender，go to step(2)。,8send a NAK to sender，go to step(2)。,32,33,3.4 Sliding Window Protocols滑動窗口協(xié)議,Bidirectional transmission, piggybacking捎帶, better use of available bandwidth,slide window,sending window: a set of sequence numbers corresponding to frame it is permitted to send for sender,receiving window: corresponding to the set of frames which is permitted to accept for receiver,34,Sliding Window Protocols (2),A One-Bit Sliding Window Protocol,A Protocol Using Go Back N后退n幀,A Protocol Using Selective Repeat選擇性重傳,35,Sliding Window Protocols (3),A sliding,window of size 1, with a,3-bit sequence number,.,(a),Initially.,(b),After the first frame has been sent.,(c),After the first frame has been received.,(d),After the first acknowledgement has been received.,36,37,A One-Bit Sliding Window Protocol (2),Two scenarios for protocol 4.,(a),Normal case.,(b),Abnormal case. The notation is (,seq, ack, packet number,). An asterisk,(*),indicates where a network layer accepts a packet.,38,39,3.4.2 A Protocol Using Go Back N,Pipelining and error recovery. Effect on an error when,(a),Receiver,s window size is 1.,(b),Receiver,s window size is large.,40,回退ngo back n,41,Sliding Window Protocol Using Go Back N (2),接收窗口大小為,W=1,拋棄所有后續(xù)的幀,最多允許有,MAX_SEQ,幀未被確認(rèn),Stop-and-wait is not fitful for channel which has long round-trip delay, e.g. Satellite channel,270 ms,Bidirectional transmission, noisy channel,Discard restricted condition: network layer of sender has unlimited data to transmit,size of receiving window = 1, receiver discards all subsequent frames after a damaged or lost data frame.,42,Sliding Window Protocol Using Go Back N (3),MAX_SEQ+1,distinct sequence numbers(0,1,2,.,MAX_SEQ),no more than MAX_SEQ unacknowledged,frames,the sender window,<=,MAX_SEQ,.,Why?,Consider the following scenario with MAX_SEQ=7(a sender,window of size eight,),:,The sender sends frames 0 through 7.,A piggybacked acknowledgement for frame 7 eventually comes back to the sender.,The sender sends another eight frames,again with sequence numbers 0 through 7.,All eight frames belonging to the second batch get lost,All eight frames belonging to the second batch arrive successfully.,Another piggybacked acknowledgement for frame 7 come in, ambiguity will arise to sender:,All eight frames belonging to the second batch get,lost,ack=7,All eight frames belonging to the second batch arrive,successfully,ack=7,43,Sliding Window Protocol Using Go Back N (4),A Protocol Using Go Back n,(,when the size of sender window=7,no ambiguity,:,The sender sends frames 0 through 6,A piggybacked acknowledgement for frame 6 eventually comes back to the sender,The sender sends another 7 frames:7,0,1,2,3,4,5,Frame 7,0,1,2,3,4,5 belonging to the second batch get lost,Frame 7,0,1,2,3,4,5 belonging to the second batch arrive,Another piggybacked ack nowledgement comes in,no ambiguity,Frame 7,0,1,2,3,4,5,belonging to the second batch get,lost,ack=6,Frame 7,0,1,2,3,4,5 belonging to the second batch,arrive,ack=5,the problem,:,Since a sender may have to retransmit all the unacknowledged frames at a future time ,it must hang on to all transmitted frames until it knows for sure that they have been accepted by the receiver.,No acknowledged frames without data.,44,Sliding Window Protocol Using Go Back N (9),Simulation of multiple timers in software.,45,3.4.3 A Sliding Window Protocol Using Selective Repeat,允許接收后續(xù)的幀接收窗口 >1,窗口大小為W<=(MAX_SEQ+1)/2,所需緩沖器的數(shù)量=W,所需計時器的數(shù)量=W,否認(rèn)性確認(rèn)幀-NAK,思考題,46,選擇重傳selective repeat,47,A Sliding Window Protocol Using Selective Repeat (6),(,a),Initial situation with a window size seven.,(b),After seven frames sent and received, but not acknowledged.,(c),Initial situation with a window size of four.,(d),After four frames sent and received, but not acknowledged.,48,2024/9/19,49,Performance：性能比較,Stop-and-wait,慢,只在特定情形有用,Sliding window,快,高速網(wǎng)絡(luò)必須,2024/9/19,50,性能比較的圖示,2024/9/19,51,滑動窗口協(xié)議的重要性,同時發(fā)送,增加了網(wǎng)絡(luò)吞吐量,流控制,如何加速？,Tw = min(B, TG W,where,B ：硬件帶寬,TW ：滑動窗口協(xié)議吞吐量,TG ： 停走協(xié)議吞吐量,W ：窗口大小,52,3.6 Example Data Link Protocols,HDLC High-Level Data Link Control 高級數(shù)據(jù)鏈路控制,The Data Link Layer in the Internet,因特網(wǎng)中的數(shù)據(jù)鏈路層,53,3.6.2 The Data Link Layer in the Internet,A home personal computer acting as an internet host.,54,用戶撥號入網(wǎng)的示意圖,路由器,調(diào)制解調(diào)器,調(diào)制解調(diào)器,因特網(wǎng)效勞提供者(ISP),用戶家庭,撥號 線,使用,TCP/IP,的,PPP,連接,使用,TCP/IP,的,客戶進程,路由選擇,進程,至,因,特,網(wǎng),PC,機,55,PPP,協(xié)議,1992 年制訂了 PPP 協(xié)議。經(jīng)過 1993 年和 1994 年的修訂，現(xiàn)在的 PPP 協(xié)議已成為因特網(wǎng)的正式標(biāo)準(zhǔn)RFC 1661。,PPP協(xié)議有三個組成局部,一個將 IP 數(shù)據(jù)報封裝到串行鏈路的方法。,鏈路控制協(xié)議 LCP (Link Control Protocol)。,網(wǎng)絡(luò)控制協(xié)議 NCP (Network Control Protocol)。,56,PPP,協(xié)議的幀格式,PPP 的幀格式和 HDLC 的相似。,標(biāo)志字段 F 仍為 0x7E 符號“0x表示后面的字符是用十六進制表示。十六進制的 7E 的二進制表示是 01111110。,地址字段 A 只置為 0xFF。地址字段實際上并不起作用。,控制字段 C 通常置為 0x03。,PPP 是面向字節(jié)的，所有的 PPP 幀的長度都是整數(shù)字節(jié)。,57,PPP,協(xié)議的幀格式,PPP 有一個 2 個字節(jié)的協(xié)議字段。,當(dāng)協(xié)議字段為 0x0021 時，PPP 幀的信息字段就是IP 數(shù)據(jù)報。,假設(shè)為 0xC021, 那么信息字段是 PPP 鏈路控制數(shù)據(jù)。,假設(shè)為 0x8021，那么表示這是網(wǎng)絡(luò)控制數(shù)據(jù)。,IP,數(shù)據(jù)報,1,2,1,1,字節(jié),1,2,不超過,1500,字節(jié),PPP,幀,先發(fā)送,7E,FF,03,F,A,C,FCS,F,7E,協(xié)議,信 息 部 分,首部,尾部,58,PPPPoint to Point Protocol點到點協(xié)議 (2),Support：error detection,、,multiple protocols(IP,IPX,Apple Talk,XNS,.),allows IP address to be negotiated、permits authentication,LCP(Link Control Protocol):,byte oriented and bit-oriented encodings,NCP(Network Control Protocol).,Frame format(as HDLC):,-,see fig 3-27,A simplified phase diagram for bringing a line up and down-,see fig 3-28,59,PPP,Point to Point Protocol (3),The PPP full,frame format,for unnumbered mode operation.,Flag: 01111110,Address: always 11111111,Control: default 00000011 (unnumbered mode),Protocol: default size is 2 bytes, tell what kind of packet is in the,Playload,field,protocols starting with a 0 bit are network lay protocols such as IP, IPX,OSL CLNP, XNS; Those starting with a 1 bit are used to negotiate other protocols: LCP or other NCP,Payload: variable length, up to some negotiated maximum; default length of 1500 bytes is used for LCP line setup,Checksum: 2 or 4 bytes,60,PPP,Point to Point Protocol (4),A simplified phase diagram for bring a line up and down.,61,PPP,Point to Point Protocol (5),The LCP frame types.,62,3.7 Summary,The task of the data link layer,The size of window、the sliding window,stop-wait protocol、sliding window protocol,Example of the data link layer：,bit-oriented：SDLC、HDLC、ADCCP or LAPB,byte-oriented and bit-oriented：SLIP and PPPInternet,