Chapter 5 Link Layer (連結層).

Presentation on theme: "Chapter 5 Link Layer (連結層)."— Presentation transcript:

1 Chapter 5 Link Layer (連結層)

2 Topic Overview 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址
5.5 乙太網路 5.6 集線器和交換器 R.-W. Hung 2011

3 Topic Overview (Cont.) 目標 (Goal) 了解資料連結層背後服務的原理： 立即性與實作不同的連結層之技術
發現錯誤並修正 分配一個廣播通道：多重存取 連結層的位址 可靠的資料轉換與流量控制：是! 立即性與實作不同的連結層之技術 應用層 傳輸層 網路層 連結層 實體層 R.-W. Hung 2011

4 第五章 導覽流程 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路
5.6 集線器和交換器 R.-W. Hung 2011

5 5.1 連結層簡介與服務 基本術語 網路層 vs. 連結層 主機和路由器皆稱為節點(node) 沿著通訊路徑，連結相鄰節點的通訊通道，稱為
5.1 連結層簡介與服務 基本術語 主機和路由器皆稱為節點(node) 沿著通訊路徑，連結相鄰節點的通訊通道，稱為 連結(link) 有線連結 (wired link) 無線連結 (wireless link) 區域網路 (LAN) 連結層的封包稱為訊框(frame)  將資料(封)包(datagram)封裝 網路層 vs. 連結層 網路層的責任是規劃來源封包到目的端主機的路徑 連結層的責任為  經由連結，將資料封包從一個節點傳輸到相鄰的節點 (路徑上，相鄰節點間的可靠/不可靠資料傳輸) 應用層 傳輸層 網路層 連結層 實體層 R.-W. Hung 2011

6 連結層的主要工作 來源主機 目的主機 圖5.1 連結層 5.1 簡介與服務 (Cont.) R.-W. Hung 2011 應用層 傳輸層
資料連結層 網路層 實體層 資料連結層 網路層 實體層 目的主機 應用層 傳輸層 資料連結層 網路層 實體層 圖5.1 連結層 R.-W. Hung 2011

7 連結層的主要工作 (Cont.) 資料(封)包在不同的連結上經由不同的連結協定傳輸： 每一種連結協定提供不同的服務 運輸的比喻
例如，第一個連結為乙太網路、中間連結為訊框傳送、最後一個連結為 每一種連結協定提供不同的服務 例如，在連結上可能提供或不提供可靠資料傳輸(rdt) 運輸的比喻 從高雄到台北的行程 小型巴士：高雄 到 台中 飛機：台中 到 新竹 火車：新竹 到 台北 旅客 = 資料包 (datagram) 每段旅程 = 通訊連結 (communication link) 運輸模式 = 連結層協定 (link layer protocol) 旅行社 = 路由演算法 (routing algorithm, 規劃行程) R.-W. Hung 2011

8 連結層服務 訊框化、連結存取：(framing & link access) 相鄰節點間的可靠傳輸 (reliable delivery)
5.1 簡介與服務 (Cont.) 連結層服務 訊框化、連結存取：(framing & link access) 將資料包(data gram  網路層封包)封裝成訊框(frame  連結層封包)  加入標頭及標尾 通道存取 (假如媒介共享) “MAC” 位址在訊框標頭中，用來識別來源端、目的端 MAC (media access control)位址與 IP 位址不同 相鄰節點間的可靠傳輸 (reliable delivery) 我們已經學習過了 (第三章) 在位元錯誤率低的連結上很少使用 (光纖、某些雙絞線) 無線連結：錯誤率高  有線連結一般採用不可靠傳輸 R.-W. Hung 2011

9 連結層服務 (Cont.) 流量控制：(flow control) 錯誤偵測：(error detection)
調整相鄰傳送端和接收端節點之間的步調 錯誤偵測：(error detection) 因訊號衰減或雜訊所產生的錯誤 接收端偵測到錯誤的存在： 通知傳送端重新傳送訊息或是將訊框丟掉 錯誤更正：(error correction) 不憑藉重新傳送、接收端辨識並更正位元錯誤 半雙工和全雙工 (half-duplex & full-duplex) 在半雙工中，連結兩端的節點可以傳送、但無法同時 與傳輸層的服務類似 傳輸層提供端點間兩行程的通訊區段的服務 連結層提供節點間訊框的服務 R.-W. Hung 2011

10 連結層的實作在那裡 ? 在任意一個與每個主機中  每台網路上的設備 連結層的實作在 “網路卡”中 (又稱網路介面卡, NIC)
5.1 簡介與服務 (Cont.) 連結層的實作在那裡 ? 在任意一個與每個主機中  每台網路上的設備 連結層的實作在 “網路卡”中 (又稱網路介面卡, NIC) 乙太網路卡、PCMCI 卡、 卡 執行連結實體層 隨著進入主機系統匯流排 結合硬體、軟體與介面卡 連結層部份功能實作在 S/W、 部份功能實作在 H/W 主機 應用層 傳輸層 網路層 連結層 實體層 CPU 記憶體 主機匯流排 (e.g. PCI) 連結層 控制器 實體傳輸 網路介面卡 圖5.2 網路介面卡 R.-W. Hung 2011

11 網路卡通訊 傳送端： 接收端 將資料包(datagram)封裝在訊框(frame)中 加入錯誤確認位元、rdt、流量控制等等
5.1 簡介與服務 (Cont.) 網路卡通訊 傳送端： 將資料包(datagram)封裝在訊框(frame)中 加入錯誤確認位元、rdt、流量控制等等 接收端 尋找錯誤、rdt、流量控制等等 取出資料包，將它傳送到接收端節點 資料包 資料包 控制器 控制器 傳送主機 接收主機 資料包 訊框(frame) 圖5.3 網路卡通訊 R.-W. Hung 2011

12 第五章 導覽流程 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路
5.6 集線器和交換器 R.-W. Hung 2011

13 5.2 錯誤偵測和更正技術 錯誤偵測 訊框封包 (frame)內容 錯誤偵測並不是 100% 可靠的
5.2 錯誤偵測和更正技術 錯誤偵測 訊框封包 (frame)內容 EDC = 錯誤偵測及更正位元 (冗餘) D = 被錯誤檢查所保護的資料、可能包含標頭欄位 錯誤偵測並不是 100% 可靠的 協定可能會遺漏某些錯誤 (不過這很少發生) 更大的 EDC 欄位能夠得到更佳的偵測與更正 (datagram) (datagram) 圖5.4 錯誤偵測與更正的情景 R.-W. Hung 2011

14 5.2.1 同位檢查 (parity checking)
單一的同位元 (偶同位/奇同位)  以偶同位為例 EDC 為1 bit D 內的1的個數+EDC = 偶數 偵測單一位元錯誤 無法更正錯誤位元 二維同位元 偵測並更正單一位元錯誤 圖5.5 單一位元的偶同位 同位位元 將D切成 i列 j行 圖5.6 二維的偶同位 R.-W. Hung 2011

15 網際網路檢查和 目標 傳送端 接收端 偵測在傳送的資料區段中的 “錯誤” (例如、翻轉的位元) (注意： 大都用在傳輸層)
5.2.2 檢查和 (check sum) 網際網路檢查和 目標 偵測在傳送的資料區段中的 “錯誤” (例如、翻轉的位元) (注意： 大都用在傳輸層) See 第3.3.2節 傳送端 將資料區段的內容視為一連串16位元的整數 檢查和：資料區段內容相加 (1的補數和) 傳送端會將檢查和的值放入UDP檢查和欄位中 接收端 計算收到的資料區段的檢查和 確認計算出來的檢查和是否和檢查和欄位中的相等： NO – 偵測到錯誤 YES – 沒有偵測到錯誤。但是仍然可能有錯誤? R.-W. Hung 2011

16 網際網路檢查和 (Cont.) 作法： 傳送端： 將資料分段的內容視為一列16位元的整數 檢查和：資料分段內容的加法 (1的補數和)
5.2.2 檢查和 (check sum) 網際網路檢查和 (Cont.) 作法： 傳送端： 將資料分段的內容視為一列16位元的整數 檢查和：資料分段內容的加法 (1的補數和) 傳送端將檢查和的值放入UDP的檢查和欄位 接收端： 計算收到的資料分段的檢查和 確認計算出來的檢查和是否和檢查和欄位中的相等： NO – 偵測到錯誤 YES – 沒有偵測到錯誤。但是仍然可能有錯誤? 後面有更多介紹  資料+檢查和 = Ex: +) 1’s補數: 01&10 check sum = R.-W. Hung 2011

17 循環冗餘檢查 (CRC, cyclic redundancy check)
選擇 r+1 個位元為樣本 (產生器) G 傳送端/接收端協調出來的資訊，第一個bit為1 運作：傳送端計算 r 個 CRC 位元，R，使得 <D, R> 正好能被 G 整除 (2模數除法，其內+和法均為XOR) 接收端知道 G  將 <D, R> (2模數除法, div2)除以 G  假如餘數不為0：偵測到錯誤 可以偵測出任何少於r+1個位元的叢發錯誤 實務上經常使用在 ATM、HDCL 圖5.7 CRC 編碼 D左移 r個位元 R = (D  2r div2 G)取餘數 R.-W. Hung 2011

18 循環冗餘檢查 (Cont.) 作法： 傳送端： 將資料位元 D 視為二進位數字 選擇 r+1 個位元為樣本 (產生器) G
計算 r 個 CRC 位元，R，使得 R = (D  2r div2 G)取餘數 將 <D, R> 傳送到接收端 接收端： 擁有 r+1 個位元為樣本 (產生器) G 計算收到的資料封包 <D’, R’> 將 <D’, R’> (2模數除法)除以 G 若餘數不為0：偵測到錯誤 否則，D = D’ R.-W. Hung 2011

19 循環冗餘檢查 (Cont.) CRC 範例 D = 101110 G = 1001, r =3
傳送端計算 R = (D  2r div2 G)取餘數 D  2r = rem(D  2r div2 G) = R = 011 <D, R> = 若接收端接收 = <D’, R’> rem( div2 1001) = 1  0  錯誤發生 XOR運算 +: XOR /: 運算過程的+均不進(借)位  XOR 圖5.8 簡單的 CRC 運算 R.-W. Hung 2011

20 第五章 導覽流程 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路
5.6 集線器和交換器 R.-W. Hung 2011

21 5.3 多重存取協定 多重存取連結與協定 兩種型態的“連結”： 點對點 廣播 (分享的線路或媒介) 撥號存取的PPP
5.3 多重存取協定 多重存取連結與協定 兩種型態的“連結”： 點對點 撥號存取的PPP 乙太網路交換器和集線器之間的點對點連結 廣播 (分享的線路或媒介) 傳統的乙太網路 上傳 HFC 無線區網 R.-W. Hung 2011

22 5.3 多重存取協定 (Cont.) 多重存取連結與協定 (Cont.) 圖5.9 各種多重存取通道 R.-W. Hung 2011

23 多重存取協定 (multiple access protocol)
5.3 多重存取協定 (Cont.) 多重存取協定 (multiple access protocol) 多重存取 單一的分享廣播通道 同時兩個或更多節點的傳送  干擾 碰撞 (collision)  假如節點在同一個時間收到兩個或更多個信號 多重存取協定 決定節點如何分享通道的分散式演算法。例如，決定節點何時能夠傳送 必須使用通道本身來傳送有關通道分享的通訊! 沒有不同頻帶的通道做為協調的功能 R.-W. Hung 2011

24 理想的多重存取協定 速率為 R bps 的廣播通道 當只一個節點要傳送資料時，它可以擁有R bps 傳輸率
5.3 多重存取協定 (Cont.) 理想的多重存取協定 速率為 R bps 的廣播通道 當只一個節點要傳送資料時，它可以擁有R bps 傳輸率 當 n 個節點要傳送資料時，每一個節點以平均速率 R/n 來傳送資料 完全的非集中式：(協定是分散式的) 沒有用來協調傳輸的特殊節點 沒有時脈和時槽的同步 協定要簡單 R.-W. Hung 2011

25 多重存取協定的分類 通道分割 (channel partitioning protocol)
5.3 多重存取協定 (Cont.) 多重存取協定的分類 通道分割 (channel partitioning protocol) 將共享的通道分割成「小塊 」 (時槽、頻率、碼) 將這些「小塊」分配為每個節點專用的 ref. 1.3節 隨機存取 (random access protocol) 不分割通道，允許碰撞 從碰撞「復原」 輪流存取 (polling protocol) 節點可以輪流，但是要傳送較多資料的節點可以傳送較長的時間 節點輪流使用完整的通道 R.-W. Hung 2011

26 通道分割協定 TDM：時間分割多重存取 (time-division) 每一個「回合」中，存取通道
5.3.1 通道分割協定 通道分割協定 TDM：時間分割多重存取 (time-division) 每一個「回合」中，存取通道 每一節點站在每一回合中，得到固定長度的時槽 (長度  封包傳送時間) 沒有使用的時槽(slot)會變成閒置的 範例：6個節點站的 LAN，1、3、4 有封包；時槽 2、5、6 為閒置的 6-slot frame 1 3 4 1 3 4 圖5.10(a) 一個6個節點的TDM例子 R.-W. Hung 2011

27 通道分割協定 (Cont.) FDM：頻率分割多重存取 (frequency-division) 通道頻譜被分割成頻帶
每一節點站分配到固定的頻帶 沒有用到的傳輸頻帶會閒置 範例：6個節點站的 LAN， 1、3、4 有封包，頻帶 2、5、6 為閒置的 時序 FDM cable 頻帶 圖5.10(b) 一個6個節點的FDM例子 R.-W. Hung 2011

28 隨機存取協定 當節點有封包要傳送時  兩個以上的節點同時傳送資料時  隨機存取協定說明： 隨機存取協定的範例：
5.3.2 隨機存取協定 隨機存取協定 當節點有封包要傳送時  以全部的通道資料速率 R 傳送 節點間沒有做前置的協調 兩個以上的節點同時傳送資料時  “碰撞” (collision) 隨機存取協定說明： 要如何偵測碰撞 要如何從碰撞中復原 (例如，經由等待一段隨機延遲時間來重傳) 隨機存取協定的範例： 分槽式 ALOHA ALOHA CSMA、CSMA/CD、CSMA/CA R.-W. Hung 2011

29 隨機存取協定 (Cont.) 分槽式(slotted) ALOHA 假設 運作 所有的訊框(frame)都是同樣大小
5.3.2 隨機存取協定 隨機存取協定 (Cont.) 分槽式(slotted) ALOHA 假設 所有的訊框(frame)都是同樣大小 時間被切分為等大小的時槽(time-slot)，長度可傳送1個訊框 節點只有在時槽開始時，才會傳送訊框 節點為同步的 如果兩個以上的節點在時槽內傳送，所有的節點都會偵測到碰撞 運作 當節點要傳送新的訊框時，它會在下一個時槽傳送 如果沒有碰撞，節點會在下一個時槽傳送新的訊框 假如產生碰撞，節點會依照機率 p，在接下來的每個時槽中重新傳送訊框，直到成功為止 R.-W. Hung 2011

30 隨機存取協定 (Cont.) 分槽式 ALOHA (Cont.) 優點 缺點 單一的活動節點，能以通道的全部速率連續傳送
5.3.2 隨機存取協定 隨機存取協定 (Cont.) 分槽式 ALOHA (Cont.) 優點 單一的活動節點，能以通道的全部速率連續傳送 高度的非集中式：只有節點中的時槽需要同步 簡單 缺點 碰撞，浪費時槽 閒置的時槽 節點需要在比傳輸封包少的時間內偵測碰撞 時脈同步 碰撞發生 C = 發生碰撞 E = 閒置 S = 成功 圖5.11 分槽式 ALOHA的例子 R.-W. Hung 2011

31 隨機存取協定 (Cont.) 分槽式 ALOHA (Cont.) 效率
5.3.2 隨機存取協定 隨機存取協定 (Cont.) 分槽式 ALOHA (Cont.) 效率 當有大量節點，每個節點有大量的訊框要傳送時，長時間下成功時槽所佔的比例 假設有 n 個節點有很多訊框要傳送，每個時槽傳送的機率為 p 節點 1 在一個時槽中成功的機率為 = p(1p)n1 (節點 1 進行傳送的機率 = p ; 其它節點不進行傳送的機率 = (1p)n1) 任意節點傳送成功的機率為 = n  p(1p)n1 當 n 趨近於無線大，我們得到 n  p(1p)n1 的極限值為 1/e = 0.37  在最佳狀況下，分槽式 ALOHA通道成功用來傳輸的時間只有 37% R.-W. Hung 2011

32 隨機存取協定 (Cont.) CSMA (carrier sense multiple access) 原理 人類的比方
5.3.2 隨機存取協定 隨機存取協定 (Cont.) CSMA (carrier sense multiple access) 原理 傳送之前先聆聽 (carrier sensing) 假如通道感測到閒置  傳送整個訊框 假如通道感測到忙碌  延後傳送 人類的比方 不要打斷別人的談話 R.-W. Hung 2011

33 隨機存取協定 (Cont.) CSMA (Cont.) CSMA 碰撞 (collision) 碰撞還是會發生
5.3.2 隨機存取協定 隨機存取協定 (Cont.) CSMA (Cont.) CSMA 碰撞 (collision) 碰撞還是會發生 傳遞延遲使得兩個節點可能無法聽到其他人的傳送 碰撞時，傳送整個封包時間的浪費 距離和傳遞延遲決定了碰撞的機率 A B C D t1 t0 t1時, B的封包還未抵達D, 因此, D會感測到"通道閒置"而送出封包  碰撞發生 圖5.13 兩個傳輸時，發生碰撞的CSMA節點的時空示意圖 R.-W. Hung 2011

34 隨機存取協定 (Cont.) CSMA (Cont.) CSMA/CD (CSMA with collision detection)
5.3.2 隨機存取協定 隨機存取協定 (Cont.) CSMA (Cont.) CSMA/CD (CSMA with collision detection) 碰撞偵測：(collision detection) 在區域網路中是簡單的：測量訊號強度，比較傳送和接收訊號 在無線區域網路中是困難的：當傳送時，接收端關閉 EtherNet(乙太網路) 採用CSMA/CD 圖5.14 使用碰撞偵測的 CSMA R.-W. Hung 2011

35 5.3.3 輪流存取協定 (taking-turns protocol)
輪詢 (Polling) 主節點輪流邀請從屬節點傳送資料 問題： 輪詢的額外負擔 延遲 單點故障 (主節點) 資料 輪詢 主節點 資料 從屬節點 R.-W. Hung 2011

36 輪流存取協定 (Cont.) 記號(令牌/權杖)傳遞 (Token passing) 控制記號(token)依序從一個節點傳到下一個節點
問題： 記號的額外負擔 延遲 單點故障 (token 遺失) 邏輯連接成環狀 (ring) ? OK T (無資料傳輸) T data R.-W. Hung 2011

37 多重存取協定總結 通道分割  以時間、頻率或碼 存機存取 (動態的) 輪流 時間分割、頻率分割
5.3 多重存取協定 (Cont.) 多重存取協定總結 通道分割  以時間、頻率或碼 時間分割、頻率分割 存機存取 (動態的) ALOHA、S-ALOHA、CSMA、CSMA/CD 載波感測  在某些技術中是簡單的 (有線)、其他的有困難 (無線) CSMA/CD 使用在乙太網路 CSMA/CA 使用在 輪流 從主節點輪詢、記號傳遞 藍芽h、FDDI、IBM Token Ring R.-W. Hung 2011

38 區域網路的技術 到目前介紹的連結層： 接下來：區域網路的技術 服務、錯誤偵測/更正、多重存取 定址 (addressing)
5.3 多重存取協定 (Cont.) 區域網路的技術 到目前介紹的連結層： 服務、錯誤偵測/更正、多重存取 接下來：區域網路的技術 定址 (addressing) 乙太網路 (Ethernet) 集線器、交換器 (hub / switch) PPP (point-to-point protocol) R.-W. Hung 2011

39 第五章 導覽流程 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路
5.6 集線器和交換器 R.-W. Hung 2011

40 5.4 連結層定址 MAC 位址 (media access control) 32 位元的 IP 位址 (IPv4)  IPv6 ?
5.4 連結層定址 MAC 位址 (media access control) 32 位元的 IP 位址 (IPv4)  IPv6 ? 網路層位址 用來接收資料包(datagram)，到目的IP子網路 MAC (或是區域網路、實體、乙太網路) 位址 (LAN 位址) 連結層位址 用來接收訊框(frame)  從一個介面到另一個實體連結介面 (同一個網路) 48 位元 MAC 位址 (大多數的 LAN) 燒錄在網路卡(NIC)的ROM中，有時候是在軟體裡 (virtual machine) R.-W. Hung 2011

41 MAC 位址 (LAN 位址) 每一張網路卡都具有唯一的MAC位址 (48 bits) 廣播位址 = FF-FF-FF-FF-FF-FF
5.4 連結層定址 (Cont.) MAC 位址 (LAN 位址) 每一張網路卡都具有唯一的MAC位址 (48 bits) 廣播位址 = FF-FF-FF-FF-FF-FF = 網路卡 1A-2F-BB AD 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 71-65-F7-2B-08-53 LAN (有線或無線的) 圖5.16 每個連接到LAN的網路卡都有獨一無二的MAC位址 R.-W. Hung 2011

42 MAC 位址 (Cont.) MAC 位址的分配 MAC 位址 vs. IP 位址 MAC 位址是可攜性
由 IEEE (Institute of Electrical and Electronics Engineers, 機構管理 網路卡製造商向 IEEE 購買部分的MAC位址 (保證唯一性) MAC 位址 vs. IP 位址 MAC 位址：如同身份證號碼 IP 位址：如同郵寄地址 MAC 位址是可攜性 可以將網路卡從一個LAN帶到另一個LAN IP 位址 不具可攜性  與節點連接的IP子網路相關 R.-W. Hung 2011

43 IP與MAC 位址 應用層 傳輸層 IP位址 MAC位址 實體層 來源端+目的端 來源端+目的端 1A-2F-BB-76-09-AD LAN
5.4 連結層定址 (Cont.) IP與MAC 位址 應用層 傳輸層 IP位址 MAC位址 實體層 來源端+目的端 1A-2F-BB AD 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 71-65-F7-2B-08-53 LAN (有線或無線的) 來源端+目的端 R.-W. Hung 2011

44 ARP ARP (Address Resolution Protocol, 位址解析協定) [RFC 826]
5.4 連結層定址 (Cont.) ARP ARP (Address Resolution Protocol, 位址解析協定) [RFC 826] Q：當我們知道節點 B 的 IP 位址時，要怎麼決定 B 的 MAC位址？ 區域網路上的每一個 IP 節點 (主機、路由器)都有 ARP 表 ARP 表格：某些區域網路節點的 IP/MAC 位址對應 < IP 位址; MAC 位址; TTL> TTL (存活期)：位址對應會被遺忘的時間 (通常 20 分鐘) LAN中部份的資料(非全部) 88-B2-2F-54-1A-00 LAN 71-65-F7-2B-08-53 88-B2-2F-54-1A-1F 7C-B2-2F90-75-B1 R.-W. Hung 2011

45 ARP (Cont.) ARP 表 IP 位址 MAC 位址 TTL 163.17.1.14 7C-B2-2F90-75-B1
13:46:20 88-B2-2F-54-1A-00 12:43:00 71-65-F7-2B-08-53 13:50:00 圖5.18 節點 中可能的 ARP 表格 R.-W. Hung 2011

46 ARP (Cont.) ARP 協定 情境一：A 想要傳送封包給同一LAN中的 B，B 的 MAC 位址不在 A 的 ARP 表中 過程步驟
 A 廣播 ARP 查詢封包，內含 B 的 IP 位址 目的端 MAC 位址 = FF-FF-FF-FF-FF-FF (廣播的MAC位址) LAN 上的所有機器都會收到 ARP 查詢  B 收到 ARP查詢 封包，將它(B)的 MAC 位址回應給 A 訊框傳送給 A 的 MAC 位址 (單點傳播)  A 在它的ARP表格中儲存B的 IP-到-MAC 的位址對應，直到資訊變舊 (逾時) ARP 為 “隨插即用”的： 節點在沒有網路管理者介入的狀況下建立它們的ARP表格 R.-W. Hung 2011

47 ARP (Cont.) A B R ARP 協定 (Cont.)
情境二：A 想要傳送封包給不同LAN中的 B，B 的 MAC 位址不在 A 的ARP表格中 (經由 R 從 A 到 B 傳送資料封包，另假設 A 知道 B 的 IP 位址) 路由器 R 中有兩個 ARP 表 (對每個 IP 介面均保存一個ARP表) R 1A-23-F9-CD-06-9B E6-E BB-4B CC-49-DE-D0-AB-7D A C-E8-FF-55 88-B2-2F-54-1A-0F B 49-BD-D2-C7-56-2A 圖5.19 由路由器相連的兩個子網路 R.-W. Hung 2011

48 ARP (Cont.) ARP 協定 (Cont.) 情境二 (Cont.) 過程步驟  A 建立來源端為 A，目的端為 B 的資料段
 A 使用 ARP表格，取得 R 中IP = 的 MAC 位址  A 使用 R 的 MAC 位址做為目的端、建立連結層訊框、訊框內包含了 A 到 B 的 IP 資料段  A 的網路卡傳送訊框  R 的網路卡接收訊框  R 從乙太網路訊框移除 IP 資料段，並看到它的目的端是 B  R 使用 ARP表 (IP = ) 取得 B 的 MAC 位址  R 建立包含 A 到 B 的 IP 資料段的訊框、並傳送給 B 應用層 傳輸層 IP位址 MAC位址 實體層 S=A; D=B S=A; D=R 應用層 傳輸層 IP位址 MAC位址 實體層 S=A; D=B S=R; D=B R.-W. Hung 2011

49 第五章 導覽流程 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址
5.5 乙太網路 (Ethernet) 5.6 集線器和交換器 R.-W. Hung 2011

50 5.5 乙太網路 乙太網路 (Ethernet) “主要的” 有線區域網路技術 便宜  100 Mbps網卡只要$20 !
5.5 乙太網路 乙太網路 (Ethernet) “主要的” 有線區域網路技術 便宜  100 Mbps網卡只要$20 ! 第一個廣泛使用的區域網路技術 比記號環區域網路以及ATM 簡單、便宜 速度不斷地提升：10 Mbps ~ 10 Gbps 圖5.20 Metcalfe’s 的原始乙太網路設計圖 R.-W. Hung 2011

51 星狀拓樸 (star topology) 在1990年代中期，匯流排拓樸 (bus topology) 是非常普及的 現今流行：星狀拓樸
5.5 乙太網路 (Cont.) 星狀拓樸 (star topology) 在1990年代中期，匯流排拓樸 (bus topology) 是非常普及的 所有節點在相同碰撞範圍內 (可以碰撞其它節點) 現今流行：星狀拓樸 在中央的是交換器(switch)作動 每一個“spoke”均執行(分離) 乙太網路協定 (每一個節點不會發生碰撞) 交換器 (a) bus：同軸電纜 (b) 星狀 (start) 圖5.21 乙太網路 (a) 匯流排架構 (b) 星狀架構 R.-W. Hung 2011

52 乙太網路訊框結構 (frame structure)
5.5 乙太網路 (Cont.) 乙太網路訊框結構 (frame structure) 傳送端網路卡將 IP 資料包(datagram) (或是其他的網路層協定封包) 封裝在乙太網路訊框中 前置位元 (8 bytes) 一個位元組 之後有7個位元組的 用來同步傳送端和接收端的時脈速率 圖5.22 乙太網路訊框結構 R.-W. Hung 2011

53 乙太網路訊框結構 (Cont.) (MAC)位址：6 個位元組 類型：2個位元組 CRC：4個位元組
假如網路卡收到與目的端位址相符的訊框或是廣播位址訊框(例如 ARP封包) ，它會將訊框中的資料傳送到網路層協定 否則，網路卡會刪除訊框 類型：2個位元組 表示上一層的協定 (通常是 IP 或是其他可能支援的協定，如 Novell IPX 和 AppleTalk) CRC：4個位元組 接收端會檢查此一欄位，如果錯誤就會丟棄此一訊框 R.-W. Hung 2011

54 乙太網路  不可靠(un-reliability)的非預接式 (connectionless)
5.5 乙太網路 (Cont.) 乙太網路  不可靠(un-reliability)的非預接式 (connectionless) 非預接式：傳送端和接收端NICs之間沒有交握程序 不可靠的：接收端NIC不會傳送 ACK 或是 NAK 到傳送端NIC 傳送到網路層的資料包串流可能會出現間斷(gaps, 資訊電報遺失) 假如應用程式使用 TCP，則間斷會被填滿 否則，應用程式會看到間斷 乙太網路MAC 協定：unslotted CSMA/CD R.-W. Hung 2011

55 乙太網路  CSMA/CD 演算法 運作步驟  NIC從網路層接收資料包並建立訊框 (datagram  frame)
5.5 乙太網路 (Cont.) 乙太網路  CSMA/CD 演算法 運作步驟  NIC從網路層接收資料包並建立訊框 (datagram  frame)  假如NIC感測通道是閒置的，則它會開始傳送訊框。假如它 感測到通道是忙碌的，則它會等待通道閒置、接著再開始傳 送  假如NIC將整個訊框傳送出去而沒有偵測到其它傳送，則 NIC完成這個訊框的傳送 !  假如NIC在傳送的同時，偵測到其它傳送，則它會停止傳送 並且傳送出一個擁擠訊號 (jam signal)  在之停止傳送之後，NIC會進入指數退回 (exponential backoff) 階段：在第 n 次碰撞之後，NIC會從{0, 1, 2, ..., 2m1}中隨機選擇 k (m = min{n, 10})。然後，NIC會等待 k512 個位元時間後，再回到步驟  R.-W. Hung 2011

56 乙太網路標準 定義在 IEEE 802.3 許多不同的乙太網路標準 定義連結層與實體層 一般 MAC協定與訊框格式
5.5 乙太網路 (Cont.) 乙太網路標準 定義在 IEEE 802.3 定義連結層與實體層 許多不同的乙太網路標準 一般 MAC協定與訊框格式 不同速度：2 Mbps、10 Mbps、100 Mbps、1Gbps、10G bps 不同實體層的媒介：光纖、電纜 MAC協定與訊框格式 100BASE-TX 100BASE-T4 100BASE-FX 100BASE-T2 100BASE-SX 100BASE-BX 光纖實體層 銅 (雙絞) 實體層 實體層 應用層 傳輸層 網路層 連結層 圖 Mbps 的乙太網路標準  共通的連結層、不同的實體層 R.-W. Hung 2011

57 第五章 導覽流程 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址
5.5 乙太網路 (Ethernet) 5.6 集線器(hub)和交換器(switch) R.-W. Hung 2011

58 5.6 集線器(hub)和交換器(switch)
實體層的中繼器(repeater) 從一個連結(link)進入的位元會以同樣的速率被送出到所有其它的連結 一個連接到集線器的節點可以碰撞另一個節點 沒有訊框緩衝區 集線器沒有 CSMA/CD：由主機的NICs偵測碰撞 雙絞線 集線器 (hub) R.-W. Hung 2011

59 交換器 (switch) 連結層裝置：比集線器聰明，扮演作動的角色 透明的 隨插即用、自我學習 儲存及轉送乙太網路訊框
5.6 集線器和交換器 (Cont.) 交換器 (switch) 連結層裝置：比集線器聰明，扮演作動的角色 儲存及轉送乙太網路訊框 當訊框在此裝置轉送時，其檢驗進入訊框MAC位址、並選擇性地轉送到一個或更多個連接介面 使用CSMA/CD來存取區段(segment) 透明的 主機感覺不到交換器的存在 隨插即用、自我學習 交換器不需要設定 R.-W. Hung 2011

60 交換器 (Cont.) 允許多個同時傳送 主機有專用且直接的連結線到交換器 交換器有緩衝區，可以緩衝封包
乙太網路協定使用在每一個進入的連結、但是沒有碰撞  全雙工 每個連結都擁有它的碰撞範圍 交換器：A-到-A’ 與 B-到-B’ 可同時傳送，且不會發生碰撞 使用 hub 則是不可能的 A C’ B 1 2 6 3 4 5 C 六個交換器介面 (1、2、3、4、5、6) B’ A’ R.-W. Hung 2011

61 交換器 (Cont.) 交換器表 (switch table) Q：交換器如何知道A’ 可通過到達介面4、B’可通過到達介面5？
主機MAC位址; 到達主機的介面; 時間標籤 類似路由器表(routing table) Q：如何建立、維持在交換表中的通道？ A：一些像是路由器的協定 (routing protocol) A C’ B 1 2 6 3 4 5 C 六個交換器介面 (1、2、3、4、5、6) B’ A’ R.-W. Hung 2011

62 交換器 (Cont.) 交換器表的自我學習(self-learning) 交換器會學習哪一個主機經由哪一個介面可以到達
當訊框抵達時，交換器會 “學習” 傳送端的位置：進入的LAN 區段(LAN segment) 在交換表中紀錄傳送端; 位置介面對 Source = A Dest = A’ A A A’ C’ B 交換器表 (初始為空) MAC 位址 到達主機的介面 TTL 1 2 6 3 A 1 60 4 5 C 六個交換器介面 (1、2、3、4、5、6) B’ A’ R.-W. Hung 2011

63 交換器 (Cont.) 以交換器互相連結 交換器之間可以連接在一起
Q：從 A傳送封包到F，如何知道 S1 把預定的訊框轉送到F via S4 與 S2？ A：自我學習！(How ? Thanking ...) D E F S2 S4 S3 H I G S1 A B C R.-W. Hung 2011

64 機構網路 電子郵件伺服器 到外部網路 web 伺服器 路由器 交換器 IP 子網路 集線器 集線器 集線器
5.6 集線器和交換器 (Cont.) 機構網路 電子郵件伺服器 到外部網路 web 伺服器 路由器 交換器 IP 子網路 集線器 集線器 集線器 圖5.26 同時使用集線器、乙太網路交換器、及路由器的機構網路 R.-W. Hung 2011

65 交換器 vs. 路由器 都是儲存並轉送的裝置 路由器：網路層裝置 (檢驗網路層標頭) 交換器：連結層裝置 路由器維護路由表，實作路由演算法
5.6 集線器和交換器 (Cont.) 交換器 vs. 路由器 都是儲存並轉送的裝置 路由器：網路層裝置 (檢驗網路層標頭) 交換器：連結層裝置 路由器維護路由表，實作路由演算法 交換器維護交換表，實作過濾、學習演算法 R.-W. Hung 2011

66 比較總表 集線器 hub 路由器 router 交換器 switch 流量隔離 無 有 隨插即用 最佳化路由 直接傳送
5.6 集線器和交換器 (Cont.) 比較總表 集線器 hub 路由器 router 交換器 switch 流量隔離 無 有 隨插即用 最佳化路由 直接傳送 R.-W. Hung 2011

67 第五章 總結 資料連結層服務的原則 各種連結層技術的例證和實作 錯誤偵測、更正 分享寬頻通道：多種存取 連結層位址 乙太網路 交換器區域網路
PPP  連結層的虛擬網路  R.-W. Hung 2011

68 End of Chapter 5 R.-W. Hung 2011

69 課程結束 謝謝同學本學期的配合 R.-W. Hung 2011