第三章 計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)

第3章計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)1.通信協(xié)議人際交流的協(xié)議:人類之間語言和文字系統(tǒng)語法、意義、對話交替順序…

說明發(fā)送的消息…說明接收到某消息后所應(yīng)采取的行動…說明動作的次序通信協(xié)議:計(jì)算機(jī)之間網(wǎng)絡(luò)中所有的通信活動都是由協(xié)議所控制協(xié)議：

定義網(wǎng)絡(luò)實(shí)體間發(fā)送和接收報文的格式、順序以及當(dāng)傳送和接收消息時應(yīng)采取的行動。（語義、語法和時序）協(xié)議設(shè)計(jì)目的計(jì)算機(jī)之間的信息交互time連接響應(yīng)發(fā)送文件連接請求獲取文件交流的基礎(chǔ)：

共同的語言、互相理解，

共同語義……有同學(xué)提問嗎？我有問題請說協(xié)議設(shè)計(jì)目的是什么呢？3人們之間的信息交互

網(wǎng)絡(luò)協(xié)議協(xié)議設(shè)計(jì)目的網(wǎng)絡(luò)協(xié)議為進(jìn)行網(wǎng)絡(luò)中的數(shù)據(jù)交換而建立的規(guī)則、標(biāo)準(zhǔn)或約定，即網(wǎng)絡(luò)協(xié)議(networkprotocol)通信雙方需要共同遵守，互相理解三要素語法：規(guī)定傳輸數(shù)據(jù)的格式（如何講）語義：規(guī)定所要完成的功能（講什么）時序：規(guī)定各種操作的順序（雙方講話的順序）網(wǎng)絡(luò)協(xié)議設(shè)計(jì)目的可靠性資源分配擁塞問題自適應(yīng)性安全問題4

網(wǎng)絡(luò)協(xié)議協(xié)議層次結(jié)構(gòu)

用戶應(yīng)用層

信件遞送層

交通運(yùn)輸層

交通工具層運(yùn)送部門鐵路部門郵局運(yùn)送部門汽運(yùn)部門汽運(yùn)部門郵包郵包貨物貨物火車汽車貨物貨物信件傳遞的信息郵包貨物用戶B用戶A郵局運(yùn)送部門鐵路部門郵包貨物信件信件5

網(wǎng)絡(luò)協(xié)議協(xié)議層次結(jié)構(gòu)層次棧為了降低網(wǎng)絡(luò)設(shè)計(jì)的復(fù)雜性，大部分網(wǎng)絡(luò)都組成一個層次棧，每一層都建立在其下一層的基礎(chǔ)上對等實(shí)體不同機(jī)器上構(gòu)成相應(yīng)層次的實(shí)體成為對等實(shí)體接口在每一對相鄰層次之間的是接口；接口定義了下層向上層提供哪些原語操作與服務(wù)網(wǎng)絡(luò)體系結(jié)構(gòu)層和協(xié)議的集合為網(wǎng)絡(luò)體系結(jié)構(gòu)，一個特定的系統(tǒng)所使用的一組協(xié)議，即每層的協(xié)議，稱為協(xié)議棧第五層第四層第三層第二層第一層物理介質(zhì)第五層第四層第三層第二層第一層主機(jī)A主機(jī)B第四/五層接口第三/四層接口第二/三層接口第一/二層接口對等實(shí)體對等實(shí)體對等實(shí)體對等實(shí)體對等實(shí)體6

網(wǎng)絡(luò)協(xié)議服務(wù)原語兩種不同類型的服務(wù)：面向連接和無連接面向連接：按照電話系統(tǒng)模型建立的（一個常見的例子）撥姑姑家的電話號碼。她家的電話鈴響了。她拿起電話。你聽到響鈴?fù)Ｖ?。你邀請她來喝茶。她聽到了你的邀請。她說她很高興來。你聽到她接受邀請。你掛斷電話。她聽到了，也掛斷電話。面向連接的服務(wù)每個“請求”或“響應(yīng)”后，都在對方產(chǎn)生一個“指示”或“確認(rèn)”動作7

網(wǎng)絡(luò)協(xié)議服務(wù)原語無連接：按照郵政系統(tǒng)模型建立的（一個常見的例子）有快遞要發(fā)給朋友快遞員上門取件快遞進(jìn)入?yún)^(qū)域集散中心區(qū)域集散中心通過運(yùn)輸系統(tǒng)發(fā)到目的地區(qū)域集散中心分發(fā)給目的地快遞員快遞員按照地址派送無連接的服務(wù)郵件攜帶了完整的目標(biāo)地址，傳輸過程不需要應(yīng)答8

網(wǎng)絡(luò)協(xié)議服務(wù)原語服務(wù)典型服務(wù)：面向連接傳輸服務(wù)，無連接傳輸服務(wù)服務(wù)由一組可用于用戶進(jìn)程以訪問服務(wù)的原語（操作）形式指定原語告訴服務(wù)執(zhí)行某些操作或報告對等實(shí)體所采取的操作六個核心服務(wù)原語（以面向連接服務(wù)為例）系統(tǒng)調(diào)用內(nèi)核協(xié)議棧驅(qū)動器系統(tǒng)調(diào)用內(nèi)核協(xié)議棧驅(qū)動器（1）連接請求（2）接受響應(yīng)（3）請求數(shù)據(jù)（4）應(yīng)答（5）請求斷開（6）斷開連接服務(wù)進(jìn)程客戶進(jìn)程客戶機(jī)服務(wù)器9

網(wǎng)絡(luò)協(xié)議服務(wù)與協(xié)議的關(guān)系協(xié)議是“水平”的，服務(wù)是“垂直”的實(shí)體使用協(xié)議來實(shí)現(xiàn)其定義的服務(wù)上層實(shí)體通過接口使用下層實(shí)體的服務(wù)協(xié)議(n+1)接口接口交換信息交換信息實(shí)體(n+1)服務(wù)提供者第n層第n+1層實(shí)體(n+1)服務(wù)的用戶實(shí)體(n)實(shí)體(n)協(xié)議(n)10

網(wǎng)絡(luò)協(xié)議OSI參考模型簡介計(jì)算機(jī)網(wǎng)絡(luò)面臨的問題

用戶的資源和信息存儲在采用不同操作系統(tǒng)的主機(jī)中，這些主機(jī)分布在網(wǎng)絡(luò)的不同地方，需要在不同的傳輸介質(zhì)上實(shí)現(xiàn)采用不同操作系統(tǒng)的主機(jī)之間的通信，解決異種機(jī)和異種網(wǎng)絡(luò)互連問題的方法。分層的好處

容易解決通信的異質(zhì)性（heterogeneity）問題；上層解決不同種語言的相互翻譯（數(shù)據(jù)的不同表示）；下層解決信息傳遞；使復(fù)雜問題簡化，高層屏蔽低層細(xì)節(jié)問題；每層只關(guān)心本層的內(nèi)容，不用知道其他層如何實(shí)現(xiàn)；使設(shè)計(jì)容易實(shí)現(xiàn)，每個層次向上一層提供服務(wù)，向下一層請求服務(wù)。參考模型的必要性互聯(lián)網(wǎng)大廠X訊與X東的合作12層級組織（分層）總裁-總監(jiān)-經(jīng)理-碼農(nóng)內(nèi)部獨(dú)立（模塊）我用Python;我用GO鐵打的項(xiàng)目，流水的碼農(nóng)溝通協(xié)作（標(biāo)準(zhǔn)）合作協(xié)議、項(xiàng)目文檔、接口定義日報、周報、月報總裁總監(jiān)經(jīng)理碼農(nóng)戰(zhàn)略合作確定項(xiàng)目細(xì)化功能代碼接口參考模型參考模型的必要性計(jì)算機(jī)網(wǎng)絡(luò)的復(fù)雜與異構(gòu)介質(zhì)：光纖、銅纜、空氣...接入：有線、WLAN、移動數(shù)據(jù)網(wǎng)絡(luò)、藍(lán)牙...應(yīng)用：無人駕駛、萬物互聯(lián)、短視頻、郵件...高速更新迭代大哥大1G（模擬）、2G(數(shù)字)、3G、4G、5GIEEE802.3：2020年推出4個版本...13分層結(jié)構(gòu)統(tǒng)一標(biāo)準(zhǔn)模塊獨(dú)立明晰簡化，便于分析學(xué)習(xí)各層獨(dú)立，加速技術(shù)演進(jìn)統(tǒng)一接口，確保技術(shù)互通（interoperable）開發(fā)個游戲直播軟件，是否需要針對3G/

4G/5G還是WiFi單獨(dú)開發(fā)？WiFi發(fā)展為新版本W(wǎng)iFi6，那么WiFi6是否要對已有直播、微信或支付寶做適配？

參考模型OSI參考模型OSI7層模型OSI：OpenSystemsInterconnectionDay,Zimmermann,1983物理層（PhysicalLayer）定義如何在信道上傳輸0、1：Bitsonthewire機(jī)械接口（Mechanical）：網(wǎng)線接口大小形狀、線纜排列等電子信號（Electronic）：電壓、電流等時序接口（Timing）：采樣頻率、波特率、比特率等介質(zhì)（Medium）：各種線纜、無線頻譜等...14應(yīng)用層ApplicationLayer表示層PresentationLayer會話層SessionLayer傳輸層TransportLayer網(wǎng)絡(luò)層NetworkLayer數(shù)據(jù)鏈路層DataLinkLayer物理層PhysicalLayer

參考模型OSI參考模型數(shù)據(jù)鏈路層(DataLinkLayer)實(shí)現(xiàn)相鄰（Neighboring）網(wǎng)絡(luò)實(shí)體間的數(shù)據(jù)傳輸成幀（Framing）：從物理層的比特流中提取出完整的幀錯誤檢測與糾正：為提供可靠數(shù)據(jù)通信提供可能物理地址（MACaddress）：48位，理論上唯一網(wǎng)絡(luò)標(biāo)識，燒錄在網(wǎng)卡，不便更改流量控制，避免“淹沒”（overwhelming）:當(dāng)快速的發(fā)送端遇上慢速的接收端，接收端緩存溢出共享信道上的訪問控制（MAC）：同一個信道，同時傳輸信號。如同：同一間教室內(nèi)，多人同時發(fā)言，需要紀(jì)律來控制。...15應(yīng)用層ApplicationLayer表示層PresentationLayer會話層SessionLayer傳輸層TransportLayer網(wǎng)絡(luò)層NetworkLayer數(shù)據(jù)鏈路層DataLinkLayer物理層PhysicalLayer

參考模型OSI參考模型網(wǎng)絡(luò)層(NetworkLayer)將數(shù)據(jù)包跨越網(wǎng)絡(luò)從源設(shè)備發(fā)送到目的設(shè)備（hosttohost）路由（Routing）：在網(wǎng)絡(luò)中選取從源端到目的端轉(zhuǎn)發(fā)路徑，常常會根據(jù)網(wǎng)絡(luò)可達(dá)性動態(tài)選取最佳路徑，也可以使用靜態(tài)路由路由協(xié)議：路由器之間交互路由信息所遵循的協(xié)議規(guī)范，使得單個路由器能夠獲取網(wǎng)絡(luò)的可達(dá)性等信息服務(wù)質(zhì)量（QoS）控制：處理網(wǎng)絡(luò)擁塞、負(fù)載均衡、準(zhǔn)入控制、保障延遲異構(gòu)網(wǎng)絡(luò)互聯(lián)：在異構(gòu)編址和異構(gòu)網(wǎng)絡(luò)中路由尋址和轉(zhuǎn)發(fā)16應(yīng)用層ApplicationLayer表示層PresentationLayer會話層SessionLayer傳輸層TransportLayer網(wǎng)絡(luò)層NetworkLayer數(shù)據(jù)鏈路層DataLinkLayer物理層PhysicalLayer思考：為何在唯一的MAC地址之外，還需要唯一的IP地址？參考模型OSI參考模型傳輸層(TransportLayer)將數(shù)據(jù)從源端口發(fā)送到目的端口（進(jìn)程到進(jìn)程）網(wǎng)絡(luò)層定位到一臺主機(jī)（host），傳輸層的作用域具體到主機(jī)上的某一個進(jìn)程網(wǎng)絡(luò)層的控制主要面向運(yùn)營商，傳輸層為終端用戶提供端到端的數(shù)據(jù)傳輸控制兩類模式：可靠的傳輸模式，或不可靠傳輸模式可靠傳輸：可靠的端到端數(shù)據(jù)傳輸，適合于對通信質(zhì)量有要求的應(yīng)用場景，如文件傳輸?shù)炔豢煽總鬏敚焊旖?、更輕量的端到端數(shù)據(jù)傳輸，適合于對通信質(zhì)量要求不高，對通信響應(yīng)速度要求高的應(yīng)用場景，如語音對話、視頻會議等17應(yīng)用層ApplicationLayer表示層PresentationLayer會話層SessionLayer傳輸層TransportLayer網(wǎng)絡(luò)層NetworkLayer數(shù)據(jù)鏈路層DataLinkLayer物理層PhysicalLayer

參考模型OSI參考模型會話層(SessionLayer)利用傳輸層提供的服務(wù)，在應(yīng)用程序之間建立和維持會話，并能使會話獲得同步表示層（PresentationLayer）關(guān)注所傳遞信息的語法和語義，管理數(shù)據(jù)的表示方法，傳輸?shù)臄?shù)據(jù)結(jié)構(gòu)應(yīng)用層（ApplicationLayer）通過應(yīng)用層協(xié)議，提供應(yīng)用程序便捷的網(wǎng)絡(luò)服務(wù)調(diào)用18應(yīng)用層ApplicationLayer表示層PresentationLayer會話層SessionLayer傳輸層TransportLayer網(wǎng)絡(luò)層NetworkLayer數(shù)據(jù)鏈路層DataLinkLayer物理層PhysicalLayer參考模型層層的名稱設(shè)備協(xié)議7|5應(yīng)用層表示層會話層TFTP、FTP、SMTP、Telnet、HTTP、SNMP、DNS、

NFS、rlogin4傳輸層TCP、UDP、IPX3網(wǎng)絡(luò)層路由器、三層交換機(jī)AppleTalk、DECnet、IP、IPX、Vines、XNS、ICMP、ARP、RARP等2數(shù)據(jù)鏈路層交換機(jī)、網(wǎng)橋、網(wǎng)卡ATM、PPP、HDLC、幀中繼、802.2、802.31物理層集線器

設(shè)備、協(xié)議與其所在的層1.各層功能總覽

SummaryofLayerFunctionsL1L2L3L4L5L6L7PhysicalLayerNetworkLayerTransportSessionPresentationApplicationDataLinkControl7應(yīng)用層6表示層5會話層4傳輸層3網(wǎng)絡(luò)層2數(shù)據(jù)鏈路層1物理層

用戶系統(tǒng)層

數(shù)據(jù)通信網(wǎng)銜接

軟件主要由軟件實(shí)現(xiàn)（面向通信用戶）

資源子網(wǎng)的任務(wù)

網(wǎng)絡(luò)主要由硬件實(shí)現(xiàn)（完成傳送服務(wù)）通信子網(wǎng)任務(wù)

OSI參考模型示意圖TCP/IP參考模型TCP/IP參考模型：ARPANET所采用以其中最主要的兩個協(xié)議TCP/IP命名Vint

Cerf和Bob

Kahn于1974年提出鏈路層（LinkLayer）描述了為滿足無連接的互聯(lián)網(wǎng)絡(luò)層需求，鏈路必須具備的功能互聯(lián)網(wǎng)層（InternetLayer）允許主機(jī)將數(shù)據(jù)包注入網(wǎng)絡(luò)，讓這些數(shù)據(jù)包獨(dú)立的傳輸至目的地，并定義了數(shù)據(jù)包格式和協(xié)議（IPv4協(xié)議和IPv6協(xié)議）傳輸層（TransportLayer）允許源主機(jī)與目標(biāo)主機(jī)上的對等實(shí)體，進(jìn)行端到端的數(shù)據(jù)傳輸：TCP，UDP應(yīng)用層（ApplicationLayer）傳輸層之上的所有高層協(xié)議：DNS、HTTP、FTP、SMTP...22應(yīng)用層applicationLayer傳輸層transportLayer互聯(lián)網(wǎng)層internetLayer網(wǎng)絡(luò)接口層host-to-network

Layer

參考模型先有TCP/IP協(xié)議棧，然后有TCP/IP參考模型參考模型只是用來描述協(xié)議棧的

ARPNET

最終采用TCP和IP為主要協(xié)議TCP/IP參考模型TCP/IP參考模型摒棄電話系統(tǒng)中“笨終端&聰明網(wǎng)絡(luò)”的設(shè)計(jì)思路采用聰明終端&簡單網(wǎng)絡(luò)，由端系統(tǒng)TCP負(fù)責(zé)丟失

恢復(fù)等，簡單的網(wǎng)絡(luò)大大提升了可擴(kuò)展性實(shí)現(xiàn)了建立在簡單的、不可靠部件上的可靠系統(tǒng)IP分組交換的特點(diǎn)可在各種底層物理網(wǎng)絡(luò)上運(yùn)行(IPovereverything)可支持各類上層應(yīng)用(EverythingoverIP)每個IP分組攜帶各自的目的地址，網(wǎng)絡(luò)核心功能

簡單（通過路由表轉(zhuǎn)發(fā)分組），適應(yīng)爆炸性增長23

參考模型TCP/IPTCP/IP的沙漏模型OSI模型與TCP/IP模型比較7層模型與4層模型TCP/IP模型的網(wǎng)絡(luò)接口層定義主機(jī)與傳輸線路之間的接口，描述了鏈路為無連接的互聯(lián)網(wǎng)層必須提供的基本功能TCP/IP模型的互聯(lián)網(wǎng)層、傳輸層與OSI模型的網(wǎng)絡(luò)層、傳輸層大致對應(yīng)TCP/IP模型的應(yīng)用層包含了OSI模型的表示層與會話層基本設(shè)計(jì)思想：通用性與實(shí)用性O(shè)SI：先有模型后設(shè)計(jì)協(xié)議，不局限于特定協(xié)議，明確了服務(wù)、協(xié)議、接口等概念，更具通用性TCP/IP模型：僅僅是對已有協(xié)議的描述無連接與面向連接OSI模型網(wǎng)絡(luò)層能夠支持無連接和面向連接通信TCP/IP模型的網(wǎng)絡(luò)層僅支持無連接通信（IP）24應(yīng)用層表示層會話層傳輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層應(yīng)用層傳輸層互聯(lián)網(wǎng)層網(wǎng)絡(luò)接口層OSI7層模型TCP/IP4層模型

參考模型OSI模型與TCP/IP模型比較從未真正被實(shí)現(xiàn)TCP/IP已成為事實(shí)標(biāo)準(zhǔn)，OSI缺少廠家支持技術(shù)實(shí)現(xiàn)糟糕OSI分層欠缺技術(shù)考慮：會話層、表示層很少內(nèi)容；數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層內(nèi)容繁雜。模型和協(xié)議過于復(fù)雜分層間功能重復(fù)：差錯控制、流量控制等在不同層反復(fù)出現(xiàn)非技術(shù)因素TCP/IP實(shí)現(xiàn)為UNIX一部分，免費(fèi)OSI被認(rèn)為是政府和機(jī)構(gòu)的強(qiáng)加標(biāo)準(zhǔn)25OSI模型的不足核心概念未能體現(xiàn)未明確區(qū)分服務(wù)、接口和協(xié)議等核心概念不具備通用性不適于描述TCP/IP之外的其它協(xié)議棧混用接口與分層的設(shè)計(jì)鏈路層和物理層一起被定義為網(wǎng)絡(luò)接口層，而非真正意思上的分層模型欠缺完整性未包含物理層與數(shù)據(jù)鏈路層物理層與數(shù)據(jù)鏈路層是至關(guān)重要的部分TCP/IP模型的不足參考模型OSI的失敗：糟糕的時機(jī)、技術(shù)、實(shí)現(xiàn)、政策本教程內(nèi)容的分層組織突出核心概念區(qū)分接口與分層體現(xiàn)完整性體現(xiàn)通用性簡化分層，易于教學(xué)26應(yīng)用層表示層會話層傳輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層應(yīng)用層傳輸層互聯(lián)網(wǎng)層網(wǎng)絡(luò)接口層OSI7層模型TCP/IP4層模型應(yīng)用層傳輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層物理層本教程的分層組織

參考模型分層模型與網(wǎng)絡(luò)實(shí)例端到端通信實(shí)例：主機(jī)A上的QQ，發(fā)送消息；主機(jī)B上的QQ，接收消息發(fā)送端層層封裝，接收端層層解封裝不同層對應(yīng)協(xié)議數(shù)據(jù)單元（PDUProtocolDataUnit）27應(yīng)用層傳輸層網(wǎng)絡(luò)層鏈路層物理層發(fā)送：hello

helloHthelloHnHthello

HlHnHthello應(yīng)用層傳輸層網(wǎng)絡(luò)層鏈路層物理層鏈路層物理層鏈路層物理層網(wǎng)絡(luò)層鏈路層物理層接收：hello101101010000...

hello

Hthello

HnHthello

HlHnHthello101101010000...消息message段segment數(shù)據(jù)報packet幀frame主機(jī)A交換機(jī)交換機(jī)主機(jī)B路由器封裝Encapsulation解封裝De-encapsulation參考模型數(shù)據(jù)鏈路層的功能鏈路管理包括：鏈路的建立、維持、釋放成幀（Framing）將比特流劃分成“幀”的主要目的是為了檢測和糾正物理層在比特傳輸中可能出現(xiàn)的錯誤，數(shù)據(jù)鏈路層功能需借助“幀”的各個域來實(shí)現(xiàn)差錯控制（ErrorControl）處理傳輸中出現(xiàn)的差錯，如位錯誤、丟失等流量控制（FlowControl）確保發(fā)送方的發(fā)送速率，不大于接收方的處理速率避免接收緩沖區(qū)溢出283.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題數(shù)據(jù)鏈路層提供的服務(wù)無確認(rèn)無連接服務(wù)（

Unacknowledgedconnectionless

）接收方不對收到的幀進(jìn)行確認(rèn)適用場景：誤碼率低的可靠信道；實(shí)時通信；網(wǎng)絡(luò)實(shí)例：以太網(wǎng)有確認(rèn)無連接服務(wù)（

Acknowledgedconnectionless

）每一幀都得到單獨(dú)的確認(rèn)適用場景：不可靠的信道（無線信道）網(wǎng)絡(luò)實(shí)例：802.11有確認(rèn)有連接服務(wù)（

Acknowledgedconnection-oriented

）適用場景：長延遲的不可靠信道293.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題成幀（Framing）分組(packet)與幀(frame)的關(guān)系303.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題數(shù)據(jù)鏈路層網(wǎng)絡(luò)層分組發(fā)送方頭標(biāo)尾標(biāo)分組接收方頭標(biāo)尾標(biāo)幀有效載荷有效載荷成幀（Framing）關(guān)鍵問題：如何標(biāo)識一個幀的開始？接收方必須能從物理層接收的比特流中明確區(qū)分出一幀的開始和結(jié)束，這個問題被稱為幀同步或幀定界關(guān)鍵：選擇何種定界符？定界符出現(xiàn)在數(shù)據(jù)部分如何處理？成幀（framing）的方式字節(jié)計(jì)數(shù)法（Bytecount）帶字節(jié)填充的定界符法（

Flagbyteswithbytestuffing）帶比特填充的定界符法（

Flagbitswithbitstuffing）物理層編碼違例（Physicallayercodingviolations）313.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題成幀（Framing）字節(jié)計(jì)數(shù)法：無差錯傳輸?shù)那樾?23.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題第1幀5字節(jié)第2幀5字節(jié)第3幀8字節(jié)第4幀6字節(jié)512345123481234567612345問題：如果某個計(jì)數(shù)字節(jié)出錯會發(fā)生什么情況？成幀（Framing）字節(jié)計(jì)數(shù)法：出現(xiàn)了一個字節(jié)差錯的情形333.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題第1幀5字節(jié)第2幀出現(xiàn)差錯第3幀8字節(jié)第4幀6字節(jié)512348123481234567612345破壞了幀的邊界，導(dǎo)致一連串幀的錯誤成幀（Framing）帶字節(jié)填充的定界符法定界符（FLAG）：一個特殊的字節(jié)，比如01111110，即0x7E，用于區(qū)分前后兩個不同的幀343.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題FLAG頭標(biāo)有效載荷尾標(biāo)FLAG一個幀定界符定界符問題：如果有效載荷部分包含與“定界符”相同的字節(jié)會有什么問題？成幀（Framing）帶字節(jié)填充的定界符法：發(fā)送方檢查有效載荷，進(jìn)行字節(jié)填充353.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題FLAG頭標(biāo)有效載荷尾標(biāo)FLAGFLAGBAESCBAESCBAFLAGESCBAFLAGESCBAESCESCBAESCESCBAESCESCFLAGESCBAESCESCESC轉(zhuǎn)義字節(jié)成幀（Framing）帶字節(jié)填充的定界符法：接收方的處理逐個檢查收到的每一個字節(jié)收到ESC則后一字節(jié)無條件成為有效載荷，不予檢查收到FLAG則為幀的邊界363.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題成幀（Framing）帶字節(jié)填充的定界符法：收方的處理示例373.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題ESCBAFLAGESCBAESCESCBAESCESCFLAGESCBAESCESCESCFLAGBAESCBAESCBAFLAGESCBAESC接收方收到的數(shù)據(jù)

處理后的數(shù)據(jù)

問題：帶字節(jié)填充的定界符法有什么不足？成幀（Framing）帶比特填充的定界符法定界符：兩個0比特之間，連續(xù)6個1比特，即01111110，0x7E383.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題010110111111001110001011定界符上一幀下一幀問題：如果有效載荷部分包含與“定界符”相同的位組合如何解決？成幀（Framing）帶比特填充的定界符法：發(fā)送方檢查有效載荷若在有效載荷中出現(xiàn)連續(xù)5個1比特，則直接插入1個0比特393.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題011111011111100011100010原始載荷載荷填充01111100111110100011101000成幀（Framing）帶比特填充的定界符法：接收方的處理若出現(xiàn)連續(xù)5個1比特若下一比特為0，則為有效載荷，直接丟棄0比特若下一比特為1，則連同后一比特的0，構(gòu)成定界符，一幀結(jié)束403.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題00011111011111100011100010處理后的載荷收到的比特流011111011111100011101000丟棄丟棄成幀（Framing）物理層編碼違例：核心思想：選擇的定界符不會在數(shù)據(jù)部分出現(xiàn)4B/5B編碼方案4比特數(shù)據(jù)映射成5比特編碼，剩余的一半碼字（16個碼字）未使用，可以用做幀定界符例如：00110組合不包含在4B/5B編碼中，可做幀定界符前導(dǎo)碼存在很長的前導(dǎo)碼（preamble），可以用作定界符例如：傳統(tǒng)以太網(wǎng)、802.11曼切斯特編碼/差分曼切斯特編碼正常的信號在周期中間有跳變，持續(xù)的高電平（或低電平）為違例碼，可以用作定界符例如：802.5令牌環(huán)網(wǎng)413.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題差錯控制鏈路層存在的一個問題：信道的噪聲導(dǎo)致數(shù)據(jù)傳輸問題差錯（incorrect）：數(shù)據(jù)發(fā)生錯誤丟失（lost）：接收方未收到亂序（outoforder）：先發(fā)后到，后發(fā)先到重復(fù)（repeatedlydelivery）：一次發(fā)送，多次接收解決方案：差錯檢測與糾正、確認(rèn)重傳確認(rèn)：接收方校驗(yàn)數(shù)據(jù)（差錯校驗(yàn)），并給發(fā)送方應(yīng)答，防止差錯定時器：發(fā)送方啟動定時器，防止丟失順序號：接收方檢查序號，防止亂序遞交、重復(fù)遞交423.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題流量控制鏈路層存在的另一個問題：接收方的處理速率接收方的接收緩沖區(qū)溢出解決方案基于反饋(feedback-based)的流量控制接收方反饋，發(fā)送方調(diào)整發(fā)送速率基于速率(rate-based)的流量控制發(fā)送方根據(jù)內(nèi)建機(jī)制，自行限速43面臨的問題3.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題本章內(nèi)容3.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題3.2差錯檢測和糾正3.3基本的數(shù)據(jù)鏈路層協(xié)議3.4滑動窗口協(xié)議3.5數(shù)據(jù)鏈路協(xié)議實(shí)例44差錯檢測與糾正概述典型的糾錯碼典型的檢錯碼差錯檢測和糾正概述如何解決信道傳輸差錯問題通常采用增加冗余信息（或稱校驗(yàn)信息）的策略簡單示例：每個比特傳三份，如果每比特的三份中有一位出錯，可以糾正453.2差錯檢測和糾正0100100010110101011010101101010010101011010133.3%66.7%原始數(shù)據(jù)冗余信息攜帶2/3的冗余信息！冗余信息量大！差錯檢測和糾正概述目標(biāo)：保證一定差錯檢測和糾錯能力的前提下，如何減少冗余信息量？考慮的問題信道的特征和傳輸需求冗余信息的計(jì)算方法、攜帶的冗余信息量計(jì)算的復(fù)雜度等兩種主要策略檢錯碼（error-detectingcode）糾錯碼（error-correctingcode)463.2差錯檢測和糾正差錯檢測和糾正概述檢錯碼（error-detectingcode）在被發(fā)送的數(shù)據(jù)塊中，包含一些冗余信息，但這些信息只能使接收方推斷是否發(fā)生錯誤，但不能推斷哪位發(fā)生錯誤，接收方可以請求發(fā)送方重傳數(shù)據(jù)主要用在高可靠、誤碼率較低的信道上，例如光纖鏈路偶爾發(fā)生的差錯，可以通過重傳解決差錯問題473.2差錯檢測和糾正差錯檢測和糾正概述糾錯碼（error-correctingcode)發(fā)送方在每個數(shù)據(jù)塊中加入足夠的冗余信息，使得接收方能夠判斷接收到的數(shù)據(jù)是否有錯，并能糾正錯誤（定位出錯的位置）主要用于錯誤發(fā)生比較頻繁的信道上，如無線鏈路也經(jīng)常用于物理層，以及更高層（例如，實(shí)時流媒體應(yīng)用和內(nèi)容分發(fā)）使用糾錯碼的技術(shù)通常稱為前向糾錯（FEC，F(xiàn)orwardErrorCorrection)483.2差錯檢測和糾正差錯檢測和糾正概述碼字(codeword)：一個包含m個數(shù)據(jù)位和r個校驗(yàn)位的n位單元描述為(n,m)碼，n=m+r碼率(coderate)：碼字中不含冗余部分所占的比例，可以用m/n表示海明距離(Hammingdistance)：兩個碼字之間不同對應(yīng)比特的數(shù)目例：0000000000與0000011111的海明距離為5如果兩個碼字的海明距離為d，則需要d個單比特錯就可以把一個碼字轉(zhuǎn)換成另一個碼字為了檢查出d個錯（比特錯），可以使用海明距離為d+1的編碼為了糾正d個錯，可以使用海明距離為2d+1的編碼493.2差錯檢測和糾正差錯檢測和糾正概述例如：一個只有4個有效碼字的編碼方案：0000000000,0000011111,1111100000,1111111111海明距離為5，可以檢測4位錯，糾正2位錯如果已知只有1位或2位錯誤，接收方接收0000000111則可知原碼字為：0000011111如果發(fā)生3位錯誤，例如0000000000變成0000000111，接收方無法糾正錯誤，但可以檢測出錯誤503.2差錯檢測和糾正典型檢錯碼常用的檢錯碼包括：奇偶檢驗(yàn)

(ParityCheck)：1位奇偶校驗(yàn)是最簡單、最基礎(chǔ)的檢錯碼校驗(yàn)和(Checksum)：主要用于TCP/IP體系中的網(wǎng)絡(luò)層和傳輸層循環(huán)冗余校驗(yàn)(CyclicRedundancyCheck，CRC)：數(shù)據(jù)鏈路層廣泛使用的校驗(yàn)方法3.2差錯檢測和糾正典型檢錯碼—奇偶校驗(yàn)1位奇偶校驗(yàn)：增加1位校驗(yàn)位，可以檢查奇數(shù)位錯誤523.2差錯檢測和糾正1011010010110101偶校驗(yàn)：保證1的個數(shù)為偶數(shù)個，例如：奇校驗(yàn)：保證1的個數(shù)為奇數(shù)個，例如：數(shù)據(jù)位校驗(yàn)位數(shù)據(jù)位校驗(yàn)位考慮二維奇偶校驗(yàn)，是否可以進(jìn)行糾錯？典型檢錯碼—校驗(yàn)和TCP/IP體系中主要采用的校驗(yàn)方法3.2差錯檢測和糾正111100110011001101110101010101010111011101110111011110111011101111001

010001000100001153發(fā)送方：進(jìn)行16位二進(jìn)制補(bǔ)碼求和運(yùn)算，計(jì)算結(jié)果取反，隨數(shù)據(jù)一同發(fā)送接收方：進(jìn)行16位二進(jìn)制補(bǔ)碼求和運(yùn)算（包含校驗(yàn)和），結(jié)果非全1，則檢測到錯誤校驗(yàn)和數(shù)據(jù)1111001100110011011101010101010101110111011101110111

0100010001000011

11111111111111111數(shù)據(jù)校驗(yàn)和未檢測到錯誤典型檢錯碼—循環(huán)冗余校驗(yàn)CRCCRC校驗(yàn)碼計(jì)算方法設(shè)原始數(shù)據(jù)D為k位二進(jìn)制位模式如果要產(chǎn)生n位CRC校驗(yàn)碼，事先選定一個n+1位二進(jìn)制位模式G(稱為生成多項(xiàng)式，收發(fā)雙方提前商定)，G的最高位為1將原始數(shù)據(jù)D乘以2n（相當(dāng)于在D后面添加n個0），產(chǎn)生k+n位二進(jìn)制位模式，用G對該位模式做模2除，得到余數(shù)R（n位，不足n位前面用0補(bǔ)齊）即為CRC校驗(yàn)碼3.2差錯檢測和糾正原始數(shù)據(jù)DCRC校驗(yàn)碼發(fā)送數(shù)據(jù)k

位n

位k+n

位CRC校驗(yàn)?zāi)芰Γ耗軝z測出少于n+1位的突發(fā)錯誤接收端如何計(jì)算？54檢錯碼—循環(huán)冗余校驗(yàn)CRCCRC校驗(yàn)碼計(jì)算示例D=1010001101n=5G=110101或G=x5+x4+x2+1R=01110實(shí)際傳輸數(shù)據(jù)：1010001101011103.2差錯檢測和糾正

1101010110

G→

110101101000110100000

←

2nD

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R55檢錯碼—循環(huán)冗余校驗(yàn)CRC四個國際標(biāo)準(zhǔn)生成多項(xiàng)式CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1例如，以太網(wǎng)、無線局域網(wǎng)使用CRC-32生成多項(xiàng)式引自：清華大學(xué)崔勇老師提供的講稿3.2差錯檢測和糾正典型糾錯碼設(shè)計(jì)糾錯碼要求：m個信息位，r個校驗(yàn)位，糾正單比特錯對2m個有效信息中任何一個，有n個與其距離為1的無效碼字：可以考慮將該信息對應(yīng)的合法碼字的n位逐個取反，得到n個距離為1的非法碼字，需要n+1個位模式來標(biāo)識因此有：(n+1)2m

2n利用n=m+r，得到(m+r+1)2r在給定m的情況下，利用該式可以得出糾正單比特錯誤校驗(yàn)位數(shù)的下界573.2差錯檢測和糾正引自：清華大學(xué)崔勇老師提供的講稿典型糾錯碼—海明碼目標(biāo)：以奇偶校驗(yàn)為基礎(chǔ)，如何找到出錯位置，提供1位糾錯能力理解海明碼編碼過程，以(15,11)海明碼為例例如：11比特的數(shù)據(jù)0101100110111比特數(shù)據(jù)按順序放入數(shù)據(jù)位校驗(yàn)位：2的冪次方位（記為p1,p2,p4,p8）每個校驗(yàn)位對數(shù)據(jù)位的子集做校驗(yàn)，縮小定位錯誤的范圍問題：每個校驗(yàn)位如何計(jì)算？583.2差錯檢測和糾正校驗(yàn)位數(shù)據(jù)位右下角數(shù)字為碼字中位序號10101100101123456789101112131415糾錯碼—海明碼子集的選擇與校驗(yàn)位計(jì)算海明碼缺省為偶校驗(yàn)（也可以使用奇校驗(yàn)）593.2差錯檢測和糾正101011001011234567891011121314155個1p1=111010110010112345678910111213141510101100101123456789101112131415101011001011234567891011121314152個1p2=0010第1組第2組第3組第4組每組的數(shù)據(jù)位每組的校驗(yàn)位5個1p4=14個1p8=0糾錯碼—海明碼碼字的發(fā)送與接收如果發(fā)送過程中第7位出現(xiàn)差錯，如何定位錯誤？603.2差錯檢測和糾正101100101100101123456789101112131415校驗(yàn)位數(shù)據(jù)位校驗(yàn)位數(shù)據(jù)位101100111010001101100100100101123456789101112131415發(fā)送方接收方糾錯碼—海明碼定位錯誤與糾正組1和組2的校驗(yàn)結(jié)果可以定位錯誤所在的列613.2差錯檢測和糾正101001001011234567891011121314155個1有錯誤1101001001011234567891011121314151個1有錯誤0第1組第2組出錯列234組1╳√╳組2√╳╳例如：組1和組2校驗(yàn)結(jié)果都指明存在錯誤，可定位錯誤位于第4列其他出錯情況判斷糾錯碼—海明碼定位錯誤與糾正（續(xù)）組3和組4的校驗(yàn)結(jié)果可以定位錯誤所在的行623.2差錯檢測和糾正出錯行234組3╳√╳組4√╳╳101001001011234567891011121314151010010010112345678910111213141510第3組第4組結(jié)論：錯誤位于第2行、第4列（位置7）5個1有錯誤4個1無錯誤例如：組3校驗(yàn)結(jié)果指明存在錯誤，組4校驗(yàn)結(jié)果指明無錯誤，可定位錯誤位于第2行其他出錯情況判斷糾錯碼—海明碼定位錯誤與糾正（續(xù)）總體的定位錯誤列表633.2差錯檢測和糾正出錯位123456789101112131415組1╳√╳√╳√╳√╳√╳√╳√╳組2√╳╳√√╳╳√√╳╳√√╳╳組3√√√╳╳╳╳√√√√╳╳╳╳組4√√√√√√√╳╳╳╳╳╳╳╳糾錯碼—海明碼海明碼糾正的實(shí)現(xiàn)過程每個碼字到來前，接收方計(jì)數(shù)器清零接收方檢查每個校驗(yàn)位k(k=1,2,4…)的奇偶值是否正確（每組運(yùn)算）若pk奇偶值不對，計(jì)數(shù)器加k所有校驗(yàn)位檢查完后，若計(jì)數(shù)器值為0，則碼字有效；若計(jì)數(shù)器值為j，則第j位出錯。例：若校驗(yàn)位p1、p2、p8出錯，則第11位變反使用海明碼糾正突發(fā)錯誤可采用k個碼字（n=m+r）組成

kn矩陣，按列發(fā)送，接收方恢復(fù)成

kn矩陣kr個校驗(yàn)位，km個數(shù)據(jù)位，可糾正最多為k個的突發(fā)性連續(xù)比特錯643.2差錯檢測和糾正

具有最簡單流量控制的數(shù)據(jù)鏈路層協(xié)議在發(fā)送結(jié)點(diǎn)：

(1)從主機(jī)取一個數(shù)據(jù)幀。

(2)將數(shù)據(jù)幀送到數(shù)據(jù)鏈路層的發(fā)送緩存。

(3)將發(fā)送緩存中的數(shù)據(jù)幀發(fā)送出去。

(4)等待。

(5)若收到由接收結(jié)點(diǎn)發(fā)過來的信息，則從主機(jī)取一個新的數(shù)據(jù)幀，然后轉(zhuǎn)到(2)。在接收結(jié)點(diǎn)：

(1)等待。

(2)若收到由發(fā)送結(jié)點(diǎn)發(fā)過來的數(shù)據(jù)幀，則將其放入數(shù)據(jù)鏈路層的接收緩存。

(3)將接收緩存中的數(shù)據(jù)幀上交主機(jī)。

(4)向發(fā)送結(jié)點(diǎn)發(fā)一信息，表示數(shù)據(jù)幀已經(jīng)上交給主機(jī)。

(5)轉(zhuǎn)到(1)。

兩種情況的對比（傳輸均無差錯）ABDATADATADATADATA送主機(jī)B送主機(jī)B送主機(jī)B送主機(jī)BABDATA送主機(jī)BDATA送主機(jī)B時間不需要流量控制需要流量控制

實(shí)用的停止等待協(xié)議時間ABDATA0送主機(jī)ACKDATA1送主機(jī)ACK(a)正常情況ABDATA0DATA0送主機(jī)ACK(c)數(shù)據(jù)幀丟失重傳tout丟失！ABDATA0送主機(jī)ACKDATA0丟棄ACK(d)確認(rèn)幀丟失重傳tout丟失！ABDATA0NAKDATA0送主機(jī)ACK(b)數(shù)據(jù)幀出錯重傳出錯四種情況無錯信道上的停等式協(xié)議（1）不再假設(shè)接收方能夠處理以無限高速進(jìn)來的數(shù)據(jù)發(fā)送方以高于接收方能處理到達(dá)幀的速度發(fā)送幀，導(dǎo)致接收方被“淹沒”(overwhelming)仍然假設(shè)通信信道不會出錯（Error-Free）數(shù)據(jù)傳輸保持單向,但是需要雙向傳輸鏈路（半雙工物理信道）683.3基本的數(shù)據(jù)鏈路層協(xié)議無錯信道上的停等式協(xié)議（2）停-等式協(xié)議（stop-and-wait）發(fā)送方發(fā)送一幀后暫停，等待確認(rèn)（Acknowldgement）到達(dá)后發(fā)送下一幀接收方完成接收后，回復(fù)確認(rèn)接收.確認(rèn)幀的內(nèi)容是不重要的：啞幀（dummyframe）69發(fā)送方接收方時間...數(shù)據(jù)幀啞幀確認(rèn)等待確認(rèn)3.3基本的數(shù)據(jù)鏈路層協(xié)議無錯信道上的停等式協(xié)議（3）發(fā)送方完成一幀發(fā)送后等待確認(rèn)到達(dá)確認(rèn)到達(dá)后，發(fā)送下一幀70接收方完成一幀接收后交給物理層一個啞幀作為成功接收上一幀的確認(rèn)3.3基本的數(shù)據(jù)鏈路層協(xié)議有錯信道上的單工停等式協(xié)議（1）假設(shè)通信信道可能會出錯，導(dǎo)致：幀在傳輸過程中可能會被損壞，接收方能夠檢測出來幀在傳輸過程中可能會丟失，永遠(yuǎn)不可能到達(dá)接收方一個簡單的解決方案發(fā)送方增加一個計(jì)時器(timer)，如果經(jīng)過一段時間沒有收到確認(rèn)，發(fā)送方將超時，于是再次發(fā)送該幀71發(fā)送方接收方時間丟失/出錯超時重發(fā)啟動計(jì)時器啟動計(jì)時器接收3.3基本的數(shù)據(jù)鏈路層協(xié)議有錯信道上的單工停等式協(xié)議（2）考慮一個特別場景A發(fā)送幀A1B收到了A1B生成確認(rèn)ACKACK在傳輸中丟失A超時，重發(fā)A1B收到A1的另一個副本（并把它交給網(wǎng)絡(luò)層）其他的場景另一個導(dǎo)致副本產(chǎn)生的場景是過長的延時(long

delay)72發(fā)送方A接收方B接收超時重發(fā)啟動計(jì)時器啟動計(jì)時器接收ACK丟失A1A1A1A13.3基本的數(shù)據(jù)鏈路層協(xié)議有錯信道上的單工停等式協(xié)議（3）序號（SEQ：sequencenumber）接收方需要區(qū)分到達(dá)的幀是第一次發(fā)來的新幀讓發(fā)送方在發(fā)送的幀的頭部放一個序號，接收方可以檢查它所收到的幀序號，由此判斷這是個新幀還是應(yīng)該被丟棄的重復(fù)幀。序號所需要的最小位數(shù)（bits）在這個協(xié)議中，唯一不明確的地方出現(xiàn)在當(dāng)前幀（序號m）和它的直接后續(xù)幀（序號m+1）1

bit序號(0或1)就足以滿足要求。自動重復(fù)請求，或帶有重傳的肯定確認(rèn)ARQ(AutomaticRepeatreQuest)PAR(PositiveAcknowledgementwithRetransmission)73發(fā)送方接收方時間SEQ=0發(fā)送方接收方超時重發(fā)SEQ=0SEQ=0丟棄重復(fù)幀確認(rèn)0丟失SEQ=1SEQ=0確認(rèn)0確認(rèn)1確認(rèn)0確認(rèn)0SEQ=1SEQ=0確認(rèn)13.3基本的數(shù)據(jù)鏈路層協(xié)議有錯信道上的單工停等式協(xié)議（4）74發(fā)送方初始化幀序號0，發(fā)送幀等待：正確的確認(rèn)/錯誤的確認(rèn)/超時正確確認(rèn)：發(fā)送下一幀超時/錯誤確認(rèn)：重發(fā)接收方初始化期待0號幀等待幀達(dá)到正確幀：交給網(wǎng)絡(luò)層，并發(fā)送該幀確認(rèn)錯誤幀：發(fā)送上一個成功接收幀的確認(rèn)3.3基本的數(shù)據(jù)鏈路層協(xié)議有錯信道上的單工停等式協(xié)議（5）效率的評估F=framesize(bits)

R=channelcapacity(Bandwidthinbits/second)I=propagationdelay+processorservicetime(second)

每幀發(fā)送時間(Timetotransmitasingleframe)=F/R總延遲(TotalDelay)=D=2I停止等待協(xié)議的發(fā)送工作時間是F/C，空閑時間是D當(dāng)F<D時：信道利用率(lineutilization)=F/(F+R?D)<50%753.3基本的數(shù)據(jù)鏈路層協(xié)議有錯信道上的單工停等式協(xié)議（6）停止等待協(xié)議的效率問題停止等待協(xié)議的問題是只能有一個沒有被確認(rèn)的幀在發(fā)送中舉例:長肥網(wǎng)絡(luò)Shortframelength:1000bitframesHighbandwidth:1Mbpschannel(衛(wèi)星信道)Longtransittime:270mspropagationdelay(傳播延遲)763.3基本的數(shù)據(jù)鏈路層協(xié)議長肥網(wǎng)絡(luò)(LFN，LongFatNetwork)：如果一個網(wǎng)絡(luò)的帶寬-延遲乘積(bandwidth-delayproduct)很明顯的大于105bits(~12kB)，則可以被認(rèn)為是長肥網(wǎng)絡(luò)有錯信道上的單工停等式協(xié)議（7）信道利用率很低：每一幀的發(fā)送時間是1毫秒(1000bits/(1,000,000bits/sec）).由于傳播延遲較長，發(fā)送者在541毫秒之后才能收到確認(rèn)，信道利用率1/541一種提高效率的方法：使用更大的幀可以使用更大的幀，但是幀的最大長度受到信道比特錯誤率（BER，Bit

Error

Ratio）的限制，幀越大，在傳輸中出錯的概率越高，將導(dǎo)致更多的重傳773.3基本的數(shù)據(jù)鏈路層協(xié)議本章內(nèi)容3.1數(shù)據(jù)鏈路層的設(shè)計(jì)問題3.2差錯檢測和糾正3.3基本的數(shù)據(jù)鏈路層協(xié)議3.4滑動窗口協(xié)議3.5數(shù)據(jù)鏈路協(xié)議實(shí)例78停等協(xié)議的性能問題滑動窗口協(xié)議回退N協(xié)議選擇重傳協(xié)議停等協(xié)議的性能問題停止-等待機(jī)制降低了信道利用率設(shè)數(shù)據(jù)速率記為R，幀長度記為F，往返延遲記為D，則采用停-等協(xié)議的線路效率為：F/(F+R?D)假如將鏈路看成是一根管道，數(shù)據(jù)是管道中流動的水，那么在傳輸延遲較長的信道上，停-等協(xié)議無法使數(shù)據(jù)充滿管道，因而信道利用率很低解決辦法流水線協(xié)議或管道協(xié)議：允許發(fā)送方在沒收到確認(rèn)前連續(xù)發(fā)送多個幀793.4滑動窗口協(xié)議滑動窗口協(xié)議—協(xié)議基本思想?yún)f(xié)議基本思想窗口機(jī)制發(fā)送方和接收方都具有一定容量的緩沖區(qū)（即窗口），發(fā)送端在收到確認(rèn)之前可以發(fā)送多個幀問題發(fā)送端一次可以發(fā)送多少個幀?某個幀出錯或丟失怎么處理？803.4滑動窗口協(xié)議滑動窗口協(xié)議—協(xié)議基本思想目的對可以連續(xù)發(fā)出的最多幀數(shù)（已發(fā)出但未確認(rèn)的幀）作限制序號使用循環(huán)重復(fù)使用有限的幀序號流量控制：接收窗口驅(qū)動發(fā)送窗口的轉(zhuǎn)動發(fā)送窗口：其大小記作WT，表示在收到對方確認(rèn)的信息之前，可以連續(xù)發(fā)出的最多數(shù)據(jù)幀數(shù)接收窗口：其大小記作WR

，為可以連續(xù)接收的最多數(shù)據(jù)幀數(shù)累計(jì)確認(rèn)：不必對收到的分組逐個發(fā)送確認(rèn)，而是對按序到達(dá)的最后一個分組發(fā)送確認(rèn)813.4滑動窗口協(xié)議滑動窗口協(xié)議—協(xié)議基本思想82序列號發(fā)送的最后幀序號發(fā)出一幀后窗口的下限前移一格收到確認(rèn)后窗口的上限前移01234567012345670已發(fā)送的幀可發(fā)送幀已接收的幀最后確認(rèn)的幀接收一幀后窗口的下限前移發(fā)出確認(rèn)后窗口的上限前移可接收幀01234567012345670發(fā)送窗口與接收窗口(窗口大小7)3.4滑動窗口協(xié)議滑動窗口協(xié)議—協(xié)議基本思想83發(fā)送窗口與接收窗口(窗口大小7)01234567S01234567R01234567②發(fā)送0,1,201234567③收到0,1,201234567④發(fā)ACK,n=301234567⑤收到ACK,n=301234567⑦收3,4,發(fā)ACK,n=501234567⑥發(fā)3,4,5①發(fā)送窗口初始化為7①接收窗口初始化為7滑動窗口協(xié)議—協(xié)議的實(shí)現(xiàn)分析84while(1){wait_for_event(&event);if(event==frame_arrival){from_physical_layer(&r);if(r.ack==next_frame_to_send){from_network_layer(&buffer);inc(next_frame_to_send);}}=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);}發(fā)送方（

WT=WR=1，序號空間0和1）初始化：ack_expected=frame_expected=next_frame_to_send=0從網(wǎng)絡(luò)層接收分組，放入相應(yīng)的緩沖區(qū)，構(gòu)造幀，物理層發(fā)送，開啟計(jì)時。等待確認(rèn)幀到達(dá)，從物理層接收一個幀，判斷確認(rèn)號是否正確，正確則停止計(jì)時器，并從網(wǎng)絡(luò)層接收新分組。發(fā)送新的幀，跳轉(zhuǎn)至33.4滑動窗口協(xié)議滑動窗口協(xié)議—協(xié)議的實(shí)現(xiàn)分析85while(1){wait_for_event(&event);if(event==frame_arrival){from_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);inc(frame_expected);}}=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);}接收方（

WT=WR=1，序號空間0和1）初始化：ack_expected=frame_expected=next_frame_to_send=0等待幀到達(dá)，從物理層接收一個幀，校驗(yàn)和計(jì)算，并判斷收到的幀序號是否正確，正確則交給網(wǎng)絡(luò)層處理，期待幀號增加。返回確認(rèn)幀，跳轉(zhuǎn)至2。3.4滑動窗口協(xié)議回退N協(xié)議—協(xié)議設(shè)計(jì)思想出錯全部重發(fā)當(dāng)接收端收到一個出錯幀或亂序幀時，丟棄所有的后繼幀，并且不為這些幀發(fā)送確認(rèn)發(fā)送端超時后，重傳所有未被確認(rèn)的幀適用場景該策略對應(yīng)接收窗口為1的情況，即只能按順序接收幀優(yōu)缺點(diǎn)優(yōu)點(diǎn)：連續(xù)發(fā)送提高了信道利用率缺點(diǎn)：按序接收，出錯后即便有正確幀到達(dá)也丟棄重傳863.4滑動窗口協(xié)議回退N協(xié)議—協(xié)議原理分析基本原理當(dāng)發(fā)送方發(fā)送了N個幀后，若發(fā)現(xiàn)該N幀的前一個幀在計(jì)時器超時后仍未返回其確認(rèn)信息，則該幀被判為出錯或丟失，此時發(fā)送方就重新發(fā)送出錯幀及其后的N幀?；瑒哟翱陂L度出錯全部重發(fā)時，若幀序號為n位，接收窗口WR=1，發(fā)送窗口WT≤2n－1873.4滑動窗口協(xié)議回退N協(xié)議—協(xié)議原理分析正常情況下的GBN88在回退N步協(xié)議中，允許發(fā)送方發(fā)送多個分組而不用等待確認(rèn)正常情況下，發(fā)送、接收窗口會隨著幀的確認(rèn)狀態(tài)隨包右移回退N協(xié)議—協(xié)議原理分析發(fā)送過程中數(shù)據(jù)包丟失89當(dāng)發(fā)送過程中的2號包發(fā)生丟失時：發(fā)送方?jīng)]有收到接收方的ACK2，于是后面發(fā)送的ACK3,ACK4全部變成了ACK1，代表接收方因?yàn)閬G失了分組2，所以分組3和分組4都被丟棄，全部返回ACK1經(jīng)過一段時間后，定時器確認(rèn)超時沒有收到ACK3,ACK4，所以發(fā)送方將重新發(fā)送?；赝薔協(xié)議—協(xié)議原理分析接收方返回的ACK丟失90假設(shè)ACK2發(fā)生了丟失時：如果接收方?jīng)]有收到分組2，則后面返回的都是ACK1，因?yàn)楸敬畏祷氐臑锳CK3,ACK4，所以發(fā)送方可以判斷接收方已經(jīng)接收到消息，不再進(jìn)行重復(fù)發(fā)送?；赝薔協(xié)議—協(xié)議的實(shí)現(xiàn)分析91實(shí)現(xiàn)要點(diǎn)必須增加序號范圍、發(fā)送方需要緩存多個分組兩個窗口發(fā)送窗口：發(fā)送方維持一組連續(xù)允許發(fā)送的幀序號接收窗口：接收方維持一組連續(xù)的允許接收幀序號發(fā)送方必須響應(yīng)的三件事上層的調(diào)用：檢測有沒有可以使用的序號，如果有就發(fā)送收到ACK：對n號幀的確認(rèn)采用累積確認(rèn)的方式超時事件：如果出現(xiàn)超時，就重傳所有已發(fā)送未確認(rèn)的分組3.4滑動窗口協(xié)議回退N協(xié)議—協(xié)議的實(shí)現(xiàn)分析92發(fā)送方：窗口尺寸：1<WT≤2n-1，最多連續(xù)發(fā)送窗口中的WT個PDU窗口滑動：收到期望的ACK(k)：窗口底部移到PDU(k)，窗口頂部向前移動，始終保持窗口里有WT個PDU未確認(rèn)。窗口滑動后，發(fā)送新進(jìn)入窗口的PDU超時重發(fā)：超過T未收到期望的ACK，重發(fā)窗口中的PDU（回退整個窗口）超次數(shù)失?。撼^最大重發(fā)次數(shù)Nmax仍無正確應(yīng)答3.4滑動窗口協(xié)議回退N協(xié)議—協(xié)議的實(shí)現(xiàn)分析93接收方：窗口尺寸：WR=1按序接收：按照PDU編號依序接收，出錯、亂序PDU一律丟棄確認(rèn)含義：ACK(k)表示對k-1及以前各編號的PDU的確認(rèn)，同時期望接收第k號PDU確認(rèn)策略：按序到達(dá)的PDU可立即確認(rèn)，也可延遲確認(rèn)(收到多幀后一起確認(rèn))，但出錯或亂序的PDU，確認(rèn)ACK(k)（期望接收k號PDU）或不應(yīng)答3.4滑動窗口協(xié)議回退N協(xié)議—協(xié)議的實(shí)現(xiàn)分析94實(shí)現(xiàn)基本過程如下：初始化。ack_expected=0(此時處于發(fā)送窗口的下沿)；next_frame_to_send=0，frame_expected=0(初始化正在發(fā)送的幀和期待的幀序號)；nbuffered=0(進(jìn)行發(fā)送大小初始化)等待事件發(fā)生（網(wǎng)絡(luò)層準(zhǔn)備好，幀到達(dá)，收到壞幀，超時）如果事件為網(wǎng)絡(luò)層準(zhǔn)備好，則執(zhí)行以下步驟。從網(wǎng)絡(luò)層接收一個分組，放入相應(yīng)的緩沖區(qū)；發(fā)送窗口大小加1；使用緩沖區(qū)中的數(shù)據(jù)分組、next_frame_to_send和frame_expected構(gòu)造幀，繼續(xù)發(fā)送；next_frame_to_send加1；跳轉(zhuǎn)（7）3.4滑動窗口協(xié)議while(1){wait_for_event(&event);switch(event){casenetwork_layer_ready:from_network_layer(&buffer[next_frame_to_send]);nbuffered=nbuffered+1;send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);break;

回退N協(xié)議—協(xié)議的實(shí)現(xiàn)分析95如果事件為幀到達(dá)，則從物理層接收一個幀，則執(zhí)行以下步驟。首先檢查幀的seq域，若正是期待接收的幀（seq=frame_expected），將幀中攜帶的分組交給網(wǎng)絡(luò)層，frame_expected加1；然后檢查幀的ack域，若ack落于發(fā)送窗口內(nèi)，表明該序號及其之前所有序號的幀均已正確收到，因此終止這些幀的計(jì)時器，修改發(fā)送窗口大小及發(fā)送窗口下沿值將這些幀去掉，繼續(xù)執(zhí)行步驟（7）3.4滑動窗口協(xié)議caseframe_arrival:from_physical_layer(&r);if(r.seq==frame_expected){to_network_layer(&);inc(frame_expected);}while(between(ack_expected,r.ack,net_frame_to_send)){nbuffered=nbuffered-1;stop_timer(ack_expected);inc(ack_expected);}break;回退N協(xié)議—協(xié)議的實(shí)現(xiàn)分析96如果事件是收到壞幀，繼續(xù)執(zhí)行步驟（7）如果事件是超時。使next_frame_to_send=ack_expected，從發(fā)生超時的幀開始重發(fā)發(fā)送窗口內(nèi)的所有幀，然后繼續(xù)執(zhí)行步驟（7）若發(fā)送窗口大小小于所允許的最大值（MAX-SEQ），則可繼續(xù)允許網(wǎng)絡(luò)層發(fā)送，否則則暫停網(wǎng)絡(luò)層發(fā)送3.4滑動窗口協(xié)議casecksum_err:；break;casetimeout:next_frame_to_send=ack_expected;for(i=1;i<=nbuffered;i++){send_data(next_frame_to_send,frame_expected,buffer);inc(next_frame_to_send);}}if(nbuffered<MAX_SEQ)enable_network_layer();elsedisable_network_layer();}選擇重傳協(xié)議—協(xié)議設(shè)計(jì)思想設(shè)計(jì)思想若發(fā)送方發(fā)出連續(xù)的若干幀后，收到對其中某一幀的否認(rèn)幀，或某一幀的定時器超時，則只重傳該出錯幀或計(jì)時器超時的數(shù)據(jù)幀適用場景該策略對應(yīng)接收窗口大于1的情況，即暫存接收窗口中序號在出錯幀之后的數(shù)據(jù)幀優(yōu)缺點(diǎn)優(yōu)點(diǎn)：避免重傳已正確傳送的幀缺點(diǎn)：在接收端需要占用一定容量的緩存973.4滑動窗口協(xié)議選擇重傳協(xié)議—協(xié)議原理分析基本原理在發(fā)送過程中，如果一個數(shù)據(jù)幀計(jì)時器超時，就認(rèn)為該幀丟失或者被破壞；接收端只把出錯的的幀丟棄，其后面的數(shù)據(jù)幀保存在緩存中，并向發(fā)送端回復(fù)NAK；發(fā)送端接收到NAK時，只重傳出錯的幀如果落在窗口內(nèi)的幀從未接受過，那么存儲起來，等比它序列號小的所有幀都正確接收后，按次序交付給網(wǎng)絡(luò)層接收端收到的數(shù)據(jù)包的順序可能和發(fā)送的數(shù)據(jù)包順序不一樣，因此在數(shù)據(jù)包里必須含有順序號來幫助接收端進(jìn)行排序?；瑒哟翱陂L度發(fā)送窗口的尺寸：WT≤2n-1,發(fā)送窗口應(yīng)等于或小于序號空間的一半983.4滑動窗口協(xié)議選擇重傳協(xié)議—協(xié)議原理分析正常情況下SR993.4滑動窗口協(xié)議同樣，在選擇重傳協(xié)議中，也允許發(fā)送方發(fā)送多個分組而不用等待確認(rèn)，與回退N步不同的是，接收窗口大小是大于1的正常情況下，發(fā)送、接收窗口會隨著幀的確認(rèn)狀態(tài)隨包右移選擇重傳協(xié)議—協(xié)議原理分析發(fā)送過程中發(fā)生丟包1003.4滑動窗口協(xié)議當(dāng)發(fā)送過程中的2號包發(fā)生丟失時：與GNB不同的是，接收方在沒有收到分組2的情況下，依然返回了ACK3,ACK4當(dāng)ACK1返回以后，分組5，分組6就已經(jīng)可以發(fā)送。然后在接收方，分組3456都已經(jīng)被緩存，等待分組2的計(jì)時器超時后，分組2將重新發(fā)送。選擇重傳協(xié)議—協(xié)議原理分析確認(rèn)過程發(fā)生丟包3.4滑動窗口協(xié)議當(dāng)ACK2丟棄時：發(fā)送方的分組已經(jīng)由0-4到了2-6,在最后2-6的窗口中。分組2會因?yàn)锳CK2被丟失然后在計(jì)時器計(jì)時后重新發(fā)送一次。如果在接收過程中有丟失發(fā)生，選擇重傳SR的效率是不如回退N步GBN的101選擇重傳協(xié)議—協(xié)議實(shí)現(xiàn)分析102實(shí)現(xiàn)要點(diǎn)在SR中，和GBN不同，SR是給每一個PDU設(shè)置定時器，發(fā)送端只重傳出錯PDU。接收端在接收到亂序的PDU的時候會進(jìn)行緩存，當(dāng)前面的PDU到達(dá)以后一起提交給上層兩個窗口發(fā)送窗口：發(fā)送方維持一組連續(xù)允許發(fā)送的幀序號接收窗口：接收方維持一組連續(xù)的允許接收幀序號發(fā)送方必須響應(yīng)的三件事上層的調(diào)用：檢測有沒有可以使用的序號，如果有就發(fā)送收到ACK：如果收到的是最小序號的ACK，窗口滑動。如果收到其他序號的ACK，進(jìn)行標(biāo)記超時事件：每個PDU都有定時器，哪個超時重傳哪個3.4滑動窗口協(xié)議選擇重傳協(xié)議—協(xié)議實(shí)現(xiàn)分析103發(fā)送方：窗口尺寸：1<WT≤2n-1，最多連續(xù)發(fā)送窗口中的WT個PDU窗口滑動：與回退N幀協(xié)議相同選擇重發(fā)：收到NAK

(k)，重發(fā)PDU(k)超時重發(fā)：超過T未收到期望的ACK，重發(fā)當(dāng)前超時未應(yīng)答的PDU超次數(shù)失敗：超過最大重發(fā)次數(shù)Nmax仍無正確應(yīng)答，報告上層失敗實(shí)現(xiàn)基本過程與回退N協(xié)議基本類似，其中3.4滑動窗口協(xié)議選擇重傳協(xié)議—協(xié)議實(shí)現(xiàn)分析104接收方：窗口尺寸：1<WR≤2n-1窗口滑動：窗口底部數(shù)據(jù)上交，窗口向前滑動一步窗口內(nèi)接收：窗口內(nèi)的PDU全部接收，存儲出錯的后續(xù)PDU，按序交付；窗口外的PDU一律丟棄確認(rèn)策略：按序到達(dá)的PDU可立即確認(rèn)，也可延遲確認(rèn)(收到多幀后一起確認(rèn))ACK(k)；出錯用否定性確認(rèn)NAK(k)（期望重發(fā)k號PDU）3.4滑動窗口協(xié)議選擇重傳協(xié)議—協(xié)議實(shí)現(xiàn)分析105實(shí)現(xiàn)基本過程如下：1、初始化。ack_expected=0(此時處于發(fā)送窗口的下沿)；next_frame_to_send=0，frame_expected=0（初始化正在發(fā)送的幀和期待的幀序號）；nbuffere