計算機網絡第5章課件

第五章.網絡層5.1 網絡層概述5.2 路由算法5.2.1 最優(yōu)化原則5.2.2 最短路徑路由算法5.2.3 洪泛算法5.2.5 距離向量路由算法5.2.6 鏈路狀態(tài)路由算法5.2.7 分層路由第五章.網絡層5.3 擁塞控制算法5.3.1 擁塞控制的基本原理5.3.2 擁塞控制算法5.5 INTERNET網絡層協(xié)議

5.5.1IP協(xié)議

5.5.2Internet控制協(xié)議

回顧CSMA以太網網絡設備。。。5.1 網絡層概述ISO定義網絡層為一個網絡連接的兩個傳送實體間交換網絡服務數據單元提供功能和規(guī)程的方法，它使傳送實體獨立于路由選擇和交換的方式。網絡層是處理端到端傳輸的最低層。網絡層要解決的關鍵問題是了解通信子網的拓撲結構，選擇路由。LAN與WAN中網絡層功能上的差別●LAN中的網絡功能有限○在LAN中，使用廣播信道，相鄰節(jié)點與源-目標節(jié)點的通信沒有區(qū)別?！鹪贚AN中，將流量控制功能,差錯控制功能和網絡互聯(lián)等功能一般放入DL層，所以網絡層功能沒有必要或很弱?！馱AN中的網絡功能強大○WAN使用點-點信道,單獨設立一層解決END-END數據傳輸問題，所以網絡層功能強大。網絡層的地位位于數據鏈路層和傳輸層之間，使用數據鏈路層提供的服務，為傳輸層提供服務；通信子網的最高層；處理端到端傳輸的最低層。網絡層的作用屏蔽各種不同類型網絡之間的差異，實現(xiàn)互連了解通信子網的拓撲結構，選擇路由，實現(xiàn)報文的網絡傳輸5.1 網絡層概述網絡層設計的有關問題為傳輸層提供服務面向連接服務傳統(tǒng)電信的觀點：通信子網應該提供可靠的、面向連接的服務。無連接服務

Internet的觀點：通信子網無論怎么設計都是不可靠的，因此網絡層只需提供無連接服務。無連接服務:主機在傳輸數據之前無需建立連接,主機有數據就交給網絡層,網絡層實體直接發(fā)送出去，每一個分組獨立選擇路由,由上層進行排序和流控。applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Senddata2.ReceivedataConnectionlessService無連接服務理由：●不管如何設計,網絡層所提供的服務都是不可靠的，與其在網絡層和傳輸層做兩遍可靠性的工作，不如在網絡層放棄可靠性的工作，只在傳輸層做差錯控制和流量控制等可靠性工作?！裼脩舻挠嬎銠C已有足夠的能力處理復雜的可靠性的工作，在用戶計算機中安裝復雜的傳輸層的軟件是可以接受的。●將可靠性的工作放在網絡層可能會導致子網所提供的服務昂貴。ConnectionlessServiceConnection-OrientedService面向連接服務通信過程：1、在主機通信之前,雙方應建立起連接2、在建立起的連接上進行數據的傳遞3、傳輸完畢,拆除連接applicationtransportnetworkdatalinkphysicalapplicationtransportnetworkdatalinkphysical1.Initiatecall2.incomingcall3.Acceptcall4.Callconnected5.Dataflowbegins6.ReceivedataConnection-OrientedService面向連接服務理由:1、在網絡層提供面向連接的通信是具備電信背景的集團提出的，子網應該提供可靠的,面向連接的服務。2、用戶對在計算機中裝配復雜的傳輸層軟件可能不感興趣。3、網絡層所提供的服務是面向連接的可靠的服務，減少了用戶主機的復雜性。網絡層的兩種實現(xiàn)方式：數據報和虛電路都屬于分組交換，采用存儲轉發(fā)機制。數據報(datagram)：每個分組被單獨路由，分組帶有全網唯一的地址虛電路(virtualcircuit)：先在源端和目的端之間建立一條虛電路，所有分組沿虛電路按次序存儲轉發(fā)，最后拆除虛電路。在虛電路中，每個分組無須進行路徑選擇。數據報：ImplementationofConnectionlessServiceFigure5-2.Routingwithinadatagramsubnet.虛電路：ImplementationofConnection-OrientedServiceFigure5-3.Routingwithinavirtual-circuitsubnet.labelswitching5.1 網絡層概述網絡層提供的服務虛電路子網與數據報子網的比較路由器內存空間與帶寬的權衡虛電路方式，路由器需要維護虛電路的狀態(tài)信息；數據報方式，每個數據報都攜帶完整的目的/源地址，浪費帶寬連接建立時間與地址查找時間的權衡虛電路需要在建立連接時花費時間數據報則在每次路由時過程復雜服務質量與可靠性的權衡虛電路方式很容易保證服務質量QoS(QualityofService)，適用于實時操作，但比較脆弱。數據報不太容易保證服務質量，但是對于通信線路的故障，適應性很強。

面向連接和無連接服務之爭本質:將可靠性的功能放置于何層的問題●面向連接的服務:放置在網絡層●無連接的服務:放置在傳輸層5.2路由算法Mainissue:Routersthatconstitutethenetworklayerofanetwork,shouldcooperatetofindthebestroutes

betweenallpairsofstations.●路由:按照某種指標(傳輸延遲,所經過的站點數目等)找到一條從源節(jié)點到目標節(jié)點的較好路徑●較好路徑:按照某種指標較小的路徑●路由的時機：○虛電路:在建立虛電路時使用○數據報:每個分組獨立路由5.2路由算法●路由算法：指管理路由表并作出路由選擇的算法。①非自適應算法：不會根據當前測量或者估計的流量和拓撲結構，來調整它們的路由決策，所有的路由選擇是預先在離線情況下計算好的，在網絡啟動的時候被下載到路由器中，所以又稱這種算法是靜態(tài)路由。②自適應算法：隨拓撲結構和流量的變化和而改變它們的路由決策，又稱這種算法是動態(tài)路由。5.2路由算法路由選擇算法的原則:●正確性(correctness):算法必須是正確的和完整的,使分組一站一站接力，正確發(fā)向目標站；完整：目標所有的站地址，在路由表中都能找到相應的表項；沒有處理不了的目標站地址；●簡單性(simplicity):算法在計算機上應簡單；最優(yōu)但復雜的算法，時間上延遲很大，不實用，不應為了獲取路由信息增加很多的通信量；5.2路由算法●穩(wěn)定性(stability)：產生的路由不應該搖擺●公平性(fairness)：對每一個站點都公平●最優(yōu)性(optimality)：某一個指標的最優(yōu)，時間上，費用上等指標，或綜合指標；實際上，獲取最優(yōu)的結果代價較高，可以選擇次優(yōu)的●健壯性(robustness):算法應能適應通信量和網絡拓撲的變化。通信量變化，網絡拓撲的變化算法能很快適應；不向很擁擠的鏈路發(fā)數據，不向斷了的鏈路發(fā)送數據；路由選擇算法的原則:5.2.1最優(yōu)化原則最優(yōu)化原則：已知I到K的最優(yōu)路徑,如果節(jié)點J在這條路徑上,則這條路徑上從J到K的路徑也一定是最優(yōu)路徑證明:如果從J到K還存在一條其它路徑,則也存在一條從I到K的最優(yōu)路徑,與前提矛盾IJK5.2.1最優(yōu)化原則匯集樹(sinktree)●一個節(jié)點的匯集樹指的是:所有其它節(jié)點到此節(jié)點的最優(yōu)路徑形成的樹●路由選擇算法就是為所有路由器找到并使用匯集樹Figure5-6.(a)Asubnet.(b)AsinktreeforrouterB.5.2.2最短路徑路由算法●屬于靜態(tài)路由選擇算法●路由算法的圖形抽象○節(jié)點表示路由器○邊用于表示路由器之間的鏈路○鏈路的代價(linkcost):表示鏈路上的距離、信道帶寬、通信開銷、延遲,隊列平均長度等參數。5.2.2最短路徑路由算法●最優(yōu)的指標:○路由指按照某種指標尋找出從源站點到目標站點的較好路徑?！鹬笜?站數,延遲,開銷,隊列長度等,或者是一些單純指標的加權平均?！鸩捎檬裁礃拥闹笜?表示網絡使用者希望網絡在什么方面表現(xiàn)突出,什么指標網絡使用者比較重視。5.2.2最短路徑路由算法配置最短路由選擇算法的路由器的工作過程●各點通過各種渠道獲得整個網絡拓撲,網絡中所有鏈路代價等信息?！袷褂米疃搪酚伤惴?計算本站點到其它站點的最優(yōu)路徑(匯集樹),得到路由表?！癜凑沾寺酚杀磙D發(fā)分組(datagram方式)或建立VC。獲得網絡拓撲和鏈路代價信息使用此路由表使用最短路由算法得到路由表5.2.2最短路徑路由算法最短路由選擇算法的工作原理:●節(jié)點標記:每一個節(jié)點使用從源節(jié)點出發(fā)經過已知的最優(yōu)路徑到達本節(jié)點的距離,和前序節(jié)點來標注:(2,A) ●臨時節(jié)點(tentativenode):還沒有找到從源節(jié)點到此節(jié)點的最優(yōu)路徑的節(jié)點●永久節(jié)點(permanentnode):已經找到了從源節(jié)點到此節(jié)點的最優(yōu)路徑的節(jié)點5.2.2最短路徑路由算法最短路由選擇算法的工作原理●初始化○除了源節(jié)點外,所有節(jié)點都為臨時節(jié)點○節(jié)點代價除了與源節(jié)點代價相鄰的節(jié)點外,都為INF(infinite)●從所有臨時節(jié)點中找到一個節(jié)點代價最小的臨時節(jié)點,將之變成永久節(jié)點(當前節(jié)點,currentnode)W●對于永久節(jié)點的所有相鄰節(jié)點V,如果D(v)>D(w)+c(w,v),則重新標注此節(jié)點,(D(W)+C(W,V),W)●開始一個新的循環(huán)

5.2.2最短路徑路由算法Figure5-5.ThefirstfivestepsusedincomputingtheshortestpathfromAtoD.Thearrowsindicatetheworkingnode.TestTheshortestpathfromAtoG5.2.3洪泛算法工作原理:路由器從一條線路中收到分組,將此分組向所有其它線路發(fā)送出去屬于靜態(tài)路由選擇算法問題在網絡中將產生大量的重復分組解決辦法:方法1:計數器法,在分組中設置計數器字段,每經過一個路由器,該計數器減1,如果計數器值為0,則拋棄該分組5.2.3洪泛算法選擇性洪泛算法（selectiveflooding）洪泛法的一種改進。將進來的每個包僅發(fā)送到與正確方向接近的線路上。應用情況對路由器和線路的資源過于浪費，實際很少直接采用；具有極好的健壯性，可用于軍事應用；作為衡量標準評價其它路由算法。5.2.4距離矢量路由算法●Basicidea:●動態(tài)路由選擇算法○各路由器維護一張路由表,給出了到每個目的地的已知的最佳距離和路線（表項的兩部分）○各路由器與相鄰路由器交換路由表○根據獲得的路由信息,更新路由表ToNextdelayAZ14…………5.2.4距離矢量路由算法Figure5-9.(a)Asubnet.(b)InputfromA,I,H,K,andthenewroutingtableforJ.5.2.4距離矢量路由算法舉例網絡拓撲以節(jié)點J為例,相鄰節(jié)點A,I,H,KJ測得到A,I,H,K的延遲為8ms,10ms,12ms,6ms從A,I,H,K獲得到它們到G的延遲為18ms,31ms,6ms,31ms因此從J經過A,I,H,K到G的延遲為26ms,41ms,18ms,37ms將到G的路由表項更新為18ms,下一個節(jié)點經過H5.2.4距離矢量路由算法無限計算問題俗話說：“好事不出門，壞事傳千里”。而這里是好消息傳播非?？?，對壞消息卻是反應遲鈍。Figure5-10.Thecount-to-infinityproblem.5.2.4距離矢量路由算法假設A停機：1，首先是B，C告訴它有到A的長度為2的路徑，故為3。2，C注意到它的鄰居B有到A的長度為3的路徑，更新，故為4。3，B和D都收到C的消息：“到A的長度為2的路徑”，故都更新，故為54，通過逐步交換下去，得到余下的記錄歷史。5.2.5鏈路狀態(tài)路由算法鏈路狀態(tài)路由算法（LinkStateRouting）距離向量路由算法的主要問題選擇路由時，沒有考慮線路帶寬；路由收斂速度慢。鏈路狀態(tài)路由算法發(fā)現(xiàn)鄰居結點，并學習它們的網絡地址；路由器啟動后，通過發(fā)送HELLO包發(fā)現(xiàn)鄰居結點；兩個或多個路由器連在一個LAN時,引入人工結點；5.2.5鏈路狀態(tài)路由算法測量到每個鄰居結點的延遲或開銷；一種直接的方法是：發(fā)送一個要對方立即響應的ECHO包，來回時間除以2即為延遲。將所有學習到的內容封裝成一個包；包以發(fā)送方的標識符開頭，后面是序號、年齡和一個鄰居結點列表；列表中對應每個鄰居結點，都有發(fā)送方到它們的延遲或開銷；鏈路狀態(tài)包定期創(chuàng)建或發(fā)生重大事件時創(chuàng)建。組裝一個分組,描述相鄰節(jié)點的情況發(fā)送者名稱;序號;年齡列表:給出它相鄰節(jié)點,和它到相鄰節(jié)點的延遲鏈路狀態(tài)定期創(chuàng)建或發(fā)生重大事件時創(chuàng)建5.2.5鏈路狀態(tài)路由算法將這個包發(fā)送給所有其它路由器；基本思想：洪泛鏈路狀態(tài)包，為控制洪泛，每個包包含一個序號，每次發(fā)送新包時加1。路由器記錄信息對(源路由器，序號)，當一個鏈路狀態(tài)包到達時，若是新的，則分發(fā)；若是重復的，則丟棄；若序號比路由器記錄中的最大序號小，則認為過時而丟棄；改進序號循環(huán)使用會混淆，解決辦法：使用32位序號；路由器崩潰后，序號重置；序號出錯；5.2.5鏈路狀態(tài)路由算法第二、三問題的解決辦法：增加年齡（age）域，每秒鐘年齡減1，為零則丟棄。鏈路狀態(tài)包到達后，延遲一段時間，并與其它已到達的來自同一路由器的鏈路狀態(tài)包比較序號，丟棄重復包，保留新包；鏈路狀態(tài)包需要應答；計算到每個其它路由器的最短路徑。根據Dijkstra算法計算最短路徑；實用協(xié)議OSPFIS-IS5.2.6HierarchicalRouting▲分級的必要性當網絡數目比較多時,路由表的項目就多路由表的掃描,發(fā)布和計算路由代價比較高▲類似于電話網絡5.2.6分層路由●二級網絡將整個網絡分成區(qū)域(region)區(qū)域內部路由器知道到本區(qū)所有其它路由器的路由,不知道其它區(qū)域內部的結構但知道到其它區(qū)域的路由大大減少了路由表中的項目數5.2.6分層路由多級網絡區(qū)域（regions）、簇（clusters）、區(qū)（zones）和組（groups）…一個例子:不分級,1A的路由表要有17表項分兩級,到其它區(qū)域的路由信息被壓縮成了1項,路由表有7表項分級的代價增加了有些路徑的長度習題3.Datagramsubnetsrouteeachpacketasaseparateunit,independentofallothers.Virtual-circuitsubnetsdonothavetodothis,sinceeachdatapacketfollowsapredeterminedroute.Doesthisobservationmeanthatvirtual-circuitsubnetsdonotneedthecapabilitytorouteisolatedpacketsfromanarbitrarysourcetoanarbitrarydestination?Explainyouranswer.習題9.ConsiderthesubnetofFig.5-13(a).Distancevectorroutingisused,andthefollowingvectorshavejustcomeintorouterC:fromB:(5,0,8,12,6,2);fromD:(16,12,6,0,9,10);andfromE:(7,6,3,9,0,4).ThemeasureddelaystoB,D,andE,are6,3,and5,respectively.WhatisC'snewroutingtable?Giveboththeoutgoinglinetouseandtheexpecteddelay.5.3 擁塞控制算法擁塞（congestion）網絡上有太多的包時，性能會下降，這種情況稱為擁塞。擁塞產生的原因多個輸入對應一個輸出；慢速處理器；低帶寬線路。解決辦法針對某個因素的解決方案，只能對提高網絡性能起到一點點好處，甚至可能僅僅是轉移了影響性能的瓶頸；需要全面考慮各個因素。5.3 擁塞控制算法擁塞控制與流量控制的差別擁塞控制（congestioncontrol）需要確保通信子網能夠承載用戶提交的通信量，是一個全局性問題，涉及主機、路由器等很多因素；流量控制（flowcontrol）與點到點的通信量有關，主要解決快速發(fā)送方與慢速接收方的問題，是局部問題，一般都是基于反饋進行控制的。5.3 擁塞控制算法5.3.1 擁塞控制的基本原理根據控制論，擁塞控制方法分為兩類開環(huán)控制通過好的設計來解決問題，避免擁塞發(fā)生；擁塞控制時，不考慮網絡當前狀態(tài)。閉環(huán)控制基于反饋機制；工作過程監(jiān)控系統(tǒng)，發(fā)現(xiàn)何時何地發(fā)生擁塞； 把發(fā)生擁塞的消息傳給能采取動作的站點調整系統(tǒng)操作，解決問題。5.3 擁塞控制算法衡量網絡是否擁塞的參數缺乏緩沖區(qū)造成的丟包率；平均隊列長度；超時重傳的包的數目；平均包延遲；包延遲變化（Jitter）。反饋方法向負載發(fā)生源發(fā)送一個告警包；包結構中保留一個位或域用來表示發(fā)生擁塞，一旦發(fā)生擁塞，路由器將所有的輸出包置位，向鄰居告警；主機或路由器主動地、周期性地發(fā)送探報（probe），查詢是否發(fā)生擁塞。5.3 擁塞控制算法5.3.2 擁塞控制算法擁塞預防策略開環(huán)控制影響擁塞的網絡設計策略5.3 擁塞控制算法流量整形（TrafficShaping）開環(huán)控制基本思想造成擁塞的主要原因是網絡流量通常是突發(fā)性的；強迫包以一種可預測的速率發(fā)送；在ATM網中廣泛使用。5.3 擁塞控制算法漏桶算法（TheLeakyBucketAlgorithm）將用戶發(fā)出的不平滑的數據包流轉變成網絡中平滑的數據包流；可用于固定包長的協(xié)議，如ATM；也可用于可變包長的協(xié)議，如IP，使用字節(jié)計數；無論負載突發(fā)性如何，漏桶算法強迫輸出按平均速率進行，不靈活。5.3 擁塞控制算法令牌桶算法（TheTokenBucketAlgorithm）漏桶算法不夠靈活，因此加入令牌機制；基本思想：漏桶存放令牌，每T秒產生一個令牌，令牌累積到超過漏桶上界時就不再增加。包傳輸之前必須獲得一個令牌，傳輸之后刪除該令牌；5.3 擁塞控制算法漏桶算法與令牌桶算法的區(qū)別流量整形策略不同：漏桶算法不允許空閑主機積累發(fā)送權，以便以后發(fā)送大的突發(fā)數據；令牌桶算法允許，最大為桶的大小。漏桶中存放的是數據包，桶滿了丟棄數據包；令牌桶中存放的是令牌，桶滿了丟棄令牌，不丟棄數據包。5.5網絡互聯(lián)Figure5-42.Acollectionofinterconnectednetworks.5.5.2網絡如何互聯(lián)Figure5-44.(a)TwoEthernetsconnectedbyaswitch.(b)TwoEthernetsconnectedbyrouters.5.6Internet網絡層協(xié)議5.6.1IP協(xié)議5.6.2IP地址5.6.3Internet控制協(xié)議5.6.1IP協(xié)議Version:協(xié)議的版本號； IHL:表明標頭的長度；Typeofservice:服務類型; Totallength:標頭以及數據；Identification:數據報的序列號； DF：分段標志；5.6.1TheIPProtocolMF：最后段標志； Fragmentoffset：分段在數據報的位置；Timetolive：用來計算包的存活期的計數器；Protocol：協(xié)議； Headerchecksum：用于校驗包頭；5.6.1TheIPProtocol5.6.2IPAddressesIP地址（IPAddress）地址組成：網絡號+主機號；地址分類:1.掌握給出一個IP地址，能指出是那類地址。2.構成。3.每類地址最大網絡數和最大主機數。5.6.2IP地址▲點分十進制表示法每字節(jié)用1個0-255的整數表示字節(jié)之間使用點隔離223.1.1.1=11011111000000010000000100000001223111DF010101特殊的IP地址Figure5-56.SpecialIPaddresses.一般約定：(0表示所有比特位全為0，-1表示所有比特位全為1)網絡號為0---本網絡主機號為0---本主機主機號為-1---廣播地址，網絡中的所有主機子網子網（Subnets）分而治之的思想：為了便于管理和使用，可以將網絡分成若干供內部使用的部分，稱為子網。對外界，該網絡還是一個單獨的網絡。子網●

子網掩碼子網的位數由各個單位確定，如何在IP地址中區(qū)分哪些是網絡號，哪些主機號。Subnetmask:32Bits，1和0組成，1表示IP地址所在的位為網絡號或子網號，0表示IP地址所在的位為主機號。上例：將16位主機號分成6位子網號，10位主機號。(255.255.252/22)不劃分子網的網絡的子網掩碼：A：255.0.0.0B：255.255.0.0C：255.255.255.0子網●未劃分子網路由器對分組的轉發(fā)到本網絡的主機，路由器直接發(fā)送。到其它網絡的IP分組，路由器知道去該網絡的下一跳IP地址，將整個網絡壓縮成一條記錄(層次路由)。如果一個分組IP地址，路由器不知道關于它的信息，將這個分組發(fā)向默認表項的下一跳。網絡號主機號下一跳(interface)本網絡主機直接其它網絡任何yDefaultz子網劃分子網路由器對分組的轉發(fā)到本子網絡的主機，路由器直接發(fā)送到本網絡的其它子網的IP分組，路由器知道去該網絡的下一跳IP地址，將整個子網壓縮成一條記錄(層次路由)到其它網絡的IP分組，路由器知道去該網絡的下一跳IP地址，將整個網絡壓縮成一條記錄(層次路由)網絡號子網號主機號下一跳(interface)本網絡本子網某主機直接本網絡其它子網任何Y其它網絡任何任何ZDefaultwDESMaskNextinterface150.1.1.0255.255.255.0-150.1.1.4150.1.2.0255.255.255.0-150.1.2.9150.1.3.0255.255.255.0-150.1.3.27DESMaskNext150.1.0.0255.255.0.0123.1.1.3……150.1.1.1150.1.1.2150.1.1.3150.1.1.4150.1.2.9150.1.2.2150.1.2.1150.1.3.2150.1.3.1150.1.3.27123.1.1.3123.1.1.4ExampleNAT—NetworkAddressTranslationReason:IPaddressesarescarce.Solution:(1)IPv6(2)DHCP(3)NATThebasicidea:assigneachcompanyasingleIPaddressforInternettraffic.Withinthecompany,everycomputergetsauniqueIPaddress,whichisusedforroutingintramuraltraffic.However,whenapacketexitsthecompanyandgoestotheISP,anaddresstranslationtakesplace.NAT10.0.0.0–10.255.255.255/8(16,777,216hosts)172.16.0.0–172.31.255.255/12(1,048,576hosts)192.168.0.0–192.168.255.255/16(65,536hosts)ThreerangesofIPaddresseshavebeendeclaredasprivate：NATExample:Whenaconnectionissetupfromaddress10.0.0.1,portX,theroutersendsitoffusingsourceaddress198.60.42.12(it’sISP-suppliedaddress)onportY,andregistersthemappingX<－>Y.WhenareplycomesinforportY,itissentbackto10.0.0.1onportX.5.6.3Internet控制協(xié)議ICMP(InternetControlMessageProtocol)ICMP和IP的關系ICMP使用IP協(xié)議傳輸ICMP報文，ICMP報文被封裝在IP數據報中；ICMP協(xié)議和IP協(xié)議同處于一個互聯(lián)網層ICMP報文的格式5.6.3Internet控制協(xié)議ARP(AddressResolutionProtocol)ARP的必要性DL層是不理解IP地址的，它只能夠按照MAC地址來發(fā)送和接收幀IP層將IP分組交給DL層，同時還應該給出該目標IP地址所對應的MAC地址，只有這樣DL層才能夠順利地將IP分組封裝成幀傳送出去如何進行IP地址和MAC地址的翻譯—ARP5.6.3Internet控制協(xié)議ARP(AddressResolutionProtocol)ARP的目的：