An effective methodology to improve the performance of the up*/down* routing algorithm

Networks of workstations (NOWs) are being considered as a cost-effective alternative to parallel computers. Most NOWs are arranged as a switch-based network and provide mechanisms for discovering the network topology. Hence, they provide support for both regular and irregular topologies, which makes routing and deadlock avoidance quite complicated. Current proposals use the up*/down* routing algorithm to remove cyclic dependencies between channels and avoid deadlock. However, routing is considerably restricted and most messages must follow nonminimal paths, increasing latency and wasting resources. We propose and evaluate a simple and effective methodology to compute up*/down* routing tables. The new methodology is based on computing a depth-first search (DPS) spanning tree on the network graph that decreases the number of routing restrictions with respect to the breadth-first search (BFS) spanning tree used by the traditional methodology. Additionally, we propose different heuristic rules for computing the spanning trees to improve the efficiency of up*/down* routing. Evaluation results for several different topologies show that computing the up*/down* routing tables by using the new methodology increases throughput by a factor of up to 2.48 in large networks with respect to the traditional methodology, and also reduces latency significantly.     

High-performance routing in networks of workstations with irregulartopology

Networks of workstations are rapidly emerging as a cost-effective alternative to parallel computers. Switch-based interconnects with irregular topology allow the wiring flexibility, scalability, and incremental expansion capability required in this environment. However, the irregularity also makes routing and deadlock avoidance on such systems quite complicated. In current proposals, many messages are routed following nonminimal paths, increasing latency and wasting resources. In this paper, we propose two general methodologies for the design of adaptive routing algorithms for networks with irregular topology. Routing algorithms designed according to these methodologies allow messages to follow minimal paths in most cases, reducing message latency and increasing network throughput. As an example of application, we propose two adaptive routing algorithms for ANI (previously known as Autonet). They can be implemented either by duplicating physical channels or by splitting each physical channel into two virtual channels. In the former case, the implementation does not require a new switch design. It only requires changing the routing tables and adding links in parallel with existing ones, taking advantage of spare switch ports. In the latter case, a new switch design is required, but the network topology is not changed. Evaluation results for several different tapologies and message distributions show that the new routing algorithms are able to increase throughput for random traffic by a factor of up to 4 with respect to the original up*/down* algorithm, also reducing latency significantly. For other message distributions, throughput is increased more than seven times. We also show that most of the improvement comes from the use of minimal routing     

Up*/Down*路由算法的改进方案

机群系统 (NOWs)用于并行计算具有性能价格比高、结构灵活、可扩展性好等优点 ,但要实现高性能的机群系统 ,必须采用交换式高速互连网络 .交换器之间连接的不规则性 ,使路由与死锁避免问题非常复杂 .介绍了不规则拓扑网络中经典的 up* / down*路由算法 ,分析它的实现原理 ,指出了它在链路方向指派方面的不合理性 ,并基于贪婪算法的思想 ,给出了优化的链路方向指派方法 ,由此确定新的路由算法 greedy- U D.经模拟实验证明 ,greedy- U D算法较up* / down*路由算法性能有了显著提高     

An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks

System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up*/down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up*/down*-based routings, and also reduce latency     

Sparse communication networks and efficient routing in the plane

Traditional approaches to network design separate the issues of designing the network itself and designing its management and control subsystems. This paper proposes an approach termed routing-oriented network design, which is based on designing the network topology and its routing scheme together, attempting to optimize some of the relevant parameters of both simultaneously. This approach is explored by considering the design of communication networks supporting efficient routing in the special case of points located in the Euclidean plane. The desirable network parameters considered include low degree and small number of communication links. The desirable routing parameters considered include small routing tables, small number of hops and low routing stretch. Two rather different schemes are presented, one based on direct navigation in the plane and the other based on efficient hierarchical tree covers. On a collection of n sites with diameter D, these methods yield networks with a total of communication links and some bounds on the degree, coupled with routing schemes with constant routing stretch, memory bits per vertex and routes with at most or hops. Received: October 2000 / Accepted: May 2001     

An Online Algorithm for the Dynamic Maximal Dense Tree Problem

Abstract. The Online Maximal Dense Tree problem is as follows: given a weighted directed graph and a source node, users issue online requests for connection to the source node. A request can either be accepted or rejected (the admission control decision). If the connection request is accepted, it must be connected to the source or to a node previously connected to the source (the routing decision). The objective is to maximize the total number of connections while keeping the connection density , i.e. the ratio of accepted requests to the weight of the spanning tree, sufficiently high. The primary motivation for the Maximal Dense Tree problem is the Online Capacitated Multicast admission control and routing problem. In the Online Capacitated Multicast problem, we are given a communication network with limited link capacities and a set of signal source nodes. Users generate online requests for connection to the signal sources, and the network administrator has to make the admission control and routing decisions. The goal of the network administrator is to maximize the total number of users connected subject to the network capacity constraints. The Online Maximal Dense Tree problem is also faced by a cable TV operator who wishes to connect as many customers as possible while keeping down the amount of wiring per customer. Informally, the Online Maximal Dense Tree algorithm must ``gamble' on certain geographic areas, connecting nodes which are unprofitable to start with, in the hope that eventually enough requests will arrive in its vicinity to make the investment profitable. In this paper we present a randomized online algorithm for the Maximal Dense Tree problem that guarantees acceptance of a (1- ɛ) factor of the requests accepted by the optimum offline algorithm with the expectation of density being at most polylogarithmically lower than that of the offline algorithm. This yields an online capacitated multicast algorithm whose throughput is only poly-logarithmically lower than that of the optimum offline algorithm. Previous work on multicast routing and maximal dense tree problems either made probabilistic assumptions or resulted in linear performance gaps with the offline algorithm. Attempts to solve the Online Maximal Dense Tree problem have also lead to the development of the first polylogarithmic approximation algorithms for the k -MST and the Prize Collecting Salesman problems [AABV].     

不规则网络中基于拐弯模型的路由算法的设计

由虫孔路由交换器连接而成的不规则拓扑网络，越来越多地用于构建工作站机群系统（NOWs），以实现高性能价格比的并行处理．采用虫孔路由技术，网络中容易发生死锁．交换器之间连接的不规则性，使路由避免死锁问题变得更加复杂．本文给出了在不规则网络中，设计基于拐弯模型的无死锁路由算法的一般方法，并采用扩展链路方向的方法得到多种路由策略，确定了up-first与down-last两种性能较优的路由算法．最后通过模拟实验，评价了算法的性能．     

A general methodology for direction-based irregular routing algorithms

This paper presents a general methodology for generating deadlock-free routing algorithms for irregular networks. Constructing a spanning tree on the given network, assigning directions to the network channels, creating deadlock-free zones, and specifying a logical sequence of the produced deadlock-free zones are the four fundamental steps that the proposed methodology takes to generate deadlock-free and connected routing algorithms. By applying the proposed methodology with two known labeling methods we have generated six irregular routing algorithms: three of them are novel routing algorithms and three of them (the Up/Down, Left/Right, and L-turn routing algorithms) have already been proposed in the literature. Extensive simulation experiments have been performed considering various network topologies, different network sizes (considering different network nodes and network channels), various message lengths, a variety of spanning tree roots, and a wide range of message (traffic) generation rates. Simulation results show that the six routing algorithms can be divided into three pairs. Routing members of each pair show similar behavior in terms of message latencies and saturation generation rates. However, it is worth noting that for a given topology the performance of the six routing algorithms may be totally different and it mainly depends on the network topology.     

新型电路版图布局布线算法设计

调研了电路自动布局布线技术的国内外研究现状,在此基础上设计了一种面向中等规模电路布局布线算法,主要用于大型版图设计软件的模块测试环节,为用户提供各模块初步的布线布局结果,方便用户高效查找并修正错误点,填补了我国在相关领域的空白.建立了超图模型并转换为图模型,改进了Stoer-Wagner算法并利用该算法和Fiduccia-Mattheyses算法对图进行了基于最小割理论的划分,从而构建出一棵划分树.在这棵树的基础上设计了一种二元相对移动算法来确定各个电路元件的位置,大大降低了布局拥挤度,提高了美观度,对于数百元件的电路均能在0.5s内得出布局结果.基于A*算法在多个方面做了改进,提高了布线速度,对于线路数1000以下的元件能在0.1 s～60 s内得出结果,实现了100％ 布通率以及均匀的布局布线效果.     

An Online Algorithm for the Dynamic Maximal Dense Tree Problem

The Online Maximal Dense Tree problem is as follows: given a weighted directed graph and a source node, users issue online requests for connection to the source node. A request can either be accepted or rejected (the admission control decision). If the connection request is accepted, it must be connected to the source or to a node previously connected to the source (the routing decision). The objective is to maximize the total number of connections while keeping the connection density , i.e. the ratio of accepted requests to the weight of the spanning tree, sufficiently high. The primary motivation for the Maximal Dense Tree problem is the Online Capacitated Multicast admission control and routing problem. In the Online Capacitated Multicast problem, we are given a communication network with limited link capacities and a set of signal source nodes. Users generate online requests for connection to the signal sources, and the network administrator has to make the admission control and routing decisions. The goal of the network administrator is to maximize the total number of users connected subject to the network capacity constraints. The Online Maximal Dense Tree problem is also faced by a cable TV operator who wishes to connect as many customers as possible while keeping down the amount of wiring per customer. Informally, the Online Maximal Dense Tree algorithm must ``gamble'' on certain geographic areas, connecting nodes which are unprofitable to start with, in the hope that eventually enough requests will arrive in its vicinity to make the investment profitable. In this paper we present a randomized online algorithm for the Maximal Dense Tree problem that guarantees acceptance of a (1- ?) factor of the requests accepted by the optimum offline algorithm with the expectation of density being at most polylogarithmically lower than that of the offline algorithm. This yields an online capacitated multicast algorithm whose throughput is only poly-logarithmically lower than that of the optimum offline algorithm. Previous work on multicast routing and maximal dense tree problems either made probabilistic assumptions or resulted in linear performance gaps with the offline algorithm. Attempts to solve the Online Maximal Dense Tree problem have also lead to the development of the first polylogarithmic approximation algorithms for the k -MST and the Prize Collecting Salesman problems [AABV].     

Integrated topology control and routing in wireless optical mesh networks

We study the problem of integrated topology control and routing in Free Space Optical (FSO) mesh backbone networks. FSO links are high-bandwidth, low interference links that can be set-up very fast, making them suitable for mesh networking. FSO networks are highly constrained by interface constraints, i.e., constraints on the number of FSO links a node can establish. We prove the problem to be NP-Hard and propose efficient algorithms for integrated topology control and single-path or multi-path routing.     

A Kind of Multistage Interconnection Networks with Multiple Paths

Mltistage Interconnection Networks(MINs)are orten used to provide interconnections in multiprocessor systems.A unique path MIN usually has lower hardware complexity and a simple control algorithm,but it lacks fault tolerance.This paper proposes a kind of multipat MINs,which are obtained by adding auxiliary links at the final stage in Quad Tree(QT) networks so that they can provide more paths between each source-destination pair,and presents their routing algorithm which is both destination tag based and adaptive.Starting with the routing tag for the minimum path between a given source-destination pair,the routing algorithm uses a set of rules to select switches and modify routing tag.In addition to trying the auxiliary link when link0 an link1 are unavilable,link1 will be tried when link0 ys unavailable.This feature distinguishing the proposed routing algorithm form that for QT networks makes better use of all the possible paths between the given source-destination pair.In the end,this paper introduces a performance index,which is called capacity,to compare different kinds of MINs .Comparison shows that the proposed MINs have better capacity than QT networks.     

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.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

LABILE: link quAlity-based lexIcaL routing mEtric for reactive routing protocols in IEEE 802.15.4 networks

In this paper, we propose a lexical routing metric to enable path-wise link quality-aware routing in Wireless Sensor Networks (WSNs). The realization of this routing metric is achieved by applying the indexing techniques of formal language processing in multi-metric route classification and cost evaluation for WSNs. In particular, the metric is motivated from the fact that IEEE 802.15.4 networks are formed on links with highly variable quality, and selection of poor quality links degrades the data delivery considerably. Although IEEE 802.15.4 supports link-level awareness through LQI, (a)?it remains unbeknownst at the path level, and therefore, (b)?its processing is link-local in scope. We propose LABILE, a composite routing metric, that is implemented through modifying RREQ and RREP structures of AODV to capture and convey two-state link information to destination which in turn is processed through an easy to compute routing lexicon and a corresponding lexical algorithm for path selection in case of availability of multiple paths. Multiple paths are represented in a path space through a proposed cost model that encompasses hop-count, weak links and a quantity weakness factor of each link, depending upon a thresholding mechanism which in turn declares a link to be either healthy (aka usable) or weak (aka unusable). Using the weakness factor, the success probability of data delivery over weak link turns out to be a fraction of success probability at healthy link. The mathematical model along with the experiments done for LABILE show that proposed composite metric and its parsing scheme together achieve link robustness consistently by evading the link failures, as the number of weak links is fairly reduced in lexical path as compared to the hop-count-based metric. Increased data delivery is obtained through preventing retransmissions as on failure-prone links.     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).     

SWER: small world-based efficient routing for wireless sensor networks with mobile sinks

The interest in small-world network has highlighted the applicability of both the graph theory and the scaling theory to the analysis of network systems. In this paper, we introduce a new routing protocol, small world-based efficient routing (SWER), dedicated to supporting sink mobility and small transfers. The method is based on the concept of the small worlds where the addition of a small number of long-range links in highly clustered networks results in significant reduction in the average path length. Based on the characteristic of sensor networks, a cluster-based small world network is presented, and an analytical model is developed to analyze the expected path length. SWER adopts a simple and effective routing strategy to forward data to the mobile sink in a small transfer scene and avoid expensive mechanisms to construct a high quality route. We also study the routing scheme and analyze the expected path length in the case where every node is aware of the existence of p long-range links. In addition, we develop a hierarchical mechanism in which the mobile sink only transmits its location information to the cluster heads when it enters a new cluster. Thus we also avoid expensive cost to flood the location of the mobile sink to the whole network.     

基于演化图论的可靠的VANETs路由协议

车载网络（VANETs）属于移动无线网络的特例,具有鲜明的特性。传统无线网络的路由协议难以直接应用于VANETs。节点的高速移动,引起网络拓扑动态变化,导致VANETs的通信链路频繁断裂。高动态网络的链路可靠性问题引起广泛的关注。为此,针对高速公路VANETs的路由可靠性进行分析,对演化图论进行扩展,建立扩展后的演化图论模型（EEGM）,并利用EEGM获取VANETs拓扑的动态信息,从而预先获取可靠路由的信息。在此基础上,提出基于演化图论的可靠路由协议（EG-RAODV）。仿真结果表明,与同类的其他协议相比,提出的路由协议在分组传输率、端到端传输时延、路由请求消息率以及链路断裂数方面得到了提升。     

异步粒子群优化算法在QoS组播路由中的应用

QoS组播路由问题是一个非线性的组合优化问题,已证明了该问题是NP完全问题。为适应下一代IP网络对实时信息传输的要求,在异步模式粒子群优化算法基础上,给出包含延迟、延迟抖动、带宽、丢包率和最小花费5个约束条件在内的QoS组播路由算法。该算法首先给出数学模型,设计适应度函数,再给出受限的网络模型,通过粒子群优化(PSO)算法最大化适应度函数来求解最优Steiner树。算法仿真实验结果表明:与遗传算法和同步模式的粒子群优化算法相比,该算法有较好的收敛速度和寻优效果。     

A QoS multicast routing protocol for dynamic group topology

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A multicast routing tree with multiple QoS constraints may be the tree in which the delay, delay-jitter, packet-loss and bandwidth should satisfy the pre-specified bounds. This paper discusses the multicast routing problem with multiple QoS constraints, which may deal with the delay, delay-jitter, bandwidth and packet-loss metrics, and describes a network model for researching the routing problem. It presents a QoS multicast routing protocol with dynamic group topology (QMRPD). The QMRPD attempts to significantly reduce the overhead of constructing a multicast tree with multiple QoS constraints. In MPRMQ, a multicast group member can join or leave a multicast session dynamically, which should not disrupt the multicast tree. It also attempts to minimize overall cost of the tree, and satisfy the multiple QoS constraints and least cost's (or lower cost) requirements. In this paper, the proof of correctness and complexity analysis of the QMRPD are also given. Simulation results show that QMRPD is an available approach to multicast routing decision with dynamic group topology.