IP路由第2頁內容概述路由的基本概念路由選擇算法靜態路由選擇算法動態路由選擇算法路由選擇算法介紹第3頁第4頁第5頁第6頁/Software/Cichlid/gallery/cheap_callouts.html第7頁第8頁網絡層的主要功能是將分組從源端機器經選定的路由送到目的端機器。在絕大多數網絡當中分組需要經過多次的轉發才能到達目的端機器。路由選擇算法和它們所使用的數據結構是網絡層設計當中的一個關鍵問題。第9頁發送端的處理過程： 當主機A要和主機B進行通信時，首先判斷主機B是否和它位于同一子網。方法：把兩個主機的IP地址分別與它(主機A)的 子網掩碼進行“位與”操作，把分別得到的網絡ID進行比較，如果結果相同，則表明位于同一子網，否則位于不同的子網。示例：第10頁主機A的IP地址與子網掩碼進行“位與”操作主機B的IP地址與子網掩碼進行“位與”操作結果相同，可見，兩個主機位于同一子網中示例1：第11頁主機A的IP地址與子網掩碼進行“位與”操作主機B的IP地址與子網掩碼進行“位與”操作結果不同，可見，兩個主機不在同一子網中示例2：第12頁

如果在同一子網，則源主機用ARP確定目標主機的硬件地址后直接發送數據幀到目標主機。(直接路由，無需路由器)

如果不在同一子網，則源主機用ARP確定默認網關(路由器)的硬件地址后，把數據幀轉發給默認網關(間接路由)。 至此源主機的發送就結束了。第13頁

剩下的任務是間接路由情形下： 路由器把收到的數據幀解開，利用IP包中的地址選擇如何進一步處理， 如果目的主機在路由器所處的另一個子網，則變成直接路由的情況，封裝IP包，直接發送。 如果目的主機不在與路由器直接相連的子網，則需要選擇轉發到下一個路由器。通過進行轉發，最終到達與目的主機在同一物理網絡的路由，從而傳送到目標主機（最終的一個步驟總是直接路由）。 問題：路由器如何選擇轉發的下一個路由器?第14頁路由器為了把收到的數據傳送到目標主機，需要知道那些主機是可達的以及如何達到。這些網絡拓撲信息由路由器中的路由表保存，路由器通過查找路由表，選擇轉發數據的路徑。路由表第15頁下一跳(Next-Hop)路由表一個簡化：是只保存目標網絡的路由信息，因為一旦找到目標主機所在的目標網絡，就可以直接在物理層傳輸數據幀了。進一步的簡化：是不必在每個路由器中都保存一個到目標網絡的完整路徑，而只保存從本路由器到目標網絡的路徑的下一步路由器地址，這樣就可以一步一步達到目標網絡了。這種路由方式稱為下一跳路由。其路由表的內容是這樣的：第16頁下一跳路由表示例表的第一列指明目標網絡，第二列指明為到達該目標網絡下一步應轉發給哪一個路由器。第17頁說明：路由表中通過指定網絡號而非具體的主機，對主機進行屏蔽。使主機通信依賴于路由器。更主要的是，通過只指定網絡，極大地減少了路由表的大小，只有網絡數目的增長才會引起路由表的擴大，而主機的增加對路由表沒有影響。路由表中列出的接口地址均應與路由器在同一物理網絡，可直接轉發物理幀的。還應該指定一個默認路由，以確定當網絡號均不匹配時，如何轉發。（當主機只能訪問一個路由器時尤其應設置）也可以為了某些目的為某個主機指定路由。第18頁

Destination

Gateway

Flags

Ref

Use

Interface

UH 0 26492lo055 UGH 0 0 emd02 3 U 3 58503le0default29 UG 0 43454emd0第19頁Flags:U:可用G:網關H:主機D:ICMP重定向報文創建M:ICMP重定向報文修改Refent：正在使用路由的活動進程個數Use：通過該路由的分組數第20頁問題：一旦路由表給定，所有的流量均將沿指定的同一路徑轉發，即使有多個可選路徑。只有最后與目標網絡相連的路由器才和目標主機直接通信，前面的路由器完全不知道目標主機的狀態，如果目標主機已經不存在，那么也只有等數據發到最后一個路由器時才知道。第21頁下一跳路由的算法：執行：拆開IP數據報，從中抽取目的IP地址：D，通過“位與”運算求出目的地址的網絡ID：NifN和某個與路由器直接相連的網絡匹配，則直接轉發到該網絡中的相應主機（這需要執行：從IP地址D解析出目的主機的物理地址，封裝IP數據報為幀，幀頭包含目的主機的物理地址，發送幀）。elseif路由器的路由表中包含有為該主機D指定的路由，則按路由表中所指定的發送到下一跳（這需要執行：解析所指定的下一跳路由的物理地址，封裝IP數據報為幀，幀頭包含下一跳路由的物理地址，發送幀）。elseif路由器的路由表中包含有到達該網絡N的路由，則按路由表中所指定的發送到下一跳（這需要執行：同上）。elseif路由器的路由表中包含有默認路由，則發送到路由表中所指定的默認路由（這需要執行：解析所指定的默認路由的物理地址，封裝IP數據報為幀，幀頭包含默認路由的物理地址，發送幀）。else發回路由出錯消息。

第22頁一個問題：上述執行中均要解析下一跳的物理地址封裝成幀，而不用IP地址，十分繁瑣，為什么不在路由中直接指定下一跳的物理地址呢？原因：層次分明，物理地址在低層使用，如果又在網絡層使用，則層次不清。分層體系的一個要點就是下層應該對上層是透明的。IP地址易于管理和維護，當路由表更新時，查看IP地址比查看物理地址更易明白發生了什么問題。第23頁子網路由當要與子網中的主機進行通信時，那么只在路由表中指定網絡ID還不夠，因為一個網絡ID中可能有多個物理子網，此時，還必須指定子網掩碼：當選擇路由時，就需要把目的主機的IP地址與子網掩碼進行“位與”，以確定目標主機所在的網絡地址，從而選擇下一跳地址。第24頁IP是提供的是無連接的服務，源主機一旦把數據報發出之后，各個中間路由器根據數據報中的信息自主操作，與源主機無關，如果所有中間傳輸以及目的接收都不出問題，則此機制能正常工作。但如果出現問題，如路徑擁塞不能正常轉發數據報或目的主機宕機等，如何通知源主機此類情況以便其采取相應措施。(ICMP消息)路由表中包含一些什么內容最好？如何建立路由表？(路由協議)第25頁主機A主機Beth0eth1eth2eth2/24eth1/24eth2/24eth1/24eth0/24接口下一跳路由網絡地址路由器1eth2/24eth0/24eth2/24eth1/24eth0/24接口下一跳路由網絡地址路由器2eth0eth1eth2第26頁IP路由協議第27頁兩個問題：路由表中應該包含一些什么信息？路由器如何獲得這些信息？第28頁11

Iproute

IprouteCisco路由器：11add-iproute=add-iproute=3com路由器：11

Iproute

Iprouteadd-iproute=add-iproute=11第29頁路由表第30頁路由表輸出的解釋第31頁理想路由算法特點算法必須是正確的和完整的。算法在計算上應簡單。算法應能適應通信量和網絡拓撲的變化算法應具有穩定性。

路由算法應收斂于一個可以接受的解，路由不應不停的變化。算法應是公平的。算法應是最佳的。

只能相對于某一種特定要求下得出的較為合理的選擇。

第32頁第33頁關于“最佳路由”不存在一種絕對的最佳路由算法。所謂“最佳”只能是相對于某一種特定要求下得出的較為合理的選擇而已。實際的路由選擇算法，應盡可能接近于理想的算法。路由選擇是個非常復雜的問題它是網絡中的所有結點共同協調工作的結果。路由選擇的環境往往是不斷變化的，而這種變化有時無法事先知道。

第34頁從路由算法的自適應性考慮靜態路由選擇策略——即非自適應路由選擇，其特點是簡單和開銷較小，但不能及時適應網絡狀態的變化。動態路由選擇策略——即自適應路由選擇，其特點是能較好地適應網絡狀態的變化，但實現起來較為復雜，開銷也比較大。第35頁ExampleofStaticRouting

directdefault

00NetMaskNexthopNetwork/16H1H2H3H4TotherestoftheInternetRouteraddress00RouterR1第36頁路由表的創建包含兩個方面—初始化路由表和更新路由表初始化路由表取決于操作系統，可能有如下幾種情況：路由器在啟動時從二級存儲器中讀取一個初始路由表，并駐留在主存中。初始路由表為空，在啟動后通過執行外部命令來填充。從它所連接的本地網絡的地址集推出一個初始的路由，并與相鄰的路由器聯系以獲得更多的路由信息。初始的路由表建立之后，就需要根據網絡路由的變化進行更新。對于較小的、變化較慢的網絡可以由管理員手工來做；而對于大的、變化較復雜的網絡則很難能由手工完成迅速的更新，就需要一些自動的方法第37頁下一跳路由表的問題：由于下一跳路由表中只包含了到下一個網絡（對于中間路由器而言，下一個網絡不是目的網絡）的路徑，如果所有網絡都是互通的，那么可以斷定的是：除非進入了某個循環路徑，數據最終總能到達目的網絡，但問題在于：所走的路徑是否是到達目的網絡的最短路徑？例如：第38頁分層次的路由選擇協議因特網采用分層次的路由選擇協議。因特網的規模非常大。如果讓所有的路由器知道所有的網絡應怎樣到達，則這種路由表將非常大，處理起來也太花時間。而所有這些路由器之間交換路由信息所需的帶寬就會使因特網的通信鏈路飽和。許多單位不愿意外界了解自己單位網絡的布局細節和本部門所采用的路由選擇協議（這屬于本部門內部的事情），但同時還希望連接到因特網上。第39頁自治系統AS

(AutonomousSystem)自治系統AS的定義：在單一的技術管理下的一組路由器，而這些路由器使用一種AS內部的路由選擇協議和共同的度量以確定分組在該AS內的路由，同時還使用一種AS之間的路由選擇協議用以確定分組在AS之間的路由。現在對自治系統AS的定義是強調下面的事實：盡管一個AS使用了多種內部路由選擇協議和度量，但重要的是一個AS對其他AS表現出的是一個單一的和一致的路由選擇策略。第40頁通過把網絡中的路由器分為兩類：一類路由器成為核心路由器，其中保有所有網絡路徑完整、可靠、一致的信息，這一類的路由器數目較少，由專門的組織負責維護；另一類是非核心的路由器，自治地維護本地路徑。示意圖：第41頁因特網有兩大類路由選擇協議內部網關協議

IGP(InteriorGatewayProtocol)即在一個自治系統內部使用的路由選擇協議。目前這類路由選擇協議使用得最多，如RIP和OSPF協議。外部網關協議EGP(ExternalGatewayProtocol)若源站和目的站處在不同的自治系統中，當數據報傳到一個自治系統的邊界時，就需要使用一種協議將路由選擇信息傳遞到另一個自治系統中。這樣的協議就是外部網關協議EGP。在外部網關協議中目前使用最多的是BGP-4。第42頁自治系統和

內部網關協議、外部網關協議

用內部網關協議（例如，RIP）自治系統B自治系統A用外部網關協議（例如，BGP-4）R1R2

用內部網關協議（例如，OSPF）自治系統之間的路由選擇也叫做域間路由選擇(interdomainrouting)，在自治系統內部的路由選擇叫做域內路由選擇(intradomainrouting)第43頁這里要指出兩點因特網的早期RFC文檔中未使用“路由器”而是使用“網關”這一名詞。但是在新的RFC文檔中又使用了“路由器”這一名詞。應當把這兩個屬于當作同義詞。IGP和EGP是協議類別的名稱。但RFC在使用EGP這個名詞時出現了一點混亂，因為最早的一個外部網關協議的協議名字正好也是EGP。因此在遇到名詞EGP時，應弄清它是指舊的協議EGP還是指外部網關協議EGP這個類別。第44頁因特網的路由選擇協議內部網關協議IGP：具體的協議有多種，如RIP和OSPF等。外部網關協議EGP：目前使用的協議就是BGP。第45頁abbaaC ABdA.cA.aC.bB.acbcborder(exteriorgateway)routers第46頁Intra-ASandInter-ASroutingHosth2abbaaCABdcA.aA.cC.bB.acbHosth1Intra-ASroutingwithinASAInter-ASroutingbetweenAandBIntra-ASroutingwithinASB第47頁

InternetBackbonesinNorthAmerica第48頁第49頁第50頁在核心路由系統中，通過把所有可能路徑的完備信息在核心路由器之間不斷傳播、更新而使核心路由系統能保有完整、一致、可靠的路由信息。其中的一個關鍵是路由傳播和更新的算法。兩種路由協議的區別：網絡規模大小的不同域和域之間的路徑度量不同考慮策略不同第51頁內部網關協議RIP

(RoutingInformationProtocol)1.工作原理路由信息協議RIP是內部網關協議IGP中最先得到廣泛使用的協議。RIP是一種分布式的基于距離向量的路由選擇協議。RIP協議要求網絡中的每一個路由器都要維護從它自己到其他每一個目的網絡的距離記錄。

第52頁“距離”的定義從一路由器到直接連接的網絡的距離定義為1。從一個路由器到非直接連接的網絡的距離定義為所經過的路由器數加1。RIP協議中的“距離”也稱為“跳數”(hopcount)，因為每經過一個路由器，跳數就加1。這里的“距離”實際上指的是“最短距離”，第53頁“距離”的定義RIP認為一個好的路由就是它通過的路由器的數目少，即“距離短”。RIP允許一條路徑最多只能包含15個路由器。“距離”的最大值為16時即相當于不可達。可見RIP

只適用于小型互聯網。RIP不能在兩個網絡之間同時使用多條路由。RIP選擇一個具有最少路由器的路由（即最短路由），哪怕還存在另一條高速(低時延)但路由器較多的路由。第54頁RIP協議的三個要點僅和相鄰路由器交換信息。交換的信息是當前本路由器所知道的全部信息，即自己的路由表。按固定的時間間隔交換路由信息，例如，每隔30秒。第55頁路由信息協議（RouteInformationProtocol）v1首個RIP（RIP1RFC1058，1988）標準發布于1988年六月。RIP把網絡中的節點分為活動的和被動的。活動節點可以廣播路由信息，也可以接收、更新信息，被動節點只能接收廣播并更新自己的路由信息。只有路由器可以作為活動節點，而主機只能作為被動節點。活動節點每隔30秒廣播一輪其當前路由表中的路由信息。RIP使用“跳數”來計算到目的網絡的距離。通過一個網絡為一跳，可以人為地把某些慢速網絡設置為多跳數，以更精確。RIP規定最大跳數為15，若跳數為16則表示不可達。RIP路由信息中只包含兩項：目的網絡和達到目的網絡的跳數。第56頁路由信息協議僅和相鄰路由器交換信息交換信息是當前本路由器所知道全部信息按固定時間間隔交換信息采用距離向量算法第57頁距離向量算法路由表格式第58頁距離向量算法收到相鄰路由器X的RIP報文1。修改此報文中的所有項目：將“下一跳”字段的地址都改為X，并且將所有的“距離”字段＋12。對修改后的RIP報文的每一個項目，重復以下步驟：若項目當中的目的網絡不在路由表中，則添加該項目到路由表中否則：若下一跳字段給出的路由器地址是相同的，則將收到項目替換原路由表中的項目否則：若收到項目中的距離小于路由器表當中的距離，則進行更新否則：什么也不做若超過3分鐘沒有收到相鄰路由器的更新路由表，則將相鄰路由距離置16返回第59頁NET1ABCNET2NET3NET4NetHopNextnet31-net41-NetHopNextnet11-net21-NetHopNextnet21-net31-第60頁NET1ABCNET2NET3NET4NetHopNextnet31-net41-net22BNetHopNextnet11-net21-net32BNetHopNextnet21-net31-net12Anet42C第61頁NET1ABCNET2NET3NET4NetHopNextnet31-net41-net22Bnet13BNetHopNextnet11-net21-net32Bnet43BNetHopNextnet21-net31-net12Anet42C第62頁RIP提出了一些規則來提供性能和可靠性。例如：一旦路由器從別的路由器學習到一個路由，那么它將一致保留直到學到了另一個更好的。（最優，又避免振蕩）被動節點在學到一個路由后要立即開始計時，在180秒之內，如果一直沒有再次得到關于此路由的廣播，則放棄此路由。（寧缺勿錯）RIP中的問題：慢收斂問題問題的描述：第63頁NET1ABNET2NetHopNextnet11-net21-net32BNetHopNextnet21-net31-net12ANET3第64頁NET1ABNET2NetHopNextnet116-net21-net32BNetHopNextnet21-net31-net12ANET3第65頁NET1ABNET2NetHopNextnet13Bnet21-net32BNetHopNextnet21-net31-net12ANET3第66頁NET1ABNET2NetHopNextnet13Bnet21-net32BNetHopNextnet21-net31-net14ANET3………………第67頁NET1ABNET2NetHopNextnet116Bnet21-net32BNetHopNextnet21-net31-net116ANET3好消息傳播快，壞消息傳播慢－需要較長時間才能將網絡故障信息傳播到網絡當中所有路由器第68頁解決方案:水平切割路由器計錄每個接口收到的路由信息，禁止把一條路由信息從收到它的接口再廣播出去。如上例，可以解決問題，但有些拓撲結構也不行。保持一旦某個路由器在收到一個網絡變為不可達的消息后，它將在一個規定時間區間內保持此消息而忽略其他路由器發給它的其他消息（壞消息優先，針對網上：好消息傳的快，壞消息傳的慢），這樣就確保壞消息能先傳播出去，而不會在傳出去之前就被更新。但會造成一個較長的保持時間，特別對廣域網。即使此時有好消息，也不可傳播。觸發更新一旦收到消息報告網絡不可達，就立即廣播，不必等下一個廣播周期到。同時，在廣播中保留此目的網絡，只是加一個很大的代價值。但在某些結構中，如多個路由器同時連在某個網絡上，此時會造成突然的流量激增。第69頁RIP報文格式:RIP報文封裝在用戶數據報(UDP)中，默認UDP端口號為520第70頁不同的命令字段值指定不同的操作:路由器和主機可以通過發送請求命令來請求另外的路由器發送路由信息。通常，路由器周期性發送非請求的路由信息。每個報文最多攜帶25個路由。第71頁RIP選路中的距離為hop值，有以下問題：hop值刻畫距離并不能十分精確，每一跳并不可能精確相同不能動態表現某個網絡的通信量負載不支持子網RIP2（RFC1388，1993）對RIP1的擴展，協議本身并無變化，只是利用RIP報文格式中的為零部分來傳遞更多的信息。其中通過傳遞子網掩碼擴展了對子網路由的支持。格式見下頁圖：第72頁第73頁內部網關協議OSPF

(OpenShortestPathFirst)1.OSPF協議的基本特點“開放”表明OSPF協議不是受某一家廠商控制，而是公開發表的。“最短路徑優先”是因為使用了Dijkstra

提出的最短路徑算法SPFOSPF只是一個協議的名字，它并不表示其他的路由選擇協議不是“最短路徑優先”。是分布式的鏈路狀態協議。

第74頁三個要點向本自治系統中所有路由器發送信息，這里使用的方法是洪泛法。發送的信息就是與本路由器相鄰的所有路由器的鏈路狀態，但這只是路由器所知道的部分信息。“鏈路狀態”就是說明本路由器都和哪些路由器相鄰，以及該鏈路的“度量”(metric)。

只有當鏈路狀態發生變化時，路由器才用洪泛法向所有路由器發送此信息。

第75頁鏈路狀態數據庫

(link-statedatabase)

由于各路由器之間頻繁地交換鏈路狀態信息，因此所有的路由器最終都能建立一個鏈路狀態數據庫。這個數據庫實際上就是全網的拓撲結構圖，它在全網范圍內是一致的（這稱為鏈路狀態數據庫的同步）。OSPF的鏈路狀態數據庫能較快地進行更新，使各個路由器能及時更新其路由表。OSPF的更新過程收斂得快是其重要優點。第76頁OSPF的區域(area)為了使OSPF能夠用于規模很大的網絡，OSPF將一個自治系統再劃分為若干個更小的范圍，叫作區域。每一個區域都有一個32位的區域標識符（用點分十進制表示）。區域也不能太大，在一個區域內的路由器最好不超過200個。第77頁自治系統ASOSPF劃分為兩種不同的區域區域區域主干區域至其他自治系統R9R7R6R5R4R3R2R1網

8網

6網

3網

2網

1網

7區域網4網

5R8第78頁劃分區域劃分區域的好處就是將利用洪泛法交換鏈路狀態信息的范圍局限于每一個區域而不是整個的自治系統，這就減少了整個網絡上的通信量。在一個區域內部的路由器只知道本區域的完整網絡拓撲，而不知道其他區域的網絡拓撲的情況。OSPF使用層次結構的區域劃分。在上層的區域叫作主干區域(backbonearea)。主干區域的標識符規定為。主干區域的作用是用來連通其他在下層的區域。

第79頁自治系統AS主干路由器區域區域主干區域至其他自治系統R9R7R6R5R4R3R2R1網

8網

6網

3網

2網

1網

7區域網4網

5R8第80頁自治系統AS區域邊界路由器區域區域主干區域至其他自治系統R9R7R6R5R4R3R2R1網

8網

6網

3網

2網

1網

7區域網4網

5R8第81頁OSPF直接用IP數據報傳送OSPF不用UDP而是直接用IP

數據報傳送。OSPF構成的數據報很短。這樣做可減少路由信息的通信量。數據報很短的另一好處是可以不必將長的數據報分片傳送。分片傳送的數據報只要丟失一個，就無法組裝成原來的數據報，而整個數據報就必須重傳。第82頁OSPF的其他特點OSPF對不同的鏈路可根據IP分組的不同服務類型TOS而設置成不同的代價。因此，OSPF對于不同類型的業務可計算出不同的路由。如果到同一個目的網絡有多條相同代價的路徑，那么可以將通信量分配給這幾條路徑。這叫作多路徑間的負載平衡。所有在OSPF路由器之間交換的分組都具有鑒別的功能。支持可變長度的子網劃分和無分類編址CIDR。每一個鏈路狀態都帶上一個32位的序號，序號越大狀態就越新。第83頁IP數據報OSPF分組IP數據報首部OSPF分組OSPF分組首部類型1至類型5的OSPF分組24字節081631版本路由器標識符類型分組長度檢驗和鑒別位鑒別區域標識符鑒別類型第84頁OSPF的五種分組類型類型1，問候(Hello)分組。類型2，數據庫描述(DatabaseDescription)分組。類型3，鏈路狀態請求(LinkStateRequest)分組。類型4，鏈路狀態更新(LinkStateUpdate)分組，用洪泛法對全網更新鏈路狀態。類型5，