Microsoft PowerPoint - Chap 0_IntroductionToCourse [相容模式]

Transcription

1 Introduction to ( 電腦網路概論 ) Prof. Ruo-Wei Hung( 洪若偉 ) Department of Computer Science and Information Engineering, Chaoyang University of Technology, Wufeng, Taichung 41349, Taiwan [email protected] by R.-W. Hung, Dept. CSIE, CYUT, Taiwan

2 Course Introduction ( 課程介紹 ) by R.-W. Hung, Dept. CSIE, CYUT, Taiwan

3 任課教師 洪若偉 (Ruo-Wei Hung) Web-site: Tel: ext Office Hours: 週二 13:30~15:30 (E724 研究室 ) 週四 13:30~15:30 (E724 研究室 ) Personal Information 一妻一子一女 一屋一田四車 ( 含腳踏車 機車 ) 一貸款一基金

4 教科書 教科書 (Textbook): 1. 劉宗瑜 陳元炘譯, 電腦網際網路 5/e, 全華圖書, 2010 年. (ISBN: ) 2. Kurose and Ross, Computer Networking A Top-Down Approach, 5/e, Pearson Addison- Wesley, ( 歐亞書局代理 ) 3. 投影片 (Slides) 參考書目 (Reference Books): 1. 陳湘陽, 網路概論 2/e, 博碩, (ISBN: ) 2. 陳惠貞 / 周念湘, 網路概論, 碁峰, (ISBN: )

5 上課方式 1. 投影片 ( 挖洞填空 )+ 題目講解 ( 課堂上課 ) 2. 隨時隨堂考 ( 不能補考 )

6 課程大綱 Chapter 1: s and the Internet ( 電腦網路與網際網路 ) Chapter I: Network Media and Devices ( 網路媒介與設備 ) Chapter 2: Application Layer ( 應用層 ) Chapter 3: Transport Layer ( 傳輸層 ) Chapter 4: Network Layer ( 網路層 ) Chapter 5: Link Layer and Local Area Networks ( 連結層與區域網路 )

7 How to Solve a Problem or Study a New Topic? 2W-1H-1E What? (Network 是什麼?) Why? ( 為何需要 Network?) How? ( 如何設計 安裝 使用 Network?) Extension! ( 如何應用 Network?) 5W-2H 思考法 九宮格思考法

8 Why do We Need to Study Network? 重要性 網路 (Network) 是終端設備透過通訊媒介及通訊設備來溝通的一種現代化電腦應用 電腦網路需要硬體及軟體互相搭配 電腦網路需要硬體基礎設施, 搭配軟體以達到終端設備通訊的目的 電腦網路的應用無遠弗界 電腦網路已成為人類不可或缺的生活必須品 課程目標 學習電腦網路系統的運作 學習電腦網路系統的組成 學習電腦網路系統的設計 學習電腦網路系統的應用

9 End of Introduction

10 Chapter 1 s and the Internet ( 電腦網路與網際網路 ) by R.W. Hung, Dept. CSIE, CYUT, Taiwan 1.1

11 Topic Overview 1.1 什麼是網際網路 (Internet)?( 網路協定 protocol) 1.2 網路的邊際 (Network Edge) 1.3 網路的核心 (Network Core) 1.4 網路的效能 (Network Performance) 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) *1.6 面臨攻擊的網路 (Networks Under Attack) *1.7 網路的歷史 (History of Networks) [*] Option 1.2 / 86

12 第一章導覽流程 1.1 什麼是網際網路 (Internet)? 1.2 網路的邊際 (Network Edge) 終端系統 連線網路 連結 1.3 網路的核心 (Network Core) 電路交換 封包交換 網際網路結構 1.4 網路的效能 (Network Performance) 封包交換網路的延遲 封包遺失和產出率 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) 1.3 / 86

13 1.1 什麼是網際網路 (Internet)? 基本元素的描述 Interconnected networks 幾百萬台連接的計算裝置 : 主機 (host) = 終端系統 (end system) 執行網路的應用程式 通訊連結 (link,wired/wireless) 雙絞線 銅線 光纖 無線電 衛星 資料傳輸速率 = 頻寬 (bandwidth, bps) 路由器 (router) / 交換器 (switch): 傳送封包 (packet, 小段的資料 ) 1.4 / 86

14 1.1 什麼是網際網路 (Cont.) 基本元素的描述 (Cont.) sensor 手機 TV 平板電腦 host/end system : PC : 伺服器 : 行動裝置 : 行動電話 communication links : 存取點 : wired links router/switch : 路由器 行動網路 家用網路 公司網路 全球性 ISP 區域性 ISP 圖 1.1 網際網路的元素 1.5 / 86

15 1.1 什麼是網際網路 (Cont.) 基本元素的描述 (Cont.) 封包交換網路 vs. 運輸網路 : End system: building Packet: truck Communication link: highway Packet switch: intersection 1.6 / 86 Ex 1.1

16 1.1 什麼是網際網路 (Cont.) 網際網路的應用 (p. 1-10) IP 相簿 (photo sharing; 網路電話 (skype; 找很久不見的朋友! 1.7 / 86

17 Handshaking 所有人必須對所有協定的運作方式有所共識 1.1 什麼是網際網路 (Cont.) 什麼是網際網路 : 從元件來看 協定 (protocol) 控制訊息的傳送 接收 例如 : TCP IP HTTP 網際網路電話協定 乙太網路協定 網際網路 : 網路組成的網路 (interconnected networks) 不嚴謹的階層性 公眾網際網路 (public) 與私有內部網路 (intra-net) 網際網路標準 Hung2 RFC:Request for comments ( IETF: 網際網路工程工作小組 (Internet Engineering Task Force; 行動網路全球性 ISP Other standards: IEEE org. 家用網路 區域性 ISP 公司網路 1.8 / 86

18 投影片 8 Hung2 Institute of Electrical and Electronics Engineers Ruo-Wei Hung, 2013/8/25

19 1.1 什麼是網際網路 (Cont.) 什麼是網際網路 : 從服務來看 通訊的架構允許分散式的應用程式 網頁 網路電話 電子郵件 遊戲 電子商務 檔案分享 提供給應用程式的通訊服務 可靠的將資料由來源送達目的地 (TCP reliability) 盡其可能 的資料交付 (UDP un-reliability) 1.9 / 86

20 1.1 什麼是網際網路 (Cont.) 什麼是協定 (protocol) 人們的協定 請問現在幾點? 傳送特定的信息 當收到訊息或其它事件時, 採取特定的動作 Hi Hi 請問現在幾點? pm 2:00 time 圖 1.2(a) 人類的協定 1.10 / 86

21 1.1 什麼是網際網路 (Cont.) 什麼是協定 (Cont.) 電腦網路的協定 機器而非人類 網際網路上的所有通訊活動都由協定來管理 連線請求 1. 協定 (protocol) 定義兩個以上通訊實體間交換訊息的格式與順序, 以及傳送與接收訊息或發生其它事件時所採取的動作 2. 不同的協定用來完成不同的通訊工作 連線回應 Get < 檔案 > time 圖 1.2(b) 計算機網路的協定 Exercise / 86 Ex 1.2

22 第一章導覽流程 1.1 什麼是網際網路 (Internet)? 1.2 網路的邊際 (Network Edge) 終端系統 連線網路 連結 1.3 網路的核心 (Network Core) 電路交換 封包交換 網際網路結構 1.4 網路的效能 (Network Performance) 封包交換網路的延遲 封包遺失和產出率 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) 1.12 / 86

23 1.2 網路的邊際 (Network Edge) 細看網路結構 網路的邊際 (edge) 應用程式與主機 (1.2 節 ) 網路應用 (p.1-10) 連線網路與實體媒介 有線 無線通訊連結 (Chapter 6) 網路的核心 (core) 互相連接的路由器 / 交換器 (1.3 節 ) 網路的網路 1.13 / 86

24 1.2 網路的邊際 (Cont.) 網路的邊際 終端系統 ( 主機 ): 執行應用程式 例如 : 網頁 電子郵件 位於 網路的邊緣 基本的終端系統互動模型 用戶端 / 伺服器模型 (client-server model) 用戶端主機從隨時開啟的伺服器端要求及接收服務 例如 : 網頁瀏覽器 / 伺服器 電子郵件用戶端 / 伺服器 分散式應用程式 (distributed application) P2P 對等式模型 (peer-peer model) 使用最少的 ( 或不使用 ) 專用伺服器 例如 : 網際網路電話 BitTorrent emule Limewire 1.14 / 86

25 1.2 網路的邊際 (Cont.) 網路的邊際 (Cont.) 基本的終端系統互動運作模型 (Cont.) 用戶端 / 伺服器模型 P2P 對等式模型 用戶端 / 伺服器 client P2P client client server 圖 1.3 終端系統互動運作模型 Ex / 86

26 1.2 網路的邊際 (Cont.) 網路的邊際 (Cont.) 終端系統間的資料傳輸服務 可靠的資料傳輸服務 不允許資料傳輸有錯誤 盡其可能的資料傳輸服務 盡其可能的將資料放入網路來傳輸, 但允許資料傳輸有錯誤 data 1.16 / 86

27 1.2 網路的邊際 (Cont.) 網路的邊際 (Cont.) 終端系統間的資料傳輸服務 (Cont.) 可靠的資料傳輸服務 交握程序 (handshaking): 設定 ( 準備 ), 在資料的傳輸之前» Hello hello 的回應 人類的回應» 在兩個通訊的主機之間設定 狀態 TCP Transmission Control Protocol (Chapter 3)» 網際網路的可靠資料轉換服務» RFC 793» 可靠的 按順序的 位元組串流資料傳輸遺失 : 確認及重傳» 流量控制 : 傳送端的流量不超過接收端» 壅塞控制 :(congestion) 當網路壅塞時, 傳送端會降低傳送速率 1.17 / 86

28 1.2 網路的邊際 (Cont.) 網路的邊際 (Cont.) 終端系統間的資料傳輸服務 (Cont.) 盡其可能的資料傳輸服務 UDP User Datagram Protocol (Chapter 3)» 網際網路的不需可靠資料傳輸服務» RFC 768» 非預接式» 不可靠的資料傳輸» 不提供流量控制» 不提供壅塞控制 1.18 / 86

29 1.2 網路的邊際 (Cont.) 網路的邊際 (Cont.) 終端系統間的資料傳輸服務 (Cont.) 使用 TCP 的應用程式 : HTTP ( 網頁 ) FTP ( 檔案傳輸 ) Telnet ( 遠端登入 ) SMTP ( 電子郵件 ) 使用 UDP 的應用程式 : 串流媒體 遠端會議 DNS ( 網域名稱系統 ) 網路電話 1.19 / 86 Ex 1.4

30 1.2 網路的邊際 (Cont.) 連線網路與實體媒介 What? 如何連結終端系統以及邊緣路由器 (edge router)? 類別 附註 家用連線網路 機構的連線網路 ( 學校 公司 ) 無線連線網路 連線網路的頻寬 (bps; 位元 / 每秒 ) 分享或專屬的 edge router 1.20 / 86

31 1.2 網路的邊際 (Cont.) 連線網路 家用連線網路 家中的終端系統連接到邊際路由器 連線方式 點對點的連線 纜線數據機的連線 1.21 / 86

32 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 家用連線網路 (Cont.) 點對點的連線 經由數據機撥接 (modem)» 至 56Kbps, 直接存取路由器 ( 通常較少 )» 無法與電話同時使用 : 不是 隨時服務 DSL: 數位用戶專線 (digital subscriber line)» 建構來源 : 電話公司 ( 典型的 )» 至 1 Mbps 上傳速率 ( 目前通常 < 256 Kbps)» 至 8 Mbps 下載速率 ( 目前通常 < 1 Mbps)» 提供中央辦公室電話的實體線路 ADSL ( 非對稱式 asymmetric 數位用戶專線 )» 下載頻寬 : 0.5~8 Mbps» 上傳頻寬 : ~ 1 Mbps VDSL ( 非常高速 DSL) 上傳與下載速率不同 1.22 / 86

33 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 家用連線網路 (Cont.) 點對點的連線 (Cont.) DSL: 數位用戶專線 (digital subscriber line) (Cont.) home phone Existing phone line: 0-4KHz phone; 4-50KHz upstream data; 50KHz- 1MHz downstream data Internet DSLAM home PC splitter ( 分離器 ) DSL modem central office telephone network 圖 1.6 DSL 網際網路連線 1.23 /

34 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 家用連線網路 (Cont.) 纜線數據機的連線 藉由電纜與光纖的網路將家庭用戶連接到 ISP (Internet Service Provider) 路由器» 家庭用戶分享到路由器的存取線路 建構來源 : 有線電視公司 HFC (Hybrid Fiber Coaxial Cable): 混合光纖 / 同軸電纜線» 非對稱的 : 至 30 Mbps 下載速率,2 Mbps 上傳速率 1.24 / 86

35 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 家用連線網路 (Cont.) 纜線數據機的連線 (Cont.) 機上盒伺服器 家庭環境 電纜數據機 電纜 分離器 電纜 10 Mbps 乙太網路 纜線頭端 纜線分佈網路 ( 簡化 ) 家庭 1.25 / 86 圖 1.7 纜線數據機的連線

36 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 家用連線網路 (Cont.) 光纖到府 (Fiber-To-The-Home) 的連線 光纖速度遠快於雙絞線及同軸電纜 光纖直接從機房鋪設到住家 兩種彼此競爭的光學傳播網路架構» Passive Optical Network (PON, 被動 )» Active Optical Network ( AON, 主動 ) 遠快於網際網路速率, 且也可提供電視及電話服務 目前提供的可能用戶速率» 上傳 : 2 ~ 10M bps» 下載 : 10 ~ 20M bps 1.26 /

37 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 家用連線網路 (Cont.) 光纖到府 (Fiber-To-The-Home) 的連線 (Cont.) ONT Internet optical fibers OLT optical fiber ONT central office optical splitter ONT 圖 1.8 PON FTTH 網際網路連線 1.27 /

38 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 機構的連線網路 公司 / 學校採區域網路 (Local Area Network, LAN) 連結終端系統到邊緣路由器 最常見的區域網路 乙太網路 (Ethernet) 10 Mbps 100 Mbps 1 Gbps 10 Gbps 乙太網路 目前的形式 : 終端系統連接到交換式乙太網路 ( 星狀 ) LANs: 第五章 第 I 章 ( 本教材 ) 1.28 / 86

39 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 機構的連線網路 (Cont.) 典型的乙太網路連線 100 Mbps Ethernet switch Institutional router To Institution s ISP 100 Mbps 100 Mbps 1 Gbps server 圖 1.9 乙太網路網際網路連線 1.29 /

40 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 無線連線網路 (Wireless) 分享的無線連網路連接終端系統到路由器 經由基地台又稱為 存取連結點 Ad hoc 無線的 LAN: b/g (WiFi) :11 or 54 Mbps 廣域無線連線網路 由電信公司提供 ~1Mbps 透過手機系統 (EVDO, HSDPA) 下一個會是 (?) :WiMAX (10 s Mbps) 涵蓋廣域 邊緣路由器 基地台 行動主機 1.30 / 86

41 1.2 網路的邊際 (Cont.) 連線網路 (Cont.) 典型家庭網路元件 : DSL 或纜線數據機 路由器 / 防火牆 /NAT 乙太網路 無線存取連結點 ( 基地台, 一般的 router 均提供此無線連結點 ) 無線手提電腦 到 / 從纜線頭端 纜線數據機 路由器防火牆 無線存取連結點 乙太網路 圖 1.6 典型家庭網路的示意圖 1.31 / 86 Ex 1.5

42 1.2 網路的邊際 (Cont.) 實體媒介 (Physical media) 基本術語 位元 : 在多組傳送器 / 接收器間傳輸 實體連結 : 位在傳送器以及接收器之間 實體媒介分類 引導式媒介 (guided media):(wired link) 信號延著固體媒介傳輸 : 銅線 光纖 同軸纜線 非引導式媒介 (unguided media):(wireless) 信號自由地傳輸, 例如 : 無線電 詳細內容 ( 本節將簡述 ) 第 I 章 ( 本教材 ) 1.32 / 86

43 1.2 網路的邊際 (Cont.) 實體媒介 (Cont.) 雙絞銅蕊線 (Twisted Pair) 兩條絕緣的銅線 第三類 : 傳統電話線 10 Mbps 乙太網路 第五類 :100 Mbps 乙太網路 第七類 : / 86

44 1.2 網路的邊際 (Cont.) 實體媒介 (Cont.) 同軸電纜 :(Cable) 兩條同軸的銅製導體 基頻 : 電纜上的單一頻道 傳統的乙太網路 寬頻 : 電纜上的多頻道 HFC 1.34 / 86

45 1.2 網路的邊際 (Cont.) 實體媒介 (Cont.) 光纖 :(Fiber Optic) 玻璃纖維, 可傳導光的脈波, 每個脈波代表一個位元 高速運轉 : 高速的點對點傳輸 ( 例如 : 10~100 Gbps) 低錯誤率 : 中繼器 (repeater) 置放距離遠, 免於電磁波干擾 1.35 / 86

46 1.2 網路的邊際 (Cont.) 實體媒介 (Cont.) 無線電 :(Radio) 利用電磁頻譜傳送訊號 沒有實體的 線路 雙向的 傳輸環境的影響 : 反射 物件的障礙 干擾 1.36 / 86

47 1.2 網路的邊際 (Cont.) 實體媒介 (Cont.) 無線電 :(Cont.) 無線電連結型態 : 地表微波» 例如 : 至 45 Mbps 頻道 LAN ( 例如 : WiFi)» 11 Mbps 54 Mbps 廣域 ( 例如 : 手機 )»3G 手機 : ~ 1 Mbps 衛星» Kbps 至 45 Mbps 頻道 ( 或多個小頻道 )» 270 msec 端點至端點延遲» 同步衛星 vs. 低軌道衛星 1.37 / 86

48 第一章導覽流程 1.1 什麼是網際網路 (Internet)? 1.2 網路的邊際 (Network Edge) 終端系統 連線網路 連結 1.3 網路的核心 (Network Core) 電路交換 封包交換 網際網路結構 1.4 網路的效能 (Network Performance) 封包交換網路的延遲 封包遺失和產出率 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) 1.38 / 86

49 1.3 網路的核心 (Network Core) 網路的核心 ( 中心, core) 網狀互相連結的路由器 基本的問題 : 資料以何種方式經由網路傳輸? 電路交換 (circuit switch): 每通電話均有專用電路 : 電話網路 封包交換 (packet switch): 以不連接的 小段資料 經由網路傳送資料 圖 1.11 網路核心 ( 中心 ) 1.39 / 86

50 1.3 網路的核心 (Cont.) 電路交換 (circuit switch) 意義 : 為通訊保留端點至端點的資源 緩衝區 連線傳輸速率等 建立實體連線, 並保證連結頻寬, 交換容量 專屬的資源 : 不需分享 如同電路的 ( 保證的 ) 效能 需要建立連線 點對點連線 1.40 / 86

51 1.3 網路的核心 (Cont.) 電路交換 (Cont.) 特性 : 網路資源 ( 例如 : 頻寬 ) 被切分為片段 (frame) 片段會被分派給通話 ( 通訊 ) 假如擁有此資源的通話沒有在使用, 則資源片段會閒置 ( 非分享的 ) 將連結頻寬 (bandwidth) 切分為 片段 的技術 分頻多工 (Frequency-Division Multiplexing, FDM) 分時多工 (Time-Division Multiplexing, TDM) 1.41 / 86

52 1.3 網路的核心 (Cont.) 電路交換 (Cont.) 將連結頻寬切分為 片段 的技術 (Cont.) FDM 4 個使用者 頻率 TDM 時間 頻率 時間 圖 1.13 分頻與分時技術 FM 廣播採用何種? 1.42 / 86

53 1.3 網路的核心 (Cont.) 電路交換 (Cont.) 範例 在電路交換網路中, 從主機 A 傳送 640,000 位元的檔案到主機 B 時, 需要多少的時間? 所有的連結都為 Mbps 所有連結都使用具有 24 個時槽的 TDM 需要 500 毫秒 (1 毫秒 = 10-3 秒 ) 的時間來建立一條端點到端點的線路 Ans. 每道線路的傳輸速率 = Mbps / 24 = 64 Kbps 需要 (640,000 bits) / (64 Kbps) = 10 sec 來傳送該檔案 總共時間 = 傳送時間 + 建立通道時間 = 10 sec sec = 10.5 sec Ex / 86

54 1.3 網路的核心 (Cont.) 封包交換 (packet switch) 意義 : 每一個端點至端點的資料串流都會被切分為封包 (packet) 使用者 A B 的封包分享網路資源 每個封包使用完整的連結頻寬 資源在需要時被使用 資源的競爭 要求的資源總量可能會超過可用的 壅塞 (congestion): 封包佇列, 等待可用的連結 儲存並轉送 (store & forward): 封包一次移動一站 節點在傳送之前會接收完整的封包 頻寬被切分為片段專屬的分派資源保留 1.44 / 86

55 1.3 網路的核心 (Cont.) 封包交換 (Cont.) A 100 Mbps 乙太網路 統計式多工 C B 1.5 Mbps 等待輸出連結的封包佇列 D E 圖 1.14 封包交換 A 與 B 的封包次序並沒有固定的模式, 按需求分配的頻寬共享方式 統計式多工 TDM: 在循環 TDM 時框時, 每一個主機會得到同一個時槽 1.45 / 86

56 1.3 網路的核心 (Cont.) 封包交換 (Cont.) 儲存並轉送 (store and forward) L R R R 在 R bps 的連結上, 需要 L/R 秒來傳遞 ( 推出 ) 長度為 L 位元的封包 儲存並轉送 : 在封包傳送到下一個連結之前, 它必須完全到達路由器 延遲 = 3L/R ( 假設沒有傳遞延遲 ) 例題 : L = 7.5 Mbits R = 1.5 Mbps 傳輸延遲 = 15 sec 1.46 / 86

57 1.3 網路的核心 (Cont.) 封包交換 vs. 電路交換 封包交換允許較多的使用者使用網路 範例 1 Mbps 的連結 每一個使用者 : 活動時的速率 100 Kbps 只有 10% 的時間在活動 電路交換 : 10 個使用者 封包交換 : 習題 P6 35 個使用者, 有大於 10 人同時活動的機率小於 N users 1 Mbps 連結 1.47 / 86

58 1.3 網路的核心 (Cont.) 封包交換 vs. 電路交換 (Cont.) 封包交換的問題 極度壅塞時 封包延遲及遺失 需要可靠資料傳輸以及壅塞控制的協定 封包交換 vs. 電路交換 依需要的分派 ( 封包交換 ) vs. 保留的資源 ( 電路交換 ) 網際網路 封包交換 電話系統 電路交換 1.48 / 86 Exercise 1.2

59 1.3 網路的核心 (Cont.) 網路們的網路 粗略的階層性 在中央 : 第一層 ISP ( 例如 :MCI Sprint AT&T Cable and Wireless), 涵蓋本國 / 國際範圍 平等地彼此對待 第一層提供者私下互相連結 ( 對等點 ) 第一層 ISP 第一層 ISP 第一層 ISP 1.49 / 86

60 1.3 網路的核心 (Cont.) 網路們的網路 (Cont.) 第二層 ISP: 較小的 ( 通常是區域性的 ) ISP 連接到一或多個第一層 ISP, 也可能是其它的第二層 ISP 第二層 ISP 付費給第一層 ISP 以連接到其餘的網際網路 第二層 ISP 為第一層提供者的客戶 第二層 ISP 第一層 ISP 第二層 ISP NAP 第二層 ISP 也會私下互相連結, 或連結到 NAP 第一層 ISP 第一層 ISP 第二層 ISP 第二層 ISP 第二層 ISP 1.50 / 86

61 1.3 網路的核心 (Cont.) 網路們的網路 (Cont.) 第三層 ISP 以及本地 ISP 最後一站 ( 存取 ) 網路 ( 最接近終端系統 ) 本地及第三層 ISP 為高層 ISP 的客戶, 連接到其餘的網際網路 本地 ISP 第三層 ISP 第二層 ISP 本地 ISP 第一層 ISP 本地 ISP 第二層 ISP 本地 ISP NAP 第一層 ISP 第一層 ISP 第二層 ISP 本地 ISP 第二層 ISP 本地 ISP 第二層 ISP 本地 ISP 本地 ISP 圖 1.15 ISP 的相互連接 1.51 / 86

62 1.3 網路的核心 (Cont.) 網路們的網路 (Cont.) 一個封包傳送經過許多網路 packet data 本地 ISP 第三層 ISP 本地 ISP 本地 ISP 本地 ISP 第二層 ISP 第二層 ISP 第一層 ISP 第一層 ISP 第一層 ISP 第二層 ISP 本地 ISP 第二層 ISP 本地 ISP 第二層 ISP 本地 ISP 本地 ISP 1.52 / 86

63 第一章導覽流程 1.1 什麼是網際網路 (Internet)? 1.2 網路的邊際 (Network Edge) 終端系統 連線網路 連結 1.3 網路的核心 (Network Core) 電路交換 封包交換 網際網路結構 1.4 網路的效能 (Network Performance) 封包交換網路的延遲 封包遺失和產出率 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) 1.53 / 86

64 1.4 網路的效能 (Network Performance) 封包交換網路的效能 延遲時間 (delay time) 封包遺失 (packet loss) 產出率 (throughput) 1.54 / 86

65 1.4 網路的效能 (Cont.) 封包延遲與遺失如何發生 路由器緩衝區內的封包佇列 封包抵達連結的速率 > 輸出連結的容量 封包在佇列中等待下一輪 正在傳送封包 ( 延遲 ) A 路由器 X B 封包在佇列中等待 ( 延遲 ) 若沒有空的 ( 可使用的 ) 緩衝區, 則抵達的封包會被丟掉 ( 遺失 ) 圖 1.16 路由器 X 的節點延遲與封包遺失 1.55 / 86

66 1.4 網路的效能 (Cont.) 封包延遲的四種來源 節點處理 (processing delay) 檢查位元錯誤 決定輸出連結 節點佇列 (queuing delay) 等待傳送到輸出連結的時間 由路由器的壅塞等級決定 傳輸延遲 (transmission delay) R = 連結頻寬 (bps) L = 封包長度 ( 位元 ) 傳送位元的連結的時間 = L/R eg. 10 Mbps 乙太網路的傳輸速率 R=10 Mbits/sec 將全部封包位元全部推入 ( 傳送到 ) 連結線所需的時間 傳播延遲 (propagation delay) d = 實體媒介的長度 s = 媒介的傳遞速率 ( ~ m/sec) 傳播延遲 = d/s 注意 : s 和 R 是非常不同的量! 1.56 / 86

67 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 傳輸 A 傳播 B 節點處理 佇列 1.57 / 86

68 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 車隊的比喻 車輛以 100 km/hr 前進 收費站以 12 秒服務一台車 ( 傳送時間 ) 車 ~ 位元 ; 車隊 ~ 封包 Q: 車隊在第二個收費站前排好需要多少時間? 100 km 100 km 10 輛車的車隊 收費站 收費站 圖 1.17 封包延遲 以車隊通過收費站為比喻 1.58 / 86

69 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 車隊的比喻 (Cont.) Q: 車隊在第二個收費站前排好需要多少時間? Ans: 整個車隊 通過 收費站所需的時間 = 12 * 10 = 120 sec = 2 min ( 佇列時間 + 處理時間 + 傳輸時間 ) 最後一台車從第一個收費站到第二個收費站所需的時間 = 100 km / (100km/hr) = 1 hr = 60 min ( 傳播時間 ) Ans: 62 分鐘 100 km 100 km 10 輛車的車隊 收費站 收費站 1.59 / 86

70 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 車隊的比喻 (Cont.) 車輛現在以 1000 km/hr 的速率 傳播 ( 遞 ) 收費站以 1 分鐘服務 1 台車 Q: 在所有的車輛被第一個收費站服務完畢之前, 是否有車輛會抵達第二個收費站嗎? Ans: 是的! 在 7 分鐘後, 第 1 台車會到達第二個收費站, 此時仍有三台車在第一個收費站 在封包從第一個路由器完全傳送出去之前, 它的第 1 個位元可能已抵達第二個路由器! 100 km 100 km 10 輛車的車隊 收費站 收費站 1.60 / 86 Ex 1.7

71 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 節點延遲 d nodal d nodal = d proc + d queue + d trans + d prop d proc = 處理延遲» 通常只有幾百萬分之一秒或更少 d queue = 佇列延遲» 取決於壅塞程度 d trans = 傳輸延遲»= L/R, 對低速連結來說, 其值會很大 d prop = 傳播延遲» 從幾百萬分之一秒到幾百個毫秒 傳輸延遲 vs. 傳播延遲 html 1.61 / 86

72 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 節點延遲 d nodal (Cont.) 傳輸延遲 vs. 傳播延遲 html 1.62 / 86

73 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 節點延遲 d nodal (Cont.) 傳輸延遲 vs. 傳播延遲 (Conti.) 傳輸延遲 : 與 routers 間的距離無關, 而與封包長度和連結的傳輸速率有關 傳播延遲 : 與 routers 間的距離有關, 而與封包長度和連結的傳輸速率無關 1.63 / 86

74 1.4 網路的效能 (Cont.) 封包延遲的四種來源 (Cont.) 佇列延遲 d queue d queue = 佇列延遲 取決於壅塞程度 相關參數 R = 連結頻寬 (bps) L = 平均封包長度 ( 位元 / 封包 ) a = 平均封包抵達率 ( 抵達封包數 /sec) 流量強度 (traffic intensity) = La/R 圖 1.18 平均佇列延遲與流量強度的關係 La/R ~ 0: 平均佇列延遲很小 La/R 1: 延遲會變大 La/R > 1: 抵達的 工作 超過可被服務的, 平均延遲為無限大! 進入 queue 的速率 La 離開 queue 的速率 R 1.64 / 86

75 1.4 網路的效能 (Cont.) 真實的 網際網路延遲與路徑 Traceroute 程式 提供延遲測量, 從來源端到路由器, 沿著端點至端點的網際網路路徑到達目的端 原理 : 對到達目的端路徑上的所有路由器 i 傳送三個探針封包, 它們會抵達路由器 i, 位在通往目的端的路徑上 路由器 i 會回傳封包給傳送端 傳送端會紀錄傳送及回傳的時間間隔 3 個探針 3 個探針 3 個探針 1.65 / 86

76 1.4 網路的效能 (Cont.) 真實的 網際網路延遲與路徑 (Cont.) Traceroute 程式 traceroute: gaia.cs.umass.edu 至 從 gaia.cs.umass.edu 到 cs-gw.cs.umass.edu, 三次的延遲測量 1 cs-gw ( ) 1 ms 1 ms 2 ms 2 border1-rt-fa5-1-0.gw.umass.edu ( ) 1 ms 1 ms 2 ms 3 cht-vbns.gw.umass.edu ( ) 6 ms 5 ms 5 ms 4 jn1-at wor.vbns.net ( ) 16 ms 11 ms 13 ms 5 jn1-so wae.vbns.net ( ) 21 ms 18 ms 18 ms 6 abilene-vbns.abilene.ucaid.edu ( ) 22 ms 18 ms 22 ms 7 nycm-wash.abilene.ucaid.edu ( ) 22 ms 22 ms 22 ms 越洋連結 ( ) 104 ms 109 ms 106 ms 9 de2-1.de1.de.geant.net ( ) 109 ms 102 ms 104 ms 10 de.fr1.fr.geant.net ( ) 113 ms 121 ms 114 ms 11 renater-gw.fr1.fr.geant.net ( ) 112 ms 114 ms 112 ms 12 nio-n2.cssi.renater.fr ( ) 111 ms 114 ms 116 ms 13 nice.cssi.renater.fr ( ) 123 ms 125 ms 124 ms 14 r3t2-nice.cssi.renater.fr ( ) 126 ms 126 ms 124 ms 15 eurecom-valbonne.r3t2.ft.net ( ) 135 ms 128 ms 133 ms ( ) 126 ms 128 ms 126 ms 17 * * * * 意指沒有回應 ( 探針遺失, 路由器沒有回應 ) 18 * * * 19 fantasia.eurecom.fr ( ) 132 ms 128 ms 136 ms 1.66 / 86

77 1.4 網路的效能 (Cont.) 真實的 網際網路延遲與路徑 (Cont.) Traceroute 程式 (Conti.) Taiwan HiNet (source) 1.67 / 86

78 1.4 網路的效能 (Cont.) 真實的 網際網路延遲與路徑 (Cont.) Traceroute 程式 (Conti.) Traceroute 應用程式 : PingPlotter ( 作者推薦的圖形介面 - free) / 86

79 1.4 網路的效能 (Cont.) 封包遺失 (packet loss) 發生的原因 連結 (link) 之前的佇列 (router 緩衝區 ) 具有有限的容量 若佇列已滿, 則抵達的封包會被丟棄 ( 遺失 ) 遺失的封包可能會被前一個節點或來源端系統重新傳送, 也可能完全不被重新傳送 A 緩衝區 ( 等待區域 ) 封包開始傳輸 B 若緩衝區已滿, 則抵達的封包將遺失 1.69 / 86

80 1.4 網路的效能 (Cont.) 佇列延遲和封包遺失 Java Applet / 86

81 1.4 網路的效能 (Cont.) 產出率 (throughput) 定義 種類 在傳送端 / 接收端之間的位元轉輸速率 ( 位元 / 每秒 ) 瞬間產出率 : 任一片刻的位元速率 平均產出率 : 某一段時間的平均位元速率 伺服器傳送位元 server, ( with 水流 ) 到輸 file 送管 of F bits to send to client 管中攜帶水流的速率 link capacity R s bits/sec 管中攜帶水流的速率 link capacity R c bits/sec 1.71 / 86

82 1.4 網路的效能 (Cont.) 產出率 (Cont.) 討論 R s < R c 終端到終端的平均產出率為何? R s > R c 終端到終端的平均產出率為何? R s bits/sec R c bits/sec 瓶頸連結 連結在終端到終端的路徑限制了終端到終端的產出率 min{r s, R c } 1.72 / 86

83 1.4 網路的效能 (Cont.) 產出率 (Cont.) 端點到端點產出率 每條連接終端到終端的產出率為 = min(r c, R s, R/10) 現實的情況 : R c 或 R s 通常為瓶頸連結 R s R s R s R R c R c R c Exercise 1.4 圖 1.20 端點到端點產出率 10 條連接 ( 完全 ) 均分主幹的瓶頸連結 R bits/sec 1.73 / 86 Exercise 1.3

84 第一章導覽流程 1.1 什麼是網際網路 (Internet)? 1.2 網路的邊際 (Network Edge) 終端系統 連線網路 連結 1.3 網路的核心 (Network Core) 電路交換 封包交換 網際網路結構 1.4 網路的效能 (Network Performance) 封包交換網路的延遲 封包遺失和產出率 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) 1.74 / 86

85 1.5 協定分層及其服務模型 (Protocol Layers and Their Service Models) 協定 分層 網路是很複雜的, 它包含許多 部份 : 主機 路由器 各種媒介的連結 應用程式 協定 硬體 / 軟體 如何讓硬體 / 軟體在網路中得以溝通 ( 通訊 )? 1.75 / 86

86 1.5 協定分層及其服務模型 (Cont.) 分層式架構 比喻 飛機旅行的組織 票務 ( 購買 ) 行李 ( 檢查 ) 登機門 ( 登機 ) 飛機起飛飛機航行 票務 ( 抱怨 ) 行李 ( 領取 ) 登機門 ( 下機 ) 飛機著陸飛機航行 飛機航行 圖 1.21 搭乘飛機旅行 一系列的步驟 1.76 / 86

87 1.5 協定分層及其服務模型 (Cont.) 分層式架構 (Cont.) 比喻 飛機旅行的組織 (Cont.) 航空公司功能的分層 機票 ( 購買 ) 行李 ( 托運 ) 登機門 ( 登機 ) 起飛跑道 機票 ( 投訴 ) 行李 ( 領取 ) 登機門 ( 下機 ) 飛機著陸 票務行李登機門起 / 降 飛機航線 飛機航線 飛機航線 飛機航行 飛機航線 起飛機場 航空控制中心 抵達機場 圖 1.22 航空功能的水平分層 分層 (layering): 每一個分層實作一個服務 每一個層級內執行某些內部動作 每一個層級使用其下一層所提供的服務 1.77 / 86

88 1.5 協定分層及其服務模型 (Cont.) 分層式架構 (Cont.) 為什麼要分層? 處理複雜的系統 模組化 容易修改分層所提供的服務實作方式 當某一層級修改其功能, 其它層級可以維持不變 (eg. 改變登機門的程序並不會影響到系統的其它部份 ) 分層被視為有害嗎? 1.78 / 86

89 1.5 協定分層及其服務模型 (Cont.) 網際網路協定堆疊 (protocol stack) 應用層 : 支援網路應用程式 FTP SMTP HTTP 傳輸層 : 應用程式端點到端點間的傳輸 TCP UDP 網路層 : 從來源端到目的端的資料段路由 IP 路由協定 連結層 : 在相鄰的網路元件間傳輸資料 PPP 乙太網路 實體層 : 電路中的 位元 應用層傳輸層網路層連結層實體層 1.79 / 86

90 Hung1 1.5 協定分層及其服務模型 (Cont.) ISO/OSI 參考模型 (reference model) 展現層 : 允許應用程式解讀資料的意義, 例如 : 資料加密 資料壓縮 不同電腦之間的轉換 會談層 : 同步化 檢查點 回復資料的交換 網際網路缺少這兩層! 這些服務需不需要? 如果需要, 必須要在應用程式中加入這個功能 需要嗎? 應用層展現層會談層傳輸層網路層資料連結層實體層 1.80 / 86

91 投影片 80 Hung1 ISO = International Organization for Standardization; OSI = Open Systems Interconnection. Ruo-Wei Hung, 2011/10/1

92 1.5 協定分層及其服務模型 (Cont.) ISO/OSI 參考模型 (Cont.) 1.81 / 86

93 1.5 協定分層及其服務模型 (Cont.) ISO/OSI 參考模型 (Cont.) ISO 封包 1.82 / 86

94 1.5 協定分層及其服務模型 (Cont.) 封裝 (Encapsulation) ( 訊息 ) message ( 區段 ) segment ( 資料包 )datagram ( 訊框 ) frame H l H n H n H t H t H t M M M M 來源 應用層傳輸層網路層連結層實體層 連結層實體層 H l H n H t M H l H n H t M switch H l H n H n H t H t H t M M M M 目的地 應用層傳輸層網路層連結層實體層 H l H n H n H t H t M M 網路層連結層實體層 H l H n H n H t H t M M router Ex 1.9 圖 1.24 Protocol layering data encapsulation 1.83 / 86 Ex 1.8

95 1.5 協定分層及其服務模型 (Cont.) 網際網路分層模式的各層簡易功能表 網際網路分層層級網際網路層級名稱功能說明 第 5 層第 4 層第 3 層第 2 層第 1 層 應用層 (Application layer) 傳輸層 (Transport layer) 網路層 (Network layer) 連結層 (Link layer) 實體層 (Physical layer) 應用層提供了使用者網路上的服務, 如網頁存取 檔案傳輸 電子郵件 網路電話... 等 傳輸層主要是確保資料在應用層與網路層之間的傳輸品質, 即正確 沒有遺失 沒有重複 (TCP vs. UDP) 網路層管理節點到另一節點的路徑, 其負責建立 維護及終止兩個節點間的連結路徑, 使資料傳輸依其規劃的路徑傳送 因此, 其必須有 IP 定址的功能 (IP) 連結層負責確保實體層連結的資料之正確性, 包括資料傳輸的錯誤偵測 / 更正 由連結層建立一條端點間的可靠通訊通道, 使網路層得以正確地存取實體層的資料 實體層負責資料位元在實體傳輸媒體上的傳輸, 使電器訊號可在兩個裝置間交換, 主要包括網路的電器規格, 如電壓 電流準位 連接器種類... 等 Exercise / 86

96 總結 涵蓋大量的題材 網際網路概觀 什麼是協定? 網路的非核心部份 核心 存取網路 封包交換 vs. 電路交換 網際網路結構 效能 : 遺失 延遲 產出率 分層與服務模型 你現在擁有 內容 概觀 網路的 感覺 接下來有更深入的細節! 1.85 / 86

97 End of Chapter / 86

98 Chapter 2 Application Layer ( 應用層 ) by R.-W. Hung, Dept. CSIE, CYUT, Taiwan 2.1

99 Topic Overview 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.2 / 103

100 Topic Overview (Cont.) 目標 (Goal) 網路應用協定的概念及實作 傳輸層服務模型 用戶端 伺服端模式網路應用程式架構 點對點架構 藉著驗證常用的應用層協定來學習協定 HTTP FTP SMTP / POP3 / IMAP DNS 撰寫網際網路應用程式 (HW 5%) socket API 應用層 傳輸層 2.3 / 103

101 Topic Overview (Cont.) 一些網路應用程式 電子郵件 Web 即時訊息 遠端登錄 點對點檔案分享 多使用者網路遊戲 串流式儲存視訊片段 影像分享 IP 即時視訊會議 網格運算 2.4 / 103

102 Topic Overview (Cont.) 產生一個網路應用程式 撰寫一個程式 在不同的終端系統上執行且透過網路通訊 例如 :Web 伺服器軟體與瀏覽器軟體通訊 為網路核心裝置撰寫小軟體 網路核心裝置不執行使用者應用程式 終端系統的應用程式允許快速應用的建置與傳遞 應用層傳輸層網路層連結層實體層 應用層傳輸層網路層連結層實體層 應用層傳輸層網路層連結層實體層 2.5 / 103 圖 2.1 應用程式在終端系統間所進行的應用層通訊

103 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.6 / 103

104 2.1.1 網路應用程式架構 應用程式架構 (application architecture) 用戶端 伺服端架構 (client-server) 點對點架構 (P2P peer to peer) 用戶端 伺服端和點對點二者混合式的架構 (hybrid) 2.7 / 103

105 2.1.1 網路應用程式架構 (Cont.) 用戶端 伺服端架構 伺服器 : (server) 隨時服務 固定 IP 位址 以伺服器群 (server farm) 延伸擴充性 用戶端 :(client) 與伺服器通訊 也許是間斷地連結 也許有動態 IP 位址 彼此間不會直接通訊 client 用戶端 / 伺服端 client client server 圖 2.2(a) 用戶端 / 伺服端架構 2.8 / 103

106 2.1.1 網路應用程式架構 (Cont.) 點對點架構 沒有隨時服務的伺服器 任意的終端系統直接通訊 對等點間斷地連結和更換 IP 位址 例如 :P2P 檔案傳輸 很高的擴張性但是難以管理 end system 點對點 end system 圖 2.2(b) 點對點架構 2.9 / 103

107 2.1.1 網路應用程式架構 (Cont.) 點對點架構 (Cont.) P2P 應用面臨的挑戰 (p. 2-5) 對 ISP 友善 ISP 提供的上傳與下載頻寬一般都不一致 (why?), 然而,P2P 應用的上傳與下載一般都是同等對待 安全性 P2P 應用有高度分散與開放的本質, 故比 clientserver 架構更有安全性的問題 誘因 如何說服 P2P 使用者願意貢獻其頻寬 儲存空間及運算資源給 P2P 應用程式使用 2.10 / 103

108 2.1.1 網路應用程式架構 (Cont.) 用戶端 伺服端和點對點二者混合式的架構 網際網路電話 P2P 網路電話的應用 中介伺服器 : 找到遠端連線位址的部份 用戶端 用戶端的連接 : 直接的 ( 不通過伺服器 ) See Sect 即時訊息 (MSN/LINE) 兩個使用者的交談是點對點的 存在的偵測 / 尋找是中央式的 當使用者上線時, 會將它的 IP 位址跟中央伺服器註冊 使用者與中央伺服器連繫以取得好友的 IP 位址 2.11 / 103 Ex 2.1

109 2.1.2 行程通訊 (process communicating) 行程 在主機內執行的程式 ( 執行中的程式 ) 在同一個主機中, 兩個行程以行程內通訊機制來互相通訊 ( 被作業系統管制 ) 在不同的主機間, 行程透過交換訊息來通訊 用戶端行程 vs. 伺服端行程 用戶端行程 : 啟動通訊的行程 主動 伺服端行程 : 等待被連接的行程 被動 在點對點架構中, 應用程式擁有用戶端行程以及伺服端行程 2.12 / 103

110 2.1.2 行程通訊 (Cont.) Sockets ( 門 / 插槽 / 插座 ) 行程傳送 / 接收訊息給 / 從它的 socket socket 好比是 門 傳送端行程將訊息推出它的門 傳送端行程依靠門另一端的運輸架構, 將訊息帶到接收端行程的 socket 主機或伺服器 主機或伺服器 行程 由應用程式開發者控制 行程 socket socket 由作業系統控制 擁有緩衝區和各種變數的 TCP Internet 擁有緩衝區和各種變數的 TCP 圖 2.3 應用程式 socket 及底層的傳輸協定的關係 Ex / 103

111 2.1.2 行程通訊 (Cont.) 行程定址 接收到信息, 此過程需要經過識別 一台主機有一個唯一的 32 位元 IP 位址 (IPv4) Q: 在行程執行的主機上,IP 位址足夠用來識別行程嗎? 主機或伺服器 行程 1? socket 行程 2 擁有緩衝區和各種變數的 TCP message 2.14 / 103

112 2.1.2 行程通訊 (Cont.) 行程定址 (Cont.) Q: 在行程執行的主機上,IP 位址足夠用來識別行程嗎? A: 不行, 可能有許多行程在同一台主機上執行 主機或伺服器 行程 1? socket 行程 2 擁有緩衝區和各種變數的 TCP message 2.15 / 103

113 2.1.2 行程通訊 (Cont.) 行程定址 (Cont.) 識別碼包含了 IP 位址以及埠號 (port number), 後者屬於主機上的行程 埠號的範例 : HTTP 伺服器 :80 Mail 伺服器 :25 寄送 HTTP 信息到 網頁伺服器 : IP 位址 : Port 數 :80 public port number of application: 行程 1 port 80 行程 2 port 25 socket 擁有緩衝區和各種變數的 TCP HTTP message Ex / 103

114 2.1.2 行程通訊 (Cont.) Socket 再論 一台伺服主機執行多個伺服程式 socket ports server clients 2.17 / 103

115 2.1.2 行程通訊 (Cont.) Socket 再論 (Cont.) Socket( 門 / 插座 ) 可由一個 IP 位址和一個埠號 (port number) 所組成 一組行程使用一對插座 ( 雙方各一個 ) 在網路上通訊 2.18 / 103

116 2.1.3 應用程式可使用的傳輸服務 應用層協定的定義 (ref. 圖 2.8) 所交換訊息的類型 例如 : 請求訊息和回應訊息 各種訊息類型的語法 : 例如 : 訊息中的欄位以及如何描述這些欄位 訊息的語義 意指欄位內的資訊所代表的意義 決定行程何時傳送訊息和回應訊息, 以及如何傳送訊息和回應訊息的規則 公眾領域的協定 : 定義在 RFC 中 允許可互通性 例如 :HTTP SMTP 私有的協定 : 例如 : 網際網路電話 (Skype) 有些私有的協定, 在普遍後也可能變成公眾領域的協定 2.19 / 103

117 2.1.3 應用程式可使用的傳輸服務 (Cont.) 應用程式需要哪些傳輸服務? 傳輸層協定能夠提供哪些服務給呼叫它的應用程式? 資料遺失 (reliable data transfer) 某些應用程式 ( 例如 : 語音 ) 可以忍受一些遺失 其它的應用程式 ( 例如 : 檔案傳輸 遠端終端機存取 ) 要求 100% 可靠的資料傳輸 時序 (timing) 某些應用程式 ( 例如 : 網際網路電話 互動遊戲 ) 需要低的延遲以確保效能 頻寬 (bandwidth) 應用層傳輸層網路層連結層實體層 某些應用程式 ( 例如 : 多媒體 ) 有最小頻寬的需求以確保其效能 其它的應用程式 ( 彈性使用的應用程式 ) 使用它們可以取得的任何頻寬 2.20 / 103

118 2.1.3 應用程式可使用的傳輸服務 (Cont.) 常見網路應用程式的傳輸服務需求 網路應用 資料遺失 頻寬 對時序的敏感性 檔案傳輸電子郵件網頁文件網路電話視訊會議預儲影音互動遊戲即時訊息 不容忍遺失不容忍遺失不容忍遺失可容忍遺失 可容忍遺失可容忍遺失不容忍遺失 彈性使用彈性使用彈性使用音訊 : 數 Kbps ~ 1 Mbps 視訊 : 10 Kbps ~5 Mbps 同上幾 Kbps ~ 10Kbps 彈性使用 無無無有, 數百毫秒 (ms) 有, 幾秒鐘有, 數百毫秒可有可無 圖 2.4 某些網路應用的需求 2.21 / 103

119 2.1.4 網際網路傳輸層協定的服務 TCP 服務 連線導向服務在用戶端和伺服端行程之間需要準備設定 可靠的傳輸服務在傳送端和接收端行程之間 流量控制傳送端傳輸資料量不會超過接收端可接收的資料量 壅塞控制當超過負荷時, 將傳送端減速 沒有提供時序 最小頻寬的保證 UDP 服務 傳送端和接收端行程之間不可靠的資料傳輸 不提供 : 連接設定 可靠性 流量控制 時序 或頻寬保證 Q: 為何會有 UDP? 當網路應用不需要可靠的資料傳輸時, 採用此種協定服務將不需作 handshaking, 如此可加速資料傳輸的速度及減少網路資料流量 2.22 / 103

120 2.1.4 網際網路傳輸層協定的服務 (Cont.) 網際網路應用 : 應用程式 vs. 其下之傳輸層協定 網路應用 電子郵件遠端終端機存取網頁檔案傳輸串流多媒體 網際網路電話 應用層協定 SMTP [RFC 2821] Telnet [RFC 854] HTTP [RFC 2616] FTP [RFC 959] HTTP ( 例如 YouTube) RTP 通常是私有協定 ( 例如 Skype) 底層傳輸層協定 TCP TCP TCP TCP TCP 或 UDP 一般是 UDP 圖 2.5 某些網路應用 它們的應用層協定 及其使用的底層傳輸層協定 Exercise 2.2 Exercise 2.1 Ex / 103

121 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.24 / 103

122 2.2 Web( 網頁 ) 和 HTTP 基本術語 (terminology) WWW Word Wide Web ( 全球資訊網 ) 網頁 (web page) 由物件 (objects) 所組成 物件可能是 HTML 檔案 JPEG 影像 Java applet 聲音檔... 網頁由基本的 HTML 檔案和數個參考物件所組成 每個物件由一個 URL (uniform resource locator) 來定址 範例 URL:( 注意其分隔符號 / ) 主機名稱 路徑名稱 2.25 / 103

123 2.2.1 HTTP 概觀 HTTP 超文件傳輸協定 (hypertext transfer protocol) Web 的應用層協定 用戶端 / 伺服端模型 用戶端 : 瀏覽器, 用來請求 接收及 顯示 Web 物件 伺服端 : Web 伺服器, 依請求回應並傳送物件 HTTP 1.0:RFC 1945 HTTP 1.1:RFC 2068 執行 Internet Explorer 的 Windows 電腦 What is hypertext? 執行 Firefox 的 Linux 電腦 執行 Apache 的 Web 伺服器 圖 2.6 HTTP 的請求 - 回應行為 2.26 / 103

124 2.2.1 HTTP 概觀 (Cont.) 使用 TCP: 用戶端先建立與伺服端的 TCP 連線 ( 產生 socket),port 80 伺服端接受來自用戶端的 TCP 連線 HTTP 訊息 ( 應用層協定訊息 ) 在瀏覽器 (HTTP 用戶端 ) 和 Web 伺服器 (HTTP 伺服端 ) 之間交換 TCP 連線結束 HTTP 是 無狀態的協定 (stateless protocol) HTTP 伺服端不會儲存 / 維護用戶端過去的請求資訊 2.27 / 103

125 2.2.2 HTTP 連線 HTTP 連線方式 非永久性 HTTP 一個 TCP 連線上最多傳送一個物件 HTTP/1.0 使用非永久性 HTTP 永久性 HTTP three-way handshake Hung1 在客戶端和伺服端之間的單一 TCP 連線上, 可以傳送多個物件 HTTP/1.1 預設使用永久性連線 2.28 / 103

126 投影片 28 Hung1 TCP uses a three-way handshake to open a connection: (1) ACTIVE OPEN: Client sends a segment with SYN bit set * port number of client initial sequence number (ISN) of client (2) PASSIVE OPEN: Server responds with a segment with SYN bit set * initial sequence number of server ACK for ISN of client (3) Client acknowledges by sending a segment with: ACK ISN of server Ruo-Wei Hung, 2013/8/29

127 2.2.2 HTTP 連線 (Cont.) 非永久性 HTTP: 用戶端瀏覽程式輸入 ( 內含 10 個.jpg 物件 ) client server 1a. HTTP 用戶端利用埠號 80 建立與 伺服器的 TCP 連線 2. HTTP 用戶端透過 TCP 連線的 socket, 傳送一個 HTTP 請求訊息給伺服器 這個訊息指出用互端需要物件檔案 /~rwhung/index.htm 5. HTTP 用戶端收到回應訊息, 其中包含 html 檔, 顯示 html 解析 html 檔, 找到 10 個參考的 jpeg 物件 1b. 位於 的 HTTP 伺服器主機等待埠號 80 的 TCP 連線 接受 連線並通知用戶端 3. HTTP 伺服器收到請求訊息, 產生回應訊息, 內含所請求的物件, 並將此訊息送到它的 socket 4. HTTP 伺服器關閉 TCP 連線 6. 對 10 個 jpeg 物件, 每個都重複步驟 / 103

128 2.2.2 HTTP 連線 (Cont.) 回應時間模型 : RTT (round-trip time, 來回時間 ) 的定義 : 一個小封包由用戶端傳送到伺服端, 然後再回來所經歷的時間 回應時間 : 一個 RTT: 初始化 TCP 連線 ( 建立 sender 與 receiver 間的 " 管子 ") 一個 RTT:HTTP 請求以及回傳的 HTTP 回應訊息的前幾個位元組 檔案傳輸時間 總計 = 2RTT+ 檔案傳輸時間 client server 建立 TCP 連線 RTT 請求 RTT 接收到檔案 回應傳送檔案所耗費的時間 時間 時間 圖 2.7 請求 / 接收 HTML 檔案所需時間的簡單計算 Exercise / 103

129 同一個 TCP 連線可傳送多個物件 HTTP 連線 (Cont.) 永久性 HTTP: 非永久性 HTTP 問題 每個物件都需要 2 個 RTT 每個 TCP 連線都造成 OS( 作業系統 ) 的額外負擔 瀏覽器通常會開啟平行的 TCP 連線以取得參考物件 永久性 HTTP 在傳送回應之後, 伺服器會持續保留該條連線 在相同的用戶端 / 伺服端之間, 後續的 HTTP 訊息會經由此 開啟的連線傳送 類別 無管線的永久性 :» 每個參考物件需要一個 RTT 管線化的永久性 :» 所有的參考物件可能只需要一次 RTT client 建立連線 server» 不需等待尚未處理完的請求得到回應, 而送出下一個物件» HTTP/1.1 的預設模式 Ex / 103

130 2.2.3 HTTP 訊息格式 兩種 HTTP 訊息 請求 (request message) 回應 (response message) ASCII ( 人類可閱讀的格式 ) 2.32 / 103

131 2.2.3 HTTP 訊息格式 (Cont.) HTTP 請求訊息 : 請求列 (GET, POST, HEAD 命令 ) 標頭列 GET /~rwhung/index.htm HTTP/1.1 Host: User-agent: Mozilla/4.0 Connection: close Accept-language:fr 非永久性連線 歸位 + 換行 (cr+lf) 表示訊息的尾端 (extra carriage return, line feed) 2.33 / 103

132 2.2.3 HTTP 訊息格式 (Cont.) HTTP 請求訊息 : 一般格式 Hung2 圖 2.8 HTTP 請求訊息的一般格式 2.34 / 103

133 投影片 34 Hung2 sp = space cr = carriage return lf = line feed Ruo-Wei Hung, 2013/8/29

134 2.2.3 HTTP 訊息格式 (Cont.) HTTP 請求訊息 (Cont.) 上傳表單 GET POST 資料主體為 輸入表單的資料 資料主體為空 2.35 / 103

135 2.2.3 HTTP 訊息格式 (Cont.) HTTP 回應訊息 : 狀態列 ( 協定狀態碼狀態訊息 ) 資料, 例如, 請求的 HTML 檔案 標頭列 HTTP/ OK Connection close Date: Thu, 06 Aug :00:15 GMT Server: Apache/1.3.0 (Unix) Last-Modified: Mon, 22 Jun Content-Length: 6821 Content-Type: text/html data data data data data / 103

136 2.2.3 HTTP 訊息格式 (Cont.) HTTP 回應訊息 :(Cont.) HTTP 回應狀態碼 ( 伺服端 用戶端回應訊息的第一行 ) 幾個狀態碼的例子 : 200 OK 請求成功, 請求的物件包含在此訊息的後方 301 Moved Permanently 請求的物件已經搬移 ; 新的位置指定在此訊息的後方 (Location:) 400 Bad Request 伺服器無法了解請求訊息 404 Not Found 請求的文件不存在於該伺服器 505 HTTP Version Not Supported 2.37 / 103

137 2.2.3 HTTP 訊息格式 (Cont.) Hung3 自己試驗 HTTP ( 用戶端 ): Telnet 登入你喜歡的 Web 伺服器 : telnet cis.poly.edu 80 輸入一個 GET HTTP 請求 : GET /~ross/ HTTP/1.1 Host: cis.poly.edu 觀察 HTTP 伺服器傳送的回應訊息! 藉著輸入這個訊息 ( 按下歸位鍵兩次 ) 你傳送了這個最小的 ( 但卻是完整的 ) GET 請求到 HTTP 伺服器 2.38 / 103

138 投影片 38 Hung3 Windows 7 使用 telnet: (1) 控制台 (2) 程式集 (3) 解除安裝程式 (4) 點選左側 " 開啟 or 關閉 Windows 功能 " (5) 對 "Telnet 用戶端 " 打勾 ==> " 命令提示字元 " 視窗程式即可輸入 "telnet" 指令 Ruo-Wei Hung, 2013/8/29

139 2.2.4 使用者與伺服器的互動 :cookies Cookies HTTP 伺服器 無狀態的 = 不用記錄使用者的存取資訊 網頁伺服器如何辨識不同使用者? HTTP 的 cookie RFC 2965 讓網站能夠追蹤使用者, 以限制使用者的存取 Cookie 技術的四項元素 : HTTP 回應訊息的 cookie 標頭列 HTTP 請求訊息的 cookie 標頭列 保留於使用者終端系統上的一份 cookie 檔案, 並且由使用者瀏覽器管理 Web 網站的後端資料庫 (back-end database) 2.39 / 103

140 2.2.4 Cookies (Cont.) Cookie 範例 : Royce 都是使用同一台 PC 來存取網際網路 第一次拜訪某個電子商務網站 當初始的 HTTP 請求到達網站時, 電子商務網站會產生 : 唯一的識別號碼 後端資料庫上為此識別碼建立一筆紀錄 2.40 / 103

141 2.2.4 Cookies (Cont.) Cookie 範例 :(Cont.) 電子商務網站儲存 狀態 client amazon server cookie 檔 ebay 8734 伺服器為使用者建立 ID 1678 ebay 8734 amazon 1678 一週後 : ebay 8734 amazon 1678 特定 Cookie 才能進行的動作 特定 Cookie 才能進行的動作 後端資料庫 圖 2.10 利用 cookie 保存使用者狀態 2.41 / 103

142 2.2.4 Cookies (Cont.) cookies 能做什麼? 授權 購物車 推薦 使用者會談狀態 (web ) 2.42 / 103 Ex 2.6

143 2.2.5 網頁快取 : 代理伺服器 (proxy) 目標 滿足用戶端的請求, 且不牽涉到來源伺服器 設定 / 使用 proxy 使用者設定瀏覽器 :Web 經由快取伺服器存取 瀏覽器傳送所有的 HTTP 請求到快取伺服器 在快取伺服器中的物件 : 快取伺服器會回傳物件 否則, 快取伺服器會向來源伺服器請求物件, 接著將物件回傳給用戶端 用戶端 代理伺服器 來源伺服器 用戶端 圖 2.11 透過 proxy 請求物件 2.43 / 103

144 2.2.5 Proxy (Cont.) 網頁快取 (Cont.) 快取伺服器同時扮演了用戶端和伺服端的角色 通常 ISP 會安裝快取伺服器 ( 大學 公司 家用型 ISP) 為什麼要使用 Web 快取? 降低用戶端發出請求後的回應時間 減少機構連結到網際網路的流量 具有高密度快取伺服器的網際網路可使得 差的 節目提供者能夠有效率地提供節目 ( 而 P2P 分享也是一樣 ) Ex / 103

145 2.2.5 Proxy (Cont.) 網頁的範例 假設 平均物件大小 = 1M bits 機構的瀏覽器到來源伺服器的平均請求速率 = 15 Objs/sec 從機構的路由器到任何來源伺服器再回來的延遲時間 = 2 sec 結果 LAN 的利用率 ( 流量強度, see 圖 1.18) = (15 Objs/sec) (1M bits/obj) / (100 Mbps) = 15% 存取連結的利用率 ( 流量強度 ) = (15 Objs/sec) (1Mbits/Obj) / (15 Mbps) = 100% 全部的延遲 = 網際網路延遲 + 存取延遲 + LAN 延遲 = 2 秒 + 幾分鐘 + 幾毫秒 公用網際網路 機構網路 來源伺服器 15 Mbps 存取連結 100 Mbps LAN 圖 2.12 機構網路與網際網路間的頻頸 2.45 / 103

146 2.2.5 Proxy (Cont.) 網頁的範例 (Cont.) 可能的解決方案 增加存取連結的頻寬, 比如說 100 Mbps 結果 LAN 的利用率 = 15% 存取連結的利用率 = 15% 全部的延遲 來源伺服器 = 網際網路延遲 + 存取延遲 + LAN 延遲 = 2 秒 + 數毫秒 + 數毫秒 升級通常是相當昂貴的 公用網際網路 機構網路 100 Mbps 存取連結 100 Mbps LAN 2.46 / 103 圖 2.12 機構網路與網際網路間的頻頸

147 2.2.5 Proxy (Cont.) 網頁的範例 (Cont.) 可能的解決方案 (Cont.) 安裝快取伺服器 ( 假設命中率為 0.4) 結果 40% 的請求會被立即滿足 60% 的請求被來源伺服器滿足 存取連結的利用率減為 60%, 變成幾乎可以忽略的延遲 ( 比如說 10 毫秒 = 0.01 秒 ) 總計的平均延遲 = 網際網路延遲 + 存取延遲 + LAN 延遲 = 0.6*(2.01) 秒 + 0.4* 毫秒 < 1.4 秒 公用網際網路 機構網路 來源伺服器 15 Mbps 存取連結 100 Mbps LAN 機構快取 圖 2.12 機構網路與網際網路間的頻頸 Ex / 103

148 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點檔案分享 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.48 / 103

149 2.3 FTP FTP (File Transfer Protocol) 檔案傳輸協定 傳輸檔案到 / 從遠端主機 ( 上傳 / 下載 ) 用戶端 / 伺服端模型 用戶端 : 開始傳輸的那一邊 ( 不管是到 / 從遠端 ) 伺服端 : 遠端主機 ftp:rfc 959 ftp 伺服器 : 埠號 21 FTP 使用者介面 FTP 用戶端 檔案傳輸 FTP 伺服端 使用者或主機 本地端檔案系統 遠端檔案系統 圖 2.14 FTP 會在本地端與遠端檔案系統間搬移檔案 2.49 / 103

150 2.3 FTP FTP 運作原理 分離的控制 資料連結 FTP 用戶端以埠號 21 聯繫 FTP 伺服端, 指定 TCP 為傳輸協定 用戶端經由控制連線取得授權 用互端經由控制連線傳送命令來瀏覽遠端目錄 當伺服器收到檔案傳輸的命令時, 伺服器會為用戶端開啟兩個 TCP 的資料連線 在傳輸一個檔案之後, 伺服器會關閉該連線 伺服端開啟第二個 TCP 資料連線以傳送另一個檔案 控制連線 : 頻帶外 (out-of-band) FTP 伺服器會維護 狀態 : 目前的目錄 之前的授權 TCP 控制連線的埠號為 21 FTP 用戶端 TCP 資料連線的埠號為 20 FTP 伺服端 圖 2.15 FTP 的控制與資料連線 2.50 / 103

151 2.3 FTP FTP 指令 回覆 範例命令 ( 經由控制連結頻道, 以 ASCII 文字傳送 ) USER username PASS password LIST 回傳目前目錄下的檔案清單 RETR filename 取得 ( 意指 get) 檔案 STOR filename 將檔案儲存 ( 意指 put) 到遠端主機 範例回覆碼 ( 狀態碼和資料 ( 類似 HTTP)) 331 使用者名稱 ok, 需要密碼 125 確定資料連結已經打開 ; 轉換開始 425 資料連結無法打開 452 錯誤訊息寫入檔案 2.51 / 103

152 2.3 FTP FTP 指令 回覆 (Cont.) >ftp ftp.isu.edu.tw > 帳號 = ftp Ex / 103

153 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.53 / 103

154 2.4 電子郵件系統的三個主要元件 使用者代理程式 (user agents) 郵件伺服器 (mail servers) 簡單郵件傳輸協定 :SMTP (Simple Mail Transfer Protocol) 使用者代理程式 郵件伺服器 SMTP 郵件伺服器 使用者代理程式 正在寄送的訊息佇列 使用者郵件信箱 SMTP 使用者代理程式 使用者代理程式 郵件伺服器 SMTP 使用者代理程式 使用者代理程式 圖 2.16 網際網路電子郵件系統的三個主要元件 2.54 / 103

155 2.4 (Cont.) 電子郵件三個主要元件 (Cont.) 使用者代理程式 (user agents) 又稱 郵件檢示器 (mail reader) 撰寫 編輯 讀取郵件訊息 例如 : Eudora Outlook elm Netscape Messenger 寄送 收取伺服器上的訊息 2.55 / 103

156 2.4 (Cont.) 電子郵件三個主要元件 (Cont.) 郵件伺服器 (mail servers) 郵件信箱 (mail box) 保存了使用者收到的信件 訊息佇列 (message queue) 內含要出去的 ( 將要寄出的 ) 郵件訊息 SMTP 協定在郵件伺服器之間傳送電子郵件訊息 用戶端 : 傳送電子郵件的伺服器 伺服端 : 接收電子郵件的伺服器 郵件伺服器 正在寄送的訊息佇列使用者郵件信箱 SMTP SMTP 郵件伺服器 郵件伺服器 SMTP 2.56 / 103

157 2.4 (Cont.) 電子郵件三個主要元件 (Cont.) 簡單郵件傳輸協定 :SMTP (Simple Mail Transfer Protocol) 定義在 RFC 2821 使用 TCP, 埠號 25, 從用戶端到伺服端可靠地傳輸電子郵件訊息 直接傳輸 : 從傳送伺服器到接收伺服器 ( 不會使用中介伺服器來傳送郵件 ) 傳輸的三個階段 交握 (handshake, 自我介紹 ) 傳送訊息 關閉 指令 / 回應的互動 指令 :ASCII 文字 回應 : 狀態碼和資訊 訊息必須是 7 個位元的 ASCII 碼 Ex / 103

158 2.4 (Cont.) 傳送電子郵件範例 情境 Alice 傳送電子郵件給 Bob 過程 Alice 執行使用者代理程式, 編寫一份訊息寄給 Alice 的使用者代理程式傳送訊息到她的郵件伺服器, 此訊息被放置在訊息佇列中 Client side of SMTP 用戶端開啟 TCP 連線, 連結到 Bob 的郵件伺服器 SMTP 透過 TCP 連線傳送 Alice 的訊息 Bob 的郵件伺服器將訊息放置在 Bob 的郵件信箱中 Bob 執行他的使用者代理器來閱讀訊息 msa.hinet.net mail.cyut.edu.tw Alice 使用者代理程式 1 郵件伺服器 2 3 郵件伺服器 4 使用者代理程式 5 6 Bob 圖 2.17 Alice 傳送一封電子信件給 Bob 的過程 2.58 / 103

159 2.4 (Cont.) SMTP 互動範例 SMTP 客戶端 (Client) 與 SMTP 伺服端 (Server) 之間訊息交換記錄 S: 220 cyut.edu.tw C: HELO msa.hinet.net S: 250 Hello msa.hinet.net, pleased to meet you C: MAIL FROM: > S: 250 Sender ok C: RCPT TO: > S: 250 Recipient ok C: DATA S: 354 Enter mail, end with "." on a line by itself C: Do you like ketchup? C: How about pickles? C:. S: 250 Message accepted for delivery C: QUIT S: 221 cyut.edu.tw closing connection 2.59 / 103

160 2.4 (Cont.) SMTP 結語 SMTP 使用永久性連線 SMTP 要求訊息 ( 標頭及主體 ) 必須是 7 位元的 ASCII 格式 SMTP 伺服器用 CRLF.CRLF 來決定訊息的尾端 與 HTTP 的比較 : HTTP: 取回 (pull) SMTP: 送出 (push) 都有 ASCII 指令 / 回應的互動 狀態碼 HTTP: 每個物件都封裝在它自己的回應訊息中 SMTP: 多個物件以一個多重訊息來傳送 2.60 / 103

161 2.4.3 郵件訊息格式與 MIME 郵件訊息格式 SMTP: 交換郵件訊息的協定 RFC 822 文字訊息的格式標準 : 標頭檔連結, 例如 : 本體 To: From: Subject: 與 SMTP 命令不同! 訊息, 僅 ASCII 字元 header body 空白行 2.61 / 103

162 2.4.3 郵件訊息格式與 MIME (Cont.) 郵件訊息格式 多媒體延伸 MIME: multipurpose internet mail extensions, multimedia mail extension, RFC 2045, 2056 訊息標頭中額外的文字列宣告了 MIME 的 content type MIME 的版本 將資料編碼所使用的方法 多媒體資料型態 子型態 參數宣告 編碼後的資料 From: To: Subject: Picture of yummy crepe. MIME-Version: 1.0 Content-Transfer-Encoding: base64 Content-Type: image/jpeg base64 encoded data base64 encoded data 2.62 / 103

163 2.4.4 郵件存取協定 (Mail access protocol) 郵件傳輸系統協定 SMTP: 傳送 / 儲存到接收端的郵件伺服器 郵件存取協定 : 從伺服器取得電子郵件 POP: Post Office Protocol [RFC 1939] 授權階段 ( 代理器 伺服器 ) 與存取程序階段 IMAP: Internet Mail Access Protocol [RFC 1730] 更多功能 ( 更複雜 ) 在伺服器上操作儲存的訊息 (Webmail) 使用者代理程式 HTTP: Hotmail Yahoo! Mail 等等 SMTP SMTP 存取協定 POP3/IMAP/ HTTP 使用者代理程式 傳送端的郵件伺服器 接收端的郵件伺服器 圖 2.18 電子郵件協定與它們的通訊實體 2.63 / 103

164 2.4.4 郵件存取協定 (Cont.) 郵件存取協定 POP3: Post Office Protocol ver. 3 [RFC 1939] 授權階段 用戶端指令 :» user: 宣告使用者名稱» pass: 密碼 伺服器回應» +OK» -ERR 存取程序階段 ( 用戶端 ) list: 將訊息編號列表 retr: 以編號收取訊息 dele: 刪除 quit S: +OK POP3 server ready C: user bob S: +OK C: pass hungry S: +OK user successfully logged on C: list S: S: S:. C: retr 1 S: <message 1 contents> S:. C: dele 1 C: retr 2 S: <message 1 contents> S:. C: dele 2 C: quit S: +OK POP3 server signing off 2.64 / 103

165 2.4.4 郵件存取協定 (Cont.) 郵件存取協定 (Cont.) POP3 (Cont.) 下載並刪除 模式 假如 Bob 更換了用戶端, 他將無法重新讀取郵件 ( 下載郵件並從 mail server 上刪除此郵件 ) 下載並保留 模式 在不同的用戶端保留副本 ( 下載郵件但不從 mail server 上刪除此郵件 ) 在會談期間,POP3 為無狀態的 (mail server 不會保有使用者的狀態資訊 ) 不允許使用者在 mail server 上建立資料夾 IMAP 較 POP3 複雜及功能更強 允許使用者在 mail server 上建立郵件資料夾 使用者可於所建立的郵件資料夾間搬移電子郵件 在會談期間,IMAP server 會保有使用者的狀態資訊 (eg. 郵件資料夾名稱 / 哪筆訊息屬於哪個資料夾 ) 2.65 / 103

166 2.4.4 郵件存取協定 (Cont.) 郵件存取協定 (Cont.) HTTP Web mail 2.66 / 103

167 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.67 / 103

168 2.5 DNS (Domain Name System) DNS (Domain Name System): 網域 ( 領域 ) 名稱系統 What? 人類 : 擁有許多識別碼來辨識身份 身份證號碼 名字 護照號碼 網際網路主機 路由器 : IP 位址 (32 位元, IPv4) 使用位址資料段 機器所使用的 領域名稱 例如,ww.cyut.edu.tw 人類所使用的 Q: IP 位址以及領域名稱之間的對應? (eg ?) A: 領域名稱系統 轉換領域名稱成 IP 位址的系統 2.68 / 103

169 2.5 DNS (Domain Name System) DNS 網域名稱系統 (Cont.) 基礎 Hung4 分散式的資料庫 (distributed database) 以許多階層式的 DNS 伺服器 (name servers) 實作 應用層協定 (application layer) 允許主機 路由器 DNS 伺服器連接, 以解析 (resolve) 網域名稱 ( 網域名稱 IP 位址的轉換 ) DNS 是讓主機可以查詢此分散式資料庫的應用層協定 2.69 / 103

170 投影片 69 Hung4 分散式 : 非由一台電腦完成解譯, 而是由多台 DNS 伺服器共同完成一解譯工作 Ruo-Wei Hung, 2013/8/29

171 2.5.1 DNS 服務 DNS 所提供的服務 基本服務 主機 ( 網域 ) 名稱到 IP 位址的轉換 額外服務 主機別名 (host aliasing) 正規主機名稱 vs. 別名 正規主機名稱 = 別名 = cyut university of technology 應用程式可以呼叫 DNS, 提供別名, 以取得正規主機名稱 /IP 位址 郵件伺服器別名 (CYUT mail server: cyut.edu.tw = mail.cyut.edu.tw) 負載分配 (load distribution) 複製的 Web 伺服器 : 一組 IP 位址對應到一個正規主機名稱 忙碌的網站 / st query nd query / 103

172 2.5.2 DNS 的運作 DNS 的運作 集中化的 DNS 只用一台 DNS 伺服器 DNS table ( 兩欄位 = domain name, IP address) 問題 : 單點故障 大量的網路流量 遠距離集中式資料庫 維護 集中化的 DNS 不具擴充性! 分散式 階層式 DNS 資料庫 目前網際網路所採用 沒有任何單一的 DNS 伺服器擁有網際網路上所有主機的對映資訊 解析網域名稱時, 需透過多台 DNS 伺服器合作, 才可完成 domain name 意義 主機服務類別 機構名稱 國名 2.71 / 103 機構屬性

173 2.5.2 DNS 的運作 (Cont.) DNS 的運作 分散式 階層式 DNS 資料庫 階層式 DNS 伺服器類別 根 (root) 名稱伺服器 高層網域 DNS (TLD) 伺服器 (Top Level Domain) 官方 DNS 伺服器 根 DNS 伺服器 com DNS 伺服器 org DNS 伺服器 edu DNS 伺服器 yahoo.com DNS 伺服器 amazon.com DNS 伺服器 pbs.org DNS 伺服器 poly.edu DNS 伺服器 umass.edu DNS 伺服器 圖 2.19 部份的 DNS 伺服器階層架構 2.72 / 103

174 2.5.2 DNS 的運作 (Cont.) DNS 的運作 分散式 階層式 DNS 資料庫 (Cont.) 用戶端想要知道 的 IP 位址 用戶端向根伺服器查詢, 尋找 com DNS 伺服器 (IP 位址 ) 用戶端向 com DNS 伺服器查詢, 得到 amazon.com DNS 伺服器 用戶端向 amazon.com DNS 伺服器查詢, 得到 的 IP 位址 Ex / 103

175 2.5.2 DNS 的運作 (Cont.) DNS 的運作 分散式 階層式 DNS 資料庫 (Cont.) DNS: 根名稱伺服器 全世界共有 13 個名稱伺服器 e NASA Mt View, CA f Internet Software C. Palo Alto, CA (and 36 other locations) a Verisign, Dulles, VA c Cogent, Herndon, VA (also LA) d U Maryland College Park, MD g US DoD Vienna, VA h ARL Aberdeen, MD j Verisign, ( 21 locations) k RIPE London (also 16 other locations) i Autonomica, Stockholm (plus 28 other locations) m WIDE Tokyo (also Seoul, Paris, SF) b USC-ISI Marina del Rey, CA l ICANN Los Angeles, CA 圖 年的 DNS 根伺服器 ( 名稱, 組織, 地點 ) 2.74 / 103

176 2.5.2 DNS 的運作 (Cont.) DNS 的運作 分散式 階層式 DNS 資料庫 (Cont.) DNS: 高層網域 DNS (TLD) 伺服器 負責 com org net edu etc 以及全部的高層國家領域 uk fr ca jp cn hk tw Network solutions 公司負責維護 com TLD 的伺服器 Educause 公司負責 edu TLD DNS: 官方 DNS 伺服器 組織 / 公司內的 DNS 伺服器, 替組織內的伺服器提供管控的主機名稱到 IP 的對應 ( 例如,web 以及 mail) 可以是組織本身或服務業者來維護的 2.75 / 103

177 2.5.2 DNS 的運作 (Cont.) DNS 的運作 分散式 階層式 DNS 資料庫 (Cont.) DNS: 區域名稱伺服器 (local DNS server) 不全然屬於階層架構中 每個 ISP ( 家用型 ISP 公司 大學) 都有一個 也稱為 預設名稱伺服器 當主機做了一個 DNS 查詢, 此查詢會被傳送到它的區域 DNS 伺服器 如同代理伺服器 (proxy), 將查詢傳入階層架構中 2.76 / 103

178 2.5.2 DNS 的運作 (Cont.) DNS 名稱解析範例 情境 csie.cyut.edu.tw 的主機想要查詢 的 IP 位址 循環式查詢 (iterative query) 根 DNS 伺服器 區域 DNS 伺服器 dns.cyut.edu.tw TLD DNS 伺服器 官方 DNS 伺服器 dns.ccu.edu.tw 請求主機 csie.cyut.edu.tw 圖 2.21 各種 DNS 伺服器的互動 (iterative query) 2.77 / 103

179 2.5.2 DNS 的運作 (Cont.) DNS 名稱解析範例 (Cont.) 情境 csie.cyut.edu.tw 的主機想要查詢 的位址 (Cont.) 遞迴式查詢 (recursive query) 加重被聯繫的名稱伺服器的名稱解析負擔 區域 DNS 伺服器 dns.cyut.edu.tw 根 DNS 伺服器 TLD DNS 伺服器 官方 DNS 伺服器 dns.ccu.edu.tw 請求主機 csie.cyut.edu.tw 圖 2.22 DNS 伺服器的遞迴式查詢 (recursive query) 2.78 / Ex 2.12

180 2.5.2 DNS 的運作 (Cont.) 在 DNS 中新增紀錄 情境 新成立的公司 Royce Corp. Hung5 向註冊服務商註冊名稱 royce.com.tw ( 例如,HiNet) 需要提供該服務商你的 ( 主要及次要 ) 官方 DNS 伺服器的名稱與 IP 位址 服務商在 com TLD 伺服器中輸入兩筆 RR:» (royce.com.tw, dns.royce.com.tw, NS)» (dns.royce.com.tw, , A) 建立官方 DNS 伺服器中放入 Type A 的 紀錄以及 Type MX 的 royce.com 紀錄 人們要如何得到你的網站的 IP 位址呢? 2.79 / 103

181 投影片 79 Hung5 MX = Message exchange Mail transfer 必須為之 ( 設定 MX) Ruo-Wei Hung, 2013/8/29

182 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7 使用 TCP 的 Socket 程式設計 2.8 使用 UDP 的 Socket 程式設計 2.80 / 103

183 2.6.1 點對點檔案分享 (P2P File Sharing) Hung6 點對點檔案分享 (peer-to-peer file sharing) 範例情境 Alice 在她的筆記型電腦上執行對等式的用戶端應用程式 間歇地連接到網際網路, 每次連接都得到一個新的 IP 位址 (Dynamic) 尋找 Hey Jude 檔案 應用程式會顯示其它擁有 Hey Jude 的副本的對等點 Alice 選擇了其中一個對等點 Bob 檔案由 Bob 的電腦複製到 Alice 的筆記型電腦 :HTTP 當 Alice 從 Bob 下載檔案的同時, 可能有其他的使用者從 Alice 下載 Alice 的對等點同時是 Web 用戶端以及暫時的 Web 伺服端 所有的對等點都是伺服器 = 高擴充性! ( 圖 2.24) 2.81 / 103

184 投影片 81 Hung6 Peer: 同儕 / 對等點 Ruo-Wei Hung, 2013/8/29

185 2.6.1 點對點檔案分享 (P2P File Sharing) 點對點檔案分享 (Cont.) 範例情境 (Cont.) 伺服器 u s : 伺服器上傳的頻寬 u i : 第 i 個用戶端的上傳頻寬 d i : 第 i 個用戶端的下傳頻寬 u 1 u 2 d 1 d 2 檔案大小 F u s d N u N Network (with abundant bandwidth) 圖 2.24 P2P 檔案散佈 2.82 / 103

186 2.6.1 點對點檔案分享 (P2P File Sharing) 集中式 P2P 索引 當對等點連結時, 它會告知中央 ( 目錄 ) 伺服器 : IP 位址 ( 分享的 ) 內容 Alice 尋找 Hey Jude 檔案 Alice 向 Bob 請求檔案 (file transfer) 問題 集中式目錄伺服器 1 單點 ( 中央伺服器 ) 故障 效能瓶頸 ( 中央伺服器 ) 2 版權侵犯 : 訴訟 目標 是非常明顯的 檔案傳輸是非集中式的, 但內容尋找是高度的集中式 Bob 對等點 Alice 圖 2.a 集中式 P2P 索引 2.83 / 103

187 2.6.1 點對點檔案分享 (P2P File Sharing) 漫出式 P2P 查尋 (query flooding) 基本概念 完全分散式 非集中式伺服器 每個對等點都會對其提供分享的檔案建立索引 每個對等點不會對其它檔案建立索引 檔案傳輸 : HTTP 查詢 命中查詢 Bob Alice 查詢 命中查詢 圖 2.b 漫出查尋 2.84 / 103

188 2.6.1 點對點檔案分享 (P2P File Sharing) 階層式重疊 (hierarchical query) 基本概念 集中式索引與查詢漫出的整合 每個對等點為一個群組領導點或是被指定給一個群組領導點 群組領導點會追蹤它的子對等點的內容 Alice 1 A B Bob 圖 2.c 階層式重疊 Ex / 103

189 2.6.1 點對點檔案分享 (P2P File Sharing) 比較客戶端 伺服端與 P2P 架構 散佈時間 Minimum Distribution Time P2P Client-Server N 圖 2.25 P2P 架構與客戶端 伺服端架構的散佈時間比較 2.86 / 103

190 2.6.2 分散式雜湊表 (DHT) DHT DHT = distributed P2P database, distributed hash table P2P 資料庫的運作 資料庫欄位 = (key, value) pairs eg.key: 身份證號碼 ; value: 姓名 對等點使用 key 來對資料庫 (DB) 查尋, 而 DB 回應該 key 對應的 value Center database: 將 DB 放於一台電腦中 (what happen?) P2P database 將 (key, value) 配對分散在所有參與的對等點 (peer) 中 每個對等點都只會持有所有 (key, value) 配對的一小部份 對等點可查尋或插入 (key, value) 到此分散式對等資料庫中 查尋作法 : 循環式 DHT 2.87 / 103

191 2.6.2 DHT Circular DHT 給每個 peer 一個唯一識別碼 (id) P2P 資料庫中的對等點形成環狀 (ring) 每個對等點只知道前及後 (immediate successor and predecessor) 的對等點 圖 2.27(a) 環狀 DHT 2.88 / 103

192 2.6.2 DHT Circular DHT (Cont.) 對等點 3 查尋 key=1110 由哪一對等點所控制擁有? 0001 誰負責 key 1110? I am / 103

193 2.6.2 DHT Circular DHT with Shortcuts 對等點 3 查尋 key=1110 由哪一對等點所控制擁有? 1 3 誰負責 key 1110? 圖 2.27(b) 包含捷徑的環狀 DHT 2.90 / 103

194 2.6.3 網際網路電話 (Skype) Skype P2P (pc 到 pc pc 到話機 話機到 pc) Voice-Over-IP (VoIP) 應用 階層式重疊 Skype 用戶端 (SC) Skype 登入伺服器 SuperNode (SN) 2.91 / 103

195 2.6.2 Skype Skype: 打電話 開始使用 Skype SC 註冊到 SN SC 登入 Skype 伺服器 打電話 : SC 連接 SN 打給 ID SN 連接其他 SNs ( 未知協定 可能的漫出 ) 找到電話的位址 ; 回傳位址到 SC Skype 登入伺服器 SC 直接連接電話 經由 TCP Exercise 2.4 Ex / 103

196 第二章導覽流程 2.1 網路應用的原理 2.2 Web 和 HTTP 2.3 FTP 2.4 電子郵件 SMTP POP3 IMAP 2.5 DNS 2.6 點對點應用 2.7/2.8 使用 TCP/UDP 的 Socket 程式設計 2.93 / 103

197 2.7/2.8 Socket Programming with TCP/UDP Socket 程式設計 socket 在應用程式行程與端點至端點傳輸協定 (UCP 或 TCP) 之間的門 ( 插槽 ) 可以同時傳送及接收 訊息到 / 從另一個應用程式的行程 Socket API (application program interface) 在 BSD4.1 UNIX,1981 被介紹 (vs. Windows socket) 由應用程式明顯地製造 使用 發佈 用戶端 / 伺服端模式 兩種型態的傳輸服務透過 socket API: 可靠的, 位元組串流導向 (TCP) 不可靠的資料段 (UDP) 應用層傳輸層網路層連結層實體層 主機或伺服器 行程 socket 擁有緩衝區和各種變數的 TCP 2.94 / 103

198 2.7/2.8 Socket Programming with TCP/UDP (Cont.) 使用 TCP 的 Socket 程式設計 TCP 服務 : 使用位元組的可靠傳輸, 從一個行程到另一個行程 由應用程式開發者所控制 行程 socket 行程 socket 由應用程式開發者所控制 由作業系統所控制 擁有緩衝區和變數的 TCP 網際網路 擁有緩衝區和變數的 TCP 由作業系統所控制 主機或伺服器 主機或伺服器 圖 2.28 透過 TCP socket 的行程通訊 2.95 / 103

199 2.7/2.8 Socket Programming with TCP/UDP (Cont.) 使用 TCP 的 Socket 程式設計 (Cont.) 用戶端 / 伺服端 socket 的互動 : TCP 伺服端 ( 在 hostid 中執行 ) 為即將來到的請求建立 Socket port = x welcomesocket = ServerSocket() 用戶端 等待連線請求到來 connectionsocket = welcomesocket.accept() 由 connectionsocket 讀取請求 TCP 建立連線 建立連線到 Hostid,port=x 的 socket clientsocket = Socket() 使用 clientsocket 傳送請求 寫入回應至 connectionsocket 從 clientsocket 讀取回應關閉 connectionsocket 關閉 clientsocket 圖 2.30 透過 TCP socket 的行程通訊過程 2.96 / 103 Ex 2.15

200 2.7/2.8 Socket Programming with TCP/UDP (Cont.) 使用 UDP 的 Socket 程式設計 (Cont.) 用戶端 / 伺服端 socket 的互動 : UDP 伺服端 ( 在 hostid 中執行 ) 為即將到來的請求建立 port=x, serversocket = DatagramSocket() 由 serversocket 讀取請求 用戶端 建立 socket, clientsocket = DatagramSocket() 建立位址 (hostid, port=x) 使用 clientsocket 傳送資料段請求 寫入回應至 serversocket 指定用戶端主機位址及埠號 從 clientsocket 讀取回應 關閉 clientsocket 圖 2.32 透過 UDP socket 的行程通訊過程 2.97 / 103

201 2.7/2.8 Socket Programming with TCP/UDP (Cont.) Berkeley Sockets 程式設計 Berkeley Sockets system calls socket() : create endpoint bind() : bind address listen() : specify queue accept() : wait for connection connect() : connect to server transfer data functions: read(), write(), recv(), send() datagrams functions : recvfrom(), sendto() terminate: close(), shutdown() 2.98 / 103

202 2.7/2.8 Socket Programming with TCP/UDP (Cont.) Berkeley Sockets 程式設計 (Cont.) connection-oriented protocol (TCP) Server socket() bind() listen() Client socket() accept() connect() blocks until connection from client send() recv() process request send() data (reply) recv() 2.99 / 103

203 Chapter 3 Transport Layer ( 傳輸層 ) by R.-W. Hung, Dept. CSIE, CYUT, Taiwan 3.1

204 Topic Overview 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原則 3.7 TCP 壅塞控制 3.2 / 96

205 Topic Overview (Cont.) 網際網路傳輸層 目標 (Goal) 了解傳輸層服務背後的原則 多工 / 解多工 可靠的資料傳輸 (reliable data transfer) 流量控制 (flow control) 壅塞控制 (congestion control) 學習有關網際網路上的傳輸層協定 UDP: 非預接式傳輸 TCP: 連線導向的傳輸 TCP: 流量控制 壅塞控制 應用層傳輸層網路層連結層實體層 3.3 / 96

206 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式 ( 無連線 ) 傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.4 / 96

207 3.1 傳輸層服務 網際網路傳輸層 傳輸層服務及協定 提供不同主機上執行應用程式之間的邏輯通訊 邏輯通訊 從應用程式的觀點來看, 兩台執行行程的主機就像是直接連線 ; 實際上, 它們可能透過許多路由器及連結線進行連線 在終端 ( 主機 ) 系統間執行的傳輸協定 (transport layer) 傳送端 : 將應用程式的訊息分割成資料分段 傳送到網路層 接收端 : 將資料分段重組成訊息 傳給應用層 應用層可用的傳輸協定超過一個 網際網路 : TCP 及 UDP 傳輸層協定的製作範圍 製作在終端系統 (network edge) 網路中的路由器 (network core) 沒有製作此層, 它們只製作到網路層 3.5 / 96

208 3.1 傳輸層服務 (Cont.) 傳輸層的邏輯通訊 (logical communication) 應用層傳輸層網路層資料連結層實體層 網路層連結層實體層 網路層連結層實體層 網路層連結層實體層 網路層連結層實體層 網路層連結層實體層 應用層傳輸層網路層資料連結層實體層 圖 3.1 傳輸層提供了應用程式行程間的邏輯通訊而非實體的通訊 3.6 / 96

209 3.1 傳輸層服務 (Cont.) 傳輸層 vs. 網路層 網路層 : 提供主機之間的邏輯通訊 傳輸層 : 提供行程之間的邏輯通訊 依賴 增強 網路層服務 家庭的比喻 :12 個小孩傳送信件給 12 個小孩 行程 = 小孩 應用程式訊息 = 信封中的信 主機 = 房子 傳輸層協定 = Royce 以及 Tommy ( 雙方收送信的代表 ) 網路層協定 = 郵政服務 Royce Tommy 3.7 / 96

210 3.1 傳輸層服務 (Cont.) 網際網路傳輸層協定 可靠的 有序的資料遞送 (TCP) 連線建立 (connection creation) 壅塞控制 (congestion control) 流量控制 (flow control) 不可靠的 無序的資料遞送 :UDP 盡全力 的 IP 的精簡延伸 不提供的服務 : 延遲保證 頻寬保證 安全性保證 應用層傳輸層網路層連結層實體層 網路層連結層實體層網路層連結層實體層 網路層連結層實體層 網路層連結層實體層 網路層連結層實體層 應用層傳輸層網路層連結層實體層 註 TCP/UDP 封包名稱 = segmentation ( 區段 ) 網路層封包名稱 = datagram ( 資料包 ) 3.8 / 96

211 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.9 / 96

212 3.2 多工和解多工 網際網路傳輸層 多工 (multiplexing) 和解多工 (Demultiplexing) 傳送端主機的多工 : 從不同的 socket 收集資料片段 用標頭 ( 稍後將用在解多工 ) 將每個資料片段封裝成資料區段 接收端主機的解多工 : 將收到的資料分段傳送給正確的 socket = socket = 行程 應用層 P3 P1 應用層 P2 P4 應用層 傳輸層 傳輸層 傳輸層 網路層 網路層 網路層 資料連結層 資料連結層 資料連結層 實體層 主機 1 ( 傳送端 ) 實體層 主機 2 ( 接收端 ) 主機 3 ( 傳送端 ) 實體層 圖 3.2 傳輸層的多工與解多工 3.10 / 96 Ex 3.1

213 3.2 多工和解多工 (Cont.) 解多工如何運作? 主機收到網路層的 IP 資料包 (IP datagram) 每一個 IP 資料包都擁有來源端 IP 位址以及目的端 IP 位址 每一個 IP 資料包載送 1 個傳輸層資料區段 (transport-layer segment) 每一個傳輸層資料區段都擁有來源端埠號以及目的端埠號 主機使用 IP 位址以及埠號 (port number) 將資料區段送到正確的 socket 32 位元 來源端埠號 # 目的端埠號 # 其它標頭欄位 同台電腦中的每個 socket 都有一個唯一的 port number, 藉以識別 socket 應用程式資料 ( 訊息 ) 圖 3.3 傳輸層資料區段 (segment) 格式 3.11 / 96

214 3.2 多工和解多工 (Cont.) Socket 行程的基本通訊 Socket 可由一個 IP 位址和一個埠號 (port number) 所組成 一組行程使用一對插座 (socket, 雙方各一個 ) 在網路上通訊 3.12 / 96

215 3.2 多工和解多工 (Cont.) 無連線 (connectionless) 的解多工 UDP 以埠號產生 socket: DatagramSocket mysocket1 = new DatagramSocket(12534); DatagramSocket mysocket2 = new DatagramSocket(12535); 以兩組資料識別 UDP socket : ( 目的端 IP 位址 目的端埠號 ) 當主機收到 UDP 資料區段 (UDP segment) 時 : 確認資料區段中的目的端埠號 以此埠號將 UDP 資料區段傳送到 socket 具有不同來源端 IP 位址的 IP 資料包 ( 網路層封包 ) 和 / 或來源端埠號會被送到同一個 socket ( 若目的端埠號相同 ) 3.13 / 96

216 3.2 多工和解多工 (Cont.) 無連線 (connectionless) 的解多工 (Cont.) DatagramSocket serversocket = new DatagramSocket(6428); 用戶端 IP:A P2 伺服端 IP:C P3 用戶端 IP:B P1P1 SP:6428 DP:9157 SP:6428 DP:5775 SP:9157 DP:6428 SP:5775 DP:6428 SP = Source Port DP = Destination Port SP 提供 回傳埠號 圖 3.4 來源端與目的端埠號的交換 3.14 / 96

217 3.2 多工和解多工 (Cont.) 連線 (connection) 的解多工 TCP TCP socket 以四組資料加以識別 : 來源端 IP 位址 來源端埠號 目的端 IP 位址 目的端埠號 接收端主機使用全部的四個數值將資料區段送到適當的 socket 伺服端主機可能同時支援許多 TCP sockets: 每個 socket 以它自己的四組資料加以識別 Web 伺服器針對連結到它的每一個用戶端都有不同的 socket 非永久性 HTTP 針對每一次的請求都有不同的 socket 3.15 / 96

218 3.2 多工和解多工 (Cont.) 連線 (connection) 的解多工 (Cont.) 用戶端 IP:A P1 P2 SP: 7532 DP: 80 S_IP: A D_IP:C SP: 7546 DP: 80 S_IP: A D_IP:C Web 伺服端 IP:C P4 每個連線由一個 HTTP 行程控制 (HTTP thread) 用戶端 IP:B P1 P5 P6 P3 傳輸層解多工控制 SP: 4560 DP: 80 S_IP: B D_IP:C SP = Source Port DP = Destination Port S_IP = Source IP addr. D_IP = Destination IP addr. 圖 3.5 兩個用戶端, 使用相同的目的端埠號 (80) 來與相同的 Web 伺服器進行通訊 Exercise 3.1 Ex / 96

219 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式 ( 無連線 ) 傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.17 / 96

220 3.3 非預接式傳輸 UDP 網際網路傳輸層 UDP (User Datagram Protocol): 使用者資料包協定 RFC 768 實際的 精簡的網際網路傳輸協定 盡全力 的服務 UDP 資料區段可能 : 遺失 不保證資料會到達目的地 不按順序傳送給應用程式 非預接式服務 在 UDP 傳送端和接收端之間沒有交握程序 (non-handshaking) 每一個 UDP 資料區段的處理和其它資料區段是獨立的 為何會使用 UDP? (1) 不需建立連線 ( 建立連線會增加延遲 ) (2) 簡單 : 在傳送端和接收端不需維持連線狀態 (3) 較小的封包標頭 (4) 沒有壅塞控制 :UDP 可以盡可能地快速傳送資料 DNS 採用此種傳輸方式 3.18 / 96

221 3.3 非預接式傳輸 UDP (Cont.) UDP (Cont.) 常見的網際網路應用及其下層的傳輸協定 應用 應用層協定 底層傳輸層協定 電子郵件 SMTP TCP 遠端終端機連線 Telnet TCP 網頁 HTTP TCP 檔案傳輸 FTP TCP 遠端檔案伺服器 NFS 一般是 UDP 串流多媒體 私人協定 UDP 或 TCP 網際網路電話 私人協定 UDP 或 TCP 網路管理 SNMP 一般是 UDP 繞徑協定 RIP 一般是 UDP 網域名稱系統 DNS 一般是 UDP 圖 3.6 常見的網際網路應用及其下層的傳輸協定 3.19 / 96

222 3.3 非預接式傳輸 UDP (Cont.) UDP (Cont.) 通常用在串流的多媒體應用程式 可以容忍資料遺失 易受速率影響 其它使用 UDP 的有 : DNS SNMP (Simple Network Management Protocol) 使用 UDP 的可靠傳輸? 在應用層加入可靠性的機制 32 位元 以位元組為單位的 UDP 資料區段大小 ( 包含標頭 = 8 bytes) 來源端埠號 # 目的端埠號 # 長度 應用程式資料 ( 訊息 ) 檢查和 Note: TCP header = 20 bytes ( 圖 3.29) 圖 3.7 UDP 資料區段 (segment) 格式 3.20 / 96

223 Ex: 非預接式傳輸 UDP (Cont.) UDP (Cont.) UDP 檢查和 (check sum) 目標 : 偵測傳送的資料區段中的 錯誤 ( 例如, 偵測被翻轉的位元 ) 作法 : 傳送端 : +) 將資料區段的內容視為一列 16 位元的整數 檢查和 : 資料區段內容的加法 (1 的補數和 ) 傳送端將檢查和的值放入 UDP 的檢查和欄位 接收端 : 計算收到的資料區段的資料和 ( 不包括檢查和欄位 ) 確認計算出來的資料和與與檢查和欄位的加法結果是否為 : NO 偵測到錯誤 YES 沒有偵測到錯誤 但是仍然可能有錯誤? 後面有更多介紹 資料和 + 檢查和 = s 補數 : 0 1&1 0 check sum = / 96 例題 : UDP 的資料區段 (segment) 格式如圖 3.7 所示 請說 Ex 3.4 明傳送端 ( 來源端 ) 與接收端 ( 目的端 ) 如何偵測傳送 Exercise 的資料區段中的錯誤? Ex

224 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.22 / 96

225 3.4 可靠資料傳輸的原理 網際網路傳輸層 實作可靠資料傳輸 (reliable data transfer) 的分層 應用層 傳輸層 資料連結層 可以列在網路問題中的前十大清單 不可靠通道 ( 資料會遺失及錯誤 ) 的特性決定了可靠資料傳輸協定 (rdt, reliable data transfer) 的複雜性 應用層傳輸層網路層連結層實體層 圖 3.8 可靠的資料傳輸 服務模型與服務實作 3.23 / 96

226 3.4.1 建立可靠資料傳輸協定 建立可靠的資料傳輸 rdt_send(): 被上層呼叫 ( 例如, 應用層 ) 將資料傳遞給接收端的上層協定 deliver_data(): 被 rdt 呼叫 將資料傳送到上層 send side rdt receive side udt_send( ) udt_send(): 被 rdt 呼叫 經由不可靠的通道將封包傳送給接收端 (un-reliable data transfer) 3.24 / 96 rdt_rcv(): 當封包抵達接收端的通道時被呼叫 Ex 3.5

227 3.4.1 建立可靠資料傳輸協定 (Cont.) 有限狀態機 (FSM) Finite-State Machine 說明傳送端 接收端可靠資料傳輸協定的狀態 / 事件轉移 導致狀態轉換的事件 狀態轉換時所採取的動作 狀態 1 狀態 2 狀態 : 在這個 狀態 時, 下一個狀態將唯一地被下一個事件所決定 3.25 / 96

228 3.4.1 建立可靠資料傳輸協定 (Cont.) FSM (Cont.) 例子 鬧鐘響刷牙 吃飯 上學 睡覺 上課 3.26 / 96 Exercise 3.3

229 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt1.0 使用可靠通道的可靠傳輸 next two slides 底層的通道是完全可靠的 沒有位元錯誤 沒有資料遺失 傳送端和接收端擁有各自的 FSM: 傳送端將資料送入底層的通道 接收端從底層的通道接收資料 等待上層傳來的呼叫 rdt_send(data) packet = make_pkt(data) rdt_send(packet) 等待下層傳來的呼叫 rdt_rcv(packet) extract (packet, data) deliver_data(data) (a) 傳送端 (b) 接收端 圖 3.9 使用絕對可靠通道的協定 3.27 / 96 Ex 3.6

230 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt1.0 使用可靠通道的可靠傳輸 (Cont.) 上層 (eg. 應用層 ) sending process data rdt_send(data) receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data make_packet(data) rdt_send(packet) 下層 (eg. 網路層 ) 可靠通道 3.28 / 96

231 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt1.0 使用可靠通道的可靠傳輸 (Cont.) 上層 (eg. 應用層 ) sending process receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data data extract(packet) rdt_rcv(packet) 下層 (eg. 網路層 ) 可靠通道 3.29 / 96

232 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 可能產生位元錯誤的通道 底層的通道可能會將封包中的位元翻轉 ( 位元錯誤 ) 偵測位元錯誤的檢查和 問題 : 如何回覆錯誤? 確認 (ACKs): 接收端明確地告訴傳送端封包的傳送 OK ( 正確 ) 否定確認 (NAKs): 接收端明確地告訴傳送端封包的傳送有問題 ( 不正確 ) 當收到 NAK 時, 傳送端會重傳封包 rdt2.0 的新機制 ( 優於 rdt1.0): 具 ARQ 協定 (Auto Repeat request) 錯誤偵測 接收端回饋 : 控制訊息 (ACK NAK) 接收端 傳送端 3.30 / 96

233 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) FSM 說明 rdt_send(data) packet = make_pkt(data, checksum) udt_send(packet) 等待上層傳來的呼叫 等待接收端傳來 ACK/NAK rdt_rcv(rcvpkt) && isnak(rcvpkt) udt_send(packet) rdt_scv(rcvpkt) && isack(rcvpkt) None (a) 傳送端 等待下層傳來的呼叫 rdt_rcv(rcvpkt) && not_correct(rcvpkt) packet = make_pkt(nak) udt_send(packet) rdt_rcv(rcvpkt) && is_correct(rcvpkt) extract(rcvpkt, data) deliver_data(data) packet = make_pkt(ack) udt_send(packet) 3.31 / 96 (b) 接收端 圖 3.10 使用會產生位元錯誤通道的協定

234 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 沒有錯誤時的運作 : 上層 (eg. 應用層 ) sending process receiver process data rdt_send(data) 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data make_packet(data) udt_send(packet) 下層 (eg. 網路層 ) 不可靠通道 3.32 / 96

235 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 沒有錯誤時的運作 : (Cont.) 上層 (eg. 應用層 ) sending process receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data rdt_rcv(rcvpkt) data extract(packet) rdt_rcv(packet) && correct 下層 (eg. 網路層 ) 不可靠通道 3.33 / 96

236 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 沒有錯誤時的運作 : (Cont.) 上層 (eg. 應用層 ) sending process receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 rdt_rcv(rcvpkt) data ACK extract(packet) udt_send(ack) 下層 (eg. 網路層 ) 不可靠通道 3.34 / 96

237 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 沒有錯誤時的運作 : (Cont.) rdt_send(data) packet = make_pkt(data, checksum) udt_send(packet) 等待上層傳來的呼叫 等待接收端傳來 ACK/NAK rdt_rcv(rcvpkt) && isnak(rcvpkt) udt_send(packet) rdt_scv(rcvpkt) && isack(rcvpkt) None (a) 傳送端 等待下層傳來的呼叫 rdt_rcv(rcvpkt) && not_correct(rcvpkt) packet = make_pkt(nak) udt_send(packet) rdt_rcv(rcvpkt) && is_correct(rcvpkt) extract(rcvpkt, data) deliver_data(data) packet = make_pkt(ack) udt_send(packet) (b) 接收端 3.35 / 96

238 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 發生錯誤時的運作 : 上層 (eg. 應用層 ) sending process receiver process data rdt_send(data) 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data make_packet(data) udt_send(packet) 下層 (eg. 網路層 ) 不可靠通道 3.36 / 96

239 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 發生錯誤時的運作 :(Cont.) 上層 (eg. 應用層 ) sending process receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data rdt_rcv(rcvpkt) rdt_rcv(packet) && incorrect 下層 (eg. 網路層 ) 不可靠通道 3.37 / 96

240 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 發生錯誤時的運作 :(Cont.) 上層 (eg. 應用層 ) sending process receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 rdt_rcv(rcvpkt) NAK udt_send(nak) 下層 (eg. 網路層 ) 不可靠通道 3.38 / 96

241 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 發生錯誤時的運作 :(Cont.) 上層 (eg. 應用層 ) sending process receiver process 本層 (eg. 傳輸層 ) 可靠傳輸協定 header data udt_send(packet) rdt_rcv(packet) 下層 (eg. 網路層 ) 不可靠通道 3.39 / 96

242 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 發生錯誤時的運作 : (Cont.) rdt_send(data) packet = make_pkt(data, checksum) udt_send(packet) 等待上層傳來的呼叫 等待接收端傳來 ACK/NAK rdt_rcv(rcvpkt) && isnak(rcvpkt) udt_send(packet) rdt_scv(rcvpkt) && isack(rcvpkt) None (a) 傳送端 等待下層傳來的呼叫 rdt_rcv(rcvpkt) && not_correct(rcvpkt) packet = make_pkt(nak) udt_send(packet) rdt_rcv(rcvpkt) && is_correct(rcvpkt) extract(rcvpkt, data) deliver_data(data) packet = make_pkt(ack) udt_send(packet) (b) 接收端 3.40 / 96

243 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt2.0 (Cont.) 致命的缺點 : 假如 ACK/NAK 損毀了會如何? 傳送端不知道接收端發生了什麼事! 沒辦法直接重傳 : 可能會重複 重複的處理 : 假如 ACK/NAK 損壞了, 傳送端會重新傳送目前的封包 傳送端會在每個封包加上序號 (sequence number) 接收端根據序號刪掉 ( 不往上傳 ) 重複的封包 Rdt2.0 為停止並等待 (stop-and-wait) 協定 傳送端傳送一個封包, 並等待接收端的回應 沒有效率 使用 Rdt3.0 改進 Rdt2.1 & Rdt2.2 ( 自我學習 ) 3.41 / 96 Exercise 3.4

244 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 使用會發生錯誤及遺失封包的通道 假設 : 底層的通道 (channel) 也可能遺失封包 ( 資料或 ACK) 檢查和 (checksum, 檢查位元錯誤 ) 封包序號 (2 個封包序號, M0 M1) ACK (2 個 ACK, ACK0 ACK1) 重傳 ( 使用 Timer 設定重傳時間 ) 方法 : 傳送端等待 ACK 合理的 時間 假如在這段時間內沒有收到 ACK, 則重傳 假如封包 ( 或 ACK) 只是延遲了 ( 沒有遺失 ):( 過早逾時 ) 重傳會導致重複, 但是封包序號的使用能夠處理這個情況 接收端必須指定確認的封包序號 需要倒數計時器 (countdown timer) 3.42 / 96

245 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (alternating-bit protocol) 傳送端 接收端 上層 上層 本層 M0 header data 本層 Ack0 下層 下層 不可靠通道 3.43 / 96

246 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (alternating-bit protocol) 傳送端 接收端 上層 上層 本層 M1 header data 本層 Ack1 下層 下層 不可靠通道 3.44 / 96

247 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (Cont.) 圖 3.16 Rdt3.0 的位元變換協定 (alternating-bit protocol, M0/M1 交換 ) 3.45 / 96

248 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (Cont.) 圖 3.16 Rdt3.0 的位元轉換協定 (Cont.) Exercise / 96 Exercise 3.5

249 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (Cont.) rdt_rcv(rcvpkt) None 等待從上一層傳來的呼叫 M0 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt, 1) stop_timer rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer 等待 ACK 訊息 0 rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isack(rcvpkt, 1) ) timeout rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isack(rcvpkt, 0) stop_timer None udt_send(sndpkt) start_timer timeout udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) isack(rcvpkt, 0) ) None 等待 ACK 訊息 1 rdt_send(data) 圖 3.15 Rdt3.0 傳送端的 FSM 等待從上一層傳來的呼叫 M1 sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) None Ex / 96

250 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (Cont.) Rdt3.0 的效能 Rdt3.0: 停止並等待的機制 傳送端 接收端 在 t = 0 時, 傳送第 1 個封包的第 1 個位元 在 t = L / R 時, 傳送第 1 個封包的最後 1 個位元 RTT (round-trip time) 第一個封包的第一個位元到達 第一個封包的最後一個位元到達, 並且送出 ACK 在 t = RTT + L / R 時,ACK 到達, 然後送出下 1 個封包 U sender L / R RTT L / R 0.008ms ms % 圖 3.18(a) Rdt3.0 的停止並等待協定 3.48 / 96

251 3.4.1 建立可靠資料傳輸協定 (Cont.) Rdt3.0 (Cont.) Rdt3.0 的效能 (Cont.) Rdt3.0 能夠運作, 但是效能很糟 範例 :1 Gbps 的連結線 15 毫秒 (ms) 終端對終端傳遞延遲 1KB 的封包傳送 傳送時間 d trans = 傳送端 ( 通道 ) 使用率 (utilization) ( 傳送端將位元傳入通道的時間比例 ) L / R 0.008ms U sender = % 傳送端處於忙碌的時間只有 0.027% 效能極差 網路協定限制了實體資源的使用! 解決方案 RTT L / R L( 封包長度位元 ) 8000bits / packet R( 傳送速率, bps) bits / sec ms 8us( 微秒 ) 0.008ms( 毫秒 ) 傳送端不使用 stop-and-wait 運作, 而允許同時送出多個封包, 不需每個封包一一等待確認 (ACK) Pipeline (3.4.2 節 ) / 96

252 3.4.2 管線化的可靠資料傳輸協定 (Pipeline) 管線化協定 管線化 (pipelining): 傳送端允許多個 傳送中的 還沒有被確認的封包 序號的範圍必須增加 傳送端和 / 或接收端需要暫存器 兩種管線化協定的一般性型態 回溯 N (Go-Back N, GBN) 選擇性重複 (Selective Repeat, SR) 圖 3.17 (a) 停止並等待協定 (b) 管線化協定 3.50 / 96

253 3.4.2 管線化的可靠資料傳輸協定 (Cont.) 管線化 增加使用率 傳送端 接收端 在 t = 0 時, 傳送第 1 個封包的第 1 個位元 在 t = L/R 時, 傳送第 1 個封包的最後一個位元 RTT 第 1 個封包的第 1 個位元到達 第 1 個封包的最後 1 個位元到達 送出 ACK 第 2 個封包的最後 1 個位元到達 送出 ACK 第 3 個封包的最後 1 個位元到達 送出 ACK ACK arrives send next packet t = RTT + L / R 續 Rdt3.0 範例 :( 同時送出 3 個封包 ) U sender 3 L / R ms % RTT L / R ms 增加 3 倍的使用率! 圖 3.18(b) 管線化傳輸協定 Ex / 96

254 3.4.3 回溯 N 協定 (Go-Back N, GBN) 回溯 N (GBN) 概念 允許傳送端同時傳送多個封包而不需等待確認 封包標頭的 k- 位元序號 ( 封包序號 ) 但管線中未被確認的封包數量不得超過某個可容許的整數 N 又稱為 sliding-window protocol ( 滑動視窗協定 ) 傳送端製作 base: 最久未被確認的封包序號 nextseqnum: 下一個要被傳送的封包序號 當 nextseqnum base + 1 N, 允許傳送封包 ( 傳送後 nextseqnum++) ; 否則, 不允許傳送封包 當收到確認 base 封包 (ACK base),base++ GBN Applet: /applets/go-back-n/index.html 圖 3.19 回溯 N 協定中, 傳送端的封包序號觀點 3.52 / 96

255 3.4.3 回溯 N 協定 (Cont.) 回溯 N (Cont.) GBN 傳送端的 FSM Initial base=1 nextseqnum=1 rdt_rcv(rcvpkt) && error(rcvpkt) None rdt_send(data) if (nextseqnum < base+n) { sndpkt[nextseqnum] = make_pkt(nextseqnum, data, chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ } else refuse_data(data) timeout start_timer 等待 udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) udt_send(sndpkt[nextseqnum-1]) rdt_rcv(rcvpkt) && not_error(rcvpkt) base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer else start_timer 圖 3.20 回溯 N 協定中, 傳送端的 FSM 圖 3.53 / 96

256 3.4.3 回溯 N 協定 (Cont.) 回溯 N (Cont.) GBN 接收端的 FSM 只使用 ACK: 只為接收順序正確的封包傳送 ACK 可能會產生重複的 ACK 只需要記住 expectedseqnum ( 期望收到的下一個封包序號 ) 順序不正確的封包 : 刪除 ( 不會暫存 ) 接收端沒有暫存器! 重新回應最高的順序正確封包 Initial expectedseqnum = 1 sndpkt = make_pkt(0, ACK, chksum) default udt_send(sndpkt) 等待 rdt_rcv(rcvpkt) && not_error(rcvpkt) && hasseqnum(rcvpkt, expectedseqnum) extract(rcvpkt, data) deliver_data(data) sndpkt = make_pkt(expectedseqnum, ACK, chksum) udt_send(sndpkt) expectedseqnum++ 圖 3.21 回溯 N 協定中, 接收端的 FSM 圖 3.54 / 96 Ex 3.9

257 3.4.3 回溯 N 協定 (Cont.) 回溯 N (Cont.) GBN 的運作 window TCP 採用 GBN 技術 GBN Applet: /applets/go-back-n/index.html 圖 3.22 回溯 N 協定的運作 3.55 / 96

258 3.4.4 選擇性重複協定 (Selective Repeat, SR) 選擇性重複協定 (SR) GBN 的問題 單一封包的錯誤, 將導致其後的所有封包均需重傳 ( 重新傳送大量封包 ) 選擇性重複 傳送端只重傳沒有收到 ACK 的封包 傳送端針對每一個未確認的封包需要一個計時器 接收端分別確認所有正確接收的封包 依需要暫存封包 最終會依序傳送到上一層 傳送端視窗 N 個連續的序號 再次 用來限制傳送出去的 未確認的封包序號 SR Applet: /applets/sr/index.html 3.56 / 96

259 3.4.4 選擇性重複協定 (Cont.) 選擇性重複協定 (Cont.) SR 的傳送端 接收端視窗 圖 3.23 選擇性重複協定中, 傳送端與接收端的封包序號觀點 3.57 / 96

260 3.4.4 選擇性重複協定 (Cont.) 選擇性重複協定 (Cont.) 選擇性重複的運作 傳送端 來自上層的資料 : 假如下一個可用的序號在視窗內, 則傳送封包 timeout(n): 重送封包 n; 重新啟動計時器 每個封包都有 timer ACK(n) 在 [sendbase, sendbase+n] 中 : 將封包 n 標示為已收到的 假如 n 為未確認的封包中最小的, 將視窗的 base 往前移到下一個未回應的序號 接收端 封包 n 在 [rcvbase, rcvbase+n 1] 中 傳送 ACK(n) 不正確的順序 : 暫存區 正確順序 : 遞送 ( 也遞送暫存區內順序錯誤的封包 ) 將視窗前進到下一個未接收的封包 封包 n 在 [rcvbase N, rcvbase 1] 中 ACK(n) 否則 : 忽略該封包 3.58 / 96

261 3.4.4 選擇性重複協定 (Cont.) 選擇性重複協定 (Cont.) 選擇性重複的運作 (Cont.) SR Applet: /applets/sr/index.html 圖 3.26 選擇性重複協定的運作 3.59 / 96

262 3.4.4 選擇性重複協定 (Cont.) 選擇性重複協定 (Cont.) 選擇性重複的困境 範例 : 序號 : 視窗大小 =3 接收端無法分辨 (a)(b) 兩種情況的差別! 不正確地重新傳送重複的資料如同 (a) 圖 3.27 選擇性重複協定中, 接收端無法判斷是新的封包還是重傳的封包 3.60 / 96

263 3.4 可靠資料傳輸的原理 (Cont.) 可靠資料傳輸機制的總整理 表 3.1 可靠資料傳輸機制及其用途的總整理 機制 Checksum Timer Sequence number Acknowledge 用途 註解 用來偵測傳輸封包的位元錯誤 用來進行封包逾時 / 重送, 可能因為該封包 ( 或其 ACK) 遺失在通道中 用來對從傳送端流向接收端的資料封包進行循序編號 收到的封包序列號碼若不連續, 則接收端可偵測出封包的遺失 接收端用此訊息封包告知傳送端某個 ( 組 ) 封包已被正確接收 Negative acknowledge Sliding-window, pipelining 接收端用此訊息封包告知傳送端某個封包並未被正確接收 傳送端可能會被限制只能傳送序號在某個範圍的封包 藉由容許多個正在傳輸但未被確認的封包傳送端的通道使用率將比停止並等待操作模式增加 3.61 / 96 Ex 3.10

264 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 區段結構 可靠的資料傳輸 流量控制 連線管理 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.62 / 96

265 3.5 連線導向傳輸 TCP 網際網路傳輸層 TCP 綜觀 TCP 定義於 RFCs TCP 具備的功能 點對點 : 一個傳送端 一個接收端 可靠的 有順序的位元組串流 : 沒有 訊息界線 管線化 : TCP 壅塞控制和流量控制, 可設定視窗大小 傳送端和接收端暫存器 ( 緩衝區, buffer) 全雙工資料傳輸 :(full-duplex service) 同一個連結中, 雙向的資料流 MSS: 最大資料區段大小 (maximum segment size) 連線導向 : 交握程序 ( 控制訊息的交換 ) 在資料開始交換之前, 設定傳送端和接收端的狀態 流量控制 : 傳送端傳送的資料量不會超過接收端可接收的資料量 3.63 / 96

266 3.5 連線導向傳輸 TCP (Cont.) TCP 綜觀 (Cont.) 讀出 TCP 傳送端緩衝區 資料區段 資料區段 TCP 接收端緩衝區 圖 3.28 TCP 的傳送端與接收端的緩衝區 (buffer) 3.64 / 96

267 3.5 連線導向傳輸 TCP (Cont.) TCP 資料區段結構 (segment structure) URG: 緊急資料 ( 通常不會使用 ) ACK: 確認有效 PSH: 馬上將資料送出 ( 通常不會使用 ) RST SYN FIN: 連線建立 ( 設定 中斷指令 ) 網際網路檢查和 ( 如同 UDP) 標頭長度 來源端埠號 未使用 U A P R 網際網路檢查和 32 位元 序列號碼 確認號碼 S F 選用欄位 ( 不固定長度 ) 應用程式資料 ( 不固定長度 ) 接收端埠號 接收端的視窗 緊急資料指標 以資料位元組計算 ( 非資料區段的編號!) 接收端願意接收的位元組數 用於流量控制 (flow control) 圖 3.29 TCP 區段的結構 (segment structure) TCP 標頭 = 20 bytes UDP 標頭 = 8 bytes 3.65 / 96

268 3.5 連線導向傳輸 TCP (Cont.) TCP 序列號碼與確認號碼 序列號碼 : 資料區段中, 第一個位元的位元組串流 編號 ( 非封包序號 ) 例如 : 主機 A 將一資料串流 (500,000 bytes 的檔案 ) 透過 TCP 傳送給主機 B, 其中 TCP 的 MSS=1,000 bytes 此資料串流的第 1 個 byte 被編號為 0 第 1 個 TCP 區段的序列號碼 = 0 第 2 個 TCP 區段的序列號碼 = See 圖 3.30 確認號碼 : 主機 A 期待從主機 B 收到的下一個位元組序列號碼 (A 到 B 的資料區段 ) 主機正在等待的下一個資料位元組的序號 累積式確認 Q: 接收端如何處理順序不正確的資料區段 Ans: TCP 規格中未限制 取決於程式開發者 3.66 / 96

269 3.5 連線導向傳輸 TCP (Cont.) TCP 序列號碼與確認號碼 (Cont.) 確認號碼 :(Cont.) 主機 A 傳送資料給主機 B 主機 A 已從主機 B 收到序號從 0 到 535 的所有位元組 主機 A 正要傳送一筆 TCP 區段給主機 B 主機 A 傳送的 TCP 區段中的 確認號碼 為 / 96

270 3.5 連線導向傳輸 TCP (Cont.) TCP 序列號碼與確認號碼 (Cont.) 主機 A 主機 B 使用者鍵入字元 C 主機確定收到 C, 然後回應字元 C 時間 主機確定收到回應字元 C 的 ACK 訊息 圖 3.31 簡單的 TCP Telnet 範例 Ex / 96 Ex 3.11

271 3.5.3 TCP 來回傳遞時間以及逾時 TCP 來回傳遞時間以及逾時 Q: 如何設定 TCP 的逾時值? 比 RTT 長 但是 RTT 是不固定的 太短 : 過早逾時 不需要重新傳送 太長 : 太晚對資料區段遺失作出反應 Q: 如何估計來回傳遞時間 ( RTT)? (EstimatedRTT) 樣本 RTT (SampleRTT): 測量資料區段傳送出去到收到確認所需的時間 忽略重傳 樣本 RTT 會有所變動 我們想要讓預估的 RTT 更平滑 將好幾個最近的測量值做平均 而非目前的樣本 RTT 3.69 / 96

272 3.5.3 TCP 來回傳遞時間以及逾時 (Cont.) TCP 來回傳遞時間以及逾時 (Cont.) TCP 更新估算 RTT 值的公式 EstimatedRTT = (1 ) EstimatedRTT + SampleRTT 指數加權移動平均值 過去樣本的影響將以指數速率減少 建議值 : = / 96

273 3.5.3 TCP 來回傳遞時間以及逾時 (Cont.) TCP 來回傳遞時間以及逾時 (Cont.) 範例 RTT 估計 : RTT: gaia.cs.umass.edu to fantasia.eurecom.fr RTT (milliseconds) time (seconnds) SampleRTT Estimated RTT 圖 3.32 RTT 取樣與 RTT 估算值 3.71 / 96

274 3.5.3 TCP 來回傳遞時間以及逾時 (Cont.) TCP 來回傳遞時間以及逾時 (Cont.) 設定逾時間隔 首先估計 SampleRTT 與 EstimatedRTT 的差距 : DevRTT = (1 ) DevRTT + SampleRTT EstimatedRTT ( 的建議值 =0.25) 接著設定逾時間隔 : TimeoutInterval = EstimatedRTT + 4 DevRTT 3.72 / 96

275 3.5.4 TCP 的可靠資料傳輸 TCP 可靠的資料傳輸 What? TCP 在 IP 的不可靠服務上建立 rdt 服務 簡化的 TCP 傳送端 : 忽略重複的 ack 忽略流量控制 壅塞控制 3.73 / 96

276 3.5.3 TCP 的可靠資料傳輸 (Cont.) TCP 可靠的資料傳輸 (Cont.) 簡化的 TCP 傳送端 :(Cont.) 從應用程式收到資料 : 產生含有序號的資料區段 序號是資料區段中 第一個資料位元組的位元組串流編號 假如計時器尚未執行 啟動計時器 ( 將計時器想成與最久的未確認資料區段有關 ) 逾時時間 :TimeOutInterval 逾時 : 重新傳送導致逾時的資料區段 重新啟動計時器 收到 Ack: ( 假如確認為之前未確認的資料區段 ) 更新已確認的狀態 假如還有未確認的資料區段 重新啟動計時器 3.74 / 96

277 3.5.3 TCP 的可靠資料傳輸 (Cont.) TCP 可靠的資料傳輸 (Cont.) 簡化的 TCP 傳送端 :(Cont.) NextSeqNum = InitialSeqNum SendBase = InitialSeqNum loop (forever) { switch(event) event: data received from application above create TCP segment with sequence number NextSeqNum if (timer currently not running) start timer pass segment to IP NextSeqNum = NextSeqNum + length(data) event: timer timeout retransmit not-yet-acknowledged segment with smallest sequence number start timer event: ACK received with ACK field value of y if (y > SendBase) { SendBase = y if (there are currently not-yet-acknowledged segments) start timer } } /* end of loop forever */ 圖 3.33 簡化的 TCP 傳送端 3.75 / 96

278 3.5.3 TCP 的可靠資料傳輸 (Cont.) TCP 可靠的資料傳輸 (Cont.) TCP 重新傳送的情況 : 主機 A 主機 B 主機 A 主機 B 逾時的間隔 X loss 序號 =92 逾時間隔 SendBase = 100 時序 ACK 遺失的情況 3.76 / 96 SendBase = 100 SendBase = 120 SendBase = 120 序號 =92 逾時間隔 時序 過早逾時

279 3.5.3 TCP 的可靠資料傳輸 (Cont.) TCP 可靠的資料傳輸 (Cont.) TCP 重新傳送的情況 :(more) 主機 A 主機 B 逾時間隔 X loss SendBase = 120 time 累積式 ACK 的情況 3.77 / 96

280 3.5.5 TCP 流量控制 (flow control) TCP 流量控制 運作原理 TCP 連線的接收端有一個接收緩衝區 ( 圖 3.38) 應用程式的行程也許會以較慢的速度從緩衝區讀取資料 流量控制 傳送端不會傳送太多太快的資料超過接收端的緩衝區 調整傳送端的速度與接收端應用程式能負擔的速度相符 圖 3.38 接收端的接收視窗 (RcvWindow) 與接收緩衝區 (RcvBuffer) 3.78 / 96

281 3.5.5 TCP 流量控制 (Cont.) TCP 流量控制的運作 假設 :TCP 接收端會將順序不正確的資料區段捨棄 緩衝區內的剩餘空間 RcvWindow = RcvBuffer (LastByteRcvd LastByteRead) 接收端將 RcvWindow 值包含在資料區段裡, 以告知剩餘的空間 傳送端限制未確認的資料大小在 RcvWindow 值之下 保證接收端緩衝區不會溢出 Flow control Applet: /applets/flow/flowcontrol.htm 3.79 / 96 Ex 3.13

282 3.5.5 TCP 流量控制 (Cont.) TCP 流量控制的運作 (Cont.) 示意圖 TCP Sender TCP Receiver Buffer 已收到的 TCP data 傳送端送出封包大小總和 x 計算 x 將 x 放入 TCP 封包的 接收端的視窗 ( 圖 3.29) 送出封包 剩餘可接收的空間大小 x x 3.80 / 96

283 3.5.6 TCP 連線管理 (connection management) TCP 建立連線 TCP 傳送端 接收端在交換資料區段之前, 會先建立 連線 將 TCP 變數初始化 : 序號 緩衝區 流量控制資訊 ( 例如 RcvWindow) 用戶端 : 開始連線者 Socket clientsocket = new Socket("hostname, "port number"); 伺服端 : 被用戶端聯繫 Socket connectionsocket = welcomesocket.accept(); 三路交握 (three-way handshaking) 步驟 1: 用戶端主機傳送 TCP SYN 資料區段到伺服器 指定初始的序號 沒有資料傳遞 步驟 2: 伺服端主機收到 SYN, 以 SYNACK 資料區段回應 伺服端配置緩衝區 指定伺服端的初始序號 步驟 3: 用戶端收到 SYNACK, 回應 ACK 資料區段, 可能含有資料 圖 / 96

284 3.5.6 TCP 連線管理 (Cont.) TCP 關閉連線 用戶端關閉 socket: clientsocket.close(); 步驟 1: 用戶端終端系統傳送 TCP FIN 控制區段到伺服端 步驟 2: 伺服端接收到 FIN 以 ACK 回應 關閉連線 傳送 FIN 步驟 3: 用戶端收到 FIN 回應 ACK 訊息 進入 等待計時 對接收到的 FIN 做確認的回應 步驟 4: 伺服端收到 ACK 連線關閉 用戶端 伺服端 關閉 關閉 已關閉 time out 已關閉 圖 3.40 關閉 TCP 連線 3.82 / 96

285 3.5.6 TCP 連線管理 (Cont.) TCP 的生命週期 圖 3.41 TCP 用戶端生命週期 圖 3.42 TCP 伺服端生命週期 3.83 / 96

286 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.84 / 96

287 網際網路傳輸層 3.6 壅塞控制的原理 (Congestion control) 網路壅塞 (congestion) 非正式地 : 太多的來源端傳送太多的資料, 對網路來說太快, 超過能處理的速度 與流量控制不同! 表現形式 : 封包遺失 ( 路由器緩衝區溢出 ) 長的延遲 ( 在路由器緩衝區佇列中等待 ) 前十大的網路問題之一 3.85 / 96

288 3.6 壅塞控制的原理 (Cont.) 網路壅塞 (Cont.) 主機 A 主機 B In router s buffer >> Out loss loss 3.86 / 96

289 3.6 壅塞控制的原理 (Cont.) 壅塞的原因和代價 情境 1 兩個傳送端 兩個接收端 ; 一個路由器具無限的緩衝區 ; 沒有重傳機制 主機 A in = 傳送的速度 out = 接收的速度 主機 B 沒有限制的分享輸出連結緩衝器 R = 通道的容量 圖 3.43 壅塞情境 / 96

290 3.6 壅塞控制的原理 (Cont.) 壅塞的原因和代價 情境 1 (Cont.) 兩個傳送端 兩個接收端 ; 一個路由器具無限的緩衝區 ; 沒有重傳機制 圖 3.44 壅塞情境 1 產出量與延遲時間相對於主機傳送速度的函數圖形 當壅塞時會有很長的延遲 最大的可達成流通量 = R/ / 96

291 3.6 壅塞控制的原理 (Cont.) 壅塞的原因和代價 情境 2 兩個傳送端 兩個接收端 ; 一個路由器具有限的緩衝區 ; 沒有重傳機制 主機 A in = 傳送的速度 out = 接收的速度 主機 B in = 原始資料 + 重新傳送的資料 有限制的分享輸出連結緩衝器 R = 通道的容量 圖 3.45 壅塞情境 / 96

292 3.6 壅塞控制的原理 (Cont.) 壅塞的原因和代價 情境 2 (Cont.) 兩個傳送端 兩個接收端 ; 一個路由器具無限的緩衝區 ; 沒有重傳機制 R/2 R/2 R/2 R/3 out out out R/4 in R/2 in R/2 in R/2 a. b. c. 圖 3.46 壅塞情境 2 使用有限緩衝區效能 壅塞的 代價 : 對給定的 實際產量 (goodput), 會有更多的工作 ( 重新傳輸 ) 不需要的重新傳輸 : 連結必須負擔多個封包的副本 3.90 / 96

293 3.6 壅塞控制的原理 (Cont.) 壅塞控制的方法 端點對端點壅塞控制 : 網路層並沒有提供明顯的協助 根據終端系統觀察到的遺失及延遲來判斷壅塞 TCP 採用的方法 網路協助的壅塞控制 : 路由器提供協助給終端系統 以一個位元來表示壅塞 (SNA DECbit TCP/IP ECN ATM) 限制傳送端應該傳送的明確速率 3.91 / 96

294 第三章導覽流程 網際網路傳輸層 3.1 傳輸層服務 3.2 多工和解多工 3.3 非預接式傳輸 UDP 3.4 可靠資料傳輸的原理 3.5 連線導向傳輸 TCP 3.6 壅塞控制的原理 3.7 TCP 壅塞控制 3.92 / 96

295 網際網路傳輸層 3.7 TCP 壅塞控制 (TCP Congestion control) TCP 壅塞控制 原理 採用端點對端點壅塞控制 讓傳送端根據某些原則來偵測網路壅塞的程度 若網路壅塞則傳送端限制自己將資料流量送入連線的速率 方法 累積遞增 倍數遞減 (only describe in this course) 低速啟動 回應逾時事件 3.93 / 96

296 3.7 TCP 壅塞控制 (Cont.) TCP 壅塞控制 累積遞增 倍數遞減 增加傳送速率 ( 視窗大小 ), 以探測可用的頻寬 ( 直到發生遺失的狀況 ) 累積遞增 : 每個 RTT, 將 CongWin (congestion window, 壅塞窗格大小 ) 加 1, 直到發生遺失 倍數遞減 : 在發生遺失之後, 將 CongWin 減為一半 看到鋸齒形式 : 頻寬的探測 圖 3.54 累積遞增 倍數遞減的壅塞控制 Exercise / 96 Ex 3.14

297 第三章總結 網際網路傳輸層 傳輸層服務的原則 : 多工 解多工 可靠的資料傳輸 流量控制 壅塞控制 網際網路上的例證和實作 UDP TCP 接下來 : 離開網路 邊緣 ( 應用層 傳輸層 ) 進入網路 核心 ( 網路層 連結層 ) 第 4 5 章 3.95 / 96

298 End of Chapter / 96

299 Chapter 4 Network Layer ( 網路層 ) by R.-W. Hung, Dept. CSIE, CYUT, Taiwan 4.1

300 Topic Overview 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.2 / 92

301 Topic Overview (Cont.) 網際網路網路層 目標 (Goal) 了解網路層服務背後 ( 隱藏 ) 的原理 : 網路層服務模型 轉送 (forward) vs. 路由 (route) 路由器 (router) 如何運作 路由演算法 ( 路徑的選擇 ) 進階課題 : IPv6 網際網路上的例證 實作 應用層傳輸層網路層連結層實體層 4.3 / 92

302 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.4 / 92

303 4.1 簡介 網際網路網路層 網路層 從傳送主機到接收主機傳輸的資料區段 (segment) 在傳送端將資料區段封裝在資料包 (datagram) 中 在接收端, 將資料區段傳送到傳輸層 每一台主機 路由器中都有網路層協定 路由器會檢查經過它的所有 IP 資料段中的標頭欄位 應用層傳輸層網路層連結層實體層 4.5 / 92

304 4.1 簡介 (Cont.) 網路層的通訊 應用層傳輸層網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 應用層傳輸層網路層資料連結層實體層 圖 4.1 網路層 4.6 / 92

305 4.1 簡介 (Cont.) 兩個主要的網路層功能 轉送 (forward): 將封包從路由器的輸入轉送到適當的路由器輸出 路由 ( 繞送 route): 決定封包從來源端到目的端的路由 ( 路徑 ) 路由演算法 (routing algorithm) 比喻 : 路由 : 計畫從來源到目的旅行的過程 轉送 : 經過單一交流道的過程 4.7 / 92

306 4.1 簡介 (Cont.) 兩個主要的網路層功能 (Cont.) 路由演算法 (routing algorithm) 本機轉送表 (forward table) 標頭值輸出連結 每台 router 均儲存一份 forward table, 以決定進入的 packet 該轉送到哪一條輸出 link 2. 如何設定 forward table: 由 routing algorithm 判斷要在 router 的 forward table 插入哪些值, 亦即, 由 routing algorithm 設定其轉送表 抵達封包的標頭值 圖 4.2 路由演算法根據轉送表來轉送資料段 4.8 / 92 Ex 4.1

307 4.1 簡介 (Cont.) 建立連線 (connection setup) 在某些網路架構中網路層的第三個重要功能 ATM 訊框轉播 (frame relay) X.25 在網路層資料包傳送之前, 兩個主機以及介於其間的所有路由器需先建立虛擬連線 (VC,Virtual connection) 路由器介入 此程序稱為 建立連線 網路層及傳輸層的連線服務 : 網路層 : 兩個主機之間 ( 在 VCs 案例中也許可以介入路由器 ) 傳輸層 : 兩個行程之間 4.9 / 92

308 4.1 簡介 (Cont.) 網路服務模型 (network service model) Q: 有哪些服務模型提供給從傳送端到接收端傳輸資料段的通道? ( 網路層可能提供的服務 ) 個別資料區段的服務範例 :(p. 4-7) 傳送保證 (guaranteed delivery) 小於 40 毫秒的傳送保證 (guaranteed delivery with bounded delay) 資料區段流量的服務範例 :(p. 4-7) 依序封包傳送 (in-order packet delivery) 流量的最低頻寬保證 (guaranteed minimal bandwidth) 限制兩個封包之間間隔的改變 (guaranteed maximum jitter) 安全性服務 (security service) Internet 的網路層只提供一種服務 : 盡力而為服務 ( 不提供任何服務 ) 4.10 / 92

309 4.1 簡介 (Cont.) 網路服務模型 (Cont.) 表 4.1 網際網路 ATM CBR ATM ABR 服務模型 網路架構 服務模型 頻寬 保證? 遺失 排序 時序 壅塞指示 網際網路 ATM 盡全力服務 CBR 無 常數速率 無有 無有 無有 無 ( 藉由遺失來推論 ) 不發生壅塞 ATM VBR 保證速率 有 有 有 不發生壅塞 ATM ATM ABR UBR 保證最小速率無 無無 有有 無無 有 無 4.11 / 92

310 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.12 / 92

311 4.2 虛擬線路網路和資料包網路 網際網路網路層 傳輸層 可提供應用程式行程間的可靠連線服務 (TCP) 及不可靠無連線服務 (UDP) 網路層 可提供給傳輸層來源端和目的端主機 可靠的連線服務 虛擬線路網路 (virtual-circuit network) ATM frame relay 不可靠的無連線服務 資料包網路 (datagram network) Internet 與傳輸層服務的差異 服務 : 主機對主機 nonhandshaking handshaking 無連線服務 應用層傳輸層網路層連結層實體層 沒有選擇性 : 單一網路只提供其中一個 ( 如 :Internet 只提供不可靠的無連線服務而無可靠的連線服務 ) 實作 : 在核心 (core- router) 及終端系統 (end system) 連線服務 4.13 / 92

312 4.2.1 虛擬線路網路 (VC) 虛擬線路 (Virtual Circuit) 意義 使用 來源端到目的端的路徑, 如同電話線路 效能良好 沿著來源端到目的端路徑的網路行為 在資料開始傳送前, 必須為每個連結建立連線 拆除 每個封包會承載一個 VC 識別碼 ( 並非目的端主機位址 ) 在來源端到目的端的路徑上, 每個路由器都必須維護每個經過的連線的 狀態 連結 (link) 和路由器 (router) 的資源 ( 頻寬 緩衝區 ) 可能會配置給 VC ( 專用資源 = 預期的伺服器 ) 4.14 / 92

313 4.2.1 虛擬線路網路 (Cont.) 虛擬線路 VC (Cont.) VC 實作 一條 VC 包含了 : 一條來源端至目的端間的路徑 VC 編號, 路徑上的每一個連結都有一個編號 路徑上的每一個路由器轉送表中的紀錄 一個屬於虛擬線路的封包會載送一個 VC 編號 在每一個連結,VC 編號必須改變 新的 VC 編號從轉送表中得來 4.15 / 92

314 4.2.1 虛擬線路網路 (Cont.) 虛擬線路 VC (Cont.) VC 編號 12 data 22 data 32 data A 12 R1 22 R B 介面號碼 R1 路由器的轉送表 (forwarding table) 進入介面進入 VC 編號離開介面離開 VC 編號 router 中的 forward table 會隨 VC 建立及移除而有所變化 圖 4.3 簡單的虛擬線路網路 情境說明 : 主機 A 要求網路在自己與主機 B 間建立一條 VC 網路選擇 : VC 路徑 =A-R1-R2-B 連結的 VC 編號依序為 / 92

315 4.2.1 虛擬線路網路 (Cont.) 虛擬線路 訊號協定 (signal protocol) 用來設定 維護及拆除 VC 用在 ATM 訊框轉播 (frame relay) X.25 並沒有用在現今的網際網路 (internet) 中 應用層傳輸層網路層資料連結層實體層 5. 開始傳送資料 6. 接受資料 4. 連線建立 3. 接受連線 1. 初始連線 2. 進入連線請求 應用層傳輸層網路層資料連結層實體層 圖 4.4 建立虛擬線路 4.17 / 92 Ex 4.2

316 4.2.2 資料包網路 (Datagram network) 資料 ( 封 ) 包網路 (Datagram network) 意義 在網路層不需要建立連線 路由器 : 沒有終端對終端的連線狀態 沒有網路層的 連線 觀念 使用目的端主機位址轉送封包 在同一對來源 - 目的端之間的封包可能會使用不同的路徑 應用層傳輸層網路層資料連結層實體層 1. 送出資料 2. 接收資料 應用層傳輸層網路層資料連結層實體層 圖 4.5 資料包網路 4.18 / 92

317 4.2.2 資料包網路 (Datagram network) 資料包網路 (Cont.) 轉送表 (forwarding table) 40 億個可能的紀錄 (32 位元 IP 位址 ) 路由器不需儲存 40 億個項目 目的端位址範圍 連結 (link) 介面 至 至 至 其它 / 92

318 4.2.2 資料封包網路 (Datagram network) 資料包網路 (Cont.) 轉送表 (Cont.) 最長前置代碼對應 (longest prefix matching) 目的端位址範圍 連結 (link) 介面 至 至 至 其它 3 範例 : (1) DA = 選擇哪一個介面來 forwarding? (2) DA = 選擇哪一個介面來 forwarding? 前置代碼對應 連結 (link) 介面 其它 / 92 Exercise 4.1 Ex 4.3

319 4.2 虛擬線路網路和資料包網路 虛擬線路網路 vs. 資料 ( 封 ) 包網路 (Ref Sect. 1.3) 資料包網路 網際網路 電腦之間的資料交換 彈性的 服務, 沒有嚴格的時限要求 聰明的 終端系統 ( 電腦 ) 能夠適應 執行控制 錯誤復原 網路內部是簡單的 邊緣是複雜的 許多連結型態 不同的特質 統一的服務困難 虛擬線路網路 ATM (Asynchronous Transfer Mode) 來自電話系統 人類的對話 : 嚴格的時限 可靠性的要求 保證服務的需求 愚笨的 終端系統 電話 網路內部是複雜的 邊緣是簡單的 4.21 / 92

320 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.22 / 92

321 4.3 路由器的內部 (Router) 網際網路網路層 路由器架構綜觀 四項元件 輸入埠 (input port) 交換結構 (switch fabric) 輸出埠 (output port) 路由處理器 (routing processor) 圖 4.6 路由器架構 4.23 / 92

322 4.3 路由器 (Cont.) 路由器主要功能 執行路由演算法 / 協定 (RIP OSPF BGP) 將資料封包從輸入轉送到輸出連結 (input link output link) 4.24 / 92

323 4.3 路由器 (Cont.) 輸入埠功能 實體層 : 位元層級的接收 資料連結層 : 例如, 乙太網路見第五章 非集中式的交換 : 給定一個資料封包目的端, 使用輸入埠記憶體中的轉送表來尋找輸出埠 目標 : 以 連線速度 完成輸入埠的處理過程 排隊 : 假如資料封包的抵達速率快於轉送進入交換結構的速率 輸入埠的功能 : 執行實體層功能, 以作為實體連結進入路由器的終端 執行連結層功能, 以和輸入連結遠端的連結層功能進行互動操作 執行查詢和轉送的功能, 以讓轉送進入路由器交換結構的封包, 會出現在適當的輸出埠中 圖 4.7 路由器輸入埠處理 4.25 / 92

324 4.3 路由器 (Cont.) 交換結構 (switch fabric) 將路由器的輸入埠連接到輸出埠 三種交換結構 透過 記憶體 匯流排 互連網路進行交換 圖 4.8 三種路由器交換技術 4.26 / 92

325 4.3 路由器 (Cont.) 交換結構 (Cont.) 三種交換結構 (Cont.) 經由記憶體的交換機制 ( 第一代的路由器 ) 傳統的電腦, 在 CPU 的直接控制下完成交換動作 封包被複製到系統記憶體,CPU 以決定該送往那個輸出埠 速度會被記憶體頻寬所限制 ( 一個資料段會經過兩次匯流排 ) CPU 記憶體 系統匯流排 輸入埠 輸出埠 4.27 / 92

326 4.3 路由器 (Cont.) 交換結構 (Cont.) 三種交換結構 (Cont.) 經由匯流排的交換機制 資料封包經由共享的匯流排從輸入埠記憶體送到輸出埠記憶體 匯流排的競爭 : 交換速度受限於匯流排頻寬 不需經由 routing processor 的介入 若 bus 忙碌, 則封包需在輸入埠中排隊 32 Gbps 匯流排的 Cisco 5600: 對存取路由器及企業路由器是足夠的 4.28 / 92

327 4.3 路由器 (Cont.) 交換結構 (Cont.) 三種交換結構 (Cont.) 經由互連網路的交換機制 克服單一共用匯流排頻寬限制的方法 Banyan 網路 其他的互連網路初始的建立, 是將處理器連接到多處裡器 更進一步的設計 : 將資料封包分割成固定長度的封包單位, 並將封包單位送入交換結構中 Cisco 12000: 經由互連網路可達 60Gbps 的交換速率 ( 棋盤式交換結構 ) 4.29 / 92

328 4.3 路由器 (Cont.) 輸出埠功能 概念 需要緩衝區 當資料封包抵達結構的速率大於傳送速率 排程原則選擇佇列中的資料封包加以傳送 處理過程與輸入埠相反 圖 4.9 路由器輸出埠處理 4.30 / 92

329 4.3 路由器 (Cont.) 輸出埠功能 (Cont.) 輸出埠佇列 (queuing) 當經由交換結構抵達的速率超過輸出連結的速度 佇列排隊 ( 延遲 ) 以及因為輸出埠的緩衝區溢出導致的遺失! 圖 4.10 路由器輸出埠佇列 4.31 / 92

330 4.3 路由器 (Cont.) 輸入埠佇列 Hung1 交換結構速度慢於輸入埠的加總 可能在輸入佇列發生排隊的情形 連線前端 (HOL) 阻塞 : 在佇列最前端排隊的資料封包會阻止佇列中的其它資料封包往前移動 佇列延遲以及導因於輸入緩衝區溢出的遺失! 圖 4.11 路由器輸入埠佇列交換結構的 HOL 攔阻 4.32 / 92 Exercise 4.2 Ex 4.4

331 投影片 32 Hung1 交換結構從輸入埠將封包移至輸出埠的速度 Ruo-Wei Hung, 2011/8/7

332 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.33 / 92

333 4.4 網際網路 IP 協定 網際網路網路層 網際網路的網路層 主機 路由器的網路層功能 : 路由協定 (routing protocol) IP 協定 (InternetProtocol protocol) ICMP 協定 (ICMP protocol) 傳輸層 路由協定 路徑選擇 RIP, OSPF, BGP 轉送表 IP 協定 定址規則 資料包格式 封包處理規則 ICMP 協定 錯誤回報 路由器 訊號 網路層 連結層 實體層 圖 4.12 網際網路中網路層的功能協定 4.34 / 92

334 4.4.1 IP 資料 ( 封 ) 包 (datagram) 格式 IPv4 資料包格式 (p.4-29) IP 協定版本號碼 標頭長度 ( 位元組 ) 資料的 類型 剩餘站數的最大數量 ( 每經過一個路由器時減 1) 版本 16 位元的識別碼 生存期 (TTL) 標頭長度 服務類型 上層協定 32 位元 旗標 資料包長度 分割偏移量 網際網路檢查和 資料 ( 封 ) 包總長度 ( 位元組 ) 用來分割 / 重組 (IPv6 不允許 router 進行分割 ) 傳送資料部分時所使用的上層協定 ( 當資料包到達目的地時, 才會使用此欄位來判斷要交給傳輸層的哪一個協定 TCP/UDP?) 32 位元來源端 IP 位址 32 位元目的端 IP 位址 選項欄位 ( 如果有的話 ) 資料 ( 不固定長度, 通常是 TCP 或 UDP 資料區段 ) 例如 : 時間戳記 路由紀錄 拜訪的路由器特定列表 圖 4.13 IPv4 資料包格式 4.35 / 92

335 4.4.1 IP 資料包格式 (Cont.) TCP/IP 有多少資源負擔? 20 位元組 TCP header 20 位元組 IP header ( 標頭 ) = 40 位元組 + 應用層的訊息負擔 UDP/IP 有多少資源負擔? 4.36 / 92

336 4.4.1 IP 資料包格式 (Cont.) IP 分割 (fragmentation) 與重組 (reassembly) 為何需要將 IP 資料包 (datagram) 分割成較小的資料分段 (fragment)? 網路的連結 (link 資料連結層 ) 具有 MTU (maximum transfer units, 最大的可傳輸大小 ) 最大的連結層訊框 (frame) 不同的連結層型態, 不同的 MTU 過大的 IP 資料包在網路內將被切分 ( 分割 ) 一個資料包 (datagram) 變成好幾個較小的資料分段 只在目的端被 重組 IP 標頭位元用來識別 排序相關的分割 eg., 乙太網路的 MTU=1500 bytes 4.37 / 92

337 4.4.1 IP 資料包格式 (Cont.) IP 分割與重組 (Cont.) 分割 : in = 1 個大的資料包 out = 3 個小的資料分段 重組 ( 只在目的端進行 ) IP Fragmentation Applet: 圖 4.14 IP 資料包的分割與重組 /applets/ip/ipfragmentation.html Ex / 92

338 4.4.1 IP 資料封包格式 (Cont.) IP 分割與重組 (Cont.) 範例 : 4000 位元組的資料包 MTU = 1500 位元組 表 4.2 IP 資料包的分段 (p. 4-33) length =4000 ID =x fragflag =0 offset =0 1 個大的資料包切割成 3 個小的資料分段 資料欄位中有 1480 個位元組 ( 扣除 20bytes header) 偏移量 = ( 以 8 bytes 為單位 ) 1480 / 8 = 185 length =1500 ID =x fragflag =1 offset =0 length =1500 ID =x fragflag =1 offset =185 length =1040 ID =x fragflag =0 offset =370 Ex / 92

339 4.4.2 IPv4 的定址 IPv4 定址 (addressing) 簡介 IP 位址 :32 位元的識別碼, 做為主機 路由器的介面 介面 : 在主機 / 路由器和實體連結的交界處 路由器通常擁有多個介面 主機通常擁有一個介面 IP 位址代表每個介面 = 圖 4.15(a) 介面位址 4.40 / 92

340 4.4.2 IPv4 的定址 (Cont.) 子網路 (Sub-net) IP 位址 : 子網路部分 ( 高階位元 ) 主機部分 ( 低階位元 ) 什麼是子網路? IP 具有相同子網路部分的裝置介面 可以在沒有路由器的狀況下, 實體地互相連結 子網路 圖 4.15(b) 包含 3 個子網路的網路 4.41 / 92

341 4.4.2 IPv4 的定址 (Cont.) 子網路 (Cont.) 表示方法 : 要決定子網路, 將每一個介面和它的主機或路由器分開, 建立分離的網路 每一個分離的網路稱為一個子網路 /24: 最左邊的 24 bits 定義子網路的位址 / / / / 92 子網路遮罩 : /24 圖 4.16 子網路位址

342 4.4.2 IPv4 的定址 (Cont.) 子網路 (Cont.) 有幾個子網路? 圖 4.17 連接到 6 個子網路的三台路由器 4.43 / 92

343 4.4.2 IPv4 的定址 (Cont.) IP 位址分配策略 :CIDR Hung2 CIDR: 無分級跨網域路由法 (Classless InterDomain Routing) 位址內任意長度的子網路部分 位址格式 :a.b.c.d/x, 其中 x 是位址的子網路部份的位元數 子網路部分 主機部分 /23 舊版分級法 classful addressing is net-id is broadcasting IP available IPs = ~ 位元的 A B C 級子網路 C 級子網路的網路遮罩 = /24, 共可容納 個 IP 位址 (0=net-id, broadcast=255) A B 級子網路, 共可容納? 個 IP 位址 廣播的 IP 位址 (broadcasting) = Ex / 92

344 投影片 44 Hung2 CIDR: 唸做 "cider" Ruo-Wei Hung, 2011/8/7

345 4.4.2 IPv4 的定址 (Cont.) 如何取得 / 設定主機 IP 位址? 手動設定在系統管理的檔案中 MS Windows:[ 控制台 ] [ 網路連線 ] [ 設定 ] tcp/ip [ 內容 ] UNIX: /etc/rc.config DHCP: 動態主機配置協定 (Dynamic Host Configuration Protocol) 動態地由 DHCP 伺服器取得位址 隨插即用 的協定 (plug-and-play protocol) 取得臨時 IP 位址 4.45 / 92

346 4.4.2 IPv4 的定址 (Cont.) DHCP ( 動態主機配置協定 ) 目標 當主機連接網際網路時, 主機會從網際網路伺服器以動態方式獲得它的 IP 位址 在使用時會更新它的 IP 位址 允許網路位址動態地重複使用 ( 當連結 上 時會鎖住這個臨時網路位址 ) 提供使用者使用手機來連接網際網路 DHCP 運作 主機廣播 DHCP 搜尋訊息 ( 廣播的 IP 位址 = ) DHCP 伺服器會回應 DHCP 提供訊息 主機請求 IP 位址 : DHCP 請求訊息 DHCP 伺服器傳送位址 : DHCP ack 訊息 4.46 / 92

347 4.4.2 IPv4 的定址 (Cont.) DHCP (Cont.) DHCP 用戶端 伺服端情境 A DHCP 伺服器 DHCP provides B DHCP OK broadcast E 新加入的 DHCP 用戶端 圖 4.20 DHCP 用戶端 伺服端的運作流程 4.47 / 92

348 4.4.2 IPv4 的定址 (Cont.) DHCP (Cont.) DHCP 用戶端 伺服端情境 (Cont.) DHCP 伺服端 : DHCP 搜尋 (broadcasting) 新到來的用戶端 來源端 : , 68 目的端 : , 67 yiaddr: 處理行程 :654 DHCP 請求 (broadcasting) DHCP 提供 (broadcasting) 來源端 : , 67 目的端 : , 68 yiaddrr: 處理行程 :654 生存期 :3600 secs 來源端 : , 68 目的端 : , 67 yiaddrr: 處理行程 :655 生存期 :3600 secs DHCP ACK 來源端 : , 67 目的端 : , 68 yiaddrr: 處理行程 :655 生存期 :3600 secs Time 圖 4.21 DHCP 用戶端 伺服端的互動 Time Ex / 92

349 4.4.2 IPv4 的定址 (Cont.) NAT 網路位址轉譯 (Network Address Translation) 動機 整個區域網路對外界而言, 通常只有一個 IP 位址 同一區域網路內的主機, 可由 router 來設定其 IP 位址 所有區域網路內的主機送出的封包均為同一 IP 位址 外界送入的封包也是同一 IP 位址 Router 如何將外界送入的封包, 正確傳送給區域網路內的主機? NAT 區域網路的外面網路部份 區域網路 ( 例如, 家庭網路 ) / router 所有離開區域網路的資料包都具有相同的單一來源 NAT IP 位址 : , 不同的來源埠號 在這個網路中, 來源端或目的端傳送的資料包, 具有 /24 的來源及主機位址 ( 一般而言 ) / 92

350 4.4.2 IPv4 的定址 (Cont.) NAT (Cont.) 實作 NAT 路由器必須 : 送出資料 ( 封 ) 包時 : 更換每一個送出的資料包 ( 來源 IP 位址 埠號 ) 成為 (NAT IP 位址 新埠號 )... 遠端的主機 ( 區網外 ) 會使用 (NAT IP 位址 新埠號 ) 做為目的端位址, 來做回應 記憶 ( 在 NAT 轉譯表中 ) 每一個 ( 來源端 IP 位址 埠號 ) 到 (NAT IP 位址 新埠號 ) 的轉譯對應 進入資料包時 : 更換每個進入資料封包目的欄位中的 (NAT IP 位址 新埠號 ) 為儲存在 NAT 表中的對應 ( 來源端 IP 位址 埠號 ) 區域網路的外面網路部份 S= , 5501 D= , 80 S= , 3345 D= , 80 S= , 80 S= , 80 D= , router D= , , , / 92

351 4.4.2 IPv4 的定址 (Cont.) NAT (Cont.) 實作 2: NAT 路由器將資料包中的來源位址從 , 3345 轉成 , 5001 並更新轉譯表 區域網路的外面網路部份 S: , D: , 80 NAT 轉譯表 (translation table) WAN 端 LAN 端 , , S: , 3345 D: , : host 傳送資料 ( 封 ) 包到 , S: , 80 D: , : 回應抵達目的端位址 : , 5001 router S: , 80 D: , : NAT 路由器將資料包目的位址從 , 5001 轉成 , 圖 4.22 NAT 網路位址轉譯 4.51 / 92 Ex 4.9

352 4.4.2 IPv4 的定址 (Cont.) NAT 的穿越問題 (traversal) What? 網外用戶端要連接到伺服器的 位址 伺服器位址 區域連線到 LAN ( 用戶端不能使用它的目標位址 ) 只能有一個外部可見的 NATted 位址 : 用戶端? NAT 路由器 4.52 / 92

353 4.4.2 IPv4 的定址 (Cont.) NAT 的穿越問題 (Cont.) How? 解 1: 靜態配置 NAT 給予埠號並請求連結向前進入到伺服器 例如 : ( 埠號 2500) 永遠向前到 ( 埠號 25000) 用戶端? NAT 路由器 4.53 / 92

354 4.4.2 IPv4 的定址 (Cont.) NAT 的穿越問題 (Cont.) How? (Cont.) Hung3 解 2: 通用型隨插即用 (UPnP) 網際網路閘道裝置 (IGD) 協定允許 NATted 主機到 : 學習公用 IP 位址 ( ) 列舉現有的對映埠號 增加 / 移除對映的埠號 ( 租借時間 ) i.e. 自動配置靜態 NAT 的對映埠號 用戶端? IGD , port = , port = 具 UPnP 的 NAT 路由器 4.54 / 92

355 投影片 54 Hung3 Universal Plug and Play Ruo-Wei Hung, 2011/8/8

356 Hung 網際網路控制訊息協定 (Internet Control Message Protocol, ICMP) ICMP 網際網路訊息控制協定 主機和路由器間互相交換網路層資訊的協定 錯誤回報 : 無法到達主機 網路 埠號 協定 回應請求 / 回覆 ( 由 ping 所使用 ) ICMP 通常被視為 IP 的一部份 ICMP 訊息在 IP 封包中載送 ICMP 訊息 類型 代碼 加上導致錯誤的 IP 資料封包的前八個位元組 類型代碼說明 0 0 回應訊息 (ping) 3 0 目的端網路無法連上 3 1 目的端主機無法連上 3 2 目的端協定無法連上 3 3 目的端埠無法連上 3 6 目的端網路未知 3 7 目的端主機未知 4 0 來源抑制訊息 ( 壅塞控制 未使用 ) 8 0 回應請求 (ping) 9 0 路由器通告 10 0 路由器搜尋中 11 0 TTL 過期 12 0 IP 標頭損毀 圖 4.23 ICMP 訊息類型 4.55 / 92

357 投影片 55 Hung4 Internet Control Message Protocol Ruo-Wei Hung, 2011/8/8

358 4.4.3 網際網路控制訊息協定 (Cont.) Traceroute 與 ICMP 來源端傳送一系列的 UDP 資料區段給目的端 Hung5 第一個具有 TTL =1 第二個具有 TTL =2 依此類推 不可能的埠號 當第 n 個資料段抵達第 n 個路由器 : 路由器刪除資料段 接著傳送一個 ICMP 訊息給來源端 ( 類型 11 代碼 0) 訊息中包含了路由器名稱以及 IP 位址 當 ICMP 訊息抵達時, 來源端會計算 RTT Traceroute 會重複這個步驟三次 停止的標準 UDP 資料區段最終會到達目的主機 目的端會回傳 ICMP 主機無法到達 封包 ( 類型 3 代碼 3) 當來源端收到這個 ICMP 時, 則會停止 4.56 / 92

359 投影片 56 Hung5 Time To Live Ruo-Wei Hung, 2011/8/8

360 4.4.4 IPv6 IPv6 第 6 版 IP 協定 動機 32 位元的位址空間 (IPv4) 很快就要使用殆盡了 標頭格式可以幫助處理 / 轉送更快速 標頭的改變可以幫助 QoS (Quality of Service) IPv6 資料封包格式 固定長度的 40 位元組標頭 不允許切割 (4.4.1 節 ) 圖 4.24 IPv6 資料包格式 4.57 / 92

361 4.4.4 IPv6 (Cont.) 從 IPv4 轉換成 IPv6 動機 並不是所有的路由器可以同時升級 無法使用 揭旗日 的方式, 將 IPv4 全部轉成 IPv6 假如網路的運作混和了 IPv4 和 IPv6 的路由器會如何? 混亂 建立通道 在 IPv4 資料包的承載資料中, 封裝完整的 IPv6 資料包 送往 IPv6 路由器 邏輯面 : 實際面 : A B E F 通道 IPv6 IPv6 IPv6 IPv6 A B E F IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 圖 4.26 IPv6 融入 IPv4 的通道建立 4.58 / 92

362 4.4.4 IPv6 (Cont.) 從 IPv4 轉換成 IPv6 (Cont.) 建立通道 (Cont.) 邏輯面 : A B E F 通道 IPv6 IPv6 IPv6 IPv6 實際面 : A B C D E F IPv6 IPv6 IPv6 IPv6 IPv4 IPv4 資料流 : X 來源端 : A 目的端 : F 資料 來源端 :B 目的端 :E 資料流 : X 來源端 : A 目的端 : F 來源端 :B 目的端 :E 資料流 : X 來源端 : A 目的端 : F 資料流 : X 來源端 : A 目的端 : F 資料 資料 資料 A- 到 -B: IPv6 B- 到 -C: IPv6 封裝在 IPv4 裡面 D- 到 -E: IPv6 封裝在 IPv4 裡面 E- 到 -F: IPv6 Exercise 4.6 Exercise 4.5 Exercise 4.4 Exercise / 92

363 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.60 / 92

364 4.5 路由演算法 (routing algorithms) 網際網路網路層 路由 (routing) vs. 轉送 (forward) 轉送 封包到達 router 時,router 會查詢其轉送表 (forwarding table) 並決定將該封包送網哪一個連結介面 (link interface) 0111 路由 (routing) Hung6 網路層必需決定封包從傳送端 router 到接收端 router 所採取的路徑 (path) routing( 繞徑 ) 的工作在於判斷傳送端到接收端, 通過路由器網路的良好路徑 (path/route) source dest 4.61 / 92

365 投影片 61 Hung6 良好路徑 = 成本最小路徑 Ruo-Wei Hung, 2011/8/8

366 4.5 路由演算法 (Cont.) 路由和轉送的交互作用 路由演算法 (routing algorithm) 本機轉送表 (forward table) 標頭值輸出連結 抵達封包的標頭值 / 92 圖 4.2 路由演算法根據轉送表來轉送資料包

367 4.5 路由演算法 (Cont.) 抽象化圖形 (abstract graph) 圖形 :G = (N, E) N = 一組路由器的集合 (node set) = { u, v, w, x, y, z } E = 一組連結的集合 (edge set) = { (u, v), (u, x), (v, x), (v, w), (x, w), (x, y), (w, y), (w, z), (y, z) } [ 註 ] 抽象化圖形在其它的網路應用上也是很有用的 例如 :P2P 中,N 為對等點的集合 而 E 為 TCP 連線的集合 5 2 v 3 w 5 u 1 x y 1 2 z 圖 4.27 電腦網路的抽象化圖形模型 4.63 / 92

368 4.5 路由演算法 (Cont.) 抽象化圖形 (Cont.) 成本 (cost, weight) c(x, y) = 連結 (x, y) 的成本 ( 權重 ) 例如,c(w, z) = 5 成本可能永遠是 1 或是相反地與頻寬相關 或是相反地與壅塞程度相關 路徑 (x 1, x 2, x 3,..., x p ) 的成本 = c(x 1, x 2 ) + c(x 2, x 3 ) c(x p 1, x p ) 問題 :u 和 z 之間的最小成本路徑為何? 路由演算法 : 尋找最小成本路徑的演算法 5 2 v 3 w 5 u 1 x y 1 2 z 圖 4.27 電腦網路的抽象化圖形模型 4.64 / 92

369 4.5 路由演算法 (Cont.) 路由演算法的分類 整體或分散式資訊? (global vs. distributed-decentralized) 整體的 (global) 所有的路由器都擁有完整的拓樸 (topology) 及連結成本 (link cost) 資訊 連結狀態 演算法 (link-state, LS) 最短路徑計算在某台電腦或多台固定電腦中執行 centralized 分散式 (distributed) 路由器只知道實體連結的鄰居以及到鄰居的連結成本 最短路徑經由分散反覆地計算, 以及與鄰居交換資訊 距離向量 演算法 (distance-vector, DV) 靜態的或動態的? (static vs. dynamic) 靜態的 (static) 路徑隨著時間緩慢地改變 動態的 (dynamic) 較快速地改變路徑 週期性的更新 回應連結成本的改變 4.65 / 92

370 4.5.1 連結狀態路由演算法 (LS algorithm) Dijkstra 演算法 已知所有節點的網路拓樸 連結成本 經由 連結狀態廣播 完成 (broadcasting algorithm) 每個節點都擁有一樣的資訊 從一個節點 ( 來源端 ) 開始 到所有其它節點, 計算最小成本路徑 (single source shortest paths) 給定此節點的轉送表 循環式的 (iterative): 在 k 次循環以後, 會知道 k 個目的節點的最小成本路徑 符號 : c(x, y): 從節點 x 到 y 的連結成本 ; = 假如不是直接連結 ( 非鄰居 ) D(v): 目前從來源端到目的端 v 的最小成本路徑的成本值 S: 一組已計算最小成本路徑的節點集合 4.66 / 92

371 4.5.1 連結狀態路由演算法 (Cont.) Dijkstra 演算法 (Cont.) // Initialization 1 S = {u}; // 起始節點 u 2 for all nodes v do 3 if v adjacent to u then D(v) = c(u, v); 4 else D(v) = ; 5 Repeat 6 find w not in S such that D(w) is a minimum; 7 add w to S; 8 for all v adjacent to w and not in S do 9 update D(v) by the following: 10 D(v) = min( D(v), D(w) + c(w, v) ); // new cost to v is either old cost to v or known // shortest path cost to w plus cost from w to v 11 Until all nodes in S; 4.67 / 92

372 4.5.1 連結狀態路由演算法 (Cont.) Dijkstra 演算法 (Cont.) 範例 Initially, S = {u}; w* v x w y z D(w*) Minimum D( ) x S = {u, x}; u v x w y z w* v x w y z D(w*) Minimum D( ) v S = {u, x, v}; Minimum D( ) w S = {u, x, v, y, w}; w* v x w y z D(w*) w* v x w y z D(w*) Minimum D( ) y S = {u, x, v, y}; Minimum D( ) z S = {u, x, v, y, w, z}; w* v x w y z D(w*) w* v x w y z D(w*) / 92

373 4.5.1 連結狀態路由演算法 (Cont.) Dijkstra 演算法 (Cont.) 範例 (Cont.) 結果 從 u 開始的最短路徑樹 : u v w z x y u 的轉送表 : 目的 v x y w z 連結 (u, v) (u, x) (u, x) (u, x) (u, x) Ex / 92

374 4.5.1 連結狀態路由演算法 (Cont.) Dijkstra 演算法 (Cont.) 討論 演算法複雜度 :n 個節點 每個迴圈 : 需要確認不在 S 中的每個節點 w n(n+1)/2 個比較 :O(n 2 ) 可能更有效率的實作 : O(n log n) 可能的問題 震盪現象 ( 圖 4.29) 連結成本 = 該連結的載送負荷 連結的成本可能是不對稱的 ( ) 1 D A 1 1+e 0 0 B 0 e C 1 A 2+e 0 D 1+e 1 B 0 0 C A 0 2+e D 0 0 B 1 1+e C A 2+e 0 D 1+e 1 B 0 e C e 初始 重新計算路由 重新計算 重新計算 4.70 / 92

375 4.5.2 距離向量演算法 (DV algorithm) 距離向量演算法 (Distance-Vector) 概念 分散式 各個節點會從一個或多個直接相鄰的節點中取得一些資訊, 進行運算, 然後, 將結果散佈給其相鄰節點 循環式 持續運作, 直到沒有資訊可以交換 非同步 不需所有節點同時運作 Bellman-Ford 方程式 ( 動態程式規劃 ) d x (y) = min v {c(x, v) + d v (y) } d x (y) = 從 x 到 y 之最小成本路徑的成本 min v 符號作用於 x 的所有相鄰節點 v x v 1 v 1... v k y 4.71 / 92

376 4.5.2 距離向量演算法 (Cont.) Bellman-Ford 方程式 範例 d v (z) = 5 d x (z) = 3 d w (z) = 3 d u (z) = min { c(u, v) + d v (z), c(u, x) + d x (z), c(u, w) + d w (z) } = min {2 + 5, 1 + 3, 5 + 3} = v w 2 u x y 1 可達成最小路徑的節點是最短路徑上的下一站 轉送表 5 2 z 4.72 / 92

377 4.5.2 距離向量演算法 (Cont.) 距離向量演算法 符號 D x (y) = 從 x 到 y 的預估最小成本 節點 x 知道到每一個鄰居 v 的成本 : c(x, v) 節點 x 維護距離向量 :D x = [D x (y):y N ] 節點 x 也維護它的鄰居的距離向量 對每一個鄰居 v, x 維護 D v = [D v (y):y N ] 4.73 / 92

378 4.5.2 距離向量演算法 (Cont.) 距離向量演算法 (Cont.) 基本想法 每一個節點定期地傳送它自己的距離向量預估值給鄰居節點 當一個節點 x 收到來自鄰居的新 D v 預估值, 它會使用 Bellman- Ford 方程式更新它自己的 D v 向量 : D x (y) = min v {c(x, v) + D v (y) }, y N 在一般的自然狀況下, 預估的 D x (y) 會涵蓋真正的最小成本 d x (y) 每一個節點的運作 : DV 演算法 等待 ( 鄰居節點的地區連結成本改變訊息 ) 重新計算預估值 假如到任何一個目的端的 DV 改變了, 通知鄰居節點 4.74 / 92

379 4.5.2 距離向量演算法 (Cont.) 距離向量演算法 (Cont.) 範例 節點 x D x (y) = min{c(x, y) + D y (y), c(x, z) + D z (y)} = min{2+0, 7+1} = 2 目的節點 目的節點 D x (z) = min{c(x, z) + D z (z), c(x, y) + D y (z)} = min{7+0, 2+1} = 3 x 目的節點 2 y 7 1 z 來源節點 x y z x y z 來源節點 x y z x y z 來源節點 x y z x y z 節點 y 目的節點 目的節點 目的節點 來源節點 x y z x y z 來源節點 x y z x y z 來源節點 x y z x y z 節點 z 來源節點 目的節點 x y z x y z 來源節點 目的節點 x y z x y z 來源節點 目的節點 x y z x y z Ex / 92

380 4.5.2 距離向量演算法 (Cont.) 距離向量演算法 (Cont.) 連結成本改變 節點偵測到區域連結成本的改變 1 x 2 y 7 1 z 更新路由資訊, 重新計算距離向量 假如 DV 改變, 通知鄰居節點 連結成本改變情境 在時間點 t0, y 偵測到連結成本的變更, 它會更新距離向量, 並通知相鄰節點 在時間點 t1,z 接收來自 y 的更新訊息, 更新自己的表格 它會計算出到 x 的新最小成本, 並傳送給相鄰節點 在時間點 t2,y 會接收到 z 的更新訊息, 並且更新自己的距離表格 因為 y 的最小成本並沒有改變, 所以 y 不會傳送任何訊息給 z 4.76 / 92

381 4.5.2 LS vs. DV LS 與 DV 演算法的比較 訊息複雜度 LS: n 個節點 E 條連結 O(nE) 個傳送出去的訊息 DV: 只在鄰居之間交換 收斂時間不固定 收斂速度 LS:O(n 2 ) 演算法需要 O(nE) 個訊息 可能有擺動 DV: 收斂速度不固定 可能產生路由迴圈 計算到無窮大的問題 強韌性 : 假如路由器故障會發生什麼問題? LS: DV: 節點可能會廣播不正確的連結成本 每個節點只計算它自己的轉送表 DV 節點可能會廣播不正確的路徑成本 每個節點的轉送表也被其他人所使用 將錯誤傳播到網路中 目前唯二被實際使用在網際網路中的路由演算法 4.77 / 92

382 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.78 / 92

383 4.6 網際網路的路由 網際網路網路層 路由資訊協定 (Routing Information Protocol, RIP) 距離向量演算法 包含在 1982 年的 BSD-UNIX Distribution 中 距離計量 :hop 數目 ( 最大 = 15 個 hops) hop count = cost u v z A C B D y w x 目的端轉送次數 u 1 v 2 w 2 x 3 y 3 z 2 圖 4.34 從來源路由器 A 到各個子網路的 hop 數 ( 站數 ) 4.79 / 92

384 4.6.1 RIP (Cont.) RIP 廣播 距離向量 : 每隔 30 秒使用回應訊息 ( 也稱做通告 ) 在相鄰節點間交換 每個通告 : 自治網路系統內最多達 25 個目的端子網路的清單 RIP 範例 z w x y A D B C 圖 4.35 RIP 範例 4.80 / 92

385 4.6.1 RIP (Cont.) RIP 範例 (Cont.) D 中的路由表 (routing table) 目的端網路 下一個路由器 到目的端所需的轉送次數 w A 2 y B 2 z B 7 x z w x y A D B C 圖 4.35 RIP 範例 4.81 / 92

386 4.6.1 RIP (Cont.) RIP 範例 (Cont.) D 中的路由表 目的端網路 下一個路由器 到目的端所需的轉送次數 w A 2 y B 2 z BA 57 x 從 A 到 D 的通告 : 目的端下一個路由器轉送次數 w -- 1 x -- 1 z C z w x y A D B C 圖 4.35 RIP 範例 4.82 / 92 Ex 4.12

387 第四章導覽流程 網際網路網路層 4.1 簡介 4.2 虛擬線路網路和資料包網路 4.3 路由器的內部 4.4 網際網路 IP 協定 網際網路的轉送 (forward) 及定址 4.5 路由演算法 (routing algorithms) 4.6 網際網路的路由 4.7 廣播與群播路由 (broadcast and multicast) 4.83 / 92

388 4.7 廣播與群播路由 網際網路網路層 廣播路由 (broadcasting) 從來源端傳送封包到所有其它的節點 廣播方式 來源端複製 網路中複製 複製 R1 複製建立 / 傳送 R1 R2 R2 複製 來源端如何決定接收位址? R3 R4 R3 R4 來源端複製網路中複製圖 4.43 來源端複製與網路中複製 4.84 / 92 cycle? 產生無止盡地 broadcast storm 序號控制 reversed path forwarding ( 圖 4.44) (p ) spanning tree broadcasting

389 4.7.1 擴張樹廣播 (spanning tree broadcasting) 擴張樹廣播 首先, 建立一個擴張樹 (spanning tree) 節點沿著擴張樹轉送複本 A A C B C B D D F E F E G G (a) 從 A 點開始廣播 (b) 從 D 點開始廣播 圖 4.45 沿著擴張樹進行廣播 4.85 / 92

390 4.7.1 擴張樹廣播 (spanning tree broadcasting) 中心式擴張樹的建構 選擇中心節點 每個節點會將加入訊息以單點傳播方式傳給中心節點 訊息會被轉送, 直到它抵達一個已經屬於擴張樹的節點 節點沿著擴張樹轉送複本 A A 3 C B C B 4 2 D D F 1 E 5 F E G G (a) 擴展樹建立步驟 (b) 建立的擴展樹 圖 4.46 擴張樹的中心式建構 (E 為中心節點 ) Ex / 92

391 4.7.2 群播 (multicasting) 群播 What? 將資料封包傳送到特定群組的節點 ( 路由器 ) 群播路由的目標 : 找到一棵樹 ( 或是多棵樹 ) 將地區群播群組成員的路由器連結起來 樹 : 不會使用到路由器間的所有路徑 以來源端為基礎 : 從每個來源端到接收端是一個不同的樹 分享樹 : 所有的群組成員都使用相同的樹 分享樹 以來源為基礎的樹 4.87 / 92

392 4.7.2 群播 (Cont.) 建立群播樹的方法 使用來源為基礎的樹 : 一棵樹一個來源端 最短路徑樹 反向路徑傳送 群組分享樹 : 群組只使用一棵樹 最小擴張 (Steiner) 以中心為基礎的樹 4.88 / 92

393 4.7.2 群播 (Cont.) 建立群播樹的方法 (Cont.) 最短路徑樹 : 群播轉送樹 : 從來源端到所有接收端的最短路徑路由所產生的樹 Dijkstra 演算法 S: 來源 說明 R1 1 2 R4 擁有附加群組成員的路由器 R2 5 沒有附加群組成員的路由器 3 4 R5 i 用來轉送的連結 i 表示演算法將連結加入的順序 R3 R6 6 R / 92

394 4.7.2 群播 (Cont.) 建立群播樹的方法 (Cont.) 分享樹 :Steiner 樹 Steiner 樹 : 最小成本樹 連接全部擁有群組成員的路由器 為 NP 完全問題 極佳的試探存在 實際不使用 : 計算複雜度 需要整個網路的資訊 龐大的 : 每當有路由器加入 / 離開時需要重新執行 4.90 / 92

395 4.7.2 群播 (Cont.) 建立群播樹的方法 (Cont.) 以中心為基礎的樹 大家一起分享的單一傳遞樹 (ref. 圖 4.46) 在樹中有一個路由器被標記為 中心 加入 : 邊緣路由器傳送單點傳播的加入訊息給中心路由器 加入訊息由中間的路由器 處理 並轉送到中心 加入訊息會觸碰到此中心現存樹的分枝 或是抵達中心 加入訊息所使用的路徑會變成這個路由器所使用的樹的分枝 假設我們選擇 R6 做為中心 : 說明 R1 3 R4 擁有附加群組成員的路由器 沒有附加群組成員的路由器 R2 2 1 加入訊息所產生的路徑順序 R5 R3 1 R6 R / 92

396 End of Chapter / 92

397 Chapter 5 Link Layer ( 連結層 ) by R.-W. Hung, Dept. CSIE, CYUT, Taiwan 5.1

398 Topic Overview 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 5.6 集線器和交換器 5.2 / 69

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

400 第五章導覽流程 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 5.6 集線器和交換器 5.4 / 69

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

402 5.1 簡介與服務 (Cont.) 連結層的主要工作 來源主機 應用層傳輸層網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 網路層資料連結層實體層 資料連結層網路層實體層 網路層資料連結層實體層 目的主機 應用層傳輸層網路層資料連結層實體層 圖 5.1 連結層 5.6 / 69

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

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

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

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

407 5.1 簡介與服務 (Cont.) 網路卡通訊 傳送端 : 將資料包 (datagram) 封裝在訊框 (frame) 中 加入錯誤確認位元 rdt 流量控制等等 接收端 尋找錯誤 rdt 流量控制等等 取出資料包, 將它傳送到接收端節點 傳送主機 接收主機 資料包 資料包 控制器 控制器 訊框 (frame) 資料包 圖 5.3 網路卡通訊 5.11 / 69 Ex 5.1

408 第五章導覽流程 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 5.6 集線器和交換器 5.12 / 69

409 5.2 錯誤偵測和更正技術 網際網路連結層 錯誤偵測 訊框封包 (frame) 內容 EDC = 錯誤偵測及更正位元 ( 冗餘 ) D = 被錯誤檢查所保護的資料 可能包含標頭欄位 錯誤偵測並不是 100% 可靠的 協定可能會遺漏某些錯誤 ( 不過這很少發生 ) 更大的 EDC 欄位能夠得到更佳的偵測與更正 (datagram) (datagram) 圖 5.4 錯誤偵測與更正的情景 5.13 / 69

410 Hung 同位檢查 (parity checking) 同位檢查 單一的同位元 ( 偶同位 / 奇同位 ) 以偶同位為例 EDC 為 1 bit D 內的 1 的個數 +EDC = 偶數 偵測單一位元錯誤 無法更正錯誤位元 二維同位元 偵測並更正單一位元錯誤 圖 5.5 單一位元的偶同位 同位位元 將 D 切成 i 列 j 行 Exercise 5.1 圖 5.6 二維的偶同位 Ex / 69

411 投影片 14 Hung3 最簡單的錯誤偵測方法 Ruo-Wei Hung, 2011/8/8

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

413 投影片 15 Hung1 CheckSum 較常用於傳輸層 Ruo-Wei Hung, 2011/8/8

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

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

416 投影片 17 Hung2 CRC 較常用於網路卡的連結層 Ruo-Wei Hung, 2011/8/8

417 5.2.3 循環冗餘檢查 (Cont.) 循環冗餘檢查 (Cont.) 作法 : 傳送端 : 將資料位元 D 視為二進位數字 選擇 r+1 個位元為樣本 ( 產生器 ) G 計算 r 個 CRC 位元,R, 使得 R = (D 2 r div 2 G) 取餘數 將 <D, R> 傳送到接收端 接收端 : 擁有 r+1 個位元為樣本 ( 產生器 ) G 計算收到的資料封包 <D, R > 將 <D, R > (2 模數除法 ) 除以 G 若餘數不為 0: 偵測到錯誤 否則,D = D 5.18 / 69

418 5.2.3 循環冗餘檢查 (Cont.) 循環冗餘檢查 (Cont.) CRC 範例 D = G = 1001, r =3 傳送端計算 R = (D 2 r div 2 G) 取餘數 D 2 r = rem(d 2 r div 2 G) = R = 011 <D, R> = 若接收端接收 = <D, R > rem( div ) = 1 0 錯誤發生 XOR 運算 + : XOR /: 運算過程的 + 均不進 ( 借 ) 位 XOR 圖 5.8 簡單的 CRC 運算 Exercise / 69 Ex 5.3

419 第五章導覽流程 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 5.6 集線器和交換器 5.20 / 69

420 5.3 多重存取協定 網際網路連結層 多重存取連結與協定 兩種型態的 連結 : 點對點 撥號存取的 PPP 乙太網路交換器和集線器之間的點對點連結 廣播 ( 分享的線路或媒介 ) 傳統的乙太網路 上傳 HFC 無線區網 5.21 / 69

421 5.3 多重存取協定 (Cont.) 多重存取連結與協定 (Cont.) 圖 5.9 各種多重存取通道 5.22 / 69

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

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

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

425 5.3.1 通道分割協定 通道分割協定 TDM: 時間分割多重存取 (time-division) 每一個 回合 中, 存取通道 每一節點在每一回合中, 得到固定長度的時槽 ( 長度 封包傳送時間 ) 沒有使用的時槽 (slot) 會變成閒置的 範例 :6 個節點站的 LAN,1 3 4 有封包 ; 時槽 為閒置的 6-slot frame 圖 5.10(a) 一個 6 個節點的 TDM 例子 5.26 / 69

426 5.3.1 通道分割協定 (Cont.) 通道分割協定 (Cont.) FDM: 頻率分割多重存取 (frequency-division) 通道頻譜被分割成頻帶 每一節點站分配到固定的頻帶 沒有用到的傳輸頻帶會閒置 範例 :6 個節點站的 LAN, 有封包, 頻帶 為閒置的 FDM cable 頻帶 圖 5.10(b) 一個 6 個節點的 FDM 例子 5.27 / 69

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

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

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

430 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% 5.31 / 69

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

432 投影片 32 Hung4 載波感測多重存取 Ruo-Wei Hung, 2011/8/8

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

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

435 5.3.3 輪流存取協定 (taking-turns protocol) 輪流存取協定 輪詢 (Polling) 主節點輪流邀請從屬節點傳送資料 問題 : 輪詢的額外負擔 延遲 單點故障 ( 主節點 ) 資料 輪詢 主節點 資料 從屬節點 5.35 / 69

436 5.3.3 輪流存取協定 (Cont.) 輪流存取協定 (Cont.) 記號 ( 令牌 / 權杖 ) 傳遞 (Token passing) 控制記號 (token) 依序從一個節點傳到下一個節點 當節點擁有 token 時, 才可傳送封包 問題 : 記號的額外負擔 延遲 單點故障 (token 遺失 ) 邏輯連接成環狀 (ring)? OK ( 無資料傳輸 ) T T data 5.36 / 69

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

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

439 第五章導覽流程 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 5.6 集線器和交換器 5.39 / 69

440 5.4 連結層定址 網際網路連結層 MAC 位址 (media access control) 32 位元的 IP 位址 (IPv4) IPv6? 網路層位址 用來接收資料包 (datagram), 到目的 IP 子網路 MAC ( 或是區域網路 實體 乙太網路 ) 位址 (LAN 位址 ) 連結層位址 用來接收訊框 (frame) 從一個介面到另一個實體連結介面 ( 同一個網路 ) 48 位元 MAC 位址 ( 大多數的 LAN) 燒錄在網路卡 (NIC) 的 ROM 中, 有時候是在軟體裡 (virtual machine) 5.40 / 69

441 5.4 連結層定址 (Cont.) MAC 位址 (LAN 位址 ) 每一張網路卡都具有唯一的 MAC 位址 (48 bits) 廣播位址 = FF-FF-FF-FF-FF-FF 1A-2F-BB AD = 網路卡 LAN ( 有線或無線的 ) F7-2B D7-FA-20-B0 0C-C4-11-6F-E3-98 圖 5.16 每個連接到 LAN 的網路卡都有獨一無二的 MAC 位址 5.41 / 69

442 5.4 連結層定址 (Cont.) MAC 位址 (Cont.) MAC 位址的分配 由 IEEE (Institute of Electrical and Electronics Engineers, 機構管理 網路卡製造商向 IEEE 購買部分的 MAC 位址 ( 保證唯一性 ) MAC 位址 vs. IP 位址 MAC 位址 : 如同身份證號碼 IP 位址 : 如同郵寄地址 MAC 位址是可攜性 可以將網路卡從一個 LAN 帶到另一個 LAN IP 位址不具可攜性 與節點連接的 IP 子網路相關 5.42 / 69

443 5.4 連結層定址 (Cont.) IP 與 MAC 位址 來源端 + 目的端 來源端 + 目的端 應用層傳輸層 IP 位址 MAC 位址實體層 1A-2F-BB AD LAN ( 有線或無線的 ) F7-2B D7-FA-20-B0 0C-C4-11-6F-E / 69 Ex 5.5

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

445 投影片 44 Hung5 Hung6 ARP 只用於區網 ; 而 DNS 可解析 internet 所有 IP 位址 Ruo-Wei Hung, 2011/8/9 Time To Live Ruo-Wei Hung, 2011/8/9

446 5.4 連結層定址 (Cont.) ARP (Cont.) ARP 表 IP 位址 MAC 位址 TTL C-B2-2F90-75-B1 13:46: B2-2F-54-1A-00 12:43: F7-2B :50:00 圖 5.18 節點 中可能的 ARP 表格 5.45 / 69

447 5.4 連結層定址 (Cont.) 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 表格 5.46 / 69

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

449 5.4 連結層定址 (Cont.) S=A; D=B S=A; D=R S=A; D=B S=R; D=B ARP (Cont.) ARP 協定 (Cont.) 應用層傳輸層 IP 位址 MAC 位址實體層 應用層傳輸層 IP 位址 MAC 位址實體層 情境二 (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 C-E8-FF-55 A E6-E BB-4B 1A-23-F9-CD-06-9B 88-B2-2F-54-1A-0F CC-49-DE-D0-AB-7D R B 49-BD-D2-C7-56-2A Exercise 5.6 Ex / 69

450 第五章導覽流程 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 (Ethernet) 5.6 集線器和交換器 5.49 / 69

451 5.5 乙太網路 網際網路連結層 乙太網路 (Ethernet) 主要的 有線區域網路技術 便宜 100 Mbps 網卡只要 $20! 第一個廣泛使用的區域網路技術 比記號環區域網路以及 ATM 簡單 便宜 速度不斷地提升 :10 Mbps ~ 10 Gbps 圖 5.20 Metcalfe s 的原始乙太網路設計圖 5.50 / 69

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

453 投影片 51 Hung7 中心通訊設備若使用 hub( 集線器 ), 則會發生碰撞 Ruo-Wei Hung, 2011/8/9

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

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

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

457 投影片 54 Hung8 Hung9 NIC = Network Interface Card Ruo-Wei Hung, 2011/8/9 CSMA/CD = Carrier Sense Multiple Access with Collision Detection Ruo-Wei Hung, 2011/8/9

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

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

460 投影片 56 Hung10 BASE: 基頻乙太網路, LAN 只有載送乙太網路的資料流. T: Twisted, 雙絞銅芯線. Ruo-Wei Hung, 2011/8/9

461 第五章導覽流程 網際網路連結層 5.1 連結層簡介與服務 5.2 錯誤偵測和更正技術 5.3 多重存取協定 5.4 連結層定址 5.5 乙太網路 (Ethernet) 5.6 集線器 (hub) 和交換器 (switch) 5.57 / 69

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

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

464 5.6 集線器和交換器 (Cont.) 交換器 (Cont.) 允許多個同時傳送 主機有專用且直接的連結線到交換器 交換器有緩衝區, 可以緩衝封包 乙太網路協定使用在每一個進入的連結 但是沒有碰撞 全雙工 每個連結都擁有它的碰撞範圍 交換器 :A- 到 -A 與 B- 到 -B 可同時傳送, 且不會發生碰撞 使用 hub 則是不可能的 A C B B A C 六個交換器介面 ( ) 5.60 / 69

465 5.6 集線器和交換器 (Cont.) 交換器 (Cont.) 交換器表 (switch table) Q: 交換器如何知道 A 可通過到達介面 4 B 可通過到達介面 5? A: 每一個交換器都有一個交換表, 其欄位如下 : 主機 MAC 位址 ; 到達主機的介面 ; 時間標籤 類似路由器表 (routing table) Q: 如何建立 維持在交換表中的通道? A: 一些像是路由器的協定 (routing protocol) A C B C B 5.61 / 69 A 六個交換器介面 ( )

466 5.6 集線器和交換器 (Cont.) 交換器 (Cont.) 交換器表的自我學習 (self-learning) 交換器會學習哪一個主機經由哪一個介面可以到達 當訊框抵達時, 交換器會 學習 傳送端的位置 : 進入的 LAN 區段 (LAN segment) 在交換表中紀錄 傳送端 ; 位置介面 對 Source = A Dest = A A A A 交換器表 ( 初始為空 ) C B MAC 位址 到達主機的介面 TTL A B A C 六個交換器介面 ( ) 5.62 / 69

467 5.6 集線器和交換器 (Cont.) 交換器 (Cont.) 以交換器互相連結 交換器之間可以連接在一起 Q: 從 A 傳送封包到 F, 如何知道 S 1 把預定的訊框轉送到 F via S 4 與 S 2? A: 自我學習!(How? Thanking...) S 4 S 1 S 3 A B C S 2 D F I E G H 5.63 / 69

468 5.6 集線器和交換器 (Cont.) 機構網路 到外部網路 電子郵件伺服器 路由器 web 伺服器 交換器 IP 子網路 集線器 集線器 集線器 圖 5.26 同時使用集線器 乙太網路交換器 及路由器的機構網路 5.64 / 69

469 5.6 集線器和交換器 (Cont.) 交換器 vs. 路由器 都是儲存並轉送的裝置 路由器 : 網路層裝置 ( 檢驗網路層標頭 ) 交換器 : 連結層裝置 路由器維護路由表, 實作路由演算法 交換器維護交換表, 實作過濾 學習演算法 5.65 / 69

470 5.6 集線器和交換器 (Cont.) 比較總表 集線器 hub 路由器 router 交換器 switch 流量隔離 無 有 有 隨插即用 有 無 有 最佳化路由 無 有 無 直接傳送 有 無 有 5.66 / 69 Ex 5.8

471 第五章總結 網際網路連結層 ( 資料 ) 連結層服務的原則 錯誤偵測 更正 分享寬頻通道 : 多種存取 連結層位址 各種連結層技術的例證和實作 乙太網路 交換器區域網路 PPP 連結層的虛擬網路 5.67 / 69

472 End of Chapter / 69

473 課程結束謝謝同學本學期的配合 5.69 / 69