計網第五章筆記 -- 資料鍊路層

文章目錄

• 介紹
• • 鍊路層服務
  • 鍊路層的實作
  • • 擴充卡通信
• 差錯檢測
• • 奇偶校驗法
  • • 一維奇偶校驗
    • 二維奇偶校驗
  • CRC
  • • 例子
• 多路通路鍊路和協定
• • 多路通路控制
  • • 理想的多路傳輸協定
  • MAC協定
  • 信道劃分
  • • 時分複用
    • 頻分複用
  • 随機通路協定
  • • Slotted ALOHA
    • • 效率分析
    • Pure(unslotted) ALOHA
    • • 效率分析
    • CSMA
    • CSMA/CD
  • Taking Turns
  • • 集中式輪詢
    • 分布式輪詢
  • 總結
• 交換區域網路
• • MAC位址和ARP
  • • 跨路由器的通信過程
  • 以太網
  • • Star topology
    • • 曾經結構：10base2
      • 目前結構：star topology prevails
    • 以太網的幀結構
    • 以太網的服務模型
    • • CSMA/CD算法
      • 指數型規避算法
      • CSMA/CD的效率
    • 以太網技術的類型
    • Mancgester Encoding
  • 互聯裝置
  • • Hubs
    • 交換機
    • • 自學習
      • 過濾轉發算法
      • 機關網絡
    • 交換機和路由器的比較
• 練習

介紹

資料鍊路層的責任是在相鄰的結點之間傳輸資料報(datagram)

主機和路由器都是一個結點

連接配接相鄰結點的通道，分為以下幾種

• 有線連接配接，無線連接配接
• 區域網路，廣域網

層二包是一個幀

資料報可以在不同連接配接上的不同協定間傳輸：

• 802.3 Ethernet link，以太網
• Ppp link，point to point protocol，點對點協定，早期的寬帶，需要撥号上網
• ATM link ，異步傳輸模式
• Frame relay，幀中機服務
• Fiber link
• 802.11 link: one type of wireless links，統稱為wifi技術
• 4G/5G link

鍊路層服務

• 封幀，解幀：把資料打包成幀傳輸
  • 确定傳輸目标位址時候需要使用MAC位址（media Access Control Address），6 * 8共四十八位，例如：00-16-EA-AE-3C-40
• 鍊路的通路控制功能
  • 上面沒有标藍的兩個有可靠性控制
• 流量控制
• 檢錯功能
  • 檢錯之後直接把這個資料扔掉，不再往上傳
  • 網卡，交換機都是這樣，檢測到有錯誤之後直接扔掉，到達不了網絡層，如果能到三層，一定沒有差錯，是以checknum是多餘的
• 差錯的校正
  • 發四個包到接收端，四個包異或一下得到第五個包，如果有一個資料包丢掉之後，但是接收到了第五個包，可以把收到的包進行異或就可以恢複了
  • 現在的網卡沒有這個功能
• 半雙工和全雙工通信
  • 目前的網絡99%都是全雙工通信的，兩方可以同時發送資訊
  • 半雙工：對講機

鍊路層的實作

對于主機來說是實作在網卡的，對于路由器來說是内置的，交換機和路由器一樣

網卡：NIC(network interface card)，現在用的是 PCMCIA card，連接配接在總線上的

PCMCIA card: Personal Computer Memory Card International Association

網卡沒有CPU，包含硬體，軟體和固件（燒在晶片中的軟體）

擴充卡通信

• 發送端
  • 把資料報封裝在幀裡面
  • 添加差錯檢驗位
  • 流量控制
• 接收端
  • 檢查錯誤
  • 把資料報從幀中解幀出來，并向上傳輸到網絡層

三種工作方式：

• 正常工作模式：看鍊路層頭的mac位址是不是自己，如果是自己就解幀發送到網絡層，如果不是直接扔掉
• 如果是全1的包，那麼說明是一個廣播位址，也會解開往上傳
• 混雜模式：收到幀就解開往上傳

差錯檢測

要求發送端發送備援資訊

奇偶校驗法

一維奇偶校驗

最後加一個校驗碼，表示這段資料中1的個數是奇數還是偶數

二維奇偶校驗

把資料組織成二維的形式，一位差錯時可以糾正，兩位出錯時可以校驗

CRC

循環備援校驗(Cyclic Redundancy check)，目前普遍使用的方法

把要發的資料左移若幹位（比generator少一位），然後除以generator，得到的餘數叫做CRC

具體移動位數取決于發送端與接收端約定的産生式(generator)，現在普遍采用的是32位，也可以叫做多項式

餘數連同要發的資料Data發送到接收端，接收端收到之後連同餘數一起除以generator，如果沒有差錯的話，最後得到的餘數是0

産生式是多少位就可以檢測出來多少位的錯誤，檢驗錯誤之後直接取反就是正确資料

原始資料左移r位（其中generate是r+1位），然後異或得到的餘數（任何數異或0都是自己）

例子

這裡的除法是模二除法，不往前借位，10-01=11

generator：1001

Data：101110

Data左移三位為：101110,000，除以generator得到餘數011，拼接到Data後面發送到接收端

lyn: ：為什麼餘數是011，不是11

這裡的remainder表示求餘數

多路通路鍊路和協定

鍊路類型

• 點對點鍊路（P2P鍊路）
  • PPP for dial-up access，ADSL
  • 不會出現碰撞，不需要控制，通信時候甚至不需要mac位址，因為已經建立好了二者之間的通信，我發就是你收
• 廣播（shared wire or medium）
  • 資料同時發的話會産生碰撞
  • 老的以太網
  • HFC，混合光纖同軸電纜
  • 802.11 無線區域網路
• 交換式鍊路
  • Ethernet

多路通路控制

多個結點同時使用鍊路時候需要處理沖突

沖突（interference）：兩個結點以上同時發資料就會發生碰撞(collision)，同時發資料在收到之後一查就發現是錯的，隻能扔掉

分類

• 分散式的
  • 目前采用比較多的方法
  • 任意一個結點需要使用通道發資料時候就直接發了，有可能産生碰撞，産生碰撞之後停止發送，過一段時間之後再申請發送，直到發送成功為止
  • 每一個結點自行決定什麼時候發送資料
  • 使用的是分布式的算法
  • 需要有能力檢測是不是發生碰撞了，檢測到需要直接停止發送
• 集中式的
  • 需要一個控制器
  • 發資料前現象控制器申請，許可之後才能發送
  • 可以保證任意時間點隻有一個結點在發送資料
  • 控制器壞了整個網絡就癱瘓了

理想的多路傳輸協定

四個要求（假設鍊路帶寬為R bps）

• 隻有一個結點傳資料的時候可以使用全部的帶寬（R bps）
• 當多個結點共享時候每一個結點使用的帶寬是相等的（R/M bps）
• 盡可能的完全分散
  • 不需要集中的控制器
  • 沒有同步的時鐘
• 算法要足夠簡單

MAC協定

三種大的分類

• 信道劃分
  • 時分
  • 頻分
  • 碼分
  • 波分
  • 空分（不同方向，例如衛星通信）
  • 适合高負載的情況
• 随機通路
  • 信道是随機劃分的，允許碰撞
  • 産生碰撞時候會重新分類
  • 适合使用者量比較少的情況
• taking turns
  • 大家輪着使用，有一個結點控制大家使用，有一個結點使用的時候其他不許使用
  • 集中式輪詢
  • 分布式輪詢
  • 同一時間隻有一個使用者發資料

信道劃分協定

信道劃分

時分複用

TDMA：每個使用者分一個時間片，大約為發一幀資料的時間，大家輪流使用通道

例如：座機打電話

頻分複用

FDMA：使用不同的頻率發資料

配置設定給你的頻率你不發資料就浪費掉了，别人不能使用

例如：wifi（分為三個頻段），ADSL

随機通路協定

重點

思想：想發就發了

當一個結點有包要發時候

• 以帶寬的速率發送
• 沒有優先級的問題

兩個結點同時發送時候會産生碰撞問題，如果産生碰撞，那麼所有結點都停止發送，讓鍊路回到碰撞之前的狀态

典型随機通路MAC協定

• ALOHA
• Slotted ALOHA
• CSMA, CSMA/CD, CSMA/CA

Slotted ALOHA

Additive Link On-link Hawaii System ，線上夏威夷系統的附加鍊路

适合與活躍的使用者數非常少的情況（會一直産生碰撞）

夏威夷島上無線通信的一個協定

ALOHA是夏威夷的一個土話，打招呼的意思

Slotted ALOHA，分片的ALOHA協定

假設

• 所有的幀都是一樣大小
• 是一個同步的協定，所有的結點發資料必須在一個時間片開頭發資料
• 時間分為大小相等的時間片
• 如果在一個開頭兩個都發資料，那麼就會産生碰撞，這時候兩個都停止發送
  • 下一個時間片開頭，兩個結點都有機率P的大小重新發送資料，直到發送成功
• 如果沒有碰撞，那麼在下一個時間片可以再發下一個幀

• 優點
  • 隻有一個結點在發資料的話，可使用所有帶寬
  • 高度分散化式的，隻要求在時間片開頭發資料
  • 簡單
• 缺點
  • 發生碰撞就浪費了
  • 有空閑的時間片
  • 結點要有能力檢測碰撞
  • 要求結點的時鐘嚴格同步

目前很少使用了

效率分析

假設有N個結點，都有大量的幀發送，發送資料的機率是P

一個結點發送成功的機率是： p ( 1 − p ) N − 1 p(1-p)^{N-1} p(1−p)N−1

N個結點發送成功的機率是： N p ( 1 − p ) N − 1 Np(1-p)^{N-1} Np(1−p)N−1

最大的效率，以p為變量求 N p ( 1 − p ) N − 1 Np(1-p)^{N-1} Np(1−p)N−1的最大值為 1 e = 0.37 \frac 1 e = 0.37 e1​=0.37

最大的利用效率為37%

Pure(unslotted) ALOHA

不分時間片，碰撞的機率增加了

效率分析

最大效率僅為0.18，比上一個Slotted ALOHA協定更糟糕

協定限制了信道的吞吐量

CSMA

這個必須要記着，不要把字寫錯了

CSMA (Carrier Sense Multiple Access)，載波偵聽多路通路

在傳輸前感覺信道是不是空閑

• 如果空閑了才發資料
• 如果不空閑就推遲傳送

也無法避免碰撞，有如下原因

• 傳播延遲，在感覺時候另一個結點占用的資訊還沒有發送到自己這裡
• 兩個同時感覺信道，發現沒被使用時候同時發資料

CSMA/CD

Collision Detection，帶碰撞檢測的載波監聽的多路通路

CSMA/CD: carrier sensing, deferral as in CSMA

• collisions detected within short time
• colliding transmissions aborted, reducing channel wastage

碰撞檢測

• 有線網絡較好檢測：測量信号強度
• 無線網絡比較複雜，采用的方式是避免碰撞

Taking Turns

鍊路上有一個主節點(master)，其他都是從節點(slave)

任意一個時間點隻有一個結點發資料，輪詢到一個結點的時候隻能發一幀資料，下次輪詢到才能再發一幀

藍牙采用的這種方式

集中式輪詢

• 主節點邀請結點去傳輸資料
  • 如果有資料就發，沒有就繼續問下一個結點
• 通常與“dumb”從裝置一起使用
  • dumb：啞裝置，都比較簡單
• 缺點
  • 輪詢是有開銷的
  • 有延時
  • 單點故障（主節點）

分布式輪詢

适用于環形網絡

Token傳輸，(托肯傳輸，建議寫成令牌傳輸)

Token：是一個很小的控制幀，每個結點必須拿到令牌才能傳輸資料

• 控制令牌在結點之間順序傳播
• 缺點
  • 輪詢是有開銷的（網絡上隻有一個結點要發資料時候需要轉一圈才能發）
  • 延時
  • 單節點故障（擁有token的結點）

總結

• 信道劃分
  • 适合于使用者比較大情況
• 随機通路協定
  • ALOHA, S-ALOHA, CSMA, CSMA/CD
  • Collision detection: easy in some technologies (wire), hard in others (wireless)
  • CSMA/CD used in Ethernet（以太網）（CD：碰撞檢測）
  • CSMA/CA used in 802.11）（CA：碰撞避免）
• Take turns
  • 集中式(Polling from central site)和分布式(token passing)
  • Bluetooth, FDDI, IBM Token Ring

交換區域網路

MAC位址和ARP

MAC：區域網路位址(LAN)，實體位址(physical)，網卡位址(NIC)，MAC位址

• 功能：擷取從一個接口到另一個實體連接配接接口（同一網絡）的幀
• 48位長的，燒在NIC的ROM中的，
  • 例如：1A-2F-BB-76-09-AD
  • Broadcast address = FF-FF-FF-FF-FF-FF

不分層，不會重複，在出廠時MAC就已經設定好了

通信：

下到二樓發送時候需要填源MAC位址和目的MAC位址

所有結點在網絡層和鍊路層之間維護了一個表，叫做ARP表，記錄了IP位址和MAC位址的對應關系

當ARP表中沒有一個IP的MAC位址的時候，會在區域網路中進行廣播，詢問MAC位址，這時候目的主機會傳回自己的MAC位址

然後發送到目的主機之後先CRC檢查差錯，沒有問題就解幀變成IP段，然後繼續向上傳輸

ARP是動态的，有一個TTL，如果在TTL時間中沒有被通路過，就會删掉這個記錄，通常為20min；初始時這個表是空的

記錄格式： < IP address; MAC address; TTL>

ARP是工作在區域網路中的，不能跨路由器

ARP: Address Resolution Protocol

跨路由器的通信過程

目的：主機A要發資料到主機B

• 網絡層，目的IP位址是B的IP位址
• 然後下到鍊路層進行封幀，源MAC位址是A的，目的MAC位址是路由器的左側MAC位址（DHCP技術獲得）
  • 如果沒有路由器左邊接口的位址，可以廣播一個ARP封包，要路由器的MAC位址
  • 路由器接收到封包之後就會發送回自己的MAC位址
• 路由器收到幀之後進行CRC檢查，沒有差錯之後就解包，送到第三層
• 然後根據目的位址查路由表，路由包就轉發到右邊的位址
• 然後下到二層，進行封幀，源MAC位址是路由器右邊的位址，目的MAC位址是B的MAC位址
  • 如果沒有就廣播ARP要B的MAC位址
• 送到B之後再次進行CRC檢查，沒有問題就往第三層送，然後逐漸解包送到應用層中

路由器上每個端口都有一個ARP表

以太網

英文：Ethernet

目前最流行的有線網絡，因為技術簡單，成本低，帶寬也很寬(10Mbps - 10Gbps)

wifi也可以稱為無線以太網

所有的網卡通過總線連到網絡(ETHER)上

Star topology

曾經結構：10base2

總線式的區域網路，需要先确定總線是否空閑，所有發出去的資料都會被其他結點收到（設定為混雜模式才可以）

• 10Mbps網
• base: 不需要調試，有資料直接傳
• 2：有效距離200M（實際185m）

目前結構：star topology prevails

樹狀結構或者是層狀結構

交換式的區域網路

每一個枝叫做一個

spoke

這裡使用的交換機也是一個存儲轉發裝置

以太網的幀結構

頭和尾統稱為幀頭，在資料的兩端

• Preamble：總共八位元組長，前7個位元組是10101010，後八個位元組是10101011，固定死的，用于同步時鐘信号
• 目标位址：MAC位址，48位的
• 源位址：MAC位址，48位的
• Type：類型，資料域中封裝的什麼類型的資料，一般都是IP包
• CRC：4個位元組長，用于校驗的，可以檢查出來32位的01跳變
• Data：資料域，最長可以有1500個位元組

wifi的幀結構和這個幀結構不相容，比這個要複雜一點

在IP層上進行變換，在無線路由器（實際是一個鍊路轉發器）進行轉換，這個既不是路由器也不是交換機

以太網的服務模型

Internet: best effort

以太網的服務模型：無連接配接的不可靠的服務（CRC+CSMA/CD ）

服務模型需要記住

• CSMA/CD: 發送之前先感覺鍊路是否空閑
• CRC: 然後進行差錯檢查

發送完資料後不需要等待接收端的确認，不需要建立連接配接和确認，隻有一個CRC檢查

傳輸采用的是基帶(base)傳輸，直接把資料發到響應的鍊路上，與ADSL不一樣，ADSL需要數據機，

采用的是Manchester encoding，從上變到下表示的是1，從下變到上表示0，傳輸過程中剛幹擾能力比較強（是實體層的方法）

CSMA/CD算法

中英文都要記住

Carrier Sense Multiple Access Collision Detection，帶碰撞檢測的載波監聽的多路通路

算法也要了解并記住

A: sense channel, if idle 
then {
    transmit and monitor the channel; 
    If detect another transmission // 檢測到碰撞，檢測到碰撞電平就會升高
  		then { 
       		abort and send jam signal;// 停止發送資料并且發送一個堵塞信号
			update collisions; // 更新碰撞次數，剛開始發的時候一定是0
			delay as required by exponential backoff algorithm; //  延遲做規避，延遲時間是指數型的backoff算法，依據是碰撞次數
			goto A//  重新偵聽信道
		}
 	else {
        done with the frame; // 資料傳輸完成 
        set collisions to zero // 清空碰撞計數器
	}
}
else {wait until ongoing transmission is over and goto A}
           

指數型規避算法

• 第一次碰撞，從0和1中選一個數字，然後做的延時是 K ∗ 512 b i t K * 512 bit K∗512bit的傳輸時間
• 第二次之後k的範圍是 { 0 , 1 , 2 , 3 } \{0,1,2,3\} {0,1,2,3}
• 大于10之後K的範圍都是 { 0 , 1 , 2 , 3 , 4 , ⋯   , 1023 } \{0,1,2,3,4,\cdots,1023\} {0,1,2,3,4,⋯,1023}

對于10Mbps的以太網來說，傳輸一位的時間是1微秒，如果K=1023，傳輸時間是50ms

Jam Signal：確定所有的傳輸都可以收到碰撞信号，有48bit

CSMA/CD的效率

• 傳播延時(prop)是指最遠的兩個點之間的時間
• 傳送延時(trans)是指最大的幀傳輸時用的時間

理想情況下效率接近于1,

鍊路的控制方式是分散式的

以太網技術的類型

統稱為802.3

802.11是wifi

• 總線式
• 交換機
• 光纖方式
• 雙絞線

紅色的使用的是光纖

藍色的使用的是雙絞線

幀結構和鍊路的使用方式都是一樣的CSMA/CD

Mancgester Encoding

• 在 10base2使用
• 不需要對時鐘進行同步
• 是一個分散式的控制

互聯裝置

Hubs

中文名：集線器

外表和宿舍的小交換機是一樣的，是一個實體層的裝置

PDU是位，不需要轉發，接收到的資料全部都廣播出去（不能隔離碰撞域）

沒有緩存，不運作CSMA/CD算法

隻要把網卡設定為混雜模式就可以收到資訊，不夠安全

資料采集時候比較友善

交換機

是一個鍊路層的裝置，是鍊路裝置

處理的PDU是幀，幀全部接受完了之後才會進行處理并轉發

是一個存儲轉發裝置（優點：隔離碰撞域）

轉發的時候需要維護一個MAC表，查詢轉發出口

檢查傳入幀的MAC位址，有選擇地将幀轉發到一個或多個傳對外連結路

轉發之前需要運作一下CSMA/CD算法避免碰撞

對使用者來說都是透明的

熱插拔的，有自學習能力（學習并維護ARP表）

對應于不同的端口可以同時發送，但是如果從一個端口進出資料就不可以同時進行

例如 A → A ′ , B → B ′ , C → C ′ A\to A',B\to B',C\to C' A→A′,B→B′,C→C′就可以同時進行，但是 A → A ′ A\to A' A→A′和 B → A ′ B\to A' B→A′就不能同時進行

全雙工的通信并且每個結點都有緩存的

路由器的每一個端口都有一個ARP表

每個交換機都維護一個交換表

• 交換表的每一行是(MAC位址， 端口号， TTL)
• TTL一般是60分鐘，逾時會直接扔掉
• 可以通過自學習獲得
• 沒有資料的時候Flooding（廣播）一下，然後接收到了資訊之後存起來友善後面使用

自學習

當Flooding之後，會把端口号和傳出端口記下來，這個過程就是一個自學習過程

傳入和傳出的時候都會記錄在表裡面

過濾轉發算法

• 交換機收到一幀資料的時候，把源MAC位址和接口号記錄下來（自學習，如果表裡面有了的話就更新一下TTL）
• 在交換表裡面查找目的MAC位址

if entry found for destination
then {
    if dest on segment from which frame arrived// 如果目的MAC位址和源MAC位址在一個interface就直接扔掉   
    then drop the frame
    else {
        CSMA/CD // 運作CSMA/CD算法檢查是否有碰撞
        forward the frame on interface indicated// 轉發幀到目的端口
    }
}   
else {
    CSMA/CD // 運作CSMA/CD算法檢查是否有碰撞
    flood // 廣播
}
           

機關網絡

主交換機帶寬1Gbps，末端交換機帶寬100Mbps

要是需要采集子網的所有進出資料，需要在主交換機上進行配置，用到的技術是端口鏡像，把輸出端口鏡像到采集端口

交換機和路由器的比較

• 都是存儲轉發裝置，交換機和路由器都可以隔離碰撞域
• 交換機運作在區域網路，路由器運作在廣域網
• 交換機維護交換表，路由器維護路由表
• 交換機運作CSMA/CD,filter & forwarding,self-learning，路由器運作路由算法
• 運作在不同的層，路由器運作在網絡層，交換機運作在鍊路層

廣播域不能被hub或者交換機隔離，隻能通過路由器隔離廣播域

如果虛拟化區域網路則需要使用路由器進行隔離，是以需要把主交換機再進行修改（交換式的路由器），修改之後再進行MAC位址配置，把那些MAC位址放到一個虛拟區域網路中

再看一下PPT73頁左右的那些東西，各種通路過程

練習

A，交換機到一個結點的最遠距離是100m

B

ADE

ADE（F是對角布線，一般都是沿着邊邊走，是以是錯的）

C

B（a:54Mbps）

Spanning Tree Protocol(STP)：生成樹算法，把一個圖轉換成樹

可以解決廣播風暴問題：一個廣播幀很快淹沒了整個網絡