An overview of quality of service routing for next-generationhigh-speed networks: problems and solutions

The upcoming gigabit-per-second high-speed networks are expected to support a wide range of communication-intensive real-time multimedia applications. The requirement for timely delivery of digitized audio-visual information raises new challenges for next-generation integrated services broadband networks. One of the key issues is QoS routing. It selects network routes with sufficient resources for the requested QoS parameters. The goal of routing solutions is twofold: (1) satisfying the QoS requirements for every admitted connection, and (2) achieving global efficiency in resource utilization. Many unicast/multicast QoS routing algorithms have been published, and they work with a variety of QoS requirements and resource constraints. Overall, they can be partitioned into three broad classes: (1) source routing, (2) distributed routing, and (3) hierarchical routing algorithms. We give an overview of the QoS routing problem as well as the existing solutions. We present the strengths and weaknesses of different routing strategies, and outline the challenges. We also discuss the basic algorithms in each class, classify and compare them, and point out possible future directions in the QoS routing area     

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     

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.     

Mobile flow-aware networks for mobility and QoS support in the IP-based wireless networks

As the volume of mobile traffic consisting of video, voice, and data is rapidly expanding, a challenge remains with the mobile transport network, which must deliver data traffic to mobile devices without degrading the service quality. Since every Internet service holds its own service quality requirements, the flow-aware traffic management in fine granularity has been widely investigated to guarantee Quality of Service (QoS) in the IP networks. However, the mobile flow-aware management has not been sufficiently developed yet because of the inherent constraints of flow routing in the mobile networks regarding flow-aware mobility and QoS support. In this paper, we propose a flow-aware mobility and QoS support scheme called mobile flow-aware network (MFAN) for IP-based wireless mobile networks. The proposed scheme consists of dynamic handoff mechanisms based on QoS requirements per flow to reduce the processing overhead of the flow router while ensuring QoS guarantee to mobile flows. The performance analyses of the proposed scheme demonstrate that MFAN successfully supports the mobile flow traffic delivery while satisfying the QoS requirement of flows in the wireless mobile IP networks.     

Interdomain quality of service routing: setting the grounds for the way ahead

A common criticism of the current Internet is the fact that it does not offer quality of service (QoS) guarantees across autonomous system boundaries. The Border Gateway Protocol (BGP) is central to solve this problem, since it enables AS to distribute reachability information. However, BGP is agnostic of any performance or QoS metrics. For this reason, the debate about the requirements for the future interdomain routing architecture and about whether these requirements are best met by an approach of introducing changes into BGP or by replacing BGP is still open. This article provides an insight into the interdomain QoS routing problem. First, the main drawbacks of current interdomain routing with regard to the provision of QoS are identified. Second, a survey of the most relevant interdomain QoS routing approaches are described and discussed. We also give a broad perspective on challenges surrounding the issue of whether to extend or replace BGP to support QoS, with particular emphasis on the technical challenges. However, we also point out some nontechnical unsolved challenges that, in our perspective, are still almost certainly the biggest barrier to the development of interdomain QoS routing.     

Study on the performance of the A*Prune QoS routing algorithm for intelligent optical networks and its improvements

1 Introduction In the past few years, many routing algorithms for compu- ting constrained paths have been proposed in the networking community. In the earlier days, research study has been concentrated on a single additive constraint, especially the delay…     

Multicast routing and its QoS extension: problems, algorithms, andprotocols

Multicast services have been increasingly used by various continuous media applications. The QoS requirements of these continuous media applications prompt the necessity for QoS-driven, constraint-based multicast routing. This article provides a comprehensive overview of existing multicast routing algorithms, protocols, and their QoS extension. In particular, we classify multicast routing problems according to their optimization functions and performance constraints, present basic routing algorithms in each problem class, and discuss their strengths and weaknesses. We also categorize existing multicast routing protocols, outline the issues and challenges in providing QoS in multicast routing, and point out possible future research directions     

QoS-driven multicast routing in sparse-splitting optical networks

This paper investigates the quality-of-service (QoS)-driven multicast routing problem in a sparse-splitting optical network. The main objective is to minimize the total cost of wavelength channels utilized by the light-tree while satisfying required QoS parameters. In this paper, both the optical-layer constraints (e.g., optical signal power) and application-layer requirements (e.g., end-to-end delay and inter-destination delay variation) are considered as the QoS parameters. First, integer linear programming (ILP) formulations to solve the optimal multicast routing problem with the given QoS parameters are presented. Solving the ILP formulations for large-scale networks can easily overwhelm the capabilities of state-of-the-art computing facilities, and hence, a heuristic algorithm is proposed to construct a feasible light-tree that satisfies the required QoS parameters in large-scale networks. Simulation results demonstrate the performance of the proposed heuristic algorithm in terms of the cost of utilized wavelength channels.     

QoS routing for MPLS networks employing mobile agents

The implementation of new networking technologies, such as multiprotocol label switching and differentiated services, will introduce powerful features to the near-future Internet backbone, making a significant contribution to the overall end-to-end provision of quality of service. However, to achieve such an improvement these technologies require not only effective support from current routing algorithms, but also enhanced capabilities, which are currently being developed. To contribute to this development, a novel and powerful scheme is introduced in this article that provides a means of supporting QoS routing through the use of mobile software agents. Specifically, we describe the use of mobile agents to efficiently realize multipoint-to-point routing trees by means of the Wave paradigm, while satisfying the QoS requirements of the set of traffic streams involved in the process. Both benefits and important issues to be considered when using mobile agent schemes in QoS routing are further stressed     

Rate control-based framework and algorithm for optimal provisioning

Ideally, networks should be designed to accommodate a variety of different traffic types, while at the same time maximizing its efficiency and utility. Network utility maximization (NUM) serves as an effective approach for solving the problem of network resource allocation (NRA) in network analysis and design. In existing literature, the NUM model has been used to achieve optimal network resource allocation such that the network utility is maximized. This is important, since network resources are at premium with the exponential increase in Internet traffic. However, most research work considering network resource allocation does not take into consideration key issues, such as routing and delay. A good routing policy is the key to efficient network utility, and without considering the delay requirements of the different traffic, the network will fail to meet the user’s quality of service (QoS) constraints. In this paper, we propose a new NUM framework that achieves improved network utility while taking into routing and delay requirements of the traffic. Then, we propose a decomposition technique-based algorithm, D-NUM, for solving this model efficiently. We compare our approach with existing approaches via simulations and show that our approach performs well.     

Energy-aware and quality of service-based routing in wireless sensor networks and vehicular ad hoc networks

Wireless Sensor Networks (WSNs) have increasingly been used for remote monitoring tasks. Limited capabilities of sensor nodes in terms of communication, computation, and storage, present challenges to protocols designed for WSNs. Due to the severe energy constraint of sensor nodes, among the major concerns is the problem of designing efficient energy-aware routing protocols. Numerous routing protocols have been proposed in the literature. Cluster-based routing protocols for large-scale WSNs have some advantages as compared to a flat network topology. Clustering results in a reduced number of messages that propagate through the network in order to accomplish a sensing task. It also offers improved power control. Quality of Service (QoS) is becoming an important feature of data routing in WSNs. QoS is required for real-time data transmission when the result of a sensing task is dependent not only on the correct sensing of the environment but also on the timely delivery of the event notification to the monitoring center, the Sink. The emergency preparedness and response class of applications, for instance, impose delay requirements on the delivery of event notification messages. Transmitting video and imaging data poses certain bandwidth, delay, and jitter requirements on the routing protocols. Vehicular Ad Hoc Networks (VANETs) are envisioned to improve intervehicle coordination and become a part of intelligent transport systems with an ultimate goal of increasing safety on the roads and improving travel comfort. VANETs may include WSNs that are placed along the sides of roads and provide monitoring of road conditions. Routing protocols for VANETs also aim at satisfying end-to-end QoS requirements. This paper first discusses energy-efficient clustering routing protocols for WSNs, followed by approaches aimed at satisfying QoS in WSNs and VANETS. Lastly, a discussion and comparison of features of the selected routing protocols and QoS-based approaches is presented.     

无线Ad Hoc网络中的QoS路由协议

无线Ad Hoc网络的应用环境以及与Internet的互连都要求其必须提供一定的服务质量(QoS)保证,QoS路由技术是在无线Ad Hoc网络中实现QoS的重要方法。本文对近年来国内外在无线Ad Hoc网络中的QoS路由技术方面取得的研究成果进行了全面的概括总结和分类,对资源预留路由、多径路由和跨层优化路由3类QoS路由协议进行比较分析,并且提出了QoS路由技术亟待解决的问题和今后的发展方向。     

QoS provision in wireless access networks: a routing perspective considering mobility

Future wireless communications are expected to provide mobile users access to the desired service with the appropriate quality at any place. The essential elements for assembling such a vision are mobility, quality of service (QoS) provision and scalability, which are expected to be merged into the design process of wireless access networks. Internet mobility support is currently entering a mature phase in which scalable solutions provide low loss or even seamless handovers in cellular and heterogeneous mobile environments. Wireless and mobile QoS architectures extend the equivalent Internet approaches in order to accommodate the requirements associated with the presence of wireless links and mobility. Nevertheless, none of the popular mobility proposals combined with wireless and mobile QoS architectures encounter QoS in the routing function, leaving the QoS provision underutilized. QoS routing (QoSR) complements existing QoS architectures, enhancing application performance especially in the case of congestion, while providing efficient resource management. However, QoSR was originally designed for fixed IP networks without taking mobility into account. This paper investigates the interaction of QoSR in wireless access networks, identifying key points for the efficient cooperation with mobility and existing QoS architectures. Copyright © 2009 John Wiley & Sons, Ltd.     

一类基于源路由的多约束实时组播路由优化控制算法

随着Internet网络的不断发展,它将成为未来网络服务的平台,而未来网络服务的种类又是多种多样的,既有传统的尽量服务(Best-Effort Service)应用,又有对网络服务质量 [1](QoS:Quality of Service)有着特殊需求的应用.本文探讨了如何在网络层路由这一层面进行QoS组播路由支持的问题.目前,已有许多组播QoS路由算法提出,在QoS路由性能、网络资源使用效率以及路由吞吐率等方面取得了许多好的成果.针对这些QoS路由算法中存在的一些问题,提出了一种组播QoS路由算法.实验结果表明:该算法在适应网络拓扑结构、网络规模、对称/非对称链路负载等方面,与其它QoS路由算法相比,在算法性能上有了一定的改进.     

A dynamic multicast routing satisfying multiple QoS constraints

In this paper we propose a QoS‐based routing algorithm for dynamic multicasting. The complexity of the problem can be reduced to a simple shortest path problem by applying a Weighted Fair Queuing (WFQ) service discipline. Using a modified Bellman–Ford algorithm, the proposed routing builds a multicast tree, where a node is added to the existing multicast tree without re‐routing and satisfying QoS constraints. With user defined life‐time of connection this heuristic algorthm builds multicast tree which is near optimum over the whole duration of session. Simulation results show that tree costs are nearly as good as other dynamic multicast routings that does not consider QoS. Copyright © 2003 John Wiley & Sons, Ltd.     

具不确定信息的延迟受限QoS路由研究

QoS路由的目的是找到一条或多条具有足够资源,以满足某种约束条件(如延迟,带宽等)的路径。在实际情况中,关于链路状态的信息并不总是确定的,这种不确定性对QoS路由的选择有着不可避免的影响。探讨其原因,在约束条件为延迟保证的前提下,讨论处理不确定信息的QoS单播路由算法。     

A QoS-aware multicast routing protocol

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new QoS-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead of constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high level design of QMRP makes it operable on top of any unicast routing algorithm in both intradomain and interdomain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees     

一种非精确状态下满足多QoS约束的 动态组播路由算法

提出了一种非精确状态下满足多QoS约束的动态组播路由算法——DMIQ,该算法采用改进的BF算法作为路径搜索算法,WFQ作为分组调度机制,链路延迟不确定且服从均匀分布,能在非精确状态且满足带宽、延迟抖动和丢包率约束的前提下确定具有最小跳数和开销的动态组播路由.仿真实验表明,DMIQ能在非精确状态且满足多QoS约束的前提下建立动态组播路由,在路由请求平均成功率、平均延迟和平均跳数等衡量指标下表现出良好的性能.     

A Cross-Layer Channel Access and Routing Protocol for Medical-Grade QoS Support in Wireless Sensor Networks

One of principal design issues of a Wireless Sensor Network (WSN) for medical information systems is to classify received packets based on their priorities and guarantees so that they can be transmitted reliably, thus satisfying QoS requirements. In addition, when the target WSN requires multi-hop communications and the traffic load increases significantly, it is challenging to support both load balancing and suitable QoS at the same time. In this paper, we propose a new reliable protocol termed Cross-layer Channel Access and Routing (CCAR), which simultaneously supports both MAC and routing operations for medical-grade QoS provisions. CCAR initially determines the routing path with the lowest traffic load and low latency using newly defined channel quality factors. Concurrently, the source node allocates the predefined QoS Access Category to each packet and reserves the channel along the route. In addition, CCAR introduces an effective route maintenance scheme to avoid link failures in bottlenecked intermediate nodes, which prevents unnecessary packet drops and route rediscovery evocations. Finally, through both simulation studies and real test-bed experiments, we evaluate the performance of CCAR by comparing it with other conventional protocols, demonstrating that the proposed protocol can more efficiently support medical-grade QoS packets, especially when the network is heavily loaded.     

QoS Based Survivable Logical Topology Design in WDM Optical Networks

The need to establish wavelength-routed connections in a service differentiated manner is becoming increasingly important. In the backbone network, support of quality of service (QoS) capabilities at the lightpath level will have to be addressed in the optical domain. Providing a service differentiated connection on an arbitrary virtual topology which does not support any differentiated services will lead to the misuse of network resources. We address the virtual topology design and routing problem, where we minimize congestion in the network. In our work, the service differentiating parameter is bit error rate (BER) in the optical domain. We present a mixed integer linear programming (MILP) formulation for the above problem. We also propose a heuristic based approach to minimize the congestion in the network while satisfying the QoS constraints. These QoS constraints in our case are the differing BER requirements for each connection between each (source, destination) pair. We then present different methods of providing survivability for the virtual topology and compare the performance of these methods.