再谈路由器之关键技术
路由器的两大功能
数据通路功能：对于每个到达路由器的数据**，在不丢失的情况下，负责寻路。此功能主要**括：转发决定，经由背板输出链路队列调度。转发功能是通过专门硬件来实现的，每一个通过路由器的分组**都要执行这个践作。数据通路功能对改进路由器的性能是很重要的。
控制功能：主要**括路由表的管理和系统的配置与管理，以及与相邻路由器交换路由表信息，通过软件实现等。这些功能不是针对每个数据**的，因此使用频度相对低一些。
路由器的关键技术问题
就目前路由器设计中的一些关键技术，有的问题已经取得了阶段性的成果，有的才刚刚开始研究。需要说明的是，这个领域的发展非常快。为了便于系统地理解这些关键技术问题，我们根据路由器发展的三大趋势，大致将这些问题分为三类。一是与高速有关的问题，如路由表快速查找、总线背板和交换结构等。二是QoS问题，如数据流和数据**的分类，流量工程和阻塞控制等。三是与软件有关的问题，如软件的稳定性、配置和管理等。需要说明的是，这种分类法并不严格，有些问题可以同时属于两类。
1.与速度有关的技术
路由表的快速查找技术
为了解决地址资源紧缺，减少路由表的规模，降低管理难度，互联网采用了CIDR（Classless Inter-Doma in Routing）。这样，路由表中存放的不是一个个具体的IP地址，而是可变长度的网络前缀。路由器在对IP**寻址时，采用 长的网络前缀匹配（LPM- Longest Prefix Matching）。例如，假设路由表中有两个表项“202.168.X.X，输出端口1”和“202.168.16.X，输出端口2”（X表示任意），如果有一个IP**的目的地址为202.168.16.5，那么这个**应该从端口2输出。传统的路由器执行 长网络前缀匹配的时间很长，使得路由表查找成为路由器速度的瓶颈。 近两年出现了一些快速查表算法，能够支持吉比特链路。这些算法**括改进的精确匹配法、基于trie法、并行硬件法、协议改变简化路由表的查询和缓冲法等。这些算法，有些易于硬件实现，有些适合软件实现。对于组播地址寻址，要根据IP**的源地址和组播地址查表，对源地址采用 长前缀匹配法，对目的地址采用精确匹配法。
交换结构和调度算法
交换结构有Crossbar、共享存储器和总线三种方式。Crossbar结构的速度由调度器决定，共享存储器结构的速度由存储器的读写速度决定，共享总线结构的速度由总线的容量和仲裁的开销决定。调度器是Crossbar交换结构的核心，它在每个调度时隙内收集各输入端口有关数据**队列的信息，经过一定的调度算法得到输入端口和输出端口之间的一个匹配，提供输入端口到输出端口的通路。采用输入缓冲无阻塞方式的Crossbar，用ESLIP算法实现调度已被一些厂家所采用。调度器设计的难点在于，既要满足系统吞吐率达到100％的要求，又要支持CoS(Classes of Service)。调度算法中，加权公平排队算法（WFQ-Weighted Fair Queuing）和经过改进后的加权公平流排队算法（WF2Q-Weighted Fair Flow Queuing）比较容易实现，而且性能也不错。总之，要让互联网真正能够综合多种业务，作为网络连接核心设备的路由器，必须提高端口速率和交换容量，提供QoS保证和流量工程（TE-Traffic Engineering）功能。
背板总线
由于端口速率高，交换结构需要加速，而且接口板与交换板之间、控制板与接口板之间、控制板与交换板之间的连线很多，目前的高速路由器以及交换机都采用高速背板总线以提高系统的吞吐率。为了提高效率，数据线采用串行差分线路，速率可达每秒钟1～2吉比特。要保证如此高的传输速率和那么多的连线，对背板总线的设计要求非常高。如何降低数据的传输误码率以及保证时钟同步是总线设计中的关键技术。斯坦福大学的Tiny Tera路由器项目中，大量采用串行总线的实现方法值得研究和借鉴。
2.与服务质量有关的技术
数据**分类技术
路由器要对到达的分组**进行识别、分类以决定其所应接受的服务类型。当初IETF所考虑的方案是在网络的核心，根据IP报头的TOS（Type of Service）域来识别分组，但是在互联网的发展过程中，由于一直采用“尽力”传输，同时由于终端在发送IP**时不考虑TOS，因此，TOS一直没有发挥作用。目前在边缘设备，根据IP分组的源IP地址、目的IP地址、源端口号、目的端口号、传输层协议类型来对分组进行识别。此外，为了实现防火墙的功能也需要对IP分组进行识别。
在识别时，每条识别规则采用的是源IP地址、目的IP地址、源端口号、目的端口号、传输层协议类型。在上述识别规则中，每个域都可能是一个区间。例如有这样一条识别规则“202.66.83.X，202.66.72.X，X，23，TCP”（X表示任意），这条规则识别从网络202.66.83.X到网络 202.66.72.X的telnet数据。从几何的角度来看，假如判别时利用了IP报头的K个域，这个问题实际上是在一个K维空间中有许多互相交叠的实体（每条判别规则对应于一个实体），每当有一个分组到达时，该分组相当于K维空间上的一个点，进行判别实际上是要找出**含该点的优先级 高的实体。
数据流的分类
一系列通过给定的源和目的地的数据**被作为数据流，流可以是长时间维持的TCP连接的一系列数据**，也可以是声音或图像的一系列UDP数据**。通常，流有长短之分，划分有两个标准：端口对和主机对。按端口对划分是指同一流的数据**必须具有相同的源、目的地址和TCP/UDP端口号等；按主机对划分只要求各数据**具有相同的源和目的地址。目前常用的流分类器有三种，一种是X/Y分类器，Y为规定的时间间隔，X为数据**数。若在时间Y内某一数据流到达的数据**数大于X，则该流就被认定为长数据流，否则是短数据流；另一种是协议分类器（Protocol Classifier），它规定了所有的TCP**均被定义为数据流；还有一种是端口分类器（Port Classifier），它规定了几个特殊的TCP端口作为长数据流。因为分类要对每个进入路由器的**进行**头检查，我们需要快速的分类算法。
QoS问题
如果能实现真正的QoS，对于互联网变为一个商业应用的网络来说，当然是 理想的。在目前网络阻塞无法避免的情况下，IETF提出了一些模型和机制来支持 QoS，主要有两种实现框架，即IS（Integrated Service）和DS（Differentiated Service）。其中，IS应用资源预留协议（RSVP），在实时业务发送前建立发送通道并预留资源；而DS通过给数据**做标记将数据**分类，使不同的数据**享受不同的服务。实现真正的QoS有一定的难度，无论是采用输出缓冲,还是共享缓冲的交换结构，内部都需要N倍的加速。
MPLS和流量工程
在互联网上，可以通过MPLS支持显式路由。显式路由可以弥补传统IP网络中OSPF（Open Shortest Path First）协议在源和目的之间只建立一条 短路径的不足。它的好处是，ISP可以在两点之间的不同路径上分配业务量，从而减少业务繁忙的路径的阻塞率，提高线路的利用率，提供一定程度的QoS保证。还可以通过显式路由建立冗余线路，在某些路由器发生故障的情况下，保证通信线路的畅通。IETF的相关工作组和许多网络设备厂商正在进行这方面的工作，并且已经提出了一些实现方案。
数据通路功能：对于每个到达路由器的数据**，在不丢失的情况下，负责寻路。此功能主要**括：转发决定，经由背板输出链路队列调度。转发功能是通过专门硬件来实现的，每一个通过路由器的分组**都要执行这个践作。数据通路功能对改进路由器的性能是很重要的。
控制功能：主要**括路由表的管理和系统的配置与管理，以及与相邻路由器交换路由表信息，通过软件实现等。这些功能不是针对每个数据**的，因此使用频度相对低一些。
路由器的关键技术问题
就目前路由器设计中的一些关键技术，有的问题已经取得了阶段性的成果，有的才刚刚开始研究。需要说明的是，这个领域的发展非常快。为了便于系统地理解这些关键技术问题，我们根据路由器发展的三大趋势，大致将这些问题分为三类。一是与高速有关的问题，如路由表快速查找、总线背板和交换结构等。二是QoS问题，如数据流和数据**的分类，流量工程和阻塞控制等。三是与软件有关的问题，如软件的稳定性、配置和管理等。需要说明的是，这种分类法并不严格，有些问题可以同时属于两类。
1.与速度有关的技术
路由表的快速查找技术
为了解决地址资源紧缺，减少路由表的规模，降低管理难度，互联网采用了CIDR（Classless Inter-Doma in Routing）。这样，路由表中存放的不是一个个具体的IP地址，而是可变长度的网络前缀。路由器在对IP**寻址时，采用 长的网络前缀匹配（LPM- Longest Prefix Matching）。例如，假设路由表中有两个表项“202.168.X.X，输出端口1”和“202.168.16.X，输出端口2”（X表示任意），如果有一个IP**的目的地址为202.168.16.5，那么这个**应该从端口2输出。传统的路由器执行 长网络前缀匹配的时间很长，使得路由表查找成为路由器速度的瓶颈。 近两年出现了一些快速查表算法，能够支持吉比特链路。这些算法**括改进的精确匹配法、基于trie法、并行硬件法、协议改变简化路由表的查询和缓冲法等。这些算法，有些易于硬件实现，有些适合软件实现。对于组播地址寻址，要根据IP**的源地址和组播地址查表，对源地址采用 长前缀匹配法，对目的地址采用精确匹配法。
交换结构和调度算法
交换结构有Crossbar、共享存储器和总线三种方式。Crossbar结构的速度由调度器决定，共享存储器结构的速度由存储器的读写速度决定，共享总线结构的速度由总线的容量和仲裁的开销决定。调度器是Crossbar交换结构的核心，它在每个调度时隙内收集各输入端口有关数据**队列的信息，经过一定的调度算法得到输入端口和输出端口之间的一个匹配，提供输入端口到输出端口的通路。采用输入缓冲无阻塞方式的Crossbar，用ESLIP算法实现调度已被一些厂家所采用。调度器设计的难点在于，既要满足系统吞吐率达到100％的要求，又要支持CoS(Classes of Service)。调度算法中，加权公平排队算法（WFQ-Weighted Fair Queuing）和经过改进后的加权公平流排队算法（WF2Q-Weighted Fair Flow Queuing）比较容易实现，而且性能也不错。总之，要让互联网真正能够综合多种业务，作为网络连接核心设备的路由器，必须提高端口速率和交换容量，提供QoS保证和流量工程（TE-Traffic Engineering）功能。
背板总线
由于端口速率高，交换结构需要加速，而且接口板与交换板之间、控制板与接口板之间、控制板与交换板之间的连线很多，目前的高速路由器以及交换机都采用高速背板总线以提高系统的吞吐率。为了提高效率，数据线采用串行差分线路，速率可达每秒钟1～2吉比特。要保证如此高的传输速率和那么多的连线，对背板总线的设计要求非常高。如何降低数据的传输误码率以及保证时钟同步是总线设计中的关键技术。斯坦福大学的Tiny Tera路由器项目中，大量采用串行总线的实现方法值得研究和借鉴。
2.与服务质量有关的技术
数据**分类技术
路由器要对到达的分组**进行识别、分类以决定其所应接受的服务类型。当初IETF所考虑的方案是在网络的核心，根据IP报头的TOS（Type of Service）域来识别分组，但是在互联网的发展过程中，由于一直采用“尽力”传输，同时由于终端在发送IP**时不考虑TOS，因此，TOS一直没有发挥作用。目前在边缘设备，根据IP分组的源IP地址、目的IP地址、源端口号、目的端口号、传输层协议类型来对分组进行识别。此外，为了实现防火墙的功能也需要对IP分组进行识别。
在识别时，每条识别规则采用的是源IP地址、目的IP地址、源端口号、目的端口号、传输层协议类型。在上述识别规则中，每个域都可能是一个区间。例如有这样一条识别规则“202.66.83.X，202.66.72.X，X，23，TCP”（X表示任意），这条规则识别从网络202.66.83.X到网络 202.66.72.X的telnet数据。从几何的角度来看，假如判别时利用了IP报头的K个域，这个问题实际上是在一个K维空间中有许多互相交叠的实体（每条判别规则对应于一个实体），每当有一个分组到达时，该分组相当于K维空间上的一个点，进行判别实际上是要找出**含该点的优先级 高的实体。
数据流的分类
一系列通过给定的源和目的地的数据**被作为数据流，流可以是长时间维持的TCP连接的一系列数据**，也可以是声音或图像的一系列UDP数据**。通常，流有长短之分，划分有两个标准：端口对和主机对。按端口对划分是指同一流的数据**必须具有相同的源、目的地址和TCP/UDP端口号等；按主机对划分只要求各数据**具有相同的源和目的地址。目前常用的流分类器有三种，一种是X/Y分类器，Y为规定的时间间隔，X为数据**数。若在时间Y内某一数据流到达的数据**数大于X，则该流就被认定为长数据流，否则是短数据流；另一种是协议分类器（Protocol Classifier），它规定了所有的TCP**均被定义为数据流；还有一种是端口分类器（Port Classifier），它规定了几个特殊的TCP端口作为长数据流。因为分类要对每个进入路由器的**进行**头检查，我们需要快速的分类算法。
QoS问题
如果能实现真正的QoS，对于互联网变为一个商业应用的网络来说，当然是 理想的。在目前网络阻塞无法避免的情况下，IETF提出了一些模型和机制来支持 QoS，主要有两种实现框架，即IS（Integrated Service）和DS（Differentiated Service）。其中，IS应用资源预留协议（RSVP），在实时业务发送前建立发送通道并预留资源；而DS通过给数据**做标记将数据**分类，使不同的数据**享受不同的服务。实现真正的QoS有一定的难度，无论是采用输出缓冲,还是共享缓冲的交换结构，内部都需要N倍的加速。
MPLS和流量工程
在互联网上，可以通过MPLS支持显式路由。显式路由可以弥补传统IP网络中OSPF（Open Shortest Path First）协议在源和目的之间只建立一条 短路径的不足。它的好处是，ISP可以在两点之间的不同路径上分配业务量，从而减少业务繁忙的路径的阻塞率，提高线路的利用率，提供一定程度的QoS保证。还可以通过显式路由建立冗余线路，在某些路由器发生故障的情况下，保证通信线路的畅通。IETF的相关工作组和许多网络设备厂商正在进行这方面的工作，并且已经提出了一些实现方案。
看看百度收录：［ 再谈路由器之关键技术］
2009-5-26 12:55:49统计：［］
相关新闻
- 上一篇：交换机路由器安全防护之三种武器
- 下一篇：如何解决无线路由器应用中的ARP故障
