Quality Of Service Manet-thesis

Quality of Service for Mobile Ad Hoc Networks

Diploma Thesis of Patrick Stüdi Assistant: Jianbo Xue Supervisor: Prof. Dr. Gustavo Alonso March 2003

ii

Abstract The fast adaptation of IP-based communications for mobile and hand-held devices equipped with wireless interfaces is creating a new challenge for Quality of Service (QoS) provision. Due the error-prone nature of wireless links and the high mobility of mobile devices, traditional Internet QoS protocols like RSVP cannot be easily migrated to the wireless environment. This is specially true for Mobile Ad Hoc Networks (MANETs) where every node moves arbitrarily causing the multi-hop network topology to change randomly and at unpredictable times. In this thesis a new framework coping with the specific issues of MANETs is proposed. The framework includes a QoS signaling protocol and flexible resource allocation and adaptation mechanisms. In order to prove its efficiency the system is implemented and simulated using the ns-2 network simulator. Keywords: MANET, QoS, In-band Signaling, Adaptation, Resource Reservation, ASAP

iv

Contents 1 Introduction

1

1.1

Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Mobile Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

Quality of Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.4

Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2 QoS Models for MANETs 2.1

2.2

2.3

3

QoS Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.1

IntServ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.2

DiffServ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.3

IntServ over DiffServ . . . . . . . . . . . . . . . . . . . . . . . . .

4

Quality of Service in Ac Hoc Networks . . . . . . . . . . . . . . . . . . .

4

2.2.1

Special Issues and Difficulties in MANETS . . . . . . . . . . . . .

4

2.2.2

Drawbacks of the different QoS Models . . . . . . . . . . . . . . .

4

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

3 Protocol Design Issues

7

3.1

Towards developing a QoS Framework for MANETs . . . . . . . . . . . .

7

3.2

QoS from a Layered Perspective . . . . . . . . . . . . . . . . . . . . . . .

7

3.3

QoS-Signaling and Routing Interaction . . . . . . . . . . . . . . . . . . . .

7

3.4

QoS-Signaling: Design Issues . . . . . . . . . . . . . . . . . . . . . . . .

8

3.4.1

In-band versus Out-of-band Signaling . . . . . . . . . . . . . . . .

8

3.4.2

Reservation Mechanism: One-pass versus Two-pass . . . . . . . .

9

3.4.3

Soft-state versus Hard-state . . . . . . . . . . . . . . . . . . . . .

9

3.4.4

Local Repair . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.5

QoS Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.5.1

Application Requirements . . . . . . . . . . . . . . . . . . . . . . 10

3.5.2

Adaptation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.5.3

Monitoring Interval and Soft-state Timer . . . . . . . . . . . . . . 12

vi

CONTENTS 3.6

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Existing Technologies 4.1

13

RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1.1

RSVP Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.2

FQMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.3

INSIGNIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.4

Some further Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.4.1

iMAQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.4.2

INORA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5 ASAP Framework 5.1

5.2

5.3

Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.1.1

Soft/Hard Reservation . . . . . . . . . . . . . . . . . . . . . . . . 19

5.1.2

Soft-State Management . . . . . . . . . . . . . . . . . . . . . . . . 19

5.1.3

Adaptive QoS Monitoring . . . . . . . . . . . . . . . . . . . . . . 20

Signaling System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.2.1

QoS Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.2.2

Message Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.2.3

Setup Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5.2.4

QoS Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Implementing ASAP using IPv6 . . . . . . . . . . . . . . . . . . . . . . . 23 5.3.1

IPv6 in a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.3.2

IPv6 Header Format . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.3.3

Using IPv6 for ASAP Signaling . . . . . . . . . . . . . . . . . . . 24

6 Ad Hoc Extensions for ASAP 6.1

6.2

6.3

19

27

Problems of ASAP in MANETs . . . . . . . . . . . . . . . . . . . . . . . 27 6.1.1

Flow Restoration . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

6.1.2

Reverse Path Problem . . . . . . . . . . . . . . . . . . . . . . . . 28

6.1.3

Lost Hard-Reservation Messages . . . . . . . . . . . . . . . . . . 28

Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.2.1

QoS Option Field for Soft-Reservation Message . . . . . . . . . . 29

6.2.2

Local Repair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

6.2.3

Dynamic Virtual Path . . . . . . . . . . . . . . . . . . . . . . . . . 30

6.2.4

Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

CONTENTS

vii

7 Implementation

33

7.1

Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

7.2

NS-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 7.2.1

Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

7.2.2

Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.2.3

Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.3

Implementation Requirements . . . . . . . . . . . . . . . . . . . . . . . . 36

7.4

Main Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

7.5

QoS Management Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.5.1

Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.5.2

Internal Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.5.3

Message Serialization/Deserialization . . . . . . . . . . . . . . . . 38

7.5.4

Reservation Processing . . . . . . . . . . . . . . . . . . . . . . . . 39

7.6

Adaptation Control Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7.7

Application QoS Request Unit . . . . . . . . . . . . . . . . . . . . . . . . 42

7.8

Some further Components . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7.9

7.8.1

Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7.8.2

Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7.8.3

Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7.8.4

Node Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

8 Simulation and Analysis

45

8.1

Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

8.2

Simulation Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

8.3

8.4

8.2.1

Flow Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

8.2.2

Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

8.2.3

A Remark in Advance . . . . . . . . . . . . . . . . . . . . . . . . 47

Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 8.3.1

Local Repair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

8.3.2

Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

8.3.3

QoS Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8.3.4

Reservation Efficiency . . . . . . . . . . . . . . . . . . . . . . . . 50

8.3.5

Signaling Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

9 Summary and Outlook

53

viii

CONTENTS 9.1

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

9.2

Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Bibliography

56

Chapter 1

Introduction 1.1 Problem Statement The introduction of real-time audio, video and data services into wireless networks presents a number of technical obstacles to overcome. Traditional internet QoS protocols like RSVP cannot be easily migrated to the wireless environment due to the error-prone nature of wireless links and the high mobility of mobile devices. This is specially true for Mobile Ad Hoc Networks (MANETs) where every node moves arbitrarily causing the multi-hop network topology to change randomly and at unpredictable times. In this thesis an existing QoS framework is extended to be suitable for MANETs. In order to prove its correctness and efficiency the system is implemented and simulated using the ns-2 network simulator.

1.2 Mobile Ad Hoc Networks A mobile ad hoc network is a concept that has received attention in scientific research since the 1970s. A clear picture of what exactly is meant by an ad hoc network is difficult to pinpoint. In today’s literature the term is used in many different ways. The Internet Engineering Task Force (IETF), the body responsible for guiding the evolution of the Internet, provides the definition as given below [23]: A mobile ad hoc network (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links. The routers are free to move randomly and organize themselves arbitrarily; thus, the network’s wireless topology may change rapidly and unpredictably. Such a network may operate in a stand-alone fashion, or may be connected to the larger Internet MANETs are useful in many applications because they do not need any infrastructure support. Collaborative computing and communications in smaller areas (building organizations, conferences, etc.) can be set up using MANETS. Communications in battlefields and disaster recovery areas are further examples of application environments. With the evolution of Multimedia Technology, Quality of Service in MANETs became an area of great interest. Besides the problems that exist for QoS in wire-based networks, MANETS impose new constraints. This is due the dynamic behaviour and the limited resources of such networks.

2

Chapter 1. Introduction

1.3 Quality of Service QoS is usually defined as a set of service requirements that needs to be met by the network while transporting a packet stream from a source to its destination. The network needs are governed by the service requirements of end user applications. The network is expected to guarantee a set of measurable prespecified service attributes to the users in terms of end-to-end performance, such as delay, bandwidth, probability of packet loss, delay variance (jitter), etc. Power consumption is another QoS attribute which is more specific to MANETs. In the literature, the research on QoS support in MANETs spans over all the layers in the network: QoS models specify an architecture in which some kinds of services could be provided. It is the system goal that has to be implemented. QoS Adaptation hides all environment-related features from awareness of the multimedia-application above and provides an interface for applications to interact with QoS control. Above the network layer QoS signaling acts as a control center in QoS support. The functionality of QoS signaling is determined by the QoS model. QoS routing is part of the network layer and searches for a path with enough resources but does not reserve resources. QoS MAC protocols are essential components in QoS for MANETs. QoS supporting components at upper layers, such as QoS signaling or QoS routing assume the existence of a MAC protocol, which solves the problems of medium contention, supports reliable communication, and provides resource reservation. This document does not treat QoS MAC and QoS routing any further and instead focuses on upper layers like QoS models and signaling.

1.4 Outline After analysing existing QoS models with respect to the dynamic behaviour of ad hoc networks in chapter 2 this document proceeds presenting some of the fundamental design issues to be considered when developing a QoS framework for MANETs. Chapter 4 focuses on some existing approaches classifying each one according to the design issues identified in chapter 3. ASAP is a QoS framework developed at the University of Stuttgart and was originally designed to support QoS in last-hop-wireless networks and is proposed in chapter 5. The ad hoc extensions to ASAP, the implementation for ns-2 and its simulation are discussed in chapter 6, 7 and 8. Finally this document concludes with a summary and gives an outlook on potential further work.

Chapter 2

QoS Models for MANETs 2.1 QoS Models Today’s Internet applies best effort (BE) IP forwarding. The network attempts to deliver all traffic as soon as possible within the limits of its abilities, but without guarantees related to throughput, delay or packet loss. It is left up to the end systems to cope with network transport impairments. Although best effort will remain adequate for most applications, QoS support is required to satisfy the growing need for multimedia over IP, like video streaming or IP telephony. The existing QoS models can be classified into two types according to their fundamental operation; the Integrated Services (IntServ) framework provides explicit reservations end-to-end and the Differentiated Services (DiffServ) architecture offers hop-by-hop differentiated treatment of packets.

2.1.1 IntServ The IntServ[7][15] model merges the advantages of two different paradigms: datagram networks and circuit switched networks. It can provide a circuit-switched service in packetswitched networks. The Resource Reservation Protocol (RSVP) was designed as the primary signaling protocol to setup and maintain the virtual connection. RSVP is also used to propagate the attributes of the data flow and to request resources along the path. Routers finally apply corresponding resource management schemes to support QoS specifications of the connection. Based on these mechanisms, IntServ provides quantitative QoS for every flow.

2.1.2 DiffServ DiffServ[5][26][10] was designed to overcome the difficulty of implementing and deploying IntServ and RSVP in the Internet backbone and differs in the kind of service it provides. While IntServ provides per-flow guarantees, Differentiated Services (DiffServ) follows the philosophy of mapping multiple flows into a few service levels. At the boundary of the network, traffic entering a network is classified, conditioned and assigned to different behaviour aggregates by marking a special DS (Differentiated Services) field in the IP packet header (TOS field in IPv4 or CLASS field in IPv6). Within the core of the network, packets are forwarded according to the per-hop behaviour (PHB) associated with the DSCP (Differentiated Service Code Point). This eliminates the need to keep any flow state information elsewhere in the network.

4

Chapter 2. QoS Models for MANETs

2.1.3 IntServ over DiffServ This model provides a reservation-based QoS architecture with feedback signaling. It uses RSVP to signal resource needs but uses DiffServ as the technology to do the actual resource sharing among flows.

2.2 Quality of Service in Ac Hoc Networks This section discusses unique issues and difficulties for supporting QoS in a MANET environment and ends up showing the major drawbacks of each of the two QoS architectures described above with respect to these characteristics.

2.2.1 Special Issues and Difficulties in MANETS MANETs differ from the traditional wired Internet infrastructures. The differences introduce difficulties for achieving Quality of Service in such networks. The following list itemizes some of the problems: Dynamic topologies: Nodes are free to move arbitrarily; thus, the network topology - which is typically multihop - may change randomly and rapidly at unpredictable times, and may consist of both bidirectional and unidirectional links. Bandwidth-constrained, variable capacity links: Wireless links will continue to have significantly lower capacity than their hardwired counterparts. In addition, the realized throughput of wireless communications - after accounting for the effects of multiple access, fading, noise, and interference conditions, etc.- is often much less than a radio’s maximum transmission rate. One effect of the relatively low to moderate link capacities is that congestion is typically the norm rather than the exception, i.e. aggregate application demand will likely approach or exceed network capacity frequently. As the mobile network is often simply an extension of the fixed network infrastructure, mobile ad hoc users will demand similar services. These demands will continue to increase as multimedia computing and collaborative networking applications rise. Energy-constrained operation: Some or all of the nodes in a MANET may rely on batteries or other exhaustible means for their energy. For these nodes, the most important system design criteria for optimization may be energy conservation.

2.2.2 Drawbacks of the different QoS Models IntServ in MANETS IntServ has the following salient shortcomings in MANET environments: Scalability: IntServ provides per-flow granularity, so the amount of state information increases proportionally with the number of flows. This results in a storage and processing overhead on routers, which is the well-known scalability problem of IntServ. The scalability problem is less likely to occur in current MANETs considering the small number of flows, the limited size of the network and the bandwidth of the wireless links. On the other hand, as the quality of wireless technology increases rapidly, high speed and large size MANETs may be a matter of fact some day. Though one could argue that whenever large high-performance MANETs will be developed in future, processing and storing capabilities will increase as well.

2.3 Conclusion Signaling: Signaling protocols generally contain three phases: connection establishment, connection maintenance and connection teardown. In highly dynamic networks such as MANETs this is no promising approach since routes may change very fast and the adaptation process of protocols using a complex handshaking mechanism would just be too slow. Furthermore the signaling overhead while maintaining the connection is a potential problem as well. DiffServ in MANETS The main drawbacks of a DiffServ approach in MANETs are listed below: Soft QoS guarantees: DiffServ uses a relative-priority scheme to map the quality of service requirements to a service level. This aggregation results in a more scalable but also in more approximate service to user flow. SLA (Service Level Agreement): DiffServ is based on the concept of SLA’s. In the Internet an SLA is a kind of contract between a customer and its Internet Service Provider (ISP) that specifies the forwarding service the customer should receive. The Administration of a DiffServ domain must assure that sufficient resources are provisioned to support the SLA’s committed by the domain [2]. Moreover, the DiffServ boundary nodes are required to monitor the arriving traffic for each service class and to perform traffic classification and conditioning to enforce the negotiated SLA’s. Generally speaking if someone acquires QoS parameters and he pays for such parameters then of course there must be some entity which will assures them. In a completely ad hoc topology where there is no concept of service provider and client and where there are only clients it would be quite difficult to innovate QoS, since there is no obligation from somebody to somebody else what makes QoS almost infeasible. Ambiguous core network: The benefit of DiffServ is that traffic classification and conditioning only has to be done at the boundary nodes[26]. This makes quality of service provisioning much easier in the core of the network. In MANETs though there is no clear definition of what is the core network because every node is a potential sender, receiver and router. This drawback would again take us back to the IntServ model where several separate flow states are maintained.

2.3 Conclusion The merit and limits of both IntServ and DiffServ are reflected in the trade-off between scalability and level of QoS performance assurance. Neither a pure IntServ nor a pure DiffServ model is suitable for Ad Hoc Networks. In order to make use of advantages of both models and avoid the disadvantages, a combination of DiffServ and IntServ as described in section 2.1.3 could be an interesting approach.

5

6

Chapter 2. QoS Models for MANETs

Chapter 3

Protocol Design Issues 3.1 Towards developing a QoS Framework for MANETs In the last chapter it was shown that MANETs propose different requirements to quality of service infrastructures than wired networks do. Neither a pure IntServ nor a DiffServ approach is satisfying. The following sections identify some of the fundamental issues to be considered when designing a quality of service infrastructure for MANETs and helps classifying existing protocols later on.

3.2 QoS from a Layered Perspective A network’s ability to provide a specific QoS depends upon the inherent properties of the network QoS itself which span over all the layers in the network. Adaptation The physical layer should take care of changes in transmission quality, for example by adaptively inQoS creasing or decreasing the transmission power. SimSignaling ilarly, the link layer should react to the changes in link error rate, let’s say by including the use of auNetwork QoS Routing tomatic repeat-request technique. QoS-Routing and Layer QoS-Signaling operate at the network layer in orLink der to search for routes with sufficient resources QoS MAC Layer or to allocate and release bandwidth respectively. Finally, QoS-adaptation hides all the environmentrelated features from the awareness of multimedia applications. Moreover it provides an interface for applications to submit their requirements and is responsible to dynamically react to QoS changes for a certain flow, according to these requirements. This document does not treat MAC layer or physical layer issues any further, but instead concentrates on the issue of end-to-end QoS control over IP, meaning QoS-Signaling in particular.

3.3 QoS-Signaling and Routing Interaction In order to improve the performance of the QoS framework in a dynamic environment, QoS-signaling and routing can be coupled. There are three scales of coupling [15][17] which are described as follows:

8

Chapter 3. Protocol Design Issues The de-coupled option refers to the fact that QoS and routing mechanisms operate independently of each other and the QoS implementation is not dependent on a particular routing protocol. Changes in the network topology have to be handled by actively monitoring the network (for example by sending periodic monitoring messages). In a loosely coupled approach QoS-Signaling and routing interact with each other. Interaction can be understood as bi-directional. Some routing protocols allow upper layers for installation of upcall procedures to be called whenever a route changes. This might significantly decrease the reaction time of the QoS-Signaling to restore a certain reservation for a flow rerouted. On the other hand QoS-Signaling could provide feedback information to the routing layer regarding the route chosen and ask the routing protocol for alternate routes if the route provided doesn’t satisfy the QoS requirements. Another example is to let signaling query the forwarding table directly. Pre-allocation would be an appliance for such an approach. Despite of these benefits any kind of interaction between QoS-signaling and routing may lead to a solution which is dependant on the specific routing protocol. This shortcoming can be minimized by designing a generic interface to access the routing layer and to develop adapters for a concrete routing protocol implementing this interface. In a closely coupled approach, the same signaling mechanism is used to propagate the routing and QoS information, what mostly refers a unique QoS-routing protocol. QoS-routing tries to search for routes to a given destination with respect to the QoS requirements. Having a such strong coupling between QoS control and Routing does of course lead to very fast flow restoration but also has some major drawbacks. First the solution is dependent on the routing protocol used. This is currently not suitable because routing in MANETs still underlies heavy research and there is no ’one’ routing protocol to be used in future. Second the route computation with this strategy may take too long[4] or be too complex. The next few sections discuss QoS-Signaling as well as different strategies for bandwidth allocation and adaptation.

3.4 QoS-Signaling: Design Issues QoS-Signaling is used to reserve and release resources, set up, tear down, and renegotiate flows in the networks. There are a few issues to be considered when designing a QoSsignaling protocol (especially in MANETs) as to how the control information is carried along with data and how the flow path is established.

3.4.1 In-band versus Out-of-band Signaling The term ’in-band signaling’ refers to the fact that any control information is piggybacked into the packet header. Hence in-band signaling systems could be more efficient for wireless networks in case of route adaptation. The signaling path will always follow the data path, even in cases when the route has changed because of a failure of an intermediate node. This leads to very fast flow state restoration times. ’Out-of-band signaling’ on the other hand uses explicit control packets. This approach can be characterized as ’heavyweight’ because extra information is carried in the network and consumes more network bandwidth. Moreover in out-of-band signaling systems, signaling packets must have higher priority than data packets in order to achieve on-time notification. This can lead to a complex system where performance will degrade substantially. The benefit of this approach is that it is more scalable since the control messages don’t rely on the transmission of data packets. Furthermore the supported services can be rich and powerful.

3.4 QoS-Signaling: Design Issues

3.4.2 Reservation Mechanism: One-pass versus Two-pass If the resource reservation is done by a two-pass mechanism, then in the first pass (sender initiated) end-to-end information (like bandwidth availability) of the specific connection is gathered. This allows for detection of any bottleneck nodes within the path. The actual reservation is made in a second pass (receiver initiated) considering the available QoS of the connection. Suppose a path comprises three nodes A, B and C with corresponding bandwidth 300K, 200K and 300K. In a first pass node B would be detected as a bottleneck due to its available bandwidth of 200K, which is the minimum on this path. An actual resource reservation in a second pass right after will not try to request more than this 200K because it cannot be provided anyway. Two-pass based reservations avoid wasting of resources but their drawback is their latency. The need for two control messages to be sent slows down the reservation process. This could be critical in a highly dynamic environment where paths have to be re-established frequently. In addition two-pass mechanisms assume bi-directional routes between the nodes. That means if A can reach B, it must be given that B can reach A as well. This assumption is not automatically true in ad hoc networks for several reasons. First routing is not guaranteed to by symmetric, second a route may change between the first and the second pass and last, wireless links often do not show symmetric behaviour at all. Reservation schemes based on a one-pass mechanism fix these shortcomings of the twopass approach using only one control message to do the actual reservation, regardless of any end-to-end information. This makes the mechanism very stable and flexible in reaction time but results in a potential bandwidth waste. Given the scenario above and assuming that there a is a bandwidth request of 300K, nodes A and C would be able to satisfy the request but node B would not. As a consequence it may happen that for a short period of time 300K of bandwidth are allocated on these two nodes but never used.

3.4.3 Soft-state versus Hard-state As to the method of keeping resource reservation, two states can be defined: Soft and Hard state. For hard state, once the reservation is established, the reserved resource and the reservation record is always kept. This happens until an explicit release message is sent. Soft state reservation has a lifetime. When a reservation is established, a timer is triggered. Within a certain time period, specific signaling or traffic will update the soft state reservation and reset the timer. Otherwise, when the timer times out without receiving any refreshing messages, the soft state reservation will be released. Hard state based reservation is simple and efficient. It needs no signaling to keep the reservation alive, and no timing processing has to be done either. Only the release message is mandatory. In a mobile ad hoc network, soft state reservation is the more suitable approach. The wireless connection is unstable, and apt to be broken. Once a mobile node has lost its connection with the network, it might not have a chance to send any signaling for hard state release. So the reserved resource would permanently be kept unused. Soft state management may easily solve this problem because the reservation state just times out.

3.4.4 Local Repair Local Repair is a mechanism which a signaling protocol should employ in order to achieve fast and efficient flow restoration in case of route changes. ’Local’ means that signaling is kept within a very small area, end-nodes must not be involved. Consider the following scenario: In a network with four nodes A, B, C and D node A sends stream data to node D

9

10

Chapter 3. Protocol Design Issues using a route over node C. It is assumed that accurate quality of service is already provided along this path. Now at a certain time node C starts moving and finally gets out of node A’s transmission range, routing then finds a new path from A to D over node B. Local Repair is now in charge to detect the route change and to restore the best possible quality of service on the new path as well as to delete the old reservation. The goal is to re-establish reservation as quickly as possible and at the same time keep the signaling overhead low. There are several approaches to do this, which can roughly be classified into ’Pro-Active’ and ’Re-Active’. Pro-Active Pre-Active local repair mechanisms try to reserve the required quality of service for a given flow in advance, that means before the old path is broken and a new one is established. This can be done by either trying to guess route changes in advance, using node movement tracking or transmission quality measurements, or by excessive resource allocation. In the latter case signaling just reserves resources on every possible path, eventually through inspecting the routing forwarding table. Both strategies do have the shortcoming that they potentially waste bandwidth due to their over-reservation, excessive allocation in particular. Re-Active Re-active signaling protocols do not reserve any resources in advance, instead they try to react to route changes as fast as possible. The easiest way to achieve this goal is to be triggered by the routing layer whenever a route changes. Another possible solution is to detect route changes for a certain flow by periodically sending monitoring messages. It is assumed that the performance of such an approach hardly depends on the interval by which monitoring messages are sent.

3.5 QoS Adaptation In contrast to a wired network, the QoS situation in a MANET may change rapidly and dramatically all the time due to wireless link characteristics or mobility. For example even if the signaling provides a very fast local repair mechanisms it is not guaranteed that after a path breaks, the same quality of service can be granted on the new path. Under certain circumstances it may happen that an active flow is rerouted to a bottleneck node which causes the end-to-end bandwidth of the flow to decrease. On the other hand, the available bandwidth will increase if less traffic is in the network or if any application releases its reserved bandwidth. So applications can’t rely on the QoS investigation done during session establishment. To solve the problem the QoS framework has to actively monitor the network dynamics and adapt flows in response to observed changes based on some adaptation strategy. In the following sections a few concepts are discussed which might be helpful designing the adaptation part of a QoS framework.

3.5.1 Application Requirements As mentioned above, QoS-adaptation provides an interface for applications to submit their requirements. Some applications are capable to expand their QoS profile, so that instead of being a single value indicating the level of service needed by an application, it becomes a range of service levels in which the application can operate, together with the current reserved value within that range. This provides the network flexibility so that reservations can be maintained as network conditions change rather than forcing the network to make

3.5 QoS Adaptation a binary "admit/fail" decision for each flow. Applications request QoS by specifying the minimum level of service they are willing to accept and the maximum level of service they are able to utilize, and then adapt to the specified point within this range that the network commits to provide, which may change with time. Changes in allocation have to be signaled to the application, which adapts its behaviour to match to what is available. The following three adaptation strategies are based on the concept of bandwidth ranges.

3.5.2 Adaptation Strategies The adaptation strategy decides how and when QoS of a certain flow has to be investigated and determines how to react to QoS changes. See [12] for details. Greedy Strategy The Greedy adaptation strategy is the simplest possible. Regardless of any end-to-end information every node tries to allocate the bandwidth requested. Suppose a scenario with 4 nodes A, B, C and D with the corresponding bandwidth resources of 200K, 300K, 200K and 300K. Furthermore assume a bandwidth request for the path A, B, C, D of within a range of 200K minimum and 300K maximum, also written as [200K,300K]. Using a greedy adaptation strategy node B allocates 300K although node A is only able to grant 200K of bandwidth. Nodes C and D act the same. If for some reason the available bandwidth on node C increases, according to the greedy adaptation strategy node C immediately allocates additional 100K to have 300K reserved in total. This is done even though node A still is a bottleneck and the end-to-end bandwidth still is 200K. The idea is that it might be quite hard to reach maximum reservation in one pass, so bandwidth is increased stepwise. Maybe at some point node A as well gains further 100K of bandwidth and the whole end-to-end reservation will be 300K which finally can be adapted by the application. Bottleneck driven Strategy In a bottleneck driven strategy each node would only try to allocate as much bandwidth as has been allocated already by previous hops for a certain flow, except the first node in the path of course which always tries to allocate maximum bandwidth. This avoids temporarily bandwidth waste but on the other hand makes it very difficult to increase endto-end bandwidth for a flow. In the scenario discussed above each node would only reserve 200K of bandwidth in a first step, which is the same as the end-to-end bandwidth for this flow. But imagine the available bandwidth of node A and B would toggle between 200K and 300K. If they never reach 300K at the same time end-to-end bandwidth will never be increased. Fair Strategy As the number of application flows competing for resources increases, rather than simply refusing to admit new flows or pre-empting existing flows, a fair adaptation strategy attempts to adjust the allocation for each flow, so that all flows can be accommodated. The strategy attempts to give each flow the minimum bandwidth requested, plus a fraction which is proportional to the requested bandwidth range. Suppose a scenario of a few nodes where each of them provides 300K of bandwidth. Assume a QoS request for a range of 150K to 230K bandwidth. There is no problem for the network to provide maximum bandwidth for this flow. But as soon as a second request arrives, for say 100K to 120K, using the same path or just a part of it, not even the minimum bandwidth could be granted. In case

11

12

Chapter 3. Protocol Design Issues of a fair strategy the first flow would be adjusted to run with its minimum of 150K, what would allow the second flow to run with its minimum as well. The remaining bandwidth of 50K (300 - 150 - 100) could be shared between both flows according to their bandwidth range, which would result in a final reservation of 190K for the first flow and 110K for the second. The major drawback of a fair adaptation strategy is its signaling overhead due to adjusting active flows. However it would be interesting to test such an approach within a simulation environment.

3.5.3 Monitoring Interval and Soft-state Timer As mentioned in section 3.5.2, an adaptation Strategy not only determines how to react on QoS changes, but also decides when and how frequently the available QoS for a fixed flow has to be investigated. If QoS investigation is done by periodically sending monitoring messages the time interval by which these messages are sent is an important factor and should be dependent on the network condition. For example if node mobility is high in a MANET or the network is unstable, then more frequent monitoring is needed in order to adapt to bandwidth fluctuations. On the other hand the monitoring interval time should also be dependant on the actual bandwidth of the flow. The aim is to keep the amount of data constant which potentially could be sent in case of increased bandwidth availability or which could be lost in case of bandwidth degradation. It does not make sense for a flow running with 100K to monitor the network as frequently as a flow running width 300K does. But when bandwidth ranges are used then the actual bandwidth of a flow is conditioned by the adaptation process itself which on his part reacts to QoS changes. To make it even worse let’s focus on another parameter mentioned in section 3.4.3. In a soft-state based framework the question arises of how large to choose the timeout interval. Actually the size of the timeout interval should be a direct function of the monitoring messages because they update the soft state. The problem is just that the soft state timeout is usually managed by each node within a path while the monitoring interval is specified by end nodes only.

3.6 Conclusion During this chapter several design issues concerning QoS-Signaling and QoS-adaptation were discussed in more detail. These concepts are not distinct from each other, often they can be combined. As in the example of soft state and hard state, one could use explicit reservation release messages in a soft-state based framework even though it is a hard-state concept. However these concepts should facilitate classifying existing technologies as it is done in the next chapter.

Chapter 4

Existing Technologies This chapter describes some of the currently existing QoS technologies. Based on the concepts identified in the last chapter assets and drawbacks of each approach are pinpointed.

4.1 RSVP As mentioned in chapter 2, RSVP [25][19] is a typical IntServ protocol for the fixed IP networks environment. It was designed to enable senders, receivers and routers of communication sessions to communicate with each other in order to set up the necessary router states to support the quality of service requested by the application. A communication session is identified by the combination of destination address, transport-layer protocol type, and destination port number. RSVP is a classic two-pass protocol using out-of-band signaling. The messages used are the Path message, which originates from the traffic sender, and the Resv message[6], which originates from the traffic receivers. The primary roles of the Path message are first to install reverse routing state in each router along the path, and second to provide receivers with information about the characteristics of the sender traffic and end-to-end path so that they can make appropriate reservation requests. Resv messages finally carry reservation requests to the routers along the distribution tree between receivers and senders. RSVP state is "soft-state", after a certain expire time, the state of the path and the reserved resource is released. Periodical issuing of Path or Resv messages are necessary to keep the reservation alive. Additional signaling information allows the soft state timeout to adapt to the refresh period. Furthermore RSVP provides a routing triggered local repair [8] mechanism to overcome the need for a very fast refresh rate in order to react to route changes. There are many shortcomings of RSVP when used in MANETs: The two-pass reservation model employed by RSVP is not suitable for MANETs, specially in case of local repair. RSVP is based on a fixed QoS level approach. As a consequence no mechanism for a fast adaptation to QoS changes can be provided. To solve this problem reservation requests should specify ranges of values instead. Due to its out-of-band approach, RSVP produces a significant signaling overhead. This may be of importance if the refresh rate high because the message size is not negligible in RSVP. A high refresh rate might occur when no route-changenotification service from the routing layer is available. This causes local repair to fail.

14

Chapter 4. Existing Technologies As an IntServ based protocol RSVP lacks of scalability. The amount of state information increases proportionally with the number of flows what causes storage and processing overhead. Although the scalability problem may not be likely to happen in current MANETs due to the limited size of the network and the bandwidth of wireless links, one could argue that it will occur with the development of fast radio technology and potential large number of users in the near future.

4.1.1 RSVP Extensions Forced by the shortcomings of RSVP in Wireless networks, some approaches were made to enhance the signaling protocol[18]. Most of them intend to solve micro-mobility issues in infrastructure based wireless networks and do not address MANET problems directly. However MRSVP and DRSVP, two extension of RSVP to support mobility and dynamic network environments, try to overcome some of the disadvantages of RSVP mentioned above and are discussed in the following sections.

MRSVP MRSVP[24] addresses mobility issues of a mobile node changing the point of attachment to the fixed network and follows a Pro-Active approach as discussed in section 3.4.4. Two types of reservations are defined in MRSVP: active and passive reservations. Active reservation makes the resource exclusively reserved for the flow, no additional traffic is allowed to use the reserved resource. Passive reservation is different, it makes resource reservation in advance before the flow uses it. These passive resources are open to any other traffic until the flow actually needs the reservation. In order to make reservations in advance, it is necessary to specify the set of locations the mobile host may visit in future. The mobile node thus passively establishes paths with sufficient resources to a possibly large set of attachment points the mobile host eventually moves to. When the node arrives at a particular point of attachment, the path to that attachment becomes active and the path to the previous one passive, so that the data can still be delivered effectively. Even though MRSVP ensures good QoS provision in case of route change it suffers from many drawbacks when used in ad hoc networks. MRSVP is designed for mobile wireless access networks not for MANETs. The concept of a mobile node and attachment points is not given in ad hoc networks where every node is a mobile having many attachment points. Adapting MRSVP to MANETs would result in a very large set of possible locations a path for a given flow Many resources are reserved that may never be used. Even though they are available for other requests it requires the nodes to maintain a lot of state information regarding active and passive reservations. It may be very difficult to accurately determine the set of nodes to which a certain flow eventually is routed. Like RSVP it does not support any QoS adaptation, relying on the reservation in the initial phase. Neither the current QoS is monitored nor bandwidth ranges are used. Considering one flow, reservation signaling has to be sent from each node in the path to all the possible neighbours. This causes a huge overhead and makes the approach almost unusable.

4.2 FQMM DRSVP DRSVP[16] aims to overcome the shortcomings of RSVP in terms of QoS adaptation. By treating a reservation as a request for service somewhere within such a range, flexibility needed to deal with network dynamics is gained. As available resources change, the network can readjust allocations within the reservation range. If resources decrease below the level currently allocated, the network can offer a more reasonable response than simply dropping the reservation. In addition DRSVP provides a fair adaptation strategy as discussed in section 3.5.2. The available bandwidth is divided up among admitted flows, taking into account the desired range for each flow. DRSVP definitely addresses one of the major shortcomings of RSVP, namely the adaptation process. Using bandwidth ranges is a reasonable approach to tackle the problem of QoS adaptation. But DRSVP does still not solve all the other problems of RSVP, like local repair or signaling overhead.

4.2 FQMM FQMM[14] (Flexible Quality of Service Model for Mobile Ad Hoc Networks) combines the IntServ and the DiffServ model discussed in the first chapter. Three kinds of nodes are defined, exactly as in DiffServ. An ingress node is a mobile node that sends data. Interior nodes are the nodes forwarding data for other nodes. An egress node is a destination node. The basic idea of FQQM is that it uses both the per-flow state property of IntServ and the service differentiation of DiffServ. This is achieved by preserving per-flow granularity for a small portion of traffic in the MANET, given that a large amount of the traffic belongs to per aggregate of flows, that is, per-class granularity. A traffic conditioner is placed at the ingress nodes where the traffic originates. It is responsible for re-marking or discarding packets according to the traffic profile, which describes the temporal properties of the traffic stream such as transmission rate and burst size. FQMM is an interesting attempt at proposing a QoS model for MANETs, however it suffers of major problems: FQQM aims to tackle the scalability problem of IntServ. But without an explicit control on the number of services with per-flow granularity, the problem still exists. Due to its DiffServ behaviour in ingress nodes, FQMM may not be able to satisfy hard QoS requirements[26]. It could be difficult to code the PHB in the DS field if the PHB includes per-flow granularity, considering the DS field is at most 8 bits without extension. How to make a dynamically negotiated traffic profile is a well-known DiffServ problem (see 2.2.2) and FQMM seems not to solve it.

4.3 INSIGNIA INSIGNIA[22][21] is a signaling protocol designed explicitly for MANETs. It supports fast flow reservation, restoration and adaptation algorithms that are specifically designed to deliver adaptive real-time service. INSIGNIA implements an in-band approach by encapsulating some control signals in the IP option of every data packet (see figure 4.3), which is now called INSIGNIA option. Furthermore flow state information is kept in every node of

15

16

Chapter 4. Existing Technologies

Service Mode

Bandwidth Indicator

Payload Type

RES/BE

BQ/EQ

MAX/MIN

1bit

1bit

1bit

Bandwidth Request MAX

MIN

16bit

Figure 4.1: ASAP/ns Insignia Option Field a particular path. This is done in a soft-state manner as explained in section 3.4.3, that is, the flow state information is periodically refreshed by the received signaling information. In the following the basic operation of the signaling system is described with respect to INSIGNIA IP option. INSIGNIA offers a one-pass reservation (3.4.2). When a source node wants to establish a reservation to a destination node it sets the reservation (RES) mode bit in the INSIGNIA IP option service mode of a data packet and sends the packet toward the destination. The bandwidth request field allows a source to specify its maximum (MAX) and minimum (MIN) bandwidth requirements. On reception of a RES intermediate routing nodes execute admission control to accept or deny the request. When a node accepts a request, resources are committed and subsequent packets are scheduled accordingly. In contrast, if the reservation is denied, packets are treated as best effort (BE) mode packets. In the case where a RES packet is received and no resources have been allocated, the admission controller attempts to make a new reservation. This is a re-active local repair mechanism (3.4.4) and commonly occurs when flows are rerouted during the lifetime of an ongoing session due to host mobility. The bandwidth indicator field of INSIGNIA option plays an important role during reservation setup and adaptation. Reception of a setup request packet with the bandwidth indicator bit set to MAX indicates that all nodes encountered have sufficient resource to support the maximum bandwidth requested. On the other hand, a bandwidth indicator set to MIN implies that at least one of the intermediate nodes between the source and destination is a bottleneck node and the maximum bandwidth requirement may not be met. When a reservation is received at the destination node, INSIGNIA checks the reservation establishment status. The status is determined by inspecting the IP option field service mode, which should be set to RES. If the bandwidth indication is set to MAX, this implies that all nodes between a source-destination pair have successfully allocated resources to meet the QoS requirements of the source node. In contrast if the bandwidth indication is set to MIN this indicates that only the minimum bandwidth can be currently supported. As a result "partial reservations" will exist between source and bottleneck node, these resources remain reserved until explicitly released. QoS reporting message can be sent by destination nodes to inform source nodes of the ongoing status of flows. They do not have to travel on the reverse path toward a node. The INSIGNIA system supports two QoS report commands in order to provide some kind of adaptation. A scale-down command requests a source either to send with the rate specified as MINIMUM instead of MAXIMUM or to send its packets as best effort instead of MINIMUM depending on the current sending rate of the source node. This will have the effect of clearing any partial reservation. A scale up requests a source node to initiate a reservation for some MINIMUM or MAXIMUM rate, depending on the actual flow state. Although INSIGNIA presents a quite promising approach to QoS support in ad hoc networks, the system still lacks of some basic mechanisms:

4.4 Some further Approaches

17

Max. Reserved Min. Reserved

QoS report: bandwidth indicator = MIN

Node Mobility

Figure 4.2: ASAP/ns Insignia Monitoring The most frequently mentioned drawback of INSIGNIA in literature is its scalability problem due to the flow state information which is kept within the nodes of a certain path. This is an inherent problem of IntServ but it is doubtful whether it will be of importance for MANETs in future (see 2.2.2). INSIGNIA’s bandwidth usage is not efficient. The extra reservation on the path from the sending node to the bottleneck is a waste of bandwidth until an explicit release message is sent. Although this waste won’t last long, topology changing of MANET will make this reservation waste propagate frequently. Furthermore releasing partial reservations using QoS reports enforces source nodes either to set the bandwidth indicator of the INSIGNIA option field to MINIMUM or to send the packets as best effort depending on the actual flow state. In both cases the opportunity to scale up is lost. INSIGNIA does not provide any mechanism to dynamically change the frequency by which control signals are inserted into the data packets. This imposes a major processing overhead on the network. Only two bandwidth levels to be used are offered, MINIMUM and MAXIMUM. A more fine-grained approach would be needed in order to satisfy application requirements and to fully exploit the resources available.

4.4 Some further Approaches 4.4.1 iMAQ iMAQ[1] is a cross-layer architecture to support the transmission of multimedia data over a MANET. They use a location-based pro-active QoS-Routing. Neither hard QoS guarantees can be provided nor are any resources reserved. Because cross-layer designs and QoSRouting are not within the scope of this document, the iMAQ approach is not considered any further.

4.4.2 INORA INORA[11] is a QoS support mechanism that makes use of the INSIGNIA in-band signaling and TORA routing protocol for MANETs. INORA represents a QoS-signaling approach in a loosely coupled kind of manner. The idea is based upon the property of TORA to provide multiple routes between a given source and destination. While INSIGNIA does

18

Chapter 4. Existing Technologies not take any help from the network with regard to redirecting the flow along routes which are able to provide the required QoS guarantees, INORA gives feedback to the routing protocol on a per-hop basis to direct the flow along the route that is able to satisfy the QoS requirements of the flow. Beyond doubt the concept of ’loosely coupling’ QoS-signaling and routing is a very promising approach and the shortcomings of INORA mostly are the shortcomings of INSIGNIA. However, the interface for signaling to access routing should be as generic as possible in order to guarantee portability.

Chapter 5

ASAP Framework ASAP[27] (Adaptive ReServation And Pre-Allocation QoS Architecture) provides adaptive QoS support to real-time applications in infrastructure based wireless IP networks. The goal of this thesis is to extend the ASAP framework to be used in mobile ad hoc networks and to implement and simulate it on the ns-2 simulator later on. This chapter describes the ASAP framework by giving a conceptual overview first and explaining the signaling system in more detail later on.

5.1 Concepts 5.1.1 Soft/Hard Reservation In ASAP, a new reservation concept, soft/hard reservation, is created for efficient resource allocation. The concept is quite similar to the passive/active reservation mechanism presented by MRSVP (4.1.1). Soft reservation can be considered as the claim of a flow for a certain amount of bandwidth to be used in future. Hard reservation instead enables a flow to exclusively reserve some bandwidth. The actual reservation mechanism is two-pass based. When a new real-time flow is about to run, a soft reservation request is sent first. If there are enough resources available, the requested bandwidth will be soft reserved for the flow. Because a soft reservation is only a claim, the reserved bandwidth is still open to any other flow for temporary usage. After a soft reservation is established, the end-node sends a HR message requesting the same amount of bandwidth. This hard reservation will remove all the traffic occupying the corresponding soft reserved bandwidth. So after a hard reservation, the QoS traffic can immediately start running with its necessary QoS support. The goal of introducing two kinds of reservations is to achieve good performance in QoS monitoring and stream upgrading/downgrading.

5.1.2 Soft-State Management ASAP follows the concept of reserving resources in a soft-state manner as described in chapter 3. That means, reservations have to be refreshed periodically in order to prevent timeouts, which would cause the resource to be released. Currently, ASAP does not provide any dynamic coupling of soft-state interval and refresh period, instead the timeout interval can be set up on a per-node basis. Because of the different characteristics of soft- and hard reservation, both timeout intervals are configurable separately.

20

Chapter 5. ASAP Framework

Flow Label 0 1 0

SrcAddress Host1 Host1 Host2

SoftResv 100 50 150

HardResv 100 100 0

Flow ID

Figure 5.1: QoS Table

5.1.3 Adaptive QoS Monitoring QoS monitoring packets will periodically investigate the QoS situation on every node within a certain path. HR messages are sent whenever the end-to-end QoS changes. In order to adapt to various network conditions the monitoring interval can be set dynamically. For example if the network is unstable, then more frequent monitoring is needed in order to adapt to bandwidth fluctuations. In contrast, if the network is stable, processing overhead can be saved by keeping the monitoring rate low.

5.2 Signaling System ASAP provides efficient in-band signaling for the purpose of resource reservation, management, adaptation and releasing. The signaling is designed to produce as little overhead as possible and at the same time provides most flexibility.

5.2.1 QoS Table Every node within the network stores information for each real-time flow having a reservation on that specific node. The per-flow information stored comprises a flowID uniquely identifying the flow and the actual soft and hard reservation for the flow. The set of all tuples stored within a node is called QoS table. Table updates are triggered upon receiving signaling messages.

5.2.2 Message Types There are two types of messages in the ASAP architecture: SR (soft reservation) and HR (hard reservation). These two messages correspond to the two types of reservations mentioned above. But not only resource reservation, also QoS monitoring and adaptation are realized by these messages. Generic Message Format Figure 5.2.2 illustrates the generic message format to be used by both, SR and HR message. How exactly this control information is carried by a normal data packet in order to provide in-band signaling will be described section 5.3. What follows is a brief explanation of each field shown in figure 5.2.2. Message Type Indicator: The reservation indication (RI) field specifies the actual message type. When a packet passes the network, routers first check its RI field. According to its type, corresponding processing will be triggered. Currently three

H ardR eservation Ms g

SoftR eserv ation Msg

5.2 Signaling System

21

SetBW

ActualBW

Src Address RI

QoS Option

Flow ID Option Flow Label

MinBW

MaxBW

ActualBW

Figure 5.2: Generic Message Format types are defined: NON means the packet is normal data, SOFTRES and HARDRES correspond to soft and hard reservation message. QoS Option: The QoS option carries all the QoS information needed by the signaling. The internal structure is message type specific. FlowID Option: The FlowID Option contains information to uniquely identify a flow. In ASAP, a flow is identified by the combination of source address and flow label. The source address is globally unique and the flow label is randomly generated by the source node, so it is unique within all the flows generated by that particular node. SoftReservation Message An SR message sets the RI field to SOFTRES and defines the QoS Option to be as shown in figure 5.2.2. Three fields are provided within the QoS option: MinBW corresponds to the minimum bandwidth requirement for the particular flow. MaxBW is defined to be the maximum amount of bandwidth the application asks for and ActualBW finally represents the actual reserved bandwidth for the flow at a certain time including the soft and the hard reservation part. HardReservation Message On the other hand an HR message sets the RI field to HARDRES and defines the QoS option as shown in figure 5.2.2. The option field provides two parameters to be set. SetBW contains the amount of soft reserved bandwidth to be switched into hard reservation and ActualBW is defined to be the actual bandwidth reserved, exactly as the SR message does.

5.2.3 Setup Procedure To setup a new real-time flow, the sender host first generates an SR message for some specific MinBW/MaxBW values. Upon receiving a such a message, an intermediate node creates an entry in its QoS table, reserves as much bandwidth as possible within the scope of MinBW/MaxBW and updates both, the QoS table and the ActualBW field of the message (this is done only if the reserved bandwidth is less than the original value). When an

22

Chapter 5. ASAP Framework

SoftReservation Msg MinBW

Real-time Application

MaxBW

Real-time Application

ActualBW 100

Bottleneck

300

100

0

300 200

100

100

300

Host1 300K

300

200

Host2

0K

200K

300

0K

100

200

Host3 300K

300

0K

Host4 300K

0K

Figure 5.3: Soft reservation setup HardReservation Msg Real-time Application

SetBW

Real-time Application

ActualBW

Bottleneck 200

200

200

200

200

200

Host1 0K

Host2

200K

0K

200K

200

200

200

Host3 0K

0

200K

Host4 0K

200K

Figure 5.4: Hard Reservation SR message arrives at a receiver node, the ActualBW field corresponds to the end-to-end bandwidth availability. The receiver then replies with an HR message setting the SetBW field equal to ActualBW, so that each node on the path switches its soft reserved bandwidth into hard reservation and releases any potential extra reservation. As soon as the sender host receives the HR message, the necessary QoS support for this particular flow is established and the real-time flow can start running.

5.2.4 QoS Monitoring After a flow path is established, SR messages are periodically inserted into data packets. These messages collect QoS information and eventually perform soft reservations. The algorithm executed when receiving a SR message on a intermediate node is actually the same as used during setup and is shown below in code style: r e c e i v i n g _ m e s s a g e ( SR ) ; TotalResvBW = SoftResvBW + HardResvBW ; i f ( TotalResvBW < SR .MaxBW) { i f ( AvailableBW > = SR .MaxBW
TotalResvBW ) { SoftResvBW = SR .MaxBW
HardResvBW ; s o f t _ r e s e r v i n g ( SR .MaxBW
TotalResvBW ) ; } e l s e i f ( AvailableBW > 0 ) { SoftResvBW = SoftResvBW + AvailableBW ; s o f t _ r e s e r v i n g ( AvailableBW ) ; } TotalResvBW = SoftResvBW + HardResvBW ; }

5.3 Implementing ASAP using IPv6 SR . ActualBW = Min ( SR . ActualBW , TotalResvBW ) ; s e n d i n g _ m e s s a g e ( SR ) ; Due to the information provided by SR messages, the receiver host is capaple to keep track of the QoS situation on an end-to-end basis and therefore can immediately adapt to any QoS change by sending an appropriate hard reservation. Adaptation means to upgrade whenever additional resources get available and to downgrade under degraded conditions. The following code illustrates how a receiver host reacts to a SR message: r e c e i v i n g _ m e s s a g e ( SR ) ; i f ( SR . ActualBW ! = HardResvBW ) { c r e a t e _ m e s s a g e (HR ) ; HR . SetBW = SR . SoftBW + SR . HardBW ; HR . ActualBW = 0 ; s e n d i n g _ m e s s a g e (HR ) ; }

5.3 Implementing ASAP using IPv6 5.3.1 IPv6 in a Nutshell IPv6[20] is the "next generation" protocol designed by the IETF to replace the current version Internet Protocol, IP Version 4 ("IPv4"). Basically IPv6 provides the following enhancements: Bigger address space Mobility Built-in security The bigger address space IPv6 offers is the most obvious enhancement it has over IPv4. While today’s Internet architecture is based on 32-bit wide addresses, the new version has 128-bit technology available for addressing. Thanks to the enlarged address space, workarounds like NAT (Networks Address Translation) do not have to be used anymore. This allows full, unconstrained IP connectivity for today’ IP-based machines as well as upcoming mobile devices like PDA’s and cell phones. When mentioning mobile devices and IP, it’s important to note that a special protocol is needed to support mobility - called "Mobile IP". IPv6 provides built-in mobility support and thus allows for roaming between different networks using global notification when leaving one network and entering the other one.

5.3.2 IPv6 Header Format IPv6 defines a base header, which is mandatory, and a few optional extension headers to be inserted in between base header and upper-layer headers in a packet. In order to connect these headers the common NEXT HEADER field can be used. This actually forms a daisy chain of headers.

23

24

Chapter 5. ASAP Framework Base Header An IPb6 base header is simpler than an IPv4 header. Some rarely used field like IHL, FRAGEMENT OFFSET and HEADER CHECKSUM are removed and two new fields are added instead: FLOW LABEL and CLASS. FLOW LABEL is a 20-bit field to be used by a source to label sequences of packets for which it requests special handling by the IPv6 routers, such as non-default quality of service or "real-time" service. Although the concrete usage of the field is still under discussion, it is believed that in the future, FLOW LABEL will be used as flow identifier mainly for the IntServ model[9]. The CLASS field is an 8-bit field evolved from the TOS field in IPv4. It is available for use by originating nodes and/or forwarding nodes to identify and distinguish between different classes or priorities of IPv6 packets. Like in the case of FLOW LABEL, the concrete usage of the CLASS field is still under experiment and discussion. However the field seems to be destined for DiffServ QoS support. RFC2474 proposes a renaming of the CLASS field into DS (Differentiated Service). The DS field should be composed of 6-bit DSCP (Differentiated Service Code Point) field and a 2-bit unused field, for which no suggestion of how to use it is defined yet. Extension Headers Six additional extension headers are defined in IPv6: Hop-by-Hop options header Routing header Fragment header Authentication header Encrypted security payload Destination options header The Routing header is used to specify a list of intermediate nodes to be visited on the way to a packet’s destination. This function is very similar to IPv4’s Source Route options. The Hop-by-Hop Options header is used to carry information that must be examined by every node along a packet’s delivery path. In contrast, the destination options header will only be examined by the packet’s destination node. Authentication header, Encrypted payload and Fragment header will not be discussed here.

5.3.3 Using IPv6 for ASAP Signaling As ASAP is an in-band signaling system it uses the packet’s header to carry all its control information. In case of IPv6 this information can be transmitted within the base header and/or within any extension headers. ASAP uses the two undefined bits of the CLASS field as discussed in a previous section to transmit its Message Type indicator. Furthermore the IPv6 Hop-by-Hop options header is perfect container for ASAP’s FlowID option and the QoS option as these informations are intended to be processed by every node along a certain path.

5.3 Implementing ASAP using IPv6

IPv6 Base Header Next Header = HopByHop

DSCP

Ver

25

HopByHop Header Next Header = TCP

TCP Segment

RI

Class

Flow Label

Payload Length

Next Header

Next Header Hop Limit

Hdr Ext Len

QoS Option

Option Type

Option Len

FlowID Option

Source Address (128 bits) Destination Address (128 bits)

Figure 5.5: ASAP message embedded in an IPv6 header The whole structure of an ASAP message embedded within an IPv6 header is shown in figure 5.3.3 Up to now it was never mentioned how ASAP aims to build a virtual path between sender node and receiver. This has to happen somehow because an HR message intends to switch soft reservation into a hard bandwidth reservation for a given flow. To achieve this, an HR message must follow the reverse path of the corresponding SR message. There are two basic opportunities to do this: One possible approach would be to store previous hop information in every node, related to a particular flow. Another solution would be to use the IPv6 routing header. Both approaches collect path information during soft reservation to be used by the HR message later on.

26

Chapter 5. ASAP Framework

Chapter 6

Ad Hoc Extensions for ASAP ASAP as it is described in the previous chapter is designed for infrastructure based wireless IP networks, in particular for a last-hop-wireless topology. To achieve seamless handover the protocol comprises some mechanisms to pre-allocate resources on a potential new access point. These features were not mentioned because they’re irrelevant within this document. Instead our focus is on how to modify the ASAP framework to be well suited for MANETs.

6.1 Problems of ASAP in MANETs As described in chapters 1 and 3 MANETs impose special requirements on QoS. Even though ASAP makes use of in-band signaling and fast adaptation, the protocol fails to meet some MANET specific demands. This section shows several problems of ASAP in a mobile ad hoc environment.

6.1.1 Flow Restoration Imagine the following scenario: In a network with four nodes A, B, C and D B Missing Reservation: node A sends stream data to node D usA Flow Restoration Needed ing a route over node B. Assume maximum quality of service is provided along D this path. Now at a certain time node C C starts moving and finally gets out of node Node Mobility A’s transmission range, routing then finds a new path from A to D over node B. Because no reservation is established at node B the flow is transmitted using best effort. This state is kept until the next SR message detects the missing reservation and triggers node D to send a hard reservation message, which will finally repairs the reservation on node B. The repair mechanism as described has at least two major shortcomings. First the latency for such a two-pass based flow restoration can be quite long, especially when a path comprises many hops. This is because reparation involves both end nodes and detecting a missing reservation can only be as fast as the soft reservation refresh period. Thus, the worst-case reparation time is twice the end-to-end delay if route change happens right after

28

Chapter 6. Ad Hoc Extensions for ASAP

D

SR Message

B

HR Message

F

A

C

E

G

Figure 6.1: Reverse Path the sending node (in our scenario this would be node A). The second problem is that detecting a missing reservation cannot be signaled to the receiving node in some cases (hard reservation leak). This happens whenever a path is rerouted on a new node that is able to provide the actual end-to-end reservation. Bandwidth will be soft reserved on the node but there is no reason to change the ActualBW field of the message because the field represents the sum of both hard and soft reservation part. As a consequence an end node will not detect any QoS change and will therefore not send any hard reservation to switch the soft reserved bandwidth into a real reservation. To overcome these shortcomings a new flow restoration mechanism has to be designed. The goal is to reduce latency and to guarantee proper restoration.

6.1.2 Reverse Path Problem As described in the last chapter, a hard reservation message is supposed to follow the reverse path that is previously established during soft reservation. This could be hard to achieve for several reasons. First, routes may change quickly in MANETs. A path established during soft reservation may be outdated while hard reservation is going on. Second, routes do not have to be symmetric. Although physically two nodes can reach each other in one hop distance that does not mean routing also behaves like this. This could result in a big latency for hard reservation messages. See figure 6.1.2 for an illustration. A soft reservation is sent along the path A, C, E, G but the corresponding hard reservation message takes a much longer way using G, F, E, D, C, A. The third problem related to reverse paths occurs when wireless links are not symmetric. Even if a node A can reach B in one hop distance it is not given that node B is able to reach A as well. As a consequence there may be no way for a hard reservation to pass through. The two-pass protocol used in ASAP seems not to be flexible enough to meet the demands of mobile ad hoc networks. The topology is just too dynamic and requires an approach which is more simple.

6.1.3 Lost Hard-Reservation Messages In case of a hard reservation getting lost some kind of starvation may occur. The following scenario is used to illustrate this: Assume three nodes A, B and C and some soft reservation request sent along this path. Furthermore assume every node to be able to provide maximum service. Upon receiving the soft reservation message node C checks whether the ActualBW (includes soft and hard reservation) field within the message corresponds to the end-to-end bandwidth information he is keeping. If both values are unequal the adaptation process updates himself and sends a hard reservation message out in order to allocate or to release bandwidth. Suppose the message gets lost right after sending, what happens? No

29

H ardR eservation Ms g

SoftR eserv ation Msg

6.2 Extensions

SetBW

RI

MinBW

ActualSoft

QoS Option

MaxBW

ActualHard

Flow ID Option

ActualSoft

ActualHard

Figure 6.2: Extended Message Format subsequent soft reservation message will trigger any hard reservation if the path condition (bandwidth allocations on the nodes) stays the same because the adaptation process already did update his ActualBW value. This state is kept until the end-to-end bandwidth for the flow changes somehow, that means until a soft reservation message arrives at node C having an ActualBW value that is unequal to the one stored by the adaptation process. If no node is moving and bandwidth isn’t fluctuating either this may take a while. So a concept is needed to overcome this shortcoming. Hard reservation messages must be triggered until the reservation is actually done.

6.2 Extensions Based on the shortcomings described in the previous section ASAP has to be redesigned in order to provide fast flow restoration and short reaction times to topology changes. To achieve this some new mechanism are developed: Local Repair and Dynamic Virtual Path. Furthermore the adaptation algorithm is slightly changed.

6.2.1 QoS Option Field for Soft-Reservation Message In order to support the mechanisms described below the QoS option field is modified to be as illustrated in figure 6.2.1. Instead of having one field indicating the actual bandwidth reserved the soft and hard reservation part is now defined separately.

6.2.2 Local Repair Local Repair addresses the lack of ASAP to provide fast flow restoration. In section 3.3 three scales of coupling between routing and QoS-signaling were discussed. It was shown that a loosely coupled approach might help to improve flow restoration after rerouting. On the other hand any dependencies between routing and QoS-signaling should be avoided. The solution developed within this thesis provides mechanisms that can be used in both ways, in a totally routing-independent manner or as a loosely coupled approach whenever routing provides the necessary functionality. The goal was to provide a basic service regardless of whatever routing looks like, but to improve the service if routing is able to bring some support.

30

Chapter 6. Ad Hoc Extensions for ASAP Concept The concept is rather simple. A local repair is triggered by a soft reservation message. Upon receiving a soft reservation message the node tries to soft reserve some bandwidth within the specified range and updates table entries as usual. Before passing the message to the next hop the node checks whether its actual hard reservation corresponds to the hard reservation specified within the received message or not. If both values are equal nothing has to be done and the soft reservation message is sent along the path. Otherwise the node releases any additional reservation if the actual hard reservation specified is smaller than its own hard reservation for that flow or tries to allocate additional resources if the specified value is greater than its own. Both releasing and allocation of bandwidth has to be done with respect to the range and the amount of soft reserved bandwidth for that flow. That means, a node must only allocate additional hard reservation if enough soft reservation is available to be switched. ... r e c e i v i n g _ m e s s a g e ( SR ) ; s o f t _ r e s e r v i n g _ a n d _ u p d a t i n g _ t a b l e s ( SR . MinBW , SR .MaxBW ) ; i f ( HardResvBW < SR . HardBW ) { i f ( SoftResvBW > = SR . HardBW
HardResvBW ) { h a r d _ r e s e r v i n g ( SR . HardBW
HardResvBW ) ; } e l s e i f ( SoftResvBW > 0 ) { h a r d _ r e s e r v i n g ( SoftResvBW ) ; } } else { h a r d _ r e l e a s i n g ( HardResvBW
SR . HardBW ) ; } ... Monitoring based Local Repair As each soft reservation message represents a potential claim for local repair, a monitoring message and even a flow setup message at the same time no further features are needed to provide a base service for fast flow restoration. It depends now on the refresh period how fast local repair can be. Monitoring based local repair can be seen as a base service which is always available due to its independence from any underlying routing protocol. Routing triggered Local Repair It was mentioned in chapter 3 that some routing protocols allow upper layers for installation of upcall procedures to be called whenever a route changes. One should take advantage of this feature if available. Suppose a route change occurs on a certain node and the signaling layer receives a corresponding upcall. All that has to be done is to send out a soft reservation message for each flow affected by this change. Routing triggered local repair should be considered as an enhancement to monitoring based local repair if the necessary support can be provided.

6.2.3 Dynamic Virtual Path Dynamic Virtual Path addresses the problem of unsymmetrical routes and links causing difficulties for hard reservation messages to follow the reverse path established during pre-

6.2 Extensions

31

SR Message

D B

HR Message

HC = 2

F MAXHOPCOUNT = 2

HC = 1 HC = 1

A

HC = 2

C

E

HC = 1

G

Figure 6.3: Dynamic Path vious soft reservation. The idea is to add a hopcount field to the hard reservation message that is reset on every node belonging to the path and incremented on every other. Furthermore a global MAXHOPCOUNT constant is defined. If hopcount reaches MAXHOPCOUNT on a certain node the hard reservation message is not processed any further but sent directly to the source node specified within the flowID of the message, regardless of the route the message will take. Temporary there may be a partial reservation on the path while some nodes stay untouched. But as the hard reservation message is received by the sender, the node updates its QoS entry for that flow by setting actualSoft and actualHard to the corresponding values within the message. The subsequent soft reservation message will then trigger a local repair as described in the previous section in order to switch any soft reserved bandwidth into hard reservation on all the remaining nodes. The approach as explained solves the problem of unsymmetrical links, the problem occurring in case of lost hard reservation messages still exists. Therefore a stable adaptation process is needed that is able to deal with such scenarios.

6.2.4 Adaptation Within this section it is assumed that if there is a path from a node A to another node B, there is also a path back from node B to node A, although the two paths might be different. Due to the modifications made at the QoS Option field the adaptation process is now able to treat changes in soft and hard reservation separately. A slight modification on the adaptation algorithm allows to overcome the problem of lost hard reservation messages: r e c e i v i n g _ m e s s a g e ( SR ) ; i f ( SR . SoftBW > 0 ) { c r e a t e _ m e s s a g e (HR ) ; HR . SetBW = SR . SoftBW + SR . HardBW ; s e n d i n g _ m e s s a g e (HR ) ; } i f ( SR . HardBW < HardResvBW ) { c r e a t e _ m e s s a g e (HR ) ; HR . SetBW = SR . HardBW ; s e n d i n g _ m e s s a g e (HR ) ; } HardResvBW = SR . HardBW ; Each adaptation process holds information about the actual end-to-end hard reservation for each flow. Upon receiving a SR message the node checks whether there is some soft reservation available to be switched into real reservation or not and sends hard reservation

32

Chapter 6. Ad Hoc Extensions for ASAP message out if necessary. Otherwise the adaptation process compares the end-to-end hard reservation with the value it is keeping. If the received one is smaller a hard reservation message is sent in order to release any extra reservation between sending node and bottleneck. In any case the adaptation process updates its hard reservation to be equal to the value specified within the message sent. This mechanism is tolerant to lost hard reservation messages and even provides detection of hard reservation leaks (see section 6.1.1 in case of path rerouting).

6.3 Conclusion Three major problems of using ASAP in MANETs were presented in the beginning of this chapter considering flow restoration, reverse path and lost hard reservation messages. The solution provided within this thesis is based on an extended QoS Option field treating soft and hard reservation separately. A local repair mechanism is used to overcome the problems related to the inertness of two-pass based reservations like the big latency during flow restorations. The reverse path problem is addressed by using dynamic virtual paths. Finally a slight modification on the adaptation algorithm helps to improve the stability of signaling with respect to lost hard reservation messages.

Chapter 7

Implementation 7.1 Overview This chapter describes the implementation of the ASAP framework using the ns-2 network simulator [3] (from now on referred to as ASAP/ns). The chapter starts giving a brief introduction to ns-2 with respect to protocol development in mobile environments. After defining the basic implementation requirements an architectural overview of ASAP/ns is presented. Subsequent sections then discuss each of the main components in more detail. All file system references mentioned within this chapter are relative to the actual ns-2 installation directory, which is used to be /ns-allinone-2.1b9a.

7.2 NS-2 The network simulator ns-2 is an object-oriented, discrete event-driven network simulator developed at UC Berkeley and USC ISI. It is a useful tool for conducting networks simulations involving local and wide area networks, but its functionality has grown during recent years to include wireless networks and ad-hoc networking as well. Ns-2 has gained popularity among participants of the research community, mainly because of its simplicity. It allows simulation scripts to be easily written in a script-like programming language, OTcl. More complex functionality relies on C++ code that either comes with ns-2 or is supplied by the user. This flexibility makes it easy to enhance the simulation environment as needed, although most common parts are already built-in, such as wired nodes, mobile nodes, links, queues, agents (protocols) and applications (i.e. ftp). Most network components can be configured in detail, and models for traffic pattern and errors can be applied to a simulation in order to increase its reality. Simulations in ns-2 can be logged to trace files, which include detailed information about received and transmitted packets and allow for post-run processing with some analysis tools. The following sections intend to outline some of the basic components of ns-2 - in particular those that are important for the implementation of the ASAP framework described later on in this chapter. The ns-2 distribution discussed within thesis is ns-allinone version 2.1b9.

34

Chapter 7. Implementation

Generated Packets

Agent Port Classifier Address Classifier

Link Entry Point

Queue

Link

Queue

Link

Figure 7.1: Wired Node

7.2.1 Nodes Nodes are fundamental in a simulation. They perform processing and forwarding of packets, and are therefore perhaps the most important entities among all network components of ns-2. The internal architecture of a node differs depending on whether the node is mobile or not.

Wired node A wired node is a compound of a node entry object and two classifiers, as shown in figure 7.2.1. The node entry is where packets first arrive. The address classifier examines the address field of a packet to check whether the packet is destined for the current node. Finally the port classifier determines which agent (protocol) at the node should receive the packet. If the packet is not destined for the current node, the address classifier decides on which link the packet should be sent. This is possible because routing constantly updates the address classifier.

Mobile node A mobile node is a node with extra functionality in order to provide mobile networking. Figure 7.2.1 shows the internal structure of such a node. In contrast to a wired node, a mobile node is connected to a wireless channel instead of a link. Also, mobile nodes may be moved within a topography, as opposed to wired nodes which remain stationary. The mobile node itself is a compound object, built from the following parts:

7.2 NS-2

35

Generated Packets

Agent Port Classifier Address Classifier

Link

Routing Agent

Entry Point Link Layer

ARP

Interface Queue

MAC

Propagation Model

Network Interface Wireless Channel

Figure 7.2: Wireless Node

an address classifier like seen in the wired node right before. It is used for handling packets to port classifier or routing agent. A port classifier as well, passing packets to the corresponding agent. A routing agent. A link layer responsible for converting network address to hardware addresses with the help of an ARP module an interface queue used for storing and scheduling of packets with respect to some well defined policies. a network interface that sends and receives packets over the wireless channel. a radio propagation model determining the signal strength of received packets, and hence, whether a packet can be received by a network interface or not. a wireless channel over which packets are distributed.

36

Chapter 7. Implementation

7.2.2 Packets Packets are the unit of exchange between objects in a simulation. They are built up of packet headers, corresponding to different protocols that may be used, and packet data. New protocols may add their own header types to the available ones, and unused packet headers may be turned off to save memory during simulations. The only mandatory packet header in ins-2 is the common header, hdr_cmn, mainly used for tracing and for measuring other quantities during a simulation.

7.2.3 Agents Agents represent endpoints where packets are generated or consumed, and are used for implementing protocols at various layers. Routing agents and traffic sinks are some examples of agents that are frequently used in simulations.

7.3 Implementation Requirements This section sketches some of the requirements the implementation finally ought to fulfill: Modularity: Message transmission, signaling processing, adaptation and application are separate functional units and therefore should be splitted into different building blocks. Well-defined interfaces have to be provided for these components to interact with each other. QoS Routing decoupling: The implementation must not be dependent on any routing protocol, instead ASAP/ns is expected to run on top of different MANET routing protocols like AODV or DSR, without need for any special configuration. Extensibility: ASAP/ns should provide an extensible framework. Future development and usage of special allocation or adaptation strategies must be easily possible as well as the extension of the existing message format by adding additional option objects. Node independence: Although the implementation is MANET driven it should not be bound to the mobile node architecture. Simulating ASAP/ns in a heterogeneous network might be of future interest.

7.4 Main Building Blocks In order to meet the requirements of modularity as indicated right before different protocol mechanisms are split up into separate building blocks. Figure 7.4 gives an architectural overview of ASAP/ns from a network layer point of view. The whole system is mainly divided into the following three parts: QoS management unit (QMU): The core unit of ASAP/ns residing on every node of a MANET dealing with all around signaling processing. Adaptation control unit (ACU): Upon receiving periodic monitoring messages the ACU decides how to react to QoS changes for a given flow according to some application specific strategy. In addition the ACU provides an interface for application requesting QoS.

7.5 QoS Management Unit

37

Real-time Server Core Application AQRU ACU

Intermediate Node QoS Signaling

QMU

QMU

LL

LL

Client ACU QMU LL

Queue

Queue

Queue

MAC

MAC

MAC

Phy

PHY

PHY

Figure 7.3: ASAP/ns Architecture Application QoS Request unit (AQRU): The AQRU is actually part of the application and decides which adaptation strategy to use. Furthermore it is responsible for adjusting the bandwidth of a given flow according to the feedback gained from the adaptation control unit (ACU). The following part of this chapter intends to describe each of these building blocks in more detail.

7.5 QoS Management Unit 7.5.1 Overview The QMU unit maintains path and reservation state on all ASAP nodes and generates and processes signaling messages, that means soft and hard reservation messages. Mainly the QMU can be seen as a black box having four connectors that allow for receiving of messages, performing bandwidth reservation and release respectively, upcalling the ACU and sending or forwarding messages. As protocols in ns-2 are implemented by so called agents, embedding the QMU component into a node object results in an architecture as shown in figure 7.5.1. Packets arriving at the node’s network interface are passed to the QMU by the classifier. In order to allocate bandwidth for a certain flow, the QMU performs some reservation on the node’s interface queue. A packet is sent or forwarded by handing it over to the classifier again. All the implementation code corresponding to QMU is located in the directory ns2.1b9a/asap/qmu/.

7.5.2 Internal Structure This section provides a deeper look at the internal structure of the QMU. Figure 7.5.2 zooms into the black box described above.

38

Chapter 7. Implementation

Upcall Generated Packets

QMU Address Classifier

Link

Routing Agent

Entry Point

Bandwidth Reservation Link Layer Interface Queue MAC Network Interface

Figure 7.4: QMU Overview ACU Upcall

SoftResv Deserialization Receive Packet

Serialization HardResv

Forward Packet

Reservation on Queue

Figure 7.5: Internal Structure of QMU Upon receiving a signaling packet the QMU first transforms the raw byte stream into a c++ message object. According to the message type, the object is dispatched to soft- or hard reservation processing where eventually some bandwidth will be allocated/released. In case of an end-node an ACU upcall is made. Otherwise the updated message object is serialized to be sent within a packet. So basically the QMU logic can be divided into two parts, namely message serialization/deserialization and reservation processing.

7.5.3 Message Serialization/Deserialization As mentioned in chapter 5 ASAP signaling is designed do be used in combination with IPv6. Unfortunately there is no such support in ns-2. So the approach made in ASAP/ns was to build a messaging framework having similar flexibility [13]. Each signaling message comprises a base header including the message type and a hop-

7.5 QoS Management Unit

ASAPObject

39

extends

QoS Option

extends extends

Flow ID

extends Previous Hop contains contains Extension

HopByHopHeader

Figure 7.6: Serialization Framework Count field as described in section 6.2.3. For any additional information the concept of Extension is provided. An Extension is a container object for additional headers. Headers are either simple objects or containers themselves. This concept refers to the idea of extension headers in IPv6. Up to now only a Hop-by-Hop option header is implemented but using a routing header might be interesting once too (see section 5.3.3). A Hop-by-Hop option header includes a QoS option object, a FlowID object and in case of a soft reservation message even a PreviousHop object. In order to construct a signaling message the Extension object has to be serialized and copied into the message payload. This is done by calling the getContents method of the extension which recursively collects the contents of all the objects within the container. Upon receiving a signaling message the payload has to be deserialized to get the Extension object. The container constructor can be used for doing this. To retrieve a certain object out of a container the getObject(int) method is called using the object’s ID as a parameter. Therefore calling getObject(HOPBYHOP) on Extension returns the Hop-by-Hop option header. Retrieving QoS option or FlowID out of a HopByHopHeader is in a similar way. Figure 7.5.3 shows the framework’s class hierarchy. ASAPObject serves as a base class to all other classes like Extension, HopByHopHeader or QoSOption. All the container functionality (addObject(ASAPObject), getObject()) is provided by ASAPObject (so every object is a potential container then). Subclasses only have to implement their own constructor and their getContents method in order to provide serialization and deserialization.

7.5.4 Reservation Processing Reservation processing as it is performed in ASAP/ns forces many components to interact. The following sections intend to describe these components and their relations briefly. Finally the whole reservation process is illustrated in a data flow manner. QoS Table As mentioned in chapter 5 each node holds a QoS table containing entries for all the flows having a reservation on that specific node. In ASAP/ns this table is indexed by the so-called sessionID, which is actually the same as the flowID except that it is a single integer value instead of a struct.

40

Chapter 7. Implementation An entry for a certain flow provides the following information: the amount of soft and hard reservation belonging to the flow the address of the previous hop; used by hard reservations to find the reverse path a network interface identifier which is of special interest for wired nodes having several links attached an expire time being refreshed by any signaling message arriving for that flow. Periodically a cleanup-timer iterates over a QoS table removing any expired entries. On the other hand, whenever a soft reservation message arrives at a node not having an entry for the particular flow, a new entry is built.

Resource Object Reservations for a certain flow are performed by modifying the appropriate flow entry of the QoS table. If some hard reservation has to be done then even the network interface queue must be updated. This is accomplished by calling the setHardRes(int sessionID) method of a special Resource object wrapping the interface queue. The reason for having such a Resource object is to clearly separate the reservation framework from the underlying queue that is part of the network stack.

SessionCtrl and AdmissionCtrl Actually neither QoS tables nor Resource objects are accessed directly. All the operations manipulating reservation states are managed by SessionCtrl and AdmissionCtrl objects respectively. Mainly these objects provide some kind of permission control, but they also offer extended functionality like transforming relative values into absolute ones. Moreover the AdmissionCtrl object provides an admitFlow() method to check whether a particular bandwidth allocation can be granted for a given flow or not.

ReservationCtrl As SessionCtrl and AdmissionCtrl both modify the flow’s soft and hard reservation, calls to these objects have to be synchronized somehow in order keep consistency. It must be guaranteed that upon any reservation change performed on the Resource object the according flow entry in the QoS table is immediately updated as well. To achieve this, a special ReservationCtrl unit is used, coordinating all the reservations on a certain node.

AdmissionCtrlManager There is always a one-to-one binding between controller objects (SessionCtrl, AdmissionCtrl) and controlled objects (QoS table, Resource Object). As a node may have more than one network interface as in the case of a wired node, several Resource objects and therefore the same number of Admission Controllers are potentially available. In order to manage these objects a special AdmissionCtrlManager object is provided within each QMU. It is responsible for returning the right Admission controller for a given flow.

7.5 QoS Management Unit

41

ACU Upcall

10

SessionCtrl Soft/Hard Resv

Forward Message

11 AdmissionCtrl Manager

0

8

QoS Table

6 ReservationCtrl 4

5 AdmissionCtrl

QMU 2

7

Resource Object

3

9 1

Allocation Strategy

Reservation on Queue

Figure 7.7: ASAP/ns Reservation process Bandwidth Allocation Strategies As discussed in 3.5.2 there are many possible bandwidth allocation strategies like the Greedy strategy or the Fair strategy. The decision which strategy to use may depend on the certain network condition. ASAP/ns therefore provides a plug-in interface for bandwidth allocation strategies. It is then up to the actual allocation strategy to determine how much bandwidth to reserve according to a given request.

Get the Big Picture Figure 7.5.4 illustrates the whole reservation process performed upon receiving a signaling message. Comments to the numbers can be found below. 1. The AdmissionCtrlManager is consulted to get the right AdmissionCtrl object for the given session. 2. The retrieved AdmissionCtrl object is passed to the AllocationStrategy together with the QoS request specified. 3. In order to compute a reasonable bandwidth proposal with respect to the given request, the AllocationStrategy has to consulted the AdmissionCtrl to check for available QoS bandwidth. 4. After verifying the bandwidth request proposed by the AllocationStrategy, the request is taken over by the ReservationCtrl controlling the actual reservation process. 5. The ReservationCtrl passes the request to both SessionCtrl and 6. AdmissionCtrl 7. The SessionCtrl updates the particular session entry in the QoSTable. 8. The AdmissionCtrl performs the specified bandwidth reservation on a generic Resource Object 9. The Resource Object finally maps the reservation to the underlying Queue

42

Chapter 7. Implementation

7.6 Adaptation Control Unit The Adaptation Control Unit (ACU) is logically located above the QMU. Information is exchanged between these two entities using the ASAP and Adaptation interface defined file "common.h". The ACU is mainly concerned with reacting to QoS changes indicated by monitoring messages. It receives upcalls from the QMU whenever a signaling message arrives for which the particular node is an end-point. Potential QoS changes can be classified into two parts: Either a flow gains more end-to-end soft reservation (this may happen if more bandwidth gets available on a bottleneck node) or the actual end-to-end hard reservation for a flow decreases (caused by bandwidth vibrations in wireless links). Reactions to such changes are performed by a special adaptation strategy object that is supposed to be plugged in by the application. This reflects the idea of application-defined adaptation policies.

Adaptation Control Unit

Adaptation Interface ASAP Interface Adaptation Strategy

QoS Management Unit

Besides controlling the adaptation process, the ACU provides an interface to be called by applications. The interface comprises functions to create sessions, starting and stopping monitoring or changing the refresh period for a given flow. Moreover the ACU allows applications to install a procedure to be called whenever the hard reservation state of a flow is changed.

The implementation code for the Adaptation Control Unit can be found under ns-2.1b9a/asap/acu/.

7.7 Application QoS Request Unit The Application QoS Request Unit (AQRU) is part of the real-time application. It is in charge of translating the QoS requirements from the application to the format provided by the underlying ACU. Furthermore AQRU reacts to ACU upcalls by changing the flow’s transmission rate according to actual end-to-end hard reservation. As mentioned in the previous section, it is up to the application to decide which adaptation strategy to use. ASAP/ns only implements one, called Greedy Adaptation. The Greedy Adaptation strategy immediately hard reserves any newly gained end-to-end soft reservation for a given flow. Implementing AQRU has been done in OTcl. The corresponding file is asap-simulation.tcl and can be found under ns-src/asap/.

7.8 Some further Components This section describes some additional components not mentioned in the last three sections but building a not unimportant part of the whole implementation.

7.8.1 Queuing As shown in figure 7.5.1, actual hard reservations are performed on the network’s interface queue. Queues are networks components storing and forwarding packets according to some

7.8 Some further Components

43

Timer Data Entry

Signaling Entry

Packet

enque

deque

Packet

Figure 7.8: Flow based Queue well-defined policies. Ns-2 ships with a few built-in queues like FIFO (First In First Out), CBQ (Class based Queue) or DropTail, but it turned out that none of these really satisfies the requirements needed by ASAP/ns, which mainly are: Flow-based treatment Exact Bandwidth warranties Detecting Contract Violation Hence a special queuing system has been developed within this thesis, called Flow based Queue (FBQ). If a bandwidth reservation is performed on an FBQ, a separate subqueue is created for the given flow. The subqueue is responsible for properly forwarding any packets belonging to that flow; properly means according to the bandwidth reserved. A best-effort subqueue is available in every FBQ treating all the packets not belonging to any reservation. Queues in ns-2 are objects implementing the built-in queue interface, which basically has two methods, that is, a method to enque and one to deque a packet. When a packet is enqued into an FBQ its flowID is first computed using the IP header’s source address and flow label. If there is some bandwidth reservation available for the particular flow the packet is passed to the appropriate subqueue, otherwise the best-effort queue is used. Packet forwarding in subqueues is triggered by a special timer object. The timer inspects the first packet in the queue and schedules an event to happen at t = now + packetSize/bw. As the event occurs the packet is dequeued and placed into the outgoing queue of the FBQ object. This procedure is kept looping. If at some point the subqueue is empty the timer changes to sleeping mode and is first waked up when a new packet is enqued to that particular subqueue. There is one last issue to be mentioned according to this queuing thing. ASAP as it is described in chapter 5 is an in-band signaling system. In ASAP/ns this behaviour is simu-

44

Chapter 7. Implementation lated using some special treatment for soft reservation messages. If such a packet arrives at an FBQ it is not enqueued into the appropriate subqueue, but stored at a special signaling queue within that subqueue. If later on a normal data packet arrives for the particular subqueue, the data packet is dropped and the previous signaling packet is sent instead. This Flow based queuing system is well suited to be used in ASAP/ns. It allows for flowbased reservations, provides in-band signaling and guarantees exact bandwidth warranties. Furthermore contract violation is detected in a sense that a flow cannot transmit data faster than the subqueue reservation.

7.8.2 Measurements In order to keep track of several important parameters during simulation, a measurement system has been developed. A measurement object including evaluation parameters is created by the QMU agent on start-up and passed to all the network interface queues of the particular node. The queues periodically update parameters upon packet reception. On the other hand, the measurement object can be read and reset from the agent at any time.

7.8.3 Logging ASAP/ns provides a special Logging mechanism, which has been very useful for debugging. Every object in ASAP/ns extends the class Loggable that allows to install a special Logger object. Any log calls (having exactly the same signature as a printf command) within a certain object are redirected to this Logger object. Logger objects can either be turned off or on. Because a Logger object can be shared among different objects or even nodes logging in ASAP/ns can be handled very flexible. Furthermore logging on a group of objects can turned on or off at a certain time in simulation.

7.8.4 Node Interface One major problem to be tackled during implementation was to let ASAP/ns run on all the different ns-2 node architectures. This turned out to be rather complex because besides separation of wired and wireless nodes the node’s architecture in ns-2 is defined by the routing protocol. A node using DSR has a completely different structure than one using AODV for example. Hence the approach made in ASAP/ns was to encapsulate all the node and routing specific details into one class called NodeInterface. This class provides adapters for each node architecture and all the MANET routing protocols, that is, AODV, DSDV, DSR and TORA.

7.9 Conclusion This chapter described the implementation of the ASAP framework in ns-2, called ASAP/ns. Four major goals to be achieved were outlined at the beginning of the chapter: Modularity, Extensibility, Routing Decoupling and Node architecture independence. ASAP/ns meets these demands by using the following concepts: Clear separation of the three building blocks (QMU, ACU and AQRU), a container-based messaging framework and node encapsulation together with an AdmissionCtrl manager.

Chapter 8

Simulation and Analysis 8.1 Overview This chapter describes the evaluation of the ASAP framework using the ns-2 implementation ASAP/ns presented in the last chapter. The chapter is organized as follows: Primarily the generic simulation framework is outlined. The second part discusses the actual evaluation and is splitted among the several test scenarios. Each scenario is described by first explaining the simulation setup and analysing the result data afterwards. Like in the previous chapter, all file system references mentioned have to be understood as relative to the actual ns-2 installation directory.

8.2 Simulation Framework To unify the various simulations later on, some kind API has been created including several flow object and a some measurement procedures.

8.2.1 Flow Objects Three different flow objects are defined: BEFlow ASAPFlow MonoFlow A BEFlow object represents a best-effort Flow. Transmission rate, source and destination node have to be specified upon creation of such an object. Best-effort flows produce EXPOO traffic with an average packet size of 500 bytes. EXPOO traffic means packets are sent at a fixed rate during On periods, and no packets are sent during Off periods. Both On and Off periods are taken from an exponential distribution with means of 1s and 0.5 seconds respectively. An ASAPFlow behaves differently. It needs source node, destination node, minimum and maximum bandwidth to be specified. Min and Max values are defined as described in section 5.2.2. Upon creation, an ASAPFlow triggers a QoS setup procedure using the interface provided by the node’s ACU 7.6. After receiving an upcall indicating that the

46

Chapter 8. Simulation and Analysis reservation is properly set up the flow object starts a CBR traffic with a transmission rate corresponding to the bandwidth reserved. The packet size is fixed to be 125 bytes. MonoFlow’s are similar to ASAPFlow’s, but they provide a separate treatment of reservation setup and packet transmission. This allows the flow to be started without any QoS support first and to start and stop bandwidth reservation periodically later on.

8.2.2 Measurements A record function is provided retrieving and cleaning the measurement 7.8.2 values constantly every 1s. The values are both written to files to allow for over-time analysis and cumulated to enable comparisons between different simulations later on. The following measurement values are used throughout the simulations: The total throughput





  

measured on a certain node .
is the total amount of traffic received (in Bytes) at a node  and  denotes the interval during which the measurement has been done. The degraded throughput






   defined as the part of throughput on a node  that is caused by QoS traffic not having any reservation on the certain node.

is the amount of QoS data which has been sent using best-effort treatement and  is the measurement interval. The fraction of all packets belonging to some ASAPFlow but beeing treated as besteffort, which is defined as



 











where 
is the number of QoS packets treated as best-effort on node  and 
refers to the number of real-time packets sent on node  . The ratio of QoS packets dropped:



 

 










denotes the QoS packets which are dropped at node  and  
refers to the number of real-time packets sent on node . The total QoS packets violating ’Guaranteed QoS’:



  

 

The actual over-reservation defined to be as

 











where refers to the amount of bandwidth hard reserved on a node , 
is total number of bytes according to QoS packets received at a node i and  is the time interval where the measurement has been done

8.3 Evaluation

47

The actual over-reservation including soft reservation which is defined as









 
  








where and refer to hard and soft reservation on a node , 
is total number of bytes according to QoS packets received at a node i and  is the time interval where the measurement has been done.

8.2.3 A Remark in Advance Readers of the following section will notice that the flow transmission rates used during simulations are mostly quite slow compared to what is usual for real-time flows. This has been done to isolate the different reasons for which packets might be dropped. In order to simplify post-analysis of simulation experiments, QoS degradation should not be caused by wireless link interferences or packet collisions.

8.3 Evaluation The goal of the evaluation is on the one hand to prove for certain special situations that ASAP/ns functions properly. On the other hand the evaluation intends to show the performance and efficiency of some of the concepts used in ASAP/ns like local repair, adaptation or soft reservation.

8.3.1 Local Repair In the following experiment the impact of rerouting on QoS flows is investigated. Rerouting involves local repair to restore the actual reservation state. A key challenge for restoration is the speed at which flows can be restored. This is dependant on the speed at which new routes can be computed by the routing protocol if no alternative routes are cached and the speed at which the signaling system can restore reservations.

0

Node Mobility

2 4 1

Node Mobility

The simulation scenario consists of 5 nodes arranged 3 as illustrated in the figure beside. Two flows are being sent: A BEFlow with a sending rate of 64K from node 0 to node 4 and an ASAPFlow from node 1 to node 4 having a transmission range of [16K,32K]. The monitoring refresh rate used is 2s, the soft state timeout is fixed to be 16s. In order to induce rerouting the following movement events are triggered: at 20s: Node 3 starts moving towards node 2 at 27s: Node 2 starts moving upwards, leaving node 1’s transmission range at 30s. at 50s: Node 3 moves back to its origin at 80s: Node 3 starts moving upwards again These events cause both flows to be rerouted twice: Once at 30s where node 2 is finally getting out of range and once after node 3 is moving in for the second time, this happens at

48

Chapter 8. Simulation and Analysis

Best-effort Traffic QoS Traffic QoS Traffic treated as Best-effort

250

Throu gh put

200

150

100

50

0 1

51

101

Time

Figure 8.1: Localrepair about 85s. The period for which the link between node 1 and 3 remains broken is chosen to be around 20s to let the reservation on node 3 timeout. The measured values during simulation are throughput  and degraded throughput  .  indicates the local repair performance on node 2. This is reasonable because within a queue packets are treated as best effort if, and only if, there is no reservation for the particular flow (in contrast to contract violation where packets arrive at the queue faster than their according flow reservation and therefore are dropped). Figure 8.3.1 shows the simulation results. No throughput degradation can be noticed during the first rerouting event at 30s. This is because the new route (from node 1 to node 3) has been cached (or has already been computed because node 3 moved into node 1’s transmission range a while ago) and the available best-effort bandwidth was big enough to support the real-time flow for the short period of no-reservation (indicated by the red line). On the second rerouting event the throughput of the ASAPFlow is affected because a short burst of be-effort traffic consumes lot of bandwidth. But after the reservation is reestablished, the flow runs with its original rate of 64K again. The burst mentioned before happens because BEFlow-packets are stored within the queue during broken-link period and sent immediately when the new route is established.

8.3.2 Adaptation During the following experiment the adaptation mechanism of ASAP is investigated. The key point to figure out is how fast ASAP is able to react to bandwidth vibrations, but also the prove the correctness of the implementation in a sense that bandwidth vibrations only affect QoS flows if best-effort is already degraded significantly. As mentioned in chapter 7 it is due to the application to choose an appropriate adaptation strategy. The adaptation strategy used during the following simulations is the GreedyStrategy mentioned in chapter 3. The scenario chosen consists of 3 nodes arranged in s straight line. Two flows are being sent, both originating at node 0 and destined to node 2. The ASAPFlow runs with a transmission range of [32K,64K] while the BEFlow is sending with a rate of 128K. During simulation the link bandwidth of node 1 is manipulated. There’s a maximum fraction of link bandwidth to be used by QoS traffic, this value is fixed to be 0.7.

8.3 Evaluation

49

Link Bandwidth Best-Effort Traffic Received QoS Traffic Sent QoS Traffic Received

250

Throu ghp ut

200

150

100

50

0 1

51

101

151

201

251

301

351

401

Time

Refresh Period = 4 Refresh Period =16

9000

8000

T hrou gh pu t

7000

6000

5000

4000

3000

2000

1000

0 1

51

101

151

201

251

301

351

401

451

Time

Figure 8.2: Adaptation and Refresh Period In order to examine the correlation of adaptation performance and refresh rate, the experiment has been done twice with a refresh period of 4s and 16s respectively. The measured values are throughputs  and  reflecting the effect of link vibration and adaptation respectively. Figure 8.3.2a shows the simulation result using a refresh rate of 4 seconds. The first thing to observe is that link vibrations above 91K (  ) do not affect the ASAPFlow, this proves the correct behaviour of bandwidth reservations in ASAP/ns. Second the adaptation of the flow is quite agile to the link bandwidth changing. The latency between sent and received traffic adaptation is caused by the agility of the ASAP protocol, which is strongly related to the refresh interval by which soft reservation messages are sent (shown in Figure 8.3.2b.

8.3.3 QoS Performance This simulation is to show the QoS performance under different mobility conditions, that is, from 10 km/h to 100 km/h. The scenario consists of 20 nodes moving randomly within a 600m x 600m area with the specified maximum speed. 12 ASAPFlow’s are generated by 12 different sender nodes and randomly selected receivers, all running with a transmission rate of 16k. Furthermore 5 BEFlow are generated introducing background traffic. The soft

50

Chapter 8. Simulation and Analysis

QoS Packet Dropped QoS Packets treated as best-effort

12

Ra tio [% ]

10

QoS Degredation 8

6

4

2

0 10

20

30

40

50

60

70

80

90

100

Velocity [km/h]

Figure 8.3: QoS Performance

4.5

ASAP 10 km/h ASAP 100 km/h

4

Others 10 km/h Others 100 km/h

O ver-Re servat io n

3.5

3

2.5

2

1.5

1

0.5

0 44

36

30

26

22

18

14

10

8

6

4

2

Timeout [Seconds]

Figure 8.4: Overreservation reservation interval is fixed to be 1 second. The measured values during simulation are QoS Degradation , the fraction   of QoS packets treated as best effort and   , the QoS packets dropped. The simulation result is shown in figure 8.3.3. As the flow bandwidth is quite small comparing to the 2Mbps wireless link throughput, the amount of QoS packets dropped is within a small percentage regardless of node mobility. But packets, which are treated as best effort scale up along with increasing mobility. This is because the high movement speed leads to frequent path changes what makes it very difficult for ASAP to restore reservation states.

8.3.4 Reservation Efficiency  In order to show the reservation efficiency during a simulation the value of   used. The measured value indicates how much extra bandwidth is reserved than consumed by QoS   this means only the half of all the bandwidth reserved traffic, for example if   for real-time flows is actually used. One major difference of ASAP compared to other resource reservation protocols is its hard/soft reservation concept. While hard reservations belong to a certain flow and cannot be shared, the soft reserved part is still available to all

8.4 Conclusion

0.35

51

QoS Degredation ASAP Signaling

0.3

Ra tio [ % ]

0.25

0.2

0.15

0.1

0.05

0 1

2

4

8

16

Soft Reservation Interval

Figure 8.5: Signaling Overhead  other flows. The measured value   indicates the bandwidth waste in absence of such a concept. This is especially interesting when comparing ASAP to INSIGNIA for example where over-reservation is a major shortcoming.

The result in figure 8.3.4 states that reservation efficiency is correlated to the speed of mobility and the timeout period of the reservation state. If routes change frequently due high mobility, reservations are propagated in the network but rarely used, this increases the wasted bandwidth. The result also shows the advantage of the soft/hard reservation concept. Comparing to other signaling protocols not having such a mechanism, ASAP’s total reservation is less, illustrated by the two pairs of parallel curves in figure 8.3.4.

8.3.5 Signaling Overhead During this simulation experiment the relation of signaling overhead and QoS Degradation is investigated. The result shown in figure 8.3.5 proves what is to be expected. Obviously the interval of sending soft reservation messages directly affects signaling overhead, agility of ASAP and QoS traffic. The smaller the interval is, the more signaling overhead is brought to network, and the corresponding processing load increases. On the other hand, a small soft reservation keeps ASAP agile to routing changes and QoS vibrations, and minimizes QOS degradation, as illustrated in Figure 8.3.5. As mentioned in the previous chapter it is up to the AQRU unit to determine the soft reservation interval. This is a great benefit and allows for adaptively changing the soft reservation interval corresponding to the various network conditions.

8.4 Conclusion The simulation result described in the previous sections basically lead to the following conclusions: The adaptation behaviour of ASAP is quite promising but depends on the interval by which soft reservation messages are sent. But as the soft reservation interval is determined by the application it can be changed adaptively to changing network conditions. Frequent route changing caused by fast node movement affects the QoS performance in a sense that the amount of degraded QoS traffic increases if the topology changes more frequently.

52

Chapter 8. Simulation and Analysis Reservation efficiency is correlated to the speed of mobility and the timeout period of the reservation state. The soft/hard reservation concept introduced by ASAP reduces bandwidth waste significantly. There is a trade-off between signaling overhead and adaptation agility.

Chapter 9

Summary and Outlook 9.1 Summary Within this thesis the challenge of bringing QoS support to mobile ad hoc networks has been addressed. After having investigated some of the existing QoS models and protocols like RSVP, INSIGNIA or FQMM it turned out that none of these technologies are able to meet the demands of QoS in MANETs. Therefore a new QoS framework referred to as ASAP has been proposed in this thesis and further extended based on some well-defined design criterions. The framework includes a QoS signaling protocol and flexible allocation and adaptation mechanisms. In order to prove the framework’s correctness and efficiency it has been implemented and simulated using the ns-2 network simulator. The results gained during the simulation experiments were quite promising. It has shown that the feature to dynamically change the soft reservation interval and the concept of soft/hard reservation are the major benefits of ASAP. However, the network’s highly dynamic characteristics make it very difficult to maintain QoS support. In order to achieve good QoS performance and adaptation agility, frequent network monitoring using soft reservation messages is needed, but this increases signaling overhead and processing load. The simulations done during this thesis can only roughly reflect the behaviour of ASAP under certain scenarios. To see how ASAP performs in the "real world" it would be necessary to implement it in a real operating system.

9.2 Future Work There remains some future work to be done. A few ideas are listed below: Many simulation variants have not been examined yet, like for example the use of different adaptation or allocation strategies. Running simulations in heterogeneous networks using MobileIP would be very interesting. Implementing ASAP within a Linux or Windows operating system would show if the simulation results could be mapped to the real world. Enabling ASAP to support multicast could be a possible future work.

54

Chapter 9. Summary and Outlook

Acknowledgement I would like to conclude with extending my gratitude to Prof. G. Alonso, his reserach group and especially my assistant Jianbo Xue who offered this interesting thesis and supported me whenever I needed advice. I also thank my friends and all the fellows sufferers in HRS G9 who made working very comfortable.

56

Chapter 9. Summary and Outlook

Bibliography [1] imaq: An integrated mobile ad hoc qos framework. http://cairo.cs.uiuc.edu/adhoc/. [2] Ip qos support in the internet backbone. Technical report, Alcatel. [3] The network simulator ns-2. http://www.isi.edu/nsnam/ns/. [4] Andreas Kassler, Teodora Guenkova-Luy, Davide Mandator, Peter Schoo. Enabling mobile heterogeneous networking environments with end-to-end user perceived qos. Technical report. IST project IST-2000-28584 MIND. [5] D. Black. Differentiated services and tunnels, 2000. RFC2983. [6] R. Braden. Resource reservation protocol - version 1 message processing rules, 1997. RFC2209. [7] R. Braden, D. Clark, and S. Shenker. Integrated services in the Internet architecture: an overview. Technical Report 1633, 1994. [8] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin. Resource reservation protocol (rsvp) - version 1 functional specification. RFC2205. [9] A. Conta. A proposal for the ipv6 flow label specificatoin, 2001. www.ietf.org/proceedings/02mar/I-D/draft-ietf-ipv6-flow-label-00.txt. [10] Zeinalipour-Yazti Demetrios. A glance at quality of services in mobile ad hoc networks. 2001. Seminar in Mobile Ad Hoc Networks. [11] Dinesh Dharmaraju, Ayan Roy-Chowdhury, Pedram Hovareshti, John S. Baras. Inora - a unified signaling and routing mechanisms for qos support in mobile ad hoc networks. 2002. Proceedings of the International Conference on Parallel Processing Workshops. [12] Kurt Geihs. Analysis of adaptation strategies for mobile qos-aware applictions. 2002. Workshop on Modelling Analysis and Simulation of Wireless and Mobile Systems. [13] Marc Greis. Rsvp/ns: An implementation of rsvp for the network simulator ns-2. [14] Kee Chaing Chua Hannan Xiao and Winston K.G Seah. A quality of service model for ad hoc wireless networks. www.ece-icr.nus.edu.sg/journal1/fqmmhandbook02.pdf. [15] Alberto López, Jukka Manner, Andrej Mihailovic, Hector Velayos, Eleanor Hepworth, and Youssef Khouaja. A study on qos provision for ip-based radio access networks, 1999. IST project IST-1999-10050 BRAIN.

58

BIBLIOGRAPHY [16] N. Schult M. Mirhakkak and D. Thomson. A new approach for providing quality of service in dynamic network environment. http://www.mitre.org/support/papers/tech_papers99_00/thomson_mp_dynamic/thomson_dynamic.pdf. [17] Jukka Manner, Alberto Lopez, Andrej Mihailovic, Hector Velayos, Eleanor Hepworth, and Youssef Khouaja. Evaluation of mobility and qos interaction. [18] Bongkyo Moon and Hamid Aghvami. Rsvp extensions for real-time services in wireless mobile networks. IEEE Communication Magazine, 2001. [19] Robert Braden, Deborah Estrin, Steven Berson, Shai Herzog and Daniel Zappala. The design of the rsvp protocol. [20] R. Hinden S. Deering. Internet protocol, version 6 specification, 1995. RFC1883. [21] Xiaowei Zhang Seoung-Bum Lee, Gahn-Seop Ahn and Andrew T. Campbell. Evaluation of the insignia signaling system. [22] Xiaowei Zhang Seoung-Bum Lee, Gahn-Seop Ahn and Andrew T. Campbell. Insignia: An ip-based quality of service framework for mobile ad hoc networks. 1999. [23] Brooke Shrader. A proposed definition of ’ad hoc network’, 2002. [24] Anup Kumar Talukdar, B. R. Badrinath, and Arup Acharya. MRSVP: A resource reservation protocol for an integrated services network with mobile hosts. Wireless Networks, 7(1):5–19, 2001. [25] Paul P. White. Rsvp and integrated services: a tutorial. 1997. [26] Kui Wu and Janelle Harms. Qos support in mobile ad hoc networks. [27] Jianbo Xue. Adaptive qos-supporting architecture for real-time application in wireless ip network. Master’s thesis, 2002. www.inf.ethz.ch/personal/jxue/.