| 文章摘要 | 摘要 网络管理者需要能够提供可扩展性、吞吐率保证及报文顺序的高性能路由器体系结构.目前基于Crossbar的集中式路由器体系结构难以实现性能和规模的可扩展，基于两级Mesh网络的负载均衡交换结构成为扩展Internet路由器容量的有效的途径.负载均衡路由器存在严重的报文乱序现象，输出端报文重定序复杂度为O(N2).文中提出一种区域均等的负载均衡交换结构，每k个连续的中间级输入端口划分为一个区域，输入端采用基于流映射的负载分配算法UFFS-k(Uniform Fine-grain Frame Spreading，k为聚合粒度，简称UFFS-k)，在k个连续的外部时间槽，以细粒度的方式将同一条流的k个信元分派到固定的映射区域，通过理论证明，该调度策略可获得100%吞吐率并能够保证报文的顺序.为避免流量区域集中现象，采用双循环(dual-rotation)方式构建不同输入端口的流到区域的映射关系；为实现负载在中间级输入端口的均衡分布，每个输入端口维护全局统一视图的流量分布矩阵，UFFS-k调度算法根据流量分布矩阵调度单位帧，可以证明，对任意输出端口j，同一区域OQj队列长度相同且不同区域OQj队列长度至多差1，从而实现了100%负载均衡度.UFFS-k调度算法分布于每个输入端口独立执行，根据流到区域的映射关系及负载分布状态分派信元，模拟结果显示，当聚合粒度k=2时，UFFS-k算法在同类维序算法中表现出最优延迟性能.
关键词 路由器体系结构；负载均衡路由器；报文乱序；双循环映射；可扩展
中图法分类号 TP306 DOI号: 10.3724/SP.J.1016.2012.00218 |