第6章網絡互連本章主要內容網絡互連是指采用各種網絡設備將同一類型的網絡或不同類型的網絡及其產品相互連接起來，形成一個更大的網絡。也可以理解為將一個大的網絡分解為若干個小的網絡。本章首先介紹了網絡層及網絡互連的基本概念和一些互連設備，然后重點討論了網絡互連的核心內容IP協議，只有掌握了IP協議的主要內容，才能理解Internet的工作原理。在介紹IP協議后，我們討論了路由原理及協議、IP多播技術和Internet組管理協議IGMP。最后簡要地討論了下一代的網際協議IPv6的主要內容。6.1網絡層服務與網絡互連6.1.1網絡層服務模型網絡層是OSI參考模型中的第三層，它介于傳輸層和數據鏈路層之間，在數據鏈路層提供的兩個相鄰結點之間數據幀的傳送功能上，進一步管理網絡中的數據通信，將數據設法從源端經過若干個中間結點傳送到目的端，從而向傳輸層提供最基本的端到端的數據傳送服務。圖6-1網絡層運行的環境6.1.2網絡互連基本概念1．基本概念在前面的討論中，我們所基于的環境是單個的同種協議網，網絡中每個結點對應的層所用的協議相同。研究的重點問題是在同一個網絡中，相鄰結點之間或跨過多個結點進行數據傳輸的概念和控制機制。本章所討論的網絡互連問題是基于同種或異種網絡之間的連接。重點考慮的是不同網絡之間的互連問題。圖6-2不同網絡之間的連接目前，隨著計算機及網絡技術的發展，網絡互連包含兩個方面的含義：①指采用各種網絡互連設備將同一類型的網絡或不同類型的網絡及其產品相互連接起來，組成地理覆蓋范圍更大、功能更強大的網絡，以實現在更大范圍內的資源共享、信息交換和協同工作。②也可以理解為將一個大的網絡分解為若干個子網，以利于更有效的管理和使用網絡資源。2．網絡互連的基本原理互連的網絡在體系結構、層次協議及服務等方面或多或少存在著差異，對于異構網來說（例如各種類型的局域網）差異就更大。這種差異主要表現在：①尋址方式；②路由選擇；③允許通過分組的最大長度；④網絡接入機制；⑤用戶接入控制；⑥超時控制、差錯恢復方法；⑦服務、管理方式等。要實現網絡互連，就必須消除網絡間的差異，這些都是網絡互連要解決的問題。將網絡互相連接起來要使用一些中間設備（或中間系統），ISO的術語稱之為中繼（relay）系統，我們把用于網絡之間互連的中繼設備稱為網絡互連設備。網絡互連方法網絡互連可以有多種方法，其最重要的方法應是以ISO/OSI互連參考模型的層次設計理論來進行網絡互連，也就是從不同的網絡體系結構上選定一個相應的協議層次，使得被互連網絡設備中的該層以及位于其上的高層協議都是相同的，其底層和硬件的差異可通過該層屏蔽，從而使網絡得以互通。如果兩個網絡第N層以上的協議都相同，網絡互連設備在這一層上互連。我們稱該設備為第N層網絡互連設備。這些設備按它們對不同層次的協議和功能轉換，可以分為以下幾類：①中繼器（Repeater）；②網橋（Bridge）；③路由器（Router）；④網關（Gateway）。圖6-3連網設備的層次關系3．網絡互連設備路由器（Router）是用于連接多個邏輯上分開的網絡。邏輯網絡是指一個單獨的網絡或一個子網。路由器是屬于網絡層的一種互連設備，只接收源站或其他路由器的信息，它不關心各子網使用的硬件設備，但要求運行與網絡層協議相一致的軟件。為了管理網絡，一般要利用路由器將大型的網絡劃分成多個子網。Internet由各種各樣的網絡構成，路由器是一種非常重要的組成部分，整個Internet上的路由器不計其數。Intranet要并入Internet，兼作Internet服務，路由器是必不可少的組件，并且路由器的配置也比較復雜。路由器的功能⑴互連不同類型的網絡⑵隔離廣播風暴（Broadcaststorm）⑶建立并維護路由表⑷子網間分組的傳輸⑸提供安全訪問的機制⑹可以提供第三層的網絡服務6.2IP協議6.2.1IP協議原理IP協議最基本的服務是提供一個不可靠的盡最大努力（BestEffort）去完成好任務的、無連接的分組傳遞服務。之所以稱該服務為不可靠的，是因為它不保證每個分組都能夠送到或者能夠正確的送到，分組可能丟失，投遞無序或重復投遞，而IP層并不檢測這些情況，發生這些情況也不通知發送者或接收者，可靠性要由傳輸層等上層協議來提供。之所以稱它為無連接的，是因為每一個分組的處理都獨立于其他分組，一串分組從一臺計算機發出，可以經由不同的路徑到達另一臺計算機。在分組傳遞過程中，可能會丟失部分分組，而其余的仍被投遞。IP協議定義數據傳送的基本單元——IP分組及其確切的數據格式。IP協議還指明分組如何處理，錯誤怎樣控制。特別是，IP協議還包含不可靠投遞的思想，以及與此關聯的分組路由選擇的思想。IP模塊是TCP/IP技術的核心，TCP/IP協議簇現有兩種IP版本：版本4（IPv4）和版本6（IPv6）。6.2.2IP地址的劃分1．IP地址的格式與分類在IPv4標準中，每個32位IP地址包含兩個部分：網絡號（netID）和主機號（hostID）。其中，網絡號用來標識一個網絡，主機號用來標識網絡中的某一臺主機。沒有兩個網絡能夠分配同一個網絡號，同一網絡上的兩臺計算機也不可能分配同一個主機號。IANA（InternetAssignedNumbersAuthority）負責分配網絡號，以確保網絡號的唯一性。Internet服務提供商（InternetServiceProvider,ISP）或網絡管理員負責維護同一網絡上主機號的唯一性等。網絡號和主機號的邊界由IP地址的類別來確定，不同類別的IP地址能夠滿足不同規模網絡的組網需要。IP地址的長度為32位，為了方便用戶理解和記憶，通常采用“x.x.x.x”的格式來表示，每個x的取值為0～255。這種格式的地址通常稱為點分十進制數地址。根據不同的取值范圍，IP地址分為5類：A類、B類、C類、D類和E類。圖6-5IP地址的類別（1）A類地址第一位為“0”，其網絡號長度為7位，主機號長度為24位。A類地址范圍是：1.0.0.0～127.255.255.255。由于網絡號長度為7位，所以從理論上可以有27=128個網絡。但由于網絡號全0和全1（用十進制數表示為0和127）的兩個網絡有特殊用途，因此一個A類IP地址實際上允許有126個不同的A類網絡。由于主機號長度為24位，因此每個A類網絡的主機號理論上為224=16777216個。其中，主機號全為0和全1的兩個地址保留用于特殊目的，因此實際上一個A類網絡的主機號為16777214個。（2）B類地址前兩位是“10”，其網絡號長度為14位，主機號長度為16位。B類地址范圍是：128.0.0.0～191.255.255.255。由于網絡號長度為14位，所以可以有214=16384個B類網絡。需要注意的是，由于B類地址的前兩位為“10”，所以后面的14位無論怎么排列也不可能使整個網絡號成為全0或全1，故不存在減2的問題。由于主機號長度為16位，所以每個B類網絡的主機號實際為2162=65534個。（3）C類地址前三位是“110”，其網絡號長度為21位，主機號長度為8位。C類地址范圍是：192.0.0.0～223.255.255.255。由于網絡號長度為21位，所以可以有221=2097152個C類網絡（這里也不需要減2）。由于主機號長度為8位，所以每個C類網絡的主機號實際為282=254個。（4）D類地址最高位是“1110”，不標識網絡，其范圍是：224.0.0.0～239.255.255.255。D類地址用于其他特殊的用途，如作為多播（multicasting）地址。（5）E類地址最高位為“11110”，是一個通常不用的實驗性地址，保留作為以后使用。地址范圍是：240.0.0.0～255.255.255.255。表6-1IP地址范圍、網絡及主機數目類別地址范圍網絡數目主機數目A1.0.0.0～127.255.255.25512616777214B128.0.0.0～191.255.255.2551683465534C192.0.0.0～223.255.255.2552097152254在IP地址的使用中應該注意，IP地址既對應一個網絡號，也對應那個網絡上的一臺主機號，因此，一個IP地址并不是標識一臺主機（或路由器），而是標識一臺主機（或路由器）與一條鏈路的接口。2．特殊用途的IP地址IP地址除了一般用于標識一臺主機外，還有幾種特殊的用途，相應的特殊形式如圖6-6所示。圖6-6特殊用途的IP地址格式3．專用地址在IP地址的管理與使用中，IP地址被分成兩類，對于采用TCP/IP協議的機構內部網或園區網，網內的IP地址自行分配，這些地址稱為內網地址、本地地址、內部IP或私有地址，而向Internet管理機構申請的IP地址稱為全球地址、公網IP或外部地址。地址類別網絡地址A類10.0.0.0～10.255.255.254B類172.16.0.0～172.31.255.254C類192.168.0.0～192.168.255.255表6-2內部IP地址的類型及范圍6.2.3IP分組1．IP分組的格式IP分組（IPdatagram）包含一個分組頭和一個數據區。頭部包括一個20字節的固定部分和一個可選的部分。圖6-7給出了IP分組更詳細的格式。圖6-7IP分組格式IP分組字段的意義（1）版本號IP分組中的第一個字段是4位的版本號（version）。當前的IP協議版本號為4，故常稱為IPv4。下一代互聯網IP協議的版本號是6，稱為IPv6。（2）分組長度和填充字段在IP分組頭中有兩個長度字段。①IP分組頭長度（InternetHeaderLength，IHL）②IP分組的總長度（3）服務類型和優先權8位長的服務類型（TypeofService，TOS）規定本分組的處理方式，并分成5個子字段。子字段的結構如圖6-8所示。圖6-8服務類型字段的5個子字段（4）標識符、分片標志和分片偏移不同的物理網絡由于采用不同的傳輸技術或具有不同的參數，其允許通過的最大幀長度是不一樣的。這個幀尺寸稱為最大傳輸單元（MaximumTransferUnit，MTU）。例如，10Mbps以太網每幀最多可承載1500個字節。當分組從一個MTU較大的網絡經路由器轉發到一個MTU較小的網絡上時，由于分組過長，路由器就會拒絕轉發，或將分組分片后再傳送。分片的過程通常在路由器中完成，而分片重組由主機中IP協議軟件完成。IP分組頭中的標識符（ID）、分片標志（fragflag）和分片偏移量（fragmentoffset）3個字段完成分片和重組控制。（5）生存時間生存時間（TimetoLive，TTL）設置了該分組在Internet中允許存在的最大生存時間，以秒為單位。每當產生一個新的分組時，就為它設置一個最大的生存時間。當分組通過主機和路由器時，減去所花費的時間。一旦生存時間小于等于0，便將該分組從Internet中刪除，并向源主機發回出錯信息。RFC建議生存時間的默認值為64，而WindowsXP和Windows2003的用戶使用的生存時間默認值為128。（6）協議8位的協議字段通過填充不同的標識號來表示哪一個高層協議將用于接收IP分組中的數據。高層協議的標識號由TCP/IP中央權威管理機構予以分配。常見的協議序列號有：1對應ICMP，6對應傳輸控制協議（TCP），8對應EGP（外部網關協議），17對應用戶數據報協議（UDP），29對應ISO運輸層協議第4類（ISO-TP4）。（7）頭部校驗和分組頭中的任何一個字段發生傳輸錯誤都會產生很多無法預料的結果。例如，如果發送地址錯誤，就可能無法刪除一個已經過期的分組或重組不屬于同一報文的分片。分組頭校驗和（headerchecksum）可以保護IP分組不產生這類錯誤，確保分組頭的完整性。IP分組頭校驗和的計算過程是，先將校驗和字段置0，把分組頭看成一個16位的整數序列，對每個整數分別計算其二進制反碼，相加后再對結果計算一次二進制反碼即可求得，該結果常簡稱為反碼和的反碼。IP協議沒有提供對數據部分的校驗。（8）源IP地址和目的IP地址源IP地址（sourceIP）和目的IP地址（destinationIP）字段包含了分組的原始發送方和最終接收方的32位IP地址。分組可能經過許多中間路由器，但是這兩個地址始終不變。（9）IP選項目的IP地址后面的IP選項字段是任選字段，它的主要目的是裝載特定的功能以便于網絡測試和調試。在IP分組中，選項是連續出現的，中間沒有任何分隔符。每個選項包含一個選項碼字節，后面可能跟有一個長度字節和該選項的一組字節數據。2．IP分組分片和重組不同的物理網絡，使用的幀格式以及允許的幀的長度都是不一樣的。物理網絡允許的MTU值由物理網絡的硬件和算法所確定，不能更改。IP分組的最大長度可以為64K，遠大于大多數物理網絡的MTU值。當一個較長的IP分組在經過一個MTU較小的物理網絡時，IP協議將采用分片機制，把一個大的IP分組，分成若干個小的分片進行傳輸。圖6-9IP分組的分片重組過程圖6-10分組被分片6.2.3IP地址的動態分配隨著Internet的迅速發展，兩級結構的IP地址分配方式很難滿足日益增長的網絡要求，并日益顯現出下面的缺點：⑴IP地址的浪費⑵路由器效率低下為了解決這些問題，人們提出了子網（subnet）和超網（supernet）的概念。劃分子網就是將一個大的網絡劃分成幾個較小的網絡，而每一個子網絡都有其自己的子網地址。構建超網則是將一個組織所屬的幾個C類網絡合成為一個地址范圍更大的邏輯網絡，其中一個比較好的方法是無分類域間路由選擇CIDR（ClasslessInter-DomainRouting）（RFC1519）。1．子網與子網掩碼（1）子網一般地，32位的IP地址分為兩部分，即網絡號和主機號，分別稱為IP地址的“網絡號”和“主機號”。子網劃分技術就是將主機部分進一步劃分為“子網號”和“主機號”，其中“子網號”用于標識同一IP網絡地址下的不同物理網絡，即“子網”。三級IP地址格式如圖6-11所示。圖6-11三級IP地址格式（2）子網掩碼IP協議規定：每一個使用子網技術的網絡都需要選擇一個32位的位模式，若位模式中的某位為1，則對應IP地址中的某位為網絡地址（包括網絡號和子網號）中的一位；若位模式中的某位為0，則對應IP地址中的某位為主機地址中的一位。例如，11111111111111111111111100000000中，前24位全為1，則對應IP地址中最高的24位為網絡地址；后8位全為0，則對應IP地址中最后的8位為主機地址。為了使用方便，常常使用“點分十進制數”來表示一個IP地址和子網掩碼。（3）子網掩碼與IP地址例如，有一個C類地址為192.168.1.1，其默認子網掩碼為255.255.255.0，則它的網絡號192.168.1.0和主機號1可以通過下面的掩碼運算方法得到。①將IP地址192.168.1.1轉換為二進制11000000101010000000000100000001②將子網掩碼255.255.255.0轉換為二進制11111111111111111111111100000000

③將兩個二進制數進行邏輯與（AND）運算后，得到的結果即為網絡號④將子網掩碼取反再與IP地址進行邏輯與（AND）運算后，得到的結果即為主機號（4）子網劃分實例例如，一個企業使用一個B類地址172.18.0.0構建企業內部網絡，內部有60個物理網絡。那么，網絡設計者就必須對這個B類地址進行子網劃分。①根據所要構建的物理網絡的數量確定子網號。由于25<60<26，所以從B類地址的主機號（16位）中取出6位（最小取6位）作為子網號。②確定子網掩碼。如圖6-12所示，根據上一步確定的子網號，將其IP地址的網絡部分和主機部分的高6位置1，低10位置0，即確定子網掩碼為255.255.252.0。③確定每個子網主機數量和子網地址的范圍。由于主機號為10位，所以每個子網可容納的主機數量為2102=1022，子網掩碼為255.255.252.0。具體劃分如下。特殊地址：172.18.0.0～172.18.0.3.255子網1：172.18.4.0～172.18.7.255子網2：172.18.8.0～172.18.11.255……子網60：172.18.248.0～172.18.251.255特殊地址：172.18.252.0～172.18.255.2552．CIDR為了更加有效地分配和利用IP地址空間，很好地解決IP地址空間既緊張又浪費的問題，IETF在1993年提出了無分類編址的方法CIDR，即無分類域間路由選擇。CIDR中的IP地址由網絡前綴和主機號構成。CIDR使用“斜線記法”（slashnotation），又稱為CIDR記法，即在IP地址后面加上一個斜線“/”，然后寫上網絡前綴所占的比特數。例如，166.100.20.82/20，前20位表示網絡前綴，而后面的12位為主機號。CIDR取消了子網概念，不進行子網劃分，但是還使用掩碼。對一個有N位網絡前綴的IP地址，其掩碼就是高位N個連續的1，余下的是32N個0。CIDR的用途之一就是構造超網。使用CIDR地址塊后，網絡路由器中的路由表項可以表示很多個傳統IP地址的路由信息，相當于把若干個網絡合并為一個超網來進行路由，這種地址的聚合稱為路由聚合，也稱為構造超網。圖6-13具有4個C類地址的企業網絡結構將這4個C類網絡地址按照CIDR方法進行路由聚合處理，過程如下:①將各網絡的網絡號轉化為二進制。②找出各網絡的公共前綴為前面的24位，即202.0.44，所以子網掩碼為11111111111111111111110000000000，即255.255.252.0。③對于位于Internet上的路由器1，如果有一個到此企業的分組，那么它的路由表中關于此企業的記錄由原來的4項（見表6-3）壓縮為1項（見表6-4），這個分組只要送到企業的網關（路由器2）即可。表6-3路由聚合前路由器1中有關此企業的路由記錄目的網絡地址子網掩碼下一個轉發結點地址202.0.44.0255.255.255.0202.112.2.1202.0.45.0255.255.255.0202.112.2.1202.0.46.0255.255.255.0202.112.2.1202.0.47.0255.255.255.0202.112.2.1表6-4路由聚合后路由器1中有關此企業的路由記錄目的網絡地址子網掩碼下一個轉發結點地址202.0.44.0255.255.252.0202.112.2.16.3ARP和RARP協議6.3.1ARP協議由于IP協議使用了下一層，即數據鏈路層協議進行實際數據的傳輸，所以在IP協議中，當實際發送數據時，發送方必須知道數據鏈路層的物理硬件地址，也稱為MAC地址。地址解析協議（AddressResolutionProtocol，ARP）實現IP地址與MAC地址之間的轉換。位于網絡中的每臺主機都要維護一個IP地址到MAC的轉換表（緩存），稱為ARP表。在主機啟動時，ARP表為空。ARP協議中所使用的ARP包的格式如圖6-14所示。圖6-14ARP包的格式6.3.2RARP協議反向地址解析協議（ReverseAddressResolutionProtocol，RARP），用于物理地址到IP地址的映射。RARP協議的一個主要應用是用于無盤工作站的初始化。當無盤工作站在啟動時，只知道自己的網絡接口的MAC地址，而不知道自己的IP地址。它首先要使用RARP協議得到自己的IP地址后，才能和其他服務器通信。6.3.3IP層處理分組的流程IP層對分組的處理分兩種情況：⑴如果源和目的主機位于相同子網中，主機之間不通過路由器，可以直接進行分組傳遞。⑵如果源和目的主機位于不同子網中，主機之間的數據傳遞就需要通過一個或多個路由器轉發。在這種情況下，每一個收到分組的路由器都要提取分組中目的IP地址的網絡號，查找自身的路由表，找出下一個轉發路由器的IP地址（一般稱為下一跳地址），然后把分組傳送給下一個路由器進行轉發。當IP分組到達與目的主機所在的子網連接的路由器時，分組將被直接交給目的主機。圖6-15路由器中的路由表舉例6.4ICMP協議ICMP（InternetControlMessageProtocol）是Internet中一個差錯和控制報文協議，由于IP協議的目的比較明確，它只是盡力地、最快地傳遞數據到目的站點，因此很難診斷錯誤情況，必須通過另外的協議返回相應的信息。針對網絡層的錯誤診斷、擁塞控制、路徑控制和查詢服務四大功能，ICMP提供相應的報文。RFC792中定義了ICMP協議。圖6-16ICMP報文的封裝圖6-17ICMP報文的格式表6-5類型字段與ICMP報文類型類型字段報文類型類型字段報文類型0回應應答12分組參數錯3目的站點不可達13時間戳請求4源抑制14時間戳應答5重定向15信息請求8回應請求16信息應答9路由器通告17地址掩碼請求10路由器詢問18地址掩碼應答11分組超時6.5路由原理路由選擇（Routing）是指選擇通過互聯網絡從源結點向目的結點傳輸信息的行為，而且信息至少通過一個中間結點。6.5.1理想路由選擇算法的特性正確性（Correctness）簡單性（Simplicity）魯棒性/健壯性（Robustness）穩定性（Stability）公平性（Fairness）最優性（Optimality）6.5.2路由選擇策略通信子網為網絡源結點和目的結點提供了多條傳輸路徑的可能性。網絡結點在收到一個分組后，要確定向下一個結點傳送的路徑，這就是路由選擇（Routing）。在數據報方式中，網絡結點要為每個分組路由做出選擇；而在虛電路方式中，只需在連接建立時確定路由。從路由選擇算法對網絡拓撲和通信量變化的自適應能力的角度劃分，可以分為靜態和動態路由選擇策略兩大類。1．靜態路由選擇策略靜態路由選擇策略是按照某種固定規則進行路由選擇，其中還可分為洪泛路由選擇固定路由選擇隨機路由選擇2．動態路由選擇策略通常根據路由信息的來源和進行路由決策的地點，把動態路由選擇策略分為以下三類：孤立路由選擇法集中路由選擇法分布路由選擇法6.5.3路由算法路由選擇算法是網絡層軟件的主要部分，它駐留在每一臺路由器（或三層交換機）中，負責告訴路由器所收到的分組應傳送的外出路線。最常用的路由算法是最短路徑算法、距離向量算法和鏈路狀態算法。1．最短路徑算法最短路徑路由選擇算法屬于靜態路由選擇方法。這里所指的“最短”可以是經過的站點數最少，也可以是真正物理距離最短或時延最小。這種算法的基本思想是：把網絡看成一個加權圖，圖中的每個結點代表一個路由器，每條邊表示一條通信鏈路，邊的權值為這條邊的長度，它可以是真正的物理距離，也可以是信道的帶寬、平均通信量等其他度量。G=（N,E）Dijkstra算法

Dijkstra算法是一個逐步搜索的過程。假定在K步，得到了K個最接近源結點的最短路徑，這K個結點組成了結點集合N。在第K+1步，找出一個不屬于N的距離源結點最近的結點，并把該結點也加入N。設：①c(i,j)為從結點i到j的鏈路費用。如果i與j不直接相連，那么鏈路費用為∞。為了簡單，假設c(i,j)=c(j,i)。②D(v)為當前從源結點到目標結點v沿著最短路徑的最小費用，v∈N。③p(v)為從源結點到目標結點v的當前最小費用路徑上的前導結點，其下一個結點是v。④N為最短路徑上的結點集合。

算法假定結點A為源結點，則①初始化：置N={A}，對每一個v不屬于N，置D(v)=c(A,v)；②重復：找出一個結點w不屬于N，且D(w)是最小的，把w加入N，然后對所有不屬于N的結點v將D(v)更新為D(v)=MIN[D(v),D(w)+c(w,v)]

步驟集合ND(B),p(B)D(C),p(C)D(D),p(D)D(E),p(E)D(F),p(F)0A3，A7，A1，A∞∞1AD3，A6，D3，D6，D2ADB6，D3，D5，B3ADBE6，D4，E4ADBEF6，D5ADBEFC結點A到其他結點的最短路徑計算過程最短通路樹目的結點路徑長度BA-B3CA-D-C6DA-D1EA-D-E3FA-D-E-F42．距離向量算法距離向量路由選擇算法（distancevectorrouting）是由Bellman，Ford和Fulkerson等人提出的，因此又稱為Bellman-Ford或Ford-Fulkerson路由選擇算法。它最初用于ARPANET中的路由選擇，后來用于Internet和早期版本的DECNet及Novell的IPX（InternetPacketExchange，網間分組交換）協議中，即路由信息協議（RoutingInformationProtocol，RIP）。在距離向量路由選擇算法中，每個結點都保存一張路由表，表中的每一個表項包括兩部分，即到達目的網絡的下一跳地址（下一站路由器地址）和到達目的網絡所需距離的度量值（metric）。所用度量標準可為站點數、估計的時間延遲（ms）、該路由排隊的分組估計總數或類似的值。路由信息交換在距離向量路由選擇算法中，如圖6-20所示，相鄰路由器之間周期性地相互交換各自的路由表備份。當網絡拓撲結構發生變化時，路由器之間也將及時地相互通知有關的變更信息。圖6-20相鄰路由器之間交換路由表信息示意圖距離向量路由算法的名稱來自更新消息中所包含的信息。更新消息由一系列二元組(V,D)組成，其中V標識目的網絡，稱為向量，D是到該目的網絡的距離。設：①DX(Y,Z)表示結點X經過結點Z到結點Y的距離。②c(X,Z)表示結點X與其鄰接結點Z之間的距離。③MINw[DZ(Y,w)]表示結點Z經過某一組中間結點到達結點Y的距離中最短的距離，w是這組結點位于最短費用路徑上的結點。④DX(Y,Z)=c(X,Z)+MINw[DZ(Y,w)]表示結點X的距離表項DX(Y,Z)是X和Z之間直接鏈路的代價c(X,Z)與鄰接結點Z目前已知的從Z到Y的最小費用路徑的和。算法對于結點X有①初始化：結點X經過結點v到其他所有結點的距離為DX(*,v)=∞；對于結點X的所有鄰接結點v,DX(v,v)=c(X,v)。②重復：對每一個非目標結點v用下式更新D(v)DX(Y,v)=c(X,v)+MINw

[Dv(Y,w)]其中，結點w為v的鄰接結點。上式對結點v的所有鄰接結點w進行計算，然后取最小者。這是一個迭代計算的過程。

示例對于DE(A,D)的值（即從E到A的最小費用），路徑上的第1步是D，那么距離表中對應表項就是從E到D的費用加上從D到A的最小費用，而從D到A的最小費用是返回來通過E到A的最小費用，即2+3=5。類似地，DE(A,B)=14。

討論在完全靜態的環境里，距離向量算法將路由傳播到所有目的地。問題:當路由迅速改變時，計算是不可能平穩的。當一條路徑（如一條新的連接出現或一條老的連接斷開）出現故障時，有關信息將緩慢地從一個結點傳播到另一個結點。在這期間，某些結點就可能擁有不正確的路由選擇信息。事實上，如果路徑變化了的信息不是很快地傳播到所有結點，那就會產生所謂的慢收斂（slowconvergence），又稱為無窮計數問題（count-to-infinite）。無窮計數問題在穩定狀態下，結點A直接連到一個網絡X，它向鄰接結點通告一條到達網絡X距離為1的路徑。結點B向鄰接結點通告一條到達網絡X距離為2的路徑。試分析：當結點A和網絡X之間的鏈路失效時，結點A和B中的路由是怎么變化的？圖6-23無窮計數問題示例如何解決此類問題？4種方法解決無窮計數問題（1）水平分割（2）毒性反轉的水平分割（3）抑制規則（4）觸發更新3．鏈路狀態算法鏈路狀態算法也稱為最短路徑優先算法（ShortestPathFirst，SPF）。與距離向量算法不同的是，這種算法要求每個路由結點都保存一份最新的整個網絡的拓撲信息。使用鏈路狀態算法的路由協議有NetWare鏈路服務協議（NetWareLinkServicesProtocol，NLSP）、開放最短路徑優先協議（OpenShortestPathFirst，OSPF）等鏈路狀態算法計算過程5個步驟，每個路由結點：①發現它的鄰居結點，并知道其網絡地址；②測量它到各鄰接結點的延遲或開銷；③組裝一個分組以告知它剛知道的到所有鄰接結點的延遲或開銷；④將這個分組發給所有其他路由結點；⑤在收到了所有其他路由結點發來的消息后，用最短路徑優先算法計算到其他每個路由結點的最短路徑。4．距離向量與鏈路狀態路由選擇算法的比較距離向量算法鏈路狀態算法不知道整個網絡的拓撲結構知道整個網絡的拓撲結構在相鄰路由結點路由信息的基礎上計算路由的距離向量根據網絡拓撲結構尋找和計算最短路徑收斂速度慢收斂速度快路由結點的路由表只發送給相鄰的路由結點路由結點的LSP發送給指定的一個或多個（或所有）路由結點6.5.4分層路由在具體實現一個網絡的路由選擇時，如果網絡結點很多，則每個結點要存儲的路由信息就會非常龐大，這增加了結點的處理時間，同時也占用了更多的帶寬。因此，考慮進行層次路由選擇，即整個網絡分成若干個區域，各個區域內的結點只考慮本區域的路由，而區域之間的路由選擇由各個區域中某幾個結點共同來完成。圖6-26層次路由中的區域某個結點給另一個結點發送分組。如果它們位于同一個區域中，可以使用先前討論過的任何一種技術來決定路由。如果它們位于不同的區域中，如結點A.a

要給C.b傳送分組，則其傳送過程如下：①A.a將分組傳送給本區域內的路由器A.b；②A.b負責確定到達C.b所在區域（域C）的最佳路徑，并發送分組；③結點C.a是區域C的路由器，它接收分組，再將它發送給結點C.b。6.6Internet路由選擇協議6.6.1有關路由選擇協議的幾個基本概念1．被路由的協議（RoutedProtocols）被路由的協議也稱為網絡協議（NetworkProtocol），是指提供了網絡層地址的協議，是在互連網絡上被路由的協議。其中包括IP協議、DECnet、AppleTalk、Novell、Netware、OSI、BanYanVINES和XeroxNetworkSystem（xNS）等。2．路由選擇協議（RoutingProtocols）路由選擇協議也稱為路由協議，是指那些執行路由選擇算法的協議，是路由器之間實現路由信息共享的一種機制，它允許路由器之間相互交換和維護各自的路由表。目前的路由協議包括路由信息協議（RoutingInformationProtocol，RIP）、內部網關路由協議（InteriorGatewayRoutingProtocol，IGRP）、開放最短路徑優先協議（OpenShortestPathFirst，OSPF）等。3．自治系統（AutonomousSystem）由一個獨立的管理實體控制的一組網絡和路由器一般稱為一個自治系統AS。一般地，一個互連的網絡是由多個自治系統組成的。在由很多自治系統組成的互連網絡中，有兩種路由策略：內部網關協議IGP（interiorgatewayprotocol）和外部網關協議EGP（exteriorgatewayprotocol。圖6-27自治系統以及IGP和EGP4．IGP和EGPIGP是在自治系統內使用的路由選擇協議，用于控制自治系統內部路由器間的路徑選擇。常見的例子有RIP，OSPF等。Cisco公司還專門開發了IGRP和EIGRP路由選擇協議。EGP是指連接多個AS的協議，它用于確定AS與AS系統之間的路由，這些協議工作在自治系統之間，在每個AS系統的邊緣上，僅僅交換所必須的最少的信息，用以確保AS之間的通信。6.6.2路由信息協議RIP路由信息協議（RIP）是一種以跳步數作為度量（metric）的典型距離向量路由選擇協議。RIP是一種內部網關協議，即在自治系統內部執行路由選擇功能。RIP的前身是Xerox協議GWINFO（GatewayInformationProtocol），后來的版本是封裝在1982年伯克利標準發布（BSD）UNIX中的routed后臺程序。RIP最新的增強版是RIPv2規范，它允許在RIP分組中包含更多的信息并提供了簡單的認證機制。RIP協議在兩個文檔中正式定義：RFC1058和RFC1723。1．RIP消息格式圖6-28RIP的消息分組格式2．協議執行過程RIP在主機或路由器中實現，因此RIP協議分為兩種不同的操作方式。（1）主機中實現的RIP工作在被動（passive）狀態：不傳遞自己路由表中的信息給別的路由器，只是偵聽其他RIP路由器廣播的路由信息，并據此更新自己的路由表。（2）路由器中實現的RIP工作在主動（active）狀態：它定期把路由信息傳遞給其他RIP路由器，并且根據收到的RIP消息來更新自己的路由表。路由表項每個RIP路由器都保存了一張路由表，每一項對應著一個目的網絡，其中每項包括：目的網絡的IP地址到目的網絡的路徑距離度量到目的網絡的路徑上的下一個轉發路由器的IP地址路由改變標志與這條路由有關的計時器距離度量RIP采用的距離度量是一種非常簡單的測量方式，即站點計數度量。路由器把到與它直接連接的網絡的距離定義為1，如果距離為n，則表示它到目的網絡途中經過n個路由器，即距離給出了該路由要經過的路由器個數。RIP通過限制從源到目的的最大跳數來防止路由環路，最大值為15。如果路由器收到了含有新的或改變的表項的路由更新信息，且把度量值加1后成為無窮大（即16），那么就認為該目的網絡不可到達。目的子網地址發送接口下一站路由器地址路由距離度量路由來源192.168.3.0E0—1直連192.168.0.0E1—1直連初始路由表192.168.1.0E1192.168.0.12RIP從R1獲得到網絡W的路由信息

3．無窮計數問題與其他距離向量協議一樣，RIP協議也會遇到無窮計數問題。在6.5.3節距離向量路由算法中介紹的幾種解決方法在RIP協議的實現中也可以采用。例如，RIP實現了水平分割和抑制規則來防止路由信息的錯誤傳播。此外，RIP的跳步數限制也防止了無限增長而產生路由環路。finalwordInternet最早使用的是RIP協議，它適合于小型網絡系統。如果一個自治系統很大，RIP協議的運行會存在一些問題，并且還會受到無窮計數問題的困擾。因此，從1988年開始IETF內部網關協議（IGP）工作組制定了開放最短路徑優先協議（OSPF），并在1990年成為標準。目前，OSPF是Internet上的主要內部網關協議。OSPF是一種鏈路狀態路由選擇協議。每一個運行OSPF協議的路由器維護本地鏈路狀態信息，并且通過擴散的方法把已更新的本地鏈路狀態信息廣播給自治系統中的其他所有路由器。通過這種方法，每個路由器都可以知道自治系統內部的拓撲結構和鏈路狀態信息，并可以構造自己的鏈路狀態數據庫。然后，每個路由器在本地根據這個數據庫中的信息，利用Dijkstra最短路徑算法可以構造一個以其自己為根到該自治系統內部各個網絡的最短路徑樹。其它的功能。。。。。。6.6.3開放最短路徑優先協議（OSPF）1．網絡拓撲數據庫按照不同網絡的特性，OSPF把網絡分為3類。①點到點網絡②廣播網絡（broadcastnetwork）③非廣播網絡（no-broadcastnetwork）圖6-30點到點網絡及其拓撲結構圖6-31多訪問網絡及其拓撲結構圖6-32stub網絡及其拓撲結構圖6-33OSPF中的路由器類型2．區域由于自治系統可能越來越大，越來越難以管理，OSPF引入了區域（area）的概念，即把許多網絡和主機組合在一起，再加上連接在這些網絡上的路由器，這些合起來稱為一個區域。一個自治系統可分為多個區域，每個區域包括一組網絡和路由器。一個區域內的路由器相互之間交換所有的信息，而對于同一個自治系統內的其他區域內的路由器則隱蔽它的詳細拓撲結構。在每個自治系統內，有一個特殊的區域，稱為主干區域（backbonearea）。OSPF中的區域、路由器圖6-33OSPF中的路由器類型3．OSPF協議的執行過程OSPF把路由器之間要交換的網絡拓撲結構信息稱為鏈路狀態公告（LinkStateAdvertisement，LSA）。OSPF規定，在多訪問網絡中，要選出一臺指定路由器（DesignatedRouter，DR）和一臺備份指定路由器（BackupDesignatedRouter，BDR）。DR和網絡上其他路由器交換LSA信息，并代表它所在網絡的LSA。BDR則在DR出現故障時快速轉變為DR，保證網絡的正常運轉。毗鄰關系當一個運行OSPF協議的路由器啟動后，它試圖與相鄰的路由器建立毗鄰關系，它會定期向與其相連的所有鏈路（各個網絡接口）上發送Hello消息。OSPF規定，僅在如下路由器之間建立毗鄰關系：①點到點網絡和虛擬鏈路兩端的路由器之間；②指定路由器（DR）和同一網絡上的所有其他路由器之間；③備份指定路由器（BDR）和同一網絡上的所有其他路由器之間。

表6-12OSPF的LSA報文類型報文類型描述Hello用于發現誰是鄰居LinkStateUpdate為鄰居提供發送者的鏈路狀態更新LinkStateAck確認鏈路狀態更新DatabaseDescription通知發送者有哪些更新LinkStateRequest從伙伴處請求信息finalword路由器通過擴散把自己的鏈路狀態信息通告給它所在區域的其他路由器。這樣，每個路由器都可以構建一個它所在區域的鏈路狀態數據庫，并利用Dijkstra算法計算出最短路徑。主干區域中的路由器也進行這樣的過程，而且它還從區域邊界路由器獲取信息，計算出從主干到每個非主干區域的最短路徑，并將這一信息再分發給區域邊界路由器，由該路由器在它的區域中廣播該信息。通過這個信息，區域內部的路由器在轉發到其他區域的分組時可以選擇到主干區域的最合適的區域邊界路由器。

6.6.4外部網關協議EGP外部網關協議（EGP）是一種用于自治系統之間交換路由信息的協議。EGP是Internet早期使用的一種外部網關路由協議。通過EGP交換的消息都是只經過1跳。也就是說，交換EGP消息的兩個路由器必須是外部鄰居，不能有中間結點。路由器當收到不是發給自己的EGP消息時，可以將其丟棄。EGP協議包括鄰居獲取、鄰居可達性確認、網絡可達性確認3個過程:①鄰居獲取②鄰居可達性③網絡可達性

6.6.5邊界網關協議BGPBGP協議是一種距離向量協議（嚴格地講，應該是路徑向量協議），但它與其他同類協議又有很大不同。每個BGP路由器記錄的是使用的實際路由，而不是到各個目的網絡的開銷。在BGP協議傳輸的路徑信息中，不僅包括到達目的網絡的距離信息，還包括到達目的地所要穿越的各個自治系統的編號。BGP協議可以很容易地用這些信息構造出各個自治系統之間的連通圖，并且能夠檢測出可能存在的路由環路，也就可以避免RIP協議中的無窮計數問題。BGP消息是通過一條BGP路由器之間的TCP協議（發送端口為179）連接來發送的，通過使用可靠的TCP協議，減少了消息傳遞可能要完成的分段、重傳、確認和序號功能。BGP采用的是增量更新機制，即只有在路由狀況發生變化時，才把變化的信息傳輸給對方。BGP協議定義了4種類型的消息：①Open，建立和另一個路由器的鄰居關系；②Update，傳輸一個單一路由的消息和（或）列出取消的多條路由；③KeepAlive，確認Open消息、定期維持鄰居關系；④Notification，檢測到錯誤時發送。BGP協議和EGP協議一樣，也包括鄰居獲取、鄰居可達性確認和網絡可達性確認3個過程。①鄰居獲取②鄰居可達性③網絡可達性6.7IP多播與IGMP6.7.1IP多播的基本概念IPv4定義了3種IP分組的傳輸：①單播（unicast）②廣播（broadcast）③多播（multicast）

圖6-34單播和多播的IP分組的傳輸方式6.7.2IP多播地址和多播組IP多播是指一個IP分組向一個“主機組”的傳送，這個包含零個或多個主機的主機組由一個單獨的IP地址標識。主機組地址也稱為多播地址或D類地址。D類地址是動態分配和恢復的瞬態地址。每一個多播組對應于動態分配的一個D類地址。當多播組結束多播時，相對應的D類地址將被回收，用于以后的多播。在D類地址的分配中，IETF建議遵循以下的原則：①全球范圍，224.0.1.0～238.255.255.255；②有限范圍，239.0.0.0～239.255.255.255；③本地站點范圍，239.253.0.0～239.253.0.16；④本地機構范圍，239.192.0.0～239.192.0.14。

6.7.3Internet組管理協議IGMPInternet組管理協議（InternetGroupManagementProtocol，IGMP）是多播中的一個非常重要的協議，它運行在IP站點和它所在的子網多播路由器之間，用來控制多播組成員的加入和退出。目前有兩個版本：IGMPv1（RFC1112）和IGMPv2（RF