本節書摘來自異步社群《is-is網絡設計解決方案》一書中的第6章，第6.1節，作者【美】abe martey，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視
is-is網絡設計解決方案
路由選擇協定的本質是收集網絡環境中的路由選擇資訊，并選擇到所有已知目的的最優路徑。如第2章中提到的，在is-is協定的體系結構中，這些功能是由兩個程序實作的：更新程序與決策程序。更新程序主要負責建立is-is資料庫并維護其穩定性；決策程序使用最短路徑優先（shortest path first，spf）算法基于鍊路狀态資料庫中的資訊計算到所有已知目的的最優路徑。spf算法通過計算區域内一個特定的節點到其他所有節點的最短路徑樹進而得出從這個特定源到每個已知目的的最優路由。
spf算法也稱為dijkstra算法，是由荷蘭數學家edsger wybe dijkstra命名的。e. w. dijkstra于1930年出生于荷蘭鹿特丹，在這裡他學習了實體和數學，并最終成為了一名著名的計算機科學家。在研究一種在兩點之間尋找最佳路徑的算法的過程中，dijkstra于1956年發明了spf算法。dijkstra最初稱之為“最短次生成樹（shortest subspanning tree algorithm）”算法，并将其用于解決早期計算機設計中将電流配置設定到所有必要電路中的問題，進而優化了昂貴的銅線的使用率。本章重點讨論is-is路由的計算過程以及spf算法的操作機制。本章主要包括以下小節：
spf算法概述；
利用spf算法計算is-is路由；
cisco路由器上的is-is spf操作。
注：
最短路徑優先（open shortest path first，ospf）協定是另一種使用spf算法計算路由的路由選擇協定。雖然在協定設計和體系結構上有本質的差別，但ospf和is-is在很多方面仍是相似的。
spf是路由選擇協定用于确定最優路徑的兩種常用算法之一。另一種是bellman-ford算法，這種算法經常用于距離矢量路由選擇協定。bellman-ford算法與spf算法的基本差別在于bellman-ford算法的每一個節點基于直連鄰居的開銷加上鄰居通告的路由的開銷進行路徑計算的。與之相對，spf算法要求每個節點具有關于整個拓撲的完整資訊。是以，一個區域内的所有節點會獲得關于此區域的一緻的鍊路狀态資料庫。鍊路狀态資料庫中包含區域内所有節點的鍊路狀态資訊（即來自區域内每個節點的鍊路狀态資料包）。
與基于bellman-ford算法的路由選擇協定相比，基于spf算法不容易産生路由環路。由于bellman-ford算法依賴鄰居發來的資訊，而這些鄰居可能已經在發生錯誤後不可用了，是以基于bellman-ford算法的路由選擇協定更容易産生環路。是以，此類協定會使用複雜的抑制機制和例如水準分割、毒性逆轉和跳數無限大等其他手段來防止環路。另外基于bellman-ford算法的協定的抑制機制會導緻較長的收斂時間，這也是距離矢量路由選擇協定典型的缺點。鍊路狀态路由選擇協定的收斂時間更快是因為每個節點基于收到的鍊路狀态資料包（lsp）重新計算路由選擇資訊，當網絡發生變化時，lsp會立即産生并泛洪出去。不過，基于spf算法的協定對網絡資源更為敏感，每台路由器需要更高的記憶體和cpu資源以儲存鍊路狀态資料庫及運作spf算法。
dijkstra的算法提供了一個通用的解決方案，該方案适用于任何可以被模拟成有向圖（digraph）的問題。有向圖是由一組通過直線或弧線（鍊路）互相連接配接的頂點（節點）構成的。圖6-1顯示了一個圖例，數字表明的圓圈代表節點，其可以表示為{1,2,3,4,5}的集合。弧線是一條規劃好的箭線。例如，頂點1和2之間的弧線是從頂點1指向頂點2的一個箭頭，可以表示為(1,2)。頂點2和3之間的弧線是對向互指的，并表示為(2,3)和(3,2)，與頂點2和3之間的鍊路方向一緻。
圖6-1中弧線的集合可以被表示為{(1, 2), (1, 3), (2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 3)}。頂點的集合與弧線的集合可以被配置設定一個字母名稱，如下：
n={1,2,3,4,5}，代表頂點的集合。
l={(1, 2), (1, 3), (2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 3)} ，代表弧線的集合。
同時，該圖可以被命名為g，表示為g=（n,l），其中n為頂點的集合，l為弧線的集合。
一條路徑是圖中任意兩個頂點之間有向弧線的序列。例如，在圖6-1中，頂點1到頂點4的路徑可以被表示為 (1, 2), (2, 4) 或 (1, 3), (3, 2), (2, 4)。spf算法的目标是确定從圖中任一參考頂點到所有其他頂點的最短路徑。spf算法使用一種疊代機制來解決這一問題。
下一節将讨論在一個表示為g = (n, l)的有向圖中spf算法的操作，在一個固定的頂點s，頂點集n中：
n—頂點的集合；
l—弧線的集合；
d(i,j) —頂點i到j的距離，如果頂點i與j非直連，則d(i, j) = 無限大；
p —到參考頂點的最短路徑已确定的頂點的集合；
l(n) —目前的從頂點s到頂點n的最小開銷。
spf算法确定了從圖中參考頂點s到每個頂點n的最短路徑。一般情況下，這個過程主要包括三個步驟：
1．初始化；
2．下一個頂點選擇；
3．最小開銷路徑更新。
spf算法操作中的三個主要步驟如下。
步驟1．設定i=0，p0={v0=s}，l(s)=0。如果n直連到s，l(n)=d(s,n)。如果n與s非直連，l(n)=無窮大。使用[l(n),s]标記每一個節點n。設定i=1。
步驟2．找到不在p集合中的下一個頂點vi，對于所有的vi來說，l(vi) = min l(n)。将vi移入p中，新的頂點為vi。
步驟3．更新p集合外的頂點的最短開銷路徑；l(n) = min{l(n),l(vi)+d(vi,n)}。如果l(n)被替代，更新n的标簽為[l(n),nh(vi)]，其中nh(vi)是從s到vi的下一跳。将i替換為 i+l，即(i = i+l)。如果i = n-i，停止；否則回到步驟2。
步驟1為初始化階段。由于算法是疊代的，是以需要按階段運作，每個階段用i标明。在初始化階段，i被設定為0。計算的執行與參考頂點s相關，參考頂點也稱為源。在算法的操作過程中會用到以下三個互相獨立的清單。
未知（unknown，u）：尚未計算的頂點集合。
實驗（tentative，t）：正在進行計算的頂點集合。
路徑（paths，p）：已經計算了最短路徑的頂點集合。
在初始化階段（i=0），參考頂點v0=s被標明并放入已知最近頂點集（p），即p0={v0=s}。圖中其餘頂點放入集合u。s到達自身的開銷l(s)=0。從s到達直連頂點的開銷設定為已知值，到達非直連頂點的開銷被認為是未知的，設定為無窮大。
在步驟2中，算法計算從集合t中標明到達s的下一個最近的頂點，并标記其相關的開銷和下一跳，然後将其移入集合p。在初始化階段，隻有與s直連的頂點會從集合u移入集合t。具有最低開銷的頂點會被移入集合p。當一個頂點從集合t移入集合p後，所有與其直連且不在集合t中的頂點将被移入集合t中。
在最後一步中，與最新移入集合p的頂點相關的集合t中的每個節點的最小開銷将被更新，下一跳也将改變為此節點。隻有當新的開銷值更低時才會替代現有的最小開銷。
算法随後進行下一次疊代，回到步驟2并再次進行步驟3，直到所有的節點被移入集合p。對于包括作為計算中心的參考頂點在内的具有n個頂點的圖例來說，從0開始需要進行n-1次疊代。在完成最後的第n-1次疊代後，會計算出從參考頂點到其他所有頂點的最短距離。
在一個有向圖中确定任意兩個頂點之間的最短路徑與在資料通信網絡中找到任意兩個節點之間的最短路徑是相似的。如前文提到的，路由選擇協定的功能是依據一些優化的标準确定網絡中兩個節點之間的最短路徑，這些标準通常為最小開銷或最低度量。以此類推，通信網絡中的路由器類似于有向圖中的頂點，鍊路或鄰接關系類似于弧線。由于網絡節點之間的通信流是雙向的，每條網絡鍊路會被看作是一對平行的指向相反方向的弧線。網絡中的鍊路會被配置設定一個稱作開銷或度量的權重值。大部分現實中的網絡使用數字表示鍊路開銷，與帶寬成反比。是以，最快的鍊路會被配置設定最小的開銷值。在網絡中的節點間尋找最短路徑的過程其實就是确定節點間最小開銷值路徑的過程。其他可能的度量選型包括跳數和複合度量。複合度量是基于帶寬、延遲、可靠性、負載、最大傳輸單元（maximum transmission unit，mtu）及其他鍊路特性綜合計算得到的。
前文描述了spf算法是如何工作的。這種工作機制表明，spf算法的運算開銷是與參與運算的節點和鍊路的數量相關的。在大型網絡中，spf算法是非常占用資源的，其需要的計算時間達到n2，其中n為節點數量。這一複雜的計算過程可以被直覺地看作是：對于全部n個節點，确定從一個參考節點到圖中所有其他節點的最低開銷路徑需要n-1次疊代，在每次疊代中，确定最小開銷頂點所需的運算次數與n成比例。
如果在一個圖中有n個節點和一共l條鍊路，那麼一般情況下，spf的計算時間與鍊路數量成比例：l的對數的l倍。這就是spf計算的開銷的階數：o(llogl)。
在一個互連程度不高的網絡中，例如，所有的節點僅以最少的鍊路以直線的布局相連，此時l等于n-1。llogl就可以被表示為llog(n-1)，等價于llogn。總的來說，可以使用o(llogn)來估算dijkstra spf算法的計算複雜度，其中l為網路中的全部鍊路的數量，n為節點數。計算複雜度與執行算法所需的處理時間是直接相關的。
與dijkstra算法相關的另一個重要元素是對存儲器或記憶體的需求。
圖中每台路由器存儲了n個lsp，每一個lsp來自于區域中的一個節點。由于每個lsp中包含所連鍊路和鄰接鄰居的資訊，假定k是所連的鍊路數，是以每個lsp的大小是與k成比例的。是以，每個節點需要的存儲空間與nk成比例。即，每個節點的記憶體需求階數是為o(nk)或o(l)，其中l是全部鍊路的數量。在互連程度不高的環境中，l與節點數n的階數相同，記憶體需求可以估算為o(n)。
對于節點數較多的網絡，spf算法過多的記憶體需求以及相應的長處理時間是在網絡設計規劃中引入層次結構的主要驅動因素。is-is提供了一個兩層的層次結構進而允許建立多個大小合理的level 1區域，并通過level 1骨幹區域将這些level 1區域連接配接起來。
dijkstra.html。
在圖6-2中，用帶有雙向箭頭的鍊路作為弧線，表示在兩個鄰接節點間雙向的開銷相同。這可能與實際的網絡情況不符。特别是is-is協定并不要求鍊路的雙向路徑成本相同。圖6-2的拓撲中包含了5個節點和7條鍊路。算法在執行過程中以節點1作為參考節點。在真實的網絡中，每一個節點會以自身為參考節點進行類似的運算。運算的最終目标是獲得從源節點到拓撲中所有其他節點的最低開銷（最優）路徑。
算法在初始化時i=0，i清單示疊代次數。l(n)是在某次疊代中參考節點s到節點n的總開銷。“下一跳”是到達某一特定節點的直連下一跳。表中其他縮寫的釋義如下所示。
p：在路徑集合或清單中的條目集合。
value：s的直連下一跳。
表6-1中加粗顯示了每次疊代中從實驗集（tentative set，t）中選出的路徑。在i=1次疊代中，隻有節點2和3被放入了t中。每條路徑都給出了到達目标的度量和下一跳。由于節點2和3是直連到節點1的，是以到達2和3的下一跳就是2和3本身。
沒有直連到參考節點s的節點從其父節點處繼承下一跳。例如，到達節點4的最優路徑是通過節點3，開銷值為3。到達節點5的最優路徑是通過節點4，而節點4的父節點是節點3。是以，節點3是從節點1到節點5的下一跳。需要注意的是下一跳的計算表達了資料轉發流程，即每個節點在沿着最優路徑将資料包發往目标時隻關注其下一跳。
表6-1的說明（spf運算示例）
本小節将對表6-1中spf算法的操作步驟進行了解釋。步驟與疊代次序一緻。
i=0 在第一次疊代中，節點1被選為源，相應地，l(1)=0和nh（下一跳）=1被填入到節點1下以表明從源到節點1的下一跳是其本身，且開銷為0。沒有關于其他節點的動作。
i=1 在疊代1的運算過程中，直連到節點1的節點2和3被放入t中。從節點1到節點2的下一跳是節點2，開銷為2。從節點1到節點3的下一跳是節點3，開銷為1。節點4和5仍留在未知集（unknown set，u）中，開銷為無窮大。由于節點3具有最低開銷，是以從t中提升到p中。
i=2 在節點3從t提升到p之後，由于其直連鄰居節點4和5并不在p中，是以将移入t中。需要注意節點2已經在t中了，開銷為2。從源節點經過節點3到達節點2的開銷為5，由于節點2直接到達源節點的開銷為2，為最低開銷，是以該條目将被保留。節點4和5使用節點3作為到達源的下一跳。從節點1到節點4的總的開銷值為3，到節點5為6。由于具有最低開銷，節點2從t提升到p中。
i=3 在節點2從t提升到p之後，其不在p中的直連鄰居将被加以運算。此操作隻會對節點5進行。節點5已經在t中。從節點1經過節點2到達節點4的總的開銷為5，先前的路徑由于開銷更低将被保留。由于與節點5相比，節點4具有更低的關聯開銷，是以節點4将被提升到p中。
i=5 在節點4從t提升到p之後，其不在p中的直連鄰居将被加以運算。此操作隻會對節點5進行。節點5已經在t中。從節點1經過節點4到達節點5的總的開銷低于先前路徑的開銷6。是以，節點4取代節點3作為節點5的父節點。同時，節點5繼承了與節點4關聯的下一跳節點3，開銷值減為5。由于節點5是t中的唯一節點，是以将被提升到p中。
圖6-3顯示了在算法運算完成後産生的以節點1為參考節點的最小開銷拓撲。節點2和3是直連到節點1的，但是到達節點4的最優路徑為通過節點3，到達節點5的最優路徑是首先通過節點3，随後通過節點4。