計算機網(wǎng)絡(luò)體系結(jié)構(gòu)之路由選擇

通信子網(wǎng)為網(wǎng)絡(luò)源節(jié)點和目的節(jié)點提供了多條傳輸路徑的可能性。網(wǎng)絡(luò)節(jié)點在收到一個分組后，要確定向下一節(jié)點傳送的路徑，這就是路由選擇。在數(shù)據(jù)報方式中，網(wǎng)絡(luò)節(jié)點要為每個分組路由做出選擇；而在虛電路方式中，只需在連接建立時確定路由。確定路由選擇的策略稱路由算法。設(shè)計路由算法時要考慮諸多技術(shù)要素。首先，考慮是選擇最短路由還是選擇最佳路由；其次，要考慮通信子網(wǎng)是采用虛電路的還是采用數(shù)據(jù)報的操作方式；其三，是采用分布式路由算法，即每節(jié)點均為到達(dá)的分組選擇下一步的路由，還是采用集中式路由算法，即由中央節(jié)點或始發(fā)節(jié)點來決定整個路由；其四，要考慮關(guān)于網(wǎng)絡(luò)拓?fù)?、流量和延遲等網(wǎng)絡(luò)信息的來源；最后，確定是采用靜態(tài)路由選擇策略，還是動態(tài)路由選擇策略。

1.靜態(tài)路由選擇策略

靜態(tài)路由選擇策略不用測量也不需利用網(wǎng)絡(luò)信息，這種策略按某種固定規(guī)則進(jìn)行路由選擇，其中還可分為泛射路由選擇、固定路由選擇和隨機路由選擇三種算法。

（1）泛射路由選擇法。這是一種最簡單的路由算法。一個網(wǎng)絡(luò)節(jié)點從某條線路收到一個分組后，再向除該條線路外的所有線路重復(fù)發(fā)送收到的分組。結(jié)果，最先到達(dá)目的節(jié)點的一個或若干個分組肯定經(jīng)過了最短的路徑，而且所有可能的路徑都被嘗試過。這種方法可用于諸如軍事網(wǎng)絡(luò)等強壯性要求很高的場合。即使有的網(wǎng)絡(luò)節(jié)點遭到破壞，只要源、目間有一條信道存在，則泛射路由選擇法仍能保證數(shù)據(jù)的可靠傳送。另外，這種方法也可用于將一個分組從數(shù)據(jù)源傳送到所有其它節(jié)點的廣播式數(shù)據(jù)交換中。它還可被用來進(jìn)行網(wǎng)絡(luò)的最短路徑及最短傳輸延遲的測試。

（2）固定路由選擇。這是一種使用較多的簡單算法。每個網(wǎng)絡(luò)節(jié)點存儲一張表格，表格中每一項記錄著對應(yīng)某個目的節(jié)點的下一節(jié)點或鏈路。當(dāng)一個分組到達(dá)某節(jié)點時，該節(jié)點只要根據(jù)分組上的地址信息，便可從固定的路由表中查出對應(yīng)的目的節(jié)點及所應(yīng)選擇的下一節(jié)點。一般，網(wǎng)絡(luò)中都有一個網(wǎng)絡(luò)控制中心，由它按照最佳路由算法求出每對源、目節(jié)點間的最佳路由，然后為每一節(jié)點構(gòu)造一個固定路由表并分發(fā)給各節(jié)點。固定路由選擇法的優(yōu)點是簡便易行，在負(fù)載穩(wěn)定，拓?fù)浣Y(jié)構(gòu)變化不大的網(wǎng)絡(luò)中運行效果很好。它的缺點是靈活性差，無法應(yīng)付網(wǎng)絡(luò)中發(fā)生的阻塞和故障。

（3）隨機路由選擇。在這種方法中，收到分組的節(jié)點，在所有與之相鄰的節(jié)點中為分組隨機選擇一個出路節(jié)點。方法雖然簡單，但實際路由不是最佳路由，這會增加不必要的負(fù)擔(dān)，而且分組傳輸延遲也不可預(yù)測，故此法應(yīng)用不廣。

2.動態(tài)路由選擇策略

節(jié)點的路由選擇要依靠網(wǎng)絡(luò)當(dāng)前的狀態(tài)信息來決定的策略，稱動態(tài)路由選擇策略。這種策略能較好地適應(yīng)網(wǎng)絡(luò)流量、拓?fù)浣Y(jié)構(gòu)的變化，有利于改善網(wǎng)絡(luò)的性能。但由于算法復(fù)雜，會增加網(wǎng)絡(luò)的負(fù)擔(dān)。獨立路由選擇、集中路由選擇和分布路由選擇是三種動態(tài)路由選擇策略的具體算法。

（1）獨立路由選擇。在這類路由算法中，節(jié)點僅根據(jù)自己搜集到的有關(guān)信息做出路由選擇的決定，與其它節(jié)點不交換路由選擇信息。這種算法雖然不能正確確定距離本節(jié)點較遠(yuǎn)的路由選擇，但還是能較好地適應(yīng)網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)的變化。一種簡單的獨立路由選擇算法是Barm在1964年提出的熱土豆（Hot Potato）算法：當(dāng)一個分組到來時，節(jié)點必須盡快脫手，將其放入輸出隊列最短的方向上排隊，而不管該方向通向何方。

（2）集中路由選擇。集中路由選擇也像固定路由選擇一樣，在每個節(jié)點上存儲一張路由表。不同的是，固定路由選擇算法中的節(jié)點路由表由人工制作，而在集中路由選擇算法中的節(jié)點路由表由路由控制中心RCC（Routing Control Center）定時根據(jù)網(wǎng)絡(luò)狀態(tài)計算、生成并分送各相應(yīng)節(jié)點。由于RCC利用了整個網(wǎng)絡(luò)的信息，所以得到的路由選擇是完美的，同時也減輕了各節(jié)點計算路由選擇的負(fù)擔(dān)。

（3）分布路由選擇。在采用分布路由選擇算法的網(wǎng)絡(luò)中，所有節(jié)點定期地與其每個相鄰

節(jié)點交換路由選擇信息。每個節(jié)點均存儲一張以網(wǎng)絡(luò)中其它節(jié)點為索引的路由選擇表，網(wǎng)絡(luò)中每個節(jié)點占用表中一項。每一項又分為兩個部分，一部分是所希望使用的到目的節(jié)點的輸出線，另一部分是估計到目的節(jié)點所需要的延遲或距離。度量標(biāo)準(zhǔn)可以是毫秒或鏈路段數(shù)、等待的分組數(shù)、剩余的線路和容量等。