1、第二章第二章 下一代互聯網根底下一代互聯網根底XXX北京交通大學北京交通大學下一代互聯網互聯設備國家工程實驗室下一代互聯網互聯設備國家工程實驗室本章提綱本章提綱v互聯網的體系構造互聯網的體系構造vIP路由中的根本概念路由中的根本概念v路由轉發原理路由轉發原理v路由選擇算法路由選擇算法v路由器硬件體系構造路由器硬件體系構造v現有信息網絡根本上都采用了分層的體系構造，即現有信息網絡根本上都采用了分層的體系構造，即將其協議體系劃分為假設干個層次，每個層次完成將其協議體系劃分為假設干個層次，每個層次完成特定的功能，這樣，各個層次綜合在一起，就可以特定的功能，這樣，各個層次綜合在一起，就可以完成一個完好

2、的系統功能。完成一個完好的系統功能。 v子網層一般又稱網絡接口層，負責從網絡層接收子網層一般又稱網絡接口層，負責從網絡層接收IP報文并向報文并向物理網絡發送，或從網絡上接收物理幀，取出物理網絡發送，或從網絡上接收物理幀，取出IP數據報并提交數據報并提交給網絡層。給網絡層。v網絡層負責處理分組在網絡中的活動，提供跨越多個網絡的網絡層負責處理分組在網絡中的活動，提供跨越多個網絡的選路功能，并對上層屏蔽底層詳細子網技術的細節。選路功能，并對上層屏蔽底層詳細子網技術的細節。v傳輸層主要為兩臺主機上的應用程序提供端到端的通信。在傳輸層主要為兩臺主機上的應用程序提供端到端的通信。在IP網絡中，有兩個傳輸協

3、議：網絡中，有兩個傳輸協議：TCPTransmission Control Protocol，傳輸控制協議和，傳輸控制協議和UDPUser Datagram Protocol ，用戶數據報協議。用戶數據報協議。v應用層處理特定應用程序細節，為用戶完成各種網絡效勞。應用層處理特定應用程序細節，為用戶完成各種網絡效勞。本章提綱本章提綱v互聯網的體系構造互聯網的體系構造vIP路由中的根本概念路由中的根本概念v路由轉發原理路由轉發原理v路由選擇算法路由選擇算法v路由器硬件體系構造路由器硬件體系構造v路由器路由器路由器是工作在網絡層上，可以連接不同類型的網絡，路由器是工作在網絡層上，可以連接不同類型的網

4、絡，可以選擇數據傳送途徑并對數據進展轉發的網絡設備。可以選擇數據傳送途徑并對數據進展轉發的網絡設備。從通信的角度看，路由器是一種中繼系統。從通信的角度看，路由器是一種中繼系統。 應應用用層層傳傳輸輸層層IP層層子子網網層層應應用用層層傳傳輸輸層層IP層層子子網網層層路路由由器器路路由由器器屏屏蔽蔽下下層層細細節節v路由表路由表路由器在接收到數據時，要對其傳輸途徑進展選擇。為了路由器在接收到數據時，要對其傳輸途徑進展選擇。為了實現這一目的，路由器需要維護一個稱為實現這一目的，路由器需要維護一個稱為“路由表路由表的數的數據構造據構造。路由表包含假設干條目，供路由器選路時查詢數據傳輸途路由表包含假設

5、干條目，供路由器選路時查詢數據傳輸途徑。徑。路由表中的一個條目至少要包含：路由表中的一個條目至少要包含： 數據的目的地址通常是目的主機所在網絡的地址數據的目的地址通常是目的主機所在網絡的地址 下一跳路由器即從本路由器出發按所給途徑到給定目的地所要通下一跳路由器即從本路由器出發按所給途徑到給定目的地所要通過的下一個路由器的地址過的下一個路由器的地址 相應的網絡接口相應的網絡接口 一般情況下還應該有標志位等內容。一般情況下還應該有標志位等內容。 泛洪泛洪Flooding源路由源路由124D3S路徑探測過程路徑探測過程S 1 2 D數據包中攜帶的選路信息數據包中攜帶的選路信息v選路策略和選路機制選路

6、策略和選路機制選路策略選路策略Routing Policy：根據數據包的目的地和網：根據數據包的目的地和網絡的拓撲構造選擇一條最正確途徑，把對應不同目的地絡的拓撲構造選擇一條最正確途徑，把對應不同目的地的最正確途徑存放在路由表中；的最正確途徑存放在路由表中；選路機制選路機制Routing Mechanism：搜索路由表，決定向：搜索路由表，決定向哪個接口轉發數據，并執行相應的操作；哪個接口轉發數據，并執行相應的操作；選路策略只影響路由表的內容，比方對同一個目的地址選路策略只影響路由表的內容，比方對同一個目的地址來說，由于選路策略的不同，最正確途徑可能會不一樣，來說，由于選路策略的不同，最正確途

7、徑可能會不一樣，但這并不影響選路機制的執行過程，只是會對其執行的但這并不影響選路機制的執行過程，只是會對其執行的結果產生影響。結果產生影響。 vIP網絡地址構造網絡地址構造 指指IP地址包括地址包括IPv4和和IPv6的編址方式。的編址方式。 通常把地址空間分為網絡號和主機號兩部分，當路由器在進展途徑通常把地址空間分為網絡號和主機號兩部分，當路由器在進展途徑選擇時，一般按照目的網絡來查詢，這樣既可以降低路由表規模，選擇時，一般按照目的網絡來查詢，這樣既可以降低路由表規模，也可以進步路由查詢效率。也可以進步路由查詢效率。 早期早期IPv4網絡把地址分為網絡把地址分為A、B、C、D、E五類，浪費了

8、大量的地址五類，浪費了大量的地址空間，并造成路由效率低下。為解決這些問題，出現了空間，并造成路由效率低下。為解決這些問題，出現了CIDRClassless InterDomain Routing ，無類別域間路由機制，即不再，無類別域間路由機制，即不再嚴格的對嚴格的對IP地址類別進展區分，地址類別進展區分，IP地址網絡號長度也不再固定。地址網絡號長度也不再固定。 IPv6地址的編址方式與地址的編址方式與CIDR類似，也是不限定網絡號空間的長度，類似，也是不限定網絡號空間的長度，因此有很強的靈敏性。因此有很強的靈敏性。 IP網絡地址構造對路由選擇和路由查詢都有很大的影響。網絡地址構造對路由選擇和

9、路由查詢都有很大的影響。 v自治系統和路由域自治系統和路由域由于由于Internet規模太大，分布范圍太廣，所以路由表中對規模太大，分布范圍太廣，所以路由表中對應每一個目的網絡都有一個條目是不可能的；同樣，也應每一個目的網絡都有一個條目是不可能的；同樣，也不可能采用一個全局的路由算法或協議。因此，不可能采用一個全局的路由算法或協議。因此，Internet將整個網絡劃分為假設干個相對自治的部分系統，即自將整個網絡劃分為假設干個相對自治的部分系統，即自治系統治系統AS，Autonomous System。自治系統自治系統可以定可以定義為同一機構下管理的路由器和網絡的集合。義為同一機構下管理的路由器

10、和網絡的集合。 一個自治系統內部還可以再劃分幾個小的路由域，也稱一個自治系統內部還可以再劃分幾個小的路由域，也稱作區域。作區域。 v 內部網關協議和外部網關協議內部網關協議和外部網關協議 路由協議可以分為內部網關協議路由協議可以分為內部網關協議IGP，Interior Gateway Protocol和外部網關協議和外部網關協議EGP，Exterior Gateway Protocol兩大類。兩大類。v 內部網關協議是用于自治系統內部的動態路由協議內部網關協議是用于自治系統內部的動態路由協議 RIPRouting Information Protocol ，路由信息協議，路由信息協議 OSPF

11、Open Shortest Path First，開放最短途徑優先，開放最短途徑優先 ；v 外部網關協議是用于自治系統之間拓撲信息交換的路由協議外部網關協議是用于自治系統之間拓撲信息交換的路由協議 BGPBorder Gateway Routing Protocol ，邊界網關路由協議，邊界網關路由協議 。 v路由選擇算法路由選擇算法路由算法是指路由器獲得對網絡拓撲構造路由算法是指路由器獲得對網絡拓撲構造的認知，并為數據包選擇正確傳輸途徑的的認知，并為數據包選擇正確傳輸途徑的方法或者策略。方法或者策略。一個理想的路由算法至少應該具備以下幾一個理想的路由算法至少應該具備以下幾點特征：完好性和正確

12、性；簡單性；點特征：完好性和正確性；簡單性；強健性；公平性；最正確性。強健性；公平性；最正確性。路由算法的分類。路由算法的分類。v靜態路由選擇和動態路由選擇靜態路由選擇和動態路由選擇按照能否自動適應網絡拓撲構造的變化，可以將按照能否自動適應網絡拓撲構造的變化，可以將選路策略分為靜態路由選擇和動態路由選擇兩大選路策略分為靜態路由選擇和動態路由選擇兩大類。類。靜態路由選擇并不是表示路由表一成不變，只是靜態路由選擇并不是表示路由表一成不變，只是說明路由器不是通過彼此之間動態交換路由信息說明路由器不是通過彼此之間動態交換路由信息來建立和更新路由表的。來建立和更新路由表的。 動態路由選擇是通過網絡中路由

13、器間的互相通信動態路由選擇是通過網絡中路由器間的互相通信來傳遞路由信息，利用接收到的路由信息自動更來傳遞路由信息，利用接收到的路由信息自動更新路由表。新路由表。 v間隔間隔 矢量路由選擇協議和鏈路狀態路由選擇協議矢量路由選擇協議和鏈路狀態路由選擇協議 間隔間隔 矢量路由選擇協議基于間隔矢量路由選擇協議基于間隔 矢量路由算法。其根本思想是路由矢量路由算法。其根本思想是路由器周期地和相鄰路由器交換路由表中的信息。這種信息是由假設干器周期地和相鄰路由器交換路由表中的信息。這種信息是由假設干V，D對組成的表項，其中，對組成的表項，其中，V代表矢量，指出該路由器可以到代表矢量，指出該路由器可以到達的目的

14、地；達的目的地；D表示去往目的表示去往目的V的間隔的間隔 。各個路由器根據收到的信息。各個路由器根據收到的信息重新計算到各目的節點的間隔重新計算到各目的節點的間隔 ，對自己的路由表進展修正。，對自己的路由表進展修正。 鏈路狀態路由選擇協議也被稱為最短途徑優先協議，它基于鏈路狀態鏈路狀態路由選擇協議也被稱為最短途徑優先協議，它基于鏈路狀態路由算法。采用這種協議的路由器都要維護一張可以表示整個網絡拓路由算法。采用這種協議的路由器都要維護一張可以表示整個網絡拓撲構造的無向圖撲構造的無向圖GV，E，在圖在圖G中，節點中，節點V表示路由器，邊表示路由器，邊E表表示連接路由器的鏈路，因此示連接路由器的鏈路

15、，因此G又可以稱為又可以稱為L-S鏈路鏈路-狀態圖，各路狀態圖，各路由器的路由表通過由器的路由表通過L-S圖計算。圖計算。 本章提綱本章提綱v互聯網的體系構造互聯網的體系構造vIP路由中的根本概念路由中的根本概念v路由轉發原理路由轉發原理v路由選擇算法路由選擇算法v路由器硬件體系構造路由器硬件體系構造路由轉發原理路由轉發原理 處理器處理器內存內存接口接口1接口接口2接口接口n查詢路由表查詢路由表首部首部數據數據首部首部首部首部數據數據首部首部數據數據首部首部數據數據首首部部數據數據處理首部本章提綱本章提綱v互聯網的體系構造互聯網的體系構造vIP路由中的根本概念路由中的根本概念v路由轉發原理路由

16、轉發原理v路由選擇算法路由選擇算法v路由器硬件體系構造路由器硬件體系構造間隔間隔 矢量路由算法矢量路由算法 1各路由器對自己的路由表進展初始化，把與自己直各路由器對自己的路由表進展初始化，把與自己直接相連網絡的間隔接相連網絡的間隔 設為設為0在某些詳細實現中也設為在某些詳細實現中也設為1，這，這只是一個初始值設定的問題，然后周期性地向外播送其路只是一個初始值設定的問題，然后周期性地向外播送其路由表的內容。由表的內容。2路由器路由器Ri收到相鄰路由器收到相鄰路由器Rj的間隔的間隔 矢量信息后，對矢量信息后，對自己的路由表進展修正。自己的路由表進展修正。假設假設Rj的間隔的間隔 矢量信息中所包含的

17、目的節點矢量信息中所包含的目的節點va在在Ri的路的路由表中沒有，那么在由表中沒有，那么在Ri的路由表中增加一個目的節點為的路由表中增加一個目的節點為va的的條目，條目，令令dia=dja+1，并把到節點并把到節點va的下一跳路由器設為的下一跳路由器設為Rj 。假設到假設到Rj目的節點目的節點vb的路由比的路由比Ri到目的節點到目的節點vb的路的路由短，那么令由短，那么令dib=djb+1 ，并把到節點，并把到節點vb的下一跳路的下一跳路由器設為由器設為Rj 。 Ri到目的節點到目的節點vc最短途徑上的下一跳是最短途徑上的下一跳是Rj 。假如。假如Rj的路由表中不再包含到的的路由表中不再包含到

18、的vc路由，那么在路由，那么在Ri中也應中也應該把去往該把去往vc的路由刪掉；假如的路由刪掉；假如Rj到到vc的間隔的間隔 發生了發生了變化，那么變化，那么Ri修改路由表中到修改路由表中到vc的間隔的間隔 ，令，令dic=djc+1 。v間隔間隔 矢量路由算法在理論上是可以正常工作矢量路由算法在理論上是可以正常工作的，但在實際中存在著一個嚴重的缺陷：盡的，但在實際中存在著一個嚴重的缺陷：盡管它可以收斂到正確的路由，但它對好消息管它可以收斂到正確的路由，但它對好消息傳播的快，而對壞消息那么傳播的慢。傳播的快，而對壞消息那么傳播的慢。v總的來說，間隔總的來說，間隔 矢量路由選擇協議的優點是矢量路由

19、選擇協議的優點是易于實現，但難以適應網絡拓撲的劇烈變動易于實現，但難以適應網絡拓撲的劇烈變動或者大型的網絡環境。或者大型的網絡環境。 鏈路狀態路由算法鏈路狀態路由算法 v鏈路狀態路由算法的根本步驟如下：鏈路狀態路由算法的根本步驟如下：1每一個路由器節點啟動后，首先執行對相每一個路由器節點啟動后，首先執行對相鄰節點的發現工作，并獲取它們的地址。鄰節點的發現工作，并獲取它們的地址。2各路由器主動測試到每一個相鄰路由器的鏈路各路由器主動測試到每一個相鄰路由器的鏈路時延或本錢，并根據測試結果設置相關鏈路的狀態。時延或本錢，并根據測試結果設置相關鏈路的狀態。3各路由器構造自己的各路由器構造自己的L-SL

20、ink-State，鏈路狀態信息鏈路狀態信息包，包，L-S信息的內容包括本路由器的標號、本路由器的鄰居路信息的內容包括本路由器的標號、本路由器的鄰居路由器列表、本路由器到各鄰居路由器的鏈路狀態時延或本由器列表、本路由器到各鄰居路由器的鏈路狀態時延或本錢、該錢、該L-S信息包的序號和生存時間等。信息包的序號和生存時間等。4各路由器向所有參與鏈路狀態交互的路由器播送其各路由器向所有參與鏈路狀態交互的路由器播送其L-S信信息，可以是周期性地發送，也可在鏈路狀態發生變化時發送。息，可以是周期性地發送，也可在鏈路狀態發生變化時發送。 5每個路由器在收到所有的每個路由器在收到所有的L-S信息后，可以構造或

21、更新信息后，可以構造或更新表示整個網絡拓撲構造的圖表示整個網絡拓撲構造的圖GV，E，頂點頂點V表示路由器，表示路由器，邊邊E表示連接路由器的鏈路；這時路由器就可以用表示連接路由器的鏈路；這時路由器就可以用Dijkstra算法算法從圖從圖G中計算出到所有目的路由器的最短途徑，也就是構造以中計算出到所有目的路由器的最短途徑，也就是構造以自己為根節點的自己為根節點的SPF樹。樹。 Dijkstra算法簡介算法簡介 設目的節點就構造設目的節點就構造SPF樹而言，是根節點為樹而言，是根節點為k，任一，任一條鏈路條鏈路i，j的長度為的長度為dij，每個節點到，每個節點到k的最短途徑長度估的最短途徑長度估計

22、為計為Dik；定義所有節點的集合為；定義所有節點的集合為A，定義集合，定義集合PA，并設定，并設定集合的初始值為集合的初始值為P=k。 在算法迭代的過程中，假如在算法迭代的過程中，假如Dik已經變成一個確定值，那已經變成一個確定值，那么將么將i標記為固定點，并將其參加集合標記為固定點，并將其參加集合P。在算法的每一步迭。在算法的每一步迭代中，在代中，在P以外的節點中，選擇與目的節點以外的節點中，選擇與目的節點k最近的節點參加最近的節點參加到到P中，算法的詳細步驟如下：中，算法的詳細步驟如下：Dijkstra算法簡介算法簡介1P=k, Dkk=0，Djk=djk假設假設j和和k不相鄰，不相鄰，

23、2求解使求解使 成立的成立的i， ，即尋找下一，即尋找下一個和目的節點最近的節點；令個和目的節點最近的節點；令 ，假設，假設P=A，算法完畢。算法完畢。3對所有對所有 ，置，置 ，返回，返回步驟步驟2jkd minikjkj PDDiP:PPiUjP: minjkjkiijiDDDd，R1R3R2R4R5R6R7R8R9613225253332R1R3R5R4R8R7R2R6R912323223本章提綱本章提綱v互聯網的體系構造互聯網的體系構造vIP路由中的根本概念路由中的根本概念v路由轉發原理路由轉發原理v路由選擇算法路由選擇算法v路由器硬件體系構造路由器硬件體系構造v集中式單多集中式單多CPU+總線構造總線構造CPU內內存存網網絡絡接接口口卡卡網網絡絡接接口口卡卡網網絡絡接接口口卡卡.缺陷缺陷 CPU要負責整體系統的控制管理、路由計算和數要負責整體系統的控制管理、路由計算和數據轉發等各項功能，存在計算瓶頸。據轉發等各