3.4.2路由選擇
通信子網為網絡源節(jié)點和目的節(jié)點提供了多條傳輸路徑的可能性。網絡節(jié)點在收到一個分組后,要確定向下一節(jié)點傳送的路徑,這就是路由選擇。在數據報方式中,網絡節(jié)點要為每個分組路由做出選擇;而在虛電路方式中,只需在連接建立時確定路由。確定路由選擇的策略稱路由算法。設計路由算法時要考慮諸多技術要素。首先,考慮是選擇最短路由還是選擇路由;其次,要考慮通信子網是采用虛電路的還是采用數據報的操作方式;其三,是采用分布式路由算法,即每節(jié)點均為到達的分組選擇下一步的路由,還是采用集中式路由算法,即由中央節(jié)點或始發(fā)節(jié)點來決定整個路由;其四,要考慮關于網絡拓撲、流量和延遲等網絡信息的來源;最后,確定是采用靜態(tài)路由選擇策略,還是動態(tài)路由選擇策略。
1.靜態(tài)路由選擇策略
靜態(tài)路由選擇策略不用測量也不需利用網絡信息,這種策略按某種固定規(guī)則進行路由選擇,其中還可分為泛射路由選擇、固定路由選擇和隨機路由選擇三種算法。
(1)泛射路由選擇法。這是一種最簡單的路由算法。一個網絡節(jié)點從某條線路收到一個分組后,再向除該條線路外的所有線路重復發(fā)送收到的分組。結果,最先到達目的節(jié)點的一個或若干個分組肯定經過了最短的路徑,而且所有可能的路徑都被嘗試過。這種方法可用于諸如軍事網絡等強壯性要求很高的場合。即使有的網絡節(jié)點遭到破壞,只要源、目間有一條信道存在,則泛射路由選擇法仍能保證數據的可靠傳送。另外,這種方法也可用于將一個分組從數據源傳送到所有其它節(jié)點的廣播式數據交換中。它還可被用來進行網絡的最短路徑及最短傳輸延遲的測試。
(2)固定路由選擇。這是一種使用較多的簡單算法。每個網絡節(jié)點存儲一張表格,表格中每一項記錄著對應某個目的節(jié)點的下一節(jié)點或鏈路。當一個分組到達某節(jié)點時,該節(jié)點只要根據分組上的地址信息,便可從固定的路由表中查出對應的目的節(jié)點及所應選擇的下一節(jié)點。一般,網絡中都有一個網絡控制中心,由它按照路由算法求出每對源、目節(jié)點間的路由,然后為每一節(jié)點構造一個固定路由表并分發(fā)給各節(jié)點。固定路由選擇法的優(yōu)點是簡便易行,在負載穩(wěn)定,拓撲結構變化不大的網絡中運行效果很好。它的缺點是靈活性差,無法應付網絡中發(fā)生的阻塞和故障。
(3)隨機路由選擇。在這種方法中,收到分組的節(jié)點,在所有與之相鄰的節(jié)點中為分組隨機選擇一個出路節(jié)點。方法雖然簡單,但實際路由不是路由,這會增加不必要的負擔,而且分組傳輸延遲也不可預測,故此法應用不廣。
2.動態(tài)路由選擇策略
節(jié)點的路由選擇要依靠網絡當前的狀態(tài)信息來決定的策略,稱動態(tài)路由選擇策略。這種策略能較好地適應網絡流量、拓撲結構的變化,有利于改善網絡的性能。但由于算法復雜,會增加網絡的負擔。獨立路由選擇、集中路由選擇和分布路由選擇是三種動態(tài)路由選擇策略的具體算法。
(1)獨立路由選擇。在這類路由算法中,節(jié)點僅根據自己搜集到的有關信息做出路由選擇的決定,與其它節(jié)點不交換路由選擇信息。這種算法雖然不能正確確定距離本節(jié)點較遠的路由選擇,但還是能較好地適應網絡流量和拓撲結構的變化。一種簡單的獨立路由選擇算法是Barm在1964年提出的熱土豆(Hot Potato)算法:當一個分組到來時,節(jié)點必須盡快脫手,將其放入輸出隊列最短的方向上排隊,而不管該方向通向何方。
(2)集中路由選擇。集中路由選擇也像固定路由選擇一樣,在每個節(jié)點上存儲一張路由表。不同的是,固定路由選擇算法中的節(jié)點路由表由人工制作,而在集中路由選擇算法中的節(jié)點路由表由路由控制中心RCC(Routing Control Center)定時根據網絡狀態(tài)計算、生成并分送各相應節(jié)點。由于RCC利用了整個網絡的信息,所以得到的路由選擇是完美的,同時也減輕了各節(jié)點計算路由選擇的負擔。
(3)分布路由選擇。在采用分布路由選擇算法的網絡中,所有節(jié)點定期地與其每個相鄰
節(jié)點交換路由選擇信息。每個節(jié)點均存儲一張以網絡中其它節(jié)點為索引的路由選擇表,網絡中每個節(jié)點占用表中一項。每一項又分為兩個部分,一部分是所希望使用的到目的節(jié)點的輸出線,另一部分是估計到目的節(jié)點所需要的延遲或距離。度量標準可以是毫秒或鏈路段數、等待的分組數、剩余的線路和容量等
通信子網為網絡源節(jié)點和目的節(jié)點提供了多條傳輸路徑的可能性。網絡節(jié)點在收到一個分組后,要確定向下一節(jié)點傳送的路徑,這就是路由選擇。在數據報方式中,網絡節(jié)點要為每個分組路由做出選擇;而在虛電路方式中,只需在連接建立時確定路由。確定路由選擇的策略稱路由算法。設計路由算法時要考慮諸多技術要素。首先,考慮是選擇最短路由還是選擇路由;其次,要考慮通信子網是采用虛電路的還是采用數據報的操作方式;其三,是采用分布式路由算法,即每節(jié)點均為到達的分組選擇下一步的路由,還是采用集中式路由算法,即由中央節(jié)點或始發(fā)節(jié)點來決定整個路由;其四,要考慮關于網絡拓撲、流量和延遲等網絡信息的來源;最后,確定是采用靜態(tài)路由選擇策略,還是動態(tài)路由選擇策略。
1.靜態(tài)路由選擇策略
靜態(tài)路由選擇策略不用測量也不需利用網絡信息,這種策略按某種固定規(guī)則進行路由選擇,其中還可分為泛射路由選擇、固定路由選擇和隨機路由選擇三種算法。
(1)泛射路由選擇法。這是一種最簡單的路由算法。一個網絡節(jié)點從某條線路收到一個分組后,再向除該條線路外的所有線路重復發(fā)送收到的分組。結果,最先到達目的節(jié)點的一個或若干個分組肯定經過了最短的路徑,而且所有可能的路徑都被嘗試過。這種方法可用于諸如軍事網絡等強壯性要求很高的場合。即使有的網絡節(jié)點遭到破壞,只要源、目間有一條信道存在,則泛射路由選擇法仍能保證數據的可靠傳送。另外,這種方法也可用于將一個分組從數據源傳送到所有其它節(jié)點的廣播式數據交換中。它還可被用來進行網絡的最短路徑及最短傳輸延遲的測試。
(2)固定路由選擇。這是一種使用較多的簡單算法。每個網絡節(jié)點存儲一張表格,表格中每一項記錄著對應某個目的節(jié)點的下一節(jié)點或鏈路。當一個分組到達某節(jié)點時,該節(jié)點只要根據分組上的地址信息,便可從固定的路由表中查出對應的目的節(jié)點及所應選擇的下一節(jié)點。一般,網絡中都有一個網絡控制中心,由它按照路由算法求出每對源、目節(jié)點間的路由,然后為每一節(jié)點構造一個固定路由表并分發(fā)給各節(jié)點。固定路由選擇法的優(yōu)點是簡便易行,在負載穩(wěn)定,拓撲結構變化不大的網絡中運行效果很好。它的缺點是靈活性差,無法應付網絡中發(fā)生的阻塞和故障。
(3)隨機路由選擇。在這種方法中,收到分組的節(jié)點,在所有與之相鄰的節(jié)點中為分組隨機選擇一個出路節(jié)點。方法雖然簡單,但實際路由不是路由,這會增加不必要的負擔,而且分組傳輸延遲也不可預測,故此法應用不廣。
2.動態(tài)路由選擇策略
節(jié)點的路由選擇要依靠網絡當前的狀態(tài)信息來決定的策略,稱動態(tài)路由選擇策略。這種策略能較好地適應網絡流量、拓撲結構的變化,有利于改善網絡的性能。但由于算法復雜,會增加網絡的負擔。獨立路由選擇、集中路由選擇和分布路由選擇是三種動態(tài)路由選擇策略的具體算法。
(1)獨立路由選擇。在這類路由算法中,節(jié)點僅根據自己搜集到的有關信息做出路由選擇的決定,與其它節(jié)點不交換路由選擇信息。這種算法雖然不能正確確定距離本節(jié)點較遠的路由選擇,但還是能較好地適應網絡流量和拓撲結構的變化。一種簡單的獨立路由選擇算法是Barm在1964年提出的熱土豆(Hot Potato)算法:當一個分組到來時,節(jié)點必須盡快脫手,將其放入輸出隊列最短的方向上排隊,而不管該方向通向何方。
(2)集中路由選擇。集中路由選擇也像固定路由選擇一樣,在每個節(jié)點上存儲一張路由表。不同的是,固定路由選擇算法中的節(jié)點路由表由人工制作,而在集中路由選擇算法中的節(jié)點路由表由路由控制中心RCC(Routing Control Center)定時根據網絡狀態(tài)計算、生成并分送各相應節(jié)點。由于RCC利用了整個網絡的信息,所以得到的路由選擇是完美的,同時也減輕了各節(jié)點計算路由選擇的負擔。
(3)分布路由選擇。在采用分布路由選擇算法的網絡中,所有節(jié)點定期地與其每個相鄰
節(jié)點交換路由選擇信息。每個節(jié)點均存儲一張以網絡中其它節(jié)點為索引的路由選擇表,網絡中每個節(jié)點占用表中一項。每一項又分為兩個部分,一部分是所希望使用的到目的節(jié)點的輸出線,另一部分是估計到目的節(jié)點所需要的延遲或距離。度量標準可以是毫秒或鏈路段數、等待的分組數、剩余的線路和容量等