Special issue: Routing and QoS over heterogenous networks

Vol. 63, n° 11-12, November-December 2008
Content available on Springerlink

Guest editors
Abdelhamid Mellouk, Université Paris XII, France
Sherali Zeadally, University of the District of Columbia, USA
Peter Mueller, IBM Zurich Research Laboratory, Switzerland

Foreword

A. Mellouk, S. Zeadally, P. Mueller

Provisioning QoS in inter-domain traffic engineering

Olivier Dugeon1, Enzo Mingozzi2, Giovanni Stea2, Luca Bisti2

1 France Telecom R&D, 2 avenue Pierre Marzin, 22307 Lannion Cedex, France
2 Dipartimento di Ingegneria dell’Informazione, University of Pisa, via Diotisalvi 2, 56122 Pisa, Italy

Abstract This work describes an architectural framework that allows inter-domain Traffic Engineering Label Switched Paths (TE-LSPs) with guaranteed quality of service (QoS) to be setup. Such TE-LSPs, called EQ-links, are setup by coordinating path computation elements (PCEs) of neighboring autonomous systems (ASs) along a pre-determined inter-AS path, computed through cooperative interaction between pairs of neighboring ASs. After defining the architectural requirements for the framework, we describe and analyze the Inter-AS Path Computation Protocol (IA-PCP), which computes an interdomain path at the AS level, i.e., selecting a sequence of ASs to the destination, based on a loose source routing approach. The results of the IA-PCP computations are then fed to the PCEs for complete path computation. The proposed architecture has been actually implemented within the testbed of the EuQoS project, which is aimed at enabling end-to-end QoS in the Internet. We report results related to the setup time of EQ-links, measured in the pan-European testbed of the EuQoS project, showing that path computation and setup takes an affordable time overhead.

Keywords Traffic engineering . Multi protocol label switching . Path computation element . DiffServ . EQ-link

Provision of End-to-End QoS in Heterogeneous Multi-Domain Networks

Wojciech Burakowski, Andrzej Bęben, Halina Tarasiuk, Jarosław Śliwiński, Robert Janowski, Jordi Mongay Batalla, Piotr Krawiec

Institute of Telecommunications, Warsaw University of Technology, ul. Nowowiejska 15/1900-665 Warsaw, Poland

Abstract In this paper, we present the framework to provision end-to-end QoS in heterogeneous multi-domain networks that was implemented in EuQoS system and tested in Pan-European research network. It assumes that a pair of end users, possibly attached to different access networks as xDSL, UMTS, LAN/Ethernet, WiFi, MPLS or Satellite, may choose for its connection an appropriate end-to-end Class of Service, depending on the application they use, e.g. VoIP, VoD, FTP, etc. Each end-to-end Class of Service has its own traffic control mechanisms and algorithms and, as a result, it has the ability to handle traffic streams with assumed guarantees for packet transfer characteristics expressed in the form of loss ratio, mean delay and delay variation. The end-to-end Classes of Service are supported in all the domains (including inter-domain links) independently using specialized inter-domain Class of Service aware QoS routing protocol which establishes the end-to-end QoS paths. The paper describes the solution and includes exemplary simulation and experimental results.

Keywords Heterogeneous multi-domain network, End-to-end QoS, Class of Service, QoS inter-domain routing, Admission Control, QoS mechanism, Network technology

Class-based multicast routing in interdomain scenarios

Maria João Nicolau1 · António Costa2 · Joaquim Macedo2 · Alexandre Santos2

1 Departamento de Sistemas de Informação, Universidade do Minho, Campus de Azurém, 4800 Guimarães, Portugal
2 Departamento de Informática, Universidade do Minho, Campus de Gualtar, 4710 Braga, Portugal

Abstract DiffServ-like domains bring new challenges to quality of service (QoS) multicast routing simply by shifting the focus from individual flows into classes of flows. Packets are marked at edge routers and receive differentiated treatment according to the class and not the flow that they belong to. DiffServ therefore became adverse to multicast, as packet replication inside the domain may require classification and remarking functions not present in core nodes. At the interdomain level, no doubt multicast QoS complexity is increased by the interleaving of DiffServ and non-Diffserv domains, making it more difficult to address QoS multicast in an end-to-end perspective. In today’s real interconnection world, classes of service have no meaning in certain links of a full interdomain path. While the problem is not new, as already pointed out, there are no real efforts to bring multicast back to a classof- service domain without compromising its model of operation. In this article, we present an innovative multicast QoS routing strategy, clearly designed for the new class-of-service paradigm. The solution is based upon the construction of multiple trees, one per class of service available, while still allowing receivers to shift for source-specific trees in its own class of service. The strategy is presented in a full end-to-end perspective. Intradomain trees use differentiated routing paths thus helping traffic differentiation. Intradomain receivers are allowed to shift from shared trees into an adequate class-of-service source tree. At interdomain level, each class-of-service interdomain tree branch is accomplished by means of an improved path probing strategy enabling for QoS path establishment. This paper presents this new strategy, and associated protocols, for constructing several multicast and directed distribution trees, one per class of service, within eachmulticast group. This new strategy and associated protocols are then simulated using NS-2 platform. Simulation results are analyzed and compared with other multicast routing solutions, both at intra- and interdomain levels.

Keywords QoS routing · Multicast · Interdomain

Cooperative Load Balancing Strategy Based on N-hops Routing Algorithm of Ad Hoc Network in Heterogeneous Overlapping Networks

Xuebing Pei, Guangxi Zhu, Qingping Wang, Gan Liu and Wenpeng Yuan

Department of Electronics & Information Engineering, Huazhong University of Science and Technology, Wuhan National Laboratory of Optoelectronics Wuhan, 430074, P. R. China

Abstract  A major challenge of the heterogeneous wireless networks is how to jointly utilize the resources of different radio access technologies in an efficient manner. In this paper, system performance such as the block probability and throughput etc. was investigated in communication hot spots overlapped by heterogeneous networks: cellular, WLAN, and WiMax networks. Two cooperative load balancing strategies based on hops-limited routing algorithm of ad hoc network are proposed in order to raise the resource utilization of the whole overlapping heterogeneous networks. They both firstly make a decision whether to admit a new call or not based on common radio resource management strategies, and in overloaded condition select certain traffic to transfer into targeted BS/AP according to minimum price strategy or minimum load BS/AP and nearest traffic strategy, which take into account these factors such as load index, number of hops, traffic prediction, cost, etc. An analytical model is used to compute the call block probability and throughput performance for two different traffic models. Simulation results show that the proposed load balancing strategies can distribute traffics to the whole heterogeneous wireless networks, decrease the call block probability, improve system throughputs efficiently, and obviously outperform HM-MACA and HS-TC load balancing strategies.

Keywords Load balancing, multi-hop routing algorithm, radio resource management, heterogeneous wireless networks

An architecture for internet inter-domain interconnections and bandwidth trading towards effective NGN deployment

Dohoon Kim

College of Business Administration, Kyung Hee University, Seoul, South Korea

Abstract The International Telecommunication Union (ITU-T) is developing an architecture for Next Generation Network (NGN) to provide end-to-end Quality of Service (e2e QoS), for which Internet service provider (ISP) interconnections play a key role. Furthermore, for an effective e2e QoS-guaranteed interconnection across multiple ISPs, it is of a great help to develop a framework which enables ISPs to trade their unused network capacity. This study presents Hub-and-Spoke (H&S) interconnection model, where the hub called Neutral Internet Business eXchange (NIBX) arranges Bandwidth Trading (BT) on the basis of the market mechanism. After introducing qualitative and quantitative justifications of the H&S NIBX interconnection model, we propose a platform prototype for BT based upon the H&S NIBX architecture. Presented also are some detailed descriptions of key functional elements together with decision models embedded in the functions. Operations scenarios show potential benefits of the NIBX + BT architecture for ensuring e2e QoS, the ultimate goal of ITU-T’s NGN.

Keywords Internet interconnections . Inter-Domain routing . Bandwidth trading . End-to-endQoS . Hub-and-spoke network . Network economics . NGN . Network operations and management

Distributed Busacker-Gowen algorithm for end-to-end QoS pipe negotiation in X-domain networks

Hélia Pouyllau1 · Stefan Haar2

1 Alcatel-Lucent Bell Labs, route de VilleJust, 91620 Nozay, France
2 IRISA/INRIA, Campus de Beaulieu, 35042 Rennes cedex, France

Abstract  Multimedia services and other critical multisite services (e.g., VPN) are becoming mainstream, and they require a guaranteed quality of service (QoS). Services need to be established across several autonomous systems (ASes), often to connect end-users. Thus, provisioning and control of end-to-end QoS requirements arise as one of the main challenges in inter-AS management. The contractual approach, consisting in using service-level agreements (SLAs) defined by each crossed AS, allows to negotiate contract chains that satisfy end-to-end requirements. However, establishing such chains by on-demand negotiations does not scale up for large numbers of requests. Hence, we propose a negotiation process to occur before users’ requests to establish service are received. The proposed negotiation process results in the selection of aggregated contract chains, called pipes, and a distribution between them. Such a distribution would indicate, for each chain of a pipe, the connection flow it may accept. In this paper, we address the pipe negotiation problem as a network flow problem. We also propose a distributed adaptation of an algorithm for network flow problems.

Keywords End-to-end QoS · Inter-AS · QoS pipes · SLA · Negotiation · Distributed algorithms · Network flow · Busacker-Gowen algorithm

A distributed scheme for optimization of interdomain routing between collaborating domains

Artur Tomaszewski1 · Michał Pióro2 · Mariusz Mycek1

1Institute of Telecommunications, Warsaw University of Technology, Warsaw, Poland
2Department of Communication Systems, Lund University, Lund, Sweden

Abstract  As today’s market forces the implementation of quality-of-service-enabled services spanned over multiple administrative domains, isolated and locally optimized interdomain routing decisions become increasingly inadequate. Instead, coordinated routing models are required together with joint optimization goals. Available papers and standardization documents focus on the description of technical means for deployment of interdomain transport services giving little (or no) attention to the problem of evaluating effective interdomain routing patterns. Our paper aims at closing this gap. It presents an iterative distributed process where domains cooperatively determine a (sub)optimal, with respect to a common utility function, flow of interdomain traffic. If all the cooperating domains adhere to the results of this process, they can reduce their operational costs, speed up operations, and increase profits. This paper is a continuation of Tomaszewski et al. (2007) and Pióro et al. (2007)-it introduces a modified problem formulation and analyzes the influence of aggregation of intradomain topology on speed and quality of the resolution process.

Keywords Interdomain routing · Distributed optimization · Lagrangean relaxation

Quality of Service Models for Heterogeneous Networks: Overview and Challenges

Hesham El-Sayed1, Abdelhamid Mellouk2, Laurent George3, Sherali Zeadally4

1 College of Information Technology UAE University, United Arab Emirates
2 LISSI Laboratory, University of Paris 12-Val de Marne, 122 rue Paul Armangot Vitry sur Seine 94400 France
3 ECE, LACSC, 53 rue de Grenelle, 75007 Paris, France
4 Network Systems Laboratory, Department of Computer Science and Information Technology, University of the District of Columbia, Washington, DC 20008, USA

Abstract The proliferation and convergence of different types of wired, wireless and mobile networks (such as WiMAX, Wireless Mesh Networks, WPANs, WLANs, etc) and cellular-based networks are crucial for the success of next generation networks. Traditional wired/wireless networks can hardly meet the requirements of future integrated-service networks which are expected to carry multimedia traffic with various Quality of Service (QoS) requirements. Therefore, it is necessary to develop efficient global control mechanisms that can maintain QoS requirements to maximize network resources utilization, and minimize operational costs on all the types of wireless-mobile networks. In this paper, we present an overview of QoS paradigms for heterogeneous networks and focus on those based on deterministic and probabilistic QoS.

Keywords QoS, QoS Routing, Heterogeneous Networks (Wireless & Wired Networks), Scheduling, QoS Signaling, Work-Conserving.

Energy-Aware and Quality of Service-based Routing in Wireless Sensor Networks and Vehicular Ad Hoc Networks

Anahit Martirosyan, Azzedine Boukerche, Richard W. Nelem Pazzi

PARADISE Research Laboratory, University of Ottawa, Canada

Abstract 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 energyaware 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 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 inter-vehicle 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 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 aiming at satisfying QoS in WSNs and VANETS. Last, a discussion and comparison of features of the selected routing protocols and QoS-based approaches is presented.

Keywords Wireless Sensor NetworksEnergy-EfficiencyQuality of ServiceRoutingVehicular Ad Hoc Networks

Inter-domain Quality of Service Routing: Setting the Grounds for the Way Ahead

Alexandre Fonte1, Marilia Curado2, Edmundo Monteiro2

1 Department of Informatics/CISUC, University of Coimbra, Portugal, School of Technology, Polytechnic Institute of Castelo Branco, Portugal
2 Department of Informatics/CISUC, University of Coimbra, Portugal

Abstract A common criticism of the current Internet is the fact that it does not offers Quality of Service (QoS) guarantees across Autonomous Systems (AS) boundaries. The Border Gateway Protocol (BGP) is central to solve this problem, since it enables ASes 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 Inter-domain 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 Inter-domain QoS Routing problem. First, the main drawbacks of current Inter-domain routing with regard to the provision of QoS are identified. Second, a survey of the most relevant Inter-domain 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 non-technical unsolved challenges that in our perspective still be almost certainly the biggest barrier to the development of inter-domain QoS routing.

Keywords QoS · Routing · Inter-domain QoS Routing · BGP