A new theory of deadlock-free adaptive routing in wormhole networks

The theoretical background for the design of deadlock-free adaptive routing algorithms for wormhole networks is developed. The author proposes some basic definitions and two theorems. These create the conditions to verify that an adaptive algorithm is deadlock-free, even when there are cycles in the channel dependency graph. Two design methodologies are also proposed. The first supplies algorithms with a high degree of freedom, without increasing the number of physical channels. The second methodology is intended for the design of fault-tolerant algorithms. Some examples are given to show the application of the methodologies. Simulations show the performance improvement that can be achieved by designing the routing algorithms with the new theory     

A general theory for deadlock-free adaptive routing using a mixedset of resources

This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory. A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks     

交换超立方网的自适应性无死锁路由算法

交换超立方网是一种新提出来的互连网络。首先,利用图论的方法研究了交换超立方网的拓扑性质,引入了相似子网的概念,得出相似子网和超立方体同构的结论;然后,利用将物理通道分成两条虚拟通道的方法,给出了一种交换超立方网的自适应性路由算法,并从理论上证明了该算法的无死锁性。     

A framework for designing deadlock-free wormhole routing algorithms

This paper presents a framework to design fully-adaptive, deadlock-free wormhole algorithms for a variety of network topologies. The main theoretical contributions are: (a) design of new wormhole algorithms using store-and-forward algorithms, (b) a sufficient condition for deadlock free routing by the wormhole algorithms so designed, and (c) a sufficient condition for deadlock free routing by these wormhole algorithms with centralized flit buffers shared among multiple channels. To illustrate the theory, several wormhole algorithms based on store-and-forward hop schemes are designed. The hop-based wormhole algorithms can be applied to a variety of networks including torus, mesh, de Brujin, and a class of Cayley networks, with the best known bounds on virtual channels for minimal routing on the last two classes of networks. An analysis of the resource requirements and performances of a proposed algorithm, called negative-hop algorithm, with some of the previously proposed algorithms for torus and mesh networks is presented     

A deadlock-free routing algorithm for dynamically reconfigurable Networks-on-Chip

We address routing in Networks-On-Chip (NoC) architectures that use irregular mesh topologies with Long-Range Links (LRL). These topologies create difficult conditions for routing algorithms, as standard algorithms assume a static, regular link structure and exploit the uniformity of regular meshes to avoid deadlock and maintain routability. We present a novel routing algorithm that can cope with these irregular topologies and adapt to run-time LRL insertion and topology reconfiguration. Our approach to accommodate dynamic topology reconfiguration is to use a new technique that decomposes routing relations into two stages: the calculation of output ports on the current minimal path and the application of routing restrictions designed to prevent deadlock. In addition, we present a selection function that uses local topology data to adaptively select optimal paths.The routing algorithm is shown to be deadlock-free, after which an analysis of all possible routing decisions in the region of an LRL is carried out. We show that the routing algorithm minimises the cost of sub-optimally placed LRL and display the hop savings available. When applied to LRLs of less than seven hops, the overall traffic hop count and associated routing energy cost is reduced. In a simulated 8 × 8 network the total input buffer usage across the network was reduced by 6.5%.     

A distributed multicast routing protocol for real-time multicast applications

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A delay bounded routing tree is a tree in which the accumulated delay from the source node to any destination along the tree does not exceed a pre-specified bound. This paper presents a distributed routing protocol which constructs delay bounded routing trees for real-time multicast connections. A constructed routing tree has a near optimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages required, and flexible in multicast membership changes. A large number of simulations have been done to show the network cost of the routing trees generated by our method is better than the other major existing algorithms.     

A distributed QoS-Aware multicast routing protocol

This paper discusses the multicast routing problem with QoS constraints, and describes a network model that is suitable to research such routing problem. The paper mainly presents a distributed QoS-aware multicast routing protocol (QMRP). The QMRP can operate on top of the unicast routing protocol. It only requires the local state information of the link (or the node), but does not require any global network state to be maintained. The QMRP can significantly reduce the overhead for constructing a multicast tree with QoS constraints. In QMRP, a multicast group member can join or leave the multicast session dynamically, which can support dynamic membership. The protocol can search multiple feasible tree branches, and select the optimal or near-optimal branch for connecting the new receiver to the multicast tree if it exists. In this paper, the proof of correctness and complexity analysis of the QMRP are given, and the performance measures of the protocol are evaluated using simulation. The study shows that QMRP provides an available approach to multicast routing with QoS constraints and dynamic membership support.Received: 3 April 2003, Published online: 2 September 2003     

Tree-turn routing: an efficient deadlock-free routing algorithm for irregular networks

In this paper, we propose a general turn model, called a Tree-turn model, for tree-based routing algorithms on irregular topologies. In the Tree-turn model, links are classified as either a tree link or a cross link and six directions are associated with the channels of links. Then we can prohibit some of the turns formed by these six directions such that an efficient deadlock-free routing algorithm, Tree-turn routing, can be derived. There are three phases to develop the Tree-turn routing. First, a coordinated tree for a given topology is created. Second, a communication graph is constructed based on the topology and the corresponding coordinated tree. Third, the forwarding table is set up by using all-pairs shortest path algorithm according to the prohibited turns in the Tree-turn model and the directions of the channels in the communication graph. To evaluate the performance of the proposed Tree-turn routing, we develop a simulator and implement Tree-turn routing along with up*/down* routing, L-turn routing, and up*/down* routing with DFS methodology. The simulation results show that Tree-turn routing outperforms other routing algorithms for all the test cases.     

AMRST: adaptive multicast routing protocol for satellite–terrestrial networks

Multicasting facilitates the distributing of multimedia information to an entire set of destinations simultaneously. However, the subsequent mass of Internet traffic usually increases the network congestion and degrades network utilization. The unexpected congestion together with limited network capacity might challenge the provision of multimedia services especially since multicast subscribers are widely scattered. The desired QoS of the ongoing services cannot be guaranteed. To address this challenge, in addition to installing new terrestrial broadband networks, another feasible solution would be to integrate now available broadcasting-oriented broadband satellite networks into the Internet backbone. This paper presents a novel adaptive multicast routing (AMRST) protocol to deliver reliable and adaptive multicast services to global subscribers, based on an integrated infrastructure, called a satellite–terrestrial network (ST network), which provides dynamic bandwidth allocation, flexible resource management and ubiquitous transmission. In the AMRST, a proposed virtual hierarchical routing tree was applied in constructing an efficient multicast tree. A routing decision model was proposed to determine routing path for the member requests. A “hierarchical membership maintenance” approach was designed to maintain the multicast membership. The scalability of the AMRST was further addressed. The AMRST not only kept the benefits of the traditional terrestrial multicast but also promoted the multicasting performance by employing the satellite broadcasting capability. The simulation results demonstrate that the AMRST performed excellently for the ST network.     

Fully adaptive minimal deadlock-free packet routing in hypercubes,meshes, and other networks: algorithms and simulations

This paper deals with the problem of packet-switched routing in parallel machines. Several new routing algorithms for different interconnection networks are presented. While the new techniques apply to a wide variety of networks, routing algorithms will be shown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Although the new techniques are designed for packet routing, they can be used alternatively for virtual cut-through routing models. The techniques presented for hypercubes and meshes are fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which all possible minimal paths between a source and a destination are of potential use at the time a message is injected into the network. Minimal paths followed by messages ultimately depend on the local congestion encountered in each node of the network. All of the new techniques are completely free of deadlock situations     

受时延约束的组播路由算法

提出了一种新的受时延约束的组播路由算法。算法借鉴了MPH算法的思想,最初的组播树只包含源结点,然后每次将到达组播树的代价最小且满足时延约束的结点及其相应的路径加入到组播树,直到所有的成员加入为止。谊算法能够快速地得到一棵满足时延约束的组播树,并且组播树的代价也很小。实验表明：该算法简单,复杂度低,性能良好,易于在分布式环境中实现,可应用于实际的应用系统中。     

A survey of combinatorial optimization problems in multicast routing

In multicasting routing, the main objective is to send data from one or more sources to multiple destinations, while at the same time minimizing the usage of resources. Examples of resources which can be minimized include bandwidth, time and connection costs. In this paper, we survey applications of combinatorial optimization to multicast routing. We discuss the most important problems considered in this area, as well as their models. Algorithms for each of the main problems are also presented.     

A necessary and sufficient condition for deadlock-free routing incut-through and store-and-forward networks

This paper develops the theoretical background for the design of deadlock-free adaptive routing algorithms for virtual cut-through and store-and-forward switching. This theory is valid for networks using either central buffers or edge buffers. Some basic definitions and three theorems are proposed, developing conditions to verify that an adaptive algorithm is deadlock-free, even when there are cyclic dependencies between routing resources. Moreover, we propose a necessary and sufficient condition for deadlock-free routing. Also, a design methodology is proposed. It supplies fully adaptive, minimal and non-minimal routing algorithms, guaranteeing that they are deadlock-free. The theory proposed in this paper extends the necessary and sufficient condition for wormhole switching previously proposed by us. The resulting routing algorithms are more flexible than the ones for wormhole switching. Also, the design methodology is much easier to apply because it automatically supplies deadlock-free routing algorithms     

A note on distributed multicast routing in point-to-point networks

The distributed algorithm for a multicast connection set-up, based on the ‘cheapest insertion’ heuristic, is reviewed. The multicast routing problem is translated into a Steiner tree problem in point-to-point networks where nodes have only a limited knowledge about the network. A solution is proposed in which the time complexity and the amount of information exchanged between network nodes are proportional to the number of members of the multicast group. The Steiner tree is constructed by means of a distributed table-passing algorithm. The analysis of the algorithm presented, backed up by simulation results, confirms its superiority over the algorithm based on ‘waving technique’.Scope and purposeMulticasting is a mechanism used in communication networks that allows distribution of information from a single source to multiple destinations. The problem of finding a multicast connection for a static group of communicating entities in connection-oriented point-to-point network can be formulated in graph theory as a minimum Steiner tree problem. Due to NP-completeness of the Steiner tree problem multicast, routing algorithms are based on heuristics. The diversity of network environments and the lack of centralised information about network topology require an effective distribution of the multicast routing algorithms among the network nodes. This article presents an alternative to the distributed algorithm proposed by Rugelj and Klavzar that implements the same heuristics for the construction of a minimum cost multicast connection in point-to-point networks. The present algorithm constitutes a substantial improvement over that previously proposed with regard to running time and the amount of the information exchanged between network nodes.     

A flexible multicast routing protocol for group communication

Multicast routing, once dominated by a single routing protocol, is becoming increasingly diverse. It is generally agreed that at least three routing protocols, PIM, DVMRP, and CBT will be widely deployed and must interoperate. This signals a shift from the Mbone as one large domain to a collection of administrative domains where each domain selects its own multicast routing protocol.This paper proposes another multicast routing protocol, Conference Steiner Multicast (CSM), that is suited for domains that implement OSPF as the unicast routing protocol. CSM is targeted towards (sparse) multicast conferencing and online discussion groups. Characteristics of such discussion groups include any member being a speaker or listener and dynamic changes in the group membership. CSM is futhermore well suited for domains with mobile hosts because its basic architecture can support a mobile environment.CSM is based on the use of a shared, heuristic Steiner minimal tree for interconnecting group members. A key component of the design is that it dynamically and reliably shifts to a different tree as changes warrant. CSM supports rudimentary entry control for security and permits application assistance over routing decisions (termed Application Assisted Routing).This paper describes the architecture of CSM as well as a prototype implementation. Several CSM routers have been interconnected to form a Multicast Steiner Backbone (Msbone). Standard applications such as vat, vic, and wb [V. Jacobson, Multimedia Conferencing on the Internet, Tutorial 4, ACM SIG-COMM 94, August 1994] have been modified to run on Msbone. CSM is designed to connect to the Mbone via interoperation with DVMRP, and as interoperation standards develop it should be capable of implementing these standards.     

Pseudo-cycle-based multicast routing in wormhole-routed networks

This paper addresses the problem of fault-tolerant multicast routing in wormholerouted multicomputers.A new pseudo-cycle-based routing method is presented for constructing deadlock-free multicast routing algorithms.With at most two virtual channels this technique can be applied to any connected networks with arbitrary topologies.Simulation results show that this technique results in negligible performance degradation even in the presence of a large number of faulty nodes.     

Adaptive and deadlock-free routing for irregular faulty patterns inmesh multicomputer

Message routing achieves the internode communication in parallel computers. A reliable routing is supposed to be deadlock-free and fault-tolerant. While many routing algorithms are able to tolerate a large number of faults enclosed by rectangular faulty blocks, there is no existing algorithm that is capable of handling irregular faulty patterns for wormhole networks. In this paper, a two-staged adaptive and deadlock-free routing algorithm called “Routing for Irregular Faulty Patterns” (RIFP) is proposed. It can tolerate irregular faulty patterns by transmitting messages from sources or to destinations within faulty blocks via multiple “intermediate nodes.” A method employed by RIFP is first introduced to generate intermediate nodes using the local failure information. By its aid, two communicating nodes can always exchange their data or intermediate results if there is at least one path between them. RIFP needs two virtual channels per physical link in meshes     

A theory for deadlock-free dynamic network reconfiguration. Part I

This paper develops theoretical support useful for determining deadlock properties of dynamic network reconfiguration techniques and also serves as a basis for the development of design methodologies useful for deriving deadlock-free reconfiguration techniques. It is applicable to interconnection networks typically used in multiprocessor servers, network-based computing clusters, and distributed storage systems, and also has potential application to system-on-chip networks. This theory builds on basic principles established by previous theories while pioneering new concepts fundamental to the case of dynamic network reconfiguration.     

一种适合于DiffServ网络的多播路由算法

提出一种适合于DiffServ网络的QoS多播路由算法PQMRD,它针对组成员不同类别的QoS请求采取不同的路由策略来选取路径,同时进行分类的接纳控制和资源预留。实验结果表明,PQMRD缓解了现有多播算法中因所有业务选择相同路径而引起的服务类间的不公平性问题。