Multicast routing with Quality-of-Service (QoS) guarantees is the key to efficient content distribution and sharing. Developing QoS-aware multicast routing algorithm is an important open topic. This paper investigates QoS-aware multicast routing problem with K constraints where K > 2. The contributions made in this paper include a heuristic that employs the concept of nonlinear combination to extend the existing well-known algorithm for fast computation of a QoS multicast tree, and a Fully Polynomial Time Approximation Scheme (FPTAS) to approximate a multicast routing tree with QoS guarantees. The theoretical analyses and simulations conducted on both algorithms show that the algorithms developed in this paper are general and flexible, thus are applicable to the various networking systems.

In order to find paths guaranteed by Quality of Service (QoS), the link state database (LSDB), containing QoS constraint information, and residing in routers, needs to be well managed. However, there is a trade-off between the exact reflection of the current link status and the update cost to calculate and maintain this data. In order to perfectly reflect the current link state, each router immediately notifies its neighbors whenever link state information changes. However, this may degrade the performance of the router. On the other hand, if current link state information is not updated routinely, route setup requests may be rejected because of the discrepancy between the current link state information and the previously updated link state information in the LSDB. Therefore, we need link state update (LSU) algorithms making it possible to appropriately update the LSDB. In addition, to facilitate implementation, they also should have low-complexity and must be adaptive under the variation of network conditions. In this paper, we propose an enhanced simple-adaptive (ESA) LSU algorithm, to reduce the generation of LSU messages while maintaining simplicity and adaptivity. The performance of this algorithm is compared with five existing algorithms by rigorous simulations. The comparision shows that the ESU algorithm can adapt to changes in network conditions and its performance is superior to existing LSU algorithms.

This paper addresses the problem of inter-domain QoS routing with Service Level Agreements (SLA) for data transport between peering domains, using virtual-trunk type aggregates. The problem is formally stated and formulated in Integer Linear Programming. As a practical solution, we define the QoS_INFO extension to the BGP routing protocol, conveying three different QoS metrics (light load delay, assigned bandwidth and a congestion alarm), and a path selection algorithm using a combination of these metrics. We present simulation results of QoS_INFO, standard BGP, and BGP with the QoS_NLRI extension, and compare them with the optimal route set provided by the ILP formulation. The results show that our proposal yields better QoS than standard BGP or BGP with the QoS_NLRI extension, since it is able to efficiently avoid congested paths, and that the impact of QoS_INFO in route stability is relatively low.

In future high-speed networks, provision of diverse multimedia services with strict quality-of-service (QoS) requirements, such as bandwidth, delay and so on, is desired. QoS routing is a possible solution to handle these services. Generally, a path selection for QoS routing is formulated as a shortest path problem subject to multiple constraints. However, it is known to be NP-complete when more than one QoS constraint is imposed. As a result, many heuristic algorithms have been proposed so far. The authors proposed a path selection algorithm Fallback+ for QoS routing, which focuses not only on the path selection with multiple constraints but also on the efficient use of network resources. This paper proposes an enhanced version of Fallback+, named Enhanced Fallback+, where in a shrewd way, it keeps tentative paths produced in the conventional Fallback algorithm with Dijkstra's algorithm. Simulation experiments prove the excellent performance of Enhanced Fallback+, compared with the original Fallback+ and other existing path selection algorithms.

In this paper, we propose a modeling framework for supporting QoS routing in mobile ad-hoc wireless networks. The basic motivations of the proposed modeling approach stem from the commonality observed in the location uncertainty in mobile ad-hoc wireless networks and the concept of entropy. These common characteristics have motivated our work in developing an analytical modeling framework using entropy concepts and utilizing mobility information as the corresponding variable features, in order to support and evaluate route stability in self-organizing mobile ad-hoc wireless networks. The corresponding methodology, results and observations can be used by the routing protocols to select the most stable route between a source and a destination, in an environment where multiple paths are available, as well as to create a convenient performance measure to be used for the evaluation of the stability and connectivity in a mobile ad-hoc wireless networks.

The modern network service of finding the optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. gives rise to the multi-constrained optimal-path (MCOP) QoS routing problem, which is NP-complete. In this paper, this problem is solved through both exact and heuristic algorithms. We propose an exact algorithm E_MCOP, which first constructs an aggregate weight and then uses a K-shortest-path algorithm to find the optimal solution. By means of E_MCOP, the performance of the heuristic algorithm H_MCOP proposed by Korkmaz et al. in a recent work is evaluated. H_MCOP only runs Dijkstra's algorithm (with slight modifications) twice, but it can find feasible paths with a success ratio very close to that of the exact algorithm. However, we notice that in certain cases its feasible solution has an unsatisfactorily high average cost deviation from the corresponding optimal solution. For this reason, we propose some modified algorithms based on H_MCOP that can significantly improve the performance by running Dijkstra's algorithm a few more times. The performance of the exact algorithm and heuristics is investigated through computer simulations on networks of various sizes.

The development of efficient quality of service (QoS) routing algorithms in a high-speed network environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently heuristic algorithms based on Lagrange relaxation techniques have been proposed to resolve the contradiction between the time complexity and the quality of solution. In this paper, we investigate the performance of two heuristic algorithms, LR_DCLC and NR_DCLC, for the delay-constrained least-cost (DCLC) routing problem. Algorithm LR_DCLC is based on linear relaxation, while algorithm NR_DCLC, which is proposed in this paper, is based on nonlinear relaxation. A large number of simulations demonstrate that even though both algorithms have very good performance, NR_DCLC can obtain much better solutions than LR_DCLC by running Dijkstra's algorithm on average a few more times, especially in the case when the optimal solutions are hard to find.

To diffuse multimedia information services, communication networks must guarantee the quality of services (QoSs) requested by users. In addition, users should be allowed to observe the network in order to customize their own services. A new network management architecture is therefore essential. It must perceive not only node connectivity, but also network failure points and the traffic situation dynamically. This paper introduces the network map as such an architecture on personalized multimedia communication networks and proposes multiple QoS routing using the network map. Moreover, a prototype system is built in order to verify the availability of the network map.

The problem of finding a path with two additive constraints, in particular finding a path that satisfies both the cost and the delay constraints, is called multi-constrained path (MCP) problem in the literature. In this paper, we explore the MCP problem based on the idea of single mixed weight --a mixed weight for each link is first obtained by combining its delay and cost, and then Dijkstra's algorithm is used to find the corresponding shortest path. Given two infeasible paths, it can be theoretically proved that a better path can possibly be found if we choose an appropriate parameter to construct the mixed weight. An approximate algorithm is thus proposed to solve the MCP problem. Theoretical analysis demonstrates that this algorithm can make a correct judgment whether there is a feasible path or not with a very high probability even in the strict case where the delay bound is between the delays of the least delay path and the least cost path, while the cost bound is between the costs of the two paths. On the other hand, the time complexity of this algorithm is very small since it only needs to execute Dijkstra's algorithm a limited number of times. The excellent performance of the proposed algorithm is verified by a large number of experiments on networks of different sizes.

Improvements of Internet technology during the last decade have shifted the technical focus from reachability to the quality of communication. There are many technical frameworks, such as Integrated Service and Differentiated Services, which have been standardized to assure the quality of communication. QoS routing is also one of such frameworks. It changes or fixes a route that IP datagrams take, and is also indispensable to put a variety of services into practice. Nevertheless, experiment reports of QoS routing on operational network are quite few, especially with dynamic SLA. Therefore, we still do not know much about the important factors for QoS-enabled network to be realized, such as users' behavior, suitable services to offer, and configuration parameters. In this paper, we carried out field-trial with pseudo QoS routing and dynamic SLA in an actual network built at the WIDE retreat in autumn 2000. In this field-trial, we provided two different types of links to attendees. Attendees chose one of the links, through which their flows go, with our dynamic SLA. We describe the details and the results of this experiment. Our results could help to understand the customers' behavior for differentiated services, and therefore be useful for designing and deploying various QoS technologies.

In order to increase the flexibility and the extensibility for packet transmission, the active network approach, that makes network nodes programmable, is very promising. Every packet includes a program specifying behavior of the packet at network nodes, and the network nodes only have the functions to execute programs of the packet. In an active network, network congestion management is achieved more flexibly and intelligently than that in the conventional internet. A number of mechanisms for congestion management are easily developed because various network functions such as QoS routing and congestion detection are easily combined in the same network nodes. By executing different routing protocols that use different levels of the link information, a congestion management scheme can be customized by users. This paper shows how QoS routing and congestion detection achieve a congestion management over an active internetwork system.