計(jì)算機(jī)網(wǎng)絡(luò)net1-new課件

計(jì)算機(jī)網(wǎng)絡(luò)原理

網(wǎng)絡(luò)層尹霞yxia@清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)研究所2000年11月21日計(jì)算機(jī)網(wǎng)絡(luò)原理

網(wǎng)絡(luò)層尹霞網(wǎng)絡(luò)層主要內(nèi)容網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的地位網(wǎng)絡(luò)層需要解決的問(wèn)題數(shù)據(jù)報(bào)和虛電路網(wǎng)絡(luò)層提供的服務(wù)擁塞控制算法擁塞控制的基本原理開(kāi)環(huán)控制擁塞預(yù)防策略通信量整形(漏桶和令牌桶)流說(shuō)明閉環(huán)控制虛電路網(wǎng)絡(luò)中的擁塞控制抑制分組負(fù)載丟棄Internet網(wǎng)絡(luò)層協(xié)議路由算法 最優(yōu)化原則最短路徑路由算法洪泛算法基于流量的路由算法距離向量路由算法鏈路狀態(tài)路由算法分級(jí)路由網(wǎng)絡(luò)互聯(lián)技術(shù)網(wǎng)絡(luò)互聯(lián)設(shè)備常用網(wǎng)絡(luò)互聯(lián)技術(shù)級(jí)聯(lián)虛電路無(wú)連接網(wǎng)絡(luò)互聯(lián)隧道技術(shù)互聯(lián)網(wǎng)路由分段防火墻計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層主要內(nèi)容網(wǎng)絡(luò)層概述路由算法 計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的位置當(dāng)今流行的通信技術(shù)傳統(tǒng)的電信網(wǎng)絡(luò)：線路交換、x.25、幀中繼、ATM。計(jì)算機(jī)網(wǎng)絡(luò)：ARPANET、INTERNET等。有線電視網(wǎng)絡(luò)。計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)層至關(guān)重要網(wǎng)絡(luò)層是通信子網(wǎng)的最高層，關(guān)系著整個(gè)網(wǎng)絡(luò)的運(yùn)行控制。網(wǎng)絡(luò)層需要解決的問(wèn)題是確定分組從源地址到目的地址是如何路由的。網(wǎng)絡(luò)層利用數(shù)據(jù)鏈路層提供的服務(wù)，為傳輸層提供服務(wù)。網(wǎng)絡(luò)層處理端到端傳輸?shù)淖畹蛯印Ｔ趶V播網(wǎng)絡(luò)中，路由選擇很簡(jiǎn)單，所以網(wǎng)絡(luò)層也很薄，甚至不存在。而在大型網(wǎng)絡(luò)中，分組不得不跨越若干個(gè)網(wǎng)絡(luò)到達(dá)目的地址，這其中的種種問(wèn)題就需要由網(wǎng)絡(luò)層來(lái)解決。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層的位置當(dāng)今流行的通信技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)原理—網(wǎng)絡(luò)層需要解決的問(wèn)題網(wǎng)絡(luò)層為了能夠了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，以便選擇路由，需要解決以下問(wèn)題：屏蔽各種不同類型網(wǎng)絡(luò)之間的差異需要統(tǒng)一數(shù)據(jù)格式需要統(tǒng)一網(wǎng)絡(luò)地址實(shí)現(xiàn)全網(wǎng)的數(shù)據(jù)傳輸建立跨越網(wǎng)絡(luò)的虛電路網(wǎng)絡(luò)之間實(shí)現(xiàn)分組的尋址和轉(zhuǎn)發(fā)網(wǎng)絡(luò)層的兩種實(shí)現(xiàn)方式虛電路(virtualcircuit)：提供面向連接的服務(wù)。類似于電話，先建立連接，之后依次發(fā)送分組，最后關(guān)閉連接。避免對(duì)每個(gè)分組進(jìn)行路由。數(shù)據(jù)報(bào)(datagram)：提供無(wú)連接的服務(wù)。類似于發(fā)送信件。對(duì)每個(gè)數(shù)據(jù)報(bào)(對(duì)于無(wú)連接中的獨(dú)立分組稱作數(shù)據(jù)報(bào))分別進(jìn)行路由。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層需要解決的問(wèn)題網(wǎng)絡(luò)層為了能夠了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，以通信交換技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)總是由資源子網(wǎng)和通信子網(wǎng)組成。通信交換技術(shù)是指數(shù)據(jù)信息如何在通信子網(wǎng)的各個(gè)結(jié)點(diǎn)之間進(jìn)行傳輸?shù)?。通常存在三種交換技術(shù)：線路交換、報(bào)文交換和分組交換。還存在某幾個(gè)技術(shù)的融合，即混合交換。線路交換(circuitswitching)在網(wǎng)絡(luò)中利用可切換的物理通信線路直接連接通信雙方。最常見(jiàn)的例子是電話系統(tǒng)。線路交換包括三種狀態(tài)：線路建立、數(shù)據(jù)傳送、線路拆除。線路交換方式中通道是專用的，利用效率低，并存在延遲。報(bào)文交換(messageswitching)是指信息以報(bào)文(邏輯上完整的信息段)為單位進(jìn)行存儲(chǔ)轉(zhuǎn)發(fā)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層通信交換技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)總是由資源子網(wǎng)和通信子網(wǎng)組成。通信交換HHHAR5R2R3Router1R4HBMMMMM存儲(chǔ)轉(zhuǎn)發(fā)(StoreandForward)發(fā)送報(bào)文的主機(jī)在發(fā)送之前，要將報(bào)文的目的地址附加在報(bào)文前面。然后將報(bào)文發(fā)送到網(wǎng)絡(luò)中的結(jié)點(diǎn)中。每個(gè)網(wǎng)絡(luò)中的結(jié)點(diǎn)將完整地接收?qǐng)?bào)文，暫存報(bào)文，然后將報(bào)文發(fā)送到下一個(gè)更接近目的主機(jī)的結(jié)點(diǎn)中。如此操作，直至將報(bào)文發(fā)送到目的主機(jī)為止。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層HHHAR5R2R3Router1R4HBMMMMM存儲(chǔ)轉(zhuǎn)發(fā)分組交換(packetswitching)分組交換結(jié)合報(bào)文交換和線路交換的優(yōu)點(diǎn)，采用存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制，但是規(guī)定了傳輸數(shù)據(jù)的單位長(zhǎng)度。過(guò)長(zhǎng)的報(bào)文被分成較小的單位(分組packet)，依次發(fā)送。如何管理這些分組的正確傳輸：數(shù)據(jù)報(bào)和虛電路。數(shù)據(jù)報(bào)(datagram)：每個(gè)分組被單獨(dú)處理。每個(gè)分組帶有自己的目的地址和序號(hào)被發(fā)出，由通信子網(wǎng)中的結(jié)點(diǎn)進(jìn)行路由選擇。在所有分組到達(dá)了目的主機(jī)后，再將各個(gè)分組按照序號(hào)編排起來(lái)。虛電路(virtualcircuit)：在發(fā)送任何分組之前，首先在發(fā)送主機(jī)和目的主機(jī)之間建立一條邏輯連接，即在通信子網(wǎng)中確定一條用于本次傳輸數(shù)據(jù)用的結(jié)點(diǎn)序列。建立虛電路后，所有的分組都將按照循序依次被發(fā)送到目的主機(jī)。當(dāng)所有的分組都發(fā)送之后，虛電路將被拆除。在虛電路方法中，每個(gè)分組無(wú)須進(jìn)行路徑選擇。每個(gè)主機(jī)可以和另一個(gè)主機(jī)建立若干個(gè)虛電路，每個(gè)主機(jī)也可以同時(shí)和若干主機(jī)個(gè)建立虛電路。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分組交換(packetswitching)分組交換結(jié)合報(bào)文虛電路與數(shù)據(jù)報(bào)的比較計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層虛電路與數(shù)據(jù)報(bào)的比較計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)虛電路與數(shù)據(jù)報(bào)之間的權(quán)衡路由器內(nèi)存空間與帶寬的權(quán)衡虛電路占用路由器中的表空間每個(gè)數(shù)據(jù)報(bào)都攜帶完整的目的/源地址，浪費(fèi)帶寬連接建立時(shí)間與地址查找時(shí)間的權(quán)衡虛電路需要在建立連接時(shí)花費(fèi)時(shí)間數(shù)據(jù)報(bào)則在每次路由時(shí)過(guò)程復(fù)雜服務(wù)質(zhì)量和健壯性的權(quán)衡虛電路方式很容易保證服務(wù)質(zhì)量QoS(QualityofService)，適用于實(shí)時(shí)操作，但比較脆弱。通信線路的故障，對(duì)于虛電路而言有時(shí)是致命的。數(shù)據(jù)報(bào)不太容易保證服務(wù)質(zhì)量，但是對(duì)于通信線路的故障，卻很容易得到補(bǔ)償。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層虛電路與數(shù)據(jù)報(bào)之間的權(quán)衡路由器內(nèi)存空間與帶寬的權(quán)衡計(jì)算機(jī)MHHHAR5R2R1R3R4HBM1M3M2M1M2M3M1M2M3舉例請(qǐng)判斷是虛電路還是數(shù)據(jù)報(bào)？計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層MHHHAR5R2R1R3R4HBM1M3M2M1M2M3M網(wǎng)絡(luò)層提供的服務(wù)網(wǎng)絡(luò)層為傳輸層提供的服務(wù)面向連接服務(wù)：將復(fù)雜的功能放在網(wǎng)絡(luò)層(通信子網(wǎng))。建立連接傳輸數(shù)據(jù)拆除連接無(wú)連接服務(wù)：將復(fù)雜的功能放在傳輸層。只負(fù)責(zé)傳輸分組。通信子網(wǎng)提供的服務(wù)(面向連接或無(wú)連接)與通信子網(wǎng)結(jié)構(gòu)(虛電路或數(shù)據(jù)報(bào))無(wú)關(guān)。面向連接的服務(wù)用虛電路來(lái)實(shí)現(xiàn)(比較合理)面向連接的服務(wù)用數(shù)據(jù)報(bào)來(lái)實(shí)現(xiàn)面向無(wú)連接的服務(wù)用虛電路來(lái)實(shí)現(xiàn)面向無(wú)連接的服務(wù)用數(shù)據(jù)報(bào)來(lái)實(shí)現(xiàn)(比較合理)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層提供的服務(wù)網(wǎng)絡(luò)層為傳輸層提供的服務(wù)計(jì)算機(jī)網(wǎng)絡(luò)通信子網(wǎng)結(jié)構(gòu)及其提供的服務(wù)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層通信子網(wǎng)結(jié)構(gòu)及其提供的服務(wù)計(jì)算機(jī)網(wǎng)絡(luò)原理——小結(jié)—網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的地位確定分組從源地址到目的地址如何進(jìn)行路由。網(wǎng)絡(luò)層需要解決的問(wèn)題屏蔽各種不同類型網(wǎng)絡(luò)之間的差異實(shí)現(xiàn)全網(wǎng)的數(shù)據(jù)傳輸網(wǎng)絡(luò)層的兩種實(shí)現(xiàn)方式——數(shù)據(jù)報(bào)和虛電路都屬于分組交換，采用存貯轉(zhuǎn)發(fā)機(jī)制。數(shù)據(jù)報(bào)(datagram)：每個(gè)分組被單獨(dú)處理，每個(gè)分組帶有自己的目的地址和序號(hào)被發(fā)出。虛電路(virtualcircuit)：先在發(fā)送主機(jī)和目的主機(jī)之間建立一條邏輯連接，所有的分組按照循序依次被發(fā)送。最后虛電路將被拆除。在虛電路方法中，每個(gè)分組無(wú)須進(jìn)行路徑選擇。網(wǎng)絡(luò)層提供的服務(wù)面向連接的服務(wù)和無(wú)連接的服務(wù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層小結(jié)—網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的地位計(jì)算機(jī)網(wǎng)絡(luò)原理路由算法路由算法路由算法路由算法是網(wǎng)絡(luò)層軟件的一部分子網(wǎng)采用數(shù)據(jù)報(bào)方式，每個(gè)分組都要做路由選擇。子網(wǎng)采用虛電路方式，只需在建立連接時(shí)做一次路由選擇。路由算法應(yīng)具有的特性正確性(correctness)、簡(jiǎn)單性(simplicity)、健壯性(robustness)、穩(wěn)定性(stability)、公平性(fairness)、最優(yōu)性(optimality)路由算法分類非自適應(yīng)算法(靜態(tài)路由算法)：按照預(yù)先計(jì)算好的(off-line)信息進(jìn)行路由。自適應(yīng)算法(動(dòng)態(tài)路由算法)：根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通信量等地變化來(lái)改變路由。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層路由算法路由算法是網(wǎng)絡(luò)層軟件的一部分計(jì)算機(jī)網(wǎng)絡(luò)原最優(yōu)化原則最優(yōu)化原則(optimalityprinciple)如果路由器J在路由器I到K的最優(yōu)路由上，那么從J到K的最優(yōu)路由會(huì)落在同一路由上。匯集樹(shù)(sinktree)路由算法的目的是找出并使用匯集樹(shù)。從所有的源

結(jié)點(diǎn)到一個(gè)給定的目的結(jié)點(diǎn)的最優(yōu)路由的集合形成了一個(gè)以目的結(jié)點(diǎn)為根的樹(shù)，稱為匯集樹(shù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層最優(yōu)化原則最優(yōu)化原則(optimalityprincipl幾種常見(jiàn)的路由算法靜態(tài)路由算法最短路徑選擇(ShortestPathRouting)洪泛算法(FloodingRouting)基于流量的路由算法(Flow-BasedRouting)動(dòng)態(tài)路由算法距離向量路由算法(DistanceVectorRouting)鏈路狀態(tài)路由算法(LinkStateRouting)分級(jí)路由(HierarchicalRouting)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層幾種常見(jiàn)的路由算法靜態(tài)路由算法計(jì)算機(jī)網(wǎng)絡(luò)原理—最短路徑路由算法基本思想構(gòu)建子網(wǎng)的拓?fù)鋱D，圖中的每個(gè)結(jié)點(diǎn)代表一個(gè)路由器，每條弧代表一條通信線路。目的是構(gòu)建兩個(gè)路由器間的路由，算法是在子網(wǎng)拓?fù)鋱D中找出最短路徑。得到最短路徑，有不同的測(cè)量

路徑長(zhǎng)度的方法：計(jì)算結(jié)點(diǎn)數(shù)量計(jì)算地理距離計(jì)算傳輸延遲計(jì)算距離、信道帶寬等參數(shù)的加權(quán)函數(shù)……Dijkstra算法是其中的一種計(jì)算最短路徑的算法。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層最短路徑路由算法基本思想計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)Dijkstra算法每個(gè)結(jié)點(diǎn)用從源結(jié)點(diǎn)沿已知最佳路徑到本結(jié)點(diǎn)的距離來(lái)標(biāo)注，標(biāo)注分為臨時(shí)性標(biāo)注和永久性標(biāo)注。開(kāi)始時(shí)，所有結(jié)點(diǎn)都為臨時(shí)性標(biāo)注，標(biāo)注為無(wú)窮大。源結(jié)點(diǎn)標(biāo)注為0，且為永久性標(biāo)注，令其為工作結(jié)點(diǎn)。檢查與工作結(jié)點(diǎn)相鄰的臨時(shí)性結(jié)點(diǎn)，若該結(jié)點(diǎn)到工作結(jié)點(diǎn)的距離與工作結(jié)點(diǎn)的標(biāo)注之和小于該結(jié)點(diǎn)的標(biāo)注，則用新計(jì)算得到的和重新標(biāo)注該結(jié)點(diǎn)。在整個(gè)圖中查找具有最小值的臨時(shí)性標(biāo)注結(jié)點(diǎn)，將其變?yōu)橛谰眯越Y(jié)點(diǎn)，并成為下一輪檢查的工作結(jié)點(diǎn)。重復(fù)第三、四步，直到目的結(jié)點(diǎn)成為工作結(jié)點(diǎn)。Dijkstra算法的圖例。Dijkstra算法的程序：與算法的區(qū)別是從目的結(jié)點(diǎn)開(kāi)始。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Dijkstra算法每個(gè)結(jié)點(diǎn)用從源結(jié)點(diǎn)沿已知最佳路徑到本結(jié)點(diǎn)Dijkstra算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Dijkstra算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)Dijkstra算法程序計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Dijkstra算法程序計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)洪泛算法基本思想把收到的每一個(gè)分組，向除了該分組到來(lái)的線路外的所有輸出線路發(fā)送。主要問(wèn)題洪泛要產(chǎn)生大量重復(fù)分組。解決措施每個(gè)報(bào)頭包含站點(diǎn)計(jì)數(shù)器，每經(jīng)過(guò)一站計(jì)數(shù)器減1，為0時(shí)則丟棄該分組。記錄下分組擴(kuò)展的路徑，防止它第二次擴(kuò)散到已經(jīng)擴(kuò)散過(guò)的路徑中。較實(shí)用的方法——選擇性洪泛算法(selectiveflooding)洪泛法的一種改進(jìn)：將進(jìn)來(lái)的每個(gè)分組僅發(fā)送到與正確方向接近的線路上。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層洪泛算法基本思想計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層洪泛算法應(yīng)用情況洪泛算法由于過(guò)于浪費(fèi)路由器和線路的資源，在實(shí)際應(yīng)用中很難被直接采用，但還是有一些用處的。在軍事領(lǐng)域中，由于需要極好的健壯性，擴(kuò)散法可以一展身手。在分布式數(shù)據(jù)庫(kù)中，有時(shí)需要并行地更新所有數(shù)據(jù)庫(kù)，這時(shí)洪泛算法也是最佳方案。因?yàn)楹榉核惴偸悄軌蜻x擇最短的路徑，可以產(chǎn)生一個(gè)最短的延遲。洪泛算法可以作為一種尺度衡量標(biāo)準(zhǔn)來(lái)評(píng)價(jià)其它路由算法。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層洪泛算法應(yīng)用情況計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層基于流量的路由算法基本思想既考慮拓?fù)浣Y(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負(fù)荷。前提：每對(duì)結(jié)點(diǎn)間平均數(shù)據(jù)流是相對(duì)穩(wěn)定和可預(yù)測(cè)的。根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均分組延遲，因此路由算法就演變?yōu)閷ふ揖W(wǎng)絡(luò)中連接兩個(gè)路由器的線路上具有最小平均分組延遲的問(wèn)題。需要預(yù)知的信息網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。通信量矩陣Fij，即線路ij之間的平均通信量。線路帶寬矩陣Cij，即線路ij之間允許的最大通信量。臨時(shí)的路由算法。圖例。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層基于流量的路由算法基本思想計(jì)算機(jī)網(wǎng)絡(luò)原理——基于流量的路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層基于流量的路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)

根據(jù)隊(duì)列原理，線路平均分組延遲的計(jì)算公式為：T=1/(C-)1/=800bit基于流量的路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層根據(jù)隊(duì)列原理，線路平均分組延遲的計(jì)算公式為：基于流量距離向量路由算法屬于動(dòng)態(tài)路由算法，最初用于ARPANET,DECnet等網(wǎng)絡(luò)。基本思想：每個(gè)路由器維護(hù)一張表，表中列出了到每個(gè)目的地址的最佳距離和線路，并通過(guò)與鄰居結(jié)點(diǎn)交換信息來(lái)更新表。表(路由表)的構(gòu)成：以子網(wǎng)中其它路由器為表的索引，到達(dá)目的結(jié)點(diǎn)的最佳輸出線路，和到達(dá)目的結(jié)點(diǎn)所需時(shí)間或距離。路由器需要知曉自己到鄰居結(jié)點(diǎn)的“距離”。所用的度量標(biāo)準(zhǔn)可以為站點(diǎn)、估計(jì)的時(shí)間延遲等。如果為站點(diǎn)，本路由器到每個(gè)鄰居結(jié)點(diǎn)的距離都為1。如果是延遲，本路由器就發(fā)送一個(gè)要對(duì)方立即響應(yīng)的ECHO分組，用來(lái)回時(shí)間除以2即得到延遲時(shí)間，每隔一段時(shí)間，路由器向所有鄰居結(jié)點(diǎn)發(fā)送它到每個(gè)目的結(jié)點(diǎn)的距離表，同時(shí)它也接收每個(gè)鄰居結(jié)點(diǎn)發(fā)來(lái)的距離表。鄰居結(jié)點(diǎn)X發(fā)來(lái)的表中，X到路由器i的距離為Xi。本路由器到X的距離為m，則本路由器經(jīng)過(guò)X到i的距離為Xi+m。根據(jù)不同鄰居發(fā)來(lái)的信息，計(jì)算Xi+m，取最小值，更新本路由器的表。注意：在計(jì)算中不使用本路由器中的老路由表。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層距離向量路由算法屬于動(dòng)態(tài)路由算法，最初用于ARPANET,D距離向量路由算法圖例路由器J計(jì)算到達(dá)路由器C的最新路由JAC=8+25=33msJIC=10+18=28msJHC=12+19=31msJKC=6+36=42ms其中JIC是最好的。因此在路由器J的新路由表中填上到C的延遲為28ms，經(jīng)過(guò)路由器I。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層距離向量路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)距離向量路由算法的缺陷缺陷——無(wú)窮計(jì)算問(wèn)題對(duì)好消息反應(yīng)迅速：在最長(zhǎng)路徑為N各結(jié)點(diǎn)的子網(wǎng)中，在N次交換之內(nèi)，所有的路由器都會(huì)指導(dǎo)新增的線路和路由器。對(duì)壞消息反應(yīng)遲鈍：對(duì)于已經(jīng)消失的結(jié)點(diǎn)，相互欺騙。圖例如下。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層距離向量路由算法的缺陷缺陷——無(wú)窮計(jì)算問(wèn)題計(jì)算機(jī)網(wǎng)絡(luò)水平分裂算法基本思想工作過(guò)程與距離向量算法相同，區(qū)別在于到X的距離不向真正通向X的鄰居結(jié)點(diǎn)報(bào)告。從而使得壞消息以每次一個(gè)結(jié)點(diǎn)的速度傳播。舉例：如右圖。在路由信息的交換中，B知道可以直達(dá)A，并告訴C，通過(guò)B到C路徑為1。C得到B發(fā)來(lái)的路由信息后，告訴D通過(guò)C到達(dá)A距離為2，告訴B通過(guò)C到達(dá)A為無(wú)窮。D得到C發(fā)來(lái)的路由信息后，告訴E通過(guò)D到達(dá)A距離為3，告訴C通過(guò)D到達(dá)A為無(wú)窮。當(dāng)A下網(wǎng)后，第一次交換：B發(fā)現(xiàn)到達(dá)A的直達(dá)路線沒(méi)有了，而且C也向B說(shuō)到達(dá)A為無(wú)窮，故B將其到達(dá)A的距離設(shè)置為無(wú)窮。第二次交換：C得到B的通知，B到達(dá)A為無(wú)窮；同時(shí)D也告訴C，通過(guò)D到達(dá)A為無(wú)窮，故C將其到達(dá)A的距離設(shè)置為無(wú)窮。以次類推，在第四次交換的時(shí)候，E也知道A不可達(dá)了。解決方案之一水平分裂ABCDE計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層水平分裂算法基本思想解決方案之一水平分裂ABCDE計(jì)算機(jī)水平分裂不能解決所有的問(wèn)題水平分裂雖然廣泛使用，但有時(shí)候會(huì)失敗。如右圖。開(kāi)始時(shí)，A和B到D的舉例都為2，C到D的舉例為1。假設(shè)CD線路斷了，使用水平分裂，A和B都告訴C，它們不能到達(dá)D，同時(shí)C自己也發(fā)現(xiàn)直達(dá)D的線路斷了，于是C很快認(rèn)定D不可達(dá)了。但是，A認(rèn)為B有一條通向D長(zhǎng)度為2的路徑，通過(guò)B經(jīng)過(guò)3個(gè)結(jié)點(diǎn)可到達(dá)D。類似，B也這樣認(rèn)為。于是兩個(gè)結(jié)點(diǎn)每交換一次信息，到達(dá)D的距離就增加1，直至加大無(wú)窮。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層水平分裂不能解決所有的問(wèn)題水平分裂雖然廣泛使用，但有時(shí)候會(huì)失鏈路狀態(tài)路由算法距離向量路由算法的主要問(wèn)題由于延遲度量?jī)H僅是隊(duì)列長(zhǎng)度，在選擇路由時(shí)沒(méi)有考慮線路帶寬。即使使用了水平分裂，路由收斂速度依然慢。在1979年前，ARPANET上都采用距離向量路由算法，但是之后，即為鏈路狀態(tài)路由算法所替代。鏈路狀態(tài)路由算法的簡(jiǎn)單步驟發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或開(kāi)銷。將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)分組。將這個(gè)分組發(fā)送給所有其它路由器。計(jì)算到每個(gè)其它路由器的最短路徑。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層鏈路狀態(tài)路由算法距離向量路由算法的主要問(wèn)題計(jì)算機(jī)網(wǎng)絡(luò)步驟1：發(fā)現(xiàn)鄰居結(jié)點(diǎn)發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。路由器啟動(dòng)后，通過(guò)發(fā)送HELLO分組，并得到鄰居路由器的響應(yīng)來(lái)發(fā)現(xiàn)鄰居結(jié)點(diǎn)。路由器的名稱必須是唯一的。當(dāng)兩個(gè)或多個(gè)路由器連在一個(gè)LAN時(shí)，引入人工結(jié)點(diǎn)。圖例。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟1：發(fā)現(xiàn)鄰居結(jié)點(diǎn)發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。計(jì)步驟2/3：測(cè)量線路開(kāi)銷和封裝分組測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或開(kāi)銷，一種直接的方法是：發(fā)送一個(gè)要對(duì)方立即響應(yīng)的ECHO分組，來(lái)回時(shí)間除以2即為延遲時(shí)間。如果在測(cè)量延遲時(shí)間的時(shí)候，考慮負(fù)載，會(huì)是什么情況？（自學(xué)）將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)分組，即在信息收集完畢后，構(gòu)造一個(gè)包含所有數(shù)據(jù)的分組。該分組的結(jié)構(gòu)為：發(fā)送方的標(biāo)識(shí)符、序號(hào)、年齡、鄰居結(jié)點(diǎn)列表（鄰居結(jié)點(diǎn)標(biāo)識(shí)符，線路開(kāi)銷值）。創(chuàng)建鏈路狀態(tài)分組的時(shí)機(jī)：一是定期創(chuàng)建，一是在發(fā)生重大事件后創(chuàng)建。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟2/3：測(cè)量線路開(kāi)銷和封裝分組測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或步驟4：發(fā)布鏈路狀態(tài)分組鏈路狀態(tài)分組的發(fā)布算法基本思想：洪泛鏈路狀態(tài)分組。為控制洪泛，每個(gè)分組中增加一個(gè)序號(hào)域，每次發(fā)送新分組時(shí)加1。路由器記錄信息對(duì)(源路由器，序號(hào))，當(dāng)一個(gè)鏈路狀態(tài)分組到達(dá)時(shí)，若是新的，則分發(fā)；若是重復(fù)的，則丟棄；若序號(hào)比路由器記錄中的最大序號(hào)小，則認(rèn)為過(guò)時(shí)而丟棄?；舅惴ㄋa(chǎn)生的問(wèn)題序號(hào)循環(huán)使用會(huì)混淆。路由器崩潰后，所有的序號(hào)丟失，從0開(kāi)始記，以后所有的新到分組都可能被當(dāng)作重復(fù)分組而被拒絕。序號(hào)在發(fā)送出去后出現(xiàn)錯(cuò)誤。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟4：發(fā)布鏈路狀態(tài)分組鏈路狀態(tài)分組的發(fā)布算法計(jì)算機(jī)網(wǎng)步驟4：發(fā)布鏈路狀態(tài)分組基本算法的改進(jìn)方案為了避免序號(hào)重復(fù)，使用32位的序號(hào)。解決序號(hào)丟失和出錯(cuò)的方法是增加年齡(age)域，每秒鐘年齡減1，至零則丟棄。鏈路狀態(tài)分組到達(dá)后，延遲一段時(shí)間(被放置在一個(gè)保持區(qū)中)，并與其它已到達(dá)的來(lái)自同一路由器的鏈路狀態(tài)分組比較序號(hào)，丟棄重復(fù)分組和超齡分組。為了防止鏈路出錯(cuò)，所有的鏈路狀態(tài)分組都需要應(yīng)答。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟4：發(fā)布鏈路狀態(tài)分組基本算法的改進(jìn)方案計(jì)算機(jī)網(wǎng)絡(luò)步驟5：計(jì)算新路由在路由器積累了一整套網(wǎng)絡(luò)的鏈路狀態(tài)分組后，就可以通過(guò)計(jì)算得到整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)?？梢岳肈ijkstra算法計(jì)算得到每個(gè)其它路由器的最短路徑?；阪溌窢顟B(tài)的路由協(xié)議OpenShortestPathFirst(OSPF)IntermediateSystem-IntermediateSystem(IS-IS)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟5：計(jì)算新路由在路由器積累了一整套網(wǎng)絡(luò)的鏈路狀態(tài)分組后，分級(jí)路由網(wǎng)絡(luò)規(guī)模增長(zhǎng)帶來(lái)的問(wèn)題路由器中的路由表增大。路由器為選擇路由而占用的內(nèi)存、CPU時(shí)間和網(wǎng)絡(luò)帶寬增大。解決辦法——分級(jí)路由對(duì)于大型網(wǎng)絡(luò)分而治之，每個(gè)路由器只知道自己所在子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。根據(jù)需要，可以分成區(qū)域(regions)、聚類(clusters)、區(qū)(zones)和組(groups)…圖例。分級(jí)路由帶來(lái)的問(wèn)題路由表中的路由不一定是最優(yōu)路由。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分級(jí)路由網(wǎng)絡(luò)規(guī)模增長(zhǎng)帶來(lái)的問(wèn)題計(jì)算機(jī)網(wǎng)絡(luò)原理—分級(jí)路由圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分級(jí)路由圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層小結(jié)—路由算法最優(yōu)化原則路由算法的目的是找出并使用匯集樹(shù)。最短路徑路由算法目的是構(gòu)建兩個(gè)路由器間的路由，算法是在子網(wǎng)拓?fù)鋱D中找出最短路徑。Dijkstra算法。洪泛算法把收到的每一個(gè)分組，向除了該分組到來(lái)的線路外的所有輸出線路發(fā)送?；诹髁康穆酚伤惴ǜ鶕?jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均延遲，因此路由問(wèn)題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的路由算法。距離向量路由算法根據(jù)兩個(gè)結(jié)點(diǎn)間的隊(duì)列長(zhǎng)度來(lái)完成路由選擇，但是最大的問(wèn)題是無(wú)窮計(jì)算，而且水平分裂也不能完全解決所有的問(wèn)題。鏈路狀態(tài)路由算法發(fā)現(xiàn)鄰居結(jié)點(diǎn)測(cè)量線路開(kāi)銷將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)分組發(fā)布鏈路狀態(tài)信息計(jì)算新路由分級(jí)路由對(duì)于大型網(wǎng)絡(luò)分而治之，每個(gè)路由器只知道自己所在子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層小結(jié)—路由算法最優(yōu)化原則距離向量路由算法計(jì)算機(jī)網(wǎng)擁塞控制擁塞控制擁塞的基本概念擁塞(congestion)：網(wǎng)絡(luò)中存在過(guò)多分組的時(shí)候，網(wǎng)絡(luò)性能降低，這種情況被稱為擁塞。圖例造成擁塞的原因多個(gè)輸入對(duì)應(yīng)一個(gè)輸出，只增加內(nèi)存，并不能解決問(wèn)題。慢速處理器。低帶寬線路。針對(duì)某個(gè)因素的解決方案，只能對(duì)提高網(wǎng)絡(luò)性能起到一點(diǎn)點(diǎn)作用，甚至可能僅僅是轉(zhuǎn)移了影響性能的瓶頸。擁塞控制(congestioncontrol)與流量控制(flowcontrol)擁塞控制需要確保通信子網(wǎng)能夠承載用戶提交的通信量，是一個(gè)全局性問(wèn)題，涉及主機(jī)、路由器等很多因素。流量控制與點(diǎn)到點(diǎn)的通信量有關(guān)，主要解決快速發(fā)送方與慢速接收方的問(wèn)題，是局部問(wèn)題，一般都是基于反饋進(jìn)行控制的。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層擁塞的基本概念擁塞(congestion)：網(wǎng)絡(luò)中存在過(guò)多分擁塞圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層擁塞圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層擁塞控制的分類根據(jù)控制論，擁塞控制可分為兩類。開(kāi)環(huán)控制(防患于未然)通過(guò)良好的設(shè)計(jì)解決問(wèn)題，以避免擁塞發(fā)生。一旦運(yùn)行，就不再做中間階段的更正。進(jìn)行開(kāi)環(huán)控制的工具需要決定何時(shí)接收新的分組、何時(shí)丟棄分組、丟棄哪些分組，制定網(wǎng)絡(luò)中不同地點(diǎn)的計(jì)劃表等。利用開(kāi)環(huán)進(jìn)行擁塞控制時(shí)，所有這些操作都不會(huì)考慮網(wǎng)絡(luò)的當(dāng)前狀態(tài)。閉環(huán)控制(因地制宜)基于反饋機(jī)制。其工作過(guò)程為：監(jiān)控系統(tǒng)，發(fā)現(xiàn)何時(shí)何地發(fā)生擁塞。 把發(fā)生擁塞的消息傳給能采取動(dòng)作的站點(diǎn)。調(diào)整系統(tǒng)操作，解決擁塞問(wèn)題。閉環(huán)控制操作需要完成以下三個(gè)問(wèn)題：何為擁塞、如何反饋和如何解決。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層擁塞控制的分類根據(jù)控制論，擁塞控制可分為兩類。計(jì)算機(jī)網(wǎng)閉環(huán)控制何為擁塞——衡量網(wǎng)絡(luò)擁塞的參數(shù)缺乏緩沖區(qū)造成的丟包率平均隊(duì)列長(zhǎng)度超時(shí)重傳的分組數(shù)目平均分組延遲分組延遲變化(Jitter)如何反饋——反饋方法向負(fù)載的發(fā)生源發(fā)送一個(gè)報(bào)警分組，這同時(shí)加強(qiáng)了擁塞。在分組結(jié)構(gòu)中保留一個(gè)位或一個(gè)域來(lái)表示發(fā)生擁塞，一旦發(fā)生擁塞，路由器將所有輸出分組的擁塞位填充，報(bào)警。主機(jī)或路由器主動(dòng)地、周期性地發(fā)送探報(bào)(probe)，查詢是否發(fā)生擁塞。如何解決——利用擁塞控制算法計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層閉環(huán)控制何為擁塞——衡量網(wǎng)絡(luò)擁塞的參數(shù)計(jì)算機(jī)網(wǎng)絡(luò)開(kāi)環(huán)控制—擁塞預(yù)防策略影響擁塞的網(wǎng)絡(luò)設(shè)計(jì)策略數(shù)據(jù)鏈路層重傳、亂序緩存、確認(rèn)、流控網(wǎng)絡(luò)層子網(wǎng)中的虛電路和數(shù)據(jù)報(bào)、分組排隊(duì)和服務(wù)策略、分組丟棄策略、路由算法、分組的生存時(shí)間管理傳輸層 重傳、亂序緩存、確認(rèn)、流控、超時(shí)中止計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層開(kāi)環(huán)控制—擁塞預(yù)防策略影響擁塞的網(wǎng)絡(luò)設(shè)計(jì)策略計(jì)算機(jī)開(kāi)環(huán)控制—通信量整形通信量整形(TrafficShaping)的基本思想網(wǎng)絡(luò)上，突發(fā)的通信量是造成擁塞的主要原因。強(qiáng)迫分組以某種可以預(yù)見(jiàn)的速率傳送，減少擁塞，這種方法就被稱為通信量整形。此方法廣泛應(yīng)用于ATM網(wǎng)絡(luò)中。漏桶算法和令牌桶算法都可以實(shí)現(xiàn)通信量整形。漏桶算法(TheLeakyBucketAlgorithm)基本原理：圖例。在計(jì)算機(jī)中的使用漏桶——有限內(nèi)部隊(duì)列；水——通信量，需要發(fā)送的分組。分組到達(dá)隊(duì)列時(shí)，隊(duì)列滿，分組被丟棄；隊(duì)列空，分組放置在隊(duì)尾。效果將用戶發(fā)出的不平滑的分組流轉(zhuǎn)變成網(wǎng)絡(luò)中平滑的分組流。漏桶算法既可以用于分組長(zhǎng)度固定的協(xié)議，如ATM，使用分組計(jì)數(shù)；也可用于可變長(zhǎng)分組的協(xié)議，如IP，使用字節(jié)計(jì)數(shù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層開(kāi)環(huán)控制—通信量整形通信量整形(TrafficShap無(wú)論水流進(jìn)桶的速度為多少，只要桶中有水，水從桶中外漏的速度是恒定的。桶空了，速度為零。桶滿了，水外泄。漏桶算法計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層無(wú)論水流進(jìn)桶的速度為多少，只要桶中有水，水從桶中外漏桶算法計(jì)令牌桶算法由于漏桶算法不夠靈活，因此加入令牌機(jī)制。令牌桶算法(TheTokenBucketAlgorithm)基本思想：漏桶存放令牌，每T秒產(chǎn)生一個(gè)令牌，分組發(fā)送傳輸之前必須獲得一個(gè)令牌，傳輸之后刪除該令牌。令牌代表的不是發(fā)送一個(gè)分組的權(quán)利，而是可以發(fā)送的字節(jié)數(shù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層令牌桶算法由于漏桶算法不夠靈活，因此加入令牌機(jī)制。計(jì)算機(jī)漏桶和令牌桶的結(jié)合算法一臺(tái)計(jì)算機(jī)以25MB/s的速率生成數(shù)據(jù)，網(wǎng)絡(luò)也可以該速率運(yùn)行，但路由器的最佳工作速率為2MB/s。右圖說(shuō)明了1M的分組在不同的算法下是如何發(fā)送的。如何計(jì)算最大速率的突發(fā)時(shí)間長(zhǎng)度：令：令牌桶容量為C字節(jié)，突發(fā)時(shí)間S秒，令牌到達(dá)速率為p字節(jié)/秒，最大輸出速率為M字節(jié)/秒有：C+pS=MS>S=C/(M-p)圖cde：M=25MB/s,p=2MB/s,C=250/500/750KB圖f：M=10MB/s,p=2MB/s,C=500KB計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層漏桶和令牌桶的結(jié)合算法一臺(tái)計(jì)算機(jī)以25MB/s的速率計(jì)算漏桶和令牌桶算法的比較通信量整形策略不同漏桶算法不允許空閑主機(jī)積累發(fā)送權(quán)。令牌桶算法允許空閑主機(jī)積累發(fā)送權(quán)，以便以后發(fā)送大的突發(fā)數(shù)據(jù)，最大為桶的大小。桶中存放的內(nèi)容不同漏桶中存放的是數(shù)據(jù)，桶滿了丟棄數(shù)據(jù)。令牌桶中存放的是令牌，桶滿了丟棄令牌，不丟棄數(shù)據(jù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層漏桶和令牌桶算法的比較計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)開(kāi)環(huán)控制—流說(shuō)明流說(shuō)明(FlowSpecification)當(dāng)發(fā)送方、接收方和子網(wǎng)都達(dá)成一致后，通信量整形才能發(fā)揮最佳效果。所以，一個(gè)數(shù)據(jù)流的發(fā)送方、接收方和通信子網(wǎng)三方認(rèn)可的、描述發(fā)送數(shù)據(jù)流的模式和希望得到的服務(wù)質(zhì)量的數(shù)據(jù)結(jié)構(gòu)，被稱為流說(shuō)明。對(duì)發(fā)送方的流說(shuō)明，子網(wǎng)和接收方可以做出三種答復(fù)：同意、拒絕、其它建議。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層開(kāi)環(huán)控制—流說(shuō)明流說(shuō)明(FlowSpecificati閉環(huán)控制—虛電路子網(wǎng)中的擁塞控制方法一許可控制(admissioncontrol)：一旦發(fā)生擁塞，就不允許再建立新的虛電路，直到擁塞解除為止。方法二在發(fā)生擁塞后可以建立新的虛電路，但要繞開(kāi)發(fā)生擁塞的地區(qū)。方法三資源預(yù)留：建立虛電路時(shí)，主機(jī)與子網(wǎng)達(dá)成協(xié)議，子網(wǎng)根據(jù)協(xié)議在虛電路上為此連接預(yù)留資源。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層閉環(huán)控制—虛電路子網(wǎng)中的擁塞控制方法一計(jì)算機(jī)網(wǎng)絡(luò)閉環(huán)控制—抑制分組抑制分組(ChokePackets)路由器監(jiān)控輸出線路及其它資源的利用情況，超過(guò)某個(gè)閾值，則此資源進(jìn)入警戒狀態(tài)。每個(gè)新分組到來(lái)，檢查它的輸出線路是否處于警戒狀態(tài)。若是，向源主機(jī)發(fā)送抑制分組，分組中指出發(fā)生擁塞的目的地址。同時(shí)將源分組打上標(biāo)記(為了以后不再產(chǎn)生抑制分組)后，正常轉(zhuǎn)發(fā)。源主機(jī)收到抑制分組后，按一定比例減少發(fā)向特定目的地的通信量，并在固定時(shí)間間隔內(nèi)忽略指示同一目的地的抑制分組。然后開(kāi)始監(jiān)聽(tīng)，若此線路仍然擁塞，則主機(jī)在固定時(shí)間內(nèi)減輕負(fù)載、忽略抑制分組；若在監(jiān)聽(tīng)周期內(nèi)沒(méi)有收到抑制分組，則增加通信量。通常采用的通信量增減策略是：減少時(shí)按一定比例減少，保證快速解除擁塞。增加時(shí)以常量增加，防止很快導(dǎo)致?lián)砣?。?jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層閉環(huán)控制—抑制分組抑制分組(ChokePackets)加權(quán)公平隊(duì)列由于采用抑制分組時(shí)，源端的抑制行為是自愿的。為了公平地對(duì)待自覺(jué)和不自覺(jué)的源端，就提出公平隊(duì)列(fairqueueing)算法。每個(gè)輸出線存在多個(gè)隊(duì)列，每個(gè)源端對(duì)應(yīng)一個(gè)隊(duì)列，當(dāng)輸出線空閑時(shí)，路由器將輪巡這幾個(gè)隊(duì)列，從下一個(gè)隊(duì)列中選出第一個(gè)字節(jié)。由于某些服務(wù)器非常重要，就可以對(duì)每個(gè)隊(duì)列采用不同的優(yōu)先權(quán)。例如：可以一次機(jī)會(huì)發(fā)送兩個(gè)或者更多的字節(jié)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層加權(quán)公平隊(duì)列由于采用抑制分組時(shí)，源端的抑制行為是自愿的。為了Hop-by-Hop抑制分組在高速、長(zhǎng)距離的網(wǎng)絡(luò)中，由于源主機(jī)響應(yīng)太慢，抑制分組算法對(duì)擁塞控制的效果并不好，可采用Hop-by-Hop抑制分組算法。Hop-by-HopChokePackets的基本思想抑制分組對(duì)它經(jīng)過(guò)的每個(gè)路由器都起作用。能夠迅速緩解發(fā)生擁塞處的擁塞。要求上游路由器有更多的緩沖區(qū)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Hop-by-Hop抑制分組在高速、長(zhǎng)距離的網(wǎng)絡(luò)中，由于源主計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層閉環(huán)控制—負(fù)載丟棄當(dāng)所有上述算法都不能消除擁塞時(shí)，路由器只得采用負(fù)載丟棄(LoadShedding)，將分組丟棄。路由器可以隨意挑選分組來(lái)丟棄，但還可以根據(jù)不同的服務(wù)，采取不同丟棄策略文件傳輸，優(yōu)先丟棄新分組，wine策略；多媒體服務(wù)，優(yōu)先丟棄舊分組，milk策略；早期丟棄分組，會(huì)減少擁塞發(fā)生的概率，提高網(wǎng)絡(luò)性能。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層閉環(huán)控制—負(fù)載丟棄當(dāng)所有上述算法都不能消除擁塞時(shí)，路由器小結(jié)—擁塞控制算法擁塞控制的基本原理網(wǎng)絡(luò)中存在過(guò)多分組的時(shí)候，網(wǎng)絡(luò)性能降低，產(chǎn)生擁塞。開(kāi)環(huán)控制(通過(guò)良好的設(shè)計(jì)解決問(wèn)題)擁塞預(yù)防策略：數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層都策略可以進(jìn)行預(yù)防通信量整形強(qiáng)迫分組以某種可以預(yù)見(jiàn)的速率傳送。漏桶和令牌桶均可實(shí)現(xiàn)通信量整形。流說(shuō)明閉環(huán)控制虛電路網(wǎng)絡(luò)中的擁塞控制許可控制、繞開(kāi)擁塞、資源預(yù)留抑制分組：向源主機(jī)發(fā)送抑制分組。為了公平，可以采用加權(quán)公平算法(字節(jié)輪巡)。為了得到快速的抑制效果，可采用Hop-by-Hop抑制分組，抑制分組對(duì)其所經(jīng)過(guò)的路由器都起作用。負(fù)載丟棄：對(duì)不同服務(wù)采用不同的丟棄策略。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層小結(jié)—擁塞控制算法擁塞控制的基本原理計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)互聯(lián)技術(shù)網(wǎng)絡(luò)互聯(lián)技術(shù)為什么需要網(wǎng)絡(luò)互聯(lián)互聯(lián)網(wǎng)(internet)：兩個(gè)或多個(gè)網(wǎng)絡(luò)構(gòu)成互聯(lián)網(wǎng)。為什么會(huì)存在多種不同的網(wǎng)絡(luò)(協(xié)議)？歷史原因：不同公司的網(wǎng)絡(luò)產(chǎn)品大量使用。價(jià)格原因：網(wǎng)絡(luò)產(chǎn)品價(jià)格低使很多人有權(quán)決定使用何種網(wǎng)絡(luò)。技術(shù)原因：不同網(wǎng)絡(luò)采用不同技術(shù)、不同硬件、不同協(xié)議。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層為什么需要網(wǎng)絡(luò)互聯(lián)互聯(lián)網(wǎng)(internet)：兩個(gè)或多個(gè)網(wǎng)絡(luò)用于互連的網(wǎng)絡(luò)設(shè)備物理層設(shè)備網(wǎng)卡(NICCard)安裝在計(jì)算機(jī)主板上的電路板插板。網(wǎng)卡的作用是將計(jì)算機(jī)與通信設(shè)施連接起來(lái)，將計(jì)算機(jī)中的數(shù)字信號(hào)轉(zhuǎn)換成通信線路上能夠傳送的電子信號(hào)或者電磁信號(hào)。調(diào)制解調(diào)器(Modem)是一種信號(hào)轉(zhuǎn)換裝置。完成數(shù)字信號(hào)和模擬信號(hào)之間的轉(zhuǎn)換。中繼器(Repeater)是一種比較簡(jiǎn)單的單向傳送設(shè)備。它能夠接收一條鏈路上的數(shù)據(jù)，并以同樣的速度串形地將該數(shù)據(jù)傳送到另一條鏈路上，而且，所有的鏈路都按一個(gè)方向傳輸數(shù)據(jù)。對(duì)弱信號(hào)進(jìn)行放大或再生，以便延長(zhǎng)傳輸距離。集線器(Hub)是局域網(wǎng)中的連接設(shè)備，具有多個(gè)端口，可連接多臺(tái)計(jì)算機(jī)。在局域網(wǎng)中常常將分散的計(jì)算機(jī)連接起來(lái)，形成星型拓?fù)浣Y(jié)構(gòu)的局域網(wǎng)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層用于互連的網(wǎng)絡(luò)設(shè)備物理層設(shè)備計(jì)算機(jī)網(wǎng)絡(luò)原理——用于互連的網(wǎng)絡(luò)設(shè)備數(shù)據(jù)鏈路層設(shè)備網(wǎng)橋(Bridge)是局域網(wǎng)中的連接設(shè)備。網(wǎng)橋?qū)⒁粋€(gè)大的局域網(wǎng)分成不同的網(wǎng)段，以擴(kuò)展網(wǎng)絡(luò)距離，減輕網(wǎng)絡(luò)負(fù)擔(dān)。網(wǎng)絡(luò)層設(shè)備多協(xié)議路由器(MultiprotocolRouter)廣域網(wǎng)中的連接設(shè)備，將多個(gè)網(wǎng)絡(luò)連接起來(lái)，形成一個(gè)更大的網(wǎng)絡(luò)。其主要的功能是路由和轉(zhuǎn)發(fā)分組。必要時(shí)，做網(wǎng)絡(luò)層協(xié)議轉(zhuǎn)換。交換機(jī)(Switch)有些交換機(jī)工作在數(shù)據(jù)鏈路層，例如幀中繼交換機(jī)、ATM交換機(jī)等，(有些交換機(jī)工作在網(wǎng)絡(luò)層)，為源和目的地址之間建立連接。交換機(jī)一般都工作在虛電路模式，在數(shù)據(jù)鏈路建立之后，直接將數(shù)據(jù)轉(zhuǎn)發(fā)出去，不需要再進(jìn)行路徑選擇，延遲小。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層用于互連的網(wǎng)絡(luò)設(shè)備數(shù)據(jù)鏈路層設(shè)備計(jì)算機(jī)網(wǎng)絡(luò)原理用于互連的網(wǎng)絡(luò)設(shè)備傳輸層設(shè)備傳輸網(wǎng)關(guān)(TtransportGateway)在傳輸層轉(zhuǎn)發(fā)字節(jié)流。應(yīng)用層設(shè)備應(yīng)用網(wǎng)關(guān)(ApplicationGateway)在應(yīng)用層實(shí)現(xiàn)互聯(lián)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層用于互連的網(wǎng)絡(luò)設(shè)備計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)網(wǎng)絡(luò)互聯(lián)設(shè)備的實(shí)際與理論半網(wǎng)關(guān)——當(dāng)一個(gè)網(wǎng)關(guān)處于兩個(gè)不同的機(jī)構(gòu)時(shí)，可以將其從中間分開(kāi)，切分成兩個(gè)部分，由導(dǎo)線連接，兩個(gè)半網(wǎng)關(guān)之間遵循一個(gè)中性協(xié)議。任意一種網(wǎng)關(guān)都可以用在任意一層。實(shí)際的網(wǎng)絡(luò)互聯(lián)設(shè)備總是很混亂。對(duì)于一個(gè)純的網(wǎng)橋而言，它只檢查數(shù)據(jù)鏈路幀的幀頭，而不關(guān)心幀中網(wǎng)絡(luò)層的分組。對(duì)于一個(gè)純的路由器而言，它只需要分析分組的報(bào)頭，按照所發(fā)現(xiàn)的地址盡力傳送，根本不關(guān)心下層是用什么方法和何種幀結(jié)構(gòu)發(fā)送。市場(chǎng)的很多設(shè)備都是將網(wǎng)橋和路由器的功能組合在一起的。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)設(shè)備的實(shí)際與理論半網(wǎng)關(guān)——當(dāng)一個(gè)網(wǎng)關(guān)處于兩個(gè)不同的機(jī)網(wǎng)關(guān)舉例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)關(guān)舉例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層各種網(wǎng)絡(luò)的不同點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層各種網(wǎng)絡(luò)的不同點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)方法—級(jí)聯(lián)虛電路級(jí)聯(lián)虛電路(ConcatenatedVirtualCircuits)的工作過(guò)程建立連接當(dāng)目的主機(jī)不在本子網(wǎng)內(nèi)時(shí)，則在子網(wǎng)內(nèi)找一個(gè)離目的網(wǎng)絡(luò)最近的路由器，與之建立一條虛電路；該路由器與外部網(wǎng)關(guān)建立虛電路；該網(wǎng)關(guān)與下一個(gè)子網(wǎng)中的一個(gè)路由器建立虛電路。重復(fù)上述操作，直到到達(dá)目的主機(jī)。傳輸數(shù)據(jù)相同連接的分組

沿同一虛電路按

照順序傳輸；網(wǎng)關(guān)根據(jù)需要轉(zhuǎn)

換分組格式和虛

電路號(hào)。拆除連接計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)方法—級(jí)聯(lián)虛電路級(jí)聯(lián)虛電路(Concatenat網(wǎng)絡(luò)互聯(lián)方法—無(wú)連接網(wǎng)絡(luò)互聯(lián)無(wú)連接網(wǎng)絡(luò)互聯(lián)(ConnectionlessInternetworking)的工作過(guò)程無(wú)連接網(wǎng)絡(luò)互聯(lián)的工作過(guò)程與數(shù)據(jù)報(bào)子網(wǎng)的工作過(guò)程相似。每個(gè)分組獨(dú)立路由，不保證分組按順序到達(dá)，提高網(wǎng)絡(luò)利用率。其中，連接不同子網(wǎng)的多協(xié)議路由器做協(xié)議轉(zhuǎn)換，包括分組格式轉(zhuǎn)換和地址轉(zhuǎn)換等。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)方法—無(wú)連接網(wǎng)絡(luò)互聯(lián)無(wú)連接網(wǎng)絡(luò)互聯(lián)(Connec級(jí)連虛電路與無(wú)連接網(wǎng)絡(luò)互聯(lián)的比較級(jí)連虛電路優(yōu)點(diǎn)路由器預(yù)留緩沖區(qū)等資源，保證服務(wù)質(zhì)量。分組按序號(hào)傳輸。分組的報(bào)文頭部較短。缺點(diǎn)路由器需要大量?jī)?nèi)存存儲(chǔ)虛電路信息。一旦發(fā)生擁塞，沒(méi)有其它路由，健壯性差。如果網(wǎng)絡(luò)中有一個(gè)不可靠的數(shù)據(jù)報(bào)子網(wǎng)，級(jí)連虛電路很難實(shí)現(xiàn)。無(wú)連接網(wǎng)絡(luò)互聯(lián)優(yōu)點(diǎn)能夠容忍擁塞，并能適應(yīng)擁塞。健壯性好?？捎糜诙喾N網(wǎng)絡(luò)互聯(lián)。無(wú)連接網(wǎng)絡(luò)互聯(lián)的缺點(diǎn)分組的報(bào)文頭部較長(zhǎng)。不能保證分組按序號(hào)到達(dá)。不能保證服務(wù)質(zhì)量。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層級(jí)連虛電路與無(wú)連接網(wǎng)絡(luò)互聯(lián)的比較級(jí)連虛電路計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)互聯(lián)方法—隧道技術(shù)路由器1剝掉局域網(wǎng)幀頭、幀尾，將得到的IP分組封裝到廣域網(wǎng)幀中(如PPP)，IP地址不變，幀地址=路由器2-幀地址；廣域網(wǎng)傳輸；路由器2剝掉廣域網(wǎng)幀頭、幀尾，將得到的IP分組封裝到局域網(wǎng)幀中，IP地址不變，幀地址=主機(jī)2-MAC地址；局域網(wǎng)傳輸；主機(jī)2接收。如果源和目的主機(jī)所在網(wǎng)絡(luò)類型相同，但連接它們的是一個(gè)不同類型的網(wǎng)絡(luò)，可采用隧道技術(shù)(Tunneling)。隧道技術(shù)的工作過(guò)程主機(jī)1構(gòu)造一個(gè)分組，IP地址=主機(jī)2-IP，將分組封裝到局域網(wǎng)幀中，幀地址=路由器1-MAC；局域網(wǎng)傳輸；計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)方法—隧道技術(shù)路由器1剝掉局域網(wǎng)幀頭、幀尾，將得網(wǎng)絡(luò)互聯(lián)方法—互聯(lián)網(wǎng)路由互聯(lián)網(wǎng)路由(InternetworkRouting)的工作過(guò)程互聯(lián)網(wǎng)絡(luò)的路由與單獨(dú)子網(wǎng)的路由過(guò)程相似，只是更復(fù)雜。一般使用兩級(jí)路由算法：內(nèi)部網(wǎng)關(guān)協(xié)議(interiorgatewayprotocol)：RIP，OSPF外部網(wǎng)關(guān)協(xié)議(exteriorgatewayprotocol)：BGP自治系統(tǒng)AS(AutonomousSystem)：使用統(tǒng)一算法的一個(gè)網(wǎng)絡(luò)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)方法—互聯(lián)網(wǎng)路由互聯(lián)網(wǎng)路由(Internetwo網(wǎng)絡(luò)互聯(lián)方法—分段每種網(wǎng)絡(luò)都對(duì)分組的最大長(zhǎng)度有限制，因?yàn)椋河布蟆２僮飨到y(tǒng)，例如所有緩沖區(qū)都是512字節(jié)。協(xié)議，例如分組長(zhǎng)度域的比特?cái)?shù)。與標(biāo)準(zhǔn)的兼容性；希望減少傳輸出錯(cuò)的概率。希望避免一個(gè)分組占用信道時(shí)間過(guò)長(zhǎng)。當(dāng)長(zhǎng)的分組經(jīng)過(guò)分組長(zhǎng)度短的網(wǎng)絡(luò)時(shí)，網(wǎng)關(guān)要將長(zhǎng)分組分成若干段(fragment)，每段作為獨(dú)立的分組傳輸。發(fā)送主機(jī)：將報(bào)文分組。路由器：將長(zhǎng)的分組分段。接收主機(jī)：將得到的(有/沒(méi)有)被切割的段重組起來(lái)，構(gòu)成完整的報(bào)文。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)方法—分段每種網(wǎng)絡(luò)都對(duì)分組的最大長(zhǎng)度有限制，因?yàn)榉指詈蜆?biāo)記段路由器在對(duì)分組做劃分時(shí)，必須按照能夠重組源數(shù)據(jù)流的方式對(duì)段進(jìn)行編號(hào)，即標(biāo)記段。有很多種標(biāo)記段的方法。樹(shù)型標(biāo)記法例，分組0分成三段，分別標(biāo)記為0.0,0.1,0.2，段0.0構(gòu)成的分組被分成三段，分別標(biāo)記為0.0.0,0.0.1,0.0.2。如果在確保所有分段都能到達(dá)情況下，無(wú)論分段是否按順序到達(dá)，這種方法可以使分段正確重組。但是，如果某個(gè)分段丟失，就會(huì)出現(xiàn)的問(wèn)題，因?yàn)樾枰龆说蕉酥貍?。這樣，如果分組通過(guò)不同的路徑，就會(huì)有不同的分段效果，從而導(dǎo)致重組出錯(cuò)。偏移量法定義一個(gè)基本段長(zhǎng)，使其能夠通過(guò)所有網(wǎng)絡(luò)。分組被分段時(shí)，除最后一個(gè)段小于等于基本段長(zhǎng)外，其他段的段長(zhǎng)都等于基本段長(zhǎng)，一個(gè)分組可以包括幾個(gè)段。每個(gè)分段的報(bào)頭中包括：原始分組標(biāo)識(shí)，分組中該段的偏移量，是否為最后段的指示位。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分割和標(biāo)記段路由器在對(duì)分組做劃分時(shí)，必須按照能夠重組源數(shù)據(jù)流標(biāo)記段圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層標(biāo)記段圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分段重組策略分段重組過(guò)程對(duì)其它網(wǎng)絡(luò)透明網(wǎng)關(guān)將長(zhǎng)的分組分段后，每段都要經(jīng)過(guò)同一出口網(wǎng)關(guān)，并在那里重組。例如：ATM網(wǎng)絡(luò)。所帶來(lái)的問(wèn)題出口網(wǎng)關(guān)需要知道何時(shí)所有分組都到齊。所有分組必須從同一出口網(wǎng)關(guān)離開(kāi)。長(zhǎng)分組經(jīng)過(guò)一系列短分組網(wǎng)絡(luò)時(shí)，需要反復(fù)地分段重組，開(kāi)銷大。分段重組過(guò)程對(duì)其它網(wǎng)絡(luò)不透明中間網(wǎng)關(guān)不做重組，而由目的主機(jī)做。所帶來(lái)的問(wèn)題對(duì)主機(jī)要求高，能夠重組。每個(gè)段都要有一個(gè)報(bào)頭，網(wǎng)絡(luò)開(kāi)銷增大。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分段重組策略分段重組過(guò)程對(duì)其它網(wǎng)絡(luò)透明計(jì)算機(jī)網(wǎng)絡(luò)原段重組策略圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層段重組策略圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層防火墻為防止網(wǎng)絡(luò)中的信息泄露出去或不好的信息滲透進(jìn)來(lái)，在網(wǎng)絡(luò)邊緣設(shè)置防火墻(firewall)。防火墻的一種常用配置：兩個(gè)路由器，

根據(jù)某種規(guī)則表，進(jìn)行分組過(guò)濾；一個(gè)應(yīng)用網(wǎng)關(guān)，審查應(yīng)用層信息。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層防火墻為防止網(wǎng)絡(luò)中的信息泄露出去或不好的信息滲透進(jìn)來(lái)，在網(wǎng)網(wǎng)絡(luò)互聯(lián)小結(jié)網(wǎng)絡(luò)互聯(lián)設(shè)備：中繼器、網(wǎng)橋、路由器、各種網(wǎng)關(guān)。級(jí)聯(lián)虛電路：在網(wǎng)關(guān)和網(wǎng)關(guān)之間建立虛電路連接。無(wú)連接網(wǎng)絡(luò)互聯(lián)：每個(gè)分組獨(dú)立路由。隧道技術(shù)：兩個(gè)同類型網(wǎng)絡(luò)通過(guò)不同類型的網(wǎng)絡(luò)連接時(shí)使用?；ヂ?lián)網(wǎng)路由：使用兩級(jí)的分級(jí)路由法，在自治系統(tǒng)內(nèi)部的為內(nèi)部網(wǎng)關(guān)算法，在自治系統(tǒng)之間的是外部網(wǎng)關(guān)算法。分段分段的時(shí)候可以通過(guò)樹(shù)形結(jié)構(gòu)或者偏移量方法來(lái)標(biāo)記段，分段重組，可以由網(wǎng)關(guān)來(lái)重組也可以由接收方主機(jī)完成重組。防火墻：常用配置是兩個(gè)路由器根據(jù)某種規(guī)則表進(jìn)行分組過(guò)濾，一個(gè)應(yīng)用網(wǎng)關(guān)審查應(yīng)用層信息。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)互聯(lián)小結(jié)網(wǎng)絡(luò)互聯(lián)設(shè)備：中繼器、網(wǎng)橋、路由器、各種網(wǎng)關(guān)。計(jì)計(jì)算機(jī)網(wǎng)絡(luò)原理

網(wǎng)絡(luò)層尹霞yxia@清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)研究所2000年11月21日計(jì)算機(jī)網(wǎng)絡(luò)原理

網(wǎng)絡(luò)層尹霞網(wǎng)絡(luò)層主要內(nèi)容網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的地位網(wǎng)絡(luò)層需要解決的問(wèn)題數(shù)據(jù)報(bào)和虛電路網(wǎng)絡(luò)層提供的服務(wù)擁塞控制算法擁塞控制的基本原理開(kāi)環(huán)控制擁塞預(yù)防策略通信量整形(漏桶和令牌桶)流說(shuō)明閉環(huán)控制虛電路網(wǎng)絡(luò)中的擁塞控制抑制分組負(fù)載丟棄Internet網(wǎng)絡(luò)層協(xié)議路由算法 最優(yōu)化原則最短路徑路由算法洪泛算法基于流量的路由算法距離向量路由算法鏈路狀態(tài)路由算法分級(jí)路由網(wǎng)絡(luò)互聯(lián)技術(shù)網(wǎng)絡(luò)互聯(lián)設(shè)備常用網(wǎng)絡(luò)互聯(lián)技術(shù)級(jí)聯(lián)虛電路無(wú)連接網(wǎng)絡(luò)互聯(lián)隧道技術(shù)互聯(lián)網(wǎng)路由分段防火墻計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層主要內(nèi)容網(wǎng)絡(luò)層概述路由算法 計(jì)算機(jī)網(wǎng)絡(luò)網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的位置當(dāng)今流行的通信技術(shù)傳統(tǒng)的電信網(wǎng)絡(luò)：線路交換、x.25、幀中繼、ATM。計(jì)算機(jī)網(wǎng)絡(luò)：ARPANET、INTERNET等。有線電視網(wǎng)絡(luò)。計(jì)算機(jī)網(wǎng)絡(luò)中的網(wǎng)絡(luò)層至關(guān)重要網(wǎng)絡(luò)層是通信子網(wǎng)的最高層，關(guān)系著整個(gè)網(wǎng)絡(luò)的運(yùn)行控制。網(wǎng)絡(luò)層需要解決的問(wèn)題是確定分組從源地址到目的地址是如何路由的。網(wǎng)絡(luò)層利用數(shù)據(jù)鏈路層提供的服務(wù)，為傳輸層提供服務(wù)。網(wǎng)絡(luò)層處理端到端傳輸?shù)淖畹蛯?。在廣播網(wǎng)絡(luò)中，路由選擇很簡(jiǎn)單，所以網(wǎng)絡(luò)層也很薄，甚至不存在。而在大型網(wǎng)絡(luò)中，分組不得不跨越若干個(gè)網(wǎng)絡(luò)到達(dá)目的地址，這其中的種種問(wèn)題就需要由網(wǎng)絡(luò)層來(lái)解決。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層的位置當(dāng)今流行的通信技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)原理—網(wǎng)絡(luò)層需要解決的問(wèn)題網(wǎng)絡(luò)層為了能夠了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，以便選擇路由，需要解決以下問(wèn)題：屏蔽各種不同類型網(wǎng)絡(luò)之間的差異需要統(tǒng)一數(shù)據(jù)格式需要統(tǒng)一網(wǎng)絡(luò)地址實(shí)現(xiàn)全網(wǎng)的數(shù)據(jù)傳輸建立跨越網(wǎng)絡(luò)的虛電路網(wǎng)絡(luò)之間實(shí)現(xiàn)分組的尋址和轉(zhuǎn)發(fā)網(wǎng)絡(luò)層的兩種實(shí)現(xiàn)方式虛電路(virtualcircuit)：提供面向連接的服務(wù)。類似于電話，先建立連接，之后依次發(fā)送分組，最后關(guān)閉連接。避免對(duì)每個(gè)分組進(jìn)行路由。數(shù)據(jù)報(bào)(datagram)：提供無(wú)連接的服務(wù)。類似于發(fā)送信件。對(duì)每個(gè)數(shù)據(jù)報(bào)(對(duì)于無(wú)連接中的獨(dú)立分組稱作數(shù)據(jù)報(bào))分別進(jìn)行路由。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層需要解決的問(wèn)題網(wǎng)絡(luò)層為了能夠了解通信子網(wǎng)的拓?fù)浣Y(jié)構(gòu)，以通信交換技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)總是由資源子網(wǎng)和通信子網(wǎng)組成。通信交換技術(shù)是指數(shù)據(jù)信息如何在通信子網(wǎng)的各個(gè)結(jié)點(diǎn)之間進(jìn)行傳輸?shù)?。通常存在三種交換技術(shù)：線路交換、報(bào)文交換和分組交換。還存在某幾個(gè)技術(shù)的融合，即混合交換。線路交換(circuitswitching)在網(wǎng)絡(luò)中利用可切換的物理通信線路直接連接通信雙方。最常見(jiàn)的例子是電話系統(tǒng)。線路交換包括三種狀態(tài)：線路建立、數(shù)據(jù)傳送、線路拆除。線路交換方式中通道是專用的，利用效率低，并存在延遲。報(bào)文交換(messageswitching)是指信息以報(bào)文(邏輯上完整的信息段)為單位進(jìn)行存儲(chǔ)轉(zhuǎn)發(fā)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層通信交換技術(shù)計(jì)算機(jī)網(wǎng)絡(luò)總是由資源子網(wǎng)和通信子網(wǎng)組成。通信交換HHHAR5R2R3Router1R4HBMMMMM存儲(chǔ)轉(zhuǎn)發(fā)(StoreandForward)發(fā)送報(bào)文的主機(jī)在發(fā)送之前，要將報(bào)文的目的地址附加在報(bào)文前面。然后將報(bào)文發(fā)送到網(wǎng)絡(luò)中的結(jié)點(diǎn)中。每個(gè)網(wǎng)絡(luò)中的結(jié)點(diǎn)將完整地接收?qǐng)?bào)文，暫存報(bào)文，然后將報(bào)文發(fā)送到下一個(gè)更接近目的主機(jī)的結(jié)點(diǎn)中。如此操作，直至將報(bào)文發(fā)送到目的主機(jī)為止。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層HHHAR5R2R3Router1R4HBMMMMM存儲(chǔ)轉(zhuǎn)發(fā)分組交換(packetswitching)分組交換結(jié)合報(bào)文交換和線路交換的優(yōu)點(diǎn)，采用存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制，但是規(guī)定了傳輸數(shù)據(jù)的單位長(zhǎng)度。過(guò)長(zhǎng)的報(bào)文被分成較小的單位(分組packet)，依次發(fā)送。如何管理這些分組的正確傳輸：數(shù)據(jù)報(bào)和虛電路。數(shù)據(jù)報(bào)(datagram)：每個(gè)分組被單獨(dú)處理。每個(gè)分組帶有自己的目的地址和序號(hào)被發(fā)出，由通信子網(wǎng)中的結(jié)點(diǎn)進(jìn)行路由選擇。在所有分組到達(dá)了目的主機(jī)后，再將各個(gè)分組按照序號(hào)編排起來(lái)。虛電路(virtualcircuit)：在發(fā)送任何分組之前，首先在發(fā)送主機(jī)和目的主機(jī)之間建立一條邏輯連接，即在通信子網(wǎng)中確定一條用于本次傳輸數(shù)據(jù)用的結(jié)點(diǎn)序列。建立虛電路后，所有的分組都將按照循序依次被發(fā)送到目的主機(jī)。當(dāng)所有的分組都發(fā)送之后，虛電路將被拆除。在虛電路方法中，每個(gè)分組無(wú)須進(jìn)行路徑選擇。每個(gè)主機(jī)可以和另一個(gè)主機(jī)建立若干個(gè)虛電路，每個(gè)主機(jī)也可以同時(shí)和若干主機(jī)個(gè)建立虛電路。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層分組交換(packetswitching)分組交換結(jié)合報(bào)文虛電路與數(shù)據(jù)報(bào)的比較計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層虛電路與數(shù)據(jù)報(bào)的比較計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)虛電路與數(shù)據(jù)報(bào)之間的權(quán)衡路由器內(nèi)存空間與帶寬的權(quán)衡虛電路占用路由器中的表空間每個(gè)數(shù)據(jù)報(bào)都攜帶完整的目的/源地址，浪費(fèi)帶寬連接建立時(shí)間與地址查找時(shí)間的權(quán)衡虛電路需要在建立連接時(shí)花費(fèi)時(shí)間數(shù)據(jù)報(bào)則在每次路由時(shí)過(guò)程復(fù)雜服務(wù)質(zhì)量和健壯性的權(quán)衡虛電路方式很容易保證服務(wù)質(zhì)量QoS(QualityofService)，適用于實(shí)時(shí)操作，但比較脆弱。通信線路的故障，對(duì)于虛電路而言有時(shí)是致命的。數(shù)據(jù)報(bào)不太容易保證服務(wù)質(zhì)量，但是對(duì)于通信線路的故障，卻很容易得到補(bǔ)償。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層虛電路與數(shù)據(jù)報(bào)之間的權(quán)衡路由器內(nèi)存空間與帶寬的權(quán)衡計(jì)算機(jī)MHHHAR5R2R1R3R4HBM1M3M2M1M2M3M1M2M3舉例請(qǐng)判斷是虛電路還是數(shù)據(jù)報(bào)？計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層MHHHAR5R2R1R3R4HBM1M3M2M1M2M3M網(wǎng)絡(luò)層提供的服務(wù)網(wǎng)絡(luò)層為傳輸層提供的服務(wù)面向連接服務(wù)：將復(fù)雜的功能放在網(wǎng)絡(luò)層(通信子網(wǎng))。建立連接傳輸數(shù)據(jù)拆除連接無(wú)連接服務(wù)：將復(fù)雜的功能放在傳輸層。只負(fù)責(zé)傳輸分組。通信子網(wǎng)提供的服務(wù)(面向連接或無(wú)連接)與通信子網(wǎng)結(jié)構(gòu)(虛電路或數(shù)據(jù)報(bào))無(wú)關(guān)。面向連接的服務(wù)用虛電路來(lái)實(shí)現(xiàn)(比較合理)面向連接的服務(wù)用數(shù)據(jù)報(bào)來(lái)實(shí)現(xiàn)面向無(wú)連接的服務(wù)用虛電路來(lái)實(shí)現(xiàn)面向無(wú)連接的服務(wù)用數(shù)據(jù)報(bào)來(lái)實(shí)現(xiàn)(比較合理)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層網(wǎng)絡(luò)層提供的服務(wù)網(wǎng)絡(luò)層為傳輸層提供的服務(wù)計(jì)算機(jī)網(wǎng)絡(luò)通信子網(wǎng)結(jié)構(gòu)及其提供的服務(wù)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層通信子網(wǎng)結(jié)構(gòu)及其提供的服務(wù)計(jì)算機(jī)網(wǎng)絡(luò)原理——小結(jié)—網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的地位確定分組從源地址到目的地址如何進(jìn)行路由。網(wǎng)絡(luò)層需要解決的問(wèn)題屏蔽各種不同類型網(wǎng)絡(luò)之間的差異實(shí)現(xiàn)全網(wǎng)的數(shù)據(jù)傳輸網(wǎng)絡(luò)層的兩種實(shí)現(xiàn)方式——數(shù)據(jù)報(bào)和虛電路都屬于分組交換，采用存貯轉(zhuǎn)發(fā)機(jī)制。數(shù)據(jù)報(bào)(datagram)：每個(gè)分組被單獨(dú)處理，每個(gè)分組帶有自己的目的地址和序號(hào)被發(fā)出。虛電路(virtualcircuit)：先在發(fā)送主機(jī)和目的主機(jī)之間建立一條邏輯連接，所有的分組按照循序依次被發(fā)送。最后虛電路將被拆除。在虛電路方法中，每個(gè)分組無(wú)須進(jìn)行路徑選擇。網(wǎng)絡(luò)層提供的服務(wù)面向連接的服務(wù)和無(wú)連接的服務(wù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層小結(jié)—網(wǎng)絡(luò)層概述網(wǎng)絡(luò)層的地位計(jì)算機(jī)網(wǎng)絡(luò)原理路由算法路由算法路由算法路由算法是網(wǎng)絡(luò)層軟件的一部分子網(wǎng)采用數(shù)據(jù)報(bào)方式，每個(gè)分組都要做路由選擇。子網(wǎng)采用虛電路方式，只需在建立連接時(shí)做一次路由選擇。路由算法應(yīng)具有的特性正確性(correctness)、簡(jiǎn)單性(simplicity)、健壯性(robustness)、穩(wěn)定性(stability)、公平性(fairness)、最優(yōu)性(optimality)路由算法分類非自適應(yīng)算法(靜態(tài)路由算法)：按照預(yù)先計(jì)算好的(off-line)信息進(jìn)行路由。自適應(yīng)算法(動(dòng)態(tài)路由算法)：根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通信量等地變化來(lái)改變路由。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層路由算法路由算法是網(wǎng)絡(luò)層軟件的一部分計(jì)算機(jī)網(wǎng)絡(luò)原最優(yōu)化原則最優(yōu)化原則(optimalityprinciple)如果路由器J在路由器I到K的最優(yōu)路由上，那么從J到K的最優(yōu)路由會(huì)落在同一路由上。匯集樹(shù)(sinktree)路由算法的目的是找出并使用匯集樹(shù)。從所有的源

結(jié)點(diǎn)到一個(gè)給定的目的結(jié)點(diǎn)的最優(yōu)路由的集合形成了一個(gè)以目的結(jié)點(diǎn)為根的樹(shù)，稱為匯集樹(shù)。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層最優(yōu)化原則最優(yōu)化原則(optimalityprincipl幾種常見(jiàn)的路由算法靜態(tài)路由算法最短路徑選擇(ShortestPathRouting)洪泛算法(FloodingRouting)基于流量的路由算法(Flow-BasedRouting)動(dòng)態(tài)路由算法距離向量路由算法(DistanceVectorRouting)鏈路狀態(tài)路由算法(LinkStateRouting)分級(jí)路由(HierarchicalRouting)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層幾種常見(jiàn)的路由算法靜態(tài)路由算法計(jì)算機(jī)網(wǎng)絡(luò)原理—最短路徑路由算法基本思想構(gòu)建子網(wǎng)的拓?fù)鋱D，圖中的每個(gè)結(jié)點(diǎn)代表一個(gè)路由器，每條弧代表一條通信線路。目的是構(gòu)建兩個(gè)路由器間的路由，算法是在子網(wǎng)拓?fù)鋱D中找出最短路徑。得到最短路徑，有不同的測(cè)量

路徑長(zhǎng)度的方法：計(jì)算結(jié)點(diǎn)數(shù)量計(jì)算地理距離計(jì)算傳輸延遲計(jì)算距離、信道帶寬等參數(shù)的加權(quán)函數(shù)……Dijkstra算法是其中的一種計(jì)算最短路徑的算法。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層最短路徑路由算法基本思想計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)Dijkstra算法每個(gè)結(jié)點(diǎn)用從源結(jié)點(diǎn)沿已知最佳路徑到本結(jié)點(diǎn)的距離來(lái)標(biāo)注，標(biāo)注分為臨時(shí)性標(biāo)注和永久性標(biāo)注。開(kāi)始時(shí)，所有結(jié)點(diǎn)都為臨時(shí)性標(biāo)注，標(biāo)注為無(wú)窮大。源結(jié)點(diǎn)標(biāo)注為0，且為永久性標(biāo)注，令其為工作結(jié)點(diǎn)。檢查與工作結(jié)點(diǎn)相鄰的臨時(shí)性結(jié)點(diǎn)，若該結(jié)點(diǎn)到工作結(jié)點(diǎn)的距離與工作結(jié)點(diǎn)的標(biāo)注之和小于該結(jié)點(diǎn)的標(biāo)注，則用新計(jì)算得到的和重新標(biāo)注該結(jié)點(diǎn)。在整個(gè)圖中查找具有最小值的臨時(shí)性標(biāo)注結(jié)點(diǎn)，將其變?yōu)橛谰眯越Y(jié)點(diǎn)，并成為下一輪檢查的工作結(jié)點(diǎn)。重復(fù)第三、四步，直到目的結(jié)點(diǎn)成為工作結(jié)點(diǎn)。Dijkstra算法的圖例。Dijkstra算法的程序：與算法的區(qū)別是從目的結(jié)點(diǎn)開(kāi)始。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Dijkstra算法每個(gè)結(jié)點(diǎn)用從源結(jié)點(diǎn)沿已知最佳路徑到本結(jié)點(diǎn)Dijkstra算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Dijkstra算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)Dijkstra算法程序計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層Dijkstra算法程序計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)洪泛算法基本思想把收到的每一個(gè)分組，向除了該分組到來(lái)的線路外的所有輸出線路發(fā)送。主要問(wèn)題洪泛要產(chǎn)生大量重復(fù)分組。解決措施每個(gè)報(bào)頭包含站點(diǎn)計(jì)數(shù)器，每經(jīng)過(guò)一站計(jì)數(shù)器減1，為0時(shí)則丟棄該分組。記錄下分組擴(kuò)展的路徑，防止它第二次擴(kuò)散到已經(jīng)擴(kuò)散過(guò)的路徑中。較實(shí)用的方法——選擇性洪泛算法(selectiveflooding)洪泛法的一種改進(jìn)：將進(jìn)來(lái)的每個(gè)分組僅發(fā)送到與正確方向接近的線路上。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層洪泛算法基本思想計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層洪泛算法應(yīng)用情況洪泛算法由于過(guò)于浪費(fèi)路由器和線路的資源，在實(shí)際應(yīng)用中很難被直接采用，但還是有一些用處的。在軍事領(lǐng)域中，由于需要極好的健壯性，擴(kuò)散法可以一展身手。在分布式數(shù)據(jù)庫(kù)中，有時(shí)需要并行地更新所有數(shù)據(jù)庫(kù)，這時(shí)洪泛算法也是最佳方案。因?yàn)楹榉核惴偸悄軌蜻x擇最短的路徑，可以產(chǎn)生一個(gè)最短的延遲。洪泛算法可以作為一種尺度衡量標(biāo)準(zhǔn)來(lái)評(píng)價(jià)其它路由算法。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層洪泛算法應(yīng)用情況計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層基于流量的路由算法基本思想既考慮拓?fù)浣Y(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負(fù)荷。前提：每對(duì)結(jié)點(diǎn)間平均數(shù)據(jù)流是相對(duì)穩(wěn)定和可預(yù)測(cè)的。根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均分組延遲，因此路由算法就演變?yōu)閷ふ揖W(wǎng)絡(luò)中連接兩個(gè)路由器的線路上具有最小平均分組延遲的問(wèn)題。需要預(yù)知的信息網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。通信量矩陣Fij，即線路ij之間的平均通信量。線路帶寬矩陣Cij，即線路ij之間允許的最大通信量。臨時(shí)的路由算法。圖例。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層基于流量的路由算法基本思想計(jì)算機(jī)網(wǎng)絡(luò)原理——基于流量的路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層基于流量的路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)

根據(jù)隊(duì)列原理，線路平均分組延遲的計(jì)算公式為：T=1/(C-)1/=800bit基于流量的路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層根據(jù)隊(duì)列原理，線路平均分組延遲的計(jì)算公式為：基于流量距離向量路由算法屬于動(dòng)態(tài)路由算法，最初用于ARPANET,DECnet等網(wǎng)絡(luò)?；舅枷耄好總€(gè)路由器維護(hù)一張表，表中列出了到每個(gè)目的地址的最佳距離和線路，并通過(guò)與鄰居結(jié)點(diǎn)交換信息來(lái)更新表。表(路由表)的構(gòu)成：以子網(wǎng)中其它路由器為表的索引，到達(dá)目的結(jié)點(diǎn)的最佳輸出線路，和到達(dá)目的結(jié)點(diǎn)所需時(shí)間或距離。路由器需要知曉自己到鄰居結(jié)點(diǎn)的“距離”。所用的度量標(biāo)準(zhǔn)可以為站點(diǎn)、估計(jì)的時(shí)間延遲等。如果為站點(diǎn)，本路由器到每個(gè)鄰居結(jié)點(diǎn)的距離都為1。如果是延遲，本路由器就發(fā)送一個(gè)要對(duì)方立即響應(yīng)的ECHO分組，用來(lái)回時(shí)間除以2即得到延遲時(shí)間，每隔一段時(shí)間，路由器向所有鄰居結(jié)點(diǎn)發(fā)送它到每個(gè)目的結(jié)點(diǎn)的距離表，同時(shí)它也接收每個(gè)鄰居結(jié)點(diǎn)發(fā)來(lái)的距離表。鄰居結(jié)點(diǎn)X發(fā)來(lái)的表中，X到路由器i的距離為Xi。本路由器到X的距離為m，則本路由器經(jīng)過(guò)X到i的距離為Xi+m。根據(jù)不同鄰居發(fā)來(lái)的信息，計(jì)算Xi+m，取最小值，更新本路由器的表。注意：在計(jì)算中不使用本路由器中的老路由表。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層距離向量路由算法屬于動(dòng)態(tài)路由算法，最初用于ARPANET,D距離向量路由算法圖例路由器J計(jì)算到達(dá)路由器C的最新路由JAC=8+25=33msJIC=10+18=28msJHC=12+19=31msJKC=6+36=42ms其中JIC是最好的。因此在路由器J的新路由表中填上到C的延遲為28ms，經(jīng)過(guò)路由器I。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層距離向量路由算法圖例計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)距離向量路由算法的缺陷缺陷——無(wú)窮計(jì)算問(wèn)題對(duì)好消息反應(yīng)迅速：在最長(zhǎng)路徑為N各結(jié)點(diǎn)的子網(wǎng)中，在N次交換之內(nèi)，所有的路由器都會(huì)指導(dǎo)新增的線路和路由器。對(duì)壞消息反應(yīng)遲鈍：對(duì)于已經(jīng)消失的結(jié)點(diǎn)，相互欺騙。圖例如下。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層距離向量路由算法的缺陷缺陷——無(wú)窮計(jì)算問(wèn)題計(jì)算機(jī)網(wǎng)絡(luò)水平分裂算法基本思想工作過(guò)程與距離向量算法相同，區(qū)別在于到X的距離不向真正通向X的鄰居結(jié)點(diǎn)報(bào)告。從而使得壞消息以每次一個(gè)結(jié)點(diǎn)的速度傳播。舉例：如右圖。在路由信息的交換中，B知道可以直達(dá)A，并告訴C，通過(guò)B到C路徑為1。C得到B發(fā)來(lái)的路由信息后，告訴D通過(guò)C到達(dá)A距離為2，告訴B通過(guò)C到達(dá)A為無(wú)窮。D得到C發(fā)來(lái)的路由信息后，告訴E通過(guò)D到達(dá)A距離為3，告訴C通過(guò)D到達(dá)A為無(wú)窮。當(dāng)A下網(wǎng)后，第一次交換：B發(fā)現(xiàn)到達(dá)A的直達(dá)路線沒(méi)有了，而且C也向B說(shuō)到達(dá)A為無(wú)窮，故B將其到達(dá)A的距離設(shè)置為無(wú)窮。第二次交換：C得到B的通知，B到達(dá)A為無(wú)窮；同時(shí)D也告訴C，通過(guò)D到達(dá)A為無(wú)窮，故C將其到達(dá)A的距離設(shè)置為無(wú)窮。以次類推，在第四次交換的時(shí)候，E也知道A不可達(dá)了。解決方案之一水平分裂ABCDE計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層水平分裂算法基本思想解決方案之一水平分裂ABCDE計(jì)算機(jī)水平分裂不能解決所有的問(wèn)題水平分裂雖然廣泛使用，但有時(shí)候會(huì)失敗。如右圖。開(kāi)始時(shí)，A和B到D的舉例都為2，C到D的舉例為1。假設(shè)CD線路斷了，使用水平分裂，A和B都告訴C，它們不能到達(dá)D，同時(shí)C自己也發(fā)現(xiàn)直達(dá)D的線路斷了，于是C很快認(rèn)定D不可達(dá)了。但是，A認(rèn)為B有一條通向D長(zhǎng)度為2的路徑，通過(guò)B經(jīng)過(guò)3個(gè)結(jié)點(diǎn)可到達(dá)D。類似，B也這樣認(rèn)為。于是兩個(gè)結(jié)點(diǎn)每交換一次信息，到達(dá)D的距離就增加1，直至加大無(wú)窮。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層水平分裂不能解決所有的問(wèn)題水平分裂雖然廣泛使用，但有時(shí)候會(huì)失鏈路狀態(tài)路由算法距離向量路由算法的主要問(wèn)題由于延遲度量?jī)H僅是隊(duì)列長(zhǎng)度，在選擇路由時(shí)沒(méi)有考慮線路帶寬。即使使用了水平分裂，路由收斂速度依然慢。在1979年前，ARPANET上都采用距離向量路由算法，但是之后，即為鏈路狀態(tài)路由算法所替代。鏈路狀態(tài)路由算法的簡(jiǎn)單步驟發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或開(kāi)銷。將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)分組。將這個(gè)分組發(fā)送給所有其它路由器。計(jì)算到每個(gè)其它路由器的最短路徑。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層鏈路狀態(tài)路由算法距離向量路由算法的主要問(wèn)題計(jì)算機(jī)網(wǎng)絡(luò)步驟1：發(fā)現(xiàn)鄰居結(jié)點(diǎn)發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。路由器啟動(dòng)后，通過(guò)發(fā)送HELLO分組，并得到鄰居路由器的響應(yīng)來(lái)發(fā)現(xiàn)鄰居結(jié)點(diǎn)。路由器的名稱必須是唯一的。當(dāng)兩個(gè)或多個(gè)路由器連在一個(gè)LAN時(shí)，引入人工結(jié)點(diǎn)。圖例。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟1：發(fā)現(xiàn)鄰居結(jié)點(diǎn)發(fā)現(xiàn)鄰居結(jié)點(diǎn)，并學(xué)習(xí)它們的網(wǎng)絡(luò)地址。計(jì)步驟2/3：測(cè)量線路開(kāi)銷和封裝分組測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或開(kāi)銷，一種直接的方法是：發(fā)送一個(gè)要對(duì)方立即響應(yīng)的ECHO分組，來(lái)回時(shí)間除以2即為延遲時(shí)間。如果在測(cè)量延遲時(shí)間的時(shí)候，考慮負(fù)載，會(huì)是什么情況？（自學(xué)）將所有學(xué)習(xí)到的內(nèi)容封裝成一個(gè)分組，即在信息收集完畢后，構(gòu)造一個(gè)包含所有數(shù)據(jù)的分組。該分組的結(jié)構(gòu)為：發(fā)送方的標(biāo)識(shí)符、序號(hào)、年齡、鄰居結(jié)點(diǎn)列表（鄰居結(jié)點(diǎn)標(biāo)識(shí)符，線路開(kāi)銷值）。創(chuàng)建鏈路狀態(tài)分組的時(shí)機(jī)：一是定期創(chuàng)建，一是在發(fā)生重大事件后創(chuàng)建。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟2/3：測(cè)量線路開(kāi)銷和封裝分組測(cè)量到每個(gè)鄰居結(jié)點(diǎn)的延遲或步驟4：發(fā)布鏈路狀態(tài)分組鏈路狀態(tài)分組的發(fā)布算法基本思想：洪泛鏈路狀態(tài)分組。為控制洪泛，每個(gè)分組中增加一個(gè)序號(hào)域，每次發(fā)送新分組時(shí)加1。路由器記錄信息對(duì)(源路由器，序號(hào))，當(dāng)一個(gè)鏈路狀態(tài)分組到達(dá)時(shí)，若是新的，則分發(fā)；若是重復(fù)的，則丟棄；若序號(hào)比路由器記錄中的最大序號(hào)小，則認(rèn)為過(guò)時(shí)而丟棄?；舅惴ㄋa(chǎn)生的問(wèn)題序號(hào)循環(huán)使用會(huì)混淆。路由器崩潰后，所有的序號(hào)丟失，從0開(kāi)始記，以后所有的新到分組都可能被當(dāng)作重復(fù)分組而被拒絕。序號(hào)在發(fā)送出去后出現(xiàn)錯(cuò)誤。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟4：發(fā)布鏈路狀態(tài)分組鏈路狀態(tài)分組的發(fā)布算法計(jì)算機(jī)網(wǎng)步驟4：發(fā)布鏈路狀態(tài)分組基本算法的改進(jìn)方案為了避免序號(hào)重復(fù)，使用32位的序號(hào)。解決序號(hào)丟失和出錯(cuò)的方法是增加年齡(age)域，每秒鐘年齡減1，至零則丟棄。鏈路狀態(tài)分組到達(dá)后，延遲一段時(shí)間(被放置在一個(gè)保持區(qū)中)，并與其它已到達(dá)的來(lái)自同一路由器的鏈路狀態(tài)分組比較序號(hào)，丟棄重復(fù)分組和超齡分組。為了防止鏈路出錯(cuò)，所有的鏈路狀態(tài)分組都需要應(yīng)答。計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟4：發(fā)布鏈路狀態(tài)分組基本算法的改進(jìn)方案計(jì)算機(jī)網(wǎng)絡(luò)步驟5：計(jì)算新路由在路由器積累了一整套網(wǎng)絡(luò)的鏈路狀態(tài)分組后，就可以通過(guò)計(jì)算得到整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)?？梢岳肈ijkstra算法計(jì)算得到每個(gè)其它路由器的最短路徑?；阪溌窢顟B(tài)的路由協(xié)議OpenShortestPathFirst(OSPF)IntermediateSystem-IntermediateSystem(IS-IS)計(jì)算機(jī)網(wǎng)絡(luò)原理——網(wǎng)絡(luò)層步驟5：計(jì)算新路由在路由器積累了一整套網(wǎng)絡(luò)的鏈路狀態(tài)分組后，分級(jí)路由網(wǎng)絡(luò)規(guī)模增長(zhǎng)帶來(lái)的問(wèn)題路由器中的路由表增大。路由器為選擇路由而占用的內(nèi)存、CPU時(shí)間和網(wǎng)絡(luò)帶寬增大。解決辦法——分級(jí)路由對(duì)于大型網(wǎng)絡(luò)分而治之，每個(gè)路由器只知道自己所在子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。根據(jù)需要，可以分成區(qū)域(regions)、聚類(clusters)、區(qū)(zo