基于流映射的负载均衡调度算法研究

• 作者: 孙志刚 戴艺 苏金树
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 路由器体系结构 负载均衡路由器 报文乱序 双循环映射 可扩展
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 218-228
• 分类号: TP306
• 字数: 12191字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2012.00218

摘要

网络管理者需要能够提供可扩展性、吞吐率保证及报文顺序的高性能路由器体系结构.目前基于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算法在同类维序算法中表现出最优延迟性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙志刚	国防科学技术大学计算机学院	45	277	9.0	14.0
2	苏金树	国防科学技术大学计算机学院	64	1757	15.0	41.0
3	戴艺	国防科学技术大学计算机学院	7	70	5.0	7.0