1、2000 年年 11 月月14日日n網(wǎng)絡(luò)層概述 n網(wǎng)絡(luò)層的地位n網(wǎng)絡(luò)層需要解決的問題n數(shù)據(jù)報和虛電路n網(wǎng)絡(luò)層提供的服務(wù)n路由算法 n最優(yōu)化原則n最短路徑路由算法n洪泛算法n基于流量的路由算法n距離向量路由算法n鏈路狀態(tài)路由算法n分級路由n擁塞控制算法 n擁塞控制的基本原理n開環(huán)控制n擁塞預防策略n通信量整形(漏桶和令牌桶)n流說明n閉環(huán)控制n虛電路網(wǎng)絡(luò)中的擁塞控制n抑制分組n負載丟棄n網(wǎng)絡(luò)互聯(lián)技術(shù) n級聯(lián)虛電路n無連接網(wǎng)絡(luò)互聯(lián)n隧道技術(shù)n互聯(lián)網(wǎng)路由n分段n防火墻nInternet網(wǎng)絡(luò)層協(xié)議 n支撐協(xié)議nIP/ICMP協(xié)議nARP/RARP協(xié)議n內(nèi)部網(wǎng)關(guān)路由協(xié)議nRIP，OSPFn外部網(wǎng)關(guān)路由協(xié)

2、議nBGPn當今流行的通信技術(shù)n傳統(tǒng)的電信網(wǎng)絡(luò)：線路交換、x.25、幀中繼、ATM。n計算機網(wǎng)絡(luò)：ARPANET、INTERNET等。n有線電視網(wǎng)絡(luò)。n計算機網(wǎng)絡(luò)中的網(wǎng)絡(luò)層至關(guān)重要n網(wǎng)絡(luò)層是通信子網(wǎng)的最高層，關(guān)系著整個網(wǎng)絡(luò)的運行控制。n網(wǎng)絡(luò)層需要解決的問題是確定分組從源地址到目的地址是如何路由的。n網(wǎng)絡(luò)層利用數(shù)據(jù)鏈路層提供的服務(wù)，為傳輸層提供服務(wù)。網(wǎng)絡(luò)層處理端到端傳輸?shù)淖畹蛯?。n在廣播網(wǎng)絡(luò)中，路由選擇很簡單，所以網(wǎng)絡(luò)層也很薄，甚至不存在。而在大型網(wǎng)絡(luò)中，分組不得不跨越若干個網(wǎng)絡(luò)到達目的地址，這其中的種種問題就需要由網(wǎng)絡(luò)層來解決。n網(wǎng)絡(luò)層為了能夠了解通信子網(wǎng)的拓撲結(jié)構(gòu)，以便選擇路由，需要解決以下

3、問題：n屏蔽各種不同類型網(wǎng)絡(luò)之間的差異n需要統(tǒng)一數(shù)據(jù)格式n需要統(tǒng)一網(wǎng)絡(luò)地址n實現(xiàn)全網(wǎng)的數(shù)據(jù)傳輸n建立跨越網(wǎng)絡(luò)的虛電路n網(wǎng)絡(luò)之間實現(xiàn)分組的尋址和轉(zhuǎn)發(fā)n網(wǎng)絡(luò)層的兩種實現(xiàn)方式n虛電路(virtual circuit)：提供面向連接的服務(wù)。n類似于電話，先建立連接，之后依次發(fā)送分組，最后關(guān)閉連接。n避免對每個分組進行路由。n數(shù)據(jù)報(datagram)：提供無連接的服務(wù)。n類似于發(fā)送信件。對每個數(shù)據(jù)報(對于無連接中的獨立分組稱作數(shù)據(jù)報)分別進行路由。n計算機網(wǎng)絡(luò)總是由資源子網(wǎng)和通信子網(wǎng)組成。通信交換技術(shù)是指數(shù)據(jù)信息如何在通信子網(wǎng)的各個結(jié)點之間進行傳輸?shù)?。通常存在三種交換技術(shù)：線路交換、報文交換和分組交換

4、。還存在某幾個技術(shù)的融合，即混合交換。n線路交換(circuit switching)在網(wǎng)絡(luò)中利用可切換的物理通信線路直接連接通信雙方。n最常見的例子是電話系統(tǒng)。n線路交換包括三種狀態(tài)：線路建立、數(shù)據(jù)傳送、線路拆除。n線路交換方式中通道是專用的，利用效率低，并存在延遲。n報文交換(message switching)是指信息以報文(邏輯上完整的信息段)為單位進行。HHHAR5R2R3Router1R4HBMMMMMn發(fā)送報文的主機在發(fā)送之前，要將報文的目的地址附加在報文前面。然后將報文發(fā)送到網(wǎng)絡(luò)中的結(jié)點中。n每個網(wǎng)絡(luò)中的結(jié)點將完整地接收報文，暫存報文，然后將報文發(fā)送到下一個更接近目的主機的結(jié)點

5、中。如此操作，直至將報文發(fā)送到目的主機為止。n分組交換結(jié)合報文交換和線路交換的優(yōu)點，采用存儲轉(zhuǎn)發(fā)機制，但是規(guī)定了傳輸數(shù)據(jù)的單位長度。n過長的報文被分成較小的單位(分組packet)，依次發(fā)送。n如何管理這些分組的正確傳輸：數(shù)據(jù)報和虛電路。n數(shù)據(jù)報(datagram)：每個分組被單獨處理。n每個分組帶有自己的目的地址和序號被發(fā)出，由通信子網(wǎng)中的結(jié)點進行路由選擇。n在所有分組到達了目的主機后，再將各個分組按照序號編排起來。n虛電路(virtual circuit)：n在發(fā)送任何分組之前，首先在發(fā)送主機和目的主機之間建立一條邏輯連接，即在通信子網(wǎng)中確定一條用于本次傳輸數(shù)據(jù)用的結(jié)點序列。n建立虛電路后

6、，所有的分組都將按照循序依次被發(fā)送到目的主機。n當所有的分組都發(fā)送之后，虛電路將被拆除。在虛電路方法中，每個分組無須進行路徑選擇。n每個主機可以和另一個主機建立若干個虛電路，每個主機也可以同時和若干主機個建立虛電路。n路由器內(nèi)存空間與帶寬的權(quán)衡n虛電路占用路由器中的表空間n每個數(shù)據(jù)報都攜帶完整的目的/源地址，浪費帶寬n連接建立時間與地址查找時間的權(quán)衡n虛電路需要在建立連接時花費時間n數(shù)據(jù)報則在每次路由時過程復雜n服務(wù)質(zhì)量和健壯性的權(quán)衡n虛電路方式很容易保證服務(wù)質(zhì)量QoS(Quality of Service)，適用于實時操作，但比較脆弱。通信線路的故障，對于虛電路而言有時是致命的。n數(shù)據(jù)報不太

7、容易保證服務(wù)質(zhì)量，但是對于通信線路的故障，卻很容易得到補償。MHHHAR5R2R1R3R4HBM1M3M2M1M2M3M1M2M3n請判斷是虛電路還是數(shù)據(jù)報？n網(wǎng)絡(luò)層為傳輸層提供的服務(wù)n面向連接服務(wù)：將復雜的功能放在網(wǎng)絡(luò)層(通信子網(wǎng))。n建立連接n傳輸數(shù)據(jù)n拆除連接n無連接服務(wù)：將復雜的功能放在傳輸層。n只負責傳輸分組。n通信子網(wǎng)提供的服務(wù)(面向連接或無連接)與通信子網(wǎng)結(jié)構(gòu)(虛電路或數(shù)據(jù)報)無關(guān)。n面向連接的服務(wù)用虛電路來實現(xiàn)(比較合理)n面向連接的服務(wù)用數(shù)據(jù)報來實現(xiàn)n面向無連接的服務(wù)用虛電路來實現(xiàn)n面向無連接的服務(wù)用數(shù)據(jù)報來實現(xiàn)(比較合理)n網(wǎng)絡(luò)層的地位n確定分組從源地址到目的地址如何進行路

8、由。n網(wǎng)絡(luò)層需要解決的問題n屏蔽各種不同類型網(wǎng)絡(luò)之間的差異n實現(xiàn)全網(wǎng)的數(shù)據(jù)傳輸n網(wǎng)絡(luò)層的兩種實現(xiàn)方式 數(shù)據(jù)報和虛電路n都屬于分組交換，采用存貯轉(zhuǎn)發(fā)機制。n數(shù)據(jù)報(datagram)：每個分組被單獨處理，每個分組帶有自己的目的地址和序號被發(fā)出。n虛電路(virtual circuit)：先在發(fā)送主機和目的主機之間建立一條邏輯連接，所有的分組按照循序依次被發(fā)送。最后虛電路將被拆除。在虛電路方法中，每個分組無須進行路徑選擇。n網(wǎng)絡(luò)層提供的服務(wù)n面向連接的服務(wù)和無連接的服務(wù)。n路由算法是網(wǎng)絡(luò)層軟件的一部分n子網(wǎng)采用數(shù)據(jù)報方式，每個分組都要做路由選擇。n子網(wǎng)采用虛電路方式，只需在建立連接時做一次路由選擇

9、。n路由算法應具有的特性n正確性(correctness)、簡單性(simplicity)、健壯性(robustness)、穩(wěn)定性(stability)、公平性(fairness)、最優(yōu)性(optimality)n路由算法分類n非自適應算法(靜態(tài)路由算法)：按照預先計算好的(off-line)信息進行路由。n自適應算法(動態(tài)路由算法)：根據(jù)網(wǎng)絡(luò)拓撲結(jié)構(gòu)，通信量等地變化來改變路由。n最優(yōu)化原則(optimality principle)n如果路由器 J 在路由器 I 到 K 的最優(yōu)路由上，那么從 J 到 K 的最優(yōu)路由會落在同一路由上。n匯集樹(sink tree)n路由算法的目的是找出并使用匯

10、集樹。n從所有的源結(jié)點到一個給定的目的結(jié)點的最優(yōu)路由的集合形成了一個以目的結(jié)點為根的樹，稱為匯集樹。n靜態(tài)路由算法n最短路徑選擇(Shortest Path Routing) n洪泛算法(Flooding Routing) n基于流量的路由算法(Flow-Based Routing) n動態(tài)路由算法n距離向量路由算法(Distance Vector Routing) n鏈路狀態(tài)路由算法(Link State Routing) n分級路由(Hierarchical Routing) n基本思想n構(gòu)建子網(wǎng)的拓撲圖，圖中的每個結(jié)點代表一個路由器，每條弧代表一條通信線路。n目的是構(gòu)建兩個路由器間的路由

11、，算法是在子網(wǎng)拓撲圖中找出最短路徑。n得到最短路徑，有不同的測量路徑長度的方法：n計算結(jié)點數(shù)量n計算地理距離n計算傳輸延遲n計算距離、信道帶寬等參數(shù)的加權(quán)函數(shù)nnDijkstra算法是其中的一種計算最短路徑的算法。n每個結(jié)點用從源結(jié)點沿已知最佳路徑到本結(jié)點的距離來標注，標注分為臨時性標注和永久性標注。開始時，所有結(jié)點都為臨時性標注，標注為無窮大。n源結(jié)點標注為0，且為永久性標注，令其為工作結(jié)點。n檢查與工作結(jié)點相鄰的臨時性結(jié)點，若該結(jié)點到工作結(jié)點的距離與工作結(jié)點的標注之和小于該結(jié)點的標注，則用新計算得到的和重新標注該結(jié)點。n在整個圖中查找具有最小值的臨時性標注結(jié)點，將其變?yōu)橛谰眯越Y(jié)點，并成為下

12、一輪檢查的工作結(jié)點。n重復第三、四步，直到目的結(jié)點成為工作結(jié)點。nDijkstra算法的圖例。nDijkstra算法的程序：與算法的區(qū)別是從目的結(jié)點開始。n基本思想n把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發(fā)送。n主要問題n洪泛要產(chǎn)生大量重復分組。n解決措施n每個報頭包含站點計數(shù)器，每經(jīng)過一站計數(shù)器減1，為0時則丟棄該分組。n記錄下分組擴展的路徑，防止它第二次擴散到已經(jīng)擴散過的路徑中。n較實用的方法選擇性洪泛算法(selective flooding)n洪泛法的一種改進：將進來的每個分組僅發(fā)送到與正確方向接近的線路上。n應用情況n洪泛算法由于過于浪費路由器和線路的資源，在實際

13、應用中很難被直接采用，但還是有一些用處的。n在軍事領(lǐng)域中，由于需要極好的健壯性，擴散法可以一展身手。n在分布式數(shù)據(jù)庫中，有時需要并行地更新所有數(shù)據(jù)庫，這時洪泛算法也是最佳方案。n因為洪泛算法總是能夠選擇最短的路徑，可以產(chǎn)生一個最短的延遲。洪泛算法可以作為一種尺度衡量標準來評價其它路由算法。n基本思想n既考慮拓撲結(jié)構(gòu)，又兼顧網(wǎng)絡(luò)負荷。n前提：每對結(jié)點間平均數(shù)據(jù)流是相對穩(wěn)定和可預測的。n根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均分組延遲，因此路由算法就演變?yōu)閷ふ揖W(wǎng)絡(luò)中連接兩個路由器的線路上具有最小平均分組延遲的問題。n需要預知的信息n網(wǎng)絡(luò)拓撲結(jié)構(gòu)。n通信量矩陣Fij，即線路ij之間的平均通信量。n線路帶寬

14、矩陣Cij，即線路ij 之間允許的最大通信量。n臨時的路由算法。n圖例。 根據(jù)隊列原理，線路平均分組延遲的計算公式為： T=1/(C-) 1/=800 bitn屬于動態(tài)路由算法，最初用于ARPANET,DECnet等網(wǎng)絡(luò)。n基本思想：每個路由器維護一張表，表中列出了到每個目的地址的最佳距離和線路，并通過與鄰居結(jié)點交換信息來更新表。n表(路由表)的構(gòu)成：以子網(wǎng)中其它路由器為表的索引，到達目的結(jié)點的最佳輸出線路，和到達目的結(jié)點所需時間或距離。n路由器需要知曉自己到鄰居結(jié)點的“距離”。所用的度量標準可以為站點、估計的時間延遲等。n如果為站點，本路由器到每個鄰居結(jié)點的距離都為1。n如果是延遲，本路由器

15、就發(fā)送一個要對方立即響應的ECHO分組，用來回時間除以2即得到延遲時間，n每隔一段時間，路由器向所有鄰居結(jié)點發(fā)送它到每個目的結(jié)點的距離表，同時它也接收每個鄰居結(jié)點發(fā)來的距離表。n鄰居結(jié)點X發(fā)來的表中，X到路由器i的距離為Xi。本路由器到X的距離為m，則本路由器經(jīng)過X到i的距離為Xi + m。根據(jù)不同鄰居發(fā)來的信息，計算Xi + m，取最小值，更新本路由器的表。n注意：在計算中不使用本路由器中的老路由表。路由器J計算到達路由器C的最新路由nJAC=8+25=33msnJIC=10+18=28msnJHC=12+19=31msnJKC=6+36=42ms其中JIC是最好的。因此在路由器J的新路由表

16、中填上到C的延遲為28ms，經(jīng)過路由器I。n缺陷無窮計算問題n對好消息反應迅速：在最長路徑為N各結(jié)點的子網(wǎng)中，在N次交換之內(nèi)，所有的路由器都會指導新增的線路和路由器。n對壞消息反應遲鈍：對于已經(jīng)消失的結(jié)點，相互欺騙。n圖例如下。n水平分裂算法基本思想n工作過程與距離向量算法相同，區(qū)別在于到X的距離不向真正通向X的鄰居結(jié)點報告。從而使得壞消息以每次一個結(jié)點的速度傳播。n舉例：如右圖。n在路由信息的交換中，B知道可以直達A，并告訴C，通過B到C路徑為1。C得到B發(fā)來的路由信息后，告訴D通過C到達A距離為2，告訴B通過C到達A為無窮。D得到C發(fā)來的路由信息后，告訴E通過D到達A距離為3，告訴C通過D

17、到達A為無窮。n當A下網(wǎng)后，n第一次交換：B發(fā)現(xiàn)到達A的直達路線沒有了，而且C也向B說到達A為無窮，故B將其到達A的距離設(shè)置為無窮。n第二次交換：C得到B的通知，B到達A為無窮；同時D也告訴C，通過D到達A為無窮，故C將其到達A的距離設(shè)置為無窮。n以次類推，在第四次交換的時候，E也知道A不可達了。ABCDEn水平分裂雖然廣泛使用，但有時候會失敗。n如右圖。n開始時，A和B到D的舉例都為2，C到D的舉例為1。n假設(shè)CD線路斷了，使用水平分裂，A和B都告訴C，它們不能到達D，同時C自己也發(fā)現(xiàn)直達D的線路斷了，于是C很快認定D不可達了。n但是，A認為B有一條通向D長度為2的路徑，通過B經(jīng)過3個結(jié)點可

18、到達D。類似，B也這樣認為。于是兩個結(jié)點每交換一次信息，到達D的距離就增加1，直至加大無窮。n距離向量路由算法的主要問題n由于延遲度量僅僅是隊列長度，在選擇路由時沒有考慮線路帶寬。n即使使用了水平分裂，路由收斂速度依然慢。n在1979年前，ARPANET上都采用距離向量路由算法，但是之后，即為鏈路狀態(tài)路由算法所替代。n鏈路狀態(tài)路由算法的簡單步驟n發(fā)現(xiàn)鄰居結(jié)點，并學習它們的網(wǎng)絡(luò)地址。n測量到每個鄰居結(jié)點的延遲或開銷。n將所有學習到的內(nèi)容封裝成一個分組。n將這個分組發(fā)送給所有其它路由器。n計算到每個其它路由器的最短路徑。n發(fā)現(xiàn)鄰居結(jié)點，并學習它們的網(wǎng)絡(luò)地址。n路由器啟動后，通過發(fā)送HELLO分組，

19、并得到鄰居路由器的響應來發(fā)現(xiàn)鄰居結(jié)點。n路由器的名稱必須是唯一的。n當兩個或多個路由器連在一個LAN時，引入人工結(jié)點。n圖例。n測量到每個鄰居結(jié)點的延遲或開銷，一種直接的方法是：發(fā)送一個要對方立即響應的ECHO分組，來回時間除以2即為延遲時間。n如果在測量延遲時間的時候，考慮負載，會是什么情況？（自學）n將所有學習到的內(nèi)容封裝成一個分組，即在信息收集完畢后，構(gòu)造一個包含所有數(shù)據(jù)的分組。n該分組的結(jié)構(gòu)為：發(fā)送方的標識符、序號、年齡、鄰居結(jié)點列表（鄰居結(jié)點標識符，線路開銷值）。n創(chuàng)建鏈路狀態(tài)分組的時機：一是定期創(chuàng)建，一是在發(fā)生重大事件后創(chuàng)建。n鏈路狀態(tài)分組的發(fā)布算法n基本思想：洪泛鏈路狀態(tài)分組。n

20、為控制洪泛，每個分組中增加一個序號域，每次發(fā)送新分組時加1。n路由器記錄信息對(源路由器，序號)，當一個鏈路狀態(tài)分組到達時，若是新的，則分發(fā)；若是重復的，則丟棄；若序號比路由器記錄中的最大序號小，則認為過時而丟棄。n基本算法所產(chǎn)生的問題n序號循環(huán)使用會混淆。n路由器崩潰后，所有的序號丟失，從0開始記，以后所有的新到分組都可能被當作重復分組而被拒絕。n序號在發(fā)送出去后出現(xiàn)錯誤。n基本算法的改進方案n為了避免序號重復，使用32位的序號。n解決序號丟失和出錯的方法是增加年齡(age)域，每秒鐘年齡減1，至零則丟棄。n鏈路狀態(tài)分組到達后，延遲一段時間(被放置在一個保持區(qū)中)，并與其它已到達的來自同一路

21、由器的鏈路狀態(tài)分組比較序號，丟棄重復分組和超齡分組。n為了防止鏈路出錯，所有的鏈路狀態(tài)分組都需要應答。n在路由器積累了一整套網(wǎng)絡(luò)的鏈路狀態(tài)分組后，就可以通過計算得到整個網(wǎng)絡(luò)的結(jié)構(gòu)?？梢岳肈ijkstra算法計算得到每個其它路由器的最短路徑。n基于鏈路狀態(tài)的路由協(xié)議nOpen Shortest Path First (OSPF)nIntermediate System-Intermediate System (IS-IS)n網(wǎng)絡(luò)規(guī)模增長帶來的問題n路由器中的路由表增大。n路由器為選擇路由而占用的內(nèi)存、CPU時間和網(wǎng)絡(luò)帶寬增大。n解決辦法 分級路由n對于大型網(wǎng)絡(luò)分而治之，每個路由器只知道自己所在

22、子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。n根據(jù)需要，可以分成區(qū)域(regions)、聚類(clusters)、區(qū)(zones)和組(groups) n圖例。n分級路由帶來的問題n路由表中的路由不一定是最優(yōu)路由。n最優(yōu)化原則n路由算法的目的是找出并使用匯集樹。n最短路徑路由算法n目的是構(gòu)建兩個路由器間的路由，算法是在子網(wǎng)拓撲圖中找出最短路徑。Dijkstra算法。n洪泛算法n把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發(fā)送。n基于流量的路由算法n根據(jù)網(wǎng)絡(luò)帶寬和平均流量，可得出平均延遲，因此路由問題歸結(jié)為找產(chǎn)生網(wǎng)絡(luò)最小延遲的路由算法。n距離向量路由算法n根據(jù)兩個結(jié)點間的隊列長度

23、來完成路由選擇，但是最大的問題是無窮計算，而且水平分裂也不能完全解決所有的問題。n鏈路狀態(tài)路由算法n發(fā)現(xiàn)鄰居結(jié)點n測量線路開銷n將所有學習到的內(nèi)容封裝成一個分組n發(fā)布鏈路狀態(tài)信息n計算新路由n分級路由n對于大型網(wǎng)絡(luò)分而治之，每個路由器只知道自己所在子網(wǎng)的路由信息，而不去了解其他子網(wǎng)的內(nèi)部結(jié)構(gòu)。n擁塞(congestion)：網(wǎng)絡(luò)中存在過多分組的時候，網(wǎng)絡(luò)性能降低，這種情況被稱為擁塞。圖例n造成擁塞的原因n多個輸入對應一個輸出，只增加內(nèi)存，并不能解決問題。n慢速處理器。n低帶寬線路。n針對某個因素的解決方案，只能對提高網(wǎng)絡(luò)性能起到一點點作用，甚至可能僅僅是轉(zhuǎn)移了影響性能的瓶頸。n擁塞控制(con

24、gestion control)與流量控制(flow control)n擁塞控制需要確保通信子網(wǎng)能夠承載用戶提交的通信量，是一個全局性問題，涉及主機、路由器等很多因素。n流量控制與點到點的通信量有關(guān)，主要解決快速發(fā)送方與慢速接收方的問題，是局部問題，一般都是基于反饋進行控制的。n根據(jù)控制論，擁塞控制可分為兩類。n開環(huán)控制(防患于未然)n通過良好的設(shè)計解決問題，以避免擁塞發(fā)生。一旦運行，就不再做中間階段的更正。n進行開環(huán)控制的工具需要決定何時接收新的分組、何時丟棄分組、丟棄哪些分組，制定網(wǎng)絡(luò)中不同地點的計劃表等。利用開環(huán)進行擁塞控制時，所有這些操作都不會考慮網(wǎng)絡(luò)的當前狀態(tài)。n閉環(huán)控制(因地制宜)

25、n基于反饋機制。其工作過程為： n監(jiān)控系統(tǒng)，發(fā)現(xiàn)何時何地發(fā)生擁塞。n把發(fā)生擁塞的消息傳給能采取動作的站點。n調(diào)整系統(tǒng)操作，解決擁塞問題。n閉環(huán)控制操作需要完成以下三個問題：何為擁塞、如何反饋和如何解決。n何為擁塞 衡量網(wǎng)絡(luò)擁塞的參數(shù)n缺乏緩沖區(qū)造成的丟包率n平均隊列長度n超時重傳的分組數(shù)目n平均分組延遲n分組延遲變化(Jitter)n如何反饋 反饋方法n向負載的發(fā)生源發(fā)送一個報警分組，這同時加強了擁塞。n在分組結(jié)構(gòu)中保留一個位或一個域來表示發(fā)生擁塞，一旦發(fā)生擁塞，路由器將所有輸出分組的擁塞位填充，報警。n主機或路由器主動地、周期性地發(fā)送探報(probe)，查詢是否發(fā)生擁塞。n如何解決 利用擁塞

26、控制算法n影響擁塞的網(wǎng)絡(luò)設(shè)計策略n數(shù)據(jù)鏈路層n重傳、亂序緩存、確認、流控n網(wǎng)絡(luò)層n子網(wǎng)中的虛電路和數(shù)據(jù)報、分組排隊和服務(wù)策略、分組丟棄策略、路由算法、分組的生存時間管理n傳輸層n重傳、亂序緩存、確認、流控、超時中止n通信量整形(Traffic Shaping)的基本思想n網(wǎng)絡(luò)上，突發(fā)的通信量是造成擁塞的主要原因。n強迫分組以某種可以預見的速率傳送，減少擁塞，這種方法就被稱為通信量整形。n此方法廣泛應用于ATM網(wǎng)絡(luò)中。n漏桶算法和令牌桶算法都可以實現(xiàn)通信量整形。n漏桶算法(The Leaky Bucket Algorithm)n基本原理：圖例。n在計算機中的使用n漏桶有限內(nèi)部隊列；水 通信量，需

27、要發(fā)送的分組n分組到達隊列時，隊列滿，分組被丟棄；隊列空，分組被放置在隊列尾。n效果n將用戶發(fā)出的不平滑的分組流轉(zhuǎn)變成網(wǎng)絡(luò)中平滑的分組流。n漏桶算法既可以用于分組長度固定的協(xié)議，如ATM，使用分組計數(shù)；也可用于可變長分組的協(xié)議，如IP，使用字節(jié)計數(shù)。無論水流進桶的速度為多少，只要桶中有水，水從桶中外漏的速度是恒定的。桶空了，速度為零。桶滿了，水外泄。n由于漏桶算法不夠靈活，因此加入令牌機制。n令牌桶算法 (The Token Bucket Algorithm) n基本思想：漏桶存放令牌，每T秒產(chǎn)生一個令牌，分組發(fā)送傳輸之前必須獲得一個令牌，傳輸之后刪除該令牌。計算最大速率突發(fā)時間的長度：令令牌

28、桶容量為C字節(jié)突發(fā)時間S秒令牌到達速率P字節(jié)/秒最大輸出速率M字節(jié)/秒則有：C+PS=MS S=C/(M-P) n通信量整形策略不同n漏桶算法不允許空閑主機積累發(fā)送權(quán)。n令牌桶算法允許空閑主機積累發(fā)送權(quán)，以便以后發(fā)送大的突發(fā)數(shù)據(jù)，最大為桶的大小。n桶中存放的內(nèi)容不同n漏桶中存放的是數(shù)據(jù)，桶滿了丟棄數(shù)據(jù)。n令牌桶中存放的是令牌，桶滿了丟棄令牌，不丟棄數(shù)據(jù)。n流說明(Flow Specification)n當發(fā)送方、接收方和子網(wǎng)都達成一致后，通信量整形才能發(fā)揮最佳效果。所以，一個數(shù)據(jù)流的發(fā)送方、接收方和通信子網(wǎng)三方認可的、描述發(fā)送數(shù)據(jù)流的模式和希望得到的服務(wù)質(zhì)量的數(shù)據(jù)結(jié)構(gòu)，被稱為流說明。n對發(fā)送方的流說明，子網(wǎng)和接收方可以做出三種答復：同意、拒絕、其它建議。n方法一 n許可控制(admission control)：一旦發(fā)生擁塞，就不允許再建立新的虛電路，直到擁塞解除為止。n方法二n在發(fā)生擁塞后可以建立新的虛電路，但要繞開發(fā)生擁塞的地區(qū)。n方法三n資源預留：建立虛電路時，主機與子網(wǎng)達成協(xié)議，子網(wǎng)根據(jù)協(xié)議在虛電路上為此連接預留資源。n抑制分組(Choke Packets)n路由器監(jiān)控輸出線路及其它資源的利用情況，超過某個閾值，則此資源進入警戒狀態(tài)。n每個新分組到來，檢查它的輸出線路是否處于警戒狀態(tài)。若是，向源主機發(fā)送抑制分