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.     

Evaluation of multicast routing algorithms for real-timecommunication on high-speed networks

Multicast (MC) routing algorithms capable of satisfying the quality of service (QoS) requirements of real-time applications will be essential for future high-speed networks. We compare the performance of all of the important MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC trees it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of real-time applications in wide-area networks. Simulations also reveal that one of the unconstrained algorithms, reverse path multicasting (RPM), is quite inefficient when applied to asymmetric networks. We study how combining routing with resource reservation and admission control improves the RPM's efficiency in managing the network resources. The performance of one semiconstrained heuristic, MSC, three constrained Steiner tree (CST) heuristics, Kompella, Pasquale, and Polyzos (1992), constrained adaptive ordering (CAO), and bounded shortest multicast algorithm (BSMA), and one constrained shortest path tree (CSPT) heuristic, the constrained Dijkstra heuristic (CDKS) are also studied. Simulations show that the semiconstrained and constrained heuristics are capable of successfully constructing MC trees which satisfy the QoS requirements of real-time traffic. However, the cost performance of the heuristics varies. The BSMA's MC trees are lower in cost than all other constrained heuristics. Finally, we compare the execution times of all algorithms, unconstrained, semiconstrained, and constrained     

A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks

Due to the recent developments in wireless technology and electronics, it is feasible to develop pervasive algorithms for satellite environments. Multi-Layered Satellite Networks (MLSNs) that consist of low earth orbit and medium earth orbit satellites are becoming increasingly important since they have higher coverage and better service than single-layered satellite networks. One of the challenges in MLSNs is the development of specialized and efficient routing algorithms. In this paper, we improved the virtual topology strategy and import heuristic algorithm to satisfy the QoS requirements of the MLSN users. The QoS requirements include end to end delay; link utilization, bandwidth, and package loss rate are mainly focused in this paper. To satisfy the QoS requirements is a multi-parameter optimization problem, and it is convinced as a Non-deterministic Polynomial Complete problem already. As a solution, three typical heuristic algorithms—Ant Colony Algorithm, Taboo Search Algorithm and Genetic Algorithm are applied in the routing scheme in order to reduce package loss, link congestion and call blocking. Simulation results show that heuristic routing algorithm can provide more QoS guarantees than shortest path first algorithm on package loss rate, link congestion and call blocking.     

两约束路由问题的近似解法

首先回顾了一些重要的QOS路由算法，然后对关于两约束路由问题(BCP,bi—constraint path problem)的线性搜索算法进行了数学分析，确定了搜索因子的范围和最佳搜索因子的值。基于以上分析，我们给出了BCP和单约束最短路径问题(RSP,restricted shortest path problem)的近似算法，并对算法性能进行了分析；最后，本文研究了采用非线性链路代价函数求解BCP。测试结果表明本文提出的算法是求解BCP和RSP的有效算法。     

Restorable dynamic quality of service routing

The focus of quality-of-service routing has been on the routing of a single path satisfying specified QoS constraints. Upon failure of a node or link on the path, a new path satisfying the constraints has to be established. However, resources needed to satisfy the QoS requirements are not guaranteed to be available at the rerouting instant, so QoS is not guaranteed upon failure. Restorable QoS routing, where active and backup paths must be simultaneously set up, has been previously studied. This is mostly motivated by the incorporation of mechanisms to establish QoS guaranteed paths with failure protection in multiprotocol label switching networks. This article describes some previously developed algorithms for dynamic routing of restorable QoS guaranteed paths     

A novel two-step approach to restorable dynamic QoS routing

Aiming at minimizing the combined bandwidth cost of a pair of disjoint active and backup paths, a popular approach to designing restorable dynamic quality of service (QoS) routing schemes is based on the integer linear programming (ILP) formulation. Owing to the very different natures of active and backup paths, we found this approach problematic. In this paper, we propose an alternative approach, called two-step restorable QoS routing. In the first step, an active path is found using the widest shortest path (WSP) routing. In the second step, the corresponding backup path is determined using one of the three variants of shortest widest path (SWP) routing: basic SWP, approximate SWP or composite SWP. Combining the two steps, three novel two-step routing algorithms, denoted by SBW, SAW, and SCW, are obtained. Comparing with the best known algorithms, we show that our two-step routing approach yields noticeably lower call blocking probability, shorter active-path length, and additional flexibility of adjusting backup-path length (depending on the SWP variant adopted). Besides, our two-step routing approach gives a much shorter running time than the ILP approach, which makes it more suitable for dynamic routing.     

基于蚂蚁算法的QoS路由调度方法

为了有效地解决QoS受限路由问题,本文提出了一种新颖的具有全局优化能力的蚂蚁算法,它是基于蚂蚁具有找到蚁巢与食物之间的最短路径原理工作的。 仿真实验表明,该方法能够有效地解决QoS受限路由问题。     

Heuristic algorithms for multiconstrained quality-of-servicerouting

Multiconstrained quality-of-service (QoS) routing deals with finding routes that satisfy multiple independent QoS constraints. This problem is NP-hard. Two heuristics, the limited granularity heuristic and the limited path heuristic, are investigated. Both heuristics extend the Bellman-Ford shortest path algorithm and solve general k-constrained QoS routing problems. Analytical and simulation studies are conducted to compare the time/space requirements of the heuristics and the effectiveness of the heuristics in finding paths that satisfy the QoS constraints. The major results of this paper are the following. For an N-nodes and E-edges network with k (a small constant) independent QoS constraints, the limited granularity heuristic must maintain a table of size O(|N|^k-1) in each node to be effective, which results in a time complexity of O(|N|^k|E|), while the limited path heuristic can achieve very high performance by maintaining O(|N|² lg(|N|)) entries in each node. These results indicate that the limited path heuristic is relatively insensitive to the number of constraints and is superior to the limited granularity heuristic in solving k-constrained QoS routing problems when k>3     

Algorithms for computing QoS paths with restoration

There is a growing interest among service providers to offer new services with Quality of Service (QoS) guarantees that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both bottleneck QoS constraints, such as bandwidth, and additive QoS constraints, such as delay and jitter. This is the first study to provide a rigorous solution, with proven guarantees, to the combined problem of computing QoS paths with restoration. It turns out that the widely used approach of disjoint primary and restoration paths is not an optimal strategy. Hence, the proposed algorithms construct a restoration topology , i.e., a set of bridges, each bridge protecting a portion of the primary QoS path. This approach guarantees to find a restoration topology with low cost when one exists.     

On the effectiveness of alternative paths in QoS routing

We propose a routing strategy in which connection requests with specific bandwidth demands can be assigned to one of several alternative paths connecting the source to the destination. The primary goal of this multiple‐path approach is to compensate for the inaccuracy of the knowledge available to routing nodes, caused by the limited frequency of link state (LS) information exchanges. We introduce a collection of K‐shortest path routing schemes and investigate their performance under a variety of traffic conditions and network configurations. We subsequently demonstrate that K‐shortest path routing offers a lower blocking probability in all scenarios and more balanced link utilization than other routing methods discussed in the literature. With our approach, it is possible to reduce the frequency of link state exchanges, and the incurred bandwidth overhead, without compromising the overall performance of the network. Based on the proposed routing scheme, we investigate different link state dissemination algorithms, which are aimed at reducing the communication overhead by prioritizing the scope and differentiating the qualitative content of LS update messages. Copyright © 2004 John Wiley & Sons, Ltd.     

QoS约束的链路故障多备份路径恢复算法

链路故障的恢复,不仅仅是选择一条连通的备份路径问题,还应考虑网络业务故障恢复过程中的QoS需求。针对此问题,该文基于多备份路径策略,构建概率关联故障模型和重路由流量丢弃量优化目标。并基于该优化目标,以业务的QoS需求为约束,建立故障恢复问题的数学模型,提出一种QoS约束的链路故障多备份路径恢复算法。该算法构建单条备份路径时,以最大程度地减少重路由流量丢弃为目标,并采用改进的QoS约束的k最短路径法进行拼接,且给与高优先级链路更多的保护资源。此外还证明了算法的正确性并分析了时间空间复杂度。在NS2环境下的仿真结果表明,该算法显著提升了链路故障恢复率和重路由流量QoS满足率,且QoS约束条件越强,相较于其它算法优势越明显。     

Multiple QoS constrained routing with inaccurate state information

An algorithm for multiple quality of service (QoS) constrained routing with inaccurate link state information is described. It incorporates knowledge of the inaccuracy in a link parameter known as the `certainty probability', which is used in the path selection process. Simulation results show that the routing performance of the proposed method (in terms of the call acceptance ratio) is better than that of existing algorithms that do not consider the inaccuracy of state information     

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.     

Performance Analysis of an Adaptive Link Status Update Scheme Based on Link‐Usage Statistics for QoS Routing

In the global Internet, a constraint‐based routing algorithm performs the function of selecting a routing path while satisfying some given constraints rather than selecting the shortest path based on physical topology. It is necessary for constraint‐based routing to disseminate and update link state information. The triggering policy of link state updates significantly affects the volume of update traffic and the quality of services (QoS). In this letter, we propose an adaptive triggering policy based on link‐usage statistics in order to reduce the volume of link state update traffic without deterioration of QoS. Also, we evaluate the performance of the proposed policy via simulations.     

GPSPA: a new adaptive algorithm for maintaining shortest path routing trees in stochastic networks

This paper presents a new efficient solution to the Dynamic Shortest Path Routing Problem, using the principles of Generalized Pursuit Learning. It proposes an efficient algorithm for maintaining shortest path routing trees in networks that undergo stochastic updates in their structure. It involves finding the shortest path in a stochastic network, where there are continuous probabilistically based updates in link‐costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are inefficient. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The proposed algorithm, referred to as the Generalized Pursuit Shortest Path Algorithm (GPSPA), will be very useful in this regard, because after convergence, it seems to be the best algorithm to‐date for this purpose. Indeed, it has the advantage that it can be used to find the shortest path within the ‘statistical’ average network, which converges irrespective of whether there are new changes in link‐costs or not. Existing algorithms are not characterized by such a behaviour inasmuch as they would recalculate the affected shortest paths after each link‐cost update. The algorithm has been rigorously evaluated experimentally, and it has been found to be a few orders of magnitude superior to the algorithms available in the literature. Copyright © 2004 John Wiley & Sons, Ltd.     

无线Mesh网络可靠多播路由

无线Mesh网络多播路由是无线路由必须解决的关键技术。部分研究者对网络资源和服务质量（QoS）进行研究,提出了建立最短路径树、最小开销树、负载感知、信道分配多播等多播算法;有的算法考虑链路可靠性,建立备用路径。将结合网络资源和可靠性对多播路由算法进行研究,提出了建立可靠多播树（RT,Reliable Tree）的多播路由算法：可靠多播树是一个多树结构,由一棵首选多播树和一棵多径树构成,多径树提供可靠多路径,以提高网络吞吐量。     

QoS routing through alternate paths in wireless ad hoc networks

Quality of service (QoS) routing plays an important role in QoS provisioning for mobile ad hoc networks. This work studies the issue of route selection subject to QoS constraint(s). Our method searches for alternate routes with satisfied QoS requirement(s) to accommodate each communication request when the shortest path connecting the source–destination pair of the request is not qualified. In order to effectively reduce protocol overhead, a directed search mechanism is designed to limit the breadth of the searching scope, which aims at achieving a graceful tradeoff between the success probability in QoS route acquisition and communication overhead. Efficient hop‐by‐hop routing protocols are designed for route selection subject to delay and bandwidth constraint, respectively. Simulation results show that the designed protocols can achieve high performance in acquiring QoS paths and in efficient resource utilization with low control overhead. Copyright © 2004 John Wiley & Sons, Ltd.     

Computing shortest paths for any number of hops

In this paper, we introduce and investigate a "new" path optimization problem that we denote the all hops optimal path (AHOP) problem. The problem involves identifying, for all hop counts, the optimal, i.e., minimum weight, path(s) between a given source and destination(s). The AHOP problem arises naturally in the context of quality-of-service (QoS) routing in networks, where routes (paths) need to be computed that provide services guarantees, e.g., delay or bandwidth, at the minimum possible "cost" (amount of resources required) to the network. Because service guarantees are typically provided through some form of resource allocation on the path (links) computed for a new request, the hop count, which captures the number of links over which resources are allocated, is a commonly used cost measure. As a result, a standard approach for determining the cheapest path available that meets a desired level of service guarantees is to compute a minimum hop shortest (optimal) path. Furthermore, for efficiency purposes, it is desirable to precompute such optimal minimum hop paths for all possible service requests. Providing this information gives rise to solving the AHOP problem. The paper's contributions are to investigate the computational complexity of solving the AHOP problem for two of the most prevalent cost functions (path weights) in networks, namely, additive and bottleneck weights. In particular, we establish that a solution based on the Bellman-Ford algorithm is optimal for additive weights, but show that this does not hold for bottleneck weights for which a lower complexity solution exists.     

一种新的基于ACSA的ad hoc多径QoS选路方法

ad hoc网络中基于蚁群系统算法（Ant Colony System Algorithms,ACSA）的路由协议已经被广泛地研究,但其中的大部分本质上都属于单径路由协议,使得源宿之间最短路径上的主机负担加重。另一方面,由于引入了蚂蚁的正反馈机制,使得协议本身比较差的鲁棒性受到进一步的削弱。多径路由能够更好地支持QoS。将ACSA和链路不相交的多径路由结合起来以解决上述问题,提出的基于ACSA的多径QoS选路方法建立和利用多条链路不相交路径来并发发送数据,并且采用信息素来分散通信流量,因此能够适应网络的动态变化和更好地支持QoS。仿真结果表明该方法要优于其他相关的算法。     

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.