BiLink: A high performance NoC router architecture using bi-directional link with double data rate

This paper presents a novel high performance Network-on-Chip (NoC) router architecture design using a bi-directional link with double data rate (BiLink). Ideally, it can provide as high as 2 times speed-up compared with the conventional NoC router. BiLink utilizes an extra link stage between routers and transmits two flits in one link per cycle using phase pipelining if both routers require to use the current link. To further increase the effective bandwidth, the direction of each link can be configured in every clock cycle to cater for different traffic loads from each side. Therefore, the data rate can be as high as 4 times compared with conventional NoC routers under uneven traffic. Centralized mode control scheme is implemented using a finite state machine (FSM) approach. Cycle-accurate simulations are carried out on both synthetic traffic patterns as well as real application benchmarks. Simulation results show that BiLink can provide as high as 90% and 250% speedup compared with conventional NoC routers for even and uneven traffic, respectively. 2X and 3X gains in throughput are obtained under even and uneven traffic, respectively, when compared with the conventional NoC router for the virtual channel flow control. The BiLink router architecture is synthesized using TSMC 65 nm process technology and it is shown that an area overhead of 28% over state-of-the-art bi-directional NoC is introduced while the critical path is about 9% higher than that of the conventional routers. Despite the overhead in critical path and power consumption, a 47.45% improvement of Energy-Delay-Product (EDP) is achieved by BiLink under high injection rate traffic.     

Functional Test of Mesh-Based NoCs with Deterministic Routing: Integrating the Test of Interconnects and Routers

In this work, a comprehensive functional-based test method is presented to integrate the test of Network-on-Chip interconnects and routers. Experimental results show that fault coverage can reach up to 100% of interconnect faults and over 90% of router faults. The test structures needed to implement the test method are presented and the scalability of the method is discussed. We show that our approach scales well with the number of routers and channel width. The cost of the functional test strategy and the cost of a scan-based strategy are also analyzed in order to present scenarios where each strategy fits better.     

Routing with a clue

We suggest a new simple forwarding technique to speed up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6), and performs IP lookup nearly as fast as IP/Tag switching but with a smaller memory requirement and a much simpler protocol. The basic idea is that each router adds a "clue" to each packet, telling its downstream router where it ended the IP lookup. Since the forwarding tables of neighboring routers are similar, the clue either directly determines the best prefix match for the downstream router, or provides the downstream router with a good point to start its IP lookup. The new scheme thus prevents repeated computations and distributes the lookup process across the routers along the packet path. Each router starts the lookup computation at the point its upstream neighbor has finished. Furthermore, the new scheme is easily assimilated into heterogeneous IP networks, does not require routers coordination, and requires no setup time. Even a flow of one packet enjoys the benefits of the scheme without any additional overhead. The speedup we achieve is about 10 times faster than current standard techniques. In a sense, this paper shows that the current routers employed in the Internet are clue-less; namely, it is possible to speed up the IP lookup by an order of magnitude without any major changes to the existing protocols     

Defending against distributed denial-of-service attacks with max-min fair server-centric router throttles

Our work targets a network architecture and accompanying algorithms for countering distributed denial-of-service (DDoS) attacks directed at an Internet server. The basic mechanism is for a server under stress to install a router throttle at selected upstream routers. The throttle can be the leaky-bucket rate at which a router can forward packets destined for the server. Hence, before aggressive packets can converge to overwhelm the server, participating routers proactively regulate the contributing packet rates to more moderate levels, thus forestalling an impending attack. In allocating the server capacity among the routers, we propose a notion of level-k max-min fairness. We first present a control-theoretic model to evaluate algorithm convergence under a variety of system parameters. In addition, we present packet network simulation results using a realistic global network topology, and various models of good user and attacker distributions and behavior. Using a generator model of web requests parameterized by empirical data, we also evaluate the impact of throttling in protecting user access to a web server. First, for aggressive attackers, the throttle mechanism is highly effective in preferentially dropping attacker traffic over good user traffic. In particular, level-k max-min fairness gives better good-user protection than recursive pushback of max-min fair rate limits proposed in the literature. Second, throttling can regulate the experienced server load to below its design limit - in the presence of user dynamics - so that the server can remain operational during a DDoS attack. Lastly, we present implementation results of our prototype on a Pentium III/866 MHz machine. The results show that router throttling has low deployment overhead in time and memory.     

RCM: A User Friendly Router Configuration Machine

In this paper a router configuration machine for Cisco routers using GUI is presented. It is developed using Visual C# .NET programming, in which the interface provides GUI platforms for various types of configuration for entire series of Cisco routers. It communicates with the Cisco Internetwork Operating System to configure the router. It includes the configuration for all interior routing protocols and all types of most common used tools. The developed system is implemented on different series of Cisco routers and it worked successfully. It is observed that it eliminates the traditional use of command line interface for configuration of Cisco routers. The router configuration machine is such an idea which never existed before in such an easy level. The machine will be a perfect tool for anyone using a router. The machine also allows for real-time monitoring of network devices and constant performance checking. By providing embedded network intelligence at the network device level, the networks can monitor themselves and adapt to changing topologies, without the need of costly external mechanisms. This machine will also be useful for academic purposes and we can use this machine in any Communication Lab.     

Design and implementation of Single-Buffered routers

A Single-Buffered （SB） router is a router where only one stage of shared buffering is sandwiched between two interconnects in comparison of a Combined Input and Output Queued （CIOQ） router where a central switch fabric is sandwiched between two stages of buffering. The notion of SB routers was firstly proposed by the High-Performance Networking Group （HPNG） of Stanford University, along with two promising designs of SB routers： one of which was Parallel Shared Memory （PSM） router and the other was Distributed Shared Memory （DSM） router. Admittedly, the work of HPNG deserved full credit, but all results presented by them appeared to relay on a Centralized Memory Management Algorithm （CMMA） which was essentially impractical because of the high processing and communication complexity. This paper attempts to make a scalable high-speed SB router completely practical by introducing a fully distributed architecture for managing the shared memory of SB routers. The resulting SB router is called as a Virtual Output and Input Queued （VOIQ） router. Furthermore, the scheme of VOIQ routers can not only eliminate the need for the CMMA scheduler, thus allowing a fully distributed implementation with low processing and commu- nication complexity, but also provide QoS guarantees and efficiently support variable-length packets in this paper. In particular, the results of performance testing and the hardware implementation of our VOIQ-based router （NDSC~ SR1880-TTM series） are illustrated at the end of this paper. The proposal of this paper is the first distributed scheme of how to design and implement SB routers publicized till now.     

IP switching and gigabit routers

To cope with the growth in the Internet and corporate IP networks, we require IP routers capable of much higher performance than is possible with existing architectures. This article examines two approaches to the design of a high-performance router, the gigabit router and the IP switch, and then provides some detail on the implementation of an IP switch and the protocols associated with IP switching     

Core-stateless fair queueing: a scalable architecture to approximate fair bandwidth allocations in high-speed networks

Router mechanisms designed to achieve fair bandwidth allocations, such as fair queueing, have many desirable properties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per-flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. We propose an architecture that significantly reduces this implementation complexity yet still achieves approximately fair bandwidth allocations. We apply this approach to an island of routers - that is, a contiguous region of the network - and we distinguish between edge routers and core routers. Edge routers maintain per-flow state; they estimate the incoming rate of each flow and insert a label into each packet based on this estimate. Core routers maintain no per-flow state; they use first-in-first-out packet scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme core-stateless fair queueing. We present simulations and analysis on the performance of this approach.     

An active scheduling paradigm for open adaptive network environments

Active and programmable networks change the functionality of routers and switches by using agents and active packets. This paper presents a new packet scheduling scheme called Active Scheduling to control and maintain QoS parameters in virtual private networks (VPNs) within the confines of adaptive and programmable networks. In Active Scheduling an agent on the router monitors the accumulated queuing delay for each service. In order to control and to keep the end‐to‐end delay within the bounds, the weights for services are adjusted dynamically by agents on the routers spanning the VPN. If there is an increase or decrease in queuing delay of a service, an agent on a downstream router informs the upstream routers to adjust the weights of their queues. This keeps the end‐to‐end delay of services within the specified bounds and offers better QoS compared to VPNs using static WFQ. The paper describes the algorithm for Active Scheduling, and presents simulation results and these are compared with WFQ. Copyright © 2004 John Wiley & Sons, Ltd.     

A Transparent Failover Mechanism for a Mobile Network with Multiple Mobile Routers

In a mobile network that is multihomed by multiple mobile routers, a mobile router that loses link connectivity can be replaced by the other mobile routers. We propose a transparent failover mechanism (TFM) to provide seamless Internet services to nodes in the mobile network, which is validated by implementing a real test-bed. Compared to the network mobility basic support protocol, TFM does not require the nodes attached to the failed mobile router to change their addresses, and hence has two advantages: (a) IP connectivity is maintained transparently, and (b) failover is quickly accomplished by avoiding the address re-configuration process in each node.     

Fault-Tolerant Mesh-Based NoC with Router-Level Redundancy

The aggressively scaled CMOS technology is increasingly threatening the dependability of network-on-chips (NoCs) architecture. In a mesh-based NoC, a faulty router or broken link may isolate a well functional processing element (PE). Also, a set of faulty routers may form isolated regions, which can degrade the design. In this paper, we propose a router-level redundancy (RLR) fault-tolerant scheme that differs from the traditional microarchitecture-level redundancy (MLR) approach to relieve the problem of isolated PE and isolated region. By simply adding one spare router within each router set in a mesh, RLR can be created and connection paths between adjacent routers can be diversified. To exploit this extra resource, two reconfiguration algorithms are demonstrated to detour observed faulty routers/links. The proposed RLR fault-tolerant scheme can tolerate at most one faulty router within a router set. After the reconfiguration, the original mesh topology is maintained. As a result, the proposed architecture does not need any support from the network layer routing algorithms. The scheme has been evaluated based on the three fault-tolerant metrics: reliability, mean time to failure (MTTF), and yield. The experimental results show that the performance RLR increases as the size of NoC grows; however, the relative connection cost decreases at the same time. This characteristic makes our architecture suitable for large-scale NoC designs.

     

可重构集群路由器并行路由分发模型

传统一对多点的路由分发方式存在周期长、负载不均衡等问题。可重构集群路由器的体系结构中板卡数大量增加,上述问题更为突出,需要对路由分发算法改进。对现有路由分发方法及可重构路由体系进行分析,设计了树型并行路由分发模型。模型将可重构路由器所有板卡构造成一棵不平衡的分发树,路由从树根向叶子并行层层传递。研究了该模型板卡路由分发速度及负载均衡状况,并设计了模型实现算法及实施步骤。基于NS2的实验结果验证了TPRD模型的性能优势。     

Optimal redundancy allocation for high availability routers

How to optimally allocate redundant routers for high availability (HA) networks is a crucial task. In this paper, a 5‐tuple availability function A (N, M, λ, µ, δ) is proposed to determine the minimum required number of standby routers to meet the desired availability (ρ) of an HA router, where N and M are the numbers of active routers and standby routers, respectively, and λ, µ, and δ are a single router's failure rate, repair rate, and failure detection and recovery rate, respectively. We have derived the availability function, and analytical results show that the failure detection and recovery rate (δ) is a key parameter for reducing the minimum required number of standby routers of an HA router. Thus, we also propose a High Availability Management (HAM) middleware, which was designed based on an open architecture specification, called OpenAIS, to achieve the goal of reducing takeover delay (1/δ) by stateful backup. We have implemented an HA Open Shortest Path First (HA‐OSPF) router, which consists of two active routers and one standby router, to illustrate the proposed HA router. Experimental results show that the takeover delays of the proposed HA‐OSPF router were reduced by 6, 37.3, and 98.6% compared with those of the industry standard approaches, the Cisco‐ASR 1000 series router, the Juniper MX series router, and the Virtual Router Redundancy Protocol (VRRP) router, respectively. In addition, in contract to the industry routers, the proposed HA router, which was designed based on an open architecture specification, is more cost‐effective, and its redundancy model can be more flexibly adjusted. Copyright © 2010 John Wiley & Sons, Ltd.     

Mitigating the gateway bottleneck via transparent cooperative caching in wireless mesh networks

Wireless mesh networks (WMNs) have been proposed to provide cheap, easily deployable and robust Internet access. The dominant Internet-access traffic from clients causes a congestion bottleneck around the gateway, which can significantly limit the throughput of the WMN clients in accessing the Internet. In this paper, we present MeshCache, a transparent caching system for WMNs that exploits the locality in client Internet-access traffic to mitigate the bottleneck effect at the gateway, thereby improving client-perceived performance. MeshCache leverages the fact that a WMN typically spans a small geographic area and hence mesh routers are easily over-provisioned with CPU, memory, and disk storage, and extends the individual wireless mesh routers in a WMN with built-in content caching functionality. It then performs cooperative caching among the wireless mesh routers.We explore two architecture designs for MeshCache: (1) caching at every client access mesh router upon file download, and (2) caching at each mesh router along the route the Internet-access traffic travels, which requires breaking a single end-to-end transport connection into multiple single-hop transport connections along the route. We also leverage the abundant research results from cooperative web caching in the Internet in designing cache selection protocols for efficiently locating caches containing data objects for these two architectures. We further compare these two MeshCache designs with caching at the gateway router only.Through extensive simulations and evaluations using a prototype implementation on a testbed, we find that MeshCache can significantly improve the performance of client nodes in WMNs. In particular, our experiments with a Squid-based MeshCache implementation deployed on the MAP mesh network testbed with 15 routers show that compared to caching at the gateway only, the MeshCache architecture with hop-by-hop caching reduces the load at the gateway by 38%, improves the average client throughput by 170%, and increases the number of transfers that achieve a throughput greater than 1 Mbps by a factor of 3.     

基于可编程硬件的虚拟路由器数据平面设计与实现

未来网络体系结构创新和验证亟需建设虚拟化网络实验平台,虚拟路由器作为其中的核心组网设备,其结构和性能决定了实验平台的灵活性和承载能力.本文提出基于并行流水线的虚拟路由器数据平面结构,结合并行包分类和异步多指针轮询调度机制,在同一物理底层上实现了多个相互隔离的并行异构路由器.本设计在可编程硬件上进行了原型实现,并结合商用及软件路由器在真实的网络环境中部署、测试与实验.实验结果表明与传统单流水线结构相比,本设计能以更高灵活性和并行性支持异构的路由器实例独立运行;在逻辑资源开销和延时特性未显著增加的情况下,并行虚拟路由器可以达到与硬件可比的线速转发能力.     

Multicast-enabled network-on-chip routers leveraging partitioned allocation and switching

Multicast on-chip communication is encountered in various cache-coherence protocols targeting multi-core processors, and its pervasiveness is increasing due to the proliferation of machine learning accelerators. In-network handling of multicast traffic imposes additional switching-level restrictions to guarantee deadlock freedom, while it stresses the allocation efficiency of Network-on-Chip (NoC) routers. In this work, we propose a novel partitioned NoC router microarchitecture, called SmartFork, which employs a versatile and cost-efficient multicast packet replication scheme that allows the design of high-throughput and low-cost NoCs. The design is adapted to the average branch splitting observed in real-world multicast routing algorithms. Compared to state-of-the-art NoC multicast approaches, SmartFork is demonstrated to yield high performance in terms of latency and throughput, while still offering a cost-effective implementation.     

IPv6软/硬路由器的发展现状及组网设计

介绍IPv6协议的基本特点及路由器的主要功能,比较软路由器与硬路由器的区别,分析软/硬路由器的发展现状,简要说明软/硬路由器的联合组网设计。     

Beyond best effort: router architectures for the differentiatedservices of tomorrow's Internet

With the transformation of the Internet into a commercial infrastructure, the ability to provide differentiated services to users with widely varying requirements is rapidly becoming as important as meeting the massive increases in bandwidth demand. Hence, while deploying routers, switches, and transmission systems of ever increasing capacity, Internet service providers would also like to provide customer-specific differentiated services using the same shared network infrastructure. We describe router architectures that can support the two trends of rising bandwidth demand and rising demand for differentiated services. We focus on router mechanisms that can support differentiated services at a level not contemplated in proposals currently under consideration due to concern regarding their implementability at high speeds. We consider the types of differentiated services that service providers may want to offer and then discuss the mechanisms needed in routers to support them. We describe plausible implementations of these mechanisms (the scalability and performance of which have been demonstrated by implementation in a prototype system) and argue that it is technologically possible to considerably raise the level of differentiated services which service providers can offer their customers, and that it is not necessary to restrict differentiated services to rudimentary offerings even in very-high-speed networks     

Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique

The network-on-chip (NoC) design problem requires the generation of a power and resource efficient interconnection architecture that can support the communication requirements for the SoC with the desired performance. This paper presents a genetic algorithm-based automated design technique that synthesizes an application specific NoC topology and routes the communication traces on the interconnection network. The technique operates on the system-level floorplan of the system on chip (SoC) and accounts for the power consumption in the physical links and the routers. The design technique solves a multi-objective problem of minimizing the power consumption and the router resources. It generates a Pareto curve of the solution set, such that each point in the curve represents a tradeoff between power consumption and associated number of NoC routers. The performance and quality of solutions produced by the technique are evaluated by experimentation with benchmark applications and comparisons with existing approaches.     

Distributed, scalable routing based on vectors of link states

We have present a new method for distributed routing in computer networks and internets using link-state information. Link vector algorithms (LVA) are introduced for the distributed maintenance of routing information in large networks and internets. According to an LVA, each router maintains a subset of the topology that corresponds to adjacent links and those links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbors. An update message contains a vector of updates; each such update specifies a link and its parameters. The LVA can be used for different types of routing. The correctness of the LVA is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router and each router is able to differentiate old updates from new. The LVA are shown to have better performance than the ideal link-state algorithm based on flooding and the distributed Bellman-Ford algorithm