摘要
Internet的迅速发展直接表现为用户流量的迅速增长,这就要求路由器必须提供更大的容量.传统的路由器由线卡和集中式交换网络构成.集中式交换网络只能支持有限的端口数目,而且随着端口数目的增加,调度算法也变得越来越复杂,所以交换网络正成为整个路由器的性能瓶颈.集中式交换网络还是路由器的单一失效点,无法提供令人满意的容错性能.直连网络具有良好的扩展性和容错性.其中,3-DTorus拓扑结构已被成功应用到可扩展路由器的设计当中.但是在实际应用中,3-DTorus结构受到等分带宽的约束,限制了扩展规模.介绍了一种新型的直连网络结构,称为蜂巢式结构.将对蜂巢结构作简单的改动,修改后的拓扑表现出很好的拓扑属性.基于该结构,提出了两类最短路径路由算法.其中,负载均衡的最短路径路由算法较好地利用了直连网络路径多样性的特点,针对均匀随机和Tornado两种类型的流量都表现出较低的分组延时和较高的吞吐量.另就队列长度和单节点调度算法等方面对路由算法的影响进行了讨论.蜂巢结构为可扩展路由器的设计提供了新的选择.
In the Internet, the exponential growth of user traffic has been driving routers to run at higher capacity. Traditional routers consist of line cards and centralized switching fabrics. The centralized switching fabric in such a router, however, is becoming the bottleneck for its limited port numbers and complicated scheduling algorithms. In addition, the fabric is the single point of failure （SPF） in the router. Direct networks, such as 3-D Torus topology, have been successfully applied to the design of scalable routers. They show good scalability and fault tolerance. Unfortunately, its scalability is limited in practice. This paper introduces another type of direct network, called cellular router （CR）. With a little modification, this network shows excellent topological properties. Based on this network, two classes of minimal routing algorithms are introduced. The load-balanced minimal routing （LBMR） algorithm makes use of path diversity and shows low latency and high throughput on both uniform random （UR） and Tornado traffic. This paper also discusses some other aspects of the routing algorithms, such as effects of queue length and scheduling algorithms. The CR architecture is a oromising choice for the design of scalable routers.
出处
《软件学报》
EI
CSCD
北大核心
2007年第10期2538-2550,共13页
Journal of Software
基金
Supported by the National Natural Science Foundation of China under Grant No.90604029 (国家自然科学基金)
the National Basic Research Program of China under Grant No.2003CB314801 (国家重点基础研究发展计划(973))
