| 出版日期：2001-11-01 总期号：1068 本年期号：83 |
|
 |
新型调度算法SRRR挑战思科
叶冰 制约路由器交换性能的因素主要方面包括：用作交换的ASIC芯片的速度、性能，路由器本身的系统结构和交换的策略。交换调度算法即为路由器作包交换时的优先选择何种包来进行交换的选择策略，它的合理性对路由器所能支持的带宽交换能力尤为重要。 Cisco路由器在世界上市场占有率最大，也是国内电信运营商普遍采用的网络设备。Cisco路由器中采用的调度方法是由斯坦福大学教授N. Mckeown发明的iSLIP方法。该方法首次见于Mckeown本人1995年5月在加州大学伯克利分校的博士论文。iSLIP的优点在于其简洁和高效。它能很容易地用硬件加以实现。在通过路由器的通信量是完全均衡的条件下，效率可接近100%。但是在某些特定的非稳定突发条件下，iSLIP的效率还是有潜力可挖的，因此，iSLIP成为几年来学术界和设备生产商挑战的对象。 
图1 均衡通信量条件下的性能比较 最近，我国香港科技大学计算机科学系的姜莹小姐，经过对多种路由器调度方式的比较和研究，对当前市场流行的路由器产品正在使用的调度方式进行了改进，并提出了一种全新的调度方式，称为有选择性请求的轮询调度（Selective-Request Round-Robin Scheduler，简称SRRR）。它是一种适用于虚拟输出端口交换矩阵（VOQ Crossbar）的新技术。交换矩阵是当前高性能路由器主要采用的一种交换结构。VOQ是为了防止交换矩阵中的HOL阻塞（Head Of Line Blocking）现象采取的一种虚拟输出队列模式。 SRRR这种新的方法，将iSLIP的三步调度拓展为四步调度，通过增加对通信请求进行选择，将进行匹配的两个步骤中的冲突进一步减少，从而增加了匹配的数量。同iSLIP相比，SRRR只增加了很低的复杂度。简单高效的硬件实现已经被设计出来。而SRRR的性能是iSLIP无法比拟的，在一般条件下，延迟只有iSLIP的几分之一到几十分之一，在某些情况下，甚至只有几百分之一。SRRR不仅在通信量均衡的情况性能良好，更加能在实际中通信量随机分布、十分不平均的情况下，实现高效率。SRRR还通过了稳定性测试，证明在各种情况下，系统不会进入不稳定状态。 
图2 带突发性通信量条件下的性能比较 接下来，用网络模拟对两种方法进行性能比较。图1-3分别显示在均衡通信量，带突发性通信量以及不均衡通信量的三种条件下SRRR与iSLIP相比较的结果。横轴显示的是路由器的平均负载，纵轴显示的是路由器处理包（Packet）的平均延迟。在这些情况下，我们可以看到，SRRR的性能极大地优于iSLIP。 该技术曾于2001年5月在美国达拉斯举行的IEEE高性能路由交换研讨会上展示，引起了业界广泛的关注。 
图3 不均衡通信量条件下的性能比较 目前，国内许多网络设备生产厂家正在积极研制我国自主开发的高性能路由器，SRRR技术如果能够应用在新一代高速路由器上，对于改善产品性能，提高网络运行效率具有很大的意义。 |
||||||||
