第 卷 第期 年月计 算 机 学 报 收稿日期： ； 最终修改稿收到日期： 本课题得到国家自然科学基金（ ） 、 国家“ 八六三” 高技术研究发展计划项目基金（ ） 资助戴 艺， 女， 年生， 博士， 讲师， 主要研究方向为路由器体系结构、 高性能报文交换及交换调度算法 ： 苏金树， 男， 年生， 博士， 教授， 博士生导师， 主要研究领域为计算机网络体系结构、 信息安全孙志刚，男， 年生， 博士， 研究员， 主要研究领域为计算机网络体系结构和通信技术、 高性能报文交换体系结构 基于流映射的负载均衡调度算法研究戴 艺 苏金树 孙志刚（ 国防科学技术大学计算机学院 长沙 ）摘 要 网络管理者需要能够提供可扩展性、 吞吐率保证及报文顺序的高性能路由器体系结构 目前基于 的集中式路由器体系结构难以实现性能和规模的可扩展， 基于两级 网络的负载均衡交换结构成为扩展 路由器容量的有效的途径 负载均衡路由器存在严重的报文乱序现象， 输出端报文重定序复杂度为（） 文中提出一种区域均等的负载均衡交换结构， 每个连续的中间级输入端口划分为一个区域， 输入端采用基于流映射的负载分配算法 （ ，为聚合粒度， 简称 ） ， 在个连续的外部时间槽， 以细粒度的方式将同一条流的个信元分派到固定的映射区域， 通过理论证明， 该调度策略可获得 吞吐率并能够保证报文的顺序为避免流量区域集中现象， 采用双循环（ ） 方式构建不同输入端口的流到区域的映射关系； 为实现负载在中间级输入端口的均衡分布， 每个输入端口维护全局统一视图的流量分布矩阵， 调度算法根据流量分布矩阵调度单位帧， 可以证明， 对任意输出端口， 同一区域 队列长 度相同且不同区域 队列长度至多差， 从而实现了 负载均衡度 调度算法分布于每个输入端口独立执行， 根据流到区域的映射关系及负载分布状态分派信元， 模拟结果显示， 当聚合粒度时， 算法在同类维序算法中表现出最优延迟性能关键词 路由器体系结构； 负载均衡路由器； 报文乱序； 双循环映射； 可扩展中图法分类号 号： （ ， ， ） ， ， ， （） ， ， （ ， ） ， ， ， ， ，