Ⅰ 路由演算法
路由演算法是網路層軟體的一部分。子網提供數據報服務，每個包都要做路由選擇；子網提供虛電路服務，只需在建立連接時做一次路由選擇
正確性，簡單性，健壯性（魯棒性，網路出現意外情況時候的解決問題的能力。例如突然某個路由器停電了，使得周邊的路由器都沒法正常工作，如果出現這樣的問題說明路由器的健壯性不夠），穩定性（常規使用是否穩定，數據量增多的時候能否正常工作），公平性（網路資源的使用是否公平，避免有些節點出現特別繁忙的狀態，而有些節點總是處於很閑的狀態），最優性
• 按轉發方式和數據副本數量劃分
1.全路路由（廣播路由）演算法：如洪泛演算法，按照所有路徑廣播轉發（中間轉發節點以及目標節點都會送到很多重復數據。不需要路由表和路由控制功能）
2.多路路由演算法：向所有接近目的節點的路徑轉發（中間轉發節點以及目標節點都會送到很多重復數據。）
3.單路路由演算法：如距離矢量演算法，向目的節點沿著唯一的路徑轉發（中間的轉發節點只轉發一份數據即可）
• 按健壯性和簡單性劃分
1.非自適應演算法（靜態路由演算法）：不能根據網路流量和拓撲結構的變化更新路由表，使用靜態路由表。需要人為的更改和設定。特點是簡單、開銷小、靈活性差。典型演算法為基於流量的路由演算法等
2.自適應演算法（動態路由演算法）：可根據網路流量（網路承載的數據量）和拓撲結構的變化更新路由表。特點是開銷大、健壯性和靈活性好。典型演算法為距離向量路由演算法、鏈路狀態路由演算法等
☆可以靜態路由和動態路由結合起來使用，此時靜態路由的優先順序別較高
測量（獲取）有關路由選擇的網路度量參數（選擇最優，比如是要求傳播距離最短，還是要求傳輸時延短等）。如何測量？選取哪些網路參數？
將路由信息傳送到適當的網路節點。傳送給誰？如何傳送？傳送什麼信息？
計算和更新路由表。更新路由表的演算法
根據新路由表執行分組的轉發
如果路由器J在路由器I到K的最優路由上，那麼從J到K的最優路由一定落在同一路由上
從所有的源節點到一個給定的目的節點的最優路由的集合形成了一個以目的節點為根的樹，稱為匯集樹；路由演算法的目的是找出並使用匯集樹
基本思想：構建子網的拓撲圖，圖中的每個節點代表一個路由器，每條弧代表一條通信線路。為了選擇兩個路由器間的路由，演算法需要在圖中找出節點間的最短路徑
節點數量；地理距離；傳輸延遲；距離、信道帶寬等參數的加權函數
網路規模增大帶來的問題：路由器中的路由表增大；路由器為選擇路由而佔用的內存、CPU時間和網路帶寬增大
分層路由：分而治之的思想；根據需要，將路由器分成區域、聚類、區和組；Fig.6-6，路由表由17項減為7項
分層路由帶來的問題：路由表中的路由不一定是最優路由
☆分層路由功能大部分時候性能是比較好的，可以選擇最優路徑，但是有時也會選擇到非最優路徑。比如上圖中如果想從1A到5C，應該是1A→1B→2A→2B→2D→5C是比較優的選擇，但是按照1A的分層路由表顯示，從區域1到區域5出口線路為1C，因此選擇的路線為1A→1C→3B→4A→5A→5B→5C，這時就相對繞遠了
DVR - Distance Vector Routing
動態路由演算法，也稱Bellman - Ford路由演算法或Ford - Fulkerson演算法，最初用於ARPANET（Internet的前身），被RIP協議所採用
每個路由器維護一張路由表，表中給出了到每個目的地的已知最佳距離和線路，並通過與相鄰路由器交換距離信息來更新表；每隔一段時間，路由器向所有鄰居節點發送它到每個目的節點的距離表，同時它也接收每個鄰居節點發來的距離表；鄰居節點X發來的表中，X到路由器I的距離為Xi，本路由器到X的距離為m，則路由器經過X到i的距離為Xi + m。根據不同鄰居發來的信息，計算Xi + m，並取最小值，更新本路由器的路由表
圖1：
此時路由A把它的路由表發給路由B，B會綜合從A得來的路由表來更新自己的矢量表↓
根據初始A矢量表和B矢量表得知B到A為6，B到C為1，B到D沒有；兩個表都有到E的距離，直接從B到E為8；如果B經由A再到E就要計算A到B的距離加上A到E的距離即可，即6+1=7
圖2：
B把路由表發給C之後↓
從C的初始矢量表可得知C到B為1，C到D為2，C無法直接到A，但是通過B的路由表得知B到A為6，再加上C到B的距離1，得出C到A距離為7，同理可得到E距離為7+1=8
圖3：
C把路由表發給D之後↓
圖4：
D把路由表發給E之後↓
J的相鄰節點為4個，分別為A，I，H，K，因此可以選擇的路線也為4種
現在要求J的最新路由表。以J到E為例，J到A為8，A到E為14，和為22；J到I為10，I到E為7，和為17；J到H為12，H到E為30，和為42；J到K為6，K到E為22，和為28。從而得出，經由I的時候得到的和17最小，因此在新生成的J到E的位置記錄17
無限計算問題：對好消息反應迅速，對壞消息反應遲鈍
比如從E到A，E剛開始連通的時候是不知道如何才能到A的，只有通過B與A交互，C與B交互這樣最終E通過與D交互才知道如何能到A，這就是好消息。可能需要花些時間，但是結果都是無論目的節點是哪裡總會找到路徑
壞消息例子：A，B，C之間通信。B到A的距離為1（A，1），C到A的距離為2（B（經B），2）。各個節點都會有一個刷新周期，到了這個周期的時候每個節點會把自己的路由信息發給其相鄰節點。例如A路由斷開連接，這個時候B到A的線路斷開。也就是B到A的距離為無窮大了（A，∞）。如果在B把這個信息反饋給C之前，C先把路由信息告訴B了，那麼B收到的信息就為（C，3）。因為A已經不存在，而B從C處得知通過C有路徑可以到達A，這時B的路由表就變成（C，3），同樣的這時B再告訴C，C就會變成（B，4），就會這樣無窮計算下去。如果一開始是B先把信息發給C就不會發生這樣的問題
• 觸發式更新：節點不等到刷新周期的到來，只要有突發情況馬上就會把情況通知相鄰路由
• 水平分割：因為一開始C是從B得知經過B可以到達A的，所以用了這種方法之後，C就不會再向B發送如何到A，而只等著B給C發如何到A了。這樣就不會有無窮計算問題
• 定義一個最大值：壞消息例子當中，括弧里後面的數會一直循環增長下去，如果把這個數字設置一個最大值，那麼當循環到這個最大值的時候雙方就不會再就怎麼到A的信息進行交互了，就不會發生無窮計算的情況
• 掛起計數器：壞消息例子當中，B收到了C的路由最新信息（C，3）的時候這個不會馬上生效刷新，（A，∞）會保留兩個周期，在這兩個周期裡面，B肯定有機會給C發送（A，∞），
而因為C沒有通往A的路徑，所以當C到刷新周期的時候給B發的就為（B，∞）。B前後收到的信息不一致，但是第二次收到的信息和B發給C的信息是一致的，所以B就會認為第一次收到的（C，3）是無效的。但是如果C真的有了一條通往A的線路，這時兩次發的信息一定是一致的，那麼B就會相信C的信息，從而把（A，∞）刷新成C給B的信息
❉距離向量路由演算法只適用於小規模網路，每個節點不清楚整個網路的拓撲結構
發現鄰居節點，並學習它們的網路地址，測量到每個鄰居節點的延遲或開銷，將所有學習到的內容封裝成一個鏈路狀態包（包以發送方的標識符開頭，後面是序號、年齡和一個鄰居節點列表；鏈路狀態包定期創建或發生重大事件時創建）。將鏈路狀態包廣播發送給所有其他路由器【洪泛方式：狀態包包含一個序號，每次發送新包時加1。路由器記錄信息對（源路由器，序號），當一個鏈路狀態包到達時，若是新的則分發，若是重復的則丟棄，若序號比路由記錄中的最大序號小則認為過時而丟棄】。計算到每個其他路由器的最短路徑
☆鏈路狀態路由演算法適用於大規模網路。每個節點都會了解其他節點的局部拓撲，因此就會了解整個網路的拓撲結構，這時當前節點就能找到到目的節點的最優路由
• 使用32位序號。
因為序號是循環使用的，如果位數很少，比如只是1~7，那麼7不一定比1大，1有可能是下一輪的第一個數。而32位的時候因為數字特別龐大，不會出現這樣問題
• 增加年齡域，每秒鍾年齡減1，為零則丟棄
比如A發給B （C，4），由於差錯，本來是（C，5）的下一個包，變成了（C，1000）。這之後來的（C，6），（C，7）。。。都沒有（C，1000）大，因此包會被丟棄。但其實後面到的包都是新的。為了避免這樣的問題發生，（C，1000）里的1000就會在每一秒減1，直到年齡比新到的包小，接下來就可以正常接包了。不過這之前到的包都會被丟棄，這也是沒有辦法的事
• 鏈路狀態包到達後，延遲一段時間，並與其它已到達的來自同一路由器的鏈路狀態包比較序號，丟棄重復包，保留新包
• 鏈路狀態包需要應答
為了保證數據傳輸的可靠性