目錄式路由選擇

目錄式路由選擇是報文或包的一種路由選擇方法，其通信網路中的每個節點均有一個到達各目的地的最佳、次佳路由的通信錄以供選擇。

基本介紹

• 中文名：目錄式路由選擇
• 外文名：directory routing
• 拼音：mù lù shì lù yóu xuǎn zé
• 定義：報文或包的一種路由選擇方法
• 相關名詞：目錄式路由選擇算法
• 套用學科：網路和接口

概述

網路層概念是建立在網際網路基礎上的。網際網路是各種通信子網通過網路層互連設備(如路由器)和協定相互連線。形成一個很大的邏輯網路，實現端到端的數據通信，網際網路模型如右圖所示。

在網際網路模型中，端節點主要完成數據的分組和組裝．中間節點則基於存儲一轉發技術，負責選擇適當的路由來轉發這些數據分組；對於面向連線的傳輸方式，中間節點只是在建立連線時選擇一次路由，以後每個數據分組都沿著該路由進行傳輸；對於無連線的傳輸方式，中間節點要為每個數據分組選擇路由，每個數據分組的傳輸路徑可能是不同的。

因此，路由選擇是中間節點網路層的重要功能之一。中間節點在選擇路由時主要基於如下原理：每箇中間節點都採用適當的路由選擇算法支持路由選擇。並維持一·個路由表來記錄有關路由信息。如端節點地址與線路(或連線埠)對應關係、路由開銷等。在轉發數據分組時，路由器將根據數據分組的目的地址查找路由表獲取有關路由信息，並採用某種路由選擇算法計算最佳路由，然後按該路由轉發數據分組。

在現在的大多數分組交換網路中，比較廣泛地採用目錄式路由選擇技術，目錄式路由選擇是報文或包的一種路由選擇方法，其通信網路中的每個節點均有一個到達各目的地的最佳、次佳路由的通信錄以供選擇。

目錄有時又稱為路由表，其中包含交換機為每個分組進行路由選擇的指示。根據目錄的組織方式不同，可以有固定(靜態)式目錄、集中自適應目錄和分散自適應目錄三種

目錄式路由選擇的質量關鍵在於目錄式路由選擇算法，目錄式路由算法是—種採用較多的簡單算法，也稱為固定式算法。

目錄分類

固定(靜態)式目錄

在採用固定式目錄路由選擇時，在網路內的每個節點交換機內都保存有一個從此節點到其它節點的路由表，表中可規定一條或多條出線。該表由網路設計者根據網路拓撲或其他因素人工編制，在網路投入運行之前就存入節點交換機的存儲器內，網路在運行中此表始終不變。右圖給出了一個例子，（a）為網路結構示意圖，（b）為節點 交換機內的路由選擇表，在表中列出了從節點 到網路內其它所有節點的三條出線。如從 到 的三條出線分別為 、 和 ，當節點 交換機收到去目的地 的分組時，先產生一個從0.00到0.99之間的隨機數，當隨機數在0.00—0.50之間時，選擇去H的出線；當隨機數在0.50—0.75之間時，選擇去 的出線；當隨機數在0.75以上時，選擇去 的出線。從上看出，它把H出線認為是最佳選擇， 出線為次最佳選擇， 出線為最差選擇。

固定目錄路由選擇方法的最大優點是算法簡單、易於實現，在網路拓撲結構和信息分布均勻的情況下，能給出較好的性能。其缺點是缺乏靈活性，不能隨網路的狀態變化(如擁塞、故障等)而動態變更路徑。

集中自適應目錄

同上述的固定式目錄一樣，在網路中的每個節點交換機都有一個路由選擇表，但產生這路由選擇表的方法則不同。在採用集中自適應式的網路內，由網路控制中心(NCC)決定各節點交換機內的路由表，並定時予以更新。具體方法是，由NCC收集各節點定期送來的狀態信息，然後根據這些狀態信息及網路拓撲結構，動態地計算出每個節點現時的路由表，再把新的路由表送回各節點交換機使用。所以，在每個交換機內都保存一張當前的狀態信息表，內含線上的相鄰節點、各輸出線待轉發分組的排隊長度、近期處理過的信息量等。

採用這種路由選擇方法的優點是適應性好，能定期地按拓撲結構和信息量的變化修改各節點的路由表。但也存在不少缺點：

(1)對NCC的可靠性要求很高，要求對NCC提供備用；

(2)要求NCC有很強的計算能力，以適應網路內信息量的快速變化；

(3)NCC每隔一定的時間都要把路由表送向各節點交換機，由於各節點離NCC的距離不同，遠離NCC的節點交換機要比靠近NCC的節點交換機晚收到新的路由表，如果不採取適蘭措施，則可能離近的節點已按新的路由表選擇路由，而遠離NCC節點，由於未收到新路由長而仍按老的路由表選擇路由。這種失調會增大分組的傳輸時延；

(4)NCC向各節點傳送路由表和各節點向NCC報告狀態信息，使網路的負荷增加，而且離NCC越近，這種額外負荷越重。

分散自適應目錄

分散自適應是另一類自適應路由選擇方法，它不依靠NCC來獲得一條分組傳輸的最佳路徑，而是由網路內的各個節點交換機依據當前的狀態、信息量的分布等計算出各自的路由表。下面介紹其中的兩種方法。 ·

（一）孤立法

它是分散式路由計算方法中最為簡單的一種。各節點交換機在決定路由時不與其他節點交換機交換信息，故把它稱為孤立法。

在最早提出孤立法時，其設計的中心思想是使到達節點的分組儘快地離開本節點，故接收分組的交換機在其所有的出線中，尋找一條排隊最短的出線把陔分組傳送出去。從表面上看，這種方法使分組在每個節點內的停留時間最短，但由於不管分組目的地的盲目傳送，使分組總的傳輸時延較大。所以，在實際套用中往往與固定目錄方式相結合使用，一般有三種結合的方法。 ·

(1)根據分組查找固定路由表，從固定路由表的最佳路由選擇開始，檢查對應出線的排隊長度，只要長度未超過規定值，就把分組從該出線中輸出；否則依次往後尋找次佳路由選擇。重複上述工作；

(2)找出排隊最短的出線，然後根據分組查找固定路由表，觀察對應出線的利用率是否達到規定值，如達到規定值就選用該出線，否則繼續尋找排隊長度第二、第三最短的出線，重複上述工作；

(3)把固定路由表中的出線按其利用率進行1、2、3…的編號，然後把出線按其隊長進行1、2、3…的編號，最後取一條在兩個排列中編號之和為最小的出線。

對於上述三種改進型孤立法，不管使用哪一種，都應使輸出線的選擇滿足下述條件，即在輕負載時，一般出線的佇列較短，應選用利用率最高的出線(即最佳選擇對應的輸出線)；而在重負載下，應選用佇列最短的輸出線，以均勻網路的負載。

注意，對同一網路的同一節點來說，把分組傳送到同一目的節點，採用集中式路由選擇得到的路徑和採用上述改進型孤立法得到的路徑不一定相同，因為前者是由NCC根據整個網路的全部情況所得出的最佳路由，而後者則僅僅考慮了本節點的情況。但是，這並不意味著前者效果一定優於後者。因為集中式路由選擇情況下，路由表是依據一段時間之前的網路狀態得出的，網路中的各節點根據路由表得到的路徑對於那時來說是最佳的，在經過一段時間(其中包括NCC收集節點狀態表的時間、路由表計算時間和各節點傳送時間等)後，網路狀態已發生了變化，這時得出的路徑也不一定是最佳的了。所以，在實踐中有時把集中式路由選擇與孤立法結合起來使用，獲得較好的效果。

（二）分散式自適應法

分散式自適應法是一種適應較好並旦得到廣泛套用的路由選擇方法。在採用這種方法時，網路中的每個節點交換機周期性地與其相鄰的節點交換機之間交換路由選擇信息，然後根據這些信息來修改自己的路由表。雖然在每次修改中僅反映了相應節點的情況，但經過幾次修改後，即可反映出第n次相鄰節點的變化情況。所以，分散式自適應路由選擇算法可以適應整個網路的變化。不過，它對近處節點的情況反應快，而對遠處節點反應慢。

在不同網路中，採用這種算法時的設計準則不同，路由表的構成和交換機之間傳遞的狀態參數也不同，常用的參數可以是時延、傳輸距離、中繼段數目或者至目的節點的排隊總長度等，下面以時延作為參數來進行說明。這時，網路中的各節點可以通過向相鄰節點傳送—-個所謂“回波”分組來測試至相鄰節點的傳輸時延，被測節點交換飢在收到“回波”分組後，收到的時間標誌後馬上回送到傳送節點。因此網路內的各節點可以知道至相鄰節點的分組傳遞時間。然後，網路中的每一個節點交換機相隔周期T向相鄰節點交換機傳送-—張至其餘目的節點的時延估計表，同時各節點交換機也收到來自各相鄰節點的類似的表格。這樣，各節點根據收到的時延占計表和由“回波”分組測得的至相鄰節點的分組傳輸時延，可以計算出最短時延路由，得到一張新的路由表。

目錄式路由選擇算法

這是—種採用較多的簡單算法，也稱為固定式算法。在此算法中，各節點要事先建立一張路由選擇表或路由選擇資料庫，建表或建庫的原則是依據鏈路代價函式，各節點可依據此表進行路由選擇。路由表一般可提供幾種可能的選擇。在該策略中，發信站在傳送一個報文分組之前，先要產生一個隨機數，待尋徑節點根據其路由表和此隨機數作出路由選擇。其選擇的依據基本上是以算法分析中的最最佳化原理為基礎。這種方法簡便，易於實現，當網路拓撲和信息量較穩定時，它能呈現較好的性能，且能較好地利用給定路由的信道頻寬；其缺點是對節點或鏈路故障缺乏堅定性和自適應性。