网络管理者需要能够提供可扩展性、吞吐率保证及报文顺序的高性能路由器体系结构.目前基于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算法在同类维序算法中表现出最优延迟性能.%Network operators would like high capacity router architectures that can offer guaranteed throughput, scalability and maintain packet ordering. However, current centralized cross bar-based architectures cannot scale to higher performance and port counts. The load-balanced switch architectures rely on two identical stages of fixed configuration meshes appear to be an ef fective way to scale Internet routers to very high capacities, they have the critical problem of packet mis-sequence with reordering complexity of O(N2). In this paper, we propose a region equalization architecture, in which every k consecutive intermediate inputs are organized as a re gion and each input port adopts a Uniform Fine-grain Frame Spreading (UFFS-k , where k is the aggregate factor) algorithm assigning k cells of the same flow to the fixed mapping region in a fine-grain manner during k successive external time slots. We give theoretical proofs that 100% throughput and packet ordering can be achieved by using UFFS-k algorithm at each input. To avoid traffic concentration in regions, a dual-rotation mapping algorithm is used to construct a mapping relationship between flows from different inputs and regions. Furthermore, in order to distribute input traffic equally among the intermediate inputs, the UFFS-k algorithm dispatches each unit frame according to a global traffic distribution matrix maintained at each input. It is proofed that for each output port j, the lengths of Oqj are equal for the same region and the lengths Oqj differ by at most 1 for any two different regions, thus achieving 100% load balancing degree. The UFFS-k algorithm is distributed and can operate independently in each input. It spreads each flow to intermediate inputs according to the mapping relationship between flows to regions as well as traffic distribution state. As the simulation results demonstrate, when k = 2, UFFS-k offers improved delay performance among existing scheduling algorithms that guarantee packet ordering.
展开▼
