2.4 網絡層

數據鏈路層主要研究和解決的是相鄰兩節點間的通信問題，實現的任務是兩節點間透明地傳輸信息幀。數據鏈路層不能解決由多條鏈路組成的兩主機之間通路的數據傳輸問題，因為兩主機間的通路多由多條鏈路組成，涉及路由選擇和流量控制問題；跨網傳輸時還會出現網絡互聯問題，而這些問題在網絡層可以得到解決。

2.4.1 網絡層的功能

網絡層是OSI參考模型的第3層，介于傳輸層和數據鏈路層之間。網絡層又稱為通信子網層，是通信子網的最高層，其主要功能是控制通信子網的工作，實現網絡節點之間穿越通信子網的數據傳輸。網絡層數據的傳輸單位是分組。網絡層主要的任務是選擇合適的路徑，把分組從源端傳送到目的端，提供的是端到端的服務。

網絡層的主要功能有以下幾項。

①建立、維持和拆除網絡連接兩終端用戶之間的通路是由一個或多個通信子網的多條鏈路串聯而成，還涉及虛電路連接的建立、維持和拆除。

②組包／拆包。它規定分組的類型和具體格式。在發送系統中將傳輸層傳遞過來的長的數據信息拆分為若干個分組，在接收系統端將各分組原來加上的分組頭／尾等控制信息拆掉（即拆包），組合成報文送至上層。

③路由選擇。它又叫路徑選擇，是根據一定的原則和路由選擇算法，在多節點的通信子網中選擇一條從源節點到目的節點的最佳路徑。最佳路徑是相對而言的，一般是選擇時延小、路徑短、中間節點少的路徑作為最佳路徑。

④擁塞控制。網絡層的擁塞控制是對整個通信子網內的流量進行控制，對進入分組交換網的流量進行控制。

網絡層向上層可提供兩類服務，即無連接的網絡服務和面向連接的網絡服務。無連接的網絡服務是不可靠的，而面向連接的網絡服務是可靠的。在網絡層中，這兩種服務的具體實現是數據報服務和虛電路服務。

典型的網絡層協議是CCITT X.25，它是用于公用數據網的分組交換（包交換）協議，另一個常用的網絡層協議是TCP/IP中的IP協議。

2.4.2 路由選擇算法

任何IP網絡最重要的一項功能就是路由。路由是發現、比較、選擇通過網絡到達任何目的IP地址的路徑的過程。在一個通信子網中，網絡源節點到目的節點可有多條傳輸路徑。網絡節點在收到一個分組后，要確定向下一節點傳送的路徑，這就是路由選擇。路由的核心是路由協議。路由協議的核心是路由算法。路由算法是指確定路由選擇的策略。

路由算法的目的就是找出源節點到目的節點的最佳路徑。最佳路徑就是兩個節點所有可能路由中具有最小度量值的那條路徑。常用的度量值包括路徑長度、可靠性或可用性、傳輸時延、帶寬、負載、通信成本。如果一個站點想與另一個并未與之直接連接的站點通信，網絡協議必須找出一條路徑來連接它們。通常根據通過每條路徑發送信息所需的費用和時間的比較來最終確定哪條路徑。這種比較是相當復雜的。小型網絡中可通過人工計算完成，但對于大型網絡則必須用軟件來計算完成。

路由算法分為以下兩種。

（1）靜態路由算法。路由器只在啟動時計算和設置路由，此后路由不再改變或者路由改變很慢，通常只有在人的干涉下才能發生改變，即由管理員手動改變路由表。

①靜態路由選擇策略：靜態路由選擇策略不用測量也無須利用網絡信息，這種策略按某種固定規則進行路由選擇，其中還可分為泛射路由選擇、固定路由選擇和隨機路由選擇3種算法。

②靜態路由的優點：可以使網絡更安全，只有一條流進和流出網絡的路徑（除非定義多條靜態路由）；可以更有效地利用資源，它幾乎不占用傳輸帶寬，不使用路由器上的CPU來計算路由，需要的存儲器也很少。

③靜態路由的缺點：在網絡發生問題或拓撲結構發生變化時，網絡管理員負責手動適應這種變化。只適用于小型網絡。

（2）動態路由算法。路由器在啟動時只建立一個初始路由，當網絡變化時隨時更新，路由動態地發生改變。除了網絡發生改變外，當發生路由循環或是路由振動時，路由也會隨之發生改變。動態路由也稱為自適應路由。

動態路由選擇策略：節點的路由選擇要依靠網絡當前的狀態信息來決定的策略稱為動態路由選擇策略，這種策略能較好地適應網絡流量、拓撲結構的變化，有利于改善網絡的性能。

根據算法是全局的還是分散的，又將動態路由算法分為全局路由算法（Global Routing Algorithm）和分散路由算法（Decentralized Routing Algorithm）。

①全局路由算法要求每一個節點都必須獲悉網絡中所有連接情況以及每條鏈路的信息、權值和開銷等。通常情況下，全局路由算法是指鏈路狀態算法（Link State Algorithms），在這種算法中，初始輸入值必須包括網絡中所有鏈路的信息。

②采用分散路由算法的每個路由僅僅知道與它相連的鏈路信息，而不是像全局路由算法那樣，每個節點都必須獲悉網絡中所有的連接情況以及每條鏈路的權值。通常情況下，分散的路由算法是指距離矢量算法。

下面介紹幾種典型的動態路由算法。

1．Dijkstra算法

Dijkstra算法把網絡看成一張圖。該算法從圖中一個源點出發，計算沿最短路徑到圖中其他各點的距離，在計算最短路徑的過程中構造下一站路由表。對每個路由表都必須用算法計算一次。

2．距離矢量路由算法

距離矢量路由算法（Distance Vector Routing Algorithm）是著名的分布式路由計算算法。路由器周期性地通過網絡向鄰居發送路由信息，每條信息包括目的地、距離等。當信息從鄰居到達包交換機時，路由器就檢查信息中的每一項，如果鄰居到某目的地有比原來更短的路徑，就更新路由表。算法會周期性地把自己的路由表復制傳給與其直接相連的網絡鄰居。每一個接收者加上一個距離向量或它自己的距離“值”到表上，并把它轉發給它的直接鄰居。這個過程在所有直接相連的路由器之間進行。這樣一步一步做下去，最后每一個路由器都得到了其他路由器的信息，最終形成一個網絡“距離”的積累視圖。

3．鏈路狀態路由

鏈接狀態路由也可稱為最短路徑優先（Shortest Path First, SPF）或SPF路由（SPF Routing）。與距離矢量算法一樣，SPF算法也能適應硬件故障的情況。而且SPF是所有計算同時進行，在鏈接狀態改變之后，所有路由器都收到該狀態信息，每個交換機都開始計算自己的路由表。SPF通過和網絡中的其他路由器交換鏈路狀態通告（LSA）來形成和維護網絡路由器的全部信息。LSA交換由網絡中的事件驅動，而不是周期性地進行。

SPF算法的思想是：如果要求節點1～5之間的最短路徑，節點1和5之間經過了節點2、3、4、5。如用minC（x,y）來表示節點x到y之間的最短路徑，則minC（1,5）=minC（1，2）+minC（2,3）+minC（3,4）+minC（4,5）。

算法描述如下。

（1）置N={A}，對于每個節點V∈M.A，置D（V）=C（A,V）。

（2）找出D（V）中最小值的節點W，將W加入到N。對于每一個節點V∈M.N，置D（V）=min（D（V），D（W）+C（W,V））。如果D（W）+C（W,V）<D（V），則從A到V的路徑就變成了A到W的路徑再加上W到V的鏈路的路徑。

（3）重復執行（2），直到N中包括所有的節點，即N=M。

整個搜索算法中的符號定義如下。

●N=已知其與源節點的最優路徑的節點的集合。

●A=源節點。

●M=所有的節點的集合。

●V=宿節點。

●D（v）=算法求得的當前從源節點A到宿節點V的最優路徑的代價。

●C（i,j）=節點i與j之間鄰接的鏈路的權值；若兩個節點之間無直接相連的鏈路，則等于∞。

●P（v）=算法求得的當前從源節點A到宿節點V的最優路徑的宿節點的前一個節點。

4．分級路由

將路由器分成自治系統（Autonomy System, AS），在AS內部，路由器運行同一個路由算法（如LS或DV算法），本AS的路由器相互擁有彼此的信息，這個在AS內部運行的路由算法稱為Inter-AS路由協議（即內部路由協議IGP）。當然，這些AS之間還必須能夠相互連接，這樣在每個AS之內就有一個或多個路由器除完成內部路由運算以外，還要承擔額外的將一些數據包送到本AS之外的目的地的任務，在AS內具有這種功能的路由器稱為網關路由器。為了使網關路由器能夠將一個數據包從一個AS路由到另一個AS（這中間可能經過很多個AS），網關路由器必須知道怎樣在AS之間進行路由。網關路由器用來實現在各個AS之間尋路的路由算法叫Intra-AS路由協議（即外部路由協議EGP）。

將網絡分為一個一個自治系統，自治系統內和自治系統間采取不同的路由算法，稱此為層次路由算法。在層次路由算法中將每個自治系統稱為一個域。

層次路由算法具有以下特點。

①所有節點被都劃分到不同的稱為域（Domain）的組中，可將域視為是分離的、獨立的網絡。

②同一個域中的兩個節點的路由根據此域或網絡的協議決定。

③每個域都有一個或多個特定的節點，稱為路由器（有時也稱為網關），它們決定了域間的路徑。實際上，這些路由器本身也構成了一個網絡。

④如果一個域很大，它可以再由多個子域構成。每個子域含有它自己的路由器。它們決定了在同一個域中各子域的路徑。