[發明專利]BGP引導的實時自治系統級拓撲發現方法

有效

• 申請號: 200910044746.1
• 申請日: 2009-11-12
• 公開（公告）號: CN101714942A
• 公開（公告）日: 2010-05-26
• 發明（設計）人: 彭偉;盧澤新;張曉哲;王宏;胡曉峰;趙鋒;胡寧
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及互聯網上進行實時拓撲發現的方法，尤其是通過域間路由協議BGP(border?gateway?protocol)獲得實時IP(Internet?Protocol)網絡路由信息，利用IP網絡路由信息來引導分布在網絡中的探測節點進行拓撲發現，從而實時地發現互聯網在自治系統AS(autonomous?system)一級的拓撲結構的方法。

背景技術

近年來，互聯網(Internet)得到了快速發展，其規模不斷擴大，網絡結構日益復雜，準確獲取Internet的拓撲結構信息成為一項具有挑戰性的任務。Internet拓撲結構信息可以應用于互聯網協議的研究、網絡測量與分析、網絡流量優化和網絡安全管理等方面。Internet的拓撲結構主要分為域間和域內兩個層次。在域間層次，Internet由多個自治系統AS構成。每個自治系統是一個獨立的管理域，由具有相同路由策略的一組路由器和其它網絡設備相互連接構成，通常被某一個因特網服務提供商ISP(Internet?Service?Provider)擁有。每個自治系統對應有一個編號，稱為AS號，為一個無符合整數。自治系統內運行域內路由協議，如OSPF或IS-IS，自治系統之間運行域間路由協議BGP。域間層次的Internet拓撲又稱為AS級拓撲，域內層次的拓撲則稱為路由器級拓撲。AS級拓撲反映了Internet的宏觀結構，掌握Internet的實時AS拓撲具有重要的意義。實時的AS拓撲信息可用于對等系統即P2P(Peer-to-Peer)系統中peer節點(組成P2P系統的網絡節點)的優化選擇，通過選擇本地peer節點和鄰近peer節點來建立連接，達到優化骨干網流量的目的。

針對AS拓撲發現問題，目前國內外提出了一些方法。這些方法主要分為兩類：基于BGP路由信息的方法和基于Traceroute探測的方法。由于BGP路由表中包含了去往各個IP網絡地址的AS路徑信息，因而可以通過分析BGP協議進程存儲的IP網絡路由信息(簡稱BGP路由信息)中每條路由的路徑屬性來構造AS級的拓撲圖。代表性的例子是美國Oregon大學的Route?Views項目。該項目的主要目的是從互聯網上獲得多臺路由器的域間路由信息，供研究人員進行互聯網拓撲特征分析和路由技術研究等。使用RouteViews提供的BGP路由信息可以計算得到互聯網的部分AS拓撲。CERNET的BGP?VIEW項目與此類似。Route?Views項目提供BGP路由信息的步驟是：(1)在Internet放置多臺route-views路由器，這些路由器分別與某些ISP的路由器建立BGP會話，從這些ISP的路由器接收BGP路由信息；(2)周期地將BGP路由器中BGP路由信息和路由更新信息保存到文件中，如每2小時保存一份BGP路由信息的鏡像；(3)通過Web網站和FTP服務器將BGP路由信息鏡像數據提供給Internet用戶使用。BGP路由表項包含AS路徑?屬性，從AS路徑屬性可以推知AS鄰接關系，從而構造出AS拓撲圖。此外，所述路由表項中包含網絡前綴信息，從網絡前綴信息和AS路徑屬性可以推導出IP網絡地址與AS號之間的對應關系。

基于Traceroute探測的方法中，首先通過traceroute探測得到IP轉發路徑。IP轉發路徑是IP分組轉發經過的路由器端口IP地址的列表。通過將IP地址映射到相應的AS號，可以得到AS轉發路徑。AS轉發路徑是IP分組轉發經過的AS號的列表。利用多個AS轉發路徑的信息，可以構造出AS級拓撲。采用此途徑的有CAIDA的Skitter項目(目前更新為Archipelago)。Skitter項目獲得AS拓撲的主要步驟為：(1)在互聯網上部署多個探測用途的監測器，這些監視器采用類似于Traceroute的方式探測IP轉發路徑。探測方法是：用TTL(time-to-live)為N的ICMP(Internet?Control?Message?Protocol)分組探測路徑上的第N跳轉發地址。(2)對于探測得到的IP轉發路徑，利用Route?Views提供的IP網絡地址與AS號的對應關系，將IP轉發路徑轉換為AS路徑，進一步得到AS拓撲數據。Skitter項目當前在互聯網上部署了幾十個監測器。