5.1數(shù)據(jù)鏈路層服務(wù)

概述

術(shù)語:

v ■主機(jī)和路由器：結(jié)點(diǎn)(nodes)

v ■連接相鄰結(jié)點(diǎn)的通信信道：鏈路(links)（物理之上數(shù)據(jù)鏈路）

§ 有線鏈路(wired links)

§ 無線鏈路(wireless links)

§ 局域網(wǎng)(LANs)

v ■鏈路層(第2層)數(shù)據(jù)分組：幀(frame)亿柑，封裝網(wǎng)絡(luò)層數(shù)據(jù)報

數(shù)據(jù)鏈路層負(fù)責(zé)通過一條鏈路從一個節(jié)點(diǎn)向另一個物理鏈路直接相連的相鄰結(jié)點(diǎn)傳送數(shù)據(jù)報朝聋。

鏈路層服務(wù)

?

v■組幀(framing)

§ 封裝數(shù)據(jù)報構(gòu)成數(shù)據(jù)幀，加首部和尾部

§ 幀同步

v■鏈路接入(link access)

§ 如果是共享介質(zhì)，需要解決信道接入(channel access)

§ 幀首部中的“ MAC” 地址另绩，用于標(biāo)識幀的源和目的

? 不同于IP地址锥余！

v■相鄰結(jié)點(diǎn)間可靠交付

§ 在低誤碼率的有線鏈路上很少采用 (如光纖宴倍，某些雙絞線等)

§ 無線鏈路：誤碼率高直奋，需要可靠交付

v■流量控制(flow control)

§ 協(xié)調(diào)(pacing)相鄰的發(fā)送結(jié)點(diǎn)和接收

v■差錯檢測(error detection)

§ 信號衰減和噪聲會引起差錯.

§ 接收端檢測到差錯:

? 通知發(fā)送端重傳或者直接丟棄幀

v■差錯糾正(error correction)

§ 接收端直接糾正比特差錯

v■全雙工和半雙工通信控制

§ 全雙工：鏈路兩端結(jié)點(diǎn)同時雙向傳輸

§ 半雙工：鏈路兩端結(jié)點(diǎn)交替雙向傳輸

鏈路層的具體實(shí)現(xiàn)？

v■每個主機(jī)或路由器接口

v鏈路層在“適配器”

(即網(wǎng)絡(luò)接口卡-NIC)中實(shí)現(xiàn) 或者在一個芯片上實(shí)現(xiàn) §

以太網(wǎng)網(wǎng)卡九杂， 802.11網(wǎng)卡颁湖；以太網(wǎng)芯片組

§ 實(shí)現(xiàn)鏈路層和物理層

v■鏈接主機(jī)的系統(tǒng)總線

v■由硬件、軟件與固件組成

網(wǎng)卡間通信

v ■發(fā)送端：

§ 將數(shù)據(jù)報封裝成幀

§ 增加差錯檢測比特尼酿，實(shí)現(xiàn)可靠數(shù)據(jù)傳輸和流量控制等.

v ■接收端：

§ 檢測差錯爷狈，實(shí)現(xiàn)可靠數(shù)據(jù)傳輸和流量控制等

§ 提取數(shù)據(jù)報，交付上層協(xié)議實(shí)體

5.2差錯編碼

差錯編碼基本原理：

D→DR裳擎，其中R為差錯檢測與糾正比特（冗余比特）（監(jiān)督位）

差錯編碼的檢錯能力

v ■差錯編碼可分為檢錯碼與糾錯碼

v ■對于檢錯碼涎永，如果編碼集的漢明距離ds=r+1（兩段碼不同比特的數(shù)量就是漢明距離，則該差錯編碼可以檢測r位的差錯

對于糾錯碼鹿响，如果編碼集的漢明距離ds=2r+1拜英，則該差錯編碼可以糾正r位的差錯（基于概率最大化糾錯

奇偶校驗(yàn)碼

■1比特校驗(yàn)位:

v 檢測奇數(shù)位差錯

能夠?qū)崿F(xiàn)奇數(shù)個差錯檢驗(yàn)份招，偶數(shù)個檢測不出來荧降，所以檢錯能力是50%冠骄，漏檢率是50%，最大有點(diǎn)編碼簡單

■二維奇偶校驗(yàn):

v檢測奇數(shù)位差錯绸贡、部分偶數(shù)位差錯

v糾正同一行/列的奇數(shù)位錯

Internet校驗(yàn)和(Checksum)

■發(fā)送端:

v 將“數(shù)據(jù)” (校驗(yàn)內(nèi)容)劃分為16位的二進(jìn)制“整數(shù)”序列

v 求和(sum)：補(bǔ)碼求和(最高位進(jìn)位的“ 1”盯蝴，返回最低位繼續(xù)加）

v 校驗(yàn)和(Checksum)：sum的反碼

v 放入分組(UDP、 TCP听怕、 IP)的校驗(yàn)和字段

■接收端:

v 與發(fā)送端相同算法計算

v 計算得到的"checksum"：

§ 為16位全0（或sum為16位全1）：無錯捧挺，否則：有錯

循環(huán)冗余校驗(yàn)碼(CRC)

v ■檢錯能力更強(qiáng)大的差錯編碼

v ■將數(shù)據(jù)比特， D尿瞭，視為一個二進(jìn)制數(shù)

v ■選擇一個r+1位的比特模式 (生成比特模式)闽烙， G

v ■目標(biāo)：選擇r位的CRC比特， R声搁，滿足

§ <D,R>剛好可以被G整除(模2)

§ 接收端檢錯：利用G除<D,R>黑竞，余式全0捕发，無錯；否則很魂，有錯扎酷！

§ 可以檢測所有突發(fā)長度小于r+1位差錯。

v ■廣泛應(yīng)用于實(shí)際網(wǎng)絡(luò) (以太網(wǎng)遏匆， 802.11 WiFi霞玄， ATM)

5.3多路訪問控制(MAC)協(xié)議

兩類“鏈路”：

v ■點(diǎn)對點(diǎn)鏈路

§ 撥號接入的PPP

§ 以太網(wǎng)交換機(jī)與主機(jī)間的點(diǎn)對點(diǎn)鏈路

v■ 廣播鏈路 (共享介質(zhì))

§ 早期的總線以太網(wǎng)

§ HFC的上行鏈路

§ 802.11無線局域網(wǎng)

v ■單一共享廣播信道

v ■兩個或者兩個以上結(jié)點(diǎn)同時傳輸：干擾(interference)

§ 沖突(collision)

? 結(jié)點(diǎn)同時接收到兩個或者多個信號→接收失敗拉岁！

多路訪問控制協(xié)議(multiple access control protocol)

v ■采用分布式算法決定結(jié)點(diǎn)如何共享信道，即決策結(jié)點(diǎn)何時可以傳輸數(shù)據(jù)

v ■必須基于信道本身惰爬，通信信道共享協(xié)調(diào)信息喊暖！

§ 無帶外信道用于協(xié)調(diào)

理想MAC協(xié)議

給定：?速率為R bps的廣播信道

期望：

1. 當(dāng)只有一個結(jié)點(diǎn)希望傳輸數(shù)據(jù)時，它可以以速率 R發(fā)送.

2. 當(dāng)有M個結(jié)點(diǎn)期望發(fā)送數(shù)據(jù)時撕瞧，每個節(jié)點(diǎn)平均發(fā)送數(shù)據(jù)的平均速率是R/M

3. 完全分散控制:

? 無需特定結(jié)點(diǎn)協(xié)調(diào)

? 無需時鐘陵叽、時隙同步

4.?簡單

MAC協(xié)議分類

三大類：

v■信道劃分(channel partitioning)MAC協(xié)議

§ ■多路復(fù)用技術(shù)

§ TDMA、 FDMA丛版、 CDMA巩掺、 WDMA等

v■隨機(jī)訪問(random access)MAC協(xié)議

§ 信道不劃分，允許沖突

§ 采用沖突“恢復(fù)”機(jī)制

v■輪轉(zhuǎn)(“ taking turns” )MAC協(xié)議

§ 結(jié)點(diǎn)輪流使用信道

5.2.1信道劃分MAC協(xié)議

信道劃分MAC協(xié)議： TDMA

TDMA: time division multiple access

v ■“周期性”接入信道

v ■每個站點(diǎn)在每個周期页畦，占用固定長度的時隙(e.g.長度=分組傳輸時間)

v ■未用時隙空閑(idle)

信道劃分MAC協(xié)議： FDMA

FDMA: frequency division multiple access

v ■信道頻譜劃分為若干頻帶(frequency bands)

v ■每個站點(diǎn)分配一個固定的頻帶

v ■無傳輸頻帶空閑

5.2.2隨機(jī)訪問MAC協(xié)議

v■當(dāng)結(jié)點(diǎn)要發(fā)送分組時：

§ 利用信道全部數(shù)據(jù)速率R發(fā)送分組

§ 沒有事先的結(jié)點(diǎn)間協(xié)調(diào)

v■兩個或多個結(jié)點(diǎn)同時傳輸： ? “沖突”

■v隨機(jī)訪問MAC協(xié)議需要定義:

§ 如何檢測沖突

§ 如何從沖突中恢復(fù) (e.g., 通過延遲重傳)

v■典型的隨機(jī)訪問MAC協(xié)議：

§ 時隙(sloted)ALOHA

§ ALOHA

§ CSMA胖替、 CSMA/CD、 CSMA/CA

時隙ALOHA協(xié)議

假定：

v ■所有幀大小相同

v ■時間被劃分為等長的時隙(每個時隙可以傳輸1個幀)

v ■結(jié)點(diǎn)只能在時隙開始時刻發(fā)送幀

v ■結(jié)點(diǎn)間時鐘同步

v ■如果2個或2個以上結(jié)點(diǎn)在同一時隙發(fā)送幀豫缨，結(jié)點(diǎn)即檢測到?jīng)_突

運(yùn)行:

v ■當(dāng)結(jié)點(diǎn)有新的幀時独令，在下一個時隙(slot)發(fā)送

§ 如果無沖突：該結(jié)點(diǎn)可以在下一個時隙繼續(xù)發(fā)送新的幀

§ 如果沖突：該結(jié)點(diǎn)在下一個時隙以概率p重傳該幀，直至成功

優(yōu)點(diǎn):

v 單個結(jié)點(diǎn)活動時好芭，可以連續(xù)以信道全部速率傳輸數(shù)據(jù)

v 高度分散化：只需同步時隙

v 簡單

缺點(diǎn):

v 沖突燃箭，浪費(fèi)時隙

v 空閑時隙

v 結(jié)點(diǎn)也許能以遠(yuǎn)小于分組傳輸時間檢測到?jīng)_突

v 時鐘同步

效率(efficiency): 長期運(yùn)行時，成功發(fā)送幀的時隙所占比例 (很多結(jié)點(diǎn)舍败，有很多幀待發(fā)送)

v ■假設(shè): N個結(jié)點(diǎn)有很多幀待傳輸邻薯，每個結(jié)點(diǎn)在每個時隙均以概率p發(fā)送數(shù)據(jù)

v ■對于給定的一個結(jié)點(diǎn)裙戏，在一個時隙將幀發(fā)送成功的概率= p(1-p)N-1

v ■對于任意結(jié)點(diǎn)成功發(fā)送幀的概率= Np(1-p)N-1

v ■最大效率: 求得使Np(1-p)N-1最大的p*

v ■對于很多結(jié)點(diǎn)，求Np*(1-p*)N-1當(dāng)N趨近無窮時的極限弛说，可得:

最大效率= 1/e = 0.37

最好情況: 信道被成功利用的時間僅占37%挽懦！

ALOHA協(xié)議

v?■非時隙(純)Aloha：更加簡單，無需同步

v ■當(dāng)有新的幀生成時

§ 立即發(fā)送

v ■沖突可能性增大:

§ 在t0時刻發(fā)送幀木人，會與在[t0-1, t0+1]期間其他結(jié)點(diǎn)發(fā)送的幀沖突

CSMA協(xié)議

v ■載波監(jiān)聽多路訪問協(xié)議CSMA (carrier sense multiple access)

v ■發(fā)送幀之前信柿，監(jiān)聽信道(載波)：

§ 信道空閑：發(fā)送完整幀

§ 信道忙：推遲發(fā)送

? 1-堅持CSMA（一直偵聽冀偶，一旦發(fā)現(xiàn)空閑就馬上發(fā)送數(shù)據(jù)

? 非堅持CSMA（隨機(jī)等待一段時間在偵聽信道

? P-堅持CSMA（以概率p堅持偵聽信道，概率1-p隨機(jī)等待時間發(fā)送數(shù)據(jù)

v ■沖突可能仍然發(fā)生：信號傳播延遲（由于鏈路太長渔嚷，可能出現(xiàn)偵聽延遲

■繼續(xù)發(fā)送沖突幀：浪費(fèi)信道資源

CSMA/CD協(xié)議

CSMA/CD: CSMA with Collision Detection（帶有沖突檢測的載波偵聽多路訪問)

§ 短時間內(nèi)可以檢測到?jīng)_突

§ 沖突后傳輸中止进鸠，減少信道浪費(fèi)

v 沖突檢測:

§ 有線局域網(wǎng)易于實(shí)現(xiàn)：測量信號強(qiáng)度，比較發(fā)射信號與接收信號

§ 無線局域網(wǎng)很難實(shí)現(xiàn)：接收信號強(qiáng)度淹沒在本地發(fā)射信號強(qiáng)度下

“邊發(fā)邊聽形病，不發(fā)不聽”(聽是指監(jiān)聽或偵聽

CSMA/CD效率

vTprop = LAN中2個結(jié)點(diǎn)間的最大傳播延遲

vttrans = 最長幀傳輸延遲

vtprop 趨近于0或者ttrans 趨近于∞時客年，效率趨近于1

v遠(yuǎn)優(yōu)于ALOHA，并且簡單漠吻、分散量瓜！

5.3.3輪轉(zhuǎn)訪問MAC協(xié)議

■信道劃分MAC協(xié)議：

§ 網(wǎng)絡(luò)負(fù)載重時，共享信道效率高途乃，且公平

§ 網(wǎng)絡(luò)負(fù)載輕時绍傲，共享信道效率低！

■隨機(jī)訪問MAC協(xié)議：

§ 網(wǎng)絡(luò)負(fù)載輕時耍共，共享信道效率高烫饼，單個結(jié)點(diǎn)可以利用信道的全部帶寬

§ 網(wǎng)絡(luò)負(fù)載重時，產(chǎn)生沖突開銷

■輪轉(zhuǎn)訪問MAC協(xié)議：

綜合兩者的優(yōu)點(diǎn)试读！

輪詢(polling):

v■主結(jié)點(diǎn)輪流“邀請”從屬結(jié)點(diǎn)發(fā)送數(shù)據(jù)

v■典型應(yīng)用：

“ 啞(dumb)” 從屬設(shè)備

v■問題：

§ 輪詢開銷

§ 等待延遲

§ 單點(diǎn)故障（主節(jié)點(diǎn)故障

令牌傳遞(token passing):

v■控制令牌依次從一個結(jié)點(diǎn)傳遞到下一個結(jié)點(diǎn).

v■令牌：特殊幀

v■問題:

§ 令牌開銷

§ 等待延遲

§ 單點(diǎn)故障（令牌節(jié)點(diǎn)故障

MAC協(xié)議總結(jié)

v■信道劃分MAC協(xié)議：時間杠纵、頻帶、碼片劃分

§ TDMA钩骇、 FDMA比藻、 CDMA

v■隨機(jī)訪問MAC協(xié)議：

§ ALOHA, S-ALOHA, CSMA, CSMA/CD

§ CSMA/CD應(yīng)用于以太網(wǎng)

§ CSMA/CA應(yīng)用802.11無線局域網(wǎng)

v■輪轉(zhuǎn)訪問MAC協(xié)議：

§ 主結(jié)點(diǎn)輪詢；令牌傳遞

§ 藍(lán)牙倘屹、 FDDI韩容、令牌環(huán)網(wǎng)

5.4ARP協(xié)議

MAC地址

v■32位IP地址:

§ 接口的網(wǎng)絡(luò)層地址

§ 用于標(biāo)識網(wǎng)絡(luò)層(第3層)分組，支持分組轉(zhuǎn)發(fā)

v■MAC地址(或稱LAN地址,物理地址,以太網(wǎng)地址) :

§ 作用：用于局域網(wǎng)內(nèi)標(biāo)識一個幀從哪個接口發(fā)出唐瀑，到達(dá)哪個物理相連的其他接口

§ 48位MAC地址(用于大部分LANs)群凶，固化在網(wǎng)卡的ROM中，有時也可以軟件設(shè)置

局域網(wǎng)中的每塊網(wǎng)卡都有一個唯一的MAC地址

v■MAC地址由IEEE統(tǒng)一管理與分配

v■網(wǎng)卡生產(chǎn)商購買MAC地址空間(前24比特)

v■類比：

§ MAC地址：身份證號

§ IP地址：郵政地址

v ■MAC地址是“平面”地址： ? 可“攜帶”

§ 可以從一個LAN移到另一個LAN

v■IP地址是層次地址： ? 不可“攜帶”

§ IP地址依賴于結(jié)點(diǎn)連接到哪個子網(wǎng)

ARP: 地址解析協(xié)議

■ARP表: LAN中的每個IP結(jié)點(diǎn)(主機(jī)哄辣、路由器)維護(hù)一個表

§ 存儲某些LAN結(jié)點(diǎn)的IP/MAC地址映射關(guān)系:< IP地址; MAC地址; TTL>

§ TTL (Time To Live)：經(jīng)過這個時間以后該映射關(guān)系會被遺棄(典型值為20min)

ARP協(xié)議: 同一局域網(wǎng)內(nèi)

v ■A想要給同一局域網(wǎng)內(nèi)的B發(fā)送數(shù)據(jù)報(在A的ARP報表檢索B的mac地址)

§ B的MAC地址不在 A的ARP 表中.

v ■A廣播ARP查詢分組请梢，其中包含B的IP地址

§ 目的MAC地址 = FF-FFFF-FF-FF-FF

§ LAN中所有結(jié)點(diǎn)都會接收ARP查詢

v ■B接收ARP查詢分組， IP地址匹配成功力穗，向A應(yīng)答B(yǎng)的MAC 地址

§ 利用單播幀向A發(fā)送應(yīng)答

v ■A在其ARP表中毅弧，緩存B的IP-MAC地址對，直至超時

§ 超時后当窗，再次刷新

v ■ARP是“即插即用”協(xié)議:

§ 結(jié)點(diǎn)自主創(chuàng)建ARP表够坐，無需干預(yù)

尋址: 從一個LAN路由至另一個LAN

■通信過程: A通過路由器R向B發(fā)送數(shù)據(jù)報

§ 關(guān)注尋址： IP地址(數(shù)據(jù)報中)和MAC地址(幀中)

§ 假設(shè)A知道B的IP地址(怎么知道的?)

§ 假設(shè)A知道第一跳路由器R (左)接口IP地址 (怎么知道的?)

§ 假設(shè)A知道第一跳路由器R (左)接口MAC地址 (怎么知道的?)

5.5以太網(wǎng)

“ 統(tǒng)治地位” 的有線LAN技術(shù):

v ■造價低廉(NIC不足￥100.00)

v ■應(yīng)用最廣泛的LAN技術(shù)

v ■比令牌局域網(wǎng)和ATM等，簡單、便宜

v ■滿足網(wǎng)絡(luò)速率需求： 10 Mbps – 10 Gbps

以太網(wǎng)：物理拓?fù)?/b>

v■總線(bus): 上世紀(jì)90年代中期前流行

§ 所有結(jié)點(diǎn)在同一沖突域(collision domain) (可能彼此沖突)

v■星型(star): 目前主流網(wǎng)絡(luò)拓?fù)?/p>

§ 中心交換機(jī)(switch)

§ 每個結(jié)點(diǎn)一個單獨(dú)沖突域(結(jié)點(diǎn)間彼此不沖突)

以太網(wǎng)：不可靠元咙、無連接服務(wù)

v■無連接(connectionless): 發(fā)送幀的網(wǎng)卡與接收幀的網(wǎng)卡間沒有“握手”過程

v■不可靠(unreliable): 接收網(wǎng)卡不向發(fā)送網(wǎng)卡進(jìn)行確認(rèn)

§ 差錯幀直接丟棄梯影，丟棄幀中的數(shù)據(jù)恢復(fù)依靠高層協(xié)議 (e.g., TCP)，否則庶香，發(fā)生數(shù)據(jù)丟失

v■以太網(wǎng)的MAC協(xié)議: 采用二進(jìn)制指數(shù)退避算法的CSMA/CD

以太網(wǎng)CSMA/CD算法

1. NIC從網(wǎng)絡(luò)層接收數(shù)據(jù)報甲棍， 創(chuàng)建數(shù)據(jù)幀。

2. 監(jiān)聽信道：

如果NIC監(jiān)聽到信道空閑赶掖， 則開始發(fā)送幀感猛；

如果NIC監(jiān)聽到信道忙，則一直等待到信道空閑奢赂， 然后發(fā)送幀陪白。

3. NIC發(fā)送完整個幀， 而沒有檢測到其他結(jié)點(diǎn)的數(shù)據(jù)發(fā)送膳灶， 則NIC確認(rèn)幀發(fā)送成功拷泽！

4. 如果NIC檢測到其他結(jié)點(diǎn)傳輸數(shù)據(jù)， 則中止發(fā)送并 發(fā) 送 堵 塞 信 號 (jam signal)

5. 中止發(fā)送后袖瞻， NIC進(jìn)入二進(jìn)制指數(shù)退避：

§ 第m次連續(xù)沖突后：

?取n = Min(m, 10)

?NIC 從{0,1,2, …, 2n-1}中隨機(jī)選擇一個數(shù)K

?NIC等待K?512比特的傳輸

延遲時間， 再返回第2步

§ 連續(xù)沖突次數(shù)越多拆吆， 平均等待時間越長聋迎。

以太網(wǎng)幀結(jié)構(gòu)

發(fā)送端網(wǎng)卡將IP數(shù)據(jù)報(或其他網(wǎng)絡(luò)層協(xié)議分組)封裝到以太網(wǎng)幀中：

■前導(dǎo)碼(Preamble)(8B):

7個字節(jié)的10101010，第8字節(jié)為10101011

用于發(fā)送端與接收端的時鐘同步

v ■目的MAC地址枣耀、 源MAC地址(各6B):

§ 如果網(wǎng)卡的MAC地址與收到的幀的目的MAC地址匹配霉晕， 或者幀的目的MAC地址為廣播地址(FF-FF-FF-FF-FF-FF)， 則網(wǎng)卡接收該幀捞奕， 并將其封裝的網(wǎng)絡(luò)層分組交給相應(yīng)的網(wǎng)絡(luò)層協(xié)議牺堰。

§ 否則， 網(wǎng)卡丟棄(不接收)該幀颅围。

v ■類型(Type)(2B): 指示幀中封裝的是哪種高層協(xié)議的分組(如伟葫， IP數(shù)據(jù)報、 Novell IPX數(shù)據(jù)報院促、 AppleTalk數(shù)據(jù)報等)

v ■數(shù)據(jù)(Data)(46-1500B): 指上層協(xié)議載荷筏养。

v R=10Mbps， RTTmax=512μs常拓， Lmin / R = RTTmax

v Lmin=512bits=64B渐溶， Datamin=Lmin-18=46B

v ■CRC(4B): 循環(huán)冗余校驗(yàn)碼

§ 丟棄差錯幀

802.3以太網(wǎng)標(biāo)準(zhǔn): 鏈路與物理層

v■許多不同的以太網(wǎng)標(biāo)準(zhǔn)

§ 相同的MAC協(xié)議和幀格式

§ 不同速率: 2 Mbps, 10 Mbps, 100 Mbps,1Gbps, 10G bps

§ 不同物理介質(zhì): 光纖, 線纜

5.5.2交換機(jī)

v■鏈路層設(shè)備

§ 存儲-轉(zhuǎn)發(fā)以太網(wǎng)幀

§ 檢驗(yàn)到達(dá)幀的目的MAC地址， 選擇性(selectively) 向一個或多個輸出鏈路轉(zhuǎn)發(fā)幀

§ 利用CSMA/CD訪問鏈路弄抬，發(fā)送幀

v■透明(transparent)

§ 主機(jī)感知不到交換機(jī)的存在

v■即插即用(plug-and-play)

v■自學(xué)習(xí)(self-learning)

§ 交換機(jī)無需配置

交換機(jī): 多端口間同時傳輸

v■主機(jī)利用獨(dú)享(dedicated)鏈路直接連接交換機(jī)

v■交換機(jī)緩存幀

v■交換機(jī)在每段鏈路上利用CSMA/CD收發(fā)幀茎辐，但無沖突，且可以全雙工

§ 每段鏈路一個獨(dú)立的沖突域

v■交換(switching): A-A’ 與B-B’ 的傳輸可以同時進(jìn)行，沒有沖突

交換機(jī)轉(zhuǎn)發(fā)表：交換表

Q: 交換機(jī)怎么知道A’ 可以通過接口4到達(dá)拖陆，而B’ 可以通過接口5到達(dá)?

v A: 每個交換機(jī)有一個交換表(switch table), 每個入口(entry):

§ (主機(jī)的MAC地址, 到達(dá)主機(jī)的接口, 時間戳)

§ 看起來很像路由表弛槐！

v Q: 交換表入口信息如何創(chuàng)建和維護(hù)的那？

§ 類似于路由協(xié)議慕蔚？

交換機(jī): 自學(xué)習(xí)

v ■交換機(jī)通過自學(xué)習(xí)丐黄，獲知到達(dá)主機(jī)的接口信息

§ 當(dāng)收到幀時，交換機(jī)“學(xué)習(xí)”到發(fā)送幀的主機(jī)（通過幀的源MAC地址）孔飒，位于收到該幀的接口所連接的LAN網(wǎng)段

§ 將發(fā)送主機(jī)MAC地址/接口信息記錄到交換表中

交換機(jī): 幀過濾/轉(zhuǎn)發(fā)

當(dāng)交換機(jī)收到幀:

1. 記錄幀的源MAC地址與輸入鏈路接口

2. 利用目的MAC地址檢索交換表

3. if 在交換表中檢索到與目的MAC地址匹配的入口(entry)

then {

if 目的主機(jī)位于收到幀的網(wǎng)段

then 丟棄幀

else 將幀轉(zhuǎn)發(fā)到該入口指向的接口

}

else 泛洪(flood) /* 向除收到該幀的接口之外的所有接口轉(zhuǎn)發(fā) */（當(dāng)交換機(jī)不清楚發(fā)送到哪個接口是時灌闺，就向每個接口（除本身外）都發(fā)送一份數(shù)據(jù)報

自學(xué)習(xí)與轉(zhuǎn)發(fā)過程舉例

交換機(jī)互聯(lián)

組織機(jī)構(gòu)(Institutional)網(wǎng)絡(luò)

交換機(jī) vs. 路由器

■兩者均為存儲-轉(zhuǎn)發(fā)設(shè)備:

§路由器: 網(wǎng)絡(luò)層設(shè)備 (檢測網(wǎng)絡(luò)層分組首部)

§交換機(jī): 鏈路層設(shè)備 (檢測鏈路層幀的首部)

■二者均使用轉(zhuǎn)發(fā)表:

§路由器: 利用路由算法(路由協(xié)議)計算(設(shè)置), 依據(jù)IP地址

§交換機(jī): 利用自學(xué)習(xí)、泛洪構(gòu)建轉(zhuǎn)發(fā)表, 依據(jù)MAC地址

網(wǎng)絡(luò)設(shè)備對比

5.5.3虛擬局域網(wǎng)(VLAN)

VLANs: 動機(jī)

在同一個路由上有不同的組織坏瞄，出于隱私和效率的考慮桂对，希望廣播只在特定的組織內(nèi)

基于端口的VLAN

v ■流量隔離(traffic isolation):去往/來自端口1-8的幀只到達(dá)端口1-8

§ 也可以基于MAC地址定義VLAN, 而不是交換端口

v ■動態(tài)成員: 端口可以動態(tài)分配給不同VLAN

v ■在VLAN間轉(zhuǎn)發(fā): 通過路由(就像在獨(dú)立的交換機(jī)之間)

實(shí)踐中，廠家會將交換機(jī)與路由器集成在一起

跨越多交換機(jī)的VLAN

v ■多線纜連接

§ 每個線纜連接一個VLAN

v ■中繼端口(trunk port): 在跨越多個物理交換機(jī)定義的VLAN承載幀

§ 為多VLAN轉(zhuǎn)發(fā)802.1幀容易產(chǎn)生歧義 (必須攜帶VLAN ID信息)

§ 802.1q協(xié)議為經(jīng)過中繼端口轉(zhuǎn)發(fā)的幀增加/去除額外的首部域

5.6ppp協(xié)議

點(diǎn)對點(diǎn)數(shù)據(jù)鏈路控制

v■一個發(fā)送端鸠匀，一個接收端蕉斜，一條鏈路：比廣播鏈路容易

§ 無需介質(zhì)訪問控制(Media Access Control)

§ 無需明確的MAC尋址

§ e.g., 撥號鏈路, ISDN鏈路

v■常見的點(diǎn)對點(diǎn)數(shù)據(jù)鏈路控制協(xié)議：

§ HDLC: High Level Data Link Control（高級鏈路控制協(xié)議，很多通信以此為基礎(chǔ)）

§ PPP (Point-to-Point Protocol)

PPP設(shè)計需求[RFC 1557]

v■組幀： 將網(wǎng)絡(luò)層數(shù)據(jù)報封裝到數(shù)據(jù)鏈路層幀中

§ 可以同時承載任何網(wǎng)絡(luò)層協(xié)議分組(不僅IP數(shù)據(jù)報)

§ 可以向上層實(shí)現(xiàn)分用（多路分解）

v■比特透明傳輸： 數(shù)據(jù)域必須支持承載任何比特模式

v■差錯檢測： (無糾正)

v■連接活性(connection liveness)檢測： 檢測缀棍、并向網(wǎng)絡(luò)層通知鏈路失效

v■網(wǎng)絡(luò)層地址協(xié)商： 端結(jié)點(diǎn)可以學(xué)習(xí)/配置彼此網(wǎng)絡(luò)地址

PPP無需支持的功能

v■無需差錯糾正/恢復(fù)

v■無需流量控制

v■不存在亂序交付

v■無需支持多點(diǎn)鏈路

差錯恢復(fù)宅此、流量控制等由高層協(xié)議處理！

PPP數(shù)據(jù)幀

v 標(biāo)志(Flag): 定界符(delimiter)

v 地址(Address): 無效(僅僅是一個選項)

v 控制(Control): 無效爬范；未來可能的多種控制域

v 協(xié)議(Protocol): 上層協(xié)議 (eg, PPP-LCP, IP, IPCP, etc)

v 信息(info): 上層協(xié)議分組數(shù)據(jù)

v 校驗(yàn)(check): CRC校驗(yàn)父腕，用于差錯檢測

字節(jié)填充(Byte Stuffing)(由于地址和控制無效，所以用一個填充字節(jié)來填充）

v ■“數(shù)據(jù)透明傳輸”需求: 數(shù)據(jù)域必須允許包含標(biāo)志模式<01111110>

§ Q: 如何判斷該作為數(shù)據(jù)接收青瀑，還是作為標(biāo)志處理璧亮？

v■發(fā)送端: 在數(shù)據(jù)中的<01111110>和<01111101>字節(jié)前添加額外的字節(jié)<01111101> (“填充(stuffs)”)

v■接收端:

§ 單個字節(jié)<01111101>表示一個填充字節(jié)；

§ 連續(xù)兩個字節(jié)<01111101>：丟棄第1個斥难，第2個作為數(shù)據(jù)接收

§ 單個字節(jié)<01111110>: 標(biāo)志字節(jié)

PPP數(shù)據(jù)控制協(xié)議

在交換網(wǎng)絡(luò)層數(shù)據(jù)之前枝嘶， PPP數(shù)據(jù)鏈路兩端必須：

v ■配置PPP鏈路

§ 最大幀長

§ 身份認(rèn)證(authentication)

§ etc.

v ■學(xué)習(xí)/配置網(wǎng)絡(luò)層信息

§ 對于IP協(xié)議: 通過交換IPCP協(xié)議 (IP Control Protocol )報文 (IP分組首部的“上層

協(xié)議”字段取值: 8021)，完成IP地址等相關(guān)信息配置

5.7 802.11無線局域網(wǎng)簡介

IEEE 802.11無線局域網(wǎng)

802.11b

v 2.4-2.5GHz免費(fèi)頻段(unlicensed spectrum)

v 最高速率： 11 Mbps

v 物理層采用直接序列擴(kuò)頻(DSSS)技術(shù)

§ 所有主機(jī)使用相同的碼片序列

802.11a

§ 5-6 GHz頻段

§ 最高速率： 54 Mbps

802.11g

§ 2.4-2.5 GHz頻段

§ 最高速率： 54 Mbps

802.11n: 多天線(MIMO)

§ 2.4-2.5 GHz頻段

§ 最高速率： 600 Mbps

v ■均使用CSMA/CA多路訪問控制協(xié)議

v■ 均有基礎(chǔ)設(shè)施(基站)網(wǎng)絡(luò)模式和特定網(wǎng)(自組網(wǎng))網(wǎng)絡(luò)模式

IEEE 802.11無線局域網(wǎng)

IEEE 802.11體系結(jié)構(gòu)

v ■無線主機(jī)與基站通信

§ 基站(base station) = 訪問點(diǎn)(access point-AP)

v ■基本服務(wù)集BSS(Basic Service Set) 哑诊，也稱為單元(cell)

§ 基礎(chǔ)設(shè)施網(wǎng)絡(luò)模式:

? 無線主機(jī)

? AP: 基站

§ 自組網(wǎng)(ad hoc)模式:

§ 只有主機(jī)

802.11：信道與AP關(guān)聯(lián)

■802.11b: 2.4GHz-2.485GHz頻譜劃分為11個不同頻率的信道

§ 每個AP選擇一個頻率(信道)

§ 存在干擾可能: 相鄰的AP可能選擇相同的信道群扶！

v■主機(jī): 必須與某個AP關(guān)聯(lián)(associate)

§ 掃描信道，監(jiān)聽包含AP名稱(服務(wù)集標(biāo)識符-SSID )和MAC地址的信標(biāo)(beacon)幀

§ 選擇一個AP進(jìn)行關(guān)聯(lián)

§ 可能需要進(jìn)行身份認(rèn)證

§ 典型情形：運(yùn)行DHCP獲取IP地址等信息

802.11AP關(guān)聯(lián)：被動掃描與主動掃描

被動掃描(scanning):

v 各AP發(fā)送信標(biāo)幀

v 主機(jī)(H1)向選擇的AP發(fā)送關(guān)聯(lián)請求幀

v AP向主機(jī)(H1)發(fā)送關(guān)聯(lián)響應(yīng)幀

主動掃描:

v 主機(jī)(H1)主動廣播探測請求幀(Probe Request Frame)

v AP發(fā)送探測響應(yīng)幀(Probe Response Frame)

v 主機(jī)(H1)向選擇的AP發(fā)送關(guān)聯(lián)請求幀

v AP向主機(jī)(H1)發(fā)送關(guān)聯(lián)響應(yīng)幀

802.11：多路訪問控制

v ■避免沖突: 2+結(jié)點(diǎn)同時傳輸

v ■802.11: CSMA – 發(fā)送數(shù)據(jù)前監(jiān)聽信道

§ 避免與正在進(jìn)行傳輸?shù)钠渌Y(jié)點(diǎn)沖突

v ■802.11: 不能像CSMA/CD那樣镀裤，邊發(fā)送穷当、邊檢測沖突！

§ 無線信道很難實(shí)現(xiàn)（信號急劇衰減）

§ 無法偵聽到所有可能的沖突：隱藏站淹禾、信號衰落

§ 目標(biāo): 避免沖突(avoid collisions)-CSMA/C(ollision)A(voidance)

IEEE 802.11 MAC協(xié)議: CSMA/CA

802.11 sender

1 if 監(jiān)聽到信道空閑了DIFS時間（分布式幀間間隔時間） then

發(fā)送整個幀(無同時檢測沖突馁菜，即CD)

2 if 監(jiān)聽到信道忙 then

開始隨機(jī)退避計時

當(dāng)信道空閑時，計時器倒計時

當(dāng)計時器超時時铃岔，發(fā)送幀

if 沒有收到ACK then

增加隨機(jī)退避間隔時間

重復(fù)第2步

802.11 receiver

- if 正確接收幀

延遲SIFS時間（短幀間間隔時間）后汪疮，向發(fā)送端發(fā)送ACK(由于存在隱藏站問題)

基本思想：?允許發(fā)送端“預(yù)約” (reserve)信道峭火，而不是隨機(jī)發(fā)送數(shù)據(jù)幀，從而避免長數(shù)據(jù)幀的沖突

v ■發(fā)送端首先利用CSMA向BS發(fā)送一個很短的RTS(request-to-send)幀

§ RTS幀仍然可能彼此沖突 (但RTS幀很短)

v ■BS廣播一個CTS(clear-to-send)幀作為對RTS的響應(yīng)

v ■CTS幀可以被所有結(jié)點(diǎn)接收

§ 消除隱藏站影響

§ 發(fā)送端可以發(fā)送數(shù)據(jù)幀

§ 其他結(jié)點(diǎn)推遲發(fā)送

利用很小的預(yù)約幀徹底避免了數(shù)據(jù)幀沖突智嚷！

?

IEEE 802.11 MAC幀

IEEE 802.11數(shù)據(jù)幀地址

v■802.11數(shù)據(jù)幀有4個地址字段

v■地址 4 用于自組網(wǎng)絡(luò)

v■地址1~地址3：