层次式交换网络

基金项目：国家高技术研究发展计划资助(“863”计划)课题(2007AA01Z214)

1 互联网面临的挑战
    Internet是20世纪对人类社会最具影响力的科技发明之一。它为人类提供了全新的通信手段、信息交换手段以及信息获取手段，极大地加速了社会的信息化进程。目前，全世界已经有超过30亿人在使用Internet，像中国、印度这样的人口大国还有超过四分之三的人口没有上网。Internet之所以发展迅速，是因为它顺应了社会向信息化进步的需要，并且采用了简洁明了的包交换协议和灵活机动的路由方法。

    包交换技术不同于以往的电路交换技术，它需要完备的路由技术来支持。利用计算机的智能，在路由器之间定期交换信息，形成一张路由表。各路由器能按照数据包外皮上写的目的地址，查看自己保存的路由表后，将数据包一站一站地往目的地方向传送。所有这些转发工作，包括路由表的更新，都不要人工干预，由路由器自动完成。有了路由器对网络结构的自动适应能力，人们连网时想怎么连就怎么连，方便地组成任意连接的网络结构。在网络部件特别是通信线路可靠性较低的情况下，任意连接的网络结构和路由器自动找路的方法非常有效。路由技术是Internet的核心和灵魂，没有人能否认这一点。

    可以说，网络发展的早期，Internet能战胜其他网络体系的优势就是网络协议简单和包交换及路由技术。然而，随着技术的发展和高级应用的出现，尤其是当网络规模极大地超出了早期网络设计者的想象，Internet的这些优势遇到了空前的挑战，有的不再是优势了，有的将转化成阻碍Internet继续发展的因素。
当网络规模不断发展，实时通信要求增长时，互联网遇到了一系列困难：网络规模使得路由表庞大，路由器不能快速有效地转发数据包；网络拓扑局部变动、信道或设备的故障与恢复、网络管理人员的配置和操作失误等局部网络行为，都必须作为全局行为向全世界通报并更改所有的路由信息，使得骨干网路由器不堪重负，网络事件发生后的路由信息收敛时间达到分钟量级，大量数据包在网络中振荡或兜圈；路由器越来越复杂，成本和耗电越来越高；为了克服包交换技术的不足，获得电路交换的好处，要增加虚拟电路交换技术，使网络协议变得越来越复杂；光通信线路的高可靠性，使得任意连接的网络结构优点不再；由于人工难以确定数据包在网络信道中走的确切路由，以及数据包的借道通行，网络设计人员无法确切地为每条信道分配合适的带宽，并且难以做到既充分又合理地利用网络信道资源；慢速的端到端的错误恢复手段，缺少网络自愈能力，使得Internet难以提供电信级的服务质量；网络行为的不确定性，使得难以对网络实施有效的管理与控制；网络地址空间与用户地址空间没有严格的区分以及骨干网络信令与用户网络信令完全融合，给骨干网设备带来了致命的安全威胁；网络源地址的可伪造性，使得网络不良行为难以得到有效的查处与抑制。所有这些困难，都是致命的。再加上早期对Internet的发展规模估计不足，IPv4地址空间将在一两年内耗尽。目前大量采用的私有地址会阻碍端到端的通信能力。采用地址空间极大的IPv6协议，如果不考虑网络的层次化，路由表会进一步急剧增大，路由器的复杂性和它在网络中的“瓶颈”地位也就越加严重。目前大量的改进措施，难以真正解决问题，陡然增加了网络协议的复杂性。Internet到了必须进行重大改革的时候。

    本文针对当前Internet难以应对的一系列挑战，介绍一种新的网络体系结构：层次交换网络技术。利用这种技术，彻底丢掉路由器；让网络回归简洁；让数据包的路径可预测，网络信道资源获得合理应用；让网络拓扑结构信息的变化、网络设备与通信线路的失效与恢复、网络管理人员的误操作等事件局部化；让快速自愈能力不依赖于另一套复杂的网络(如SDH/SONET)；让组播树自然形成；让骨干网地址空间与用户地址空间相分离；对用户不良行为易于追踪。

    任何想在Internet上做的改革或在Internet上使用一项新的技术，都必须与原有的Internet各种协议完全兼容，否则将是不可行的。

2 层次交换网络基本结构
    早期设计Internet时，一个核心的思想就是要保证可靠性。这样做有充足的理由：当时的信道失效率和误码率都很高；希望在自然灾害或战争环境下网络有很好的可存活性。但绝对没有一个设计者想到过将来这个网络怎样用于话音和视频等实时多媒体应用。甚至连这个网络的用户群体和使用规模都是他们始料不及的，不然的话，很容易设计的地址空间问题，就不会让后人这样费尽周折了。他们从可靠性出发，各种设计都采取了无中心、分散、分布的思想。以太网是最典型的网络结构，由粗缆或细缆相连的多台计算机，没有主次，没有控制者或协调者，任何一台计算机的失效，都不会影响其他计算机的通信。Internet网络的拓扑结构，用的是格状网(Mesh)任意连接结构，没有中心，没有层次，想怎么连就怎么连，只要每个路由交换设备有两条或两条以上信道，就认为可靠性获得了很大提高。IP地址的安排，以网号为基础，辅以网内主机号。而在路由算法中起决定性作用的网号是一维平铺(Flat)的，没有任何结构，更没有层次性。对一维平铺的IP网络地址，当其数量十分庞大时，既不能设计出高效的路由信息交换算法，也无法设计出快速的路由表查询算法。这就是路由问题的症结所在。

    其实，任意连接的结构和一维平铺的地址空间并不适合人类的思维模式和计算机高效处理的要求，更缺少可扩展性，只有在非常小的系统中才能以其简易而获得应用。人类社会的组织结构和地址空间，无一不是层次式的，例如一个国家、一个学校、一个企业、一支部队、邮政地址空间、学科分类、图书编目等等，几乎找不出非层次性的组织。传统的电话系统是一个可管可控、可扩展并能保证通信质量的成功系统，也是层次式的。Internet的域名系统，最初是一维平铺的，连网计算机数量达到数百台时，就无法使用了，不得不中途改为层次式结构。以太网的结构，再也没有人用总线方式了，改用集线器(HUB)或交换机，端口不够或距离延伸时，将多个交换机级连，变成了典型的星形或树形的层次结构。层次式结构无处不在。从管理的角度看，层次式结构本身代表了一种分散/分布性，该由下级完成的事情，上级不必操心也无法操心，下级在自己的管辖范围内所做的变动，上级可以不知道，这使得系统充分可扩展。文献[1]是最早建议层次式结构的，由于其编址方法不够完善和灵活，没有摆脱路由的影响，没有得到重视。研究人员意识到当网络规模巨大时，首先受到挑战的是路由系统的扩展性，便都从层次化入手，提出了诸如地标分层[2]、地理分层、按因特网业务提供商(ISP)分层[3]等层次化方法。

    本文提出的层次式交换网络结构的基本想法是将整个网络划分为清晰而简单的两部分：骨干网与用户网，如图1所示。

3 树形结构的扩展
    虽然树形结构有优良的特性，但与现有的互联网任意连接的Mesh结构相比，缺乏结构上的灵活性。例如处于两个树叶位置的用户网之间通信，数据包必须上行到与对方属于同一棵子树的位置，才能开始下行，到达对方用户网，而实际上这两个用户网可能相距甚近。又例如，两个不同ISP在某城市A同时提供接入服务，就有两棵树延伸到该城市A，而这两个ISP树形网络的互连地点可能在外地的某大城市B。城市A中相距很近的两个用户网分别连到了不同ISP的树上，他们之间通信时，数据包可能会在一个ISP的树形网络中上行到城市B，在两个ISP树互连的地方进入对方ISP的树，再下行到城市A的对方用户网。如果这两个ISP的树形网络在城市A也有互连的信道，就避免了绕道城市B的通信。满足这种要求的网络结构例子如图4所示。

    短接信道连接中，不仅能将数据包转发到短接信道的对端，还可以转发到对端以外更远的地方。例如图4中，逻辑节点E’不仅能把目的地为J的数据包通过短接信道E’-J转发，还可以把目的地为L、M等远程逻辑节点的数据包通过E’-J转发。这涉及直接短接信道和间接短接信道技术，不再细述，详细请见文献[4]。

4 交换方法
    骨干网被组织成树形结构并配以一定数量的短接信道后，就可以取消任何形式的路由协议，对IP数据包进行简单的交换。以IPv6地址格式为例，低64比特用作接口标志，骨干网设备是不能利用的，高64比特为可路由地址，供骨干网设备转发IP数据包时用。

    IPv6地址结构中，SL部分给用户使用，从SF1开始到SL左边的部分是分配给ISP的。由于网络拓扑结构是树形的，ISP可以将得到的地址划分为多个不定长的字段，称为“交换字段”，每个交换字段对应树的一个层次，高位交换字段对应树的高层，依此类推。

    用户网络处于骨干网的边缘，发出的数据包总是从骨干树的叶节点进入，设该叶逻辑节点对应的交换字段为SFi，暂不考虑短接信道，其树结构数据包交换过程极其简单：

• 判断IP数据包中目的地址的前缀与本逻辑节点的地址前缀内容是否相等；
• 若不等，表示该数据包继续上行，选择上行信道，将数据包转发给上一层逻辑节点；
• 若相等，表明该数据包应该下行，根据交换字段SFi 的值，选择下行逻辑信道(例如交换字段SFi 的值等于5，就从逻辑信道5下行)，将数据包转发给下层逻辑节点。

    考虑短接信道的交换，在进行上述交换之前，先判断本逻辑节点是否有短接信道，如果有，则对应每一条短接信道都存在一张短接信道表，内容为信道对方的直接短接逻辑节点(短接信道连接的对方逻辑节点)和对方更远的间接短接逻辑节点的地址前缀。如果数据包地址前缀与该表中任一逻辑节点的地址前缀相等，则经短接信道转发；否则，直接执行上面介绍的树结构数据包交换算法。

    可见，一旦将地址结构与网络拓扑结构相关联，对用户数据包的交换极其简单，不需要全局交流的路由信息，仅根据数据包中目的地址的前缀和相应的交换字段值就可以完成数据包的交换。

5 层次交换网络的特点
    树形网络拓扑结构以及与地址结构相关联的特点为网络带来一系列的好处。

    首先，树形结构是一种确定性结构，数据包在网络中的流向是可预测的，因而网络行为也是可预测可确定的，网络成为可控制可管理的网络。ISP可以把网络管理简单地分成两层：逻辑节点的管理和全网的管理。前者监测逻辑节点中各交换机、逻辑节点中各内部信道、逻辑节点与其他逻辑节点之间的信道(外部信道)的状态、流量、性能及计费信息等。全网管理则更为简单，它只要综合各逻辑节点的管理信息，形成全网的网络状态图、外部信道负荷状态图以及收费数据库等全局信息和全局显示。另外，树形结构的网络是可扩展的，横向可以增加逻辑节点的扇出数，纵向可以增加树的层次数，以容纳更多的用户接入网。

    其次，由于通信路径的确定性，易于实现路径资源的管理、分配和准入控制，因而能提供真正意义上的服务质量保障(QoS)。要真正实现QoS必须在3个环节上加以控制和管理：资源管理，准入控制，输出调度。资源管理是对通信路径上的信道容量、端口缓冲能力等资源加以登记和分配，保证能满足已接纳的通信流能获得足够的资源。准入控制则依据资源管理中提供的资源余量信息，接纳或拒绝新的通信要求，防止过度的通信量争夺资源。输出调度则按照通信流不同的优先等级管理输出队列。目前的互联网是无法做到QoS的，连数据包走的路径都不确定，怎么能做到沿路径预留资源以及准入控制？

    第三，通信路径的确定性还使得通信负载的估算与信道容量的配备有了依据，避免当前网络中普遍存在的网络负载不均衡而造成的资源利用率低下，避免了复杂而效果不佳的流量工程(TE)带来的负担，使得信道容量的配备不再带有盲目性。

    第四，树形结构将网络拓扑结构与地址结构相关联，可以用IP交换代替IP路由，从而避免全网规模的路由信息交换，避免了路由表的维护、管理和更新，避免了为IP包查询庞大的路由表或其衍生出来的转发表。由于转发一个IP数据包的工作十分简单，大大提高了IP数据包的转发速度，提高了网络的性能。

    第五，树形结构使得网络事件局部化，例如任何节点或信道的失效和恢复，都不会影响远程的数据包交换算法。同时，逻辑节点的配置和管理，远比路由系统的配置和管理简单，网络运行维护人员的操作失误不大可能发生，即使有某些操作错误也不会像路由系统那样对全世界的网络产生影响。因为边界网关协议(BGP)不再存在，所有核心路由器每天都要处理数百万BGP更新和撤销的重负不再存在。

    第六，网络本身的安全得到了极大的加强。现有网络中，核心路由器端口的IP地址与用户主机IP地址处在同一个地址空间中，任何用户都可以组织对任何一个核心路由器的分布式拒绝服务攻击(DDOD)。在层次交换网络中，骨干网和用户网的地址空间可以很容易地分离，用户数据包只能穿越骨干网而不能打扰骨干网设备。另外，现有互联网中，用户可以使用虚假的源地址，逃避对其不良行为的追踪。层次交换网络体系结构中，用户网络的地址前缀与骨干网边缘设备端口的地址前缀是相同的，任何冒用其他用户网络源地址的行为立即得到判定并报警。而用户网内部的地址真实性管理是比较简单的。

    第七，逻辑信道技术控制了一批物理信道，拥有两方面的好处：个别物理信道的失效，略为减小了逻辑信道的总容量，仍能保证正常的通信，体现了信道自愈的能力，为提供QoS提供了必要条件；增加了扩充信道容量的手段，要增加逻辑信道的容量，既可以增大每根物理信道的带宽，也可以增加物理信道的数量。

    第八，网络设备的复杂性、可靠性、成本、耗电等都可以获得很大的改善。

6 层次交换网络的部署
    对现有系统作革新性的改造，能否成功的关键是部署问题，既要使用新系统，又要兼容原有系统，两者要能简便地实现互通。目前IPv4与IPv6的关系，就存在这个致命的不兼容问题，导至IPv6部署缓慢。由于层次交换网络与现有网络共存时，既不要求现有网络作任何修改，也不涉及应用层问题，从部署的角度看，层次交换网络可以采用局部地、渐进地部署的方法。

    目前的Internet技术，由于GE、10GE甚至100GE技术与长途高速传输技术(例如10 Gbit/s、40 Gbit/s甚至100 Gbit/s)同步地发展，使得能用于长途骨干网的速率，也能十分方便地用于用户接入网。这些速率对骨干网显然不够，且由于路由器的“瓶颈”，不能充分发挥光纤的每秒太比特传输能力，但对用户接入网而言，它所面临的是有限的用户群体，保留了现有的路由技术，也能满足对话音、视频和数据通信的需要。互联网的致命缺陷在用户网络中并不紧迫。

    骨干网就不同，除了非实时应用外，它可能要对付成十万、百万甚至千万的视频和话音通信流。低效率、低速度、不能快速自愈、难以实现组播、不能有效解决QoS保证机制的路由结构，就是解决“三网融合”的关键性障碍所在。解决骨干网的问题是目前的当务之急。其实，Internet界正在研究的无数企图解决QoS的方案、方法，无一不是针对骨干网络的。遗憾的是，这些方法异常复杂，效果甚微，难以部署，甚至连制订标准都难以完成。

    向层次交换骨干网过渡，以ISP的骨干网或骨干网的一部分为单位来部署比较合宜。层次网络的地址结构，只要地址空间足够大，便于划分层次就行，因而可以直接使用IPv6地址结构进行层次交换。

    如果注意一下当前各ISP骨干网络的拓扑结构，可以发现，除了顶层有一批(通常也只有10多个)核心节点以环形、环形加任意连接、全连接等方式互连外，往下层的延伸，无一例外地采用了层次式的树形结构。如果把这些顶层核心节点组织在一个(或几个)逻辑节点中，向下层延伸时自然构成了一棵树。这种发现并不奇怪，是组网时受地理位置的影响而自然形成的。只是我们采用了路由系统后，无法利用这种树形结构的特性，把本可以有序地加以组织的网络结构变成了一个无序的混沌巨系统(自然界存在很多混沌巨系统，人造系统中，只有互联网有此属性)。因此，把现有骨干网改造成层次交换网络时，人们完全可以对现有的网络拓扑(节点和信道组成)不作任何改动，只做逻辑上的划分和逻辑节点控制软件的变动。

    层次结构也可以向用户接入网推进，使得用户网络中只有层次交换逻辑节点和以太网交换机或只用以太网交换机，网络管理的技术难度将大幅度降低。

7 结束语
    新的层次交换网络体系结构，克服了现有互联网的几乎所有缺陷，证实了Rekhter定律的正确性[5]。本文描述的层次交换网络系统，已经实现了多个原型系统和样机，在实验平台上进行了性能测试，并在办公室的网络中进行了长时间的使用，提供对外界IPv6和IPv4网络的访问能力。使用结果表明，想法是可行的，实现是简单的，性能是满意的。

8 参考文献
[1] KLEINROCK L, KAMOUN F. Hierarchical routing for large networks: Performance evaluation and optimization[J]. Computer Networks, 1977,1(3):155-174.
[2] TSUCHIYA F. The landmark hierarchy: A new hierarchy for routing in very large networks[C]//Proceedings of Symposium on Communication Architectures and Protocols (SIGCOMM’88),Aug 16-18,1988,Stanford, CA, USA.New York, NY,USA: ACM, 1988: 35-42.
[3] FRANCIS P. Comparison of geographical and provider - rooted Internet addressing[J]. Computer Networks and ISDN Systems, 1994,27(3):437-448.
[4] 钱华林, 葛敬国, 李俊. 层次交换网络体系结构[M]. 北京: 清华大学出版社, 2008.
[5] MEYER D, ZHANG L, FALL K. Report from the IAB workshop on routing and addressing[R]. IETF RFC 4984. 2007.

收稿日期：2010-01-07

    如果把图4中的虚线信道与实线信道等同看待并且还可以继续增加虚线信道的话，网络的拓扑结构与现有的互联网没有差别了，通信可以减少甚至消除经过上层节点的绕道，获得了充分的灵活性。但这样的网络结构破坏了树结构的优异特性。为了既不失去网络结构的灵活性，又保持树形结构的优良特性，应当把图4中的实线信道与虚线信道加以区分，分别称为“树信道”和“短接信道”(或称“直达信道”)。短接信道可以是单根物理信道，也可以是由多条物理信道组成的逻辑信道，就信道而言，与树信道没有差别，但在交换用户数据包时，短接信道被看作特例而优先加以处理。

    图3表达了一棵树中最基本的部分。实际上，一个上层节点可以有大量的下层节点，一个下层节点可以有自己的下层节点。黑色方块表示IP交换机，两台或更多的交换机可以组成一个逻辑节点。逻辑节点内部的各交换机用高速信道相互连接。逻辑节点控制软件可以使内部各交换机对外呈现单一节点的特性。在上下层逻辑节点之间，用一组物理信道将两个逻辑节点中的IP交换机相互连接。在逻辑节点软件的控制下，这组物理信道构成一条逻辑信道(图3中用虚线圈在了一起)。这样的结构，从逻辑上看，是严格的树，从物理上看，连接复杂，没有单点失效问题。

    树形结构最致命的缺陷是任何节点或信道的单点失效将造成相应子树的断连。利用逻辑节点和逻辑信道的概念可以克服这种缺点，如图3所示。

    图1中，所有的通信主体都来自用户网，即只有用户网内部或用户网之间的主机(泛指个人计算机、服务器以及任何能入网进行通信的有线或无线连接的终端等)才需要互相通信，没有用户要求与骨干网中的设备进行通信。骨干网的功能极其简单，只要把来自一个用户网的数据包转发到另一个用户网。因此，骨干网可被看成一个巨大的IP交换机。然而对大规模的系统，不可能做出一个能连接全世界所有用户网的大型交换机。这个虚拟大型交换机的一个最简单清晰的物理实现，就是一棵树，结构演变成图2。虽然图2中的骨干网树形结构只示意性地画了两层，它可以像电话网一样由多层组成。

[摘要] 文章认为互联网核心设备不堪重负、网络行为难以预测、数据包路径不确定、可控可管和可扩展性差、无法实现服务质量保障、网络设施易受攻击、核心路由设备复杂昂贵耗电等一系列缺陷，是由互联网的路由系统引起的。文章提出一种新的网络体系结构，将网络拓扑与网络编址相结合，提出逻辑节点和逻辑信道的概念保证树形结构的可靠性，用短接信道技术提供连接的灵活性，以简单的IP交换替代IP路由克服现有网络的各种缺陷。

[关键词] 路由系统；IP交换；树形结构；网络拓扑结构

[Abstract] The Internet of today is facing serious challenges including lack of routing system scalability, unpredictable network behaviour, uncertainty of data packet paths, poor control and manageability, unachieved Quality of Service (QoS), vulnerability of network facilities to DDOS attacks, core router complexity, costliness, and high power consumption. All of these defects have their root cause in the routing system. This paper first proposes a new network architecture which combines the network typology with addressing. Then, it highlights that reliability of the tree structure is guaranteed by the concepts of logical node and logical link. Furthermore, shortcut link technology supports the flexibility of tree topology, and IP routing is replaced with IP switching. As a result, all flaws in the current Internet architecture would be overcome.

[Keywords] routing system; IP switching; tree structure; network topology