An Overview of Quality-ofService Routing for the Next Generation High-Speed Networks: Problems and Solutions
---
paper_title: Routing subject to quality of service constraints in integrated communication networks

paper_content:

With increasingly diverse QOS requirements, it is impractical to continue to rely on conventional routing paradigms that emphasize the search for an optimal path based on a predetermined metric, or a particular function of multiple metrics. Modern routing strategies must not only be adaptive to network changes but also offer considerable economy of scope. We consider the problem of routing in networks subject to QOS constraints. After providing an overview of prior routing work, we define various QOS constraints. We present a call architecture that may be used for QOS matching and a connection management mechanism for network resource allocation. We discuss fallback routing, and review some existing routing frameworks. We also present a new rule-based, call-by-call source routing strategy for integrated communication networks. >
---
paper_title: Competitive routing of virtual circuits with unknown duration

paper_content:

In this paper we present a strategy to route unknown duration virtual circuits in a high-speed communication network. Previous work on virtual circuit routing concentrated on the case where the call duration is known in advance. We show that by allowing O(logn) reroutes per call, we can achieve O(logn) competitive ratio with respect to the maximum load (congestion) for the unknown duration case, where n is the number of nodes in the network. This is in contrast to the ?(n) lower bound on the competitive ratio for this case if no rerouting is allowed (Azar et al., 1992, Proc. 33rd IEEE Annual Symposium of Foundations of Computer Science, pp. 218?225). Our routing algorithm can be also applied in the context of machine load balancing of tasks with unknown duration. We present an algorithm that makes O(logn) reassignments per task and achieves O(logn) competitive ratio with respect to the load, where n is the number of parallel machines. For a special case of unit load tasks we design a constant competitive algorithm. The previously known algorithms that achieve up to polylogarithmic competitive ratio for load balancing of tasks with unknown duration dealt only with special cases of related machines case and unit-load tasks with restricted assignment (Azar et al., 1993, Proc. Workshop on Algorithms and Data Structures, pp. 119?130; Azar et al., 1992, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 203?210).
---
paper_title: On finding multi-constrained paths

paper_content:

New emerging distributed multimedia applications provide guaranteed end-to-end quality of service (QoS) and have stringent constraints on delay, delay-jitter, cost, etc. The task of QoS routing is to find a route in the network which has sufficient resources to satisfy the constraints. The delay-cost-constrained routing problem is NP-complete. We propose a heuristic algorithm for this problem. The idea is to first reduce the NP-complete problem to a simpler one which can be solved in polynomial time, and then solve the new problem by either an extended Dijkstra's algorithm or an extended Bellman-Ford algorithm. We prove the correctness of our algorithm by showing that a solution for the simpler problem must also be a solution for the original problem. The performance of the algorithm is studied by both theoretical analysis and simulation.
---
paper_title: Multicast Routing with End-to-End Delay and Delay Variation Constraints

paper_content:

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session.
---
paper_title: Multi-path routing combined with resource reservation

paper_content:

In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is an example of an algorithm that does this using a sequential crank-back mechanism. We suggest the implementation of resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different trade-offs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithms, including the PNNI crank-back, and exhibit higher network utilization and faster connection set-up time.
---
paper_title: A Scheme for Real-Time Channel Establishment in Wide-Area Networks

paper_content:

Multimedia communication involving digital audio and/or digital video has rather strict delay requirements. A real-time channel is defined as a simplex connection between a source and a destination characterized by parameters representing the performance requirements of the client. A study is made of the feasibility of providing real-time services on a packet-switched store-and-forward wide-area network with general topology. A description is given of a scheme for the establishment of channels with deterministic or statistical delay bounds, and the results of the simulation experiments run to evaluate it are presented. The results are judged encouraging: the approach satisfies the guarantees even in worst case situations, uses the network's resources to a fair extent, and efficiently handles channels with a variety of offered load and burstiness characteristics. Also, the packet transmission overhead is quite low, and the channel establishment overhead is small enough to be acceptable in most practical cases. >
---
paper_title: RSVP: a new resource ReSerVation Protocol

paper_content:

A resource reservation protocol (RSVP), a flexible and scalable receiver-oriented simplex protocol, is described. RSVP provides receiver-initiated reservations to accommodate heterogeneity among receivers as well as dynamic membership changes; separates the filters from the reservation, thus allowing channel changing behavior; supports a dynamic and robust multipoint-to-multipoint communication model by taking a soft-state approach in maintaining resource reservations; and decouples the reservation and routing functions. A simple network configuration with five hosts connected by seven point-to-point links and three switches is presented to illustrate how RSVP works. Related work and unresolved issues are discussed. >
---
paper_title: A Distributed Algorithm for Delay-Constrained Unicast Routing

paper_content:

We study the NP-hard delay-constrained least cost (DCLC) path problem. A solution to this problem is needed to provide real-time communication service to connection-oriented applications, such as video and voice. We propose a simple, distributed heuristic solution, called the delay-constrained unicast routing (DCUR) algorithm, DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of DCUR is O(|V|/sup 2/) messages, where |V| is the number of nodes. However, simulation results show that, on the average, DCUR requires much fewer messages. Therefore, DCUR scales well to large networks. We also use simulation to compare DCUR to the optimal algorithm, and to the least delay path algorithm. Our results show that DCUR's path costs are within 10% of those of the optimal solution.
---
paper_title: A distributed route-selection scheme for establishing real-time channels

paper_content:

To guarantee the delivery of real-time messages before their deadline, a real-time channel or connection must be established before the transmission of any real-time messages. During this channel establishment phase, one must first select a route between the source and destination of this channel and then reserve sufficient resources along this route so that the end-to-end delay over the selected route may not exceed the user-specified delay bound.
---
paper_title: Distributed quality-of-service routing in high-speed networks based on selective probing

paper_content:

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.
---
paper_title: Routing with end to end QoS guarantees in broadband networks

paper_content:

We consider routing schemes for connections with end to end delay requirements, and investigate several fundamental problems. First, we focus on networks which employ rate-based schedulers and hence map delay guarantees into nodal rate guarantees, as done with the guaranteed service class proposed for the Internet. We consider first the basic problem of identifying a feasible route for the connection, for which a straightforward, yet computationally costly solution exists. Accordingly, we establish several /spl epsiv/-optimal solutions that offer substantially lower computational complexity. We then consider the more general problem of optimizing the route choice in terms of balancing loads and accommodating multiple connections, for which we formulate and validate several optimal algorithms. We discuss the implementation of such schemes in the context of link-state and distance-vector protocols. Next, we consider the fundamental problem of constrained path optimization. This problem, typical of QoS routing, is NP-hard. While standard approximation methods exist, their complexity may often be prohibitive in terms of scalability. Such approximations do not make use of the particular properties of large-scale networks, such as the fact that the path selection process is typically presented with a hierarchical, aggregated topology. By exploiting the structure of such topologies, we obtain an /spl epsiv/-optimal algorithm for the constrained shortest path problem, which offers a substantial improvement in terms of scalability.
---
paper_title: Analysis and simulation of a fair queueing algorithm

paper_content:

We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.
---
paper_title: QoS routing in networks with uncertain parameters

paper_content:

This article considers the problem of routing connections with QoS requirements across networks, when the information available for making routing decisions is inaccurate. This uncertainty about the actual state of a network component arises naturally in a number of different environments, which are reviewed in the paper. The goal of the route selection process is then to identify a path that is most likely to satisfy the QoS requirements. For end to end delay guarantees, this problem is intractable. However we show that by decomposing the end-to-end constraint into local delay constraints, efficient and tractable solutions can be established. We first consider the simpler problem of decomposing the end-to-end constraint into local constraints, for a given path. We show that, for general distributions, this problem is also intractable. Nonetheless, by defining a certain class of probability distributions, which posses a certain convexity property, and restricting ourselves to that class, we are able to establish efficient and exact solutions. Moreover, we show that typical distributions would belong to that class. We then consider the general problem, of combined path optimization and delay decomposition. We present an efficient solution scheme for the above class of probability distributions. Our solution is similar to that of the restricted shortest-path problem, which renders itself to near-optimal approximations of polynomial complexity. We also show that yet simpler solutions exist in the special case of uniform distributions.
---
paper_title: On finding multi-constrained paths

paper_content:

New emerging distributed multimedia applications provide guaranteed end-to-end quality of service (QoS) and have stringent constraints on delay, delay-jitter, cost, etc. The task of QoS routing is to find a route in the network which has sufficient resources to satisfy the constraints. The delay-cost-constrained routing problem is NP-complete. We propose a heuristic algorithm for this problem. The idea is to first reduce the NP-complete problem to a simpler one which can be solved in polynomial time, and then solve the new problem by either an extended Dijkstra's algorithm or an extended Bellman-Ford algorithm. We prove the correctness of our algorithm by showing that a solution for the simpler problem must also be a solution for the original problem. The performance of the algorithm is studied by both theoretical analysis and simulation.
---
paper_title: A distributed route-selection scheme for establishing real-time channels

paper_content:

To guarantee the delivery of real-time messages before their deadline, a real-time channel or connection must be established before the transmission of any real-time messages. During this channel establishment phase, one must first select a route between the source and destination of this channel and then reserve sufficient resources along this route so that the end-to-end delay over the selected route may not exceed the user-specified delay bound.
---
paper_title: Competitive routing of virtual circuits with unknown duration

paper_content:

In this paper we present a strategy to route unknown duration virtual circuits in a high-speed communication network. Previous work on virtual circuit routing concentrated on the case where the call duration is known in advance. We show that by allowing O(logn) reroutes per call, we can achieve O(logn) competitive ratio with respect to the maximum load (congestion) for the unknown duration case, where n is the number of nodes in the network. This is in contrast to the ?(n) lower bound on the competitive ratio for this case if no rerouting is allowed (Azar et al., 1992, Proc. 33rd IEEE Annual Symposium of Foundations of Computer Science, pp. 218?225). Our routing algorithm can be also applied in the context of machine load balancing of tasks with unknown duration. We present an algorithm that makes O(logn) reassignments per task and achieves O(logn) competitive ratio with respect to the load, where n is the number of parallel machines. For a special case of unit load tasks we design a constant competitive algorithm. The previously known algorithms that achieve up to polylogarithmic competitive ratio for load balancing of tasks with unknown duration dealt only with special cases of related machines case and unit-load tasks with restricted assignment (Azar et al., 1993, Proc. Workshop on Algorithms and Data Structures, pp. 119?130; Azar et al., 1992, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 203?210).
---
paper_title: Multicast Routing for Multimedia Communication

paper_content:

The authors present heuristics for multicast tree construction for communication that depends on: bounded end-to-end delay along the paths from source to each destination and minimum cost of the multicast tree, where edge cost and edge delay can be independent metrics. The problem of computing such a constrained multicast tree is NP-complete. It is shown that the heuristics demonstrate good average case behavior in terms of cost, as determined by simulations on a large number of graphs. >
---
paper_title: A source-based algorithm for delay-constrained minimum-cost multicasting

paper_content:

A new heuristic algorithm is presented for constructing minimum-cost multicast trees with delay constraints. The new algorithm can set variable delay bounds on destinations and handles two variants of the network cost optimization goal: one minimizing the total cost (total bandwidth utilization) of the tree, and another minimizing the maximal link cost (the most congested link). Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible search optimization method which starts with the minimum-delay tree and monotonically decreases the cost by iterative improvement of the delay-bounded tree. The optimality of the costs of the delay-bounded trees obtained with the new algorithm is analyzed by simulation. Depending on how tight the delay bounds are, the costs of the multicast trees obtained with the new algorithm are shown to be very close to the costs of the trees obtained by the Kou, Markowsky and Berman's algorithm (1981).
---
paper_title: Multicast Routing with End-to-End Delay and Delay Variation Constraints

paper_content:

We study the problem or constructing multicast trees to meet the quality of service requirements of real-time interactive applications operating in high-speed packet-switched environments. In particular, we assume that multicast communication depends on: (1) bounded delay along the paths from the source to each destination and (2) bounded variation among the delays along these paths. We first establish that the problem of determining such a constrained tree is NP-complete. We then present a heuristic that demonstrates good average case behavior in terms of the maximum interdestination delay variation. The heuristic achieves its best performance under conditions typical of multicast scenarios in high speed networks. We also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session.
---
paper_title: Competitive routing of virtual circuits with unknown duration

paper_content:

In this paper we present a strategy to route unknown duration virtual circuits in a high-speed communication network. Previous work on virtual circuit routing concentrated on the case where the call duration is known in advance. We show that by allowing O(logn) reroutes per call, we can achieve O(logn) competitive ratio with respect to the maximum load (congestion) for the unknown duration case, where n is the number of nodes in the network. This is in contrast to the ?(n) lower bound on the competitive ratio for this case if no rerouting is allowed (Azar et al., 1992, Proc. 33rd IEEE Annual Symposium of Foundations of Computer Science, pp. 218?225). Our routing algorithm can be also applied in the context of machine load balancing of tasks with unknown duration. We present an algorithm that makes O(logn) reassignments per task and achieves O(logn) competitive ratio with respect to the load, where n is the number of parallel machines. For a special case of unit load tasks we design a constant competitive algorithm. The previously known algorithms that achieve up to polylogarithmic competitive ratio for load balancing of tasks with unknown duration dealt only with special cases of related machines case and unit-load tasks with restricted assignment (Azar et al., 1993, Proc. Workshop on Algorithms and Data Structures, pp. 119?130; Azar et al., 1992, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 203?210).
---
paper_title: On finding multi-constrained paths

paper_content:

New emerging distributed multimedia applications provide guaranteed end-to-end quality of service (QoS) and have stringent constraints on delay, delay-jitter, cost, etc. The task of QoS routing is to find a route in the network which has sufficient resources to satisfy the constraints. The delay-cost-constrained routing problem is NP-complete. We propose a heuristic algorithm for this problem. The idea is to first reduce the NP-complete problem to a simpler one which can be solved in polynomial time, and then solve the new problem by either an extended Dijkstra's algorithm or an extended Bellman-Ford algorithm. We prove the correctness of our algorithm by showing that a solution for the simpler problem must also be a solution for the original problem. The performance of the algorithm is studied by both theoretical analysis and simulation.
---
paper_title: A route pre-computation algorithm for integrated services networks

paper_content:

We provide an algorithm for computing best paths on a graph where edges have a multidimensional cost, one dimension representing delay, the others representing available capacity. Best paths are those which guarantee maximum capacity with least possible delay. The complexity of the algorithm is of the order ofO(V3) in the bidimensional case, for a graph withV vertices. The results can be used for routing connections with guaranteed capacity in a communication network.
---
paper_title: Competitive Routing of Virtual Circuits in ATM networks

paper_content:

Classical routing and admission control strategies achieve provably good performance by relying on an assumption that the virtual circuits arrival pattern can be described by some a priori known probabilistic model. A new on-line routing framework, based on the notion of competitive analysis, was proposed. This framework is geared toward design of strategies that have provably good performance even in the case where there are no statistical assumptions on the arrival pattern and parameters of the virtual circuits. The on-line strategies motivated by this framework are quite different from the min-hop and reservation-based strategies. This paper surveys the on-line routing framework, the proposed routing and admission control strategies, and discusses some of the implementation issues. >
---
paper_title: Competitive routing of virtual circuits with unknown duration

paper_content:

In this paper we present a strategy to route unknown duration virtual circuits in a high-speed communication network. Previous work on virtual circuit routing concentrated on the case where the call duration is known in advance. We show that by allowing O(logn) reroutes per call, we can achieve O(logn) competitive ratio with respect to the maximum load (congestion) for the unknown duration case, where n is the number of nodes in the network. This is in contrast to the ?(n) lower bound on the competitive ratio for this case if no rerouting is allowed (Azar et al., 1992, Proc. 33rd IEEE Annual Symposium of Foundations of Computer Science, pp. 218?225). Our routing algorithm can be also applied in the context of machine load balancing of tasks with unknown duration. We present an algorithm that makes O(logn) reassignments per task and achieves O(logn) competitive ratio with respect to the load, where n is the number of parallel machines. For a special case of unit load tasks we design a constant competitive algorithm. The previously known algorithms that achieve up to polylogarithmic competitive ratio for load balancing of tasks with unknown duration dealt only with special cases of related machines case and unit-load tasks with restricted assignment (Azar et al., 1993, Proc. Workshop on Algorithms and Data Structures, pp. 119?130; Azar et al., 1992, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 203?210).
---
paper_title: Routing virtual circuits with timing requirements in virtual path based ATM networks

paper_content:

Real-time communication with performance guarantees is expected to become an important feature of future computer networks. Given an ATM network topology, its virtual path (VP) layout, and its traffic demands, we consider in this paper the problem of selecting for each virtual circuit (VC) with timing requirements a route (i.e., a sequence of VPs) along which sufficient resources are available to meet the user-specified end-to-end delay requirements. Our objective is to (i) provide the timing guarantee for the VC, while not jeopardizing the QoS guarantees to other existing VCs. We adopt the real-time channel model to characterize the traffic characteristics and the timing requirements of a VC. We then propose a distributed VC routing scheme based on the distributed Bellman-Ford algorithm to identify an "appropriate" route through the network. By "appropriate", we mean that the route traverses a minimum number of VPs among all possible routes that have sufficient resources over to fulfill the end-to-end timing requirement of the VC. To ensure that there are sufficient bandwidths over all the VPs along the selected route, we incorporate in our proposed scheme a priority assignment method to calculate the minimum worst-case traversal time which messages of a VC will experience on a VP along which the VC is routed. We also comment on the performance of, and the message overhead incurred in the proposed scheme.
---
paper_title: Distributed quality-of-service routing in high-speed networks based on selective probing

paper_content:

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.
---
paper_title: Multicast routing in datagram internetworks and extended LANs

paper_content:

Multicasting, the transmission of a packet to a group of hosts, is an important service for improving the efficiency and robustness of distributed systems and applications. Although multicast capability is available and widely used in local area networks, when those LANs are interconnected by store-and-forward routers, the multicast service is usually not offered across the resulting internetwork . To address this limitation, we specify extensions to two common internetwork routing algorithms—distance-vector routing and link-state routing—to support low-delay datagram multicasting beyond a single LAN. We also describe modifications to the single-spanning-tree routing algorithm commonly used by link-layer bridges, to reduce the costs of multicasting in large extended LANs. Finally, we discuss how the use of multicast scope control and hierarchical multicast routing allows the multicast service to scale up to large internetworks.
---
paper_title: Shortest connection networks and some generalizations

paper_content:

The basic problem considered is that of interconnecting a given set of terminals with a shortest possible network of direct links. Simple and practical procedures are given for solving this problem both graphically and computationally. It develops that these procedures also provide solutions for a much broader class of problems, containing other examples of practical interest.
---
paper_title: Multicast Routing for Multimedia Communication

paper_content:

The authors present heuristics for multicast tree construction for communication that depends on: bounded end-to-end delay along the paths from source to each destination and minimum cost of the multicast tree, where edge cost and edge delay can be independent metrics. The problem of computing such a constrained multicast tree is NP-complete. It is shown that the heuristics demonstrate good average case behavior in terms of cost, as determined by simulations on a large number of graphs. >
---
paper_title: A source-based algorithm for delay-constrained minimum-cost multicasting

paper_content:

A new heuristic algorithm is presented for constructing minimum-cost multicast trees with delay constraints. The new algorithm can set variable delay bounds on destinations and handles two variants of the network cost optimization goal: one minimizing the total cost (total bandwidth utilization) of the tree, and another minimizing the maximal link cost (the most congested link). Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible search optimization method which starts with the minimum-delay tree and monotonically decreases the cost by iterative improvement of the delay-bounded tree. The optimality of the costs of the delay-bounded trees obtained with the new algorithm is analyzed by simulation. Depending on how tight the delay bounds are, the costs of the multicast trees obtained with the new algorithm are shown to be very close to the costs of the trees obtained by the Kou, Markowsky and Berman's algorithm (1981).
---
paper_title: Distributed quality-of-service routing in high-speed networks based on selective probing

paper_content:

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.
---
paper_title: QoSMIC: quality of service sensitive multicast Internet protocol

paper_content:

In this paper, we present, QoSMIC, a multicast protocol for the Internet that supports QoS-sensitive routing, and minimizes the importance of a priori configuration decisions (such as core selection). The protocol is resource-efficient, robust, flexible, and scalable. In addition, our protocol is provably loop-free.Our protocol starts with a resources-saving tree (Shared Tree) and individual receivers switch to a QoS-competitive tree (Source-Based Tree) when necessary. In both trees, the new destination is able to choose the most promising among several paths. An innovation is that we use dynamic routing information without relying on a link state exchange protocol to provide it. Our protocol limits the effect of pre-configuration decisions drastically, by separating the management from the data transfer functions; administrative routers are not necessarily part of the tree. This separation increases the robustness, and flexibility of the protocol. Furthermore, QoSMIC is able to adapt dynamically to the conditions of the network.The QoSMIC protocol introduces several new ideas that make it more flexible than other protocols proposed to date. In fact, many of the other protocols, (such as YAM, PIMSM, BGMP, CBT) can be seen as special cases of QoSMIC. This paper presents the motivation behind, and the design of QoSMIC, and provides both analytical and experimental results to support our claims.
---
paper_title: Distributed quality-of-service routing in high-speed networks based on selective probing

paper_content:

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.
---
paper_title: Building shared trees using a one-to-many joining mechanism

paper_content:

This paper presents a new approach for building shared trees which have the capability of providing multiple routes from the joining node onto an existing tree. The approach follows a design parameter of CBT and PIM in that it operates independently of any unicast routing protocol. However, a paradigm shift is introduced such that trees are built in an on-demand basis through the use of a one-to-many joining mechanism. In addition, the paper presents optimisations of the new mechanism to help constrain its impact in the case where many receivers exist for a given multicast group.
---
paper_title: QoS routing in networks with uncertain parameters

paper_content:

This article considers the problem of routing connections with QoS requirements across networks, when the information available for making routing decisions is inaccurate. This uncertainty about the actual state of a network component arises naturally in a number of different environments, which are reviewed in the paper. The goal of the route selection process is then to identify a path that is most likely to satisfy the QoS requirements. For end to end delay guarantees, this problem is intractable. However we show that by decomposing the end-to-end constraint into local delay constraints, efficient and tractable solutions can be established. We first consider the simpler problem of decomposing the end-to-end constraint into local constraints, for a given path. We show that, for general distributions, this problem is also intractable. Nonetheless, by defining a certain class of probability distributions, which posses a certain convexity property, and restricting ourselves to that class, we are able to establish efficient and exact solutions. Moreover, we show that typical distributions would belong to that class. We then consider the general problem, of combined path optimization and delay decomposition. We present an efficient solution scheme for the above class of probability distributions. Our solution is similar to that of the restricted shortest-path problem, which renders itself to near-optimal approximations of polynomial complexity. We also show that yet simpler solutions exist in the special case of uniform distributions.
---
paper_title: Distributed quality-of-service routing in high-speed networks based on selective probing

paper_content:

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.
---
paper_title: Multi-path routing combined with resource reservation

paper_content:

In high-speed networks it is desirable to interleave routing and resource (such as bandwidth) reservation. The PNNI standard for private ATM networks is an example of an algorithm that does this using a sequential crank-back mechanism. We suggest the implementation of resource reservation along several routes in parallel. We present an analytical model that demonstrates that when there are several routes to the destination it pays to attempt reservation along more than a single route. Following this analytic observation, we present a family of algorithms that route and reserve resources along parallel subroutes. The algorithms of the family represent different trade-offs between the speed and the quality of the established route. The presented algorithms are simulated against several legacy algorithms, including the PNNI crank-back, and exhibit higher network utilization and faster connection set-up time.
---
paper_title: QoS routing via multiple paths using bandwidth reservation

paper_content:

The authors address the problem of computing a multipath, consisting of possibly overlapping paths, to transmit data from the source node s to the destination node d over a computer network while ensuring deterministic bounds on end-to-end delay or delivery rate.They consider two generic routing problems within the framework wherein bandwidth can be reserved, and guaranteed, once reserved, on various links of the communication network. The first problem requires that a message of finite length be transmitted from s to d within {tau} units of time. The second problem requires that a sequential message of r units be transmitted at a rate of {eta} such that maximum time difference between two units that are received out of order is no more than q. They propose a polynomial-time algorithm to the first problem based on an adaptation of the classical Ford-Fulkerson`s method. They present simulation results to illustrate the applicability of the proposed algorithm. They show the second problem to be NP-complete, and propose a polynomial-time approximately solution.
---
paper_title: A distributed route-selection scheme for establishing real-time channels

paper_content:

To guarantee the delivery of real-time messages before their deadline, a real-time channel or connection must be established before the transmission of any real-time messages. During this channel establishment phase, one must first select a route between the source and destination of this channel and then reserve sufficient resources along this route so that the end-to-end delay over the selected route may not exceed the user-specified delay bound.
---
paper_title: Simulation study of the capacity effects of dispersity routing for fault tolerant realtime channels

paper_content:

The paper presents a simulation study of the use of dispersity routing to provide fault tolerance on top of a connection oriented realtime service such as that provided by the Tenet scheme. A framework to study the dispersity schemes is presented. The simulations show that the dispersity schemes, by dividing the connection's traffic among multiple paths in the network, have a beneficent effect on the capacity of the network. Thus, for certain classes of dispersity schemes, we obtain a small improvement in fault tolerance as well as an improvement in the number of connections that the network can support. For other classes of dispersity schemes, greater improvement in service may be purchased at the cost of decrease in capacity. The paper explores the tradeoffs available through exhaustive simulations. We conclude that dispersity routing is a flexible approach to increasing the fault tolerance of realtime connections, which can provide a range of improvements in service with a corresponding range of costs.
---
paper_title: Distributed quality-of-service routing in high-speed networks based on selective probing

paper_content:

We propose an integrated QoS routing framework based on selective probing for high-speed packet-switching networks. The framework is fully distributed and depends only on the local state maintained at every individual node. By using controlled diffusion computations, the framework captures the common messaging and computational structure of distributed QoS routing, and allows an efficient implementation due to its simplicity. Different distributed routing algorithms (DRAs) can be quickly developed by specifying only a few well-defined constraint-dependent parameters within the framework. Our simulation shows that the overhead of the proposed algorithms is stable and modest.
---

Title: An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions

Section 1: Introduction
Description 1: Introduce the need for Quality-of-Service routing in next-generation high-speed networks and outline the paper's focus.

Section 2: Maintenance of State Information
Description 2: Discuss the tasks involved in routing, such as maintaining and updating state information, and explain the concepts of local and global state.

Section 3: Routing Problems
Description 3: Define and differentiate between unicast and multicast routing problems, and introduce the sub-classes within these two major categories.

Section 4: Routing Strategies
Description 4: Describe various routing strategies including source routing, distributed routing, and hierarchical routing, and discuss their respective strengths and weaknesses.

Section 5: Unicast Routing Algorithms
Description 5: Survey existing unicast routing algorithms, presenting specific algorithms, their methodologies, and comparative analysis of their pros and cons.

Section 6: Distributed Routing Algorithms
Description 6: Present distributed routing algorithms, including their specific methodologies and the analysis of their distinctive properties.

Section 7: Hierarchical Routing Algorithms
Description 7: Describe hierarchical routing protocols, focusing on examples like PNNI, and illustrate the routing processes within hierarchical networks.

Section 8: Multicast Routing Algorithms
Description 8: Examine multicast routing algorithms, focusing on problems such as bandwidth-constrained and delay-constrained multicast routing and the heuristic solutions proposed for these NP-complete problems.

Section 9: QoS Routing and Other Network Components
Description 9: Explore how QoS routing interacts with other network components like resource reservation, admission control, and QoS negotiation.

Section 10: Future Directions
Description 10: Identify and discuss potential future research areas and directions for improving QoS routing, handling imprecise state information, and integrating with best-effort traffic.

Section 11: Summary
Description 11: Summarize the key findings and insights of the paper, emphasizing the importance of efficient QoS routing in the future high-speed networks.