在線輔導　面授招生　考試大綱　指定教材　報名時間

　　1.路由選擇算法
(1)用圖表示網絡
路由問題就是解決分組交換網中的各節點交換機應該如何進行分組轉發的問題.因此有必要先研究網絡的拓撲結構。可以用圖論中的“圖”（Graph)來表示一個分組交換網絡，用圖的“頂點”表示網絡節點，用連接頂點的“邊”表示網絡節點間的鏈路，如一個網絡圖G表示為G=(V,E),其中，F是網絡節點的集合，E是鏈路的集合。
通過網絡的一條有向通路（Path),可用一組鏈路的有序集（L1,L2,……，Ln）來表示。在分組交換網絡中，該通路稱為“分組傳送路徑”（Route)。因此，所謂“路由算法”或“路徑選擇算法”，就是指確定分組從它的源點到達目的點的有向傳輸通路的法則。

現在面臨的問題是：
①采用什么算法來選擇合適的路徑？
②依據什么信息來進行這種選擇？
③應該如何執行這種選擇的策略？
④用什么標準來評判所選擇路徑的好壞？
下面就討論路由選擇的一般原理以及幾種
不同的路由選擇策略和算法。
理想的路由選擇算法圖5-16網絡

一個理想的路由選擇算法應滿足如下要求。
①算法必須是正確的和完整的。每一個節點交換機中的路由表，都必須給出到所有可能的目的節點的下一節點，并且沿著各交換機中路由表所指引的路由，分組一定能夠最終到達目的計算機所在的那個節點交換機，并且該交換機可以根據自己的路由表識別出目的計算機直接與自己相連，因此不會再向其他交換機轉發該分組。
②算法在計算上應盡可能簡單。對于數據報分組交換方式，在每個節點上都要對每個分組進行路由選擇的計算，路由的計算必然增加分組的轉發處理時延，因此應簡化計箅。另外，路由選擇的計算不應使網絡通信資源增加太多的額外開銷。若為了計算合適的路由必須使用網絡其他節點發來的大量狀態信息，就會加大額外開銷。
③算法應能適應分組流量和網絡拓撲的變化，也就是說，要有自適應性。當網絡中某些鏈路的流量過大時，算法應能自適應地改變路由，以均衡各鏈路的負載。當某個或某些節點、鏈路發生故障不能工作，或者修理好了再投人運行時，算法能及時地改變路由。有時稱這種自適應性為“頑健性”（Robustness)。
④箅法應具有穩定性。在網絡通信流童和網絡拓撲相對穩定的情況下，路由算法應收斂于一個可以接受的解，而不應產生過多的振蕩。所謂振蕩，是指由算法得出的路由在一些路由之間來回不停地變化。
⑤算法應是公平的。這就是說，算法應對所有用戶（除對少數優先級髙的用戶）都是平等的。例如，若使某一對用戶的端到端時延為最小，但卻不考慮其他的廣大用戶，這就明顯地不符合公平性的要求。
⑥算法應是最佳的。這里的“最佳”是指以最低的“代價"（Cost)來實現的路由算法。這里特別需要注意的是，在研究路由選擇時，“代價”并#一定指“錢”。通常是給每一條鏈路指定一定的代價，而這個代價又是由一個或多個因素（幾個因素綜合起來）決定的，如鏈路長度、數據率、鏈路容量、是否要保密、傳輸時延等，甚至還可以是一天中某一個小時內的通信流量、節點緩沖區被占用的程度、鏈路的差錯率情況等。可以根據用戶的具體情況來設置每一條鏈路的“代價”。從這里坷以看出，不存在一種絕對的最佳路由算法。所謂“最佳”只能是相對于某一種特定要求下得出的較為合理的選擇而已。
一個實際的路由選擇算法，應盡可能接近理想的算法。在不同的應用條件下，對以上提出的六個方面也可有不同的側重。
2.路由策略的分類
路由選擇算沬是解決如何根據網絡拓撲和狀態，按照一定的性能準則，計算分組傳送路徑的問題。而路由策略則是解決路由的選擇能否適應網絡拓撲和狀態變化的問題。這兩者不可混淆。一般說來，路由選擇算法僅是路由策略的一部分。倘若從路由的選擇能否隨網絡的變化而自適應地進行調整變化來區分，則路由策略可分為兩大類，即非自適應路由選擇策略與自適應路由選擇策略。
非自適應路由選擇也叫做靜態路由選擇，其特點是簡單和開銷較小，但不能及時適應網絡狀態（包括網絡拓撲和流量分布）的變化。自適應路由選擇也叫做動態路由選擇，其特點是能較好地適應網絡狀態的變化，但實現起來較為復雜。下面兩小節將分別進行介紹。

返回目錄： 通信專業交換技術考試培訓分組交換匯總

編輯推薦：

通信專業實務考試終端與業務教程匯總

通信專業實務考試設備與環境教程匯總

通信工程師考試培訓交換理論基確匯總