Adaptive Multimodule Routers for Multiprocessor Architectures

Recent multiprocessors such as Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate adaptivity into such routers with simple changes to the router structure and logic. We show that with as few as two virtual channels per physical channel, adaptivity can be provided to handle nonuniform traffic in multidimensional meshes.     

Minimizing the system impact of router faults by means of reconfiguration and adaptive routing

To tolerate faults in Networks-on-Chip (NoC), routers are often disconnected from the NoC, which affects the system integrity. This is because cores connected to the disabled routers cannot be accessed from the network, resulting in loss of function and performance. We propose E-Rescuer, a technique offering a reconfigurable router architecture and a fault-tolerant routing algorithm. By taking advantage of bypassing channels, the reconfigurable router architecture maintains the connection between the cores and the network regardless of the router status. The routing algorithm allows the core to access the network when the local router is disabled.Our analysis and experiments show that the proposed technique provides 100% packet delivery in 100%, 92.56%, and 83.25% of patterns when 1, 2 and 3 routers are faulty, respectively. Moreover, the throughput increases up to 80%, 46% and 33% in comparison with FTLR, HiPFaR, and CoreRescuer, respectively.     

Comparing Adaptive Routing and Dynamic Voltage Scaling for Link Power Reduction

We compare techniques that dynamically scale the voltage of individual network links to reduce power consumption with an approach in which all links in the network are set to the same voltage and adaptive routing is used to distribute load across the network. Our results show that adaptive routing with static network link voltages outperforms dimension-order routing with dynamic link voltages in all cases, because the adaptive routing scheme can respond more quickly to changes in network demand. Adaptive routing with static link voltages also outperforms adaptive routing with dynamic link voltages in many cases, although dynamic link voltage scaling gives better behavior as the demand on the network grows.     

Routing performance enhancement in hierarchical torus network by link-selection algorithm

A hierarchical torus network (HTN) is a 2D-torus network of multiple basic modules, in which the basic modules are 3D-torus networks that are hierarchically interconnected for higher-level networks. The static network performance of the HTN and its dynamic communication performance using the popular dimension-order routing algorithm have already been evaluated and shown to be superior to the performance of other conventional and hierarchical interconnection networks. In this paper, we propose a link-selection algorithm for efficient use of physical links of the HTN, while keeping the link-selection algorithm as simple as the dimension-order routing algorithm. We also prove that the proposed algorithm for the HTN is deadlock-free using three virtual channels. We evaluate the dynamic communication performance of an HTN using dimension-order routing and link-selection algorithms under various traffic patterns. We find that the dynamic communication performance of an HTN using the link-selection algorithm is better than when the dimension-order routing algorithm is used.     

Resource deadlocks and performance of wormhole multicast routingalgorithms

We show that deadlocks due to dependencies on consumption channels are a fundamental problem in wormhole multicast routing. This type of resource deadlocks has not been addressed in many previously proposed wormhole multicast algorithms. We also show that deadlocks on consumption channels can be avoided by using multiple classes of consumption channels and restricting the use of consumption channels by multicast messages. We provide upper bounds for the number of consumption channels required to avoid deadlocks. In addition, we present a new multicast routing algorithm, column-path, which is based on the well-known dimension-order routing used in many multicomputers and multiprocessors. Therefore, this algorithm could be implemented in existing multicomputers with simple changes to the hardware. Using simulations, we compare the performance of the proposed column-path algorithm with the previously proposed Hamiltonian-path-based multipath and an e-cube-based multicast routing algorithms. Our results show that for multicast traffic, the column-path routing offers higher throughputs, while the multipath algorithm offers lower message latencies. Another result of our study is that the commonly implemented simplistic scheme of sending one copy of a multicast message to each of its destinations exhibits good performance provided the number of destinations is small     

Non-uniform EWMA-PCA based cache size allocation scheme in Named Data Networks

As a data-centric cache-enabled architecture, Named Data Networking (NDN) is considered to be an appropriate alternative to the current host-centric IP-based Internet infrastructure. Leveraging in- network caching, name-based routing, and receiver-driven sessions, NDN can greatly enhance the way Internet resources are being used. A critical issue in NDN is the procedure of cache allocation and management. Our main contribution in this research is the analysis of memory requirements to allocate suitable Content-Store size to NDN routers, with respect to combined impacts of long-term centrality-based metric and Exponential Weighted Moving Average (EWMA) of short-term parameters such as users behaviours and outgoing traffic. To determine correlations in such large data sets, data mining methods can prove valuable to researchers. In this paper, we apply a data-fusion approach, namely Principal Component Analysis (PCA), to discover relations from short- and long-term parameters of the router. The output of PCA, exploited to mine out raw data sets, is used to allocate a proper cache size to the router. Evaluation results show an increase in the hit ratio of Content-Stores in sources, and NDN routers. Moreover, for the proposed cache size allocation scheme, the number of unsatisfied and pending Interests in NDN routers is smaller than the Degree-Centrality cache size scheme.     

容迟网络广义k选播路由资源分配模型

容忍网络（DTN）协议现用于缓解移动网络频繁中断和网络分割造成的性能不稳,其核心之一是资源分配。然而在公共交通工具移动网络或物流环境中,现有路由算法的先验知识具有时间的概率不确定性,降低了资源分配效率。提出广义k选播,在许可时间段内对k个路由器之间进行路由和资源分配,分散其时间不确定性的偏差程度。而接入路由器信息矩阵可决定广义k选播集,从而实现对多个目的地的托管传送。在此基础上进一步提出路由资源分配的概率不确定模型。仿真验证其传输性能和鲁棒性整体优于DTN多播路由方案。     

Learning the valid incoming direction of IP packets

Packet forwarding on the Internet is solely based on the destination address of packets, and it is easy to forge the source address of IP packets without affecting the delivery of the packets. To solve this problem, one can have routers check whether or not every packet comes from a correct direction based on its source address field. However, due to routing asymmetry in today’s Internet, a router cannot simply reverse its forwarding table to determine the correct incoming direction of a packet.In this paper, we present the source address validity enforcement protocol, SAVE, which allows routers to learn valid incoming directions for any given source address. SAVE is independent from—and can work with—any specific routing protocol. By only interfacing with the forwarding table at routers, SAVE allows routers to properly propagate valid source address information from source address spaces to all destinations, and allows each router en route to build and maintain an incoming tree to associate each source address prefix with a corresponding incoming interface. The incoming tree is further valuable in handling routing changes: although a routing change at one router could affect the incoming direction of source address spaces from many locations, only the router that sees the change needs to send out new updates. Finally, SAVE has a good performance with low overhead.     

A Centrality-measures based Caching Scheme for Content-centric Networking (CCN)

Content-centric networking (CCN) is gradually becoming an alternative approach to the conventional Internet architecture through the distribution of enlightening information (named as content) on the Internet. It is evaluated that the better performance can be achieved by caching is done on a subset of content routers instead of all the routers in the content delivery path. The subset of a content router must be selected in a manner such that maximum cache performance can be achieved. Motivated by this, we propose a Centrality-measures based algorithm (CMBA) for selection of an appropriate content router for caching of the contents. The Centrality-measures are based on the question: ”Who are the most important or central content router in the network for the caching of contents?”. We found that our novel CMBA could improve content cache performance along the content delivery path by using only a subset of available content routers. Our results recommend that our proposed work consistently achieves better caching gain across the multiple network topologies.     

XGRouter: high-quality global router in X-architecture with particle swarm optimization

This paper presents a high-quality very large scale integration (VLSI) global router in X-architecture, called XGRouter, that heavily relies on integer linear programming (ILP) techniques, partition strategy and particle swarm optimization (PSO). A new ILP formulation, which can achieve more uniform routing solution than other formulations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing region is extended progressively from the most congested region. In the post-processing stage of XGRouter, maze routing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global routing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global routers, XGRouter has no overflow.     

一种可配置双向链路的片上网络容错偏转路由器

随着CMOS工艺进入纳米时代,工艺尺寸的不断缩小增加了集成电路对瞬态故障与永久故障的敏感性.在片上网络中提供容错支持对于提高单芯片多处理器片上数据传输的可靠性至关重要.为了处理片上网络中的瞬态故障与永久故障链路,提出一种可配置双向链路的容错偏转路由器BiFTDR.相邻BiFTDR路由器之间采用一对可配置方向的双向链路互连,根据链路的故障状态和路由器的到达包信息对双向链路的方向进行动态配置,在单向链路故障的情况下不需要绕道路由即可实现容错,并且不需要路由表从而降低了路由器的硬件实现开销.模拟结果表明,在合成通信模式下,网络中包含5条和15条永久故障链路的情况下,BiFTDR路由器的包平均延迟比一种基于强化学习的容错偏转路由器分别少10%和19%;在真实应用运行踪迹通信模式下,与无故障网络的包平均延迟相比,BiFTDR路由器的性能损失不到1%.对于瞬态故障,即使在高故障率下BiFTDR路由器的性能下降程度也较小.在65 nm工艺下对BiFTDR路由器进行综合,能达到500 MHz的时钟频率,并且具有较小的面积和功耗开销.     

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

基于节点失效的洋葱路由匿名链路控制方法

针对洋葱路由(Tor)随机选路算法选取的通信路径不可控制,进而导致匿名技术滥用和溯源方法失效的问题,提出了一种基于节点失效的Tor匿名链路控制方法。通过发送伪造的TCP复位信息模拟节点失效,从而不断让Tor客户端重新选路,并最终选择到受控链路,来达到有效链路控制的目的。对Tor网络选路算法的理论分析和在拥有256个洋葱路由组成的私有Tor网络中的实际测试结果表明,与传统部署高带宽路由吸引用户选中受控节点的方法相比,该方法在Tor客户端默认开启入口守卫的情况下,将传统方法选择受控入口节点的概率由4.8%提高到约60%。实验结果表明,随着受控链路长度的增大,链路建立的成功率会降低,因此所提方法适用于控制较短链路的情形。     

Efficient Management and Packets Forwarding for Multimedia Flows

Well known requirements for handling multimedia flows in routers are resource reservation and fast packets forwarding. The former takes into account the quite stable and long lasting bandwidth occupation, whereas the latter takes into account the large number of packets routed along the same path. Many techniques have been proposed and standardized to face these requirements, but their application is often complex, expensive and sometimes limited by the need of agreements between network managers of the many networks and Autonomous Systems. This paper introduces IMFM (Integrated Multimedia Flows Management), an innovative, scalable, and extremely lightweight technique to provide routers deterministic and dynamic resource reservation and a fast forwarding table lookup. It is based on a distributed linked data structure that allows direct (searchless) access to entries in the routers’ tables, extending the resource reservation algorithm REBOOK. Unlike conventional virtual circuits, IMFM does not require any interaction with (nor change in) the underlying routing protocols and autonomously recovers from errors, faults and route changes. If information stored in its data structure becomes obsolete, packet handling is reverted to best-effort, lookup-driven forwarding, so that packets are never dropped nor misrouted. IMFM can be gradually deployed, providing a framework for congestion avoidance solutions and increasing the forwarding speed in IMFM-aware router even along partially IMFM-unaware paths. IMFM has been fully implemented. Experiments have been designed to demonstrate its feasibility and the measured performance is reported and compared with existing techniques.     

Fuzzy-based Adaptive Routing Algorithm for Networks-on-Chip

In this paper, we propose two adaptive routing algorithms to alleviate congestion in the network. In the first algorithm, the routing decision is assisted by the number of occupied buffer slots at the corresponding input buffer of the next router and the congestion level of that router. Although this algorithm performs better than the conventional method, DyXY, in some cases the proposed algorithm leads to non-optimal decisions. Fuzzy controllers compensate for ambiguities in the data by giving a level of confidence rather than declaring the data simply true or false. To make a better routing decision, we propose an adaptive routing algorithm based on fuzzy logic for Networks-on-chip where the routing path is determined based on the current condition of the network. The proposed algorithm avoids congestion by distributing traffic over the routers that are less congested or have a spare capacity. The output of the fuzzy controller is the congestion level, so that at each router, the neighboring router with the lowest congestion value is chosen for routing a packet. To evaluate the proposed routing method, we use two multimedia applications and two synthetic traffic profiles. The experimental results show that the fuzzy-based routing scheme improves the performance over the DyXY routing algorithm by up to 25% with a negligible hardware overhead.     

Experimental validation of resilient tree-based greedy geometric routing

Geometric routing is an alternative for IP routing based on longest prefix matching. Using this routing paradigm, every node in the network is assigned a coordinate and packets are forwarded towards their intended destination following a distance-decreasing policy (greedy forwarding). This approach makes the routers significantly more memory-efficient compared to the current IP routers. In this routing, greedy embeddings are used to guarantee a 100% successful delivery to every destination in the network. Most of the existing proposals lack resiliency mechanisms to react efficiently to network changes. We propose a distributed algorithm to calculate a greedy embedding based on a spanning tree of the network. In this algorithm, nodes are triggered to re-calculate their coordinates upon a change in the topology such as link or node failures. The advantage of this approach is that it recovers from topology failures within a very short period of time. We further extend the algorithm to generate backups to apply protection in distributed setups. Different trade-offs and trends of re-convergence for geometric routing have been evaluated in an emulation environment. Realistic results are achieved through emulation as no model or abstraction is involved. The proposed routing scheme is implemented in Quagga routing software and new elements are developed in Click modular router to enable greedy forwarding. For the first time, the performance of this scheme is evaluated through emulation on a large topology of 1000 nodes and the results are compared with BGP. The experimental results indicate that the proposed scheme has interesting characteristics in terms of convergence time upon a change in the network topology.     

WEAVER: A Knowledge-Based Routing Expert

WEAVER, a channel/switchbox knowledge-based routing program, simultaneously considers all the important routing metrics including 100 percent routability, minimum routing area, minimum wire length, and the minimum number of vias. It allows prerouted nets and user interaction throughout the entire routing process, while relaxing the unnecessary contraints of assigning different directions?constraints imposed by all of the current channel and switchbox routers. A grid-based router using two interconnection layers, WEAVER can be easily expanded to route any shape routing area such as T or +. Implemented in OPSS, a production system language, WEAVER routinely produces routings requiring less area than routers that focus on a single routing metric.     

Dynamic filter merging and mergeability detection for publish/subscribe

Filter-based publish/subscribe and content-based routing have been proposed for flexible information dissemination in distributed environments. A content-based router is part of an overlay structure, in which each router forwards events to neighbouring routers and local clients based on their interests. Filter merging or summarization has been proposed as an optimization strategy in this environment. These techniques combine filters to reduce the number of propagated filters and thus the size of distributed state. In this paper, we present the algorithms for generic dynamic filter merging and filter mergeability detection, and discuss integration with routing tables. The algorithms are based on a formal framework of merging rules. Experimental results are examined and analyzed for both desktop systems and small devices. The results indicate that dynamic filter merging is feasible given that the workload is mergeable.     

Evaluation of Crossbar Architectures for Deadlock Recovery Routers

The performance of interconnection networks is significantly affected by router speed and routing adaptivity, which can be competing factors. To achieve a high-speed, true-fully-adaptive router design, this paper explores the exploitation of dynamic routing behavior identified as routing locality. When routing locality is exploited, it enables the internal crossbar of a router to be partitioned into smaller and faster units without sacrificing true-fully-adaptive routing capabilities. Extensive evaluation of partitioned crossbar designs which exploit routing locality shows that the increased adaptivity offered by deadlock recovery-based routing algorithms can be implemented in routers without sacrificing router speed. The partitioned crossbar designs reduce average message latency by up to 65% and increase maximum network throughput by up to 51%.     

Monitoring Edge-to-Edge Traffic Aggregates in Differentiated Services Networks

Differentiated Services (DiffServ), which are currently being standardized in the IETF DiffServ working group, is a solution that can provide different qualities of service to different network users. DiffServ aggregates network packets at edge routers and forwards the aggregated packets to core routers with different priorities. In this paper, we propose methods using the SNMP framework for monitoring edge-to-edge traffic aggregates in a DiffServ domain, which consists of a set of DiffServ-enabled routers. In order to manage each DiffServ router, we have analyzed the DiffServ MIB and instrumented it in the router. Further, we propose monitoring behaviors of edge-to-edge traffic aggregates by combining topology and performance information from MIB II and DiffServ MIB. Construction procedures and graphical representation of the edge-to-edge traffic aggregates are explained in detail. We also extend our efforts to implement a DiffServ domain monitoring system that monitors a set of DiffServ-enabled routers and traffic aggregates between every edge router pair. We believe that the proposed monitoring methods can serve as useful building blocks for managing DiffServ networks.