1、 路由選擇技術路由選擇技術 第第 4-5 講講網(wǎng)絡通用技術-2-v本講提要本講提要 基本概念基本概念 路由選擇的作用路由選擇的作用 電路交換網(wǎng)絡的路由選擇電路交換網(wǎng)絡的路由選擇 分組交換網(wǎng)絡的路由選擇分組交換網(wǎng)絡的路由選擇 IP網(wǎng)絡的路由選擇網(wǎng)絡的路由選擇小結(jié)小結(jié)-3-v基本概念基本概念路由選擇路由選擇在網(wǎng)絡中選擇轉(zhuǎn)接信息的中間節(jié)點以及節(jié)點之間的鏈路，從在網(wǎng)絡中選擇轉(zhuǎn)接信息的中間節(jié)點以及節(jié)點之間的鏈路，從而確定一條連接發(fā)信節(jié)點和收信節(jié)點的信道的過程而確定一條連接發(fā)信節(jié)點和收信節(jié)點的信道的過程電路交換網(wǎng)絡電路交換網(wǎng)絡節(jié)點間的通信路由一般事先確定好，在呼叫建立階段按照確節(jié)點間的通信路由一般事先確定

2、好，在呼叫建立階段按照確定的路由進行連接定的路由進行連接只在確定路由出現(xiàn)溢呼或故障時，才選擇新的路由（迂回路只在確定路由出現(xiàn)溢呼或故障時，才選擇新的路由（迂回路由），路由轉(zhuǎn)接設備稱為交換機由），路由轉(zhuǎn)接設備稱為交換機分組交換網(wǎng)絡分組交換網(wǎng)絡采用存儲轉(zhuǎn)發(fā)方式傳輸分組，每個節(jié)點都需要選擇下一個節(jié)采用存儲轉(zhuǎn)發(fā)方式傳輸分組，每個節(jié)點都需要選擇下一個節(jié)點和鏈路，路由轉(zhuǎn)接設備稱為路由器點和鏈路，路由轉(zhuǎn)接設備稱為路由器-4-路由選擇問題本質(zhì)上是一個優(yōu)化問題，也就是選擇哪路由選擇問題本質(zhì)上是一個優(yōu)化問題，也就是選擇哪條路由更好的問題。優(yōu)化的標準包括跳數(shù)、距離、時條路由更好的問題。優(yōu)化的標準包括跳數(shù)、距離、時延

3、、帶寬、誤碼率、安全性等，優(yōu)化的基本方法是圖延、帶寬、誤碼率、安全性等，優(yōu)化的基本方法是圖論中的最短路算法、最大流算法和最小費用算法論中的最短路算法、最大流算法和最小費用算法硬件路由器（專門的硬件）：專門針對路由功能進行硬件路由器（專門的硬件）：專門針對路由功能進行設計和優(yōu)化的設備，如設計和優(yōu)化的設備，如Cisco 1600、2500、2600系列系列路由器等路由器等軟件路由器：又稱多宿主計算機軟件路由器：又稱多宿主計算機(Multihomed Computer) ，軟路由器可以看成帶有兩個以上網(wǎng)卡，軟路由器可以看成帶有兩個以上網(wǎng)卡(或有兩個或有兩個以上以上IP地址地址)的服務器的服務器v基本

4、概念基本概念-5-v硬件路由器硬件路由器-6-v軟件路由器軟件路由器子網(wǎng)子網(wǎng) 1服務器服務器客戶機客戶機子網(wǎng)子網(wǎng)2服務器服務器客戶機客戶機網(wǎng)卡網(wǎng)卡1網(wǎng)卡網(wǎng)卡2-7-v路由選擇的作用路由選擇的作用路由選擇決定數(shù)據(jù)分組通過哪條路徑傳輸，直接關系路由選擇決定數(shù)據(jù)分組通過哪條路徑傳輸，直接關系到網(wǎng)絡傳輸?shù)拈_銷和數(shù)據(jù)分組的傳輸質(zhì)量到網(wǎng)絡傳輸?shù)拈_銷和數(shù)據(jù)分組的傳輸質(zhì)量路由選擇策略應正確、穩(wěn)定、公正、最佳和簡單，適路由選擇策略應正確、穩(wěn)定、公正、最佳和簡單，適應網(wǎng)絡規(guī)模、網(wǎng)絡拓撲和網(wǎng)絡中數(shù)據(jù)流量的變化應網(wǎng)絡規(guī)模、網(wǎng)絡拓撲和網(wǎng)絡中數(shù)據(jù)流量的變化路由選擇與業(yè)務量控制緊密相關，其主要目標是提高路由選擇與業(yè)務量控制

5、緊密相關，其主要目標是提高網(wǎng)絡正常狀態(tài)下的性能（如電路交換網(wǎng)絡的接通率和網(wǎng)絡正常狀態(tài)下的性能（如電路交換網(wǎng)絡的接通率和分組交換網(wǎng)絡的時延等）分組交換網(wǎng)絡的時延等）選擇什么樣的路由，如何使路由自動適應網(wǎng)絡業(yè)務量選擇什么樣的路由，如何使路由自動適應網(wǎng)絡業(yè)務量和用戶需求的變化、有效利用網(wǎng)絡資源，是網(wǎng)絡管理和用戶需求的變化、有效利用網(wǎng)絡資源，是網(wǎng)絡管理的一項重要問題的一項重要問題-8-v電路交換網(wǎng)絡的路由選擇電路交換網(wǎng)絡的路由選擇電話交換網(wǎng)的基本路由結(jié)構(gòu)電話交換網(wǎng)的基本路由結(jié)構(gòu)大區(qū)中心、省中心、市中心和縣中心大區(qū)中心、省中心、市中心和縣中心 大區(qū)中心和市中大區(qū)中心和市中心心包括基干路由、直達路由和迂回

6、路由包括基干路由、直達路由和迂回路由路由選擇的基本原則路由選擇的基本原則確保傳輸質(zhì)量和信令信號的可靠傳輸確保傳輸質(zhì)量和信令信號的可靠傳輸路由選擇應有明確的規(guī)律性，確保路由選擇不出現(xiàn)死循環(huán)路由選擇應有明確的規(guī)律性，確保路由選擇不出現(xiàn)死循環(huán)路由選擇應首先選擇電路段數(shù)少的路由路由選擇應首先選擇電路段數(shù)少的路由在業(yè)務量不溢出的情況下優(yōu)先選擇直達路由在業(yè)務量不溢出的情況下優(yōu)先選擇直達路由能夠在低等級網(wǎng)絡中疏通的話務盡量在低等級疏通能夠在低等級網(wǎng)絡中疏通的話務盡量在低等級疏通-9-v電路交換網(wǎng)絡的路由選擇方式電路交換網(wǎng)絡的路由選擇方式靜態(tài)路由選擇靜態(tài)路由選擇發(fā)端交換局至收端交換局的路由選擇順序是固定不變的

7、發(fā)端交換局至收端交換局的路由選擇順序是固定不變的網(wǎng)絡各部分負荷不均衡、不能充分利用網(wǎng)絡資源、接通率較網(wǎng)絡各部分負荷不均衡、不能充分利用網(wǎng)絡資源、接通率較低低動態(tài)路由選擇動態(tài)路由選擇發(fā)端交換局至收端交換局的路由及其選擇順序可動態(tài)變化發(fā)端交換局至收端交換局的路由及其選擇順序可動態(tài)變化包括時變動態(tài)路由選擇和態(tài)變動態(tài)路由選擇，前者隨時間的包括時變動態(tài)路由選擇和態(tài)變動態(tài)路由選擇，前者隨時間的變化而變化，后者隨網(wǎng)絡中負荷的變化而變化（實現(xiàn)相對復變化而變化，后者隨網(wǎng)絡中負荷的變化而變化（實現(xiàn)相對復雜）雜）可以提高資源利用率、節(jié)省網(wǎng)絡投資、提高服務質(zhì)量可以提高資源利用率、節(jié)省網(wǎng)絡投資、提高服務質(zhì)量特別適合于網(wǎng)

8、絡規(guī)模較大、交換節(jié)點數(shù)量較多、業(yè)務量較大特別適合于網(wǎng)絡規(guī)模較大、交換節(jié)點數(shù)量較多、業(yè)務量較大的情況的情況-10-v分組交換網(wǎng)絡的路由選擇分組交換網(wǎng)絡的路由選擇路由選擇的要求路由選擇的要求正確性：確保分組從源節(jié)點傳送到目的節(jié)點正確性：確保分組從源節(jié)點傳送到目的節(jié)點簡單性：實現(xiàn)方便，軟硬件開銷小簡單性：實現(xiàn)方便，軟硬件開銷小可靠性：能長時間無故障運行可靠性：能長時間無故障運行公平性：每個節(jié)點都有機會傳送信息公平性：每個節(jié)點都有機會傳送信息最優(yōu)化：盡量選取最優(yōu)化：盡量選取“好的好的”路由，以適應網(wǎng)絡規(guī)模、拓撲結(jié)構(gòu)路由，以適應網(wǎng)絡規(guī)模、拓撲結(jié)構(gòu)和業(yè)務量的變化和業(yè)務量的變化路由選擇的指標路由選擇的指標跳

9、數(shù)跳數(shù)時延時延吞吐量吞吐量-11-v路由選擇策略和方法路由選擇策略和方法靜態(tài)路由選擇策略靜態(tài)路由選擇策略擴散式擴散式選擇擴散式選擇擴散式隨機式隨機式固定式固定式動態(tài)路由選擇策略動態(tài)路由選擇策略集中式集中式孤立式孤立式分布式分布式分層式分層式-12-v靜態(tài)路由選擇策略靜態(tài)路由選擇策略擴散（洪泛）式擴散（洪泛）式將分組復制到除輸入節(jié)點以外的所有相鄰節(jié)點、可靠將分組復制到除輸入節(jié)點以外的所有相鄰節(jié)點、可靠性高性高存在大量重復分組、網(wǎng)絡資源利用率低、吞吐量小存在大量重復分組、網(wǎng)絡資源利用率低、吞吐量小需要采用計數(shù)器等方式限制分組在網(wǎng)絡中循環(huán)轉(zhuǎn)發(fā)需要采用計數(shù)器等方式限制分組在網(wǎng)絡中循環(huán)轉(zhuǎn)發(fā)適用于負荷較強

10、、規(guī)模較小的網(wǎng)絡適用于負荷較強、規(guī)模較小的網(wǎng)絡選擇擴散式選擇擴散式將分組復制到靠近目的節(jié)點的一部分節(jié)點、也稱多路將分組復制到靠近目的節(jié)點的一部分節(jié)點、也稱多路傳送傳送一定程度上提高了網(wǎng)絡吞吐量一定程度上提高了網(wǎng)絡吞吐量-13-v靜態(tài)路由選擇策略靜態(tài)路由選擇策略隨機式隨機式收到分組的節(jié)點隨機選擇下一跳節(jié)點和鏈路收到分組的節(jié)點隨機選擇下一跳節(jié)點和鏈路實現(xiàn)簡單、但可靠性低實現(xiàn)簡單、但可靠性低固定式固定式每個節(jié)點維護一張人工計算得到的固定路由表，給出每個節(jié)點維護一張人工計算得到的固定路由表，給出了對應所有目的節(jié)點的轉(zhuǎn)發(fā)出口了對應所有目的節(jié)點的轉(zhuǎn)發(fā)出口實現(xiàn)簡單，但不能適應網(wǎng)絡變化實現(xiàn)簡單，但不能適應網(wǎng)絡

11、變化適用于小規(guī)模網(wǎng)絡適用于小規(guī)模網(wǎng)絡-14-v動態(tài)路由選擇策略動態(tài)路由選擇策略集中式路由選擇集中式路由選擇網(wǎng)絡中存在一個路由控制中心（網(wǎng)絡中存在一個路由控制中心（RCC）節(jié)點定期向節(jié)點定期向RCC發(fā)送狀態(tài)信息發(fā)送狀態(tài)信息RCC依據(jù)某種算法為每個節(jié)點計算出最佳路由表，并依據(jù)某種算法為每個節(jié)點計算出最佳路由表，并發(fā)送到各個節(jié)點發(fā)送到各個節(jié)點優(yōu)點：優(yōu)點：RCC能夠依據(jù)當前網(wǎng)絡狀況選擇最佳路由、各能夠依據(jù)當前網(wǎng)絡狀況選擇最佳路由、各個節(jié)點不必計算路由個節(jié)點不必計算路由RCC鏈路業(yè)務量過大、負擔較重、易成為網(wǎng)絡瓶頸，鏈路業(yè)務量過大、負擔較重、易成為網(wǎng)絡瓶頸，并且節(jié)點之間路由更新時間可能不一致并且節(jié)點之間

12、路由更新時間可能不一致-15-v動態(tài)路由選擇策略動態(tài)路由選擇策略孤立式路由選擇孤立式路由選擇節(jié)點選擇路由時，不與其他節(jié)點交換信息，僅依靠自節(jié)點選擇路由時，不與其他節(jié)點交換信息，僅依靠自身擁有的信息身擁有的信息熱土豆（熱土豆（hot potato）算法：節(jié)點收到分組后，將其放）算法：節(jié)點收到分組后，將其放在該節(jié)點最短的輸出隊列中，減少分組的排隊等待時在該節(jié)點最短的輸出隊列中，減少分組的排隊等待時間，但顯然不是最佳路由間，但顯然不是最佳路由反向?qū)W習算法：根據(jù)輸入分組中的路由信息來判決已反向?qū)W習算法：根據(jù)輸入分組中的路由信息來判決已有的路由，如果輸入分組中指出的路由比已有的路由有的路由，如果輸入分組

13、中指出的路由比已有的路由好，則替換原來的路由，經(jīng)過反復學習比較來得到最好，則替換原來的路由，經(jīng)過反復學習比較來得到最佳的路由佳的路由-16-v動態(tài)路由選擇策略動態(tài)路由選擇策略分布式路由選擇分布式路由選擇每個節(jié)點與其相鄰的各節(jié)點交換路由信息，根據(jù)交換每個節(jié)點與其相鄰的各節(jié)點交換路由信息，根據(jù)交換后的信息確定新的路由表后的信息確定新的路由表能夠反映網(wǎng)絡拓撲和業(yè)務量的變化，屬于自適應路由能夠反映網(wǎng)絡拓撲和業(yè)務量的變化，屬于自適應路由分層式路由選擇分層式路由選擇將網(wǎng)絡中的節(jié)點分成若干個區(qū)，每個節(jié)點只需維護區(qū)將網(wǎng)絡中的節(jié)點分成若干個區(qū)，每個節(jié)點只需維護區(qū)內(nèi)的路由信息，區(qū)內(nèi)和區(qū)間可以采用不同的路由選擇內(nèi)的

14、路由信息，區(qū)內(nèi)和區(qū)間可以采用不同的路由選擇方式方式可以減少網(wǎng)絡開銷，適合于網(wǎng)絡規(guī)模較大、節(jié)點數(shù)量可以減少網(wǎng)絡開銷，適合于網(wǎng)絡規(guī)模較大、節(jié)點數(shù)量較多的情況較多的情況-17-vIPIP網(wǎng)絡的路由選擇網(wǎng)絡的路由選擇vIPIP網(wǎng)絡的路由選擇網(wǎng)絡的路由選擇IP網(wǎng)絡是指采用網(wǎng)絡是指采用TCP/IP協(xié)議將大量物理網(wǎng)絡連接協(xié)議將大量物理網(wǎng)絡連接起來構(gòu)成的互聯(lián)網(wǎng)（起來構(gòu)成的互聯(lián)網(wǎng)（internet）與單一網(wǎng)絡中的路由選擇相比，互聯(lián)網(wǎng)中的路由與單一網(wǎng)絡中的路由選擇相比，互聯(lián)網(wǎng)中的路由選擇復雜很多選擇復雜很多網(wǎng)絡中的主機首先要把分組送給同一網(wǎng)絡中用于網(wǎng)間網(wǎng)絡中的主機首先要把分組送給同一網(wǎng)絡中用于網(wǎng)間連接的路由器連接

15、的路由器路由器根據(jù)目的地址選擇合適的路由傳遞到目的網(wǎng)絡路由器根據(jù)目的地址選擇合適的路由傳遞到目的網(wǎng)絡中用于網(wǎng)間連接的路由器中用于網(wǎng)間連接的路由器然后目的網(wǎng)絡的路由器通過內(nèi)部路由協(xié)議把分組送給然后目的網(wǎng)絡的路由器通過內(nèi)部路由協(xié)議把分組送給目的主機目的主機-18-vIPIP網(wǎng)絡的路由選擇網(wǎng)絡的路由選擇vIPIP網(wǎng)絡的路由選擇網(wǎng)絡的路由選擇在互聯(lián)網(wǎng)中，由一個獨立的管理機構(gòu)控制的一組在互聯(lián)網(wǎng)中，由一個獨立的管理機構(gòu)控制的一組網(wǎng)絡和路由器稱為一個自治系統(tǒng)（網(wǎng)絡和路由器稱為一個自治系統(tǒng)（AS）互聯(lián)網(wǎng)包括多個自治系統(tǒng)，每個互聯(lián)網(wǎng)包括多個自治系統(tǒng)，每個AS都有中央權(quán)威都有中央權(quán)威機構(gòu)分配的唯一的編號機構(gòu)分配的

16、唯一的編號AS內(nèi)部使用的路由協(xié)議稱為內(nèi)部網(wǎng)關協(xié)議（內(nèi)部使用的路由協(xié)議稱為內(nèi)部網(wǎng)關協(xié)議（IGP），），AS之間使用的路由協(xié)議稱為外部網(wǎng)關協(xié)議之間使用的路由協(xié)議稱為外部網(wǎng)關協(xié)議（EGP），對應的鄰居路由器分別稱為內(nèi)部鄰居），對應的鄰居路由器分別稱為內(nèi)部鄰居和外部鄰居和外部鄰居典型的典型的IGP包括包括RIP和和OSPF典型的典型的EGP包括包括EGP和和BGP-19-v路由信息協(xié)議（路由信息協(xié)議（RIPRIP）RIP（RoutingInformationProtocols）它是由施樂）它是由施樂（Xerox）在）在70年代開發(fā)的、使用較普遍的內(nèi)部網(wǎng)關協(xié)議，年代開發(fā)的、使用較普遍的內(nèi)部網(wǎng)關協(xié)議，適用

17、于中小型同類網(wǎng)絡，是典型的距離矢量適用于中小型同類網(wǎng)絡，是典型的距離矢量(distance-vector)協(xié)議，以協(xié)議，以hop為度量來計算為度量來計算“距離距離”RIP協(xié)議假定如果從網(wǎng)絡的一個終端到另一個終端的路由協(xié)議假定如果從網(wǎng)絡的一個終端到另一個終端的路由跳數(shù)超過跳數(shù)超過15個，則牽涉到了循環(huán)，因此當一個路徑達到個，則牽涉到了循環(huán)，因此當一個路徑達到16跳，將認為是不可達的（無窮計數(shù)、路由環(huán)回和路由時效跳，將認為是不可達的（無窮計數(shù)、路由環(huán)回和路由時效問題）問題） RIP協(xié)議每隔協(xié)議每隔30秒定期發(fā)送一次更新報文（也可按需詢問秒定期發(fā)送一次更新報文（也可按需詢問路由），據(jù)此更新路由。如果

18、路由器經(jīng)過路由），據(jù)此更新路由。如果路由器經(jīng)過180秒沒有收到秒沒有收到來自某一路由器的路由更新報文，則將所有來自此路由器來自某一路由器的路由更新報文，則將所有來自此路由器的路由信息標志為不可達，若在其后的路由信息標志為不可達，若在其后240秒內(nèi)仍未收到更秒內(nèi)仍未收到更新報文，就將這些路由從路由表中刪除新報文，就將這些路由從路由表中刪除-20-v開放最短路徑優(yōu)先（開放最短路徑優(yōu)先（OSPFOSPF） OSPF（Open Shortest Path First）是一種典型的鏈路狀）是一種典型的鏈路狀態(tài)路由協(xié)議，支持大規(guī)模的網(wǎng)絡態(tài)路由協(xié)議，支持大規(guī)模的網(wǎng)絡 O指指OSPF是公開的，可免費使用；是公

19、開的，可免費使用；SPF是指采用是指采用Dijkstra最短路徑優(yōu)先算法最短路徑優(yōu)先算法 所有的路由器都維持一個鏈路狀態(tài)數(shù)據(jù)庫（網(wǎng)絡拓撲結(jié)構(gòu)所有的路由器都維持一個鏈路狀態(tài)數(shù)據(jù)庫（網(wǎng)絡拓撲結(jié)構(gòu)圖，給每個鏈路狀態(tài)分配序號（圖，給每個鏈路狀態(tài)分配序號（32位）并廣播到自治系統(tǒng)位）并廣播到自治系統(tǒng)內(nèi)的每個路由器，每個路由器據(jù)此分別計算出到每個目的內(nèi)的每個路由器，每個路由器據(jù)此分別計算出到每個目的地的最短路由（分布式）地的最短路由（分布式） 拓樸發(fā)生變化，采用泛洪廣播使各路由器很快重新計算新拓樸發(fā)生變化，采用泛洪廣播使各路由器很快重新計算新的路由表（收斂速度快）的路由表（收斂速度快） 每隔每隔10妙相鄰

20、路由器交換一次妙相鄰路由器交換一次hello報文，如果報文，如果40秒沒有收秒沒有收到到hello報文，則認為對應的路由器不可達報文，則認為對應的路由器不可達-21-v外部網(wǎng)關協(xié)議（外部網(wǎng)關協(xié)議（EGPEGP）是是Internet早期使用的一種外部網(wǎng)關協(xié)議，后來被廣泛使早期使用的一種外部網(wǎng)關協(xié)議，后來被廣泛使用的用的BGP所替代所替代 EGP協(xié)議包括三個過程：鄰居獲取、鄰居可達性確認、網(wǎng)協(xié)議包括三個過程：鄰居獲取、鄰居可達性確認、網(wǎng)絡可達性確認絡可達性確認 EGP協(xié)議所交換的消息都只經(jīng)過協(xié)議所交換的消息都只經(jīng)過1跳，即交換跳，即交換EGP消息的消息的兩個路由器必須是外部鄰居路由器，不會有任何中間路由兩個路由器必須是外部鄰居路由器，不會有任何中間路由器。路由器可以丟棄收到的不是發(fā)給自己的器。路由器可以丟棄收到的不是發(fā)給自己的EGP消息消息EGP通過路由更新來計算路由，通過路由更新來計算路由，EGP的外部網(wǎng)關可以傳遞的外部網(wǎng)關可以傳遞兩種消息：它所在自治系統(tǒng)的可達子網(wǎng)的信息和學習到的兩種消息：它所在自治系統(tǒng)的可達子網(wǎng)的信息和學習到的自治系統(tǒng)之外的消息自治系統(tǒng)之外的消息EGP受到諸多限制，應用很受局限受到諸