现代通信网络交叉开关交换结构调度算法

1、3. 交换结构(SWITCHING FABRIC)根据转发表对分组进行处理，将某个输根据转发表对分组进行处理，将某个输入端口进入的分组从一个合适的输出端口转发出去。入端口进入的分组从一个合适的输出端口转发出去。是路由器的关键构件是路由器的关键构件三类常用交换结构：三类常用交换结构： 共享内存、共享总线、共享内存、共享总线、 crossbar(交叉开关交叉开关)高性能交换结构及其调度算法是研制高速高性能交换结构及其调度算法是研制高速IPIP路由器路由器交换结构是路由器的核心，有总线、共享交换结构是路由器的核心，有总线、共享内存和交叉开关内存和交叉开关3 3种类型。种类型。目前在实际的路由器设计中

2、，一般采用如目前在实际的路由器设计中，一般采用如下两种方式构建高端路由器：共享内存下两种方式构建高端路由器：共享内存+ +集中转发，分布缓存集中转发，分布缓存+ +交换矩阵。交换矩阵。第一种方式的典型代表为第一种方式的典型代表为JuniperJuniper的的M40 M40 路路由器，由器，第二种方式的典型代表为第二种方式的典型代表为CiscoCisco的的GSR12000GSR12000路由器路由器总线总线 由于由于端口速率高，交换结构需要加速，而且端口速率高，交换结构需要加速，而且接口板与交换板之间、控制板与接口板之间、控接口板与交换板之间、控制板与接口板之间、控制板与交换板之间的连线很多

3、，目前的高速路由制板与交换板之间的连线很多，目前的高速路由器以及交换机都采用高速背板总线以提高系统的器以及交换机都采用高速背板总线以提高系统的吞吐率吞吐率。 为了提高效率，数据线采用串行差分线路，速率可达每秒钟12吉比特。要保证如此高的传输速率和那么多的连线，对背板总线的设计要求非常高。如何降低数据的传输误码率以及保证时钟同步是总线设计中的关键技术。斯坦福大学的Tiny Tera路由器项目中，大量采用串行总线的实现方法值得研究和借鉴共享内存结构共享内存结构 的路由器把接收的数据包存储在共享内存，端口间只需交换数据包指针而无需拷贝整个数据包，可有效提高交换结构带宽利用率。但存储器存取速度受限制，

4、也限制路由器带宽。交叉开关交叉开关在在N N个输入端口和个输入端口和N N个输出端口间个输出端口间建立建立N N条共享总线条共享总线。输入。输入和输出端口通过并和输出端口通过并发交换多个数据包而提高带宽发交换多个数据包而提高带宽。一般的交叉开关存在的一个问题是，输入端一般的交叉开关存在的一个问题是，输入端口口HOLHOL阻塞使带宽利用率低。阻塞使带宽利用率低。一一个解决方法是内部加速，使交叉开关的内个解决方法是内部加速，使交叉开关的内部带宽大于输入链路带宽总和，输出端口同部带宽大于输入链路带宽总和，输出端口同时接收多个输入端口的数据包。这种输出排时接收多个输入端口的数据包。这种输出排队方式优点

5、是数据包只存在输出排队时延，队方式优点是数据包只存在输出排队时延，但缺点是扩展性较差但缺点是扩展性较差。另另一个解决方法是输入虚拟排队。交叉开关一个解决方法是输入虚拟排队。交叉开关在每个输入端口对应于一个输出端口维持一在每个输入端口对应于一个输出端口维持一个个FIFOFIFO队列。队列。调度算法确定各排队数据包在路由器输出端口的发调度算法确定各排队数据包在路由器输出端口的发送顺序，得到输入端口和输出端口之间的一个匹配，送顺序，得到输入端口和输出端口之间的一个匹配，提供输入端口到输出端口的通路提供输入端口到输出端口的通路。 n 先来先服务先来先服务n 随机选择随机选择(Random Select

6、ing)n 轮循轮循(Round-Robin)n 加权公平排队加权公平排队(WFQ-Weighted FairQueuing) n 分层链路共享算法等。分层链路共享算法等。3. 交换结构交换结构(switching fabric)调度算法确定各排队数据包在路由器输出端口的发调度算法确定各排队数据包在路由器输出端口的发送顺序，得到输入端口和输出端口之间的一个匹配，送顺序，得到输入端口和输出端口之间的一个匹配，提供输入端口到输出端口的通路提供输入端口到输出端口的通路。 n 先来先服务先来先服务n 随机选择随机选择(Random Selecting)n 轮循轮循(Round-Robin)n 加权公平

7、排队加权公平排队(WFQ-Weighted FairQueuing) n 分层链路共享算法等。分层链路共享算法等。3. 交换结构交换结构(switching fabric)调度算法中，加权公平排队算法（调度算法中，加权公平排队算法（WFQ-WFQ-Weighted Fair QueuingWeighted Fair Queuing）和经过改进后的加权公）和经过改进后的加权公平流排队算法（平流排队算法（WF2Q-Weighted Fair Flow WF2Q-Weighted Fair Flow QueuingQueuing）比较容易实现，而且性能也不错。总）比较容易实现，而且性能也不错。总之，

8、要让互联网真正能够综合多种业务，作为之，要让互联网真正能够综合多种业务，作为网络连接核心设备的路由器，必须提高端口速网络连接核心设备的路由器，必须提高端口速率和交换容量，提供率和交换容量，提供QoSQoS保证和流量工程（保证和流量工程（TE-TE-Traffic EngineeringTraffic Engineering）功能。）功能。 加权公平排队算法是一种理想的调度算法。它加权公平排队算法是一种理想的调度算法。它根据每个连接权值分配链路带宽。设各连接权根据每个连接权值分配链路带宽。设各连接权值可表示为值可表示为w1, w2,wnw1, w2,wn，其中，其中wi=1wi=1，则排队，则排

9、队连接连接k k具有可保证带宽具有可保证带宽wkwk* *R/wiR/wi，R R为链路带宽。为链路带宽。因此，加权公平排队算法可保护和隔离连接，因此，加权公平排队算法可保护和隔离连接，公平分配剩余带宽，并且若连接发送速率受限公平分配剩余带宽，并且若连接发送速率受限于漏桶控制算法，则该连接具有一个可保证的于漏桶控制算法，则该连接具有一个可保证的端到端时延上限。但加权公平排队算法缺点是端到端时延上限。但加权公平排队算法缺点是需要保存每个排队连接状态信息，各数据包需需要保存每个排队连接状态信息，各数据包需求虚拟时钟并且按优先级排队，其扩展性差。求虚拟时钟并且按优先级排队，其扩展性差。分层链路共享服

10、务是指按类层次组织一个链路的分层链路共享服务是指按类层次组织一个链路的所有连接，路由器基于策略地给每个类对象分配所有连接，路由器基于策略地给每个类对象分配链路带宽。分层链路共享需要实现以下几个目标：链路带宽。分层链路共享需要实现以下几个目标：若一个类有足够带宽需求，应保证该类的最小网若一个类有足够带宽需求，应保证该类的最小网络带宽；若一个类具有剩余带宽，应保证各兄弟络带宽；若一个类具有剩余带宽，应保证各兄弟类公平使用这些剩余带宽；在类层次内，支持实类公平使用这些剩余带宽；在类层次内，支持实时和优先级服务。对于以上这些目标，有时可能时和优先级服务。对于以上这些目标，有时可能是冲突的，调度算法应实现相应机制优先满足某是冲突的，调度算法应实现相应机制优先满足某些目标要求。用于分层链路共享服务的调度算法些目标要求。用于分层链路共享服务的调度算法主要包括基于类排队主要包括基于类排队(Class Based Queueing)4(Class Based Queueing)4，分，分层加权公平排队算法层加权公平排队算法(Hierarchical Packet Fair (Hierarchical Packet Fair Que