Multi‐constrained Shortest Disjoint Paths for Reliable QoS Routing

Finding link‐disjoint or node‐disjoint paths under multiple constraints is an effective way to improve network QoS ability, reliability, and so on. However, existing algorithms for such scheme cannot ensure a feasible solution for arbitrary networks. We propose design principles of an algorithm to fill this gap, which we arrive at by analyzing the properties of optimal solutions for the multi‐constrained link‐disjoint path pair problem. Based on this, we propose the link‐disjoint optimal multi‐constrained paths algorithm (LIDOMPA), to find the shortest link‐disjoint path pair for any network. Three concepts, namely, the candidate optimal solution, the contractive constraint vector, and structure‐aware non‐dominance, are introduced to reduce its search space without loss of exactness. Extensive simulations show that LIDOMPA outperforms existing schemes and achieves acceptable complexity. Moreover, LIDOMPA is extended to the node‐disjoint optimal multi‐constrained paths algorithm (NODOMPA) for the multi‐constrained node‐disjoint path pair problem.     

A fault tolerant routing scheme for hypercubes

An efficient distributed fault‐tolerant routing algorithm for the hypercube is proposed based on the existence of a complete set of node‐disjoint paths between any two nodes. Node failure and repairs may occur dynamically provided that the total number of faulty nodes at any time is less than the node‐connectivity n of the n‐cube. Each node maintains for each possible destination which of the associated node‐disjoint paths to use. When a message is blocked by a node failure, the source node is warned and requested to switch to a different node‐disjoint path. The methods used to identify the paths, to propagate node failure information to source nodes, and to switch from one routing path to another incur little communication and computation overhead. We show that if the faults occur reasonably apart in time, then all messages will be routed on optimal or near optimal paths. In the unlikely case where many faults occur in a short period, the algorithm still delivers all messages but via possibly longer paths. An extension of the obtained algorithm to handle link failures in addition to node failures is discussed. We also show how to adapt the algorithm to n‐ary n‐cube networks. The algorithm can be similarly adapted to any interconnection network for which there exists a simple characterization of node‐disjoint paths between its nodes. This revised version was published online in June 2006 with corrections to the Cover Date.     

网树求解有向无环图中具有长度约束的最大不相交路径

对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为k的最大不相交路径。为了对该问题进行求解,提出了贪婪搜索算法(GP, greedy path),该算法先将一个有向无环图转化为一棵深度为k+1的网树,然后计算每个网树节点的树根叶子路径数,并以此计算图中每个顶点的总路径数,之后从网树的第k+1层节点出发,在当前节点的双亲节点中选择未被使用且总路径数最小的双亲,以此形成一条优化的不相交路径,最后迭代这一过程,直到不再有新的不相交路径为止。GP算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n2)。为了测试GP算法的近似性,又建立了一种能够生成人工数据的算法,该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据,实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短,验证了该方法的有效性和可行性。     

Link‐disjoint paths for reliable QoS routing

The problem of finding link/node‐disjoint paths between a pair of nodes in a network has received much attention in the past. This problem is fairly well understood when the links in a network are only specified by a single link weight. However, in the context of quality of service routing, links are specified by multiple link weights and restricted by multiple constraints. Unfortunately, the problem of finding link/node disjoint paths in multiple dimensions faces different conceptual problems. This paper presents a first step to understanding these conceptual problems in link‐disjoint quality of service routing and proposes a heuristic link‐disjoint QoS algorithm that circumvents these problems. Copyright © 2003 John Wiley & Sons, Ltd.     

Loop-free routing using diffusing computations

A family of distributed algorithms for the dynamic computation of the shortest paths in a computer network or internet is presented, validated, and analyzed. According to these algorithms, each node maintains a vector with its distance to every other node. Update messages from a node are sent only to its neighbors; each such message contains a distance vector of one or more entries, and each entry specifies the length of the selected path to a network destination, as well as an indication of whether the entry constitutes an update, a query, or a reply to a previous query. The new algorithms treat the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten (1980). They improve on a number of algorithms introduced previously. The new algorithms are shown to converge in finite time after an arbitrary sequence of link cost or topological changes, to be loop-free at every instant, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities     

Queue‐based multiple path load balancing routing protocol for MANETs

Congestion in the network is the main cause for packet drop and increased end‐to‐end transmission delay of packet between source and destination nodes. Congestion occurs because of the simultaneous contention for network resources. It is very important to efficiently utilize the available resources so that a load can be distributed efficiently throughout the network. Otherwise, the resources of heavily loaded nodes may be depleted very soon, which ultimately affects network performances. In this paper, we have proposed a new routing protocol named queue‐based multiple path load balancing routing protocol. This protocol discovers several node‐disjoint paths from source to destination nodes. It also finds minimum queue length with respect to individual paths, sorts the node‐disjoint paths based on queue length, and distributes the packets through these paths based on the minimum queue length. Simulation results show that the proposed routing protocol distributes the load efficiently and achieves better network performances in terms of packet delivery ratio, end‐to‐end delay, and routing overhead. Copyright © 2016 John Wiley & Sons, Ltd.     

Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information

The paper presents new algorithms for dynamic routing of restorable bandwidth-guaranteed paths. We assume that connections are requested one-by-one and there is no prior knowledge of future arrivals. In order to guarantee restorability an alternate link (node) disjoint backup (restoration) path has to be determined, as well as an active path, when the connection is initiated. This joint on-line routing problem is particularly important in optical networks and in MPLS networks for dynamic provisioning of bandwidth-guaranteed or wavelength paths. A simple solution is to find two disjoint paths, but this results in excessive resource usage. Backup path bandwidth usage can be reduced by judicious sharing of backup paths amongst certain active paths while still maintaining restorability. The best sharing performance is achieved if the routing of every path in progress in the network is known to the routing algorithm at the time of a new path setup. We give a new integer programming formulation for this problem. Complete path routing knowledge is a reasonable assumption for a centralized routing algorithm, but is not often desirable, particularly when distributed routing is preferred. We show that a suitably developed algorithm which uses only aggregated information, and not per-path information, is able to perform almost as well as one using complete information. Disseminating this aggregate information is feasible using proposed traffic engineering extensions to routing protocols. We formulate the dynamic restorable bandwidth routing problem in this aggregate information scenario and develop efficient routing algorithms. The performance of our algorithm is close to the complete information bound.     

Power-aware single- and multipath geographic routing in sensor networks

Nodes in a sensor network, operating on power limited batteries, must save power to minimize the need for battery replacement. We note that the range of transmission has a significant effect on the power consumption of both the transmitting node and listeners. This paper first presents a Geographical Power Efficient Routing (GPER) protocol for sensor networks. Each sensor node makes local decisions as to how far to transmit: therefore, the protocol is power efficient, localized, highly distributed, and scalable. In GPER, given a final destination, each node first establishes a subdestination within its maximum radio range. The node, however, may decide to relay the packet to this subdestination through an intermediary node or alter the subdestination if this will preserve power. Traditional deterministic geographic routing algorithms aim at achieving close to the shortest weighted paths. However, they normally stick to the same paths for the same source/destination pairs. This may conversely drain the nodes on these paths and result in short network life when the communication in the network is unevenly distributed. Thus, we further investigate a set of probabilistic multipath routing algorithms, which generate braided multipaths based only on local information. The algorithms have less communication and storage overhead than conventional on-demand multipath routing algorithms, while providing greater resilience to node failures. Simulations on NS2 show that GPER almost halves the power consumption in the network relative to alternative geographic routing algorithms. Furthermore, in situations where the communication tasks are non-uniformly distributed, probabilistic multipath routing contributes up to an additional 30% to network lifetime.     

一种集中调控的分布式服务路径选择算法

在可重构网络多态路由模型中,通常存在多条满足业务需求的服务路径。针对最优服务路径选择问题,该文设计了一种集中调控的分布式服务路径选择算法,各节点根据服务请求中的第1个元能力和目的节点生成路由表,控制器实时监控网络,调控代价过高路径并平衡网络的带宽和负载。性能分析和仿真结果表明,分布式路由表能够生成有效的服务路径,表项规模、收敛时间与元能力个数成正比,在30%的集中调控比例下,路径代价和负载均衡度性能良好,与其他算法相比,对服务请求的响应时延降低约50%。     

Solution to the problem of ant being stuck by ant colony routing algorithm

Many ant colony routing (ACR) algorithms have been presented in recent years, but few have studied the problem that ants will get stuck with probability in any terminal host when they are searching paths to route packets around a network. The problem has to be faced when designing and implementing the ACR algorithm. This article analyzes in detail the differences between the ACR and the ant colony optimization (ACO). Besides, particular restrictions on the ACR are pointed out and the three causes of ant being-stuck problem are obtained. Furthermore, this article proposes a new ant searching mechanism through dual path-checking and online routing loop removing by every intermediate node an ant visited and the destination host respectively, to solve the problem of ant being stuck and routing loop simultaneously. The result of numerical simulation is abstracted from one real network. Compared with existing two typical ACR algorithms, it shows that the proposed algorithm can settle the problem of ant being stuck and achieve more effective searching outcome for optimization path.     

Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is somewhat surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.Anand Srinivas is currently a PhD candidate in the Laboratory for Information and Decision Systems (LIDS) at MIT. He recieved his Masters of Science in EECS from MIT in 2004, and his Bachelors of Applied Science in Computer Engineering from the University of Toronto in 2001. In 2004 he also received a Masters of Science in Aerospace Engineering from MIT. His current research interests include reliability and energy-efficiency in wireless ad-hoc networks, routing and network optimization, graph theory, and the design of efficient algorithms. E-mail: anand3@mit.eduEytan Modiano received his B.S. degree in Electrical Engineering and Computer Science from the University of Connecticut at Storrs in 1986 and his M.S. and Ph.D. degrees, both in Electrical Engineering, from the University of Maryland, College Park, MD, in 1989 and 1992 respectively. He was a Naval Research Laboratory Fellow between 1987 and 1992 and a National Research Council Post Doctoral Fellow during 1992–1993 while he was conducting research on security and performance issues in distributed network protocols.Between 1993 and 1999 he was with the Communications Division at MIT Lincoln Laboratory where he designed communication protocols for satellite, wireless, and optical networks and was the project leader for MIT Lincoln Laboratory’s Next Generation Internet (NGI) project. He joined the MIT faculty in 1999, where he is presently an Associate Professor in the Department of Aeronautics and Astronautics and the Laboratory for Information and Decision Systems (LIDS). His research is on communication networks and protocols with emphasis on satellite, wireless, and optical networks.He is currently an Associate Editor for Communication Networks for IEEE Transactions on Information Theory and for The International Journal of Satellite Communications. He had served as a guest editor for IEEE JSAC special issue on WDM network architectures; the Computer Networks Journal special issue on Broadband Internet Access; the Journal of Communications and Networks special issue on Wireless Ad-Hoc Networks; and for IEEE Journal of Lightwave Technology special issue on Optical Networks. He is the Technical Program co-chair for Wiopt 2006 and vice- chair for Infocom 2007. E-mail: modiano@mit.edu     

Distributed simultaneous wireless information and power transfer in multiuser amplify‐and‐forward ad hoc wireless networks

This paper studies the problem of stable node matching for distributed simultaneous wireless information and power transfer in multiuser amplify‐and‐forward ad hoc wireless networks. Particularly, each source node aims to be paired with another node that takes the role of an amplify‐and‐forward relay to forward its signal to the destination, such that the achievable rate is improved, in return of some payment made to the relaying node. Each relaying node splits its received signal from its respective source into two parts: one for information processing and the other for energy harvesting. In turn, a matching‐theoretic solution based on the one‐to‐one stable marriage matching game is studied, and a distributed polynomial‐time complexity algorithm is proposed to pair each source node with its best potential relaying node based on the power‐splitting ratios, such that their utilities or payments are maximized while achieving network stability. For comparison purposes, an algorithm to enumerate all possible stable matchings is also devised to study the impact of different matchings on the source and relay utilities. Simulation results are presented to validate the proposed matching algorithm and illustrate that it yields sum‐utility and sum‐payment that are closely comparable to those of centralized power allocation and node pairing, with the added merits of low complexity, truth telling, and network stability.     

Tree-based differential evolution algorithm for QoS multicast routing

Differential evolution(DE)algorithm has attracted more and more attention due to its fast optimization performance and good stability.When DE algorithm is applied into multi-constrained multicast routing optimization problem,a common solution to such problem is to merge the paths into a tree after finding paths from the source node to each destination node.This method maybe obtains the better result,but it can consume a lot of computational time.To solve the problem,a tree-based DE algorithm is introduced in this paper.The central operations of the algorithm are realized with tree structure.This method saves the time of finding paths and integrating them to construct a multicast tree.The experiments show that the proposed algorithm can achieve higher success rate than several common algorithms with much smaller running time for different networks.     

A k shortest path algorithm for adaptive routing incommunications networks

An efficient and flexible algorithm is presented for finding a k shortest loopless path with distinct initial links from one node to each other node. Low-order polynomial bounds are established for the worst-case time complexity of the algorithm, showing it to offer a substantial improvement over applying known algorithms to the problem. The algorithm can incorporate various extensions, including the ability to handle an algebraic objective, which enhance its applicability to diverse network models. In addition, the k shortest path formulation and algorithm are proposed as a basis for network survivability measures where path length bounds exist     

Energy‐efficient partner selection in cooperative wireless networks: a matching‐theoretic approach

In this paper, the problem of stable energy‐efficient partner selection in cooperative wireless networks is studied. Each node aims to be paired with another node so as to minimize the total energy consumption required to meet a target end‐to‐end signal‐to‐noise ratio requirement and thus maintain quality of service. Specifically, each node ranks every other node in the network according to their energy saving achievable through cooperation. Two polynomial time complexity algorithms based on the stable roommates matching problem are proposed through which nodes are paired according to their preference lists. The first algorithm, denoted Irving's stable matching, may not always have a stable solution. Therefore, the second algorithm—which is a modified version of Irving's algorithm and denoted maximum stable matching—is proposed to find the maximum number of stable disjoint pairs. Simulation results are provided to validate the efficiency of the proposed algorithms in comparison with centralized energy‐efficient partner selection as well as other matching algorithms, yielding a trade‐off between stability and total energy consumption, but comparable symbol error rate performance and network sum rate. Copyright © 2016 John Wiley & Sons, Ltd.     

Virtual topologies for multicasting with multiple originators in WDM networks

In this paper, we consider the problem of multicasting with multiple originators in WDM optical networks. In this problem, we are given a set S of source nodes and a set D of destination nodes in a network. All source nodes are capable of providing data to any destination node. Our objective is to find a virtual topology in the WDM network which satisfies given constraints on available resources and is optimal with respect to minimizing the maximum hop distance. Although the corresponding decision problem is NP-complete in general, we give polynomial time algorithms for the cases of unidirectional paths and rings.     

Routing with topology aggregation in delay-bandwidth sensitive networks

Routing is a process of finding a network path from a source node to a destination node. The execution time and the memory requirement of a routing algorithm increase with the size of the network. In order to deal with the scalability problem, large networks are often structured hierarchically by grouping nodes into different domains. The internal topology of each domain is then aggregated into a simple topology that reflects the cost of routing across that domain. This process is called topology aggregation. For delay-bandwidth sensitive networks, traditional approaches represent the property of each link in the aggregated topology as a delay-bandwidth pair, which corresponds to a point on the delay-bandwidth plane. Since each link after aggregation may be the abstraction of many physical paths, a single delay-bandwidth pair results in significant information loss. The major contribution of this paper is a novel quality-of-service (QoS) parameter representation with a new aggregation algorithm and a QoS-aware routing protocol. Our QoS representation captures the state information about the network with much greater accuracy than the existing algorithms. Our simulation results show that the new approach achieves very good performance in terms of delay deviation, success ratio, and crankback ratio.     

On distributed power control in full duplex wireless networks

In this paper, we first consider the problem of distributed power control in a Full Duplex (FD) wireless network consisting of multiple pairs of nodes, within which each node needs to communicate with its corresponding node. We aim to find the optimal transmition power for the FD transmitters such that the network-wide capacity is maximized. Based on the high Signal-to-Interference-Plus-Noise Ratio (SINR) approximation and a more general approximation method for logarithm functions, we develop effective distributed power control algorithms with the dual decomposition approach. We also extend the work to the general FD network scenario, which can be decomposed into subproblems of isolated nodes, paths, and cycles. The corresponding power control problem is then be solved with the distributed algorithm. The proposed algorithms are validated with simulation studies.     

Algorithms for finding an optimal set of short disjoint paths in acommunication network

The motives for seeking a set of short disjoint paths in a communication network are explained. A sequentially constructed optimal set is defined. Three efficient algorithms, one that constructs an optimal set and two that construct approximations, are presented. One of the latter algorithms not only constructs a larger set of short disjoint paths than an iterated version of the standard Dijkstra algorithm, but also offers a major reduction in computation time for large networks     

A new approach for fast segment‐based protection in WDM mesh networks

We propose a new approach for developing segment‐based schemes for protection against single link/node failure in wavelength division multiplexing (WDM) mesh networks. In the proposed approach, every request is allocated a pair of link disjoint but most coupled primary and backup paths. Two paths are said to be most coupled if they share the maximum number of end nodes of some existing requests. Coupled paths reduce the total number of hops need to be traversed by a failure signal and, hence, potentially reduces the overall recovery time. We show that the problem of finding a pair of disjoint and most coupled paths is NP‐complete. Accordingly, we propose an efficient and fast protection algorithm called SPXP—Segment Pre‐Cross‐Connected Protection, to allocate disjoint and most coupled paths. The proposed SPXP algorithm reduces the recovery time by ensuring that backup resources are pre‐configured along each backup segment and, hence, is readily available upon a failure. Simulation results for different incremental traffic models and network topologies show that, for most cases, the proposed SPXP exhibits better performance in terms of blocking probability, resource usage, and recovery time compared with existing protection schemes. Copyright © 2010 John Wiley & Sons, Ltd.