第四章網絡層

網絡層的功能與服務路由選擇擁塞控制X.25中的網絡層

網絡層的任務是要以分組為單位將數據信息從源節點傳送到目的節點。第四章網絡層網絡層的功能與服務網絡層的任務是1第一節網絡層的功能與服務4.1.1網絡層功能及模型

網絡層的作用：在數據鏈路層提供的在相鄰兩個節點之間透明、可靠的傳送數據幀的功能的基礎上，進一步管理網絡中的通信，將從傳輸層交出的數據以分組為單位，從源節點通過通信子網沿適當的路徑傳送到目的節點。

網絡層的功能：向傳輸層提供服務、路由選擇、擁塞控制、網絡互聯。第一節網絡層的功能與服務4.1.1網絡層功能及模型2第一節網絡層的功能與服務4.1.2網絡層提供的服務

面向連接的網絡服務——虛電路服務無連接的網路服務——數據報服務虛電路服務

虛電路：在通信之前，需要在源節點和目的節點間建立起一條邏輯上的網絡連接，我們稱之為虛電路。建立虛電路過程：

建立連接

數據交換

拆除連接H5BADECVC1VC2VC3H1H2H4H3(a)第一節網絡層的功能與服務4.1.2網絡層提供的服務H53第一節網絡層的功能與服務每個節點都應保持一個虛電路表，它的每一項記錄了一個打開的虛電路信息，包括虛電路號、前一節點和下一節點的標識。通常采用“動態”虛電路號碼選取法：即總是選取當前尚未使用的最低虛電路號。BADECH1H2H4H3H5

A—EA—DC—D(b)虛電路的實現：建立虛電路時分配給該虛電路一個沒用過的虛電路號，以區別于本系統中的其他虛電路。傳送數據時，每個數據分組含有分組號、校驗和控制信息及其要經過的虛電路的號碼，以區別其它虛點路上的分組信息。第一節網絡層的功能與服務每個節點都應保持一個虛電路表，它4虛電路實現圖例

（表示5條虛電路建立的順序以及所經過的節點）（5個節點的內存路由表）（表示沿虛電路H1→A→B→C→E→H5傳送時，虛電路號的變換情況）

BADECH1H2H4H3H5

A—EA—DC—D(b)虛電路實現圖例（表示5條虛電路建立的順序以及所經過的節點5第一節網絡層的功能與服務數據報方式

數據報服務：沒有虛電路建立的過程，每一個發出的分組（稱為一個數據報）都攜帶了完整的目的地址信息，因而每一個分組都可以獨立的選擇路由。分組到達目的節點的順序有可能與發送順序不完全一致，甚至會失去某些分組。

要求接收方主機具有重新排序、糾正重復或丟失分組的功能。數據報實現在每個節點同樣要有一個路由表，按照每個分組所攜帶的目的地址查找路由表來決定應沿哪條鏈路轉發分組。

BADECH1H2H4H3H5

A—EA—DC—D(b)第一節網絡層的功能與服務數據報方式數據6第一節網絡層的功能與服務虛電路服務與數據報服務的比較第一節網絡層的功能與服務虛電路服務與數據報7第二節路由選擇4.2.1理想的路由算法

路由算法：網絡節點在收到一個分組后，決定在那一條輸出鏈路上傳送下去所使用的策略。理想的路由算法的一些特點：(1)正確性。必須是信息快速、正確的傳輸。(2)簡單性。計算簡單可以減少時延。另外，路由選擇的計算不應使網絡的通信量增加太多的額外開銷。(3)堅固性。算法應能適應通信量和網絡拓撲的變化，要有自適應性。有時稱這種自適應性為“健壯性”(robustness)。(4)穩定性。當通信量和網絡拓撲發生變化時，路由算法應收斂于一個可以接受的解，而不應產生過多的振蕩。(5)公平性。算法應對所有用戶（除對少數優先級高的用戶）都是平等的。(6)最佳性。是指以最低的費用來實現路由算法。實際上，所謂“最佳”只能是相對于某一種特定要求下得出的較為合理的選擇而已。第二節路由選擇4.2.1理想的路由算法8第二節路由選擇4.2.2最短通路路由選擇

例：尋找從源節點A到網絡中其他各節點的最短通路。令D(ν)為源節點(節點A)到節點ν的距離；令N表示網絡節點的集合，初始時令N＝{A}；令l(i，j)為節點i至節點j之間的距離。算法：(1)初始化D(ν)=(A,ν)若節點ν與節點A直接相連∞若節點ν與節點A不直接相連(2)尋找一個不在N中的節點ω，其D(ω)值為最小，把ω加入到N中，然后對所有不在N中的節點，用D(ν)和[D(ω)+λ(ω，ν)]中的較小的值去更新原有的D(ν)值，即：

D(ν)←min[D(ν)，D(ω)+λ(ω，ν)]

(3)重復步驟(2)，直到所有的網絡節點都在N中為止。

ECFABD1211223355圖4-6求最短通路算法的網絡舉例

第二節路由選擇4.2.2最短通路路由選擇ECFAB9第二節路由選擇ECFABD1211223355圖4-6求最短通路算法的網絡舉例

步驟ND(B)D(C)D(D)D(E)D(F)初始化{A}251∞∞1{A,D}24①2∞2{A,D,E}231②43{A,B,D,E}②31244{A,B,C,D,E}2③1245{A,B,C,D,E,F}2312④第二節路由選擇ECFABD1211223355圖4-610第二節路由選擇4.2.3路由選擇的不同策略

1.非自適應路由選擇——簡單、開銷小(1)洪泛法(flooding)策略：當某個網絡節點從某條輸入線路收到一個不是發給它的分組時，就向所有與此節點相連的其它鏈路轉發出去。優點：①算法簡單，幾乎不需要什么計算；②可以在最短的時間內接收方收到信息；③方便實現廣播通信和多址通信，具有良好的健壯性，廣泛應用于軍事網中。缺點：①造成分組無休止的傳輸；②使接收方收到多個重復的分組；③網絡中分組數目迅速增長，結果導致網絡出現擁塞現象。改進：采用計數器或登記表法控制網絡中分組數目的增長。第二節路由選擇4.2.3路由選擇的不同策略11第二節路由選擇(2)有選擇的洪泛法策略：僅在滿足某些事先確定的條件的鏈路上轉發分組。好處：分組不會向不希望去的方向轉發。(3)固定路由法策略：在每個節點上保存一張由此節點到網絡中其他節點的固定路由表（由網絡設計人員或管理人員根據網絡拓撲結構、流量分布和其他因素編制的，并且在此后的一段相當時間保持固定不變），表中規定一條或多條輸出線。適用：當網絡拓撲固定不變并且通信量也相對穩定時。(4)隨機走動法(randomwalk)策略：當分組到達某個節點時就隨機地選擇應當走哪條鏈路作為轉發的路由，因此又稱為隨機徘徊。適用：在非自適應的路由策略中，若可能發生節點或鏈路的故障，那么隨機走動法巳被證明是非常有效的，它使得路由算法具有較好的健壯性。第二節路由選擇(2)有選擇的洪泛法12第二節路由選擇(5)分散通信量法(trafficbifurcation)或查表選擇路由(directoryrouting)策略：事先在每個節點的內存中設置一個路由表，路由表中給出幾個可供采用的輸出鏈路，并且對每條鏈路賦予一個概率；當一個分組到達該節點時，此節點即產生一個從0.00到0.99的隨機數，然后按此隨機數的大小，查表找出相應的輸出鏈路。HBACIEJKDGFL（a）目的節點最佳選擇次佳選擇最差選擇輸出線概率輸出線概率輸出線概率BA0.46H0.31I0.23CA0.38I0.34H0.28DH0.50A0.25I0.25EA0.40I0.40H0.20FA0.37H0.33I0.30GH0.46A0.31K0.23HH0.63K0.21A0.16II0.65A0.22H0.13KK0.67H0.22A0.11LK0.42H0.40A0.18AA0.63I0.21H0.16第二節路由選擇(5)分散通信量法(trafficbi13第二節路由選擇2．自適應路由選擇當網絡拓撲發生變化時及網絡某個節點或鏈路發生故障時，在網絡的某個局部范圍做出調整路由的決定。(1)孤立的路由選擇策略策略：只根據本節點的狀態來選擇路由，而不和其它節點交換狀態信息。“熱土豆”算法：當收到一個分組時，不管其目的地址如何，把剛收到的分組以最快速度發往各鏈路中等待隊列長度最短的等待隊列中排隊等候發送。缺點：不準確，有時隊列最短的方向井非正確的轉發路由。改進：令隊列長度為Q，在每個隊列增加一個對于某一目的地址的偏移數B，取Q+B值為最小的隊列作為轉發方向。例如：對應于F，E，D和C的B值若分別為0，6，5和8．則算出相應的Q十B值分別為5，7，9和10，因此應把收到的分組送到發往F的隊列中。

至C至F從A來節點J至D至E第二節路由選擇2．自適應路由選擇至C至F從A來節點J至14第二節路由選擇(2)分布式路由選擇策略——是目前應用最廣泛的路由算法特點：適應性較好，每個節點周期性地從相鄰的節點獲得網絡狀態信息，同時也將本節點做出的決定周期性地通知周圍的各節點，以使這些節點不斷地根據網絡新的狀態更新其路由選擇決定。例：ARPANET使用算法是在每一個節點保持兩個向量，即：dil

·Di=··

dinsil

·Si=··

sin

Di——節點i的時延向量；dij——節點i至節點j的最小時延當前估值(dij=0)；n——網絡中的節點數；Si——節點i的后繼節點向量；SIJ——后繼節點(節點i到節點j當前最小時延路由中的第二個節點。對于任一節點k每隔128ms與其所有相鄰節點交換時延向量，按以下方法對本節點的時延向量和后繼節點向量進行修改：dki＝[dki+dij-] Ski==i，用這個i使[dki+dij-]為最小。

A——節點k的所有相鄰節點的集合；dki——節點k到節點i的時延的當前估值。

第二節路由選擇(2)分布式路由選擇策略——是目前應用最15第二節路由選擇例：5361241212123355203235330213122013D2D4D3節點1收到3個時延向量

目的節點延遲下一個節點10—222353414563683目的節點延遲下一個節點10—222334414524644更新后的路由表

更新前在節點1的路由表

第二節路由選擇例：5361241212123355216第二節路由選擇(3)集中式路由選擇策略策略：利用網控中心NCC，專門收集各節點定期發來的狀態信息，然后由它根據這些狀態信息及網絡拓撲結構，動態的計算出每個節點現時的路由選擇表，再將新的路由選擇表同時送回各個節點使用。優點：算法能定期按拓撲結構和信息量變化修改各節點的路由選擇表；容易得到精確的路由，消除了分組在網內“兜圈子”及路由“振蕩”的現象；可起到對進入網絡通信量的某種流量控制作用。缺點：在報告狀態-計算-送回路由選擇表的過程中花費了不少時間，因此在系統變化較快的網絡中很難獲得理想的控制效果；NCC的工作量大，因此需要采用速度快、可靠性高的機器；由于采用集中控制，因而NCC工作的可靠性尤為重要，所以應采用若干個級別的NCC協同控制，一旦高一級的NCC出現故障，低一級的NCC馬上接替工作，但這種方法花費較大且仍不能滿足全部要求；網中負載不平衡，靠近NCC的鏈路負擔重，而遠離NCC的鏈路負載較輕。

(4)混合式路由選擇策略第二節路由選擇(3)集中式路由選擇策略17第三節擁塞控制

擁塞：當到達通信子網中某部分的分組量過多時，就會造成網絡性能的下降的現象，稱為擁塞。網絡性能下降的表現：信息報傳輸延遲增加和網絡吞吐量下降。

吞吐量理想的擁塞控制實際的擁塞控制無擁塞控制死鎖擁塞輸入負載圖4-12流量控制所起的作用

4.3.1擁塞產生的原因

出現資源擁塞的條件：

∑對資源的需求＞可用資源解決網絡擁塞的辦法是采用流量控制。擁塞控制的主要功能：(1)防止網絡因過載而引起吞吐量下降和時延增加；(2)避免死鎖；(3)在互相競爭的各用戶之間公平地分配資源。單純的增加資源不一定能解決擁塞問題，甚至可能更壞！第三節擁塞控制擁塞：當到達通信子網中某部分的分組量18第三節擁塞控制4.3.2擁塞控制方法

1．緩沖區預分配法——適用于虛電路通信子網建立虛電路時源節點相鄰節點下一節點目的節點呼叫分組登記路徑選擇出入口表；單工停——等信道：預定一個buffer；雙工停——等信道：預定兩個buffer（每個方向一個)；滑動窗口流水協議：預定數量等于滑動窗口尺寸大小個buffer。傳送分組時源節點相鄰節點下一節點目的節點數據分組buffer滿?NY改走其它路徑優點：可靠。缺點：可能造成浪費。第三節擁塞控制4.3.2擁塞控制方法源節點19第三節擁塞控制2．抑制分組法——可用虛電路或數據報通信子網策略：在出現擁塞前兆時，對分組進行截流。算法實現：每個節點(路由器)都監視其輸出線路利用率μ=

(0，1)

μ可用下列公式更新：μ新=αμ舊+（1-α）f

f反映線路瞬時利用率，取值為0-1之間的常數；α反映了更新速度。各節點為每一條線路定義閥值，當μ大于此值時，則該線路進入“告警”狀態。每新收到分組時路由器要查看其輸出線是否處于“告警”狀態，若是則發送一個抑制分組到源主機，并在抑制分組中指明分組的目的地，并在原分組上加一個標志，表示以后不用再產生抑制分組；發送端主機收到該抑制分組后，將發送速率降低一檔，若繼續發送抑制分組，則發送端繼續降低速率。近期實際數據速率最大數據速率第三節擁塞控制2．抑制分組法——可用虛電路或數據報通信20第三節擁塞控制3．分組丟棄法策略：當緩沖區滿時，將到來的分組丟棄，丟棄分組后，發送端因得不到確認而超時重發。緩沖器分配規則：為每個輸入線分配一個能容納一個分組的緩沖器先把到達的分組接收下來，檢查該分組內有無對前面發送的信息報的應答，如果應答表明前一次發送的信息包已經妥收，那么把此分組丟棄，準備接收下一個分組。限制輸出線隊列長度N+1個節點緩沖區除了分給輸入線(1個)以外，剩余的全分給輸出線(N個)。

分配給輸出緩沖區的方法有平分法最大分配法最小分配法最大最小分配法第三節擁塞控制3．分組丟棄法21第三節擁塞控制4．許可證法策略：限制通信子網內的分組數目，使之不超過某一個固定值從而避免擁塞。實現方法：在通信子網中有固定數目的許可證在網中隨機巡航流動，任何一個分組想進入網絡必須先獲得一個許可證；當分組到達終點時就釋放許可證。許可證的分布原則：盡量減少分組等待許可證的時間。平均分布；——忙、閑不公平所有許可證在網內四處流動；——付出等待時延每個節點上保存少量許可證，其它許可證在網內流動。存在問題：

能防止全局性擁塞，但仍不能完全消除局部擁塞；

需要防止許可證丟失。設網內節點數為N，則許可證數可選為3N，每個節點能擁有的許可證L3為最佳分布。第三節擁塞控制4．許可證法22第三節擁塞控制DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

4.3.3流量控制

流量控制和擁塞控制的區別

擁塞控制:必須保證通信子網能正常傳輸數據，包括流量控制，使全局性問題。

流量控制:根據接收端能承受的數據速率來調節發送端傳輸數據的速率，防止到達接收端的數據速率超過接收端的處理速率，只與發送者與接收者之間的點到點通信量有關。流量控制是按級進行的，大致可以劃分為四種不同級別。沒有擁塞問題不等于沒有流量控制問題！第三節擁塞控制DTEDCEDTEDCE傳輸級入口級到出23第三節擁塞控制1.網段級流量控制——需要解決“存儲——轉發”問題目的：在相鄰兩節點之間維持一個均勻的流量，以避免出現局部緩沖區擁塞和死鎖。根據是對兩節點間的流量還是對其中每條虛電路的流量進行控制可再劃分為：數據鏈路網段級流量控制——適用于虛電路、數據報兩種業務采用信道隊列限制法(即分組丟棄法)進行控制：監視每一個隊列的緩沖區的占用情況并對其定義一個極限(固定的或動態可調的)，當某一隊列中待轉發的分組數超過此極限時即丟棄該分組。特點：能有效的避免吞吐量的降低，但無法解決間接死鎖的問題。虛電路網段級流量控制——適用于虛電路DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

第三節擁塞控制1.網段級流量控制——需要解決“存儲——24第三節擁塞控制信道隊列限制法有以下四種變形：平均分配設N為節點中輸出隊列的總數,Ni為第i個隊列中的分組數,而B為緩沖區的大小(除分配給輸入線的之外），則約束條件為：0≤Ni≤B/N這種固定分配方法，效率低，性能較差。

最長隊列共享設bmax為所允許的最長隊列(此處bmax＞B/N)，則約束條件為：0≤Ni≤bmax以及∑Ni≤B最小分配共享設bmin為保證分配給每一隊列的緩沖區大小(當然bin≤B/N)，則約束條件為：∑Max(0,Ni-bmin)≤B-Nbmin最小分配最長隊列共享合并了前兩種方式，即每—隊列保證有一個最小的緩沖區bmin供使用，同時其最大長度受bmax的限制。第三節擁塞控制信道隊列限制法有以下四種變形：25第三節擁塞控制死鎖：兩個節點之間互相僵持，整個網絡不能傳輸分組，吞吐量為零的情況。1.存儲——轉發死鎖直接存儲——轉發死鎖：互相占用了對方需要的資源而造成的死鎖。間接存儲——轉發死鎖：每個節點都試圖向相臨節點發送分組，但沒有一個節點有空閑緩沖區來接收分組導致產生死鎖。2.重裝死鎖：發生在目的節點，因緩沖區不足無法排序組裝造成。R4R3R1Q3Q2P1Q1P3P2Q4R2主機H節點X節點Y節點Z發往A發往DBACD發往C發往Bbmax(b)AB(a)第三節擁塞控制死鎖：兩個節點之間互相僵持，整個網絡不26第三節擁塞控制信道隊列限制法無法解決間接死鎖的問題！

解決間接存儲——轉發死鎖

采用結構化緩沖池策略或稱為緩沖區的有向圖分配法給每個節點開辟M十1個緩沖區(每個緩沖區存放一個分組)，并從0到M編上號碼。僅當與主機相連的源節點的緩沖區0空閑時分組才能發往源節點的緩沖區0。接著，僅當某個相鄰節點中的緩沖區1空閑時分組才能發往緩沖區1，以后每轉發一次，所到達的緩沖區的編號就增大一個號，012……M最終，分組的最壞結局一定是以下兩種情況之一：·傳到所要到達的目的節點，然后交付給主機；·傳到編號為M的緩沖區，然后被丟棄，因而不再消耗網絡的資源。第三節擁塞控制信道隊列限制法無法解決間接死鎖的問題！27第三節擁塞控制2．源節點到目的節點級的流量控制——需要解決“重裝死鎖”問題目的：防止在輸出節點出現由于目的節點到主機的連接線路過載或是由于主機接收數的速率太低而導致緩沖區擁塞。當需要在目的節點把到達的分組重新裝配成報文時有可能出現重裝死鎖！在ARPANET中使用的源節點到目的節點級的流量控制的方法是：①源節點發送報文時必須先發送一個“請求緩沖空間”的分組；②目的節點收到該分組后，即為此報文保留8個緩沖區并回答一個“分配”分組。③當整個報文的8個分組都收齊并送交主機后，目的節點就發回一個“準備下一報文”的確認分組。④當源節點無報文要發送但仍收到“分配”分組時，須發回“歸還”分組以釋放目的節點緩沖空間。DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

第三節擁塞控制2．源節點到目的節點級的流量控制——需要28第三節擁塞控制3．進網級流量控制目的：控制網絡外部的通信量進入網絡從而防止整個網內的緩沖區產生擁塞。

擁塞的測量：①局部測量：測量入口節點緩沖區的情況；②全局測量：測量全網所有緩沖區的占用程度；③選擇測量：測量某個目的節點的整條通路的擁塞情況。將測量結果報告進網節點，以控制從外部進入網內的通信量。最出名的進網級流量控制方案為許可證法。DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

第三節擁塞控制3．進網級流量控制DTEDCEDTEDC29第三節擁塞控制4．傳輸級流量控制目的：在兩個遠程進程之間的虛電路連接中提供分組的可靠傳送，即在進程級防止用戶緩沖區出現擁塞。各層采取的流量控制：數據鏈路層：進網級、網段級（數據鏈路網段級）網絡層：入口到出口級、網段級（虛電路網段級）傳輸層：傳輸級DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

第三節擁塞控制4．傳輸級流量控制DTEDCEDTEDC30第四節X.25的網絡層4.4.1X.25簡介

1．X.25的層次結構

由CCITT制定，是關于用專用電路連接到公用數據網上的分組型數據終端設備（DTE）與數據電路端接設備（DCE）之間的接口標準。版本：1976、1980支持虛電路、數據報兩種服務；1984取消了數據報服務；1988、1992只支持虛電路服務。X.25協議目前以虛電路服務為基礎。分組級主要功能：向主機提供多邏輯信道的虛電路服務。X.25接口X.25接口X.25接口DTEDCEDTEDCEDCEDTEVC1VC2公用分組交換網第四節X.25的網絡層4.4.1X.25簡介X.31第四節

X.25的網絡層FAC數據FCSFTPDU數據比特流LAPB數鏈層接口分組層數據鏈路層物理層高層分組層數據鏈路層物理層至遠程用戶進程多重信道接口X.21物理層X.25的三層層次結構

物理層：數據傳送單位是“比特”，接口標準采用X.21建議書。數據鏈路層：數據傳送單位是“幀”，接口標準采用平衡型鏈路接入規程LAPB，是HDLC的一個子集。分組層：數據傳送單位是“分組”，在DTE與的DCE之間可以建立多條邏輯信道(0-4095號)。第四節X.25的網絡層FAC數據FC32第四節

X.25的網絡層2．X.25的分組層通信過程可分為三個階段：呼叫建立階段、數據傳送階段、虛電路釋放階段。DTELCN=10LCN=10LCN=10LCN=10LCN=10LCN=10DTELCN=99LCN=99LCN=99LCN=99LCN=99LCN=99DCEDCE主叫方被叫方網絡呼叫請求呼叫接通數據釋放請求釋放證實數據入呼叫呼叫接受數據數據釋放指示釋放響應第四節X.25的網絡層2．X.25的分組層DTEDTED33第四節

X.25的網絡層3．X.25的狀態圖

例：呼叫建立階段的狀態圖

1就緒5呼叫沖突4數據傳送3DCE等待2DTE等待DTE呼叫請求DTE呼叫請求DCE入呼叫DCE入呼叫DCE呼叫接通DCE呼叫接通DTE呼叫請求橢圓代表一個DTE或DCE對的狀態；箭頭代表狀態變遷的方向；箭頭旁邊的文字說明表示是由誰(DTE還是DCE)發出了何種分組。第四節X.25的網絡層3．X.25的狀態圖15432DT34第四節

X.25的網絡層4.4.2X.25的分組格式

X.25的分組可分為：控制分組、數據分組。X.25分組由分組的首部和分組的數據部分組成。所謂分組格式，主要就是指分組首部的組成，在分組的后面不加尾部。1.控制分組

例：呼叫請求分組第四節X.25的網絡層4.4.2X.25的分組格式35第四節

X.25的網絡層2．數據分組格式

第四節X.25的網絡層2．數據分組格式36第四節

X.25的網絡層4.4.3X.25網絡與字符方式終端的連接

CCITT制定了分組裝拆器PAD(又稱為分組組裝分解設施)以適應以下兩種情況：PAD則提供了智能使字符方式終端能夠用X．25協議同網上的其他主機通信；PAD提供了許多參數供種類繁多、性能各異的字符方式終端選擇，使其能夠方便地接入到X．25網。定義PAD設施的三個建議書：X．30——描述PAD的功能以及控制它工作的一些參數。X．28——描述PAD到字符方式終端的協議。X．29——描述PAD到主機(同步終端)的協議。X.3主機字符方式終端字符流分組流分組流X.25接口X.25接口X.28X.29第四節X.25的網絡層4.4.3X.25網絡與字符方式37第四章網絡層

網絡層的功能與服務路由選擇擁塞控制X.25中的網絡層

網絡層的任務是要以分組為單位將數據信息從源節點傳送到目的節點。第四章網絡層網絡層的功能與服務網絡層的任務是38第一節網絡層的功能與服務4.1.1網絡層功能及模型

網絡層的作用：在數據鏈路層提供的在相鄰兩個節點之間透明、可靠的傳送數據幀的功能的基礎上，進一步管理網絡中的通信，將從傳輸層交出的數據以分組為單位，從源節點通過通信子網沿適當的路徑傳送到目的節點。

網絡層的功能：向傳輸層提供服務、路由選擇、擁塞控制、網絡互聯。第一節網絡層的功能與服務4.1.1網絡層功能及模型39第一節網絡層的功能與服務4.1.2網絡層提供的服務

面向連接的網絡服務——虛電路服務無連接的網路服務——數據報服務虛電路服務

虛電路：在通信之前，需要在源節點和目的節點間建立起一條邏輯上的網絡連接，我們稱之為虛電路。建立虛電路過程：

建立連接

數據交換

拆除連接H5BADECVC1VC2VC3H1H2H4H3(a)第一節網絡層的功能與服務4.1.2網絡層提供的服務H540第一節網絡層的功能與服務每個節點都應保持一個虛電路表，它的每一項記錄了一個打開的虛電路信息，包括虛電路號、前一節點和下一節點的標識。通常采用“動態”虛電路號碼選取法：即總是選取當前尚未使用的最低虛電路號。BADECH1H2H4H3H5

A—EA—DC—D(b)虛電路的實現：建立虛電路時分配給該虛電路一個沒用過的虛電路號，以區別于本系統中的其他虛電路。傳送數據時，每個數據分組含有分組號、校驗和控制信息及其要經過的虛電路的號碼，以區別其它虛點路上的分組信息。第一節網絡層的功能與服務每個節點都應保持一個虛電路表，它41虛電路實現圖例

（表示5條虛電路建立的順序以及所經過的節點）（5個節點的內存路由表）（表示沿虛電路H1→A→B→C→E→H5傳送時，虛電路號的變換情況）

BADECH1H2H4H3H5

A—EA—DC—D(b)虛電路實現圖例（表示5條虛電路建立的順序以及所經過的節點42第一節網絡層的功能與服務數據報方式

數據報服務：沒有虛電路建立的過程，每一個發出的分組（稱為一個數據報）都攜帶了完整的目的地址信息，因而每一個分組都可以獨立的選擇路由。分組到達目的節點的順序有可能與發送順序不完全一致，甚至會失去某些分組。

要求接收方主機具有重新排序、糾正重復或丟失分組的功能。數據報實現在每個節點同樣要有一個路由表，按照每個分組所攜帶的目的地址查找路由表來決定應沿哪條鏈路轉發分組。

BADECH1H2H4H3H5

A—EA—DC—D(b)第一節網絡層的功能與服務數據報方式數據43第一節網絡層的功能與服務虛電路服務與數據報服務的比較第一節網絡層的功能與服務虛電路服務與數據報44第二節路由選擇4.2.1理想的路由算法

路由算法：網絡節點在收到一個分組后，決定在那一條輸出鏈路上傳送下去所使用的策略。理想的路由算法的一些特點：(1)正確性。必須是信息快速、正確的傳輸。(2)簡單性。計算簡單可以減少時延。另外，路由選擇的計算不應使網絡的通信量增加太多的額外開銷。(3)堅固性。算法應能適應通信量和網絡拓撲的變化，要有自適應性。有時稱這種自適應性為“健壯性”(robustness)。(4)穩定性。當通信量和網絡拓撲發生變化時，路由算法應收斂于一個可以接受的解，而不應產生過多的振蕩。(5)公平性。算法應對所有用戶（除對少數優先級高的用戶）都是平等的。(6)最佳性。是指以最低的費用來實現路由算法。實際上，所謂“最佳”只能是相對于某一種特定要求下得出的較為合理的選擇而已。第二節路由選擇4.2.1理想的路由算法45第二節路由選擇4.2.2最短通路路由選擇

例：尋找從源節點A到網絡中其他各節點的最短通路。令D(ν)為源節點(節點A)到節點ν的距離；令N表示網絡節點的集合，初始時令N＝{A}；令l(i，j)為節點i至節點j之間的距離。算法：(1)初始化D(ν)=(A,ν)若節點ν與節點A直接相連∞若節點ν與節點A不直接相連(2)尋找一個不在N中的節點ω，其D(ω)值為最小，把ω加入到N中，然后對所有不在N中的節點，用D(ν)和[D(ω)+λ(ω，ν)]中的較小的值去更新原有的D(ν)值，即：

D(ν)←min[D(ν)，D(ω)+λ(ω，ν)]

(3)重復步驟(2)，直到所有的網絡節點都在N中為止。

ECFABD1211223355圖4-6求最短通路算法的網絡舉例

第二節路由選擇4.2.2最短通路路由選擇ECFAB46第二節路由選擇ECFABD1211223355圖4-6求最短通路算法的網絡舉例

步驟ND(B)D(C)D(D)D(E)D(F)初始化{A}251∞∞1{A,D}24①2∞2{A,D,E}231②43{A,B,D,E}②31244{A,B,C,D,E}2③1245{A,B,C,D,E,F}2312④第二節路由選擇ECFABD1211223355圖4-647第二節路由選擇4.2.3路由選擇的不同策略

1.非自適應路由選擇——簡單、開銷小(1)洪泛法(flooding)策略：當某個網絡節點從某條輸入線路收到一個不是發給它的分組時，就向所有與此節點相連的其它鏈路轉發出去。優點：①算法簡單，幾乎不需要什么計算；②可以在最短的時間內接收方收到信息；③方便實現廣播通信和多址通信，具有良好的健壯性，廣泛應用于軍事網中。缺點：①造成分組無休止的傳輸；②使接收方收到多個重復的分組；③網絡中分組數目迅速增長，結果導致網絡出現擁塞現象。改進：采用計數器或登記表法控制網絡中分組數目的增長。第二節路由選擇4.2.3路由選擇的不同策略48第二節路由選擇(2)有選擇的洪泛法策略：僅在滿足某些事先確定的條件的鏈路上轉發分組。好處：分組不會向不希望去的方向轉發。(3)固定路由法策略：在每個節點上保存一張由此節點到網絡中其他節點的固定路由表（由網絡設計人員或管理人員根據網絡拓撲結構、流量分布和其他因素編制的，并且在此后的一段相當時間保持固定不變），表中規定一條或多條輸出線。適用：當網絡拓撲固定不變并且通信量也相對穩定時。(4)隨機走動法(randomwalk)策略：當分組到達某個節點時就隨機地選擇應當走哪條鏈路作為轉發的路由，因此又稱為隨機徘徊。適用：在非自適應的路由策略中，若可能發生節點或鏈路的故障，那么隨機走動法巳被證明是非常有效的，它使得路由算法具有較好的健壯性。第二節路由選擇(2)有選擇的洪泛法49第二節路由選擇(5)分散通信量法(trafficbifurcation)或查表選擇路由(directoryrouting)策略：事先在每個節點的內存中設置一個路由表，路由表中給出幾個可供采用的輸出鏈路，并且對每條鏈路賦予一個概率；當一個分組到達該節點時，此節點即產生一個從0.00到0.99的隨機數，然后按此隨機數的大小，查表找出相應的輸出鏈路。HBACIEJKDGFL（a）目的節點最佳選擇次佳選擇最差選擇輸出線概率輸出線概率輸出線概率BA0.46H0.31I0.23CA0.38I0.34H0.28DH0.50A0.25I0.25EA0.40I0.40H0.20FA0.37H0.33I0.30GH0.46A0.31K0.23HH0.63K0.21A0.16II0.65A0.22H0.13KK0.67H0.22A0.11LK0.42H0.40A0.18AA0.63I0.21H0.16第二節路由選擇(5)分散通信量法(trafficbi50第二節路由選擇2．自適應路由選擇當網絡拓撲發生變化時及網絡某個節點或鏈路發生故障時，在網絡的某個局部范圍做出調整路由的決定。(1)孤立的路由選擇策略策略：只根據本節點的狀態來選擇路由，而不和其它節點交換狀態信息。“熱土豆”算法：當收到一個分組時，不管其目的地址如何，把剛收到的分組以最快速度發往各鏈路中等待隊列長度最短的等待隊列中排隊等候發送。缺點：不準確，有時隊列最短的方向井非正確的轉發路由。改進：令隊列長度為Q，在每個隊列增加一個對于某一目的地址的偏移數B，取Q+B值為最小的隊列作為轉發方向。例如：對應于F，E，D和C的B值若分別為0，6，5和8．則算出相應的Q十B值分別為5，7，9和10，因此應把收到的分組送到發往F的隊列中。

至C至F從A來節點J至D至E第二節路由選擇2．自適應路由選擇至C至F從A來節點J至51第二節路由選擇(2)分布式路由選擇策略——是目前應用最廣泛的路由算法特點：適應性較好，每個節點周期性地從相鄰的節點獲得網絡狀態信息，同時也將本節點做出的決定周期性地通知周圍的各節點，以使這些節點不斷地根據網絡新的狀態更新其路由選擇決定。例：ARPANET使用算法是在每一個節點保持兩個向量，即：dil

·Di=··

dinsil

·Si=··

sin

Di——節點i的時延向量；dij——節點i至節點j的最小時延當前估值(dij=0)；n——網絡中的節點數；Si——節點i的后繼節點向量；SIJ——后繼節點(節點i到節點j當前最小時延路由中的第二個節點。對于任一節點k每隔128ms與其所有相鄰節點交換時延向量，按以下方法對本節點的時延向量和后繼節點向量進行修改：dki＝[dki+dij-] Ski==i，用這個i使[dki+dij-]為最小。

A——節點k的所有相鄰節點的集合；dki——節點k到節點i的時延的當前估值。

第二節路由選擇(2)分布式路由選擇策略——是目前應用最52第二節路由選擇例：5361241212123355203235330213122013D2D4D3節點1收到3個時延向量

目的節點延遲下一個節點10—222353414563683目的節點延遲下一個節點10—222334414524644更新后的路由表

更新前在節點1的路由表

第二節路由選擇例：5361241212123355253第二節路由選擇(3)集中式路由選擇策略策略：利用網控中心NCC，專門收集各節點定期發來的狀態信息，然后由它根據這些狀態信息及網絡拓撲結構，動態的計算出每個節點現時的路由選擇表，再將新的路由選擇表同時送回各個節點使用。優點：算法能定期按拓撲結構和信息量變化修改各節點的路由選擇表；容易得到精確的路由，消除了分組在網內“兜圈子”及路由“振蕩”的現象；可起到對進入網絡通信量的某種流量控制作用。缺點：在報告狀態-計算-送回路由選擇表的過程中花費了不少時間，因此在系統變化較快的網絡中很難獲得理想的控制效果；NCC的工作量大，因此需要采用速度快、可靠性高的機器；由于采用集中控制，因而NCC工作的可靠性尤為重要，所以應采用若干個級別的NCC協同控制，一旦高一級的NCC出現故障，低一級的NCC馬上接替工作，但這種方法花費較大且仍不能滿足全部要求；網中負載不平衡，靠近NCC的鏈路負擔重，而遠離NCC的鏈路負載較輕。

(4)混合式路由選擇策略第二節路由選擇(3)集中式路由選擇策略54第三節擁塞控制

擁塞：當到達通信子網中某部分的分組量過多時，就會造成網絡性能的下降的現象，稱為擁塞。網絡性能下降的表現：信息報傳輸延遲增加和網絡吞吐量下降。

吞吐量理想的擁塞控制實際的擁塞控制無擁塞控制死鎖擁塞輸入負載圖4-12流量控制所起的作用

4.3.1擁塞產生的原因

出現資源擁塞的條件：

∑對資源的需求＞可用資源解決網絡擁塞的辦法是采用流量控制。擁塞控制的主要功能：(1)防止網絡因過載而引起吞吐量下降和時延增加；(2)避免死鎖；(3)在互相競爭的各用戶之間公平地分配資源。單純的增加資源不一定能解決擁塞問題，甚至可能更壞！第三節擁塞控制擁塞：當到達通信子網中某部分的分組量55第三節擁塞控制4.3.2擁塞控制方法

1．緩沖區預分配法——適用于虛電路通信子網建立虛電路時源節點相鄰節點下一節點目的節點呼叫分組登記路徑選擇出入口表；單工停——等信道：預定一個buffer；雙工停——等信道：預定兩個buffer（每個方向一個)；滑動窗口流水協議：預定數量等于滑動窗口尺寸大小個buffer。傳送分組時源節點相鄰節點下一節點目的節點數據分組buffer滿?NY改走其它路徑優點：可靠。缺點：可能造成浪費。第三節擁塞控制4.3.2擁塞控制方法源節點56第三節擁塞控制2．抑制分組法——可用虛電路或數據報通信子網策略：在出現擁塞前兆時，對分組進行截流。算法實現：每個節點(路由器)都監視其輸出線路利用率μ=

(0，1)

μ可用下列公式更新：μ新=αμ舊+（1-α）f

f反映線路瞬時利用率，取值為0-1之間的常數；α反映了更新速度。各節點為每一條線路定義閥值，當μ大于此值時，則該線路進入“告警”狀態。每新收到分組時路由器要查看其輸出線是否處于“告警”狀態，若是則發送一個抑制分組到源主機，并在抑制分組中指明分組的目的地，并在原分組上加一個標志，表示以后不用再產生抑制分組；發送端主機收到該抑制分組后，將發送速率降低一檔，若繼續發送抑制分組，則發送端繼續降低速率。近期實際數據速率最大數據速率第三節擁塞控制2．抑制分組法——可用虛電路或數據報通信57第三節擁塞控制3．分組丟棄法策略：當緩沖區滿時，將到來的分組丟棄，丟棄分組后，發送端因得不到確認而超時重發。緩沖器分配規則：為每個輸入線分配一個能容納一個分組的緩沖器先把到達的分組接收下來，檢查該分組內有無對前面發送的信息報的應答，如果應答表明前一次發送的信息包已經妥收，那么把此分組丟棄，準備接收下一個分組。限制輸出線隊列長度N+1個節點緩沖區除了分給輸入線(1個)以外，剩余的全分給輸出線(N個)。

分配給輸出緩沖區的方法有平分法最大分配法最小分配法最大最小分配法第三節擁塞控制3．分組丟棄法58第三節擁塞控制4．許可證法策略：限制通信子網內的分組數目，使之不超過某一個固定值從而避免擁塞。實現方法：在通信子網中有固定數目的許可證在網中隨機巡航流動，任何一個分組想進入網絡必須先獲得一個許可證；當分組到達終點時就釋放許可證。許可證的分布原則：盡量減少分組等待許可證的時間。平均分布；——忙、閑不公平所有許可證在網內四處流動；——付出等待時延每個節點上保存少量許可證，其它許可證在網內流動。存在問題：

能防止全局性擁塞，但仍不能完全消除局部擁塞；

需要防止許可證丟失。設網內節點數為N，則許可證數可選為3N，每個節點能擁有的許可證L3為最佳分布。第三節擁塞控制4．許可證法59第三節擁塞控制DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

4.3.3流量控制

流量控制和擁塞控制的區別

擁塞控制:必須保證通信子網能正常傳輸數據，包括流量控制，使全局性問題。

流量控制:根據接收端能承受的數據速率來調節發送端傳輸數據的速率，防止到達接收端的數據速率超過接收端的處理速率，只與發送者與接收者之間的點到點通信量有關。流量控制是按級進行的，大致可以劃分為四種不同級別。沒有擁塞問題不等于沒有流量控制問題！第三節擁塞控制DTEDCEDTEDCE傳輸級入口級到出60第三節擁塞控制1.網段級流量控制——需要解決“存儲——轉發”問題目的：在相鄰兩節點之間維持一個均勻的流量，以避免出現局部緩沖區擁塞和死鎖。根據是對兩節點間的流量還是對其中每條虛電路的流量進行控制可再劃分為：數據鏈路網段級流量控制——適用于虛電路、數據報兩種業務采用信道隊列限制法(即分組丟棄法)進行控制：監視每一個隊列的緩沖區的占用情況并對其定義一個極限(固定的或動態可調的)，當某一隊列中待轉發的分組數超過此極限時即丟棄該分組。特點：能有效的避免吞吐量的降低，但無法解決間接死鎖的問題。虛電路網段級流量控制——適用于虛電路DTEDCEDTEDCE傳輸級入口級到出口級網段級進網級進網級四種不同級別的流量控制

第三節擁塞控制1.網段級流量控制——需要解決“存儲——61第三節擁塞控制信道隊列限制法有以下四種變形：平均分配設N為節點中輸出隊列的總數,Ni為第i個隊列中的分組數,而B為緩沖區的大小(除分配給輸入線的之外），則約束條件為：0≤Ni≤B/N這種固定分配方法，效率低，性能較差。

最長隊列共享設bmax為所允許的最長隊列(此處bmax＞B/N)，則約束條件為：0≤Ni≤bmax以及∑Ni≤B最小分配共享設bmin為保證分配給每一隊列的緩沖區大小(當然bin≤B/N)，則約束條件為：∑Max(0,Ni-bmin)≤B-Nbmin最小分配最長隊列共享合并了前兩種方式，即每—隊列保證有一個最小的緩沖區bmin供使用，同時其最大長度受bmax的限制。第三節擁塞控制信道隊列限制法有以下四種變形：62第三節擁塞控制死鎖：兩個節點之間互相僵持，整個網絡不能傳輸分組，吞吐量為零的情況。1.存儲——轉發死鎖直接存儲——轉發死鎖：互相占用了對方需要的資源而造成的死鎖。間接存儲——轉發死鎖：每個節點都試圖向相臨節點發送分組，但沒有一個節點有空閑緩沖區來接收分組導致產生死鎖。2.重裝死鎖：發生在目的節點，因緩沖區不足無法排序組裝造成。R4R3R1Q3Q2P1Q1P3P2Q4R2主機H節點X節點Y節點Z發往A發往DBACD發往C發往Bbmax(b)AB(a)第三節擁塞控制死鎖：兩個節點之間互相僵持，整個網絡不63第三節擁塞控制信道隊列限制法無法解決間接死鎖的問題！

解決間接存儲——轉發死鎖

采用結構化緩沖池策略或稱為緩沖區的有向圖分配法給每個節點開辟M十1個緩沖區(每個緩沖區存放一個分組)，并從0到M編上號碼。僅當與主機相連的源節點的緩沖區0空閑時分組才能發往源節點的緩沖區0。接著，僅當某個相鄰節點中的緩沖區1空閑時分組才能發往緩沖區1，以后每轉發一次，所到達的緩沖區的編號就增大一個號，012……M最終，分組的最壞結局一定是以下兩種情況之一：·傳到所要到達的目的節點，然后交付給主機；·傳到編號為M的緩沖區，然后被丟棄，因而不再消耗網絡的資源。第三節擁塞控制信道隊列限制法無法解決間接死鎖的問題！64第三節擁塞控制2．源節點到目的節點級的流量控制——需要解決“重裝死鎖”問題目的：防止在輸出節點出現由于目的節點到主機的連接線路過載或是由于主機接收數的速率太低而導致緩沖區擁塞。當需要在目的節點把到達的分組重新裝配成報文時有可能出現重裝死鎖！在ARPANET中使用的源節點到目的節點級的流量控制的方法是：①源節點發送報文時必須先發送一個“請求緩沖空間”的分組；②目的節點收到該分組后，即為此報文保留8個緩沖區并回答一個“分配”分組。③當整個報文的8個分組都收齊并送交主機后，目的節點就發回一個“準備下一報文”的確認分組。④當源節點無報文要發送但仍收到“分配”分組時，須發回“歸還”分組以