對新型網絡路由機制的思考

摘要：路由是網絡的結構基石，新型網絡路由機制是構建新型網絡體系的必需。目前網際層的路由本質上是所謂的“單下一跳路由”機制，解決網絡傳輸擁塞問題的一個根本措施在于改變當前網絡單下一跳的選路模式，允許多條路徑的并行傳輸。邊界網關協議(BGP)是目前Internet唯一采用的域間路由協議，針對當前域間路由系統面臨的規模可擴展性問題，文章提出了一個規模可擴展的新型分層域間路由架構(s-idra)。除了可擴展性以外，路由體系還面臨其他挑戰，比如安全性、服務質量(QoS)、組播、移動、動態網絡拓撲等等。路由協議尤其是未來新型信息網絡體系結構的路由協議的研究任重而道遠。

關鍵詞：網絡體系結構；域內路由；域間路由

Abstract: Since routing is the cornerstone of a network， constructing new routing mechanisms is indispensable to novel network architectures. The present nature of current routing mechanisms in the network layer is based on the so-called single-next-hop. Therefore， a radical solution to network transmission congestion problem is required to change from the single-next-hop mode to something else to allow simultaneous traffic transmission on multiple paths. The Border Gateway Protocol (BGP) is now the unique inter-domain routing protocol used in the Internet. A new scalable hierarchical inter-domain routing architecture (s-idra) is proposed here to deal with the scalability problem posed to the current inter-domain routing. Other than scalability， the routing system is facing other challenges such as security， Quality of Service (QoS)， multicast， mobility and adaptability to dynamic network topologies. Researches on routing protocols， especially on those employed in future information network architectures， will shoulder heavy responsibilities.

Key words: network architecture; intra-domain routing; inter-domain routing

基金項目：國家重點基礎研究發展規劃項目(“973”計劃)( 2007CB307102)；國家高技術研究發展計劃資助項目(“863”計劃)( 2007AA01Z212)

作為一種日益重要的信息網絡，Internet以“數據信息傳遞”為基本宗旨，從為人類科學研究提供便利開始，朝著促進人類社會的政治、經濟、教育、軍事等等各個領域發生深刻變革的方向演變。被極大拓展的應用范圍使得Internet的設計結構所對應的基本能力與當今對它的能力要求產生了明顯的矛盾。針對這一矛盾的解決，學術界目前達成了這樣的共識，即，為Internet構建新型的體系結構是滿足應用環境對其要求、全面而顯著提升其能力進而解決這一矛盾的根本途徑。學術界的這一共識構成了新型信息網絡體系結構研究的強大推動力，美國的GENI[1]和NewArch[2]計劃、歐盟的Euro-NGI計劃[3]、中國的863計劃和973計劃等都展開了針對未來新型信息網絡體系結構的全面研究。

對于新型的Internet體系結構，需要重新反思的重點包括Internet網絡結構的功能劃分、協議層定義、透明性、魯棒性、端到端、異構互聯等根本問題。盡管目前學術界尚未在Internet新型體系結構的具體形態上取得實質性突破并達成共識，但是在“新型Internet體系結構依然需要網際互聯功能”上取得了較為廣泛的一致，就是說，仍由網際互聯層以“信息轉發”的形式承擔整個Internet最為基本的“信息傳遞”功能。在Internet新型體系結構的背景下，需要重新反思其協議體系中網際互聯層的信息傳遞模式、尋址、轉發、路由、匯聚、擁塞控制等根本問題。網際互聯層的根本功能在于“在多個異種物理網絡之間發現和建立信息傳遞的路徑并在實施通信的多個實體之間完成信息的傳遞”，顯然路由是構成網際互聯層完成“互聯、選路、轉發”這一根本任務所必備而重要的基礎功能。

1 Internet路由結構的研究

當前Internet中的路由系統是一種層次式的結構，在劃分不同管理域的基礎上，將路由分為“域內路由”和“域間路由”兩個不同層面。這種層次式路由結構的本質是在微觀和宏觀兩個層面實現局部路由結構與全局路由結構的“分離”或“去耦合”，這種“分離”既實現了Internet網際層在整體路由結構層面的統一性，也同時在個體路由結構層面上實現了最大程度的靈活性和適應性。另一方面，這種“分離”思想以及兩級路由結構也為將其進一步推廣為更為一般的層次式路由體系提供了良好的理論和技術基礎。

針對Internet新型體系結構而展開的路由研究大體上按兩種思路沿兩個方向進行，一是繼續研究等級制/層次式的路由結構，二是發展全新的路由系統(如“扁平底”、“立體的”等等)。作者認為，Internet網際層的整體路由結構最有可能以“演進”而非“變革”的方式繼續發展。Internet的網絡系統必然是一種特定的復雜系統，對于復雜系統，其結構按怎樣的模式發展？目前存在兩種不同的、也是相互對立的觀點，第一，漸變式的“進化觀點”，第二，突變式的“變革觀點”。“進化觀點”注重系統功能和結構的漸進、改良，而“變革觀點”則強調突變、革命。值得指出的是，即便持有“變革觀點”，也有相當的學者認為包括Internet體系結構在內的復雜系統其結構的變化在某種程度上也存在明顯的“非均勻性”，比如，其核心結構要素的變化相對比較緩慢而溫和，因而保持相對的穩定性。許多典型的生物系統和物理復雜系統的演進均遵循所謂這種“核心漸變”的發展模式。對于Internet的網絡系統而言，有人將其網絡協議結構比作一個“沙漏”結構，這樣，Internet網絡系統之核心結構要素正是它的網際互聯層。

縱觀Internet產生和發展的歷程可以看到，其外界環境以及外部對其需求、應用的發展要遠遠快于結構本身的發展。從這一基本事實出發不難想象，人們在任何一個時段為未來Internet構想的“超前”需求，進而為其構建的“超前”結構其“有效期”都是極為有限的，相反，基于“漸變”的演進觀念，構建具有強“自適應”、“自我演進”能力的“適度超前”結構，不失為一種合理的選擇，尤其對于作為Internet網絡系統核心結構要素的Internet網際層路由系統更是如此。需要進一步強調的是，演進式的構造方法可以使被研究對象與其應用和發展環境演進產生強關聯，從而最有可能使得環境與結構的演進發展產生最為密切、因而是最為有效和雙向的良性互動。

在Internet的新型網絡體系結構確立之前，基于“構建具有強自適應、自我演進能力的適度超前結構”的思想，繼續深入研究其網際層路由結構的既有問題，一方面，能為探索更為一般的等級/層次的路由結構提供更為清晰、有效的解決方法，以便采用“漸變”方式推動路由結構的演進發展，另一方面也可以為Internet的新型網絡體系結構提供所必要的技術準備。

本文基于“域內”和“域間”兩個層面分別探討“域內路由”和“域間路由”的關鍵問題、研究現狀和發展方向。

2 域內路由問題

目前網際層的路由本質上是所謂的“單下一跳路由”機制，本節分析“單下一跳路由”機制的利與弊，提出并闡述消除“單下一跳路由”弊端的所謂“多下一跳路由”機制。

2.1 單下一跳路由機制是當前網絡擁塞問題的重要根源

目前網際層路由系統采用所謂“單下一跳路由”機制。單下一跳路由是指每個路由器將去往相同網絡出口所有數據分組均通過其確定的某一個下一跳鏈路進行轉發。導致單下一跳路由的根本原因是路由協議采用的選路算法總是計算節點對之間的最優路徑，因而導致信息分組沿最優路徑傳輸，網絡流量于是總是傾向占用處理能力強的節點和鏈路。網絡中不同節點對的最優路徑趨向重疊，而且這種最優路徑的重疊在時間上保持相對穩定，這使得某些節點和鏈路被長時間過多地占用，傳輸負荷過大，時常導致局部網絡擁塞。從總體上看，當前的“單下一跳路由”機制雖然發現并建立了分組傳送的“最優路徑”，但卻使得網絡中各節點和鏈路對于傳輸信息分組的作用極其不均衡，在某些節點、鏈路持續擁塞的同時，其他的幾乎持續閑置。

例如：在圖1網絡中，鏈路上數字表示傳輸距離。“單下一跳路由”機制下的路由算法以“最短”為目標算出節點之間傳輸信息分組的路徑，紅色箭頭標明其他各個節點去往節點A的單一路徑；計算任兩個節點之間的最短路徑，可以發現它們與當前紅色標明的路徑是重疊的，只是傳輸的方向可能不同。紅色鏈路組成網絡傳輸的最優路徑，網絡所有信息分組的傳輸都由這些紅色鏈路承擔，從而當前網絡從E1到B1的傳輸所經歷的E1→D1→C1→B1的鏈路和節點就可能發生擁塞，而其他節點和其他鏈路因不參與中間數據的轉發而相對空閑，黑色標明的鏈路始終閑置。可見，“單下一跳路由”機制下的路由算法導致“最優路徑相對穩定、其他鏈路則全部閑置”局面的形成，從而為網絡實際發生局部擁塞建立了條件。

解決網絡傳輸擁塞問題的一個根本措施在于改變當前網絡單下一跳的選路模式，允許多條路徑的并行傳輸，即，每個節點采用多下一跳鏈路并行轉發的路由機制，最終使得在微觀上網絡各鏈路的利用率趨向均衡，而在宏觀上使得網絡流量在空間上均勻分布，在整體上趨向均衡。

2.2 多下一跳路由是實現“盡力傳送”網絡設計目標的重要方面

IP網絡的一個設計思想是數據信息分組的“盡力傳送”，在可以有效預見的未來，“盡力傳送”仍然是一種典型的網絡模式。當前的實現思路是根據目的地址選擇一條最優路徑傳輸信息分組。也就是說，調用最好的資源來干一件事情。然而，我們認為僅僅這樣還沒有達到“盡力傳送”的設計目標，還應該盡可能地調用更多的資源來完成同一件事，極端的情況是，我們可以調動網絡內的所有鏈路都參與對具有相同網絡出口的信息分組的傳輸。將這一想法落實到單個路由節點，可以這樣理解：對于需到達某個出口的分組，該路由器所屬鏈路接口可分為兩類，一類是可以接收信息分組，另外一類是可以向其他鄰居轉發該分組。也就是說，到達同一目的地的諸多分組可以在單個路由器上實現多下一跳鏈路的分流、分路轉發。多下一跳路由要完成的事情就是確定目的網絡的多個下一跳轉發鏈路接口，多下一跳路由表項在形式上表現為每個目的網絡對應多個下一跳接口。

在單下一跳路由網絡中，同一目的地的數據分組通過單一路徑進行傳輸。在多下一跳路由網絡中，路由器對于任何去往相同網絡出口的分組都可以在多個下一跳中并行地分流轉發，通過每個下一跳流出的數據分組都可在局部子網中分流傳輸，直至出口節點。對比可知，多下一跳路由機制可以明顯提高數據傳輸的效率，使得網絡中各資源的利用率趨于均衡，使得網絡中的流量總體趨向均衡，令網絡傳輸過程中的擁塞程度降到最低。

2.3 多下一跳路由機制可以改善網絡的可用性和抗毀性

在當前的單下一跳路由網絡中，當網絡某處出現故障，路由協議必須計算新的路由。如果在路由重新計算的過程中路由尚未收斂，網絡就不能保證相關數據業務的可靠傳輸。而在多下一跳路由網絡中，對于去往相同網絡出口的分組，路由器有多個下一跳鏈路接口可以對其并行地分流轉發，如果發現鏈路層的某個接口出現故障，路由器可以快速中止該接口的轉發任務，屏蔽該接口，并通過其他接口正常進行數據的可靠轉發。雖然在出現故障后，多下一跳路由協議也需要進行路由計算，但是計算過程中，網絡的正常業務不會中斷。可見，多下一跳路由機制可以顯著改善網絡的可用性和抗毀性。

2.4 多下一跳路由機制為QoS選路提供了可靠基石

Internet為傳送信息分組所進行的選路過程可以分為兩步：(1) 標識可行路徑：路由協議確定通過網絡中的哪些路徑可以到達目的網絡；(2) 選擇傳輸路徑：在第一步提供的路徑集合中，為數據分組的轉發挑選具體的傳輸路徑。

在傳統路由機制約束下，分組選路過程實際上將兩者合二為一，或者說只是提供一條路徑，分組傳輸的路徑沒有可選性。基于此，有關“多路由尺度的路徑選擇”問題的研究，目前已有思路考慮的是：如何綜合多類路由因素，提供一條最優的傳輸路徑。他們只是提供一條可行路徑，其他可行路徑全部閑置。

對于這個問題的研究，我們認為：所有可行路徑都應該放入可行路徑集合而不應該主動將其閑置。各類路由因素只是路徑特征的描述信息，它只能衡量路徑的“好壞”，不能否認路徑本身的存在性，它們本身無法成為確定某條路到達某個網絡出口可行路徑的唯一判據，而只是“選擇傳輸路徑”的數量標尺，因此，根據路由參數選路的過程不應該影響網絡對于數據分組的正常傳輸過程。基于此，我們可將選路過程的第一步劃分出去，另行研究，要求它提供所有可行路徑；同時，將基于多路由尺度的路徑選擇問題局限于第二步，路徑的選擇過程不影響路徑的分組傳輸功能；具體路徑的選擇也變成策略類的選擇，從而可以根據各種需求，靈活多樣地進行調整。

服務質量(QoS)問題，本質上是根據多個路由參數選擇能夠滿足QoS要求的“好”路。在單下一跳路由機制約束下，這是一個NP完全問題。也就是說，單下一跳路由機制和QoS的需求是矛盾的。在多下一路由機制的框架下，QoS問題其實和分組選路過程的第一步實現了分離，只和第二步相關，也就是說，QoS選路是在已提供的諸多可行路徑中選擇滿足要求的“好”路，即使這個要求通常涉及多個路由參數，這個過程不會影響網絡的分組傳輸過程，可以自由進行。

3 域間路由問題

邊界網關協議(BGP)[4]是目前Internet唯一采用的域間路由協議。該協議的基本功能是與其他BGP自治系統交換網絡層的可達信息，構造全球路由表，以使數據分組在Internet上全球可達。

BGP協議所具有的基于前綴、路徑適量、策略路由和增量式更新4個屬性，要求全球路由表必須包含路由器學習到的所有可達前綴，而對每個可達前綴，必須包含完整的自治系統路徑信息(AS PATH信息)，對每個AS PATH，必須存儲所有相關的路徑屬性(如度量、本地優選等)以供選擇最優路徑，全球路由器還必須存儲所有學習到的路由信息。

假設M表示整個全球路由表占用的內存空間，N_prefix表示全球路由表中可達前綴個數，N_path表示可達某個前綴的路徑個數，全球路由表中每個可達路徑及相關屬性所占內存空間相同且表示為R，則有下式。

M = N_prefix×N_path×R (1)

根據路由觀察(RouteViews)得到的數據[5]，2007年12月4日全球路由表的N_prefix= 246 778，N_path的數學期望值為36，最大值為43，最小值為1。N_prefix＞＞N_path，M是O(N_prefix)級。值得注意的是，近10年來，N_prefix呈現出指數級增長。圖2給出了從1989年7月1日至2007年12月4日全球路由表的N_prefix增長圖[6]。

導致N_prefix指數級增長的原因主要包括有多宿主、聚合故障、負載均衡技術及地址分段[7]。為了獲得更好的連接性，大量的客戶網絡選擇到多個提供商網絡的多條連接。目前Internet中多宿主自治系統(Multi-homed ASes)已經占全部自治系統的70%[8]。由于從一個提供商處獲得的前綴難以被其他提供商網絡聚合，所以多宿主技術會通常使得全球路由表中增加額外表項，如圖3示。有研究發現：多宿主技術的應用已經向全球路由表中引入20%~30%左右的額外前綴。因聚合故障，全球路由表存在接近15%~20%的前綴可被聚合卻未被聚合的路由表項。不能聚合由相同自治系統所發起前綴的另一個原因是負載均衡。如圖4示，Stub_AS₁通過分別向Transit_AS₁和Transit_AS₂通告不同的子前綴，以達到鏈路Link1和Link2上輸入流量均衡的目的。目前，負載均衡已經引入20%~ 25%的額外前綴。自治系統本身就可能擁有多個不可聚合的地址分段，如圖5示。應予特別關注的是，地址分段引入的額外前綴最多，接近75%。

N_prefix指數級增長所引發的直接后果是網絡的規模可擴展性變差。根據解決問題的著眼點不同，當前域間路由系統面臨的規模可擴展性問題的解決方案分為以下4類：

(1)提出新的域間路由協議，包括緊湊路由(compact routing)[9]，混合鏈路狀態路徑矢量(HLP)[10]等。世界Internet研究中心 (CAIDA)的Krioukov教授認為導致域間路由可擴展性差的根本原因是缺乏能夠嚴格保證性能的尋找拓撲中任意兩點間最短路徑的路由需求。因為要滿足此路由需求，路由器需要獲得關于網絡拓撲的全部知識，這就意味著巨大的信息量，可擴展性差。因此，Krioukov教授將研究路徑伸展度(Stretch)和路由表大小之間平衡的compact routing應用到Internet域間路由，產生了不錯的結果[11]。但是，compact routing并不能直接應用于域間路由，因為域間路由是策略路由。當compact routing考慮到策略后，是否還能夠具有良好的可擴展性目前還不能夠確定。HLP協議是一種混合鏈路狀態和路徑矢量路由算法的新型域間路由協議，與基于前綴的BGP協議不同的是，HLP協議是基于自治系統的，其可擴展性得到了一定的改進。

(2)縮減N prefix的方案，典型的是核心路由器完整覆蓋(CRIO)[12]。CRIO技術是一種使用IP隧道縮減全球路由表的技術，但它以更長的路徑為代價。CRIO隔離由第1層Internet服務提供商(tier-1 ISPs)構成的傳輸網和客戶網，數據信息分組在傳輸網中通過隧道傳輸，客戶網可根據tier-1 ISPs通告的可達“虛前綴”(如，/8)來選擇隧道入口。

(3)縮減N path的方案，典型的是健忘路由(Forgetful routing)[13]。Forgetful routing的主要思想是計算到達相同前綴每個路由的下次使用時間，并壓縮最后使用路由，以不影響路由選擇過程，并且，當被壓縮路由被選擇為最優路由時，通過請求初始發送該路由信息的對等體重新發送來恢復被壓縮的路由。Forgetful routing不要求修改BGP協議，可增量式布署且而不會影響收斂。

(4)同時縮減N prefix和N path的方案，典型的是原子路由(Atomized routing)[14]。Atomized routing將擁有相同AS PATH的前綴構成一個稱為“atoms”的前綴集合，這些atoms在全球范圍內計算且被用于路由數據包。

針對當前域間路由系統面臨的規模可擴展性問題，我們在此提出一個規模可擴展的新型分層域間路由架構(s-idra)，如圖6示。該結構含有“端接”和“中介”兩類不同的自治域(AD)，“端接自治域”v-Origin AD是指發起和接收數據信息分組的自治域；“中介自治域”v-Transit AD是指只負責轉發數據信息分組的自治域。所有v-Transit AD構成一個傳輸網絡，且v-Transit AD中的路由器運行域間路由協議，構造一個基于v-Transit AD的全球路由表。基于s-idra的映射表建立機制，構建一個全球映射表，包括表項(主機位置標識，v-Origin AD， v-Transit AD)。當v-Origin AD中邊界路由器收到出域數據信息分組后，首先根據目的主機的位置標識查找全球映射表，獲得目的主機所在的v-Origin AD標識和v-Transit AD標識，并根據v-Transit AD標識封裝信息分組，轉發到傳輸網。傳輸網中的路由器根據目的v-Transit AD標識轉發信息分組。在s-idra中，v-Origin AD中的邊界路由器只保存全球映射表，v-Transit AD中的路由器只保持全球路由表。需要說明的是，v-Origin AD和v-Transit AD是一種“邏輯(virtual)”域間路由實體，若現實中的自治域既發起和接收數據信息分組，又為其他自治域中轉自治域信息分組，那么它既是v-Origin AD又是v-Transit AD。

s-idra的全球路由表基于v-Transit AD。以Internet數據[2]為例說明，2007年12月4日，Internet擁有4 244個Transit AS。并且，Transit AS呈現出線性增長，增長趨勢緩慢[8]。從而，s-idra具有良好的規模可擴展性，且增長可控。s-idra中，以映射表替代路由表的部分功能，管理簡單，因為分發映射表比分發路由簡單。映射表項在任意地點都是相同的，而全球路由表項在每個路由器上是不同的。并且，給定一個全球路由表項，判斷它是否正確是困難的，因為路由表項的正確與否依賴于其他路由器的狀態，而映射表項的正確性則易于判斷。另外，s-idra是一個域間路由架構，傳輸網具有域間路由協議無關性，可采用任意域間路由協議，例如緊湊策略路由協議。s-idra隔離了傳輸網和客戶網，符合Internet網絡拓撲的發展趨勢。在SIGCOMM 2007會議上，Olivera等人公布了Internet網絡拓撲發展趨勢的最新研究成果：提供商網絡和客戶網絡拓撲表現出不同的發展趨勢，分別為客戶網絡大量增加，其增長率是提供商網絡的3.6倍，而提供商網絡的連接愈加緊密。在這樣的背景之下引入s-idra，在隔離傳輸網和客戶網的同時也可以增加了傳輸網的穩定性和安全性。

4 結束語

路由體系良好的可擴展性意味著路由表項呈線性、充其量呈多項式增長。但現實是，多種因素導致了路由表項呈指數增長，龐大的路由表及路由表項指數增長的直接后果是分組傳送性能的顯著下降。在部署具有龐大地址空間的IPv6協議之后，可擴展性可能面臨更為嚴峻的挑戰。除了可擴展性以外，路由體系還面臨其他挑戰，比如安全性、服務質量、組播、移動、動態網絡拓撲等等。以服務質量為例，就各種網絡業務流量類型所占的比例而言，預計到2010年，以IPTV/VoD為代表的流媒體業務類型將會占到接入網和MAN網絡流量的80%以上，而這些占有絕對份額的流媒體業務需要嚴格的服務質量保證，從接入網、MAN甚至核心骨干網的路由層面支持這種保證將會成為重要的手段。

此外，無論是域內還是域間路由協議均不支持高度變化的動態網絡拓撲和能力/特性非對稱的傳送路徑，而支持這些特性恰恰是支持移動性的無線網絡、移動網絡(NEMO)所需要的路由協議。路由協議尤其是未來新型信息網絡體系結構的路由協議的研究任重而道遠。

信息網絡已經走過了為經濟社會提供便利、促進經濟社會發展和部分改變社會運行模式的歷程，展望未來，它必然發揮引領社會未來走向和發展的作用。有理由預言，2020年左右，Internet將從人類社會的“信息基礎設施”逐步演進為全球的“社會基礎設施”。

5 參考文獻

[1] GENI Planning Group. GENI design principles[EB/OL]. http://www.geni.net/docs/

20060901_ieee_computer_geni_design_principles.pdf.

[2] CLARK D， SOLLINS K， WROCLAWSKI J， et al. New arch: Future generation Internet architecture[R/OL]. White paper. http://www.isi.edu/newarch/iDOCS/final. finalreport.pdf， 2003.

[3] Sixth Framework Programme， Information Society Technologies (IST). Design and engineering of the next generation Internet， towards convergent multi-service networks[EB/OL]. http://www.ist-bread.org/pdf/

Euro_NGI_vision.pdf

[4] REKHTER Y， LI T， HARES S. A border gateway protocol 4 (BGP-4) [R]. RFC4271. 2006.

[5] University of Oregon Route Views Project[EB/OL].2004-06-20.http://www.routeviews.org/.

[6] BGP routing table analysis reports [EB/OL]. http://bgp.potaroo.net

[7] BU T， GAO L X， TOWSLEY D. On characterizing BGP routing table growth[C]// Proceedings of Global Telecommunications Conference (GLOBECOM2002): Vol 3， Nov 17-21， 2002， Taipei， China. Piscataway， NJ， USA: IEEE， 2002: 2185-2189.

[8] OLIVEIRA R， ZHANG B C， ZHANG L X. Observing the evolution of Internet AS topology[C]// Proceedings of Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications (SIGCOMM 2007)， Aug 27-31， 2007， Kyoto， Japan. New York， NY， USA: ACM， 2007:313-324.

[9] THORUP M， ZWICK U. Compact routing schemes[C]// Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures， Jul 3-6， 2001，Crete Island， Greece. 2001:1-10.

[10] SUBRAMANIAN L， CAESAR M， EE C T， et al. HLP: A next generation interdomain routing protocol[C]// Proceedings of Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications (SIGCOMM2005)， Aug 22-26， 2005， Philadelphia，PA， USA. New York，NY，USA: ACM， 2005:13-24.

[11] KRIOUKOV D， FALL K， YANG X. Compact routing on Internet-like graphs[C]// Proceedings of 23rd Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2004)， Mar 7-11， 2004， Hong Kong， China. Piscataway，NJ，USA:IEEE， 2004: 209-219.

[12] ZHANG Xinyang， FRANCIS P， WANG Jia，et al. Scaling IP routing with the core router-integrated overlay[C]// Proceedings of 14th IEEE International International Conference on Network Protocols， Nov 12-15， 2006， Santa Barbara， CA，USA. Piscataway，NJ，USA:IEEE，2006:147-156 .

[13] KARPILOVSKY E， REXFORD J. Using forgetful routing to control BGP table size[C]// Proceedings of 2nd Conference on Future Networking Technologies(CoNext2006)，Dec 4-7， 2006，Lisbon， Portugal. 2006.

[14] Atoms-atomised routing[EB/OL]. http://www.caida.org/projects/routing/atoms/.

收稿日期：2007-11-15

作者簡介

郭云飛，信息工程大學信息工程學院教授、博士生導師。研究生畢業于北京理工大學。現任信息技術研究所所長、國家數字交換系統工程技術研究中心常務副主任，主要研究方向為信息網絡與交換。主持過多項國家重大科技項目，曾獲國家科技進步一等獎和省部級科技進步一等獎，發表學術論文30余篇。

朱宣勇，信息工程大學講師。博士畢業于信息工程大學。現工作于信息工程大學信息技術研究所，主要從事網絡通信算法尤其是新型路由算法的研究與開發工作。在《IEEE Transactions on Information Theory》、《Finite Fields and Their Applications》、《Mathematics of Computation》、《數學學報》、《應用數學學報》等學術期刊發表論文若干，近5年來在SCI核心期刊發表學術論文7篇。

王娜，信息工程大學信息工程學院在讀博士研究生，講師。主要研究方向為寬帶信息網絡，先后參加了國家863“大規模接入匯聚路由器(ACR)系統性能和關鍵技術研究”、“軍用IPv6實驗網(MNGI)”，“快速自愈路由協議與試驗系統”，國家973項目課題“一體化網絡體系結構模型及交換路由理論與技術”等的研究，已發表論文10余篇。