通信工程師交換技術無窮計算問題

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

　?、贌o窮計算問題
距離向量路由算法在理論上是能有效工作的，但在實際運用中卻有很大的缺陷。雖然它最終能得出正確的答案，但有可能太慢。特別是，它對好消息的反應迅速，但對壞消息卻反應遲鈍?？紤]有一個節(jié)點，它到目的點尤的最佳路由很長，如果在某次交換信息時，它的鄰居A突然報告說有一個到X更短的路徑，即可以使該節(jié)點到X的距離更短，那么該節(jié)點僅需簡單地將后繼節(jié)點改為A,也就是使用它到A的鏈路來傳送到的分組流?？梢?，好消息經(jīng)過一次向量交換就處理完畢了。如圖5-22所示的一個5節(jié)點（線性）子網(wǎng)，距離采用跳數(shù)度量，即每條鏈路的距離為1。假設節(jié)點A剛開始不在子網(wǎng)上，而且所有其他節(jié)點也知道這一點。也就是說，它們將到A的距離都記為無窮大。當A連接到網(wǎng)絡工作后，其他節(jié)點通過向量交換都知道它上網(wǎng)了。為了簡單起見，假設有一個時鐘周期地令所有節(jié)點同時啟動向量交換。在第一次交換路由信息后，B就在路由表中記上到A的距離是1。其他節(jié)點還認為A沒有上網(wǎng)。這時候各節(jié)點的路由表中關于節(jié)點A的表項如圖5-22(a)中的第二行所示。在第二次交換后，C知道B有一條到A和長度為1的路徑，因此它就更新其路由表，記上一條長度為2的到A的路徑，但D和E到現(xiàn)在還不知道這一消息。很明顯，好消息的傳播是每交換一次路由信息就前進一個節(jié)點。在一個最長路徑為N跳的子網(wǎng)中，最多經(jīng)過W次路由信息的交換，所有節(jié)點都會知道新增的鏈路和節(jié)點。
現(xiàn)在討論一下壞消息的傳播速度。如圖5-22(b)所示，開始時，所有的鏈路和節(jié)點都在網(wǎng)上。節(jié)點B，C,D和E到A的距離分別是1，2,3和4。假定A突然下網(wǎng)了，或者A與B之間的線路斷開了，這對于B來說都一樣。在第一次交換路由信息時，B沒有從A處得到任何信息，但C說：“我有一條到A的長度為2的路徑?！盉并不知道C到A的路徑還要經(jīng)過B本身。B認為C可能有多條獨立的長度為2的路徑通往A。結果，B認為它能通過C到達A,路徑長度為3。第一次交換后，D和E并不更新其對應于A的表項。第二次交換路由信息時，C注意到它所有的鄰居都聲稱有一條通往A的長度為3的路徑。它隨意選擇任意一個鄰居，并將到A的距離設為4,如圖5-22(b)中第三行所示。后續(xù)的交換過程如圖22(b)中所示。通過這張圖可以看出，壞消息傳播的很慢。只有當所有節(jié)點慢慢地增加其距離值，直至無窮大時，才發(fā)現(xiàn)網(wǎng)絡拓撲發(fā)生了變化。這就是所謂的“無窮計算問題”。在實際的系統(tǒng)中可以將無窮大的取值設置成最長路徑加1。但是，如果采用時延作為距離的度量值時，就很難定義一個合適的距離上限。

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

編輯推薦：

通信專業(yè)實務考試終端與業(yè)務教程匯總

通信專業(yè)實務考試設備與環(huán)境教程匯總

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