绕送演算法距离向量课件

4.14.24.34.44.54.6第1頁，共241頁4.74.8n傳輸層是藉由網路層主機到主機的通訊服務，來提供各種形式的行程到行程通訊服務。n網路層會如何實作主機到主機的通訊服務。n網路層是存在於網路上的每台主機與路由器之中。n探討建構封包投遞服務的兩大途徑資料報與虛擬迴路模。n轉送所牽涉的是在單單單單一一一一路由器內，將封包由輸入連結傳送到輸出連結的過程。4.14.24.34.44.54.6第2頁，共241頁4.74.8n繞送則跟網路中所所所所有有有有的的的的路由器都有關，這些路由器會透過繞送協定進行整體性的互動，以決定封包從來源節點移動到目的節點時所要採取的路徑。n檢視路由器的內部包括硬體架構以及組織n探討網路層的定址以及IPv4 的資料報格式。n探討網路位址轉譯(network address translation，NAT)、資料報分段(datagram fragmentation)、網際網路控制訊息協定(Internet Control Message Protocol，ICMP)以及IPv6。4.14.24.34.44.54.6第3頁，共241頁4.74.8n繞送演算法的職責便是判斷從傳送端到接收端的良好路徑(意即路由)。n重點放在兩類最普遍的演算法上：連結狀態(link-state)演算法以及距離向量(distance-vector)演算法。n階層式的繞送方法。n述網際網路其自治系統內部繞送協定(RIP、OSPF 和IS-IS)，以及跨自治系統繞送協定，BGPn廣播及群播繞送。4.14.24.34.44.54.6第4頁，共241頁4.74.84.1導言導言n路由器的主要任務便是將資料報從輸入連結轉送到輸出連結。n路由器並不會執行諸如我們在第二章跟第三章所檢視過的應用層及傳輸層協定。4.14.24.34.44.54.6第5頁，共241頁4.74.84.1.1轉送與繞送轉送與繞送n兩項重要的網路層功能：轉轉轉轉送送送送 (Forwarding)(Forwarding)。當封包抵達路由器的輸入連結時，路由器必須將這份封包移動到適當的輸出連結。繞繞繞繞送送送送 (Routing)(Routing)。網路層必須判斷封包從傳送端流向接收端時所採取的路由或路徑。用來計算這些路徑的演算法便稱為 繞繞繞繞 送送送送 演演演演 算算算算 法法法法 (routing algorithm)(routing algorithm)。4.14.24.34.44.54.6第6頁，共241頁4.74.84.14.24.34.44.54.6第7頁，共241頁4.74.8n許多作者在討論網路層時，經常會交替使用繞繞繞繞送送送送和轉轉轉轉送送送送這兩個詞彙。本書會較精確地使用這兩個詞彙。n n轉轉轉轉送送送送意指在路由器本機進行的動作，會將封包從輸入連結介面傳輸到適當的輸出連結介面。n n繞繞繞繞送送送送指的則是關於整體網路的程序，會判斷封包由來源端到目的端所採取的端點到端點路徑。4.14.24.34.44.54.6第8頁，共241頁4.74.8n每具路由器都擁有一份轉轉轉轉送送送送表表表表 (forwarding(forwarding table)table)。路由器會檢查到來的封包標頭中某欄位的數值，然後使用這個標頭數值來查詢路由器轉送表以轉送封包。n你現在可能會好奇，要如何設定路由器的轉送表。n繞送演算法會判斷要在路由器的轉送表中插入哪些數值。n路由器都會接收繞送協定訊息，以用來設定其轉送表。4.14.24.34.44.54.6第9頁，共241頁4.74.8n人工設定可能會比較容易出錯，而且速度慢上許多。n n封封封封包包包包交交交交換換換換器器器器 (packet(packet switch)switch)這個詞保留給一般性的封包交換裝置。n某些封包交換器，我們稱之為連連連連結結結結層層層層交交交交換換換換器器器器 (link-layer(link-layer switch)switch)，則是根據連結層訊框欄位中的數值來下其轉送判定；因此我們把它們稱為連結層(第二層)裝置。4.14.24.34.44.54.6第10頁，共241頁4.74.8n其它的封包交換器，叫作路路路路由由由由器器器器 (router)(router)，則是根據網路層欄位的數值來下其轉送判定。n因此我們把路由器稱為網路層(第三層)裝置，但是也必須實作第二層協定，因為第三層裝置需要第二層的服務才能實作它們(第三層)的功能。4.14.24.34.44.54.6第11頁，共241頁4.74.84.14.24.34.44.54.6第12頁，共241頁4.74.8建立連線建立連線n網路層有兩項重要功能，轉送跟繞送。n某些網路層架構例如ATM、訊框轉播(Frame relay)，MPLS(我們在5.8 節中會探討)要求，在指定的來源端到目的端連線中，網路層資料報在可以開始流動以前，在此連線所選擇的來源端到目的端路徑上的所有路由器都要先進行握手程序來設定其狀態。4.14.24.34.44.54.6第13頁，共241頁4.74.84.1.2網路服務模型網路服務模型n n網網網網路路路路服服服服務務務務模模模模型型型型 (network(network service service model)model)定義了傳送端與接收端主機之間的端點到端點封包傳輸特性。4.14.24.34.44.54.6第14頁，共241頁4.74.8n網路層可能提供的一些服務包括：投遞保障投遞保障投遞保障投遞保障 (guaranteed delivery)(guaranteed delivery)。有有有有限限限限延延延延遲遲遲遲的的的的投投投投遞遞遞遞保保保保障障障障 (guaranteed(guaranteed delivery delivery with with bounded delay)bounded delay)。依序的封包投遞依序的封包投遞依序的封包投遞依序的封包投遞 (in-order packet delivery)(in-order packet delivery)。最低頻寬保障最低頻寬保障最低頻寬保障最低頻寬保障(guaranteed minimal bandwidth(guaranteed minimal bandwidth)。最大時基誤差保障最大時基誤差保障最大時基誤差保障最大時基誤差保障 (guaranteed maximum jitter)(guaranteed maximum jitter)安全性服務安全性服務安全性服務安全性服務 (Security service)(Security service)。4.14.24.34.44.54.6第15頁，共241頁4.74.8n網際網路的網路層只提供一種服務，稱為盡盡盡盡力力力力而而而而為的服務為的服務為的服務為的服務 (best-effort service)(best-effort service)。n n盡盡盡盡力力力力而而而而為為為為的的的的服服服服務務務務，意思大概就是不不不不提提提提供供供供任任任任何何何何服服服服務務務務的婉轉說法。4.14.24.34.44.54.6第16頁，共241頁4.74.84.14.24.34.44.54.6第17頁，共241頁4.74.8n除了網際網路的盡力而為服務外，我們確實有其他選擇存在。兩種較重要的ATM 服務模型分別是固定位元傳輸速率，以及可用位元傳輸速率服務：固固固固定定定定位位位位元元元元傳傳傳傳輸輸輸輸速速速速率率率率ATMATM網網網網路路路路服服服服務務務務 constant constant bit bit rate(CBR)ATM network servicerate(CBR)ATM network service。可可可可用用用用位位位位元元元元傳傳傳傳輸輸輸輸速速速速率率率率ATMATM網網網網路路路路服服服服務務務務 available available bit bit rate(ABR)ATM network servicerate(ABR)ATM network service。4.14.24.34.44.54.6第18頁，共241頁4.74.84.2虛擬迴路與資料報網路虛擬迴路與資料報網路n網際網路的傳輸層讓每個應用程式都可以在兩種服務中做選擇：UDP，無連線的服務。TCP，連線導向的服務。類似地，網路層也可以在兩個主機之間提供無連線的服務或連線服務。n在網路層只有提供連線服務的計算機網路稱為虛虛虛虛擬擬擬擬迴迴迴迴路路路路網網網網路路路路 virtual-circuit virtual-circuit(VC)(VC)networknetwork，而在網路層只提供無連線服務的計算機網路則稱為資資資資料報網路料報網路料報網路料報網路 (datagram network)(datagram network)。4.14.24.34.44.54.6第19頁，共241頁4.74.84.2.1虛擬迴路網路虛擬迴路網路nATM 與訊框轉播則屬於虛擬迴路網路；因此，它們會在網路層使用連線服務。n這些網路層連線稱為虛虛虛虛擬擬擬擬迴迴迴迴路路路路 (virtual(virtual circuitcircuit，VC)VC)。n一條VC 包含了(1)一條從來源端主機到目的端主機之間的路徑(亦即一連串的連結及路由器)。(2)VC 編號，路徑上的每道連結都會有一個編號。4.14.24.34.44.54.6第20頁，共241頁4.74.8(3)路徑上所有路由器的轉送表項目。屬於某條虛擬迴路的封包，會在其標頭中夾帶一則VC編號。因為虛擬迴路在每道連結上的VC 編號可能都有所不同，所以每台中介的路由器都必須將每個通過的封包VC 編號換成新的VC 編號。這個新的VC 編號是從轉送表中取得。4.14.24.34.44.54.6第21頁，共241頁4.74.84.14.24.34.44.54.6第22頁，共241頁4.74.8n對VC 網路而言，每台路由器的轉送表都包含VC 編號的轉譯資訊；例如，R1 的轉送表看起來可能像是：4.14.24.34.44.54.6第23頁，共241頁4.74.8n每當有一條新的，跨越某台路由器的VC 被建立起來時，便會有一筆新項目被加入到轉送表中。n同樣地，當VC 終結時，其路徑上每份轉送表中的對應項目也都會被移除。n在VC 網路中，網路的路由器必須維護運作中之連線的連線狀態資訊連線狀態資訊連線狀態資訊連線狀態資訊(connection state(connection state information)information)。n更清楚地說，每當跨越某台路由器的新連線建立時，就必須加入一筆新的連線項目到該具路由器的轉送表中；每當解除一筆連線時，就必須從轉送表中移除一筆項目。4.14.24.34.44.54.6第24頁，共241頁4.74.8n在虛擬迴路中，我們可以指出三個階段：建立建立建立建立 VCVC。資料傳輸資料傳輸資料傳輸資料傳輸。VCVC斷線斷線斷線斷線。n在傳輸層連線建立期間，只有這兩台終端系統會參與決定其傳輸層連線的參數。n另一方面來說，在 VC 的網路層中，兩兩兩兩台台台台終終終終端端端端系系系系統統統統之之之之間間間間路路路路徑徑徑徑上上上上的的的的所所所所有有有有路路路路由由由由器器器器都都都都會會會會參參參參與與與與VCVC的的的的建建建建立立立立，而且每台路由器都完全知曉所有通過它的而且每台路由器都完全知曉所有通過它的而且每台路由器都完全知曉所有通過它的而且每台路由器都完全知曉所有通過它的VCVC。4.14.24.34.44.54.6第25頁，共241頁4.74.8n終端系統送入網路以開啟或關閉VC 的訊息，以及在路由器之間傳遞以設定VC(意即，修改路由器轉送表中的連線狀態)的訊息，通常稱為信信信信號號號號訊訊訊訊息息息息 (signaling(signaling message)message)，用來交換這些訊