对新型网络路由机制的思考

基金项目：国家重点基础研究发展规划项目(“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表示整个全球路由表占用的内存空间，Nprefix表示全球路由表中可达前缀个数，Npath表示可达某个前缀的路径个数，全球路由表中每个可达路径及相关属性所占内存空间相同且表示为R，则有下式。
M = Nprefix×Npath×R   (1)

    根据路由观察(RouteViews)得到的数据[5]，2007年12月4日全球路由表的Nprefix= 246 778，Npath的数学期望值为36，最大值为43，最小值为1。Nprefix?垌Npath，M是O(Nprefix)级。值得注意的是，近10年来，Nprefix呈现出指数级增长。图2给出了从1989年7月1日至2007年12月4日全球路由表的Nprefix增长图[6]。

    导致Nprefix指数级增长的原因主要包括有多宿主、聚合故障、负载均衡技术及地址分段[7]。为了获得更好的连接性，大量的客户网络选择到多个提供商网络的多条连接。目前Internet中多宿主自治系统(Multi-homed ASes)已经占全部自治系统的70%[8]。由于从一个提供商处获得的前缀难以被其他提供商网络聚合，所以多宿主技术会通常使得全球路由表中增加额外表项，如图3示。有研究发现：多宿主技术的应用已经向全球路由表中引入20%~30%左右的额外前缀。因聚合故障，全球路由表存在接近15%~20%的前缀可被聚合却未被聚合的路由表项。不能聚合由相同自治系统所发起前缀的另一个原因是负载均衡。如图4示，Stub_AS1通过分别向Transit_AS1和Transit_AS2通告不同的子前缀，以达到链路Link1和Link2上输入流量均衡的目的。目前，负载均衡已经引入20%~ 25%的额外前缀。自治系统本身就可能拥有多个不可聚合的地址分段，如图5示。应予特别关注的是，地址分段引入的额外前缀最多，接近75%。

    Nprefix指数级增长所引发的直接后果是网络的规模可扩展性变差。根据解决问题的着眼点不同，当前域间路由系统面临的规模可扩展性问题的解决方案分为以下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]. 
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.  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]. 
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.    
[6] BGP routing table analysis reports [EB/OL]. 
[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]. 

收稿日期：2007-11-15

[摘要] 路由是网络的结构基石，新型网络路由机制是构建新型网络体系的必需。目前网际层的路由本质上是所谓的“单下一跳路由”机制，解决网络传输拥塞问题的一个根本措施在于改变当前网络单下一跳的选路模式，允许多条路径的并行传输。边界网关协议(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.

[Keywords] network architecture; intra-domain routing; inter-domain routing