計(jì)算機(jī)網(wǎng)絡(luò)直接連接的網(wǎng)絡(luò)

計(jì)算機(jī)網(wǎng)絡(luò)直接連接的網(wǎng)絡(luò)1第1頁，共165頁，2023年，2月20日，星期二教學(xué)提示教學(xué)目的理解數(shù)據(jù)鏈路層服務(wù)，掌握可靠數(shù)據(jù)傳輸和多路訪問原理，熟練掌握各種鏈路層協(xié)議與設(shè)備重要知識點(diǎn)成幀差錯(cuò)檢測可靠數(shù)據(jù)傳輸多路訪問技術(shù)學(xué)習(xí)方法以基礎(chǔ)性問題為中心展開學(xué)習(xí)

MAC地址CSMA/CD以太網(wǎng)交換機(jī)IEEE802.112第2頁，共165頁，2023年，2月20日，星期二直連連接的網(wǎng)絡(luò)中的機(jī)制和設(shè)備機(jī)制設(shè)備在其他層可用3第3頁，共165頁，2023年，2月20日，星期二WhatisaLink?4CommunicationMediumNetworkAdapter4第4頁，共165頁，2023年，2月20日，星期二數(shù)據(jù)鏈路層的基本概念

鏈路(link)是一條無源的點(diǎn)到點(diǎn)的物理線路段，中間沒有任何其他的交換結(jié)點(diǎn)。一條鏈路只是一條通路的一個(gè)組成部分。數(shù)據(jù)鏈路(datalink)除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路?，F(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來實(shí)現(xiàn)這些協(xié)議的硬件和軟件。一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層的功能。

5第5頁，共165頁，2023年，2月20日，星期二工作場景最簡單網(wǎng)絡(luò)：用某種傳輸媒體連接所有主機(jī)涉及數(shù)據(jù)鏈路層技術(shù)單段鏈路使用點(diǎn)到點(diǎn)通信協(xié)議或廣播多路訪問協(xié)議為大型網(wǎng)絡(luò)提供某“一跳”的低層通信支撐以太網(wǎng)無線局域網(wǎng)路由器IP網(wǎng)絡(luò)通信網(wǎng)6第6頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)7第7頁，共165頁，2023年，2月20日，星期二鏈路層環(huán)境鏈路層協(xié)議任務(wù)：通過單段鏈路，點(diǎn)到點(diǎn)傳送上層數(shù)據(jù)報(bào)定義了鏈路兩端結(jié)點(diǎn)間交互的幀格式，以及發(fā)送和接收幀時(shí)的操作兩種網(wǎng)絡(luò)鏈路類型點(diǎn)對點(diǎn)鏈路廣播鏈路8第8頁，共165頁，2023年，2月20日，星期二點(diǎn)對點(diǎn)鏈路：由鏈路一端的單個(gè)發(fā)送結(jié)點(diǎn)和鏈路另一端的單個(gè)接收結(jié)點(diǎn)組成。這種鏈路使用一對一的點(diǎn)對點(diǎn)通信方式。廣播鏈路：能夠讓多個(gè)發(fā)送結(jié)點(diǎn)和接收結(jié)點(diǎn)都連接到單一的，共享的廣播信道上。這種鏈路使用一對多的廣播通信方式。因廣播鏈路上連接的主機(jī)很多，必須使用專用的共享鏈路協(xié)議來協(xié)調(diào)這些主機(jī)的數(shù)據(jù)發(fā)送。9第9頁，共165頁，2023年，2月20日，星期二鏈路層環(huán)境鏈路層環(huán)境重要特點(diǎn)一條路徑上的不同鏈路可運(yùn)行不同的鏈路層協(xié)議鏈路層協(xié)議提供的服務(wù)可以不同通信環(huán)境較為簡單10第10頁，共165頁，2023年，2月20日，星期二利用不同交通工具旅游的例子北京杭州黃山首都機(jī)場杭州機(jī)場黃山火車站11第11頁，共165頁，2023年，2月20日，星期二鏈路層的基本服務(wù)就是將網(wǎng)絡(luò)層分組通過單段通信鏈路從一個(gè)結(jié)點(diǎn)移動到相鄰結(jié)點(diǎn)。且其所提供的服務(wù)會隨著鏈路層協(xié)議轉(zhuǎn)變而改變。12第12頁，共165頁，2023年，2月20日，星期二鏈路層協(xié)議的設(shè)計(jì)問題1.成幀將數(shù)據(jù)報(bào)封裝進(jìn)幀，加上首部和尾部，幀定界問題2.媒體訪問規(guī)定了結(jié)點(diǎn)在鏈路上傳輸幀的規(guī)則如何共享媒體，如何訪問信道？用媒體訪問控制(MAC)協(xié)議協(xié)調(diào)結(jié)點(diǎn)之間的幀傳輸

3.相連結(jié)點(diǎn)間的可靠交付是網(wǎng)絡(luò)中基礎(chǔ)性問題（無差錯(cuò)的傳輸每個(gè)幀）在比特差錯(cuò)低的鏈路很少使用(光纖，雙絞線)無線鏈路:高差錯(cuò)率則需要13第13頁，共165頁，2023年，2月20日，星期二鏈路層服務(wù)的設(shè)計(jì)問題(續(xù))4.流量控制相鄰發(fā)送和接收結(jié)點(diǎn)間的步調(diào)協(xié)調(diào)（防止接收結(jié)點(diǎn)緩沖區(qū)溢出）5.差錯(cuò)檢測差錯(cuò)由信號衰減、噪聲所致接收方檢測出差錯(cuò)，將幀丟棄發(fā)送方負(fù)責(zé)重傳通常用硬件實(shí)現(xiàn)6.糾錯(cuò)接收方識別和糾正比特差錯(cuò)，而不采取重傳14第14頁，共165頁，2023年，2月20日，星期二網(wǎng)絡(luò)適配器及其與協(xié)議棧功能的關(guān)系問題：鏈路層功能在哪里？網(wǎng)絡(luò)適配器設(shè)備驅(qū)動程序15第15頁，共165頁，2023年，2月20日，星期二網(wǎng)絡(luò)適配器也成為網(wǎng)絡(luò)接口卡或網(wǎng)卡。網(wǎng)絡(luò)適配器通常與系統(tǒng)的I/O總線相連，在結(jié)點(diǎn)內(nèi)存和網(wǎng)絡(luò)鏈路之間傳輸數(shù)據(jù)。結(jié)點(diǎn)上運(yùn)行的一個(gè)軟件模塊稱為設(shè)備驅(qū)動程序，用來管理網(wǎng)絡(luò)適配器。鏈路層功能的主體部分是在網(wǎng)絡(luò)適配器中實(shí)現(xiàn)的（鏈路層控制器）。16第16頁，共165頁，2023年，2月20日，星期二17第17頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)18第18頁，共165頁，2023年，2月20日，星期二IP數(shù)據(jù)報(bào)1010……0110幀取出數(shù)據(jù)鏈路層網(wǎng)絡(luò)層鏈路結(jié)點(diǎn)A結(jié)點(diǎn)B物理層數(shù)據(jù)鏈路層結(jié)點(diǎn)A結(jié)點(diǎn)B幀(a)(b)發(fā)送幀接收鏈路IP數(shù)據(jù)報(bào)1010……0110幀裝入數(shù)據(jù)鏈路層傳送的是幀19第19頁，共165頁，2023年，2月20日，星期二在分組交換網(wǎng)絡(luò)中，結(jié)點(diǎn)交換的是數(shù)據(jù)塊而不是比特流。結(jié)點(diǎn)的網(wǎng)絡(luò)適配器通過鏈路層協(xié)議在結(jié)點(diǎn)之間交換幀（一個(gè)比特序列）。為了完成幀在結(jié)點(diǎn)之間的傳輸，適配器首先要準(zhǔn)確識別這個(gè)比特序列具有什么樣的幀結(jié)構(gòu)，即決定幀從哪里開始到哪里結(jié)束。20第20頁，共165頁，2023年，2月20日，星期二面向比特的協(xié)議面向比特的協(xié)議把幀看成比特的集合以HDLC協(xié)議為例，用特別的比特序列表示幀的開始和結(jié)束（01111110）比特填充(bitstuffing)法(用于發(fā)送前/接收后)發(fā)送方：報(bào)文中5個(gè)連續(xù)1，插入0接收方：收到5個(gè)連續(xù)1：后為0，去掉；為1，后為0，則幀結(jié)束；否則出錯(cuò)21第21頁，共165頁，2023年，2月20日，星期二PPP協(xié)議點(diǎn)對點(diǎn)協(xié)議(PPP)家庭主機(jī)到第一跳路由器的點(diǎn)對點(diǎn)鏈路的鏈路層協(xié)議用戶使用撥號電話線接入因特網(wǎng)時(shí)，一般都是使用PPP協(xié)議。PPP協(xié)議是家庭用戶的計(jì)算機(jī)和ISP進(jìn)行通信時(shí)所使用的數(shù)據(jù)鏈路層協(xié)議。22第22頁，共165頁，2023年，2月20日，星期二用戶到ISP的鏈路使用PPP協(xié)議用戶至因特網(wǎng)已向因特網(wǎng)管理機(jī)構(gòu)申請到一批

IP地址ISP接入網(wǎng)PPP

協(xié)議23第23頁，共165頁，2023年，2月20日，星期二PPP協(xié)議的幀格式協(xié)議代碼24第24頁，共165頁，2023年，2月20日，星期二PPP協(xié)議的幀格式PPP有一個(gè)2個(gè)字節(jié)的協(xié)議字段。當(dāng)協(xié)議字段為0x0021時(shí)，PPP幀的信息字段就是IP數(shù)據(jù)報(bào)。若為0xC021,則信息字段是PPP鏈路控制數(shù)據(jù)。若為0x8021，則表示這是網(wǎng)絡(luò)控制數(shù)據(jù)。

IP數(shù)據(jù)報(bào)1211字節(jié)12不超過1500字節(jié)PPP幀先發(fā)送7EFF03FACFCSF7E協(xié)議信息部分首部尾部25第25頁，共165頁，2023年，2月20日，星期二面向字節(jié)的協(xié)議早期每幀都看成是字節(jié)的集合保留一組字符為控制字符同步字符SYN；首部開始符SOH；正文開始符STX；正文結(jié)束符ETX；轉(zhuǎn)義字符DLE效率較低，目前已很少使用DLE字符的“轉(zhuǎn)義”作用信息DLESTXADLEBDLEETX在網(wǎng)絡(luò)中傳送26第26頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)奇偶校驗(yàn)檢驗(yàn)和方法循環(huán)冗余檢測(CRC)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)27第27頁，共165頁，2023年，2月20日，星期二為了保證數(shù)據(jù)的可靠傳輸，在數(shù)據(jù)傳輸出現(xiàn)錯(cuò)誤后，有兩種處理方法，一是檢錯(cuò)重發(fā)；二是前向糾錯(cuò)。28第28頁，共165頁，2023年，2月20日，星期二處理幀差錯(cuò)兩種方法檢錯(cuò)重發(fā)(detectandretransmission)檢測到發(fā)送方報(bào)文受損，則通知發(fā)送方重傳副本差錯(cuò)率低效果好前向糾錯(cuò)(ForwardErrorCorrection,FEC)糾錯(cuò)通過“預(yù)先”發(fā)送額外信息進(jìn)行時(shí)效性好適用場合檢錯(cuò)重發(fā)適合鏈路差錯(cuò)率很低的場合，如有線通信前向糾錯(cuò)適合對時(shí)間要求很高的場合，如航天和實(shí)時(shí)控制29第29頁，共165頁，2023年，2月20日，星期二

為此，首先要檢查出誤碼。這樣就需要在傳輸數(shù)據(jù)時(shí)加上能夠檢查出錯(cuò)誤或能夠定位錯(cuò)誤的冗余信息。冗余信息——用某種明確定義的算法直接從原始報(bào)文中導(dǎo)出的信息。30第30頁，共165頁，2023年，2月20日，星期二差錯(cuò)檢測EDC：差錯(cuò)檢測和糾錯(cuò)比特(冗余)D：數(shù)據(jù)由差錯(cuò)校驗(yàn)保護(hù)，可能包括首部字段

易出現(xiàn)比特錯(cuò)鏈路

31第31頁，共165頁，2023年，2月20日，星期二差錯(cuò)檢測不是100%可靠!

協(xié)議可能漏掉某些差錯(cuò)，但是非常少較大的EDC字段產(chǎn)生更好的檢測和糾正一種優(yōu)秀的差錯(cuò)檢測方法應(yīng)當(dāng)滿足：加入的冗余信息較少，而能檢測出所有的差錯(cuò)。

32第32頁，共165頁，2023年，2月20日，星期二差錯(cuò)檢測方法奇偶校驗(yàn)檢驗(yàn)和方法循環(huán)冗余檢驗(yàn)33第33頁，共165頁，2023年，2月20日，星期二奇偶校驗(yàn)奇偶校驗(yàn)碼是奇校驗(yàn)碼和偶校驗(yàn)碼的統(tǒng)稱，是一種最基本的檢錯(cuò)碼。用單個(gè)奇偶校驗(yàn)位可檢測出鏈路發(fā)生的單個(gè)比特差錯(cuò)。發(fā)送方發(fā)送的信息由n-1位信息元和1位校驗(yàn)元組成，可以表示成為（n，n-1）。如果是奇校驗(yàn)碼，在附加上一個(gè)校驗(yàn)元以后，碼長為n的碼字中“1”的個(gè)數(shù)為奇數(shù)個(gè)；如果是偶校驗(yàn)碼，在附加上一個(gè)校驗(yàn)元以后，碼長為n的碼字中“1”的個(gè)數(shù)為偶數(shù)個(gè)。例：

信息字段

奇校驗(yàn)碼

偶校驗(yàn)碼

0110001

01100010

01100011編碼效率：Q/(Q+1)

(信息字段占Q個(gè)比特)34第34頁，共165頁，2023年，2月20日，星期二奇偶校驗(yàn)二維比特奇偶校驗(yàn):檢測到所有1,2,3個(gè)比特差錯(cuò)和大部分4bit差錯(cuò)和糾正1個(gè)比特差錯(cuò)。00奇偶差錯(cuò)奇偶差錯(cuò)可糾正的單比特差錯(cuò)無差錯(cuò)35第35頁，共165頁，2023年，2月20日，星期二檢驗(yàn)和方法檢驗(yàn)和方法（可用于因特網(wǎng)網(wǎng)絡(luò)層）思想：將傳輸?shù)乃凶止?jié)當(dāng)做整數(shù)加起來，其和作為檢驗(yàn)和，然后將這個(gè)檢驗(yàn)和連同數(shù)據(jù)傳輸?shù)浇邮辗?，接收方對收到的?shù)據(jù)執(zhí)行相同的計(jì)算，再把得到的結(jié)果與收到的檢驗(yàn)和進(jìn)行比較。因特網(wǎng)檢驗(yàn)和就基于這種方法。36第36頁，共165頁，2023年，2月20日，星期二因特網(wǎng)檢驗(yàn)和發(fā)送方:將段內(nèi)容作為16比特整數(shù)序列來處理檢驗(yàn)和:連續(xù)兩兩求和，校驗(yàn)和為和的反碼發(fā)送方將檢驗(yàn)和的值放入

檢驗(yàn)和字段接收方:計(jì)算接收到段的檢驗(yàn)和檢查是否計(jì)算的檢驗(yàn)和等于檢驗(yàn)和字段的值:NO–

檢測到差錯(cuò)YES–

沒有檢測到差錯(cuò)，仍可能有錯(cuò)目標(biāo)：檢測傳輸段中的“差錯(cuò)”(如比特翻轉(zhuǎn))37第37頁，共165頁，2023年，2月20日，星期二因特網(wǎng)檢驗(yàn)和例子注意：當(dāng)作加法時(shí)，最高位進(jìn)比特位的進(jìn)位需要加到結(jié)果中例子：

3個(gè)16bit的整數(shù)1100011001100110，1111010101010101，1000111100001100相加1

1100011001100110

111

1010101010101110111011101110111

1011101110111100100011110000110010100101011001000010010101100100111011010100110110回卷和檢查和(求反)和回卷38第38頁，共165頁，2023年，2月20日，星期二因特網(wǎng)檢驗(yàn)和檢錯(cuò)效果

對不同的報(bào)文，容易找到具有相同檢驗(yàn)和的另一段報(bào)文:IOU100.99BOB494F553130302E393942D242messageASCIIformatB2C1D2ACIOU900.19BOB494F553930302E313942D242messageASCIIformatB2C1D2AC不同的報(bào)文但相同的檢驗(yàn)和!效果不好!

報(bào)文

報(bào)文ASCII形式ASCII形式39第39頁，共165頁，2023年，2月20日，星期二循環(huán)冗余檢驗(yàn)為了提供很強(qiáng)的差錯(cuò)檢測能力，現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)普遍在鏈路層用硬件芯片實(shí)現(xiàn)了基于循環(huán)冗余檢驗(yàn)（CRC—CyclicRedundancyCheck）編碼的差錯(cuò)檢驗(yàn)技術(shù)。

40第40頁，共165頁，2023年，2月20日，星期二循環(huán)冗余檢驗(yàn)的原理

假設(shè)待傳送的數(shù)據(jù)M=1010001101（共kbit）。發(fā)送方和接收方協(xié)商一個(gè)mbit的除數(shù)P即可確定我們在數(shù)據(jù)M的后面添加的供差錯(cuò)檢測用冗余碼的長度為nbit（n=m-1）。

41第41頁，共165頁，2023年，2月20日，星期二冗余碼的計(jì)算

用二進(jìn)制的模2

運(yùn)算進(jìn)行2n乘M的運(yùn)算，這相當(dāng)于在M后面添加n個(gè)0。得到的(k+n)bit的數(shù)除以事先選定好的長度為mbit

的數(shù)P，得出商是Q而余數(shù)是R（即為所求的冗余碼），所得余數(shù)R比除數(shù)P至少要少1個(gè)比特。

42第42頁，共165頁，2023年，2月20日，星期二設(shè)

M=1010001101,P=110101，即

n=5,模2運(yùn)算的結(jié)果是：商Q=1101010110，

余數(shù)R=01110。將余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去，即發(fā)送的數(shù)據(jù)是101000110101110，或2nM+R。43第43頁，共165頁，2023年，2月20日，星期二

1101010110

←

Q

商

除數(shù)

P→

110101101000110100000

←

2nM被除數(shù)

110101

111011

110101

111010

110101

111110

110101

101100

110101

110010

110101

01110

←

R

余數(shù)44第44頁，共165頁，2023年，2月20日，星期二接收方如何檢測呢？用接收端收到得數(shù)據(jù)除以P（發(fā)送端事先定好的那個(gè)）如果所得余數(shù)為0，則在傳輸過程中沒有產(chǎn)生誤碼；如果所得余數(shù)不為0，則在傳輸過程中產(chǎn)生了誤碼；45第45頁，共165頁，2023年，2月20日，星期二但這種檢測方法并不能確定究竟是哪一個(gè)或哪幾個(gè)比特出現(xiàn)了差錯(cuò)。一旦檢測出差錯(cuò)，就丟棄這個(gè)出現(xiàn)差錯(cuò)的幀。注意：能不能說所得余數(shù)為0，就肯定沒有出現(xiàn)差錯(cuò)？只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)P，那么出現(xiàn)檢測不到的差錯(cuò)的概率就很小很小。

檢測出錯(cuò)了？46第46頁，共165頁，2023年，2月20日，星期二

任何一個(gè)由二進(jìn)制數(shù)位串組成的代碼可以和一個(gè)只含有0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對應(yīng)的關(guān)系。

例如，代碼1010111對應(yīng)的多項(xiàng)式為X6+X4+X2+X+1，而多項(xiàng)式X5+X3+X2十X十1對應(yīng)的代碼為101111。47第47頁，共165頁，2023年，2月20日，星期二目前，廣泛使用的除數(shù)P主要有四種:CRC12＝X12十X11十X3十X2+1CRC16＝X16十X15十X2十1(IBM公司)CRC16＝X16十X12十X5十1(CCITT)CRC32＝X32十X26十X23十X22十X16十X11十X10十X8十X7十X5十X4十X2+X+1

48第48頁，共165頁，2023年，2月20日，星期二應(yīng)當(dāng)注意

僅用循環(huán)冗余檢驗(yàn)CRC差錯(cuò)檢測技術(shù)只能做到無差錯(cuò)接受(accept)?！盁o差錯(cuò)接受”是指：“凡是接受的幀（即不包括丟棄的幀），我們都能以非常接近于1的概率認(rèn)為這些幀在傳輸過程中沒有產(chǎn)生差錯(cuò)”。也就是說：“凡是接收端數(shù)據(jù)鏈路層接受的幀都沒有差錯(cuò)”（有差錯(cuò)的幀就丟棄而不接受）。傳輸差錯(cuò)可分為兩大類：幀出現(xiàn)比特差差錯(cuò)；幀丟失、幀重復(fù)和幀失序?！翱煽總鬏敗保窗l(fā)送什么就收到什么）就必須再加上幀編號、確認(rèn)和重傳機(jī)制。

49第49頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議流水線可靠數(shù)據(jù)傳輸協(xié)議回退N步協(xié)議選擇重傳協(xié)議3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)50第50頁，共165頁，2023年，2月20日，星期二可靠數(shù)據(jù)傳輸：服務(wù)模型與服務(wù)實(shí)現(xiàn)可靠數(shù)據(jù)傳輸是互聯(lián)網(wǎng)中最為重要的問題之一該問題在多層協(xié)議中出現(xiàn)一般服務(wù)模型51第51頁，共165頁，2023年，2月20日，星期二設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議基本思想：在分組傳輸過程進(jìn)行差錯(cuò)檢測，一旦接收方發(fā)現(xiàn)差錯(cuò)，就應(yīng)當(dāng)告知發(fā)送方，由發(fā)送方重傳該分組學(xué)習(xí)方法：研究一系列協(xié)議，一步解決一個(gè)問題，直至實(shí)用52第52頁，共165頁，2023年，2月20日，星期二設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議：SW0協(xié)議前提條件：信道不丟包解決方案：接到正確PKT，發(fā)送一個(gè)肯定確認(rèn)(ACK)收到錯(cuò)誤PKT，發(fā)送一個(gè)否定確認(rèn)(NAK)，重傳原PKT停止等待(stop-and-wait,SW)協(xié)議實(shí)用中有不少漏洞53第53頁，共165頁，2023年，2月20日，星期二設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議：SW1協(xié)議條件：信道丟包SW0的發(fā)送方會一直等待ACK，引起協(xié)議死鎖解決方案：增加超時(shí)定時(shí)器每發(fā)PKT，啟動超時(shí)定時(shí)器，稱為超時(shí)重傳機(jī)制重傳時(shí)間略大于平均RTT無需NAK（否認(rèn)確認(rèn)）54第54頁，共165頁，2023年，2月20日，星期二設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議：SW2協(xié)議條件：確認(rèn)分組丟失出現(xiàn)了分組冗余的差錯(cuò)解決方案：增加一種新機(jī)制：發(fā)送序號序號空間要較小如發(fā)送序號3bit，在0~7間循環(huán)使用55第55頁，共165頁，2023年，2月20日，星期二設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議：SW3協(xié)議對確認(rèn)進(jìn)行編號？收到重復(fù)的確認(rèn)，無法分辨對應(yīng)哪個(gè)分組解決方案：增加確認(rèn)序號機(jī)制，分辨出確認(rèn)對應(yīng)哪個(gè)分組綜合以上機(jī)制為SW協(xié)議，或自動重傳請求(ARQ)設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議機(jī)制：差錯(cuò)檢測、接收方確認(rèn)(肯定/否定)、重傳、定時(shí)器和序號(數(shù)據(jù)和確認(rèn))56第56頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議流水線可靠數(shù)據(jù)傳輸協(xié)議回退N步協(xié)議選擇重傳協(xié)議3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)57第57頁，共165頁，2023年，2月20日，星期二流水線協(xié)議2.5Gbps光傳輸系統(tǒng)，RTT為35ms。分組長L＝1,500byte，發(fā)送時(shí)延信道的利用率改進(jìn)停止等待協(xié)議，提高傳輸效率58第58頁，共165頁，2023年，2月20日，星期二流水線:提高協(xié)議利用率59第59頁，共165頁，2023年，2月20日，星期二可連續(xù)發(fā)送若干個(gè)分組，提高信道利用率實(shí)際的協(xié)議一次至少允許連續(xù)發(fā)送256個(gè)分組，協(xié)議效率至少提高256倍!看似n個(gè)分組被填充到一條流水線上，故此技術(shù)被稱為流水線60第60頁，共165頁，2023年，2月20日，星期二流水線傳輸流水線:發(fā)送方允許發(fā)送多個(gè)、傳輸中、未應(yīng)答的分組，不必每發(fā)完一個(gè)分組就停頓下來等待對方的確認(rèn)。由于信道上一直有數(shù)據(jù)不間斷地傳送，這種傳輸方式可獲得很高的信道利用率。B分組ttAACK61第61頁，共165頁，2023年，2月20日，星期二流水線協(xié)議必須增加序號范圍發(fā)送方和/或接收方設(shè)有緩沖兩種流水線協(xié)議:

回退N步（go-Back-N）,選擇性重傳（S-R）62第62頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議流水線可靠數(shù)據(jù)傳輸協(xié)議回退N步協(xié)議選擇重傳協(xié)議3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)63第63頁，共165頁，2023年，2月20日，星期二如何處理流水線差錯(cuò)？使用流水線技術(shù)傳輸分組時(shí)，若出現(xiàn)接收方或網(wǎng)絡(luò)來不及處理這些分組情況，就會導(dǎo)致丟包。當(dāng)流水線差錯(cuò)時(shí)，對所需序號窗口和緩沖的要求取決于數(shù)據(jù)傳輸協(xié)議處理丟失、損壞及時(shí)延過大分組的方式恢復(fù)流水線差錯(cuò)的兩種基本方法回退N步(Go-Back-N，GBN)選擇重傳(SelectiveRepeat,SR)64第64頁，共165頁，2023年，2月20日，星期二GBN協(xié)議在流水線傳輸?shù)幕A(chǔ)上。通過發(fā)送窗口機(jī)制來限制發(fā)送方連續(xù)發(fā)送分組的個(gè)數(shù)?；赝薔步協(xié)議(Go-Back-N)65第65頁，共165頁，2023年，2月20日，星期二回退N步協(xié)議(Go-Back-N)發(fā)送方:在分組首部需要K比特序號，2k=N（序號循環(huán)使用）“窗口”最大為N,允許連續(xù)發(fā)送N個(gè)沒有應(yīng)答分組滑動窗口(流水線)已確認(rèn)已發(fā)送但未確認(rèn)可用但未發(fā)送不可用窗口長度N發(fā)送基序號下一個(gè)序號66第66頁，共165頁，2023年，2月20日，星期二發(fā)送窗口機(jī)制123456789101112(a)發(fā)送方維持發(fā)送窗口（發(fā)送窗口是5）發(fā)送窗口(b)收到對第一個(gè)分組的確認(rèn)后發(fā)送窗口向前滑動向前123456789101112發(fā)送窗口位于發(fā)送窗口的中的分組可以連續(xù)發(fā)送出去，而不需要等待對方的確認(rèn)信息67第67頁，共165頁，2023年，2月20日，星期二GBN協(xié)議注意點(diǎn)接收方按序根據(jù)滑動窗口的序號接收分組GBN協(xié)議的接收窗口的長度為1窗口中失序的分組將被丟棄（接收方除了丟棄失序分組外，還要對最近按序接收的分組進(jìn)行確認(rèn)）發(fā)送方采用超時(shí)機(jī)制來重傳出現(xiàn)丟失會差錯(cuò)的分組接收方可采用累積確認(rèn)的方式68第68頁，共165頁，2023年，2月20日，星期二GBN協(xié)議例子發(fā)送窗口為3，序號范圍為[0，3]69第69頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理設(shè)計(jì)可靠數(shù)據(jù)傳輸協(xié)議流水線可靠數(shù)據(jù)傳輸協(xié)議回退N步協(xié)議選擇重傳協(xié)議3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)70第70頁，共165頁，2023年，2月20日，星期二選擇性重傳(SelectiveRepeat)問題：GBN是否還能夠改善？(單一差錯(cuò)可能導(dǎo)致大量不必要重傳)接收方可分別確認(rèn)所有正確接收的報(bào)文段緩存失序分組,以便最后按序交付給上層發(fā)送方只需要重傳沒有收到ACK的分組發(fā)送方定時(shí)器對每個(gè)分組計(jì)時(shí)發(fā)送窗口N個(gè)連續(xù)的序號也需要限制已發(fā)送但尚未應(yīng)答分組的序號71第71頁，共165頁，2023年，2月20日，星期二選擇性重傳:發(fā)送方/接收方窗口a.發(fā)送方看到的序號b.接收方看到的序號已經(jīng)確認(rèn)可用，還未發(fā)送發(fā)送，還未確認(rèn)不可用可接受（窗口內(nèi)）失序(已緩存)但已被確認(rèn)期待，還未收到不可用窗口長度N窗口長度N發(fā)送基序號接收基序號下一個(gè)序號72第72頁，共165頁，2023年，2月20日，星期二選擇性重傳算法上層傳來數(shù)據(jù):如果窗口中下一個(gè)序號可用,發(fā)送報(bào)文段timeout(n):重傳丟失分組n,重啟其計(jì)時(shí)器ACK(n)在[發(fā)送基,發(fā)送基+N]:標(biāo)記分組n已經(jīng)收到如果n是最小未收到應(yīng)答的分組，向前滑動窗口基指針到下一個(gè)未確認(rèn)序號發(fā)送方分組n在[接收基,接收基+N-1]發(fā)送ACK(n)失序:緩存按序:交付(也交付所有緩存的按序分組),向前滑動窗口到下一個(gè)未收到報(bào)文段的序號分組n在[接收基-N,接收基-1]ACK(n)其他:忽略接收到的分組接收方73第73頁，共165頁，2023年，2月20日，星期二選擇重傳的例子74第74頁，共165頁，2023年，2月20日，星期二SR:窗口長度問題（序號空間有限時(shí)）例子:序號:0,1,2,3窗口長度=3接收方：在(a)和(b)兩種情況下，接收方?jīng)]有發(fā)現(xiàn)兩者間的差別!在(a)和(b)接收方無法區(qū)分接收到的分組是重傳的還是新的。問題:

序號長度與窗口長度有什么關(guān)系?回答：窗口長度小于等于序號空間的一半75第75頁，共165頁，2023年，2月20日，星期二可靠數(shù)據(jù)傳輸機(jī)制及用途小結(jié)機(jī)制用途和說明檢驗(yàn)和用于檢測在一個(gè)傳輸分組中的比特錯(cuò)誤。定時(shí)器用于超時(shí)/重傳一個(gè)分組，可能因?yàn)樵摲纸M（或其ACK）在信道中丟失了。由于當(dāng)一個(gè)分組被時(shí)延但未丟失（過早超時(shí)），或當(dāng)一個(gè)分組已被接收方收到但從接收方到發(fā)送方的ACK丟失時(shí)，可能產(chǎn)生超時(shí)事件，所以接收方可能會收到一個(gè)分組的多個(gè)冗余拷貝。序號用于為從發(fā)送方流向接收方的數(shù)據(jù)分組按順序編號。所接收分組的序號間的空隙可使該接收方檢測出丟失的分組。具有相同序號的分組可使接收方檢測出一個(gè)分組的冗余拷貝。確認(rèn)接收方用于告訴發(fā)送方一個(gè)分組或一組分組已被正確地接收到了。確認(rèn)報(bào)文通常攜帶著被確認(rèn)的分組或多個(gè)分組的序號。確認(rèn)可以是逐個(gè)的或累積的，這取決于協(xié)議。否定確認(rèn)接收方用于告訴發(fā)送方某個(gè)分組未被正確地接收。否定確認(rèn)報(bào)文通常攜帶著未被正確接收的分組的序號。窗口、流水線發(fā)送方也許被限制僅發(fā)送那些序號落在一個(gè)指定范圍內(nèi)的分組。通過允許一次發(fā)送多個(gè)分組但未被確認(rèn)，發(fā)送方的利用率可在停等操作模式的基礎(chǔ)上得到增加。窗口長度可根據(jù)接收方接收和緩存報(bào)文的能力或網(wǎng)絡(luò)中的擁塞程度，或兩者情況來進(jìn)行設(shè)置。76第76頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議信道劃分協(xié)議輪流協(xié)議隨機(jī)接入?yún)f(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)77第77頁，共165頁，2023年，2月20日，星期二多路訪問(multipleaccess)鏈路和協(xié)議多路訪問多個(gè)發(fā)送/接收結(jié)點(diǎn)同時(shí)使用廣播信道，如何協(xié)調(diào)它們共享一個(gè)信道局域網(wǎng)環(huán)境，密集端系統(tǒng)通常使用多路訪問方式應(yīng)用場景：信道資源緊缺，大量端系統(tǒng)或者頻繁訪問網(wǎng)絡(luò)，或者以較小概率訪問網(wǎng)絡(luò)78第78頁，共165頁，2023年，2月20日，星期二多路訪問協(xié)議：共享單一廣播信道兩個(gè)或更多結(jié)點(diǎn)并行傳輸相互干擾碰撞：如果結(jié)點(diǎn)同時(shí)接收到兩個(gè)或更多信號多路訪問協(xié)議決定結(jié)點(diǎn)怎樣共享信道的分布式算法，如：決定何時(shí)結(jié)點(diǎn)能夠傳輸？出現(xiàn)碰撞時(shí)如何解決？共享信道的通信必須使用信道本身!不能用帶外信道來協(xié)調(diào)79第79頁，共165頁，2023年，2月20日，星期二理想的多路訪問協(xié)議速率Rbps的廣播信道1.當(dāng)只有一個(gè)結(jié)點(diǎn)時(shí)，能夠以速率R發(fā)送2.當(dāng)有M個(gè)結(jié)點(diǎn)時(shí)，每個(gè)能以平均速率R/M發(fā)送3.分布式:無特殊結(jié)點(diǎn)來協(xié)調(diào)傳輸無同步時(shí)鐘、時(shí)隙4.簡單80第80頁，共165頁，2023年，2月20日，星期二多路訪問協(xié)議:分類有3種類型:信道劃分將信道劃分為較小的“段”

(時(shí)隙，頻率，編碼)為每個(gè)結(jié)點(diǎn)分配一部分專用輪流結(jié)點(diǎn)輪流，信息較多的輪流發(fā)送的時(shí)間較長隨機(jī)訪問不劃分信道，允許碰撞設(shè)法從“碰撞”恢復(fù)問題：協(xié)議應(yīng)用場景不同，設(shè)計(jì)協(xié)議的方法是否有所不同？81第81頁，共165頁，2023年，2月20日，星期二信道劃分協(xié)議:TDMATDMA:時(shí)分多路訪問

“循環(huán)”訪問信道每個(gè)站點(diǎn)在每個(gè)循環(huán)中獲得固定長度時(shí)隙(長度=分組傳輸時(shí)間)不使用的時(shí)隙則空閑例子：6個(gè)站點(diǎn)的LAN,時(shí)隙1、3、4有分組,時(shí)隙2、5、6空閑(浪費(fèi))82第82頁，共165頁，2023年，2月20日，星期二信道劃分協(xié)議:FDMAFDMA:頻分多路訪問

信道頻譜劃分為頻帶每個(gè)站點(diǎn)分配固定的頻帶頻帶中未使用的傳輸時(shí)間空閑例子：6個(gè)站點(diǎn)的LAN,頻帶1、3、4有分組,頻帶2、5、6空閑(浪費(fèi))83第83頁，共165頁，2023年，2月20日，星期二FDM和TDM特點(diǎn)消除了碰撞且公平結(jié)點(diǎn)在每個(gè)幀時(shí)間內(nèi)得到了專用的傳輸速率R/Nbps若系統(tǒng)僅有少數(shù)幾個(gè)有大量分組要發(fā)送的結(jié)點(diǎn)分配的頻率或時(shí)隙被浪費(fèi)適合場合所有結(jié)點(diǎn)都持續(xù)有大量數(shù)據(jù)發(fā)送CDMA是另一種信道劃分協(xié)議2.3.2節(jié)84第84頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議信道劃分協(xié)議輪流協(xié)議隨機(jī)接入?yún)f(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)85第85頁，共165頁，2023年，2月20日，星期二兩種輪流協(xié)議輪詢(有中心):

主結(jié)點(diǎn)“邀請”從結(jié)點(diǎn)依次傳輸關(guān)注問題:輪詢開銷時(shí)延單點(diǎn)故障(主結(jié)點(diǎn))令牌傳遞(無中心):控制令牌從一個(gè)結(jié)點(diǎn)順序地傳遞到下一個(gè)令牌報(bào)文關(guān)注問題:令牌開銷時(shí)延單點(diǎn)故障(令牌消失)適用于希望共享信道但卻無法預(yù)測訪問結(jié)點(diǎn)的數(shù)量的場景86第86頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議信道劃分協(xié)議輪流協(xié)議隨機(jī)接入?yún)f(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)87第87頁，共165頁，2023年，2月20日，星期二隨機(jī)訪問協(xié)議大量結(jié)點(diǎn)以小概率發(fā)送分組以信道全部速率R傳輸結(jié)點(diǎn)間無優(yōu)先權(quán)協(xié)調(diào)兩個(gè)或更多傳輸結(jié)點(diǎn)發(fā)送?

“碰撞”(小概率)隨機(jī)訪問協(xié)議定義了:如何檢測碰撞如何從碰撞中恢復(fù)(例如，經(jīng)延遲后重新傳輸)隨機(jī)訪問協(xié)議的實(shí)例:ALOHA時(shí)隙ALOHACSMA,CSMA/CD,CSMA/CA88第88頁，共165頁，2023年，2月20日，星期二ALOHA協(xié)議

一種用于解決在分組無線通信系統(tǒng)中分配廣播信道的分布式方法假定所有幀有相同長度結(jié)點(diǎn)隨時(shí)傳輸幀結(jié)點(diǎn)是異步的如果2+結(jié)點(diǎn)同時(shí)傳輸，所有結(jié)點(diǎn)檢測碰撞操作當(dāng)結(jié)點(diǎn)獲得新幀，將隨時(shí)傳輸無碰撞，結(jié)點(diǎn)能夠繼續(xù)發(fā)送新幀如果碰撞，結(jié)點(diǎn)能夠檢測到，以概率P重傳幀89第89頁，共165頁，2023年，2月20日，星期二時(shí)隙ALOHA特點(diǎn)單個(gè)活躍結(jié)點(diǎn)能夠連續(xù)地以信道的全速傳輸結(jié)點(diǎn)中的時(shí)隙需要同步簡單碰撞，浪費(fèi)時(shí)隙空閑時(shí)隙結(jié)點(diǎn)能以小于傳輸分組的時(shí)間檢測到碰撞節(jié)點(diǎn)時(shí)鐘同步困難90第90頁，共165頁，2023年，2月20日，星期二在時(shí)隙ALOHA協(xié)議和純ALOHA協(xié)議中,一個(gè)結(jié)點(diǎn)的成功傳輸取決于連接在這個(gè)廣播信道上的其他結(jié)點(diǎn)的活動。由于無線信道的特點(diǎn)，傳輸結(jié)點(diǎn)有時(shí)無法得知其他結(jié)點(diǎn)的活動情況。有線局域網(wǎng)中就不一樣了。91第91頁，共165頁，2023年，2月20日，星期二CSMA(載波偵聽多路訪問)CSMA:

工作原理：發(fā)送前監(jiān)聽。每個(gè)站點(diǎn)在發(fā)送數(shù)據(jù)之前要監(jiān)聽信道上是否有數(shù)據(jù)在傳送。若有，則此站不能發(fā)送，以免發(fā)生碰撞，需等待一段時(shí)間后重試。人類類比：

不要打斷他人說話!避免兩人同時(shí)講話!CSMA用于有線，ALOHA用于無線92第92頁，共165頁，2023年，2月20日，星期二CSMA：載波監(jiān)聽多點(diǎn)訪問載波監(jiān)聽策略：非堅(jiān)持CSMA：一旦監(jiān)聽到信道忙，就不再監(jiān)聽；延遲一個(gè)隨機(jī)時(shí)間后再次監(jiān)聽。堅(jiān)持CSMA：監(jiān)聽到信道忙時(shí)，仍繼續(xù)監(jiān)聽，直到信道空閑。

1-堅(jiān)持CSMA：一聽到信道空閑就立即發(fā)送數(shù)據(jù)

p-堅(jiān)持CSMA：聽到信道空閑時(shí)，以概率p發(fā)送數(shù)據(jù)（以概率1-p延遲一段時(shí)間后再發(fā)送）93第93頁，共165頁，2023年，2月20日，星期二CSMA：載波監(jiān)聽多點(diǎn)訪問CSMA技術(shù)能解決發(fā)送時(shí)出現(xiàn)的沖突現(xiàn)象幀在發(fā)送過程中有可能出現(xiàn)“碰撞”CSMA技術(shù)不能解決發(fā)送中出現(xiàn)的沖突現(xiàn)象

94第94頁，共165頁，2023年，2月20日，星期二問題：

既然發(fā)送前已經(jīng)監(jiān)聽到信道空閑，為什么發(fā)送時(shí)還要繼續(xù)監(jiān)聽信道？95第95頁，共165頁，2023年，2月20日，星期二電磁波在總線上的有限傳播速率的影響

當(dāng)某個(gè)站監(jiān)聽到總線是空閑時(shí)，也可能總線并非真正是空閑的。A向B發(fā)出的信息，要經(jīng)過一定的時(shí)間后才能傳送到B。B若在A發(fā)送的信息到達(dá)B之前發(fā)送自己的幀(因?yàn)檫@時(shí)B的載波監(jiān)聽檢測不到A所發(fā)送的信息)，則必然要在某個(gè)時(shí)間和A發(fā)送的幀發(fā)生碰撞。碰撞的結(jié)果是兩個(gè)幀都變得無用。

96第96頁，共165頁，2023年，2月20日，星期二CSMA碰撞碰撞:整個(gè)分組傳輸時(shí)間被浪費(fèi)產(chǎn)生碰撞的分組變得無用注意:距離與傳播時(shí)延在決定碰撞概率中的作用97第97頁，共165頁，2023年，2月20日，星期二CSMA/CD(碰撞檢測)CSMA/CD:

傳送過程中也進(jìn)行載波偵聽在短時(shí)間內(nèi)檢測到碰撞碰撞的傳輸盡快結(jié)束，以減少信道浪費(fèi)碰撞檢測:

在有線的LAN中容易:測量信號強(qiáng)度，比較傳輸?shù)暮徒邮盏男盘栐跓o線LAN中困難：碰撞可能聽不到人類類比:禮貌的交談?wù)邌栴}：能否進(jìn)一步提高CSMA效率？98第98頁，共165頁，2023年，2月20日，星期二CSMA/CD的基本工作原理工作原理：每個(gè)站發(fā)送數(shù)據(jù)前先監(jiān)聽信道是否空閑，若空閑則立即發(fā)送數(shù)據(jù)。在發(fā)送時(shí)，邊發(fā)送邊檢測。若檢測到?jīng)_突，則立即停止發(fā)送。等待一段隨機(jī)時(shí)間（稱為退避）以后，再重新嘗試。CSMA/CD可歸結(jié)為四句話：

發(fā)前先監(jiān)聽空閑即發(fā)送邊發(fā)邊檢測沖突時(shí)退避99第99頁，共165頁，2023年，2月20日，星期二1kmABt碰撞t=2

A檢測到發(fā)生碰撞t=

B發(fā)送數(shù)據(jù)B檢測到發(fā)生碰撞t=t=0單程端到端傳播時(shí)延記為

100第100頁，共165頁，2023年，2月20日，星期二1kmABt碰撞t=

B檢測到信道空閑發(fā)送數(shù)據(jù)t=

/2發(fā)生碰撞t=2

A檢測到發(fā)生碰撞t=

B發(fā)送數(shù)據(jù)B檢測到發(fā)生碰撞t=ABABABt=0A檢測到信道空閑發(fā)送數(shù)據(jù)ABt=0t=B檢測到發(fā)生碰撞停止發(fā)送STOPt=2

A檢測到發(fā)生碰撞STOPAB單程端到端傳播時(shí)延記為

101第101頁，共165頁，2023年，2月20日，星期二強(qiáng)化碰撞

當(dāng)發(fā)送數(shù)據(jù)的站一旦發(fā)現(xiàn)發(fā)生了碰撞時(shí)，除了立即停止發(fā)送數(shù)據(jù)外，還要再繼續(xù)發(fā)送若干比特的阻塞信號(jammingsignal)，以便讓所有用戶都知道現(xiàn)在已經(jīng)發(fā)生了碰撞。

102第102頁，共165頁，2023年，2月20日，星期二數(shù)據(jù)幀干擾信號TJ阻塞信號

ABTBtB發(fā)送數(shù)據(jù)A檢測到?jīng)_突開始沖突信道占用時(shí)間A發(fā)送數(shù)據(jù)B也能夠檢測到?jīng)_突，并立即停止發(fā)送數(shù)據(jù)幀，接著就發(fā)送干擾信號。這里為了簡單起見，只畫出A發(fā)送干擾信號的情況。103第103頁，共165頁，2023年，2月20日，星期二多路訪問協(xié)議比較信道劃分協(xié)議在高負(fù)載時(shí)高效、公平地共享信道低負(fù)載時(shí)低效：信道訪問中延時(shí)，當(dāng)1個(gè)活躍結(jié)點(diǎn)時(shí)，甚至僅有分配了1/N帶寬!隨機(jī)訪問協(xié)議低負(fù)載是有效：單個(gè)結(jié)點(diǎn)能夠全面利用信道高負(fù)載：碰撞開銷大輪流協(xié)議兼有兩方面的優(yōu)點(diǎn)!104第104頁，共165頁，2023年，2月20日，星期二多路訪問協(xié)議小結(jié)問題：對共享媒體你需要做些什么?信道劃分,通過時(shí)間、頻率或編碼時(shí)分,頻分輪流從中心站點(diǎn)輪詢，令牌傳遞隨機(jī)劃分(動態(tài)的),ALOHA,S-ALOHA,CSMA,CSMA/CD載波偵聽:在某些技術(shù)(有線)中容易，在另一些(無線)中困難CSMA/CD用在以太網(wǎng)中CSMA/CA用在802.11中105第105頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)MAC地址CSMA/CD以太網(wǎng)技術(shù)標(biāo)準(zhǔn)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)106第106頁，共165頁，2023年，2月20日，星期二以太網(wǎng)(Ethernet)以太網(wǎng)——占統(tǒng)治地位的有線LAN技術(shù)來自20世紀(jì)70年代在20世紀(jì)80年代和90年代早期，流行的局域網(wǎng)技術(shù)主要有兩類：一類以太網(wǎng)局域網(wǎng)，它基于隨機(jī)接入?yún)f(xié)議；另一類令牌傳遞技術(shù)局域網(wǎng)，它基于令牌傳遞協(xié)議。107第107頁，共165頁，2023年，2月20日，星期二以太網(wǎng)(Ethernet)占統(tǒng)治地位的有線LAN技術(shù)（簡單者生存）：

率先廣泛使用的LAN技術(shù)100Mbs網(wǎng)卡低于$10!比令牌LAN和ATM等更簡單、便宜在速率競賽中取勝:10Mbps~10GbpsMetcalfe的以太網(wǎng)草圖108第108頁，共165頁，2023年，2月20日，星期二從總線拓?fù)涞叫切屯負(fù)涞?0世紀(jì)90年代，總線拓?fù)淞餍惺褂每偩€拓?fù)涞囊蕴W(wǎng)是一種廣播局域網(wǎng)總線：同軸電纜109第109頁，共165頁，2023年，2月20日，星期二從總線拓?fù)涞叫切屯負(fù)涞?0世紀(jì)90年代后期，集線器出現(xiàn)使以太網(wǎng)在物理上呈星型拓?fù)浣Y(jié)構(gòu)，而邏輯上讓保持為總線結(jié)構(gòu)，提高了以太網(wǎng)的可靠性集線器是一種物理層設(shè)備，它作用于各個(gè)比特而不是作用于幀如果集線器同時(shí)從兩個(gè)不同的接口接收到比特，將出現(xiàn)一次碰撞，必須重新傳輸它們。110第110頁，共165頁，2023年，2月20日，星期二從總線拓?fù)涞叫切屯負(fù)浣粨Q機(jī)的出現(xiàn)使以太網(wǎng)升級為交換以太網(wǎng)交換以太網(wǎng)不僅是無碰撞的，還是存儲轉(zhuǎn)發(fā)的中心為交換機(jī)（二層設(shè)備）交換機(jī)星形111第111頁，共165頁，2023年，2月20日，星期二MAC地址點(diǎn)對點(diǎn)鏈路：廣播鏈路：多個(gè)結(jié)點(diǎn)之間為了進(jìn)行通信，每個(gè)結(jié)點(diǎn)都必須具有唯一的標(biāo)識。即鏈路層地址。112第112頁，共165頁，2023年，2月20日，星期二MAC地址以太網(wǎng)工作在數(shù)據(jù)鏈路層，以太網(wǎng)適配器具有唯一的鏈路層地址。LAN地址=物理地址=MAC地址，通常用6字節(jié)16進(jìn)制表示如1a-03-65-3F-2e-46共有248個(gè)LAN地址IEEE地址分配方式：固定前24bit，公司生成后24bit，每個(gè)適配器具有唯一MAC地址適配器的MAC地址具有扁平(沒有層次)結(jié)構(gòu)，且保持不變113第113頁，共165頁，2023年，2月20日，星期二MAC地址與MAC地址形成對照的是，IP地址（網(wǎng)絡(luò)層地址）是有層次結(jié)構(gòu)的，且當(dāng)主機(jī)移動時(shí)，IP地址通常需要改變MAC地址<——>身份證號IP地址<——>郵政地址就像郵政地址和身份證號都有特定用途一樣，一個(gè)結(jié)點(diǎn)必須同時(shí)具有MAC地址和IP地址114第114頁，共165頁，2023年，2月20日，星期二網(wǎng)卡檢查MAC地址

網(wǎng)卡從網(wǎng)絡(luò)上每收到一個(gè)數(shù)據(jù)幀就首先用硬件檢查該數(shù)據(jù)幀中的MAC地址。如果是發(fā)往本站的幀則收下，然后再進(jìn)行其他的處理。否則就將此幀丟棄，不再進(jìn)行其他的處理?！鞍l(fā)往本站的幀”包括以下三種幀：

單播(unicast)幀（一對一）廣播(broadcast)幀（一對全體）多播(multicast)幀（一對多）115第115頁，共165頁，2023年，2月20日，星期二以太網(wǎng)幀結(jié)構(gòu)發(fā)送端適配器在以太網(wǎng)幀中封裝上層數(shù)據(jù)如：IP數(shù)據(jù)報(bào)。116第116頁，共165頁，2023年，2月20日，星期二以太網(wǎng)幀結(jié)構(gòu)MAC幀物理層MAC層IP層以太網(wǎng)V2MAC幀目的地址源地址類型數(shù)據(jù)FCS6624字節(jié)46~1500IP數(shù)據(jù)報(bào)1010101010101010101010101010101011前同步碼幀開始定界符7字節(jié)1字節(jié)…8字節(jié)插入前導(dǎo)碼:為了達(dá)到比特同步，需增加8個(gè)字節(jié)，其中，第一個(gè)字段共7個(gè)字節(jié)，是前同步碼，用來迅速實(shí)現(xiàn)MAC幀的比特同步。第二個(gè)字段是幀開始定界符，表示后面的信息就是MAC幀。117第117頁，共165頁，2023年，2月20日，星期二以太網(wǎng)幀結(jié)構(gòu)MAC幀物理層MAC層IP層以太網(wǎng)V2MAC幀目的地址源地址類型數(shù)據(jù)FCS6624字節(jié)46~1500IP數(shù)據(jù)報(bào)目的地址字段6字節(jié)源地址字段6字節(jié)118第118頁，共165頁，2023年，2月20日，星期二以太網(wǎng)幀結(jié)構(gòu)MAC幀物理層MAC層IP層以太網(wǎng)V2MAC幀目的地址源地址類型數(shù)據(jù)FCS6624字節(jié)46~1500IP數(shù)據(jù)報(bào)類型字段2字節(jié)

類型字段用來標(biāo)志上一層使用的是什么協(xié)議，以便把收到的MAC幀的數(shù)據(jù)上交給上一層的這個(gè)協(xié)議。119第119頁，共165頁，2023年，2月20日，星期二以太網(wǎng)幀結(jié)構(gòu)MAC幀物理層MAC層IP層以太網(wǎng)V2MAC幀目的地址源地址類型數(shù)據(jù)FCS6624字節(jié)46~1500IP數(shù)據(jù)報(bào)

數(shù)據(jù)字段的最小長度=最小長度64字節(jié)

18字節(jié)的首部和尾部。當(dāng)數(shù)據(jù)字段的長度小于46字節(jié)時(shí)，應(yīng)在數(shù)據(jù)字段的后面加入整數(shù)字節(jié)的填充字段，以保證以太網(wǎng)的MAC幀長不小于64字節(jié)。數(shù)據(jù)字段46~1500

字節(jié)FCS字段4

字節(jié)120第120頁，共165頁，2023年，2月20日，星期二幀的長度不是整數(shù)個(gè)字節(jié)；用收到的幀檢驗(yàn)序列

FCS查出有差錯(cuò)；數(shù)據(jù)字段的長度不在46~1500字節(jié)之間。注意：對于檢查出的無效MAC幀就簡單地丟棄。以太網(wǎng)不負(fù)責(zé)重傳丟棄的幀。

無效的MAC幀

121第121頁，共165頁，2023年，2月20日，星期二為了通信的簡便

以太網(wǎng)采取了不可靠、無連接服務(wù)無連接:

在發(fā)送和接收適配器之間不必先建立連接就可以直接發(fā)送數(shù)據(jù)。不可靠:

接收適配器不向發(fā)送適配器發(fā)送應(yīng)答或否定應(yīng)答這樣做的理由是局域網(wǎng)信道的質(zhì)量很好，因信道質(zhì)量產(chǎn)生差錯(cuò)的概率是很小的。

以太網(wǎng)提供的服務(wù)是不可靠的交付，即盡最大努力的交付。122第122頁，共165頁，2023年，2月20日，星期二當(dāng)目的站收到有差錯(cuò)的數(shù)據(jù)幀時(shí)就丟棄此幀，其他什么也不做。差錯(cuò)的糾正由高層來決定。如果應(yīng)用程序使用TCP，將能彌補(bǔ)丟包否則，應(yīng)用程序?qū)l(fā)現(xiàn)丟包如果高層發(fā)現(xiàn)丟失了一些數(shù)據(jù)而進(jìn)行重傳，但以太網(wǎng)并不知道這是一個(gè)重傳的幀，而是當(dāng)作一個(gè)新的數(shù)據(jù)幀來發(fā)送。

123第123頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)MAC地址CSMA/CD以太網(wǎng)技術(shù)標(biāo)準(zhǔn)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)124第124頁，共165頁，2023年，2月20日，星期二當(dāng)多個(gè)結(jié)點(diǎn)通過集線器互聯(lián)時(shí)，該以太網(wǎng)形成了一個(gè)總線廣播信道。若某適配器傳輸一幀，局域網(wǎng)上的所有適配器都能收到幀。這時(shí)需要多路訪問協(xié)議來解決幀之間的碰撞。125第125頁，共165頁，2023年，2月20日，星期二以太網(wǎng)協(xié)議(CSMA/CD)1.適配器從網(wǎng)絡(luò)層接收數(shù)據(jù)報(bào)并生成幀2.如果適配器感知信道空閑，它開始傳輸幀；如果它感知信道忙，等待信道空閑再傳輸3.當(dāng)適配器傳輸整個(gè)幀時(shí)，一直檢測另一個(gè)幀的傳輸4.如果適配器傳輸過程中檢測到另一次傳輸,中止并發(fā)送強(qiáng)化沖突信號5.中止后,適配器進(jìn)入指數(shù)回退:在第m次碰撞后,適配器隨機(jī)地從{0,1,2,…,2m-1}選擇一個(gè)K值。適配器等待K*512比特時(shí)間并返回到第2步126第126頁，共165頁，2023年，2月20日，星期二以太網(wǎng)協(xié)議(CSMA/CD)(續(xù))強(qiáng)化沖突信號:

確保所有的其他傳輸方都知道碰撞;48bit長比特時(shí)間:

對10Mbps以太網(wǎng)傳每比特需0.1μs;對K=1023,等待時(shí)間約為50msec

若碰撞次數(shù)達(dá)到16次，則放棄傳輸。指數(shù)回退:

目標(biāo)：估計(jì)當(dāng)前負(fù)載，適應(yīng)重傳嘗試重負(fù)載:隨機(jī)等待時(shí)間更長首次碰撞后:從{0,1}中選擇K；時(shí)延是K*512bit傳輸時(shí)間第二次碰撞后:從{0,1,2,3}選擇K10次碰撞后,從{0,1,2,3,4,…,1023}選擇K127第127頁，共165頁，2023年，2月20日，星期二CSMA/CD效率τ=LAN中的2站點(diǎn)之間的最大傳播時(shí)間T0=傳輸最長幀的時(shí)間隨著τ趨于0,效率趨于1隨著T0趨于無窮大，效率趨于1比ALOHA好得多,簡單且便宜

128第128頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)MAC地址CSMA/CD以太網(wǎng)技術(shù)標(biāo)準(zhǔn)3.7鏈路層交換機(jī)3.8802.11無線局域網(wǎng)3.9小結(jié)129第129頁，共165頁，2023年，2月20日，星期二802.3以太網(wǎng)標(biāo)準(zhǔn):鏈路&物理層許多不同的以太網(wǎng)標(biāo)準(zhǔn)共同的MAC協(xié)議和幀格式不同的速率:2Mbps,10Mbps,100Mbps,1Gbps,10Gbps不同的物理層媒體應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層鏈路層物理層MAC協(xié)議和幀格式100BASE-TX100BASE-T4100BASE-FX100BASE-T2100BASE-SX100BASE-BX光纖物理層銅(雙絞線)物理層130第130頁，共165頁，2023年，2月20日，星期二第3章：內(nèi)容提要3.1鏈路層概述3.2成幀3.3差錯(cuò)檢測和糾正技術(shù)3.4可靠數(shù)據(jù)傳輸原理3.5多路訪問協(xié)議3.6以太網(wǎng)3.7鏈路層交換機(jī)轉(zhuǎn)發(fā)和過濾自學(xué)習(xí)鏈路層交換機(jī)的性質(zhì)3.8802.11無線局域網(wǎng)3.9小結(jié)131第131頁，共165頁，2023年，2月20日，星期二集線器的一些特點(diǎn)

集線器的主要功能是對接收到的信號進(jìn)行再生整形放大，以擴(kuò)大網(wǎng)絡(luò)的傳輸距離，同時(shí)把所有節(jié)點(diǎn)集中在以它為中心的節(jié)點(diǎn)上。

集線器很像一個(gè)多端口的轉(zhuǎn)發(fā)器，工作在物理層。集線器是使用電子器件來模擬實(shí)際電纜線的工作，因此整個(gè)系統(tǒng)仍然像一個(gè)傳統(tǒng)的以太網(wǎng)那樣運(yùn)行。使用集線器的以太網(wǎng)在邏輯上仍是一個(gè)總線網(wǎng)，各端系統(tǒng)使用的還是CSMA/CD

協(xié)議，并共享邏輯上的總線。在同一時(shí)刻至多只允許一個(gè)站發(fā)送數(shù)據(jù)。132第132頁，共165頁，2023年，2月20日，星期二集線器集線器的工作過程：節(jié)點(diǎn)發(fā)信號到線路，集線器接收該信號，因信號在電纜傳輸中有衰減，集線器接收信號后將衰減的信號整形放大，最后集線器將放大的信號廣播轉(zhuǎn)發(fā)給其他所有端口。與集線器連接的所有結(jié)點(diǎn)相互碰撞無幀緩存在小型以太網(wǎng)中并不會造成很大問題，并且可以很好的工作，但是如果網(wǎng)絡(luò)上的通訊量有增加，或者連接的節(jié)點(diǎn)數(shù)目很多的時(shí)候，“沖突”會嚴(yán)重影響網(wǎng)絡(luò)的性能。133第133頁，共165頁，2023年，2月20日，星期二交換機(jī)鏈路層設(shè)備：比集線器智能化存儲并轉(zhuǎn)發(fā)以太網(wǎng)幀當(dāng)幀在網(wǎng)段上轉(zhuǎn)發(fā)時(shí)，檢查幀首部并基于MAC目的地址，選擇性地向一個(gè)或多個(gè)鏈路轉(zhuǎn)發(fā)幀透明性主機(jī)不知道交換機(jī)的存在即插即用,自學(xué)習(xí)交換機(jī)不必配置134第134頁，共165頁，2023年，2月20日，星期二以太網(wǎng)交換機(jī)的每個(gè)端口都直接與主機(jī)或另外一個(gè)集線器相連，并且一般都工作在全雙工方式。交換機(jī)能同時(shí)連通許多對的端口，使每一對相互通信的主機(jī)都能像獨(dú)占通信媒體那樣，進(jìn)行無碰撞地傳輸數(shù)據(jù)。以太網(wǎng)交換機(jī)由于使用了專用的交換結(jié)構(gòu)芯片，其交換速率就較高。以太網(wǎng)交換機(jī)的特點(diǎn)135第135頁，共165頁，2023年，2月20日，星期二對于普通10Mb/s的共享式以太網(wǎng)，若共有N個(gè)用戶，則每個(gè)用戶占有的平均帶寬只有總帶寬(10Mb/s)的N分之一。使用以太網(wǎng)交換機(jī)時(shí)，雖然在每個(gè)端口到主機(jī)的帶寬還是10Mb/s，但由于一個(gè)用戶在通信時(shí)是獨(dú)占而不是和其他網(wǎng)絡(luò)用戶共享傳輸媒體的帶寬，因此對于擁有N對端口的交換機(jī)的總?cè)萘繛镹10Mb/s。這正是交換機(jī)的最大優(yōu)點(diǎn)。以太網(wǎng)交換機(jī)的特點(diǎn)136第136頁，共165頁，2023年，2月20日，星期二用以太網(wǎng)交換機(jī)擴(kuò)展局域網(wǎng)

集線器集線器集線器一系三系二系10BASE-T至因特網(wǎng)100Mb/s100Mb/s100Mb/s萬維網(wǎng)服務(wù)器電子郵件服務(wù)器以太網(wǎng)交換機(jī)路由器137第137頁，共165頁，2023年，2月20日，星期二交換機(jī):并行傳輸擴(kuò)大容量端系統(tǒng)與交換機(jī)有專門的直接連接交換機(jī)緩存分組在鏈路上使用以太網(wǎng)協(xié)議：全雙工，無碰撞交換:

A到A’和B到B’能夠同時(shí)無碰撞地進(jìn)行而集線器無法辦到!AA’BB’CC’具有6個(gè)接口的交換機(jī)(1,2,3,4,5,6)123456138第138頁，共165頁，2023年，2月20日，星期二轉(zhuǎn)發(fā)與過濾過濾：是交換機(jī)決定應(yīng)該將一個(gè)幀轉(zhuǎn)發(fā)到某個(gè)接口還是將其丟棄的功能轉(zhuǎn)發(fā)：是決定應(yīng)該將一個(gè)幀導(dǎo)向哪個(gè)接口并把該幀移動到相應(yīng)接口的交換機(jī)功能。交換機(jī)轉(zhuǎn)發(fā)或過濾分組是基于MAC地址進(jìn)行的139第139頁，共165頁，2023年，2月20日，星期二交換機(jī)表問題:

交換機(jī)如何知道經(jīng)接口4可達(dá)A’,經(jīng)接口5可達(dá)B’?交換機(jī)具有一個(gè)交換表，每表項(xiàng):(MAC地址,到達(dá)接口,到達(dá)時(shí)間)問題:

這些表項(xiàng)是如何創(chuàng)建的，誰維護(hù)交換機(jī)表?AA’BB’CC’123456具有6個(gè)接口的交換機(jī)(1,2,3,4,5,6)140第140頁，共165頁，2023年，2月20日，星期二交換機(jī)開機(jī)初始化時(shí)，MAC地址表是空的，因?yàn)镸AC地址表是存儲在內(nèi)存中的。141第141頁，共165頁，2023年，2月20日，星期二如果計(jì)算機(jī)A發(fā)送數(shù)據(jù)幀到計(jì)算機(jī)C,此時(shí)交換機(jī)的E0口接收該數(shù)據(jù)幀，交換機(jī)記錄下該數(shù)據(jù)幀的源地址A的對應(yīng)關(guān)系及E0口的對應(yīng)關(guān)系。由于交換機(jī)并不知道C的MAC地址，所以將此數(shù)據(jù)幀對除了E0口以外的其他端口進(jìn)行轉(zhuǎn)發(fā)。142第142頁，共165頁，2023年，2月20日，星期二如果是計(jì)算機(jī)D發(fā)送數(shù)據(jù)幀到計(jì)算機(jī)C，此時(shí)交換機(jī)的E3口接收該數(shù)據(jù)幀，交換機(jī)記錄下該數(shù)據(jù)幀的源地址D的地址與端口的對應(yīng)關(guān)系。此時(shí)交換機(jī)仍然不知道C的地址，所以還是要對除了E0口以外的其他端口上進(jìn)行轉(zhuǎn)發(fā)。143第143頁，共165頁，2023年，2月20日，星期二交換機(jī)不斷記錄每個(gè)接口上接收到的數(shù)據(jù)幀的地址，一段時(shí)間以后所有的端口所連接的MAC地址都會記錄到MAC地址表中。此時(shí)計(jì)算機(jī)A再向計(jì)算機(jī)C發(fā)送數(shù)據(jù)時(shí)，就直接查MAC地址表進(jìn)行轉(zhuǎn)發(fā)即可，不會再轉(zhuǎn)發(fā)到其他端口上。144第144頁，共165頁，2023年，2月20日，星期二圖中計(jì)算機(jī)A和計(jì)算機(jī)B通過HUB連接到Switch的E0口上，所以在MAC地址表中記錄兩個(gè)MAC地址對應(yīng)同一個(gè)端口，此時(shí)如果A與B通訊，則交換機(jī)不會轉(zhuǎn)發(fā)該數(shù)據(jù)幀，因?yàn)樵春湍繕?biāo)MAC都在同一個(gè)接口上。145第145頁，共165頁，2023年，2月20日，星期二交換機(jī):自學(xué)習(xí)初始化過程：加電開機(jī)，交換表初始化為空。學(xué)習(xí)過程：P111更新過程（刷新/老化期）AA’BB’CC’123456AA’Source:ADest:A’MAC地址接口時(shí)間交換機(jī)表(初始為空)A18:32146第146頁，共165頁，2023年，2月20日，星期二交換機(jī)：幀過濾/轉(zhuǎn)發(fā)算法當(dāng)交換機(jī)收到幀:1.記錄與發(fā)送主機(jī)關(guān)聯(lián)的鏈路2.使用MAC目的地址索引交換機(jī)表3.if

（找到目的地項(xiàng)）

{

if

（目的地位于幀到達(dá)的段）

{丟棄幀}

else

在指示的接口轉(zhuǎn)發(fā)該幀

}

else

洪泛向所有接口(除了該幀到達(dá)的)轉(zhuǎn)發(fā)該幀147第147頁，共165頁，2023年，2月20日，星期二自學(xué)習(xí)、轉(zhuǎn)發(fā)的例子AA’BB’CC’123456AA’源:A目的地:A’MACaddrinterface時(shí)間A18:32AA’AA’A