三、路由算法

路由算法可以根據多個特性來加以區分。首先,算法設計者的特定目標影響了該路由協議的操作;其次,存在著多種路由算法,每種算法對網絡和路由器資源的影響都不同;最後,路由算法使用多種metric,影響到最佳路徑的計算。下面的章節分析了這些路由算法的特性。

1、設計目標

路由算法通常具有下列設計目標的一個或多個:優化簡單、低耗健壯、穩定快速聚合靈活性

優化指路由算法選擇最佳路徑的能力,根據metric的值和權值來計算。例如有一種路由算法可能使用跳數和延遲,但可能延遲的權值要大些。當然,路由協議必須嚴格定義計算metric的算法。

路由算法也可以設計得盡量簡單。換句話說,路由協議必須高效地提供其功能,盡量減少軟件和應用的開銷。當實現路由算法的軟件必須運行在物理資源有限的計算機上時高效尤其重要。

路由算法必須健壯,即在出現不正常或不可預見事件的情況下必須仍能正常處理,例如硬件故障、高負載和不正確的實現。因為路由器位於網絡的連接點,當它們失效時會產生重大的問題。最好的路由算法通常是那些經過了時間考驗,證實在各種網絡條件下都很穩定的算法。

此外,路由算法必須能快速聚合,聚合是所有路由器對最佳路徑達成一致的過程。當某網絡事件使路徑斷掉或不可用時,路由器通過網絡分發路由更新信息,促使最佳路徑的重新計算,最終使所有路由器達成一致。聚合很慢的路由算法可能會產生路由環或網路中斷。

路由算法還應該是靈活的,即它們應該迅速、準確地適應各種網絡環境。例如,假定某網段斷掉了,當知道問題後,很多路由算法對通常使用該網段的路徑將迅速選擇次佳的路徑。路由算法可以設計得可適應網絡帶寬、路由器隊列大小和網絡延遲。

2、算法類型

各路由算法的區別點包括:

靜態與動態
單路徑與多路徑
平坦與分層
主機智能與路由器智能
域內與域間
鏈接狀態與距離向量

(1)靜態與動態

靜態路由算法很難算得上是算法,只不過是開始路由前由網管建立的表映射。這些映射自身並不改變,除非網管去改動。使用靜態路由的算法較容易設計,在網絡通信可預測及簡單的網絡中工作得很好。

由於靜態路由系統不能對網絡改變做出反映,通常被認為不適用於現在的大型、易變的網絡。九十年代主要的路由算法都是動態路由算法,通過分析收到的路由更新信息來適應網絡環境的改變。如果信息表示網絡發生了變化,路由軟件就重新計算路由並發出新的路由更新信息。這些信息滲入網絡,促使路由器重新計算並對路由表做相應的改變。

動態路由算法可以在適當的地方以靜態路由作為補充。例如,最後可選路由(router of last resort),作為所有不可路由分組的去路,保證了所有的數據至少有方法處理。

(2)單路徑與多路徑

一些複雜的路由協議支持到同一目的的多條路徑。與單路徑算法不同,這些多路徑算法允許數據在多條線路上復用。多路徑算法的優點很明顯:它們可以提供更好的吞吐量和可靠性。

(3)平坦與分層

一些路由協議在平坦的空間裡運作,其它的則有路由的層次。在平坦的路由系統中,每個路由器與其它所有路由器是對等的;在分層次的路由系統中,一些路由器構成了路由主幹,數據從非主幹路由器流向主幹路由器,然後在主幹上傳輸直到它們到達目標所在區域,在這裡,它們從最後的主幹路由器通過一個或多個非主幹路由器到達終點。

路由系統通常設計有邏輯節點組,稱為域、自治系統或區間。在分層的系統中,一些路由器可以與其它域中的路由器通信,其它的則只能與域內的路由器通信。在很大的網絡中,可能還存在其它級別,最高級的路由器構成了路由主幹。

分層路由的主要優點是它模擬了多數公司的結構,從而能很好地支持其通信。多數的網絡通信發生在小組中(域)。因為域內路由器只需要知道本域內的其它路由器,它們的路由算法可以簡化,根據所使用的路由算法,路由更新的通信量可以相應地減少。

(4)主機智能與路由器智能

一些路由算法假定源結點來決定整個路徑,這通常稱為源路由。在源路由系統中,路由器只作為存貯轉發設備,無意識地把分組發向下一跳。其它路由算法假定主機對路徑一無所知,在這些算法中,路由器基於自己的計算決定通過網絡的路徑。前一種系統中,主機具有決定路由的智能,後者則為路由器具有此能力。

主機智能和路由器智能的折衷實際是最佳路由與額外開銷的平衡。主機智能係統通常能選擇更佳的路徑,因為它們在發送數據前探索了所有可能的路徑,然後基於特定係統對“優化”的定義來選擇最佳路徑。然而確定所有路徑的行為通常需要很多的探索通信量和很長的時間。

(5)域內與域間

一些路由算法只在域內工作,其它的則既在域內也在域間工作。這兩種算法的本質是不同的。其遵循的理由是優化的域內路由算法沒有必要也成為優化的域間路由算法。

(6)鏈接狀態與距離向量

鏈接狀態算法(也叫做短路徑優先算法)把路由信息散佈到網絡的每個節點,不過每個路由器只發送路由表中描述其自己鏈接狀態的部分。距離向量算法(也叫做Bellman-Ford算法)中每個路由器發送路由表的全部或部分,但只發給其鄰居。也就是說,鏈接狀態算法到處發送較少的更新信息,而距離向量算法只向相鄰的路由器發送較多的更新信息。

由於鏈接狀態算法聚合得較快,它們相對於距離算法產生路由環的傾向較小。在另一方面,鏈接狀態算法需要更多的CPU和內存資源,因此鏈接狀態算法的實現和支持較昂貴。雖然有差異,這兩種算法類型在多數環境中都可以工作得很好。

3、路由的metric

路由表中含有由交換軟件用以選擇最佳路徑的信息。但是路由表是怎樣建立的呢?它們包含信息的本質是什麼?路由算法怎樣根據這些信息決定哪條路徑更好呢?

路由算法使用了許多不同的metric以確定最佳路徑。複雜的路由算法可以基於多個metric選擇路由,並把它們結合成一個複合的metric。常用的metric如下:

路徑長度
可靠性
延遲
帶寬
負載
通信代價

路徑長度是最常用的路由metric。一些路由協議允許網管給每個網絡鏈接人工賦以代價值,這種情況下,路由長度是所經過各個鏈接的代價總和。其它路由協議定義了跳數,即分組在從源到目的的路途中必須經過的網絡產品,如路由器的個數。

可靠性,在路由算法中指網絡鏈接的可依賴性(通常以位誤率描述),有些網絡鏈接可能比其它的失效更多,網路失效後,一些網絡鏈接可能比其它的更易或更快修復。任何可靠性因素都可以在給可靠率賦值時計算在內,通常是由網管給網絡鏈接賦以metric值。

路由延遲指分組從源通過網絡到達目的所花時間。很多因素影響到延遲,包括中間的網絡鏈接的帶寬、經過的每個路由器的端口隊列、所有中間網絡鏈接的擁塞程度以及物理距離。因為延遲是多個重要變量的混合體,它是個比較常用且有效的metric。

帶寬指鏈接可用的流通容量。在其它所有條件都相等時,10Mbps的以太網鏈接比64kbps的專線更可取。雖然帶寬是鏈接可獲得的最大吞吐量,但是通過具有較大帶寬的鏈接做路由不一定比經過較慢鏈接路由更好。例如,如果一條快速鏈路很忙,分組到達目的所花時間可能要更長。

負載指網絡資源,如路由器的繁忙程度。負載可以用很多方面計算,包括CPU使用情況和每秒處理分組數。持續地監視這些參數本身也是很耗費資源的。

通信代價是另一種重要的metric,尤其是有一些公司可能關係運作費用甚於性能。即使線路延遲可能較長,他們也寧願通過自己的線路發送數據而不採用昂貴的公用線路。

四、網絡協議

可被路由的協議(Routed Protocol)由路由協議(Routing Protocol)傳輸,前者亦稱為網絡協議。

這些網絡協議執行在源與目的設備的用戶應用間通信所需的各種功能,不同的協議中這些功能可能差異很大。網絡協議發生在OSI參考模型的上四層:傳輸層、會話層、表示層和應用層。

術語routed protocol(可被路由的協議)和routing protocol(路由協議)經常被混淆。 routed protocol在網絡中被路由,例如IP、DECnet、AppleTalk、Novell NetWare、OSI、Banyan VINES和Xerox Network System(XNS)。而路由協議是實現路由算法的協議,簡單地說,它給網絡協議做導向。路由協議如:IGRP、EIGRP、OSPF、EGP、 BGP、IS-IS及RIP等。

創作者介紹

IT資訊-實驗室[MIS LAB ]

bubble727 發表在 痞客邦 PIXNET 留言(0) 人氣()