作業十二(筆記)

筆記:

作業十一(筆記)

第十四週計算機網路

作業1:說明Link state rooling algorigrithm出現的oscilation problem解決方法

利用Dijkstra algorithm來計算:
初始化:
     N' ={u}
　對於所有的節點v
　如果v是u的相鄰節點
　則 D(v) = c(u,v)
　否則 D(v) = 無限大

loop:
　尋找不屬於N'的w，使D(w)最小
　將w加入N'
　更新所有不屬於Ｎ’的相鄰節點ｖ的D(v)
　前往ｖ的新成本，會是前往ｖ的舊成本，或是已知前往ｗ的最小路徑加上從ｗ前往ｖ地成本
    直到N' = N

給定n個節點，最糟狀況的複雜度為O(n^2)

如果連結成本等於連結負載，可能會碰上震盪!
解決方法: 確保所有router不要同時執行LS演算法
=> 執行最後會同步!!
避免同步 => 每個router隨機選擇時間送出通告

作業2:說明Distance vector rooting alorigrithm出現的bad news travel slow解決方法

初始化:
　對所有屬於Ｎ的目的端ｙ：
　    如果ｙ不是相鄰節點，則ｃ（ｘ，ｙ）等於無限大
　對於每個相鄰節點ｗ
　　對所有屬於Ｎ的目的端ｙ，Ｄｗ（ｙ）等於無限大
　對於每個相鄰節點ｗ
　　送出距離向量Dx = [Dx(y): y屬於N] 給w

迴圈
　　等待：直到我看見某個相鄰節點ｗ的連結成本改變，或是直到我收到來自某個相鄰節點ｗ的距離向量
　　對於所有屬於Ｎ的ｙ：
　　Dx(y) = min{c(x, v) + Dv(y)}
　　如果有任何目的端ｙ的Dx(y)改變了
　　送出距離向量Dx = [Dx(y): y屬於N]給所有相鄰節點
        永遠執行下去

DV演算法是分散式的

網路直徑: 從一個node到另一個node的最長距離
DV需要至少(網路直徑)的時間才會收斂

因為每一網路節點不需掌握網路整體拓撲，因此在選徑時就有可能會有形成迴圈的現象
，甚至有可能會使得路徑的選擇產生無限計數（Count to infinity）的問題


解決無限計數的方法：
Maximum hop count：限制其跳躍數
Split horizon：這個方法的原則是不回送資料，所以當A-B之間斷了，C不會再把A的訊息告訴B，因為到A的訊息是由B告訴C的
Hold Down： 利用Hold down timer，若hold down timer過期前的任何時間裡，從不同的路由器接到更新資訊，但指標較差，則不理會更新資訊。在hold down timer時效範圍內，不理會指標較差的更新資訊，則能有更多時間將中斷的改變資訊傳播到整個網路上。


筆記: