高阶路由器结构研究综述

随着高性能网络规模的增加,高阶路由器结构设计成为高性能计算中研究的重点和热点。使用高阶路由器,网络能实现更低的报文传输延迟、网络构建成本和网络功耗,同时高阶路由器的应用还可以提高网络可靠性。过去十年是高阶路由器发展最快的时期,对近年高阶路由器的研究进行了综述,并对未来发展趋势进行了预测,主要介绍了以YARC为代表的经典结构化设计以及"network within a network"等近年来涌现的新型设计方法。未来的研究重点是解决高阶路由器结构设计中遇到的缓存和仲裁等各种问题,并利用光互连等技术设计性能更好的结构。     

绿色路由器的低功耗FIS转发机制及其能耗分析

随着互联网的发展,现有路由器体系结构在性能、复杂性和节能等方面存在许多难以克服的问题,如何实现高效节能的转发机制是绿色高性能路由器设计面临的重大挑战.基于边交换边转发思想提出一种边转发边交换(forwarding in switching, FIS)机制,通过模糊转发流水交换减少了路由器转发和交换阶段的存储需求和访存次数.该机制复用多个低速节点构成多级流水线结构,通过低成本执行部件的规模化运行提高交换性能和IP查找速率,可降低报文查表交换的硬件实现复杂度.建立了先转发后交换(forwarding before switching, FBS)机制和FIS机制的能耗模型,使用不同模型模拟内部缓存、输入输出端口等具有不同结构的节点,仿真实验证明FIS机制比现有的FBS机制减少约12.5%的能耗.提出的分析模型适用于可扩展和绿色节能路由器的设计.     

iSLIP调度算法研究及其实现

目前，为提高交换系统吞吐率，设计开发高性能网络交换机或路由器内部交换结构的技术已趋成熟．但易于在硬件中实现的、高效的队列调度算法仍然是一项值得研究的重要技术．文章首先讨论了对于输入缓冲采用FIF0队列交换系统，其吞吐率主要受HOL队首阻塞的影响．然后研究了iSLIP调度算法的基本原理、迭代仲裁步骤及它在硬件中的实现．针对硬件交换转发判决这一关键问题，给出了在输入队列交换机中采用虚拟输出队列的交换结构和多优先级调度算法的硬件实现方案．最后，对isLIP算法的性能进行了分析比较，证明isLIP算法的实现方案不仅实现简单，而且具有良好的特性．     

一种二维片上网络路由器的设计实现

片上网络(Network on Chip, NoC)作为解决众核芯片互连的主流方案,其性能很大程度上取决于网络的拓扑结构。而网络拓扑结构的效能受到网络路由器的直接影响。因此,基于特定拓扑结构的路由器设计实现具有非常重要的研究意义。因此将XY路由算法应用于路由器节点中,设计了基于2D Mesh拓扑结构、轮询仲裁机制与虫孔交换流控的片上网络路由器,并使用Modelsim对路由器进行了功能验证。实验结果表明,设计的路由器能满足微片数据的处理,能够正确的收发数据包。     

基于Clos网络的高阶路由器结构

路由器为高性能互连网络的关键组成部分，利用高阶路由器可灵活构建网络直径低、路由路径丰富、容错性能高的拓扑结构。分层结构将整个路由器分成多个子交叉开关实现，子交叉开关规模较小，典型实现为子交叉开关的数量等于路由器端口数，每个子交叉开关对应一个输入/输出端口。分层结构每个子交叉开关的输入和输出都设有缓冲区，导致分层结构路由器内部有大量缓冲区，扩展性受限。网络结构将用于构建系统的网络拓扑实现在片内，如通过网格、全互连或胖树连接较小的交换机，并通过集成电路技术实现在一个路由器中，对外表现为一个高阶路由器。网络结构成本低，构建系统网络后除了要考虑系统网络拓扑的性能，还需要考虑路由器本身的路由问题。提出基于Clos网络的分层结构路由器，综合了传统分层结构高性能和网络结构低成本的优点，并提出2种Clos网络的调度算法，在均匀流量模式下接近100%带宽，RTL综合评估其实现最多减少面积25.9%。     

输入缓存Clos网络中分布式正交分路路由算法

提出了一种采用输入缓存MSM结构的Clos网络,该结构适用于高速交换网络。提出了这一结构中的路由算法,该算法采用正交分路的方法来减小网络内部的冲突,引入路由优先级来提高网络内部的链路利用率,使用优先级轮转来均衡网络内部负载。针对这一路由算法,还给出了与之对应的信元调度算法。仿真表明,尽管采用共享缓存的MSM结构内部使用了很高的加速比,但是采用了正交分路的路由算法后,输入缓存MSM结构,可以获得比共享缓存MSM结构更好的时延及吞吐性能,更适合在高速大容量多端口的路由器或交换机中采用。     

高效的Crossbar仲裁算法--ISP

交换开关是高性能路由器的核心,目前高性能骨干路由器一般采用基于输入队列的ｃｒｏｓｓｂａｒ交换开关。高效的ｃｒｏｓｓｂａｒ仲裁算法对路由器设计十分重要,文中提出一种轮询与Ｒｏｕｎｄ Ｒｏｂｉｎ相结合的仲裁算法－ＩＳＰ（Ｉｎｐｕｔ Ｓｅｒｉａｌ Ｐｏｌｌｉｎｇ）。轻负载时ＩＳＰ算法与ｉＳＬＩＰ算法性能相当,重负载时ＩＳＰ算法在宽带利用率、信元平均延时和公平性等方面优于ｉＳＬＩＰ算法,ＩＳＰ算法实现简单     

多维交换网络中的一种流量控制机制

多维交换网络是大容量、可扩展分组交换机/路由器设计中的关键技术之一.本文给出了基于这种网络拓扑、采用虫孔路由、结合虚通道技术时的一种有效的流量控制机制,它可在这种网络中同时有效地实现分组级和微片级的流量控制,提高网络交换性能.文中对节点缓存长度与网络性能进行了分析和仿真,描述了有限缓存资源下单节点和全网的流量控制过程,给出了网络中发生阻塞的条件.     

SuperStar:一种可扩展高阶互连拓扑结构

随着高速信号传输技术和VLSI技术的发展,使用高阶路由器来应对因高性能计算机峰值性能不断攀升给高性能互连网络带来的新挑战已是发展需求;同时,如何利用高阶特性减少互连网络延迟和成本开销,以支持更大的网络规模是设计高性能互连网络拓扑结构的关键和突破点。针对目前基于高阶路由器的典型拓扑结构进行了分析,并在此基础上提出一个新的高阶拓扑架构SuperStar,其不仅具有较短的网络直径而且具有良好的可扩展性;通过在一个基于OMNeT++平台自主开发的高阶互连网络性能测评模拟器上设定不同的通信负载,测评各种拓扑结构在通信系统下实际的网络延迟和吞吐率的走势,以分析SuperStar的通信开销。     

一种基于FPGA实现的高速多路交换开关

多路交换开关是高性能交换部件的核心。本文描述了基于Xilinx公司Virtex-Ⅱ系列FPGA的特点设计和实现的一种高速多路交换开关,它由输入信道组织、内部无阻塞crossba r交换和仲裁调度器三部分组成。仲裁调度器的设计是多路交换开关的关键,申请和仲裁许可的完成时间关系到整个实现的综合频率和性能。我们提出一种改进的行波流水仲
裁器设计,它公平有效,工作频率达到135MHz,在实际应用中效果良好。     

On the design of IP routers Part 1: Router architectures

Internet Protocol (IP) networks are currently undergoing transitions that mandate greater bandwidths and the need to prepare the network infrastructures for converged traffic (voice, video, and data). Thus, in the emerging environment of high performance IP networks, it is expected that local and campus area backbones, enterprise networks, and Internet Service Providers (ISPs) will use multigigabit and terabit networking technologies where IP routers will be used not only to interconnect backbone segments but also to act as points of attachments to high performance wide area links. Special attention must be given to new powerful architectures for routers in order to play that demanding role. In this paper, we describe the evolution of IP router architectures and highlight some of the performance issues affecting IP routers. We identify important trends in router design and outline some design issues facing the next generation of routers. It is also observed that the achievement of high throughput IP routers is possible if the critical tasks are identified and special purpose modules are properly tailored to perform them.     

利用直连网络实现可扩展路由器

Internet的迅速发展直接表现为用户流量的迅速增长,这就要求路由器必须提供更大的容量.传统的路由器由线卡和集中式交换网络构成.集中式交换网络只能支持有限的端口数目,而且随着端口数目的增加,调度算法也变得越来越复杂,所以交换网络正成为整个路由器的性能瓶颈.集中式交换网络还是路由器的单一失效点,无法提供令人满意的容错性能.直连网络具有良好的扩展性和容错性.其中,3-D Torus拓扑结构已被成功应用到可扩展路由器的设计当中.但是在实际应用中,3-D Torus结构受到等分带宽的约束,限制了扩展规模.介绍了一种新型的直连网络结构,称为蜂巢式结构.将对蜂巢结构作简单的改动,修改后的拓扑表现出很好的拓扑属性.基于该结构,提出了两类最短路径路由算法.其中,负载均衡的最短路径路由算法较好地利用了直连网络路径多样性的特点,针对均匀随机和Tornado两种类型的流量都表现出较低的分组延时和较高的吞吐量.另就队列长度和单节点调度算法等方面对路由算法的影响进行了讨论.蜂巢结构为可扩展路由器的设计提供了新的选择.     

Shared memory multiprocessor architectures for software IP routers

We propose new shared memory multiprocessor architectures and evaluate their performance for future Internet protocol (IP) routers based on symmetric multiprocessor (SMP) and cache coherent nonuniform memory access (CC-NUMA) paradigms. We also propose a benchmark application suite, RouterBench, which consists of four categories of applications representing key functions on the time-critical path of packet processing in routers. An execution driven simulation environment is created to evaluate SMP and CC-NUMA router architectures using this RouterBench. The execution driven simulation can produce accurate cycle-level execution time prediction and reveal the impact of various architectural parameters on the performance of routers. We port the FUNET trace and its routing table for use in our experiments. We find that the CC-NUMA architecture provides an excellent scalability for design of high-performance IP routers. Results also show that the CC-NUMA architecture can sustain good lookup performance, even at a high frequency of route updates.     

On the design of a high-performance adaptive router for CC-NUMA multiprocessors

This work presents the design and evaluation of an adaptive packet router aimed at supporting CC-NUMA traffic. We exploit a simple and efficient packet injection mechanism to avoid deadlock, which leads to a fully, adaptive routing by employing only three virtual channels. In addition, we selectively use output buffers for implementing the most utilized virtual paths in order to reduce head-of-line blocking. The careful implementation of these features has resulted in a good trade-off between the network performance and hardware cost. The outcome of this research is a high-performance adaptive router (HPAR), which adequately balances the needs of parallel applications: minimal network latency at low loads and high throughput at heavy loads. The paper includes an evaluation process in which HPAR is compared with other adaptive routers using FIFO input bufferring, with or without additional virtual channels to reduce head-of-line blocking. This evaluation contemplates both the VLSI costs of each router and their performance under synthetic and real application workloads. To make the comparison fair, all the routers use the same efficient deadlock avoidance mechanism. In all the experiments, HPAR exhibited the best response among all the routers tested. Moreover, the observed packet latencies were comparable to those exhibited by simpler routers. Therefore, HPAR can be considered as a suitable candidate to implement packet interchange in next generations of CC-NUMA multiprocessors.     

一个新颖的模块化NoC路由器设计

片上网络（NoC）作为复杂片上系统的有效解决方案,已经成为研究的热点。互连网络的性能很大程度取决于构建网络的路由器结构。基于时延、吞吐和可靠性等考虑,提出一种基于虫孔交换的模块化设计的路由器结构。该结构采用路径分组,使用更小的交叉开关,同当前设计相比,很大程度上减少了输出端口竞争。且该结构自身具有一定的容错功能。     

Asynchronous spatial division multiplexing router

Asynchronous quasi-delay-insensitive (QDI) NoCs have several advantages over their clocked counterparts. Virtual channel (VC) is the most utilized flow control method in asynchronous routers but spatial division multiplexing (SDM) achieves better throughput performance for best-effort traffic than VC. A novel asynchronous SDM router architecture is presented. Area and latency models are provided to analyse the network performance of all router architectures including wormhole, virtual channel and SDM. Performance comparisons have been made with different configurations of payload size, communication distance, buffer size, port bandwidth, network size and number of VCs/virtual circuits. Compared with VC, SDM achieves higher throughput with lower area overhead.