路由器技术的发展趋势

文章编号：1009－6868(2001)04－0019－05 文献标识码：A 中图分类号：TN915.05

　　因特网正飞速发展，主要表现在如下几个方面：xDSL、HFC和无线接入等多样化的宽带接入技术，视频点播、电子商务等多样化的网络应用，DWDM技术的出现使得网络干线带宽的成倍增加和几乎畅通无阻。新的应用对因特网提出了更多更高的要求，其中最重要的便是服务质量保证。服务质量保证对于这些新应用的成功实施具有重要的意义，同时网络服务质量保证能力的提高又能促进更多新应用的出现。网络服务质量的保证通常有两种途径：在有限网络带宽的基础上采用先进的服务质量(QoS)保证机制，或者提供足够的网络带宽。不论采用那种途径都会涉及到网络的三大组成部件：网络终端设备、网络链路、网络交换或者中转接点(这里指路由器)。目前，网络链路的带宽由于 DWDM技术的出现已经得到了成倍的增加，同时网络终端设备的处理能力也基本能满足各种新应用的需求。然而路由器的速度却跟不上链路带宽的飞速增长，正成为整个因特网发展的瓶颈所在；同时路由器是整个因特网的核心组件，需要有更多更好的智能性，这对提高整个网络的性能起着重要的作用。

　　高速化和智能化正成为下一代路由器的发展方向和目标。未来核心路由器可能的发展方向是：混合式输入输出排队的体系结构、分布式的队列调度机制、并行式输入调度技术、分组转发速度的高速化、分组处理的职能化(可能会借助于网络处理器)。

　　1 路由器工作原理

　　路由器工作在OSI七层协议的第3层——网络层。它负责接收来自各个网络入接口的分组，并把分组从其相应的出接口转发出去。这里涉及到两个方面：首先找到分组相应的出接口，这只需查找路由表即可，因为每个路由器都会有一个(通过路由协议来形成的)路由表；其次把分组从入接口发到出接口，这取决于路由器的体系结构。

　　路由器的功能可以分为两个层面：控制通路和数据转发通路。控制通路主要完成系统配置和管理、选路等功能，它负责维护、更新和发布路由表的信息。数据转发通路只是通过查路由表来完成相对简单的数据转发，主要包括：转发决策、入口和出口之间的转发、出口链路调度。设计高速路由器的关键是提高分组转发的速度，主要便是提高数据通路各功能部件的处理速度。

　　(1)分组转发决策

　　每到来一个分组时，根据分组中所携带的目的地地址来对路由表进行搜索，从而得到此分组的输出端口。同时，下一跳媒体访问控制子层(MAC)地址附加到分组的前面，另外原来IP分组头中的透明链路层(TTL)字段减1(如果TTL为零，则丢弃此分组)，然后生成新的头校验和。

　　(2)入口和出口之间的转发

　　其具体的转发方式取决于路由器的体系结构。如果采用共享缓存的方式，则共享缓存区作为入口和出口之间交流数据的一个场所，入口往里面写数据，出口从里面读取数据。另外，分组也可以通过入口和出口之间的背板(Backplane)进行传输。

　　(3)出口链路调度

　　当分组到达出口时，在发往链路之前，可能需要排队等候。传统的路由器大多采用先入先出(FIFO)的排队方式。但是先进的路由器会为不同的业务流提供不同的分组队列，在这些不同的队列之间采用优先级调度、轮询调度、公平排队等调度机制来为不同的业务流提供更好的服务质量保证，包括丢包率、调度时延、吞吐量等。

　　由于路由器涉及到对分组的接收和发送，排队现象不可避免，这种排队在入接口和出接口上都可能发生，随之而来的便是对队列的管理和调度。另外，即使是在一个入接口上，也会收到来自不同业务流的分组，如果要对不同的业务流提供不同的服务质量，就需要路由器首先对这些进来的业务流进行区分或者分类，然后再对这些业务流进行不同的处理。对业务流的区分由专门的业务流分类算法来完成，业务流分类是控制通路所要完成的功能之一。

　　2 路由器体系结构

　　评价路由器性能好坏的指标参数通常有如下几个方面：

• 高分组转发速率。考虑到网络规模的扩大、应用的急剧增加以及链路带宽的增加，路由器必须具有高速的分组转发速度。
• 多业务支持。由于大多数的骨干网络都支持ATM和IP，所以路由器必须能够支持这些不同的网络业务流。
  
• 确定性小的调度时延。实时的语音和视频业务流在通过网络时需要可预知的且较小的时延，这需要路由器的支持。
  
• 服务质量。路由器还必须能够给不同的业务流提供区分的服务质量保证，而且这种区分的服务质量是可配置的。
  
• 对组播的有效支持。组播业务将会成为未来因特网上的一种重要业务，路由器必须能够提供对大量组播业务同时传输的有效支持。
  
• 高可用性。用在骨干因特网上的高速路由器需要处理大量不断的数据传输，不允许因为软件升级等原因而突然停止工作。
  

　　2.1 传统的路由器

　　传统的路由器主要基于一个通用的计算机来进行构建(见图1)，是一种基于单总线、单CPU的结构，包括一条共享中央总线、一个中央处理器、内存、一些输入输出线路卡。其分组处理过程如下：每个从线路卡入端口进来的分组首先经过共享总线送到中央处理器进行转发决定处理，然后再经这一条共享总线发到相应的出端口。这种单总线单CPU体系结构的路由器性能受到很大的限制，原因是单个的中央处理器要完成所有的处理任务会限制系统总的吞吐率。另外每个分组必须经过共享总线两次，所有的分组都争用这一条总线，这也大大限制了路由器总吞吐率的提高。

图1 传统路由器体系结构

　　2.2 单总线多CPU结构路由器

　　为了解决单CPU的处理瓶颈，随后又出现了多CPU的体系结构(见图2)，每个线路卡上都有一个独立CPU，实现了简单的并行处理。线卡上各个独立的CPU负责收发本接口的数据包、管理收发分组单元、查询本地路由表、作出转发决定。每个分组从入口到出口只需经过共享总线一次。中央处理器则完成路由器所有的其他控制、配置和管理功能。所有收到的控制分组都会送到中央路由器里进行处理，然后再把一些控制信息(比如路由表更新消息)回送到各线卡上去。另外，现在有的路由器在线卡上用基于特定应用的ASIC芯片取代通用的CPU处理芯片来进一步提高转发决定、队列管理和调度、总线访问仲裁等的处理速度，这是因为尽管通用CPU处理芯片的速度在一直增加，但还是跟不上线路速度的增加。这种体系结构的优点是：分组的转发决定由每个线卡上独立的CPU来完成，数据分组只经过共享总线一次，线卡上有路由高速缓存(Cache)能进一步加快转发决定的速度。

图2 单总线多CPU路由器体系结构

　　2.3 基于交换矩阵的路由器

　　单总线结构路由器的最大缺陷在于一次只能有一个分组从入口交换到出口。如果能在入口和出口之间有多条数据传输通路，则能解决这种问题，同时大大提高系统的吞吐率。基于这种想法，同时借鉴ATM交换机结构的优点，提出了基于交换机结构的新一代路由器体系结构(见图3)。一个N×N的非复合交换机构由N2个交换开关构成，分组可以直接从输入端经过交换开关流向输出端。交换机构可以允许多个分组同时通过不同的线路进行传送，从而使系统总的吞吐率得到显著的提高。在这种结构中，可能在入口和出口都存在分组的排队现象，会涉及到输入和输出侧的队列调度机制。同时为了缓解输出侧和交换机构的压力，先进的路由器大都提供了“后压(Backpressure)反馈”的流控机制，当输出端队列发生拥塞时，它可以主动向输入端发一个反馈信号，要求降低其流量注入速度。这类似于以太网中的后压流控机制。这种结构由于其较高的分组转发速度和良好的可扩展性，是设计未来高速核心路由器的一种较为理想的方案。

图3 基于交换机结构的路由器体系

　　2.4 未来光交叉连接路由器

　　由于DWDM及其相关技术的飞速发展和商用化，光互联网已经成为未来因特网发展的一个重要趋势和方向。光互联网的一个重要问题是如何解决IP over DWDM，最为重要的设备便是可能需要有路由功能的光交叉连接设备(OXC)，本文暂且称为光交叉连接路由器。最近AT＆T的研究人员提出了一种基于光交叉连接的智能路由器结构(见图4)，它包括了电路由器的功能和光层交叉连接的功能。IP层负责完成电域的一些较为复杂的控制管理功能，包括：寻址、路由、全网拓扑发现、业务量工程、服务质量控制、对光资源的管理(光路的建立和波长的分配)、网络故障恢复等。光层交叉连接器(OLXC)负责连接入口和出口之间的高速光通道，它通过交换式的光通路来提供高速动态的连接。IP层拥有光层的资源，对之进行分配和管理，负责各光交叉连接路由器之间信令和控制消息的处理，而光层只需要负责简单的传输即可。

图4 未来光交叉连接路由器

　　2.5 主动网络路由器

　　随着主动网络技术的发展和进一步成熟，主动网络路由器的需求不可避免。这种路由器需要提供可编程的能力，能够执行分组里携带的代码，或者根据每个分组里提供的特殊信息对分组进行不同的路由选择或转发处理。主动式路由器可以在现有路由器硬件结构的基础上添加数据分组主动处理功能而构成。最近，华盛顿大学的研究人员提出了一种高性能主动式路由器体系结构(见图5)。每个物理接口上包括一个端口处理器(PC)和一个处理引擎(PE)。PC完成对分组的分类、缓存和调度，主要由一个分组分类和排队的处理芯片来完成；PE通过一个主动处理芯片(APC)来完成对分组的个性化处理，主动处理芯片通常包括一个或者几个带动态随机存储器(DRAM)的处理器，处理器之间、处理器与队列控制器之间、处理器与片外动态随机存储器之间通过主动处理芯片上I/O通道进行通信。

点击放大
图5 主动式路由器

　　可编程的PE可以用现在已经基本商用的网络处理器(NP)来实现。NP是一种芯片级的系统设计，通常把处理器、内存、输入输出做在一个单独的ASIC芯片上。NP可以实现从数据链路层到应用层的编程处理，可以提供更多的个性化、智能化、主动式的服务。目前常见几种NP的性能比较见表1。

　　表1 几种常见网络处理器(NP)的性能比较

　　3 业务流分类技术

　　新的网络应用的出现对路由器提出了更多的功能需求，比如服务质量管理和控制、安全控制、记费管理等。这需要路由器必须具有有效的业务流分类技术。IP流分类技术的实质在于给定N条规则库，根据IP分组里的一些字段来判断此分组最符合规则库里的哪条规则。IP流分类问题是一种最佳的规则匹配问题，其性能指标主要有：分类速度、占用内存大小、可扩展性。目前出现的分类算法主要有：递归流分类(RFC)算法、元组空间搜索算法(Tuple Space Search)、无冲突哈希搜索算法、基于树的搜索算法等。其中RFC算法在时间效率上是最好的，但其预处理过程随着过滤规则的增加会消耗大量的内存。而无冲突哈希搜索在整体性能上更好，其查找速度接近RFC，而内存消耗远比RFC小得多。IP流分类技术的可能趋势是多种搜索算法的综合，以取长补短。

　　4 队列管理技术

　　在网络发生拥塞时，路由器必须丢弃分组，那么必然涉及到的问题便是路由器选择丢弃什么分组?在什么时候丢弃分组?如果只是在拥塞发生时才丢弃分组，则在网络时延较大的情况下，其控制效率可能会很低；如果不加选择地丢弃到达的分组，则可能会连续地丢弃同一个TCP连接的多个分组，从而导致发送方超时重传和拥塞窗口(CWND)的骤减，使TCP的吞吐量无法提高。为了解决这些问题，就必须实施有效的队列管理机制(或缓冲区管理策略)。

　　目前，队列管理技术的趋势是以随机早期探测(RED)为代表的主动式队列管理机制(AQM)。RED中设置了两个队列门限值。当平均队列长度大于大门限时，分组丢弃概率为1；当平均队列长度小于小门限时，分组丢弃概率为零；当平均队列长度位于二者之间时，丢弃概率为与平均队列长度递增相关的一个函数。RED算法允许短时的分组突发，因而可以避免因为网络负荷变化造成的分组丢弃。RED能避免多个TCP连接同时超时重传，从而保持高的带宽利用率。但是RED算法对参数设置的依赖性较强，所以在复杂网络环境下，其性能可能会出现不稳定性。因此近年来出现了一些自适应的参数可调的基于RED的算法设计的性能更稳定可靠的主动式队列管理机制。一个趋势是在设计AQM时，可以直接采用即时的物理队长作为控制的参数，另外就是必须同端到端的传输控制协议进行有效的结合。

　　5 队列调度技术

　　队列调度算法与路由器的交换结构有一定关系，如果采用输出排队，则有WFQ、EDF、RR等调度算法。如果采用输入排队，则此时的调度算法实际上为输入端口与输出端口之间的匹配算法，目前主要有最大匹配算法、随机匹配算法、并行迭代算法(PIM)、最长队列优先(LQF)、最早信元优先(OCF)、指针滑动多次迭代循环优先级别匹配算法(iSLIP)等。由于链路速率的不断提高，未来交换结构的趋势将是输入排队或者输入和输出混合的排队方式。输出排队调度算法以WFQ为代表，但目前的现实是缺少性能好又易于实现的调度算法。输入排队调度算法目前缺乏可快速的、有效的、可支持带宽预约、组播和公平性的匹配算法。

　　参考文献

1 Hjlmtysson G,Yates J,Chaudhuri S ,Greenberg A.Smart Routers－Simple Optics: An Architecture for the Optical Internet.IEEE/OSA Journal of Lightwave Technology, 2000,18(12)
2 Wolfand T ,Turner S J.Design Issues for High－Performance Active Routers. IEEE JSAC,2001,19(3):404－409
3 Singhal A ,Jain R.Terabit Switching:A Survey of Techniques and Current Products.http://www.cis.ohio－state.edu/jain/papers/terabit.htm

[摘要] 文章对路由器中的一些关键技术，主要包括路由器工作原理、路由器体系结构、业务流分类技术、队列管理技术、队列调度技术，进行了较为详细的描述和分析。

[关键词] 高速路由器 体系结构 流分类 队列管理 队列调度

[Abstract] Key technologies of high-speed router, such as the working principle and architecture of router, flow classification technology, queue management technology and queue scheduling technology, are described and analyzed in detail

[Keywords] High-speed router Architecture Flow classification Queue management Queue scheduling