（通信与信息系统专业论文）中国自治系统间关系的分析.pdf

韭峦 銮迪 厶堂亟堂位 i 金 塞虫塞垴 壁 中文摘要 摘要：由于自治系统( a u t o n o m o 潞s y s t c m ，简称a s ) 可以自主配置路由输入输 出策略，所以仅仅研究a s 级的网络拓扑并不能正确描述互联网的特征。近几年来， 对互联网中自治系统问商业关系的推断和研究已经成为互联网特征研究领域中的 热门之一。 本文对中国的自治系统进行了研究和分析。作者搜集整理出了包括香港、台湾 和澳门在内的4 9 8 个中国a s ，统计出了中国自治系统的类型分类和地域分布，分 析了中国自治系统的使用和发展情况。从c e r n 玎提供的b g p 路由表数据中提取 出了中国a s 对。提出了中国a s 的外度和内度以及最具中国知名度的外国a s 等 在国家或者地区范围彳有的概念，进而计算出了中国a s 的外度和内度、国外a s 的中国知名度。所谓内度是指和国内a s 连接的数目，所谓外度是指和国外a s 连 接的数目，所谓a s 的中国知名度是指国外a s 和中国a s 连接的数目。每个中国 a s 有外度和内度两个分量，按照外度优先、度值大者为p m “d e r 的基本推断规则 以及w h o i s 提供的a s 信息，对中国a s 进行了p f o v i d * c u s t o m e r 、p e 盯- p e e r 、 s i b l i n 哥s i b l i n g 等商业关系的推断。推断结果与l ( c 公布的推断结果在 p r o v i d 盯- t o c 璐t o m 盯关系上与有9 8 4 的一致性。根据国外a s 的中国知名度，统 计出了和中国a s 联系密切的外国a s 以及和中国有a s 连接的国家和地区。 关键词：中国自治系统：内度；外度 b 瘟变通厶堂亟堂位j 金塞垦! r ! a b s t r a c t a b s i 。r a c l ： r 鹤e 盯c ho n 曲l ea s l e v e lt o p o l o g yi sn o te n o u g ht oc h a r a c t e r i m eh l t e m e t ， b e c a u s et 1 1 er o u t i n gp o l o c i c sa r es t r o n 百ys h 印c db yt h eb u s i n e s sr c l a t i o n s h i p sb c t w 。e n a u t o n o m o l l ss y s t 锄s ( a s s ) i nt h e s ey c a r s ，l l l ec o i i l i n c r c i a lc o n n 孔t l l a lr e l a t i o n s h i p 锄o n ga s s i so n eo f t h el l o tt o p i c si i ln l ei i l t e n l e tc h 啪c t 甜s t i cr c s e a r c hf i e l d mt h i sp 印is e l e c tt l l ec h i n e s ea s e s 舔r e s e a r c h i n go b j c c t id 硒s i 母c h i n 昭e a s 髂i n t os e v 郴e 1 1 t a t i v cc l 鹊s e sm a tr e f l e c ta s e sw i md i f r e r e n tp r o p e r t i e s i d e r i v ct l l es t a t i s t i c so n 1 cd i tc i t i e so f a s e si nc l l i n a ii m r o d u c et h ec o n c 印t so f h 伽ed e 伊e c 、f o r e i g nd e g r e ea l l dt l l ed e g r e eo fp o p u l a r i t y 枷o n ga 晡n 髓ea s s ，a i l d 学l v ean o v da l g o r i t h mb 嬲e do nt h e 如佗i g nd e g r a 1 1 dh o m ed e g r e et oi n f ht l l e r e l a t i o n s h i p sb e t w e e i la sp a i r s ic o m p a r ct l l ei n f e r r i n g r c s u l tw i t l lk cr c s u l tp u b l i s h e d o nm cw 西s i t e 【3 5 】，眦did i s c o v e rt 1 1 a tm ya l g o 珊瞄o u t p e 面册sw e l lo ni n f 确n g p f o v i d e r - l o c u s t o m 盯a c c o r d i n gt h ed ：l i n e s cp o p u l 撕哆d e 伊o ft l l ef o r e i g na s ，i 髟l v e t l l et o pf o r t yf o r e i g na s s ，a i i dl i s ta l lt h ec o u n 埘e sw h i c hh a v et h ec o n n e c t i o nw i m c h i n 鼯ea s k e y w o r d s ：c h i n e s ea u t o n o m o u ss y s t e m ；h o m ed e g 咒e ；f o r e i 缈d e g r e e 致谢 本论文的工作是在我的导师郭字春教授的悉心指导下完成的，郭宇春教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 郭老师对我的关心和指导。 胡师舜老师在学习上和生活上都给予了我很大的关心和帮助，在此向胡老师 表示衷心的谢意。 张立军老师、李磊博士对于我的科研工作和论文都提出了许多的宝贵意见， 在此表示衷心的感谢。 在实验室工作及撰写论文期间，高贺、姜山、薛海清等同学对我论文中的研 究工作给予了热情帮助和鼓励，在此向他们表达我的感激之情。 另外也感谢家人，他们对我永远的理解和支持使我能够在学校专心完成我的 学业。 塞窑遒厶堂亟堂位 j 金童缝盈 l 绪论 1 1课题来源及研究的目的和意义 i n t e r n e t 是一个巨大、复杂、开放的网络集合，宏观上它由上万个自治系统 ( a u t o n o m o u ss y s t e m ，简称a s ) 组成，这些自治系统通过专线或者公共网络接入 点彼此相连，自治系统自j 使用的是边界网关协议b g p 。 两个自治系统物理连接上的相通，并不意味着网络信息上的可达。因为a s 问 的路由输入输出策略主要受自治系统问达成的商业关系的制约。a s 进行着频繁的 业务交互活动，每个a s 充当的角色也是频繁的转换。在一个商业关系中，某个自 治系统可能接受服务，是客户；但在另一个关系中，它又可能提供服务，是提供 者。另外，a s 之间的连接是动态可变化的，各i s p 可以增加和取消与其他a s 间 的连接：各公司可以更换它们的网络服务商；i s p 的合并和重组也会影响a s 间商 业关系的变化，这些都会在自治系统间的路由信息通告中有所体现。 研究a s 间的商业关系，是为了能够更加深入地理解互联网a s 级的拓扑特征， 从而保证互联网能够一直朝着健康、稳定的方向发展。 1 2国内外的研究现状及分析 研究a s 间商业关系的标志性文章是2 0 0 1 年高立新的o i li n f b 币n g ”t o m o m o s v s t r c l a t i o n s h i p s i n m e i l l t e t 一文，在该篇文章中高立新明确了a s 闻存在的关系 模式，并给出了推断p r o v i d e r c u s t o 鹏r 、p e e r p e e r 、s i b l i n g s i b l i n g 关系的 算法，而且还在实际b g p 数据上验证了算法的准确性。紧接着l a r k 算法 9 提出 文中提出从多个数据源综合考察同一对a s 关系的观点，并系统提出了自己的一套 算法，而且依据a s 问关系重新划分了a s 等级。稍后的e h s 算法 1 z 和d p p 算法 1 0 针对l a r k 算法进行了改进，其中d p p 算法使用满足性问题的表达方式和图论 中连通性概念对求解a s 问商业关系问题进行了阐释和求解。k cc l a f f y 后来居上， 对前面已有算法进行综合分析评价后，重点对d p p 算法进行了改进，一方面引入 了s d p ( s 啪i d e 丘n i t ep f o 伊锄m i n g ) 模型和相关公式，另一方面一改前人对a s 度 的简单使用方法，改用了a s 度梯度的概念和方法，从而将无效路径多少和a s 度 两方面因素以公式化的方式都考虑进a s 关系的推断过程中。此外b s r 算法抛开 a s 关系推断中已有的规则，首先假定每条至少包含3 个a s 的a sp a m 中，最后 个a s 是倒数第二个a s 的伽t o m e r ，然后按照自定义的规则继续推断。后来高 立新又提出了从分析b g p 路由协议中c o i 砌m 时属性入手来推断a s 关系，从而 开辟了新的思路。由于a s 间的商业关系属于企业的商业机密，而查询w h o i s 信 息得到的a s 信息往往有些陈旧，所以a s 推断结果的验证一只是个令人头疼的问 题。2 0 0 5 年k c 的研究团队通过邮件提问的方式向一些a s 所有者确认a s 关系推 断结果的正确性，反馈的结果较好，k c 在【2 1 】中有详细说明。自此k c 将c a i d a 3 5 】 作为一个交流平台，将每次推断出的a s 关系公布于上，供其他研究者参考。 对中国自治系统的研究，作者目前了解到的有周实【2 3 】，但是他主要关注的是 互联网a s 级的拓扑结构，并且提出了p o s j t i v c f e e d b a c kp r e f h e n c e ( p f p ) 模型和相 应算法。此外还有哈尔滨工业大学2 0 0 3 届硕士张尼【4 】，在推断a s 关系中使用的 算法是高立新最早提出的算法的简化，该论文主要研究的是中国大陆的a s ，并没 有考虑台湾、香港和澳门的a s o 与上述各人不同的是，首先本文所使用的数据源是中国国教育科研机构 c e r n e t 提供的b g p 路由数据，用它来研究中国自治系统能够得到更丰富的中国 a s 路径信息；其次本文提出了a s 的外度和内度，虽然这两个概念仅对局部地区 或者某一国家而言有意义，但却提供了一个对互联网局部进行研究的简单方法。 1 3本文的内容和结构 本文首先整理出了近5 0 0 个中国a s ，其中包括香港、台湾和澳门在内，虽然 没有找全所有的中国a s ( 据统计目前大约有7 0 0 个a s ) ，但是后续的实验还是得 到了比较可信的结果。同时这为今后继续研究中国a s 节省很多查找时间。 第二、本文编写了解析原始b g p 数据的p e r l 脚本工具以及后续的从原始数据 得到a sp 甜i 、从a sp a m 得到中国a s 对、计算a s 度、计算中国a s 内度外度 等一系列的p 以脚本工具，这不仅极大地提高了本文各阶段的研究效率，而且也 可以供后续其他a s 研究人员使用。 第三、本文第三章详细介绍了a s 间商业关系的研究现状，重点介绍了这一领 域的重要人物和重要算法，使读者对a s 间商业关系研究有比较全面和清晰的认 识。 第四、在第四章中，首先展示了中国a s 的增长速度以及世界排名，然后对中国 a s 进行了分类和地域分布的统计，使得读者可以对中国自治系统的整体状况有所 了解。最为重要的是，作者根据研究对象的特殊性，提出了a s 的内度和外度，所 谓内度就是中国a s 邻居的数目，所谓外度就是国外a s 邻居的数目，这在研究整 2 e 立交道厶堂亟堂位论奎自逾丕筮缝疆鳖班宜现达 个互联网a s 关系的一般性当中是没有的概念，接着作者根据每个a s 对中双方外 度、内度的相对优势来推断a s 问的商业关系。与k c 3 5 】同同公布的a s 推断结果 相比较后发现，本文的推断结果在p r o “d 仃_ c u s t o m e r 关系推断上取得了9 8 4 的一 致性。另外还发现有5 3 对a s 在k c 的推断结果中是没有的，这很可能是k c 所 用的原始b g p 数据中缺少相关中国a s 的路径信息的缘故。 2 自治系统级网络研究现状 i n t e r n e t 拓扑可以分为两个抽象层：路由器级拓扑图和自治系统级拓扑图。 路由器级拓扑图表现物理的路由器问的连接关系，反映数据实际的流动方向和路 径。自治系统拓扑表现各个不同自治系统日j 的连接关系和路由更新策略，从中可 以考察不同网络日j 的连接情况、网络的关键部分，从而为优化网络接入提供依据。 应该说i n t e r n e t 首先是由自治系统构成的，为了从宏观上了解i n t e r n e t 的结构， 有必要构造自治系统级拓扑图。 2 1 自治系统介绍 自治系统拓扑是i n t e r n e t 网络状况的反应；一个自治系统是拥有同一选路策 略、在同一技术管理部门下运行的一组路由器。自治系统可以是工作在一起以提 供内部选路的内部网关协议的汇集。一般来说一个i s p ( i n t e r n e ts e r v i c e p r o v i d e r s ) 可以称为一个自治系统，在外部世界来看，整个自治系统是一个单一 实体。每个自治系统有一个由因特网登记处或者i s p 分配的识别码( a s n ) 。 各个自治系统包含运行外部网关协议b g p ( 当前主要是b g p 一4 ) 和内部网关协 议i g p 的路由器，其中a s 内部使用的i g p 协议通常有0 s p f 和i s i s 协议，外部网 关协议b g p 又分为e b g p 和i b g p ，e b g p 负责在a s 之间交换可达性信息，而i b g p 负责在a s 内部交换外来的可达性信息。 2 2b g p 协议介绍 自治系统间通过b g p 路由器连接起来，b g p 是一种不同自治系统的路由器之 间进行通信的外部网关协议。它是a i e t 所使用的老e g p 协议的取代品。 l 强c 1 2 6 7 对第3 版的b g p 进行了描述。r f c l 2 6 8 描述了如何在i n t e r n e t 中使用b g p 。 1 9 9 3 年开发第4 版的b g p ( 见r f c l 4 6 7 【t o p o l c i c l 9 9 3 】) ，以支持聚合c i d r 。 就b g p 而论，因特网就是一个a s 图，每个a s 用a s 号码来识别。两个a s 之日j 的连接形成一个路径，路径信息的汇集形成到达特定目的地的v 路由。b g p 使 用这些与既定目的相关的路径信息来确保无循环域间选路。由b g p 和a s 之问的这 种关系可知，b g p 协议本身在实现过程就包含了自治系统拓扑图的构造。 首先，我们将一个自治系统中的i p 数据报分成本地流量和通过流量。在自治 系统中，本地流量是起始或终止于该自治系统的流量。也就是说，其信源i p 地址 或信宿i p 地址所指定的主机位于该自治系统中。其他的流量则称为通过流量。在 i n t 锄e t 中使用b g p 的一个目的就是减少通过流量。由此可以将自治系统分为以下 几种类型： 1 ) 残桩自治系统( s t u b a s ) ，它与其他自治系统只有单个连接。s t i l b a s 只有本 地流量。 2 ) 多接口自治系统( m u l t i h o m o d a s ) ，它与其他自治系统有多个连接，但拒绝 传送通过流量。 3 ) 转送自治系统( t r 孤s i 协s ) ，它与其他自治系统有多个连接，在一些策略准则 之下，它可以传送本地流量和通过流量。 这样，可以将i n t e r i l e t 的总拓扑结构看成是由一些残桩自治系统、多接口自治 系统以及转送自治系统的任意互连。残桩自治系统和多接口自治系统不需要使用 b g p 协议，它们通过运行e g p 协议在自治系统之问交换可到达信息。 b g p 是一个距离向量协议，但是与其他距离向量协议有很大不同。比如说r m 协议，它保留了到每个目的地址的跳数，而b g p 则保留了到每个目的地址的完整 路由( 自治系统到达目的地址的序列号) 。这样就排除了一些距离向量协议的问题。 b g p 采用1 6 b i t 数字表示自治系统标识。 b g p 与r i p 和o s p f 的不同之处在于b g p 使用t c p 作为其传输层协议，端口 号为1 7 9 。两个运行b g p 的系统之间建立一条t c p 连接，然后交换整个b g p 路 由表。从这个时候开始，在路由表发生变化时，再发送更新信号。 b g p 有五种报文：o p e n 报文、u p d a l 吧报文、增量u p d a t e 报文、 k e e 队l 愆忸报文和n o t i f i c a t i o n 报文。 0 p e n 报文：用来与相邻的另外一个路由器建立关系； u p d a t e 报文：用来发送某一路由的信息，以及列出要撤销的多条路由； k c 印a l i v e 报文：用来确认o p e l l 报文，和周期性地证实邻站关系； n 胡6 c a t i o n 报文：用来发送监测到的差错。 b g p 有以下三个功能过程： 邻站探测( 确曲b o r a c q l l i s i t i o n ) ：接在同一个子网上的两个路由器称之为邻站。 在进行邻站探测时，申请作为对方邻站的路由器要发送一个o p c i l 报文。若对方路 由器同意，则发回一个k e 印a l i v e 报文。 4 j e 塞銮堑厶髦亟堂位论塞臼塑丕蕴缝匦鳖班蕴丑送 邻站可达性( n e i g 灿o rr a a c h a b i l i t y ) ：一旦邻站关系建立了，就要用邻站可达 性过程来维持这种关系。双方中的每一方都需要确信对方是存在的，且一直在保 持这种邻站关系。为此目的，这两个路由器彼此要周期性地交换k e 印a l i v e 报文( 一 般每隔3 0 秒) 。 网络可达性( n c t w o r kr c h a b i 】i t y ) ：当路由表发生变化时，路由器就用广播方 式对所有执行b g p 的路由器发出一个u p d a t e 报文。这样，所有的b g p 路由器就 维持了新的路由信息。 b g p 通过定期发送k e e p a l i v e 报文给其邻站来检测t c p 连接对端的链路或主机 是否失败。两个报文之间的时间间隔建议值为3 0 秒。应用层的k e 印a l i v e 报文与 t c p 的k e 印a l i v e 选项是独立的。 b g p 允许使用基于策略的选路。由自治系统管理员制订策略，并通过配置文 件将策略指定给b g p 。制订策略并不是协议的一部分，但指定策略允许b g p 实现 在存在多个可选路径时选择路径，并控制信息的重发送。选路策略与政治、安全 或经济因素有关。 b g p 协议的关键特点是它允许每个自治系统使用自己的策略选择最佳路由、 发布和接收路由，这就使得管理域之间商业合同关系成为决定路由策略的最重要 因素。为简单起见，目前一般将b g p 的路由策略分为输入策略和输出策略。输入 策略决定了是否接受收到的路由更新消息；路由器会在从不同邻居处接受的路径 中为某个目的地址前缀选出最佳路由，最佳路由的标准由a s 自己制定；根据输出 策略，b g p 路由器将决定是否向其邻居通告该最佳路由。 b g p 的路径属性： 1 a s p 御属性 o p e n 报文中有a s 号字段，在收到一个u p d a r e 报文时，网关会根据输入 策略来决定是否使用这条路径，如果选择了接受，又会根据输出策略决定是否把 这个更新报文广播给邻居a s 。u p d a l 吧报文中路径属性，路径属性中a s 路径属 性属于公认必遵属性，它由一条b g p 路由所经过的a s 号组成。 a s 到汀h 中有两种类型： a ss e o u e n c e ：经过的a s 号的顺序排列 a ss e t ：经过的a s 号的无序排列 向e b g p 对等体通告路由时，修改该属性，向i b g p 对等体通告路由时，不修 改该属性。 a s p 舢的产生方式： a ) 如果a s p 棚的第一个路径属性是a s s e q u e n c e 类型，本地系统应该 把两字节的a s 号码作为序列的最后一个a s 号码加在后面( 最左面) 。 5 e 塞窑遵厶堂亟堂位盈塞自逾丕缝缝旦缝班宜理猛 b ) 如果a s p 舢的第一个属性类型是a s s e t 类型，本地系统应该添加一 个新的路径段a s s e o u e n c e 类型，在段的内部放a s 号码。 a s 号的添加原则：a s p 舢的顺序和流量的方向相反，最后一个a s 为路由 来源自治系统( 产生流量的自治系统) 。 从其生产方式可知，a s 路径表示的是从起点到终点a s 的访问序列，其中的每 个a s 对都体现出了彼此的输入、输出策略，可以说a s 路径实际上是相关自治系 统之间输入输出策略的集中体现，而本地策略则是由自治系统之间的商业关系所 决定。通过分析这三者之间的因果关系，我们相信自治系统间有什么样的商业关 系，就会形成其相应的a s 路径，那么路由表中的a s 路径一定会遵循某种固有的 模式，因此我们可以利用这个逆向推理的过程，通过分析a s 路径的模式，来还原 出a s 之i 日j 的商业关系。 利用a s 路径属性，b g p 可以实现无循环的选路。当一台路由器收到一个其 中列有它自己的a s 号的b g p 更新时，该更新将被视为循环的而被丢弃。 2 b g p 的l o c “p r e 触n c e 属性 当b g p 路由器收到一个路由通告时， p r e 触饥c e ) 以表明对该路由的喜好程度。 控制输出的流量。 会给该条路由赋一个本地偏好值( 1 0 c a l 偏好值可以用于影响最佳路由的选择和 b g p 路由器根据下面的标准为每个前缀选择最佳路由： 1 ) 具有最高的本地偏好值； 2 ) 具有最短的a s 路径； 3 ) 具有最小的源属性值，源属性属于公认必遵属性，它指明了b g p 路由信 息的来源。有下面三种取值：o 代表i g p ，使用n e 咐o r k 命令和从i g p 引入的路 由具有此属性，用i 表示； 1 代表e g p ，通过e g p 学习的路由具有此属性，用e 表示；2 代表h l c o m p l e t c ： 重分配进来的静态路由具有此属性，用? 表示。 4 ) 当下一条a s 相同时，选择具有最小m e d ( m u l t ie x i td i s c ) 值的路 由； 5 ) 优先选择从e b g p 学习来的路由而不是从i b g p 学习来的路由； 6 ) 到出口边界路由器的i g p 度量最小； 7 ) 路由i d 最小。 从上面可以看出，本地偏好值是选择最佳路由时首先考虑的参数。 2 3自治系统级拓扑研究的内容 6 e 塞窑通厶堂亟堂垃i 佥塞自盗丕统缝嗵终班荭强丛 目前自治系统级拓扑发现主要分为三个研究领域： 1 ) 统计和建模 捕捉大量的b g p 路由数据，对数据进行分析，统计指定时问内网络的行为和 变化规律，并根据网络的变化，分析网络性能、网络发展趋势，对网络效率和运 行情况做出预测和评价，建立正式的网络描述与模拟，现在和可视化技术相结合。 2 ) 网络拓扑设计和管理 从b g p 协议出发，研究协议中的各种特定属性，并将其应用到具体互联网拓 扑上，目前主要是针对冗余度、对称性和负载平衡等目标的设计，使管理域中的 各个网络能够在最优的配置下进行工作。 3 ) 自治系统问拓扑关系的研究 通过对路由数据的提取、分析、计算出自治系统间相互关系的商业关系。从 而考察不同管理部门网络间的连接关系和连接参数，发现并改正病态路由、减少 误配现象，为优化网络结构和网络接入提供依据。 2 4a s 号的申请、分配和使用情况 2 4 1a s 号的注册机构 自治系统号a s n ( a u t o n o m o u ss y s t 啪n u r n b c r ) 作为一种全球唯一且空间有限 的互联网资源，同i n t e m e t 的i p 地址一样，其分配是分级进行的。i c a n n ( 1 1 1 ei n t 锄c t c o r p o r a t i o nf o r a s s i 龃e dn 锄馏锄dn l l l 】m e r s ) ，负责全球i n t 锄e t 上的i p 地址的分配 ( 原来是由i a n a 负责) 。根据i c a n n 的规定，i c a n n 将部分i p 地址和a s 号( a s n 啪b e r b l o c k ) 分配给地区级的h t e r l l e t 注册机构( r e 舀o n a li m 黜c t r e 西s h y ) ，由各 区域机构负责向其各自的下级进行分配。目前世界上共有五个区域注册机构： 1 非洲网络信息中心( a f m q i c ：a 伍c 蛆n e t w o r k i n f o n n a t i o n c e n t e r ) 2 亚太网络信息中心( a p n i c ：舢i a p a d f i cn 咖o r l 【i n f o n i l a t i c t e r ) 3 因特网号码美国注册处( a r i n ：a m e r i c 姐r e 百s t r y 矗) ri n t c r n c tn 砌b e r s ) 4 i p l 网络欧洲协调中心( r i p en c cr 铝船吼me u r o p e e n s ) 5 拉丁美洲和加勒比海地区因特网地址注腭机构( l c n i c ：1 1 1 el 撕n a m 耐c ma n dc a r i b b e 粗i l l t 锄e ta d d r 豁s 部r e 西s n y ) 中国的c n n i c 以国家n i c 的身份于1 9 9 7 年1 月成为a p n l c 的联盟会员，成立了 以c n n i c 为召集单位的分配联盟。按照a p n i c 的有关规定( a p n i c - 0 5 1 ) ，c n n i c 分 配联盟成员单位可以通过c n n i c 获得i p 地址和a s 号码；c n n i c 必须将c n 小i i c 分配 联盟单位的名单及i p 地址和a s 号码分配情况报告a p n i c 。中国的i s p ，获得i p 地址 7 e 塞变通厶堂亟堂位论室自淦丕筮缝嗵终班宜现越 和a s 号码最有效的方法为申请加入c n n i c 分配联盟，由。附i c 分配联盟代其申 请l p 地址和a s 号码。 此外，还有台湾的台湾网路咨讯中心t w n i c ( n a t i o n a ln e 呐o r ki n f o n l l a t i o n c 朗t e r ) ，日本的j p n i c ，韩国的k r n i c 等地区或国家级机构。 下面表中列出了各机构负责的地区： 注册机构负责地区 a 衔n i c 非洲、部分印度洋地区 a p n i c 部分弧洲、部分大洋州地区 a r i n 加拿人、美国、加勒比海年| i 北人艏洋地区岛屿 l a c n i c拉丁美洲、部分加勒比地区 r j p e n c c欧洲、中尔、中讵 表2 1 a s 号分配机构 下图直观地给出了五大机构管辖的地区和范围： 图2 1 五大a s 号分配机构管辖区域图【4 5 】 有关自治系统的信息包括自治系统号码、名称、描述、输入输出策略等等。 通过输入输出策略的描述，可以得知该自治系统的地理信息、隶属单位名称、从 哪些自治系统接受路由更新，向哪些自治系统发送路由更新，从而得到自治系统 概貌。 亚太网络信息中心、英特网号码美国注册处和i p 网络欧洲协调中心都提供 w h o i s 数据库，允许个人和组织查询分配的i p 地址和自治系统号码信息，然而 w h o i s 中关于a s 的连接信息都是建网申请自治系统号码时的资料，很难反映当前 网络的实际路由状况，而且i s p 也不会对外公布这些信息。因而无法从网络上现 有的数据资料得到自治系统互连的信息，但是基于w h o i s 上其他静态信息，比如 a s 名称、描述、所属国家、管理者等等具有可参考的价值，而且难以从其他方式 得到，所以可以用来作为b g p 路由信息的补充。 2 4 2申请a s 号的条件 e 峦窑堑厶堂亟堂焦迨塞自治丕缝级圜鳖硒荭现丛 1 ) 申请单位的网络必须具有多路出口。 般如果该单位的网络规模比较大或者将来会发展成较大规模的网络，而且 有多个出口，则建议建成一个自治系统，这样就需要a s 号码。如果网络规模较 小，或者规模较为固定，而且只有一个出口，则可采用静态路由或其它路由协议， 这样就不需要a s 号码。 2 ) 申请单位必须认真填写a s 号申请表。 3 ) 申请单位必须提供与对方i s p 签署的关于双方使用b g p 协议互联的协议书。 4 ) 申请a s 号码的单位需要与两家以上( 包括两家) 、有不同a s 号码的网络接入 商进行网络互联，并计划三个月内与他们同时运行b g p 协议进行外部路由。只有 一个网络接入商的i s p ，我们建议使用私有a s 号码( a s 6 4 5 1 2 到a s 6 5 5 3 5 ) 与 对方进行b g p 连接。c n n i c 在分配a s 号静需在a p n l cw h o i s 数据库中注册。 如果申请单位在拿到a s 号后起三个月内没有使用该a s 号，则c n n i c 有权收回 该a s 号。 自治域网络接入i n t 锄e t 前，必须向因特网注册机构申请自治系统号码，填写 有关自治系统的基本信息。 2 4 3a s 号码的分配及使用情况 a s 号是用于标识自治系统的全球唯一的号码，它是一个1 6 比特的整数值， 因此最大允许有6 5 5 3 6 个a s 号码。其中预留了a s 6 4 5 1 2 到a s 6 5 5 3 5 共1 0 2 3 个 a s 号码用于本地或者私用，另外还预留了3 个用作特殊用途。其余“5 1 0 个a s 号码以a sb l o c k 形式在i a n a 和五大区域性机构中进行了分配。 图2 2 a s 号分配机构负责的a s 数目 上图是网站【“】提供的截止2 0 0 6 年1 2 月2 2 日a s 号的分布情况。其中i a n a 9 e 立交通厶堂亟堂垃i 金塞自渔丞统级陋终班荭丑丛 负责a s 号资源的总调度，它根据五大区域性互联网注册机构a s 号的使用情况和 需求给它们补充新的a sb l o c k ，目前它还有2 1 5 0 4 个a s 号未进行发放。五大区域 性互联网注册机构负责具体给i s p 或者终端用户分配a s 号。 下图是五大区域性互联网注册机构目前对4 3 0 0 6 个a s 的管理情况，其中还有 6 3 2 2 个a s 没有进行分配，在已分配出去的3 6 6 8 4 个a s 当中，已经投入使用的有 2 3 8 2 6 个，还未使用的有1 2 8 5 8 个。 幽2 3 a s 号在五人r m 中的总体分配和使心情况 下图是从网蛳4 4 】上直接获得的五大r m 机构中a s 号的具体使用情况。其中 黄色方块p o o l 表示尚未进行分配的a s 资源，紫红色方块表示已经分配出去但尚 未投入使用的a s 号，浅紫色表示已经分配出去且已经开始在网络中使用的a s 号。 f r i i c 口 r p n i c i _ 豳 鲰i n 缀黧麓鳓燃戮缀戮鬻 睥i p e n c c l 燃缀缀缀缀缀蓊貔缀瓣缀黝 | l r c n i c 瞳 i p 神l州- p l 一 磁m 憎啼i 一 图2 4a s 号在五大r 瓜中的分配和使用情况 i o 匙峦蛮道太堂亟堂位i 金塞自盗丞统羞丕班蕴强拭 3 自治系统关系研究现状 3 1自治系统关系研究的意义和方法 3 1 1自治系统关系研究的意义 互联网由数千个i s p 组成，每个i s p 都分管着互联网架构中的各个体网络。i s p 决定着自治系统问的连接关系和输入输出策略。这些关系以商业协议的形式实现， 并最终转化为各个体网络内或之问的交通流量的工程控制。管理域之间商业合同 关系已经成为决定路由策略的最重要因素。下面列举的这些方面都或多或少需要 知道a s 之日j 的关系：1 ) 仿真建模由路由策略引起的路由膨胀影响；2 ) 理解数据 包是如何在互联网中被路由的以及如何通过分析现有的不足来优化网络路径；3 ) 开发更多可测量的域| b j 路由协议和结构，如协议h l p ，将a s 问关系考虑进去，以 优化它们的性能；4 ) 评估a s 关系是如何影响互联网架构的演化以及如何构建整 个互联网增长的经济模型的。5 ) 分析b g p 配置方案的范围，从而开发更有表达 力的路由协议和配置语言；6 ) 互联网中a s 路径的推断；7 ) 对路由表的结构进行 建模，为仿真路由表的查找算法而开发综合的路由表；8 ) 开发出更好的拓扑产生 器用于说明与a s 关系相关的拓扑特性；9 ) 通过测量到已知服务器的流量的源头 和评估候选数据中心的连通性及a s 关系来为服务器备份选择数据中心。1 0 ) 根据 候选i s p 的连通性和a s 间的关系选择对等体和上层供应商。 由此可见，a s 之问的关系是i n t e r i l e t 拓扑结构的重要方面，从中可以考虑不 同部门网络间的连接关系和运营情况，为优化网络结构和网络接入提供依据；同 时自治系统的商业关系也是一种网络备战资源，对于国家网络宏观管理与维护有 深远的意义。具体表现在以下几个方面： 1 ) 在设计和优化网络方面，为管理域的负载平衡、拥塞避免提供参考； 2 ) 可以在研究自治系统关系的基础上，进一步确定自治系统在h l t 锄c t 中的 等级，为企业或者小型i s p 接入网络和签订商业协议提供依据。 3 ) 比较a s 拓扑图中的逻辑关系和自治系统问的真实关系，可以发现故障点、 减少误配现象、指导并调试路由器配置文件。 3 1 2 自治系统关系研究的方法 b 峦銮道厶堂亟堂位i 盆童自洫丕筮羞丕硒窟理丛 有两种基本方法； 1 根据w h o i s 库提供的a s 信息进行研究 这是最直接的方法，各机构在申请注册a s 号时，会向注册机构登记一些机构 名称、所在地区、路由输入输出策略等信息。我们通过w h o i s 查询，就可以得到 关于某个a s 的这些信息。然而互联网是动态变化的，而w h o i s 库信息又更新得 不及时，单纯使用这种方法来推断a s 问的关系，难免会出现推断错误。 2 根据b g p 路由表的路径属性进行研究 其中根据b g p 路由表的路径属性又包括： a 根据b g p 路由表中的a s p a l h 属性研究 这是最常用的方法，然而随着互联网规模的不断增大，b g p 路由表的规模也 是同益庞大，数据处理上的困难和关系推断算法的准确性，是该方法主要考虑的 问题。目前，全新的算法还没有出现，多数都是在已有算法的基础上进行改进。 b 根据b g p 路由表中的c o m m u n i t y 属性研究 这是比较新的方法，c o m m u l l i t y 属性最一般的用途是用于标记路由来源的特 定邻居a s 。当b g p 路由器收到一条来自它的邻居的路由时，路由器会使用 c o m m 砌t y 属性对该路由打上标记以表明它和邻居a s 的关系。 3 2 原始数据的获取 基于b g p 协议测量是一种较为常见的方法，在b g p 路由表中包含有a s p a t h 表项，分析这一表项我们可以得到a s 的连接关系，同时，路由更新的发送路线也 就是a s 的策略允许的路线，又可以进一步分析出a s 自j 的路由更新策略。如何获 得b g p 路由表信息呢? 目前已知的公开数据源有c e r n e t 数据源 2 7 】、c a i d a 数据源 3 6 】和r i p e 数 据源【4 3 】，其中c e r n e tb g p 数据分为i p v 6 和m v 4 两大块，口v 4 的b g p 数据是从 2 0 0 2 年6 月提供到2 0 0 6 年5 月4 日，每两个小时提供一个b g p 快照( s n a p s h o t ) ； c a i d a b g p 数据是从2 0 0 1 年l o 月份开始提供的，也是每2 个小时提供一个b g p 快照；r i p e 目前提供两种b g p 数据文件，一种是b g p 报文，文件名称以“u p d 掘” 开头，每1 5 分钟提供一次。另外一种是b g p 路由表，文件名以“b v i 钾”开头， 每8 个小时提供一次。 3 3管理域之间商业关系的划分 1 9 9 9 年，g h u s t o n 在【5 ，6 】中把管理域之自j 的商业关系划分为以下几类： 1 2 j e 塞銮道厶堂亟堂位逾窑自湓丕统羞丕皿盈班迭 a ) 客户一供应商( c u s t o m * p m v i d e r ) 关系： 客户向供应商交纳连接到i n t e l l l e t 的费用，供应商为用户转发业务流量。而客 户不转发它的供应商之间的业务流量。 b ) 对等( p e c r 。t o p e e r ) 关系： 一对在双方的客户日j 提供连通性的a s 。 c ) 相互转发( m u t i l a l t r a n s i t ) 关系： 这种关系要求两个管理域之问彼此提供到达m t e n l e t 其他地方的连接。多发生 在小型i s p 之问，它们彼此临近且都支付不起更优互联网连接的所需要的额外费 用。 d ) 相互备份( m u t i l a l - b a c k u p ) 关系： 当一方到其供应商的连接失败时，另一方为其提供一条通向i n t e r n e t 的备份连 接。 文章【7 】是研究a s 日j 商业关系的一篇十分重要的文章，在这篇文章中，作者 高立新称这是理解和推断互联网中a s 关系的首次尝试。在这篇文章中高立新将两 个相连的a s 之间的关系分为： 客户一供应商( c l l s t o m 昏p r o “d c r ) 关系，对等( p e 昏t o - p e 盯) 关系和s i b l i n g 关系( 对应的应该是g h u s t o n 定义的m u n l a l t f 锄s i t 关系) 。 客户一供应商关系是h l t e l l l e t 中最常见的一种商业关系。对等( p e e r i n g ) 关系 是i n t e n i e t 中一种重要的商业关系，多发生在级别较高的a s 之间。实际上，正是 因为对等关系的存在，才使得i n t e m e t 能够互相连通，没有网络不能覆盖的角落。 相互转发关系或称兄弟关系的两个a s ，通常隶属于同一个i s p 或者地理位置相近， 二者通常有相同的供应商，a s 级别也相差不多。这种关系较为特殊，并不属于规 范的商业关系。相互备份( m u t l 山a c k u p ) 关系，主要考虑的是在网络发生故障 的情况下的应急措施。 高立新在【7 】中同时也强调：a s 之间的关系有可能不是直接和管理域间的商务 和贸易契约相对应，有可能在a s 间的一个商业契约中会同时包含供应商一客户、 对等体等多种关系。这些商业关系按照优势从强到弱的顺序排列为：相互转发备 份、供应商一客户和对等体关系。 随着网络的快速增长，许多i s p 会在多个网络点交互流量，在这些交互点 ( i n t 盯n n e c n n gp o i n 括) 上遵守的就不一定是相同的路由策略，这是a s 和其他 a s 间的商业关系比我们想象的要复杂的多。而且越来越多的a s 都和网络交换点 ( e x c h a n g e p o i 吣) 建立了连接，它们之间的策略就可能既不属于供应商一客户关系 也不属于对等关系，那些包含这些网络交换点的a s 路径自然也就不满足后面讲到 的v a l l e y - 丘性质。 另外，从流量的角度也可以这样划分a s ：除了通告自身路由外还通知其他 e 巫窑煎厶堂亟土堂撞j 金塞自逾丕筮差丞班左理丛 a s 路由的自治系统称为过渡a s 。对过渡a s 而言，来源和目的地都在本a s 之外 的任何流量都称为过渡业务量。显然，在a s 路径中既不是起点又不是终点的自治 系统都是过渡a s 。同样地，非过渡a s 只通告自身路由，而不通告从其他a s 处 得知的路由，非过渡的a s 不允许业务量通过它过渡到另一个a s ，这就保证了目 的地不在本a s 中的流量不会流入自治域。显然，非过渡a s 在任何a s 路径中或 者是a s 路径的起点，或者是a s 路径的终点。 3 4 自治系统的路由输出策略 所谓的路由策略就是一组由网络管理员配置的规则，规定a s 如何选择最佳路 由、是否将最佳路由通告给邻居a s 。路由策略包括输入策略和输出策略。b g p 协 议允许a s 自主使用路由策略，其中的输出策略包括：允许或拒绝一条路由，通过 赋值m e d 末控制进入的流