Xavier Sanchez-Loro

Josep Paradells
email: josep.paradells@entel.upc.edu

Jordi Casademont
email: jordi.casademont@entel.upc.edu

José Luís Ferrer
email: jlferrer@i2cat.net

Optimizing the Delivery Chain in Heterogenous Networks

Introduction

In previous work [START_REF] Sanchez-Loro | Dynamic content negotiation in web environments[END_REF][START_REF] Sanchez-Loro | Ubiquitous web access: Collaborative optimization and dynamic content negotiation[END_REF][START_REF] Sanchez-Loro | Ubiquitous web access and application layer optimization: Dynamic content negotiation over cellular links[END_REF][START_REF] Sanchez-Loro | A proxy-based solution for device capabilities detection[END_REF], we explored the possibilities of context-awareness, service discovery and negotiation as the basis to deploy ubiquitous services in heterogenous environments. First, we explored the concept of delivery context in the Ubiquitous Web, seeking ways to acquire context data from user devices and enhancing the available mechanisms for negotiation and context acquisition across the delivery chain. This way we worked with proxies to enhance server and client negotiation in heterogeneous web environments, allowing proxies to transparently detect device capabilities and personalizing context distribution and content negotiation according to user preferences, device capabilities and network environment. Furthermore, we explored the possibilities of using intermediaries to optimize web traffic by means of header reduction. One conclusion of this piece of work is that e-2-e principles of current Internet are not valid in heterogeneous environments. With such different underlying computing and networking technologies, we need more intelligence and autonomy in the network and means to adopt different protocol behaviours depending on underlying network environment and context. Using a model of autonomic proxies/middleboxes performing local adaptations at required network segments provides better results than plain-old e-2-e negotiation across the delivery chain.

All this work give us with enough insight in the field to conclude that Ubiquitous and Pervasive Computing requires more level of control and adaptation granularity than current networking models offer. We cannot made the network more pervasive and invisible at the Application level, indeed we need that the network stack itself becomes ubiquitous and pervasive. Thus, on further efforts [START_REF] Sanchez-Loro | Can Future Internet be based on constrained networks design principles? Computer Networks In Press[END_REF][START_REF] Sanchez-Loro | Proposal of a Clean Slate Network Architecture for Ubiquitous Services Provisioning[END_REF][START_REF] Sanchez-Loro | A Semantic Context-Aware Network Architecture[END_REF] we have worked in designing from scratch a semantic context-aware network architecture focused on the provision of ubiquitous services. This Future Internet (FI) architecture expands the concept of delivery context to support any type of service traffic, not just web traffic. So, we propose that intermediate nodes participate in the discovery, negotiation and adaptation of services. Hence, integrating service discovery, negotiation and adaptation as core features of the architecture. Besides, another important divergence of the architecture from TCP/IP stack is its layer-less modular nature, since it is based on SOA principles, and follows the model of RBA instead of OSI's one. Hence we designed a flow-oriented context-aware network architecture where communications are composed on the fly (using reusable components) according to the needs and requirements of the consumed service [START_REF] Tarifa | The Atomic Redesign of the Internet Future Architecture[END_REF].

New Networking Models for the Future Internet

The Internet is facing an architectural crisis as the load and stress on the Network increase with new users and applications. Current Internet architecture is becoming more and more ossified and complex; with lots of patches aimed to amend different issues that have arisen during its almost 40 years of existence. This patching has been done outside the core of the architecture, increasing its complexity and blurring -and sometimes even contradicting-the neat principles behind the original design of the Internet. Furthermore, new services and computing paradigms require new modes of interaction, new features (identification, context-awareness, seamless service discovery and composition, etc.) and clean solutions to known issues (mobility, security, flexibility, etc.); but it is not clear how the current Internet architecture will be able to cope with all these new requirements. In the research community, there are two approaches to solve this crisis: evolutionary and disruptive (clean-slate). Most of the initiatives fall in the category of clean-slate redesign, where the network architecture is designed anew from scratch. These initiatives exhibit some clear lines of research and similar approaches for certain issues. The main common lines of research are:

1. Redefinition of the layering concept and protocol design. These lines imply a complete redefinition of the network architecture. Most of the initiatives follow this trend in one-way or the other. Some approaches: (a) Questioning of the end-to-end principles of communication. e-2-e principles are not taken for granted and many initiatives depart from this communication paradigm.

(b) Changes from host/interface-centric paradigm to information/service centric paradigms. with all probability no one architecture will be the final solution and many of them will coexist in the future thanks to virtualization.

Herein, we will focus on proposing a service taxonomy and classification for RBA/SOA architectures aiming to model a common framework for the descrip-tion and composition of possible Atomic Services (ASs)1 or networking functions valid for architectures coping with heterogenous environments. The final objective is the fine-tuning the delivery chain to optimize application and delivery performance and behaviour. The paper is structured as follows: first we will introduce the concept of RBA in section 1.2 and how this model is key to understand the philosophy behind some of the most disruptive FI architectures. In section 2 we will analyze the available service definition in the field and propose a "common" service definition, valid for any type of networking service regardless the granularity, thus including support both for Atomic Services (ASs) and Composed Services (CSs). Once we have a clear definition of what a service is, we can propose a taxonomy in section 3 useful for classifying services for composition and allocation purposes in heterogenous environments. With this taxonomy at hand, we propose a service classification in section 4 which is suitable for our needs 2 . In section 5 we discuss some strategies fro the allocation of services along the delivery chain. Finally, section 6 concludes the paper.

RBA

From an architectural point of view, the most ground-breaking (and influential for our own research) proposal was, and still is, the RBA [START_REF] Braden | From protocol stack to protocol heap: rolebased architecture[END_REF], a non-layered and modular architecture built around the concept of roles. A role represents a communication building block that performs some specific function relevant to forwarding or processing packets. Therefore, new relations amongst network components are established by defining a set of roles to be played by each component involved. In this way, nodes implement the different roles required for a certain communication (i.e., "packet forwarding", "fragmentation", "flow rate control", "byte-stream packetization", "request web page", or "suppress caching"). The protocol stack in this architecture is replaced by a protocol "heap" in which each node's realm of execution in the protocol heap is restricted to the roles it exercises. Non layering thus implies new rules for modularity, header structure and ordering for the processing of metadata, as well as encapsulation. These new rules and relationships were (and still are) not fully investigated and unexpected synergies and incompatibilities may appear in implementing RBA-based architectures. This kind of micro-modularization, breaking existing protocols into small modules with a definite function, is common practice in most clean slate proposals [START_REF] Dutta | The SILO architecture for services integration, control, and optimization for the future internet[END_REF][START_REF] Müller | Future Internet Architecture -A Service Oriented Approach (Future Internet Architecture -Ein serviceorientierter Ansatz)[END_REF][START_REF] Touch | A Recursive Network Architecture[END_REF][START_REF] Jelger | Basic Abstractions for an Autonomic Network Architecture. A World of Wireless, Mobile and Multimedia Networks[END_REF]. While they are all aimed at improving flexibility, their key difference is the way in which modularization is approached (in terms of scope, focus, purpose and module granularity) and how network architecture and protocols are abstracted, defined and built on the basis of these modules, that is, how the architecture and communications are composed with these modules. All these synergies between different initiatives concentrate around the concept of service/role. Nevertheless there is no unified or commonly agreed service definition and taxonomy [?,?]. There are some timid approaches, but none fully developed.

Since RBA proposes a conceptual model, it can be implemented in different terms: disruptive or evolutionary. On one hand, a pure RBA architecture may be implemented with no layers at all and roles scope ranging from application all the way through to physical layers or perhaps just above a virtualized link layer. This would be the disruptive or clean-slate approaches, and it is the main trend for RBA-based architectures. On the other hand, it can be deployed as an evolutionary enhancement on top of the network layer or even just at the application level. The scope and definition of roles will be directly derived from the implementation scenario. Hence, a common definition of basic roles would be useful both for FI architectures and evolutionary solutions applying the concept at the Application layer.

This kind of micro-modularization, breaking existing protocols into small modules with a definite function, is common practice in most of clean slate proposals. They key difference is how this modularization is approached (in terms of scope, focus, purpose and level of granularity) and how network architecture and protocols are abstracted, defined and built on using these modules as basis; that is how the architecture and communications are composed with these modules.

Service Definition: What Constitutes a Service?

If we take a look on the literature of service discovery, Service-Oriented Architectures, protocol modularization and service/funtional composition fields, we can found different definitions of what is a service.

-RFC 2165-SLPv1: The service is a process or system providing a facility to the network. The service itself is accessed using a communication mechanism external to the the Service Location Protocol. -ATIS: Something of value being provided to and consumed by end-users of communications networks. A function that is performed by software whose output is used by some other entity. It may be, for example, a presence engine, or a routing function, or a number translation capability, or protocol interworking. 'Service' may also refer to the software itself. -W3C

• Web Service: A service is an abstract resource that represents a capability of performing tasks that form a coherent functionality from the point of view of providers entities and requesters entities. To be used, a service must be realized by a concrete provider agent. • An application that provides computational or informational resources on request. A service may be provided by several physical servers operating as aunit.

-OSAIS: The performance of work (a function) by one for another. Services are the mechanism by which needs and capabilities are brought together.

Broadly speaking, all these definitions are specifically tailored to certain application domains or computing solutions and are usually defined from the point of view of the applications that will consume them. There is no unified definition in the field of what constitutes a service that is generic enough to be usable to different service-centric approaches in different application domains.

Service Taxonomy

The following independent categories define a taxonomy valid for different types of services, regardless their granularity (see figure 1). This taxonomy aims to organize and ease role/service definition in SOA/RBA solutions and is inferred from our initial proposal of AS, published in [START_REF] Sanchez-Loro | Proposal of a Clean Slate Network Architecture for Ubiquitous Services Provisioning[END_REF]. Figure 1 illustrates graphically this taxonomy.

-Granularity: atomic, molecular, composed.

• Atomic Services are the core of our architecture. They are the building blocks (roles) used to establish communications and to deliver data in a self-adaptable, self-configurable and context-aware way. Each atomic service provides one concrete and well-defined networking function (along with the reverse function, if any). Different algorithms and implementations of an atomic service may exist (i.e. different congestion control algorithms), and co-exist in the same node, using attributes to both describe the different possibilities and to tune/configure the atomic service in order to use it to fulfill specific workflows needs. • Molecular Services are common compositions for small sets of ASs that usually work together to perform a more complex function than just a single ASs (e.g. sequencing and retransmission may be composed as two independent ASs, but they are often composed together in form of a molecular service). Using this intermediate abstractions can ease and simplify the composition process of bigger composed services. • Composed Services are network applications with a wider scope than just establishing communications (e.g. sensing service, directory service, file transfer, instant messaging, presence, etc.). Each composed service or application implies consuming different atomic and sometimes other composed services, with possible dependences appearing between them. In addition, they can involve one or more nodes, depending on the complexity of the service. -Execution/Distribution:

• Isolated : local execution of the service • Distributed : execution distributed between two nodes, regardless their location. It includes support for e-2-e, section and hop-by-hop distribution/allocation of services. -Scope: services can be applied with different scopes or considerations depending on the desired result.

• Network : services are executed to optimize communication according network context.

• Application: services are executed to optimize application behaviour and interconnection to meet application requirements according to context characteristics. -Usage: rules governing the service usage.

• Mandatory: usage of this service is mandatory as it i basic for establishing a communication (e.g. forwarding). • Optional : usage of this service is optional, its usage will depend on application requirements and context characteristics -Purpose: which is the purpose of the service.

• Delivery: to deliver data between two different entities involved in the delivery chain (they can be adjacent or non-adjacent nodes or they can be two end applications, depending on the scope of the service) • Mobility: services related to application, user and node mobility.

• Storage: services dealing with the storage of data.

• Security: services dealing with security issues.

• Data Adaptation: services dealing with adapting and transforming data for different objectives, interoperability, customization and optimization of data. • Addressing: services dealing with the identification and labeling of resources.

• Management: services dealing with the management of the different entities in the network (nodes, applications, services, etc.). • Signaling: services dealing with interchange of signaling and control data.

• Presentation3 : services dealing with the presentation of contents and user/application interfaces -Order: order/existence of the AS in workflow composition may be dependent of another service.

• Dependent.

• Independent.

Service Classification

The following tables (see table 1 andtable 2) show the different services that can be applied according to different purposes: Application and Network. 45

Allocation Strategies

One critical process during the negotiation of a composed service is the composition and allocation of AS to obtain a feasible workflow for each node involved in the communication; one that allows the fulfillment of the service requirements according to the context constraints. Thus, this process must perform the following analysis:

Granularity

Atomic Molecular Composed

Execution

Isolated Distributed e-2-e hop-by-hop section

Scope

Application Network

Usage

Mandatory Optional

Purpose

Delivery Mobility Storage Security Data Adaptation Addressing Management Signaling Presentation

Order

Independent Dependent

Fig. 1. Service taxonomy -Analysis of context constraints Vs QoS Requirements. Requirements should be checked against context constraints in order to obtain sets of possible AS. -Analysis of possible feasible AS configurations for the whole path (not for just isolated individual nodes) to fulfill service requirements with these context constraints. Obviously, this analysis implies knowing where the different AS are allocated in each configuration. For this analysis, we can adopt some techniques proposed in the field (see section 5).

Hence, as we can see, service composition and allocation are two interleaved processes that cannot be feasibly decoupled.

Implementing this process implies knowing two variables for each AS/AM: the cost and the benefit/effect of using it. Costs should be checked against context constraints, whilst effects should achieve QoS requirements. Therefore, metrics should be researched to measure the cost of executing an AS in different terms (e.g. CPU/RAM utilization, affected bandwidth, delay, etc.), although in the end all these metrics should be unified/normalized to use the same units in order to be suitable for expressing a cost function. Even it must be thoroughly investigated, at a first glance expressing costs in terms of delay with time units seems a good starting approach. However, our first impressions is that the benefits of using a certain AS have not a straightforward translation to a common unit, and it should be investigated even if it is possible.

When deciding which is the best workflow configuration for a composed service path, it is needed some tools to analyze the effect and the cost of using each configuration. After some research on the field, we have found some techniques and references that may be suitable for our purposes. This is the case of Wolf's layered graph approach [START_REF] Choi | Configuring sessions in programmable networks[END_REF], this technique allows to compute the cost of service allocation inside a network, by transforming it in a shortest-path problem, which can be easily computed using Dijkstra's algorithm. The key idea is to transform the network in a graph with multiple layers, where each layer represents the execution of a service. Then, the optimal path is found executing Dijkstra's algorithm for finding the shortest path in the transformed graph. Finally, the multi-layered graph is mapped back to the original network. This approach has some real good pros and some cons we discuss:

-It is suitable for computing the placement of multiple services.

But services are allocated in sequential order, thus not suitable for parallel service execution. In our virtual circuit model, for the purposes of allocation, services may be deployed sequentially. -Session-oriented . The algorithm assumes that the intermediate nodes and the network links used for communication are selected. This is the case of our architecture, since we use a virtual circuit model with a fixed path. -Bandwidth alteration awareness. The algorithm can be extended to be aware of the influence on bandwidth of using one service. For instance some services like compression have a cost, but decrease the required bandwidth.

In the opposite site, FEC increases overhead and, thus, the required bandwidth. This effect is reflected with bandwidth scaling factor. It should be investigated, but probably this extension of the algorithm (or a very similar one) may be applied for services affecting other network metrics like delay, probability error, etc.

-Optional processing . The algorithm can be used to incorporate the possibility of optional services, services that are not necessary for the correct data communication but can enhance the quality of the connection. -Multicast sessions. Multicast sessions may also be computed using this approach, but instead of a shortest-path problem, the resulting problem is a standard Steiner tree problem. -Capacity constraints. Although taking into account capacity constraints is clearly a NP-hard Hamiltonian path problem, which cannot be assured to find an efficient solution, least the lowest-cost path; the authors have proposed modification to Dijkstra's algorithm to incorporate capacity constraints, so that in most situations they can find low cost session configurations with the required resources. -Decided and ordered set of services. In this technique, services to be placed are decided beforehand. For purposes of adapting it to our proposal, we must decide first which sets of AS will be tested, so we can check the feasibility of a certain set of AS; but the algorithm cannot decide for us which are the services to be allocated. -Knowing costs and benefits. In order to be able to use this technique, we must envision a method to obtain the correct values for costs and effects of using the services. However, this is not a problem of this technique alone, whatever method we use to compute the allocation of services will require to know the cost and the benefit of using a service.

It seems quite obvious that this technique can help to compute the cost of a service allocation with a reasonable computation cost, but it is not straightforward how to use it for expressing effects. It must be investigated but one possibility to be researched is integrating the effects of services as a means to modify the cost, and thus, just checking if the modified cost complies with the context constraints and the service requirements. This can be feasible for those services where the cost and the benefit can be easily related; but this is not always the case (e.g. FEC increases delay and required bandwidth, but decreases PER). For those metrics that cannot be incorporated in the graph as a scaling factor, the benefit may be calculated with a new layered-graph where the benefit is computed as a cost, but inverted in order to keep the problem as a Dijkstra's shortest-path problem. Some of the shortcomings of these approaches for our case study is that they cannot take into account capacity constrains [28]; the exact services that will be used and the ordering of execution of these services are known before-hand, since they work with high-level and application level services and not with basic network services like ASs. So, in order to make these solutions work with our proposal we must devise ways to:

1. Compute the cost of using each AS in terms of computing and network usage 2. Decide what are the most appropriate ASs (and their configuration) to obtain a certain performance and behavior. This implies finding ways to infer the benefits of using a certain service. This may be a simple problem when dealing with independent services, but it can become complex when working with inter-dependent services (i.e. ACK and CRC). Furthermore, many ASs imply allocating two services, one at the input node and one at the output node, which further complicates the problem. 3. Determine the correct ordering of execution of ASs.

We are currently working on simple scenarios with a small subset of ASs, researching for interdependences and the cost and the benefit of using these services, both alone and in combination. We expect to obtain results in the following months.

Conclusion

TODO

Acknowledgments. This work is partially funded by MECD and FEDER project TEC2009-11453 and I2Cat Foundation Project TARIFA. The authors would like to express their thanks for contributions from the TARIFA project [START_REF] Tarifa | The Atomic Redesign of the Internet Future Architecture[END_REF] and the participating research groups: NETS, MediaEntel, GXO, ANA, Cols and GMT.

Table 1 .

 1 Service Classification for Application domain.

	Purpose	Service
	Delivery	Flow control/Rate control
		Error Control
		Object Control
		Flow Multiplex/Joining
		Monitoring
	Mobility	Portability
		Nomadism
	Storage	Cache
		Directory
		Store
	Security	Authorization
		Authentication
		Access Control
		Token Exchange
	Data Adaptation	Encoding/Transcoding
	Addressing	Labeling
	Management	Configuration
	Signaling	Session control
		Service Discovery
		Service Announcement
		Negotiation
	Presentation	Rendering
		Adaptation
		Encoding/Format
		Content Negotiation
		Interaction (Modality)

Table 2 .

 2 Service Classification for Network domain

	Purpose	Service
	Delivery	Congestion control
		Flow control/Rate control
		Forwarding
		Joining/Multiplex
		Forking/Splitting
		Aggregation
		Framing/Encapsulation
		Fragmentation
		Medium Access Control
		Acknowledgement
		Retransmission
		Sequencing
		Monitoring
		Negotiation
	Mobility	Inter-domain
		Intra-domain
		Handover
		Point of Attachment (Multi-path)
	Storage	Cache
		Buffering
	Security	Authorization
		Authentication
		Access Control
		Token Exchange
	Data Adaptation	Encoding/Transcoding
		Rate adaptation
		Channel adaptation
	Addressing	Labeling (flow, packets, etc.)
	Management	Configuration
		Network management
		Node management
	Signaling	Session control
		Route discovery
		Route setup
		Circuit setup
		Session Negotiation

Other terminology for ASs are roles, building blocks, functions...

Any service classification will be subject of controversy and lack of exhaustiveness. We think the proposed classification covers most of the aspects for optimizing service provisioning and connection performance, but it by no means an exhaustive list

This category is only available for services with application scope.

Each service includes the reverse function if any.

Transcoding is a coupled pair of Decoding/Encoding. Includes any data transformations, i.e. data transcoding, cyphering, compression, etc.

This work is partially funded by MECD and FEDER project TEC2009-11453 and I2Cat Foundation Projects TARIFA. The authors would like to express their thanks for contributions from the TARIFA project and the participating research groups: NETS, MediaEntel, GXO, ANA, Cols and GTM.


A Cuadra
email: acuadra@indra.es

F Mata

J L García-Dorado

J Aracil

J Vergara

F J Cortés
email: fcortes@telnet-ri.es

P Beltrán
email: pbeltran@telnet-ri.es

E De Mingo
email: edemingo@telnet-ri.es

A Ferreiro

J López De Vergara

Traffic Monitoring for Assuring Quality of Advanced Services in Future Internet

Keywords: QoS, network monitoring, Future Internet

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Future Internet must tackle the lack of built-in facilities to support non-basic functionalities in order to offer service-aware functionality [START_REF] Galis | Management and Service-aware Networking Architectures (MANA) for Future Internet System Functions, Capabilities and Requirements[END_REF]. Traditionally, the growth of the Internet and convergent services in the IP layer has been solved, as far as performance concerns, by increasing bandwidth and computational power in the edge devices. However, this trend is reaching its limits to provide Quality of Service (QoS); furthermore security and differentiated QoS, namely QoS as a service beyond the "best effort" packet delivery, which also takes into account specific applications characteristics, requires a new network-centric management architecture. Among their goals, the Future Internet service-aware architecture should include a cost-effective QoS management based on direct IP traffic monitoring so that network operators and service providers can verify their Service Level Agreement (SLA). Besides, combining traffic measurement systems with on-line analysis will help detecting malicious users or unintended configuration errors even in multi-operator scenarios and render Internet governance plausible. In summary, the transition from specific circuit-switched (CS) networks towards convergent packet-switched (PS) networks supporting real-time applications and numerous new broad-band services in a disaggregated market must be based on powerful yet intelligent traffic monitoring systems in order to guarantee cost-effective QoS, security and privacy protection. The objective is to keep the old CS networks facilities in the multiplexed Service Centric (SC) transport networks by means of additional control elements inside the network. So far only client devices and applications tackled these issues considering the operator could just offer them end-to-end (E2E) connectivity without any additional service. However, the required analysis to improve service architectures and diagnose configuration failures or critical dimensioning lacked significant traffic data from commercial networks. Numerous projects have developed measurement infrastructures to track Internet functioning [START_REF] Ferreiro | IP traffic monitoring for Future Internet management and governance[END_REF] and several research groups have actively participated in these efforts [START_REF]Cooperative Association for Internet Data Analysis[END_REF], [START_REF]The Traffic Monitoring and Analysis (TMA[END_REF]. Recent proposals to use such measurement facilities for network management have raised relevant problems such as privacy protection, leading to the development of anonymization solutions [5]. Besides, the access to heterogeneous traffic monitoring data is very challenging; thus, a semantic tool (mediator) has been developed [START_REF] Ferreiro | Semantic Unified Access to Traffic Measurement Systems for Internet Monitoring Service[END_REF], and standardization initiatives [START_REF] Ferreiro | Standardizing ontologies for the IP traffic measurement: A first step in QoS standardization at ETSI[END_REF] have been carried out in order to establish interoperable data formats, as well as KPI (key Performance Indicator) and other measurements to support QoS monitoring. This paper presents an architecture for service-aware networking compatible with Future Internet paradigms like resources virtualization and autonomic management within a network-centric approach. After a brief presentation of measurement devices developed by the authors, their application to service monitoring platforms and QoSdriven network management design are presented. Due to space limitations, results are rather given by reference so that a holistic view can be reached.

QoS datasources

Monitoring systems can be categorized according to the measuring devices. In fact, KPI can be derived from active or passive probes: The first ones inject packets into the network with explicit control of timing, scheduling and sizes [START_REF] Paxson | End-to-End Internet Packet Dynamics[END_REF], while the second ones just capture traffic in order to analyze it in terms of protocol performance and application modeling. Active methods are used to measure delay, packet loss, jitter, available capacity and connectivity. Passive methods are useful to measure network parameters like data rate, most-used services, traffic matrix, routing, etc. and derive traffic modeling or supervise specific applications, as well as to detect fraud or hacking. Deep Packet Inspection (DPI) systems analyze traffic in detail by decoding application protocol headers; thus their exploitation allows characterizing network traffic in detail and differentiated QoS analysis can be performed. Active and passive methods can be considered complementary since they provide information about different network characteristics and parameters [START_REF] Lindh | A new approach to performance monitoring in IP networks combining active and passive methods[END_REF] [START_REF]FP7-MOMENT (Monitoring and Measurement in the Next Generation Technologies)[END_REF].

Active probes are intrusive and overload the network with their traffic but are simple, can reproduce users behavior and may be distributed throughout the network for different tests simulating different devices (access ADSL / FTTH terminals GSM / GPRS / UMTS, etc..). A smart planning of tests, placement of probes and knowledge of the service to analyze is required to obtain a clear insight into end to end services by this means. Passive probes are non-intrusive equipment but analyze the whole traffic in the section of network considered (access point, for instance, or a core link). Their hardware must cope with the connection bandwidth and need a great amount of computational power to analyze the data they extract. Some network elements incorporate passive monitoring facilities, such as STP (signaling transfer point) probing its own SS7 links, DWDM multiplexers or port span switches with monitoring capabilities. Thus, these deployed network elements (WDM equipment line, HLR and MSC in GSM and UMTS SGSN and GGSN in GPRS and UMTS, IP Routers, etc) provide traffic information to the network operator: The data collection is mainly done through OMCs (Operation and Maintenance Center) developed by each provider, but is sometimes reached through a mediation device. The principal drawback is that the measures provided are defined by the supplier because of lack of standardization. Embedded agents are software pieces that can be introduced in a network element, such as a softswitch in an OLT (Optical Line Terminator), or in the customer's equipment, like a Set-Top-Box or a mobile terminal. These agents can act as active or passive probes and may be useful to monitor the perceived quality of service or QoE (Quality of Experience). Their main obvious drawback is the difficulty of deployment since they require the approval of manufacturer, service provider and end user. In general, we can assume that an intelligent combination of probes would set up a platform for service providers, network operators and authorities to monitor traffic and supervise applications performance. Obviously, the availability of universal interfaces and standard KPI is a requirement to progress in this way. As a first diagnosis tool, operators and big clients look after point-to-point (p2p) links, then operators and service providers watch end-to-end (e2e) connections so as to check QoS at IP layer and supervise applications performance. In the following, some examples of products designed as probes to accomplish the corresponding measurements are given. Furthermore, a whole range of line cards have been added to satisfy specific customers demands and should be submitted to standardization process; for example, to monitor QoS in master-slave fashion networks (master is at the operator's domain and the slave in the customer premises) as a kind of VIP service for corporations, government and large customers. These devices are known as Ethernet Demarcation Devices (EDD). They are gaining interest for L2-VPN and new PTT-based networks [START_REF] Tramms | Traffic Measurements and Models in Multi-Service Networks) project measurement devices are describe in its document D4.3[END_REF]. Their interfaces can be either optical or electrical. The EDD equipments developed by the authors (and tested in a public Spanish network) permit to extend optical gaps (up to 80Km) between two user switches, using the dark fiber property of the telecom operator and, allow setting alternative paths or simply determining the responsibility of eventual failures (packet loss, latency, etc.).

One way P2P systems measurements

To measure the IP services performance in terms of bandwidth availability and eventual differences between one way and return packet travelling, one can inject test packets and accurately timestamp the capture instant of such packets. One of the authors has developed a high-precision timestamping probe based on GPS synchronization. Its design was developed taking as a base the NetFPGA card, which provides a cost-effective, yet powerful solution with four 1-Gbps interfaces (see fig. 2).

Fig. 2. Printed board composing the core of the probe for timestamping through Global

Positioning System (GPS)

The application of this system to measure OWD (One Way Delay) was presented in the CELTIC event (Paris, 2009) for a connection Madrid-Paris and has also been partially funded by the ONELAB FP7 project. The OWD measurement tool sent trains of UDP packets while other (streaming) applications were delivered e2e through the public networks. The OWD measurements are statistically analyzed in order to give an accurate mean value for the OWD. Accuracy of tens of nanoseconds is achieved by means of this simple device, which can be easily plugged in a PCI bus in the measurement device. At the operating system, the card can be accessed through a standard socket interface, which makes it possible to analyze packet-by-packet from any user application.

On the other hand BART platform [START_REF] Ekelin | Real-time measurement of end-to-end available bandwidth using Kalman filtering[END_REF] (Bandwidth Available in Real Time) is an active measurement method for estimating path available capacity and other capacityrelated parameters in real time over multi-domain packet-switched network paths.

BART sends traffic over a network path in order to determine at which rate the path shows signs of congestion. This rate defines the path available capacity. A BART sender is transmitting IP packets at randomized inter-packet separations towards a receiver; the separation is affected by other IP traffic sharing the network path. The receiver timestamps each incoming IP packet and calculates the new inter-packet separation. The inter-packet separations at the receiver are analyzed by a Kalman filter, a statistical method for tracking not directly observable properties in real time.

Combining measurements from different segments for a given end-to-end connection gives rise to a powerful tool to operate the network and find bottlenecks.

Service monitoring architecture

A service monitoring platform has an architecture composed by probes distributed in different segments of the network depending on its topology, the remote preprocessors, physically close to the probes, and the central repository and analyzer system (fig. 3).

Fig. 3. Architecture of a service monitoring platform

The Remote pre-processors are able to calculate specific KPI; in fact, the captured frames are stored in these remote locations during a reasonable time in order to analyze anomalies "post mortem". In the central process unit, those KPI are further processed (grouped and correlated) in order to analyze the whole service platform performance and produce periodic reports for administrative and technical purposes.

Service monitoring platforms must provide capabilities for analysis, service assurance and monitoring support. Furthermore, they must support tools for diagnosing problems, such as protocol analyzers and call tracers. A wide number of functionalities must be fulfilled in order to support QoS management. These functionalities can be grouped in two areas: Traffic measures and quality measures.

The first ones offer an overview of the network load (volume) and traffic characteristics along specific time periods (charged hour, cycling holiday, etc) similar to the traffic modeling mentioned above. Quality measures are targeted towards obtaining a thorough overview of how users perceive the service and how network services (offered by the operator) match service demands by applications (offered by the service providers). The traffic measures are grouped in a few parameters every hour to get a statistical estimate of the network evolution; the quality measures are taken more often (every few minutes) so that anomalies can be detected before users complain. The traffic measures cover all the protocols of the OSI tower, covering the range from level to level Liaison Implementation, and also distinguishing the particularities of each plane. As a natural nomenclature, these measures are referred to:

Origin (probe side, close to a remote site): This range would be implicitly associated with a particular geographical area, such as a network access node. Destination (end opposite site towards traffic is driven): Core network elements such as application servers or control nodes.

Quality measures are obtained from statistics of failure in the protocol, number of errors in connections made and other parameters that indicate degradation in service quality.

The QoS monitoring platform (called OMEGA-Q, fig. 4) developed in Telefónica Group (Spain, Brazil, Venezuela, etc.) supports three categories of services so far: Broadband for mobile access, VoIP provision in the framework of next generation networks (NGN) and IPTV. It monitors voice-PLMN, mobile services (SMS, MMS, roaming, CAMEL…), VoIP/IMS/NGN, IPTV/MobileTV, etc. The main parameters monitored are:

For Internet data transmission: Effectiveness of the service rate, Time to establish a connection and Loss rate information For VoIP quality: Effectiveness of the service rate, Call setup time For IPTV: Effectiveness of the service rate, Average time to swap channels and Loss of signal reception. infrastructure. ETOMIC automatically performs periodic measurements that provide general network performance parameters like routes and one-way delay between all nodes of the system. DIMES [START_REF]FP7-MOMENT (Monitoring and Measurement in the Next Generation Technologies)[END_REF] uses a dedicated community of software "agents", installed by thousands of volunteers around the Globe. Using these agents, DIMES manages to measure from roughly 200 VPs on a weekly basis since 2005 and from over 350 different VPs overall since the beginning of 2009. Once installed by the user, the agent operates at a very low rate so as to have minimal impact on the machine performance and on its network connection. The project intends to explore possible relationships between the data gathered on the Internet's growth with geographical and socio-economic data, in particular for fast developing countries, to see if they can provide a measure of economic development and societal openness. The project is committed to openness and thus publishes period maps at several aggregation levels on the web. It also includes web interfaces for running remote coordinated measurements, which is used by researches around the world.

Other relevant projects are PerfSonar, a FP7 effort that serves to integrate different measurement probes in a single measurement infrastructure, and OneLab / OneLab2

IP projects that have also provided the PlanetaLab community [START_REF]FP7-MOMENT (Monitoring and Measurement in the Next Generation Technologies)[END_REF] with monitoring tools. These projects have pursued rather different objectives, and have involved a large number of research groups across Europe but most of the research groups have been involved in only one project thus being unaware of the rest.

QoS management and network management

Monitoring platforms link a series of precedent monitoring systems, some of developed from previous circuit-switched network maintenance systems or ad-hoc operation platforms and management systems provided by manufacturers. Others were specifically designed and implemented for managing QoS of new services. From the point of view of pure operator, it is also interesting to obtain information from the service providers´ premises through SNMP access to extract basic statistics about network behavior. Then operators and service providers may overlap their respective platforms and integrate systems to manage QoS. This effort of integration is really important (fig. 5) in setting up Future Internet management and renders benefits to both agents since the final objective of such integration is achieving a QoS-driven network management. In practice, this approach leads to close the loop of "service provision -traffic monitoring -QoS monitoring -adaptive service provision" by means of cognitive systems acting on the network operation systems. Whether this loop requires a central operation mechanism or it is performed by autonomic agents is a further development issue although one can imagine parallel improvements following both approaches, for different scenarios, namely MANET (Mobile Ad hoc Networks), home networks, corporative virtual private networks, public networks of general purpose, etc. This management architecture will be able to cope with the increasing demands to offer bundled multi-services (Multi-play with IPTV/VoD/mobile), which is an important way to attract and retain customers and complies to NGN paradigms, namely convergent transport infrastructures. From a rather economic point of view, such integration is the only cost-effective solution to fulfil future Internet expectations, like operating upon virtualized resources and satisfy the "four anies", namely any access, anywhere, any time for any service users may demand.

Conclusions

This paper has presented several tools for service monitoring and QoS management including recently developed devices for traffic monitoring and a complete operating platform. All these elements should converge towards the objectives of extending Internet services with guaranteed quality, coping with NGN paradigms, in a costeffective way for both service providers and network operators. Improved active and passive probes to measure traffic parameters were used to verify connectivity performance of public networks. Point-to-point measurement products were included as OAM tools for networks over packet transport technology. End-to-end measurement devices demonstrated their ability to detect network congestion and feed repositories for bottleneck analysis. Besides, an enhanced algorithm for analysis of traffic data was used to achieve traffic modeling and anomalies detection. The performance of the systems achieved is self-explained by the applications of the service monitoring world-wide deployed, as described, for IPTV, VoIP and ISP among other services. Thus a solid base of devices, algorithms and architecture design is available for achieving network monitoring and service monitoring although other instruments, like DPI (deep packet inspection) not presented in this paper, must complete the toolbox.

A further work to develop cognitive agents that perform real-time actions to correct network bottlenecks or protect it from attacks will be next step.

Fig. 1 .

 1 Fig. 1. Equipments developed for Ethernet transport networks checking and operation

Fig. 4 .

 4 Fig. 4. Network and Services monitored by OMEGA-QThere are several experimental initiatives for Future Internet monitoring fostered by the European Commission, each of them devoted to extend the current state of the art in different topics. See a list of referred infrastructures and traffic measurement testbeds in[START_REF]FP7-MOMENT (Monitoring and Measurement in the Next Generation Technologies)[END_REF]. The European Traffic Observatory Measurement InfrastruCture (ETOMIC) was launched in 2004 to provide the scientific community with an Internet measurement platform that was fully open and reconfigurable, extremely accurate and uses GPS synchronization for timing. Now more than 20 nodes are distributed throughout Europe, with specific monitoring hardware that is integrated with the Planetlab[START_REF]FP7-MOMENT (Monitoring and Measurement in the Next Generation Technologies)[END_REF] infrastructure. ETOMIC automatically performs periodic measurements that provide general network performance parameters like routes and one-way delay between all nodes of the system. DIMES[START_REF]FP7-MOMENT (Monitoring and Measurement in the Next Generation Technologies)[END_REF] uses a dedicated community of software "agents", installed by thousands of volunteers around the Globe. Using these agents, DIMES manages to measure from roughly 200 VPs on a weekly basis since 2005 and from over 350 different VPs overall since the beginning of 2009. Once installed by the user, the agent operates at a very low rate so as to have minimal impact on the machine performance and on its network connection. The project intends to explore possible relationships between the data gathered on the Internet's growth with geographical and socio-economic data, in particular for fast developing countries, to see if they can provide a measure of economic development and societal openness. The project is committed to openness and thus publishes period maps at several aggregation levels on the web. It also includes web interfaces for running remote coordinated measurements, which is used by researches around the world. Other relevant projects are PerfSonar, a FP7 effort that serves to integrate different measurement probes in a single measurement infrastructure, and OneLab / OneLab2

Fig. 5 .

 5 Fig. 5. Conceptual representation of a network-centric approach for QoS-driven network management architecture in future Internet

P2P traffic monitoring systems

Point-to-point (p2p) measurements include throughput, latency, jitter and packet loss detected in the network layer. As it turns out, the operators have interest in supervising critical links in order to react quickly to any performance loss. One of the authors implemented a probe of high flexibility by means of a FPGA that allows generating and measuring Ethernet traffic [11] without using expensive equipment (fig. 1). Besides, the monitoring system built on them can be used to set demarcation between operator and client network.

Acknowledgments. This work has been partially developed in the framework of the Celtic and EUREKA initiative IPNQSIS (IP Network Monitoring for Quality of Service Intelligent Support).


⋆⋆ Vasilios A Siris
email: vsiris@ics.forth.gr

George Stamatakis

Elias Tragos
email: etragos@ics.forth.gr

Channel Assignment based on the End-to-end Throughput in Multi-hop Wireless Networks ⋆

Keywords: end-to-end throughput, 802.11 MAC, multi-rate

We define a utility-based framework for joint channel assignment and topology control in multi-rate multi-radio wireless mesh networks, and present a greedy algorithm for solving the corresponding optimization problem. The proposed approach can support different target objectives, which are expressed as utility functions of the end-to-end throughput from the gateways to the mesh nodes. The latter accounts for the 802.11 MAC sharing model and rate diversity. The model can be extended to the case of multipath routing, where there are multiple paths from the same or different gateways to the mesh nodes, and for performing joint channel assignment, topology control, and routing.

Introduction

Channel assignment in wireless mesh networks (WMNs) influences the contention among wireless links and the network topology or connectivity between mesh nodes. There is a trade-off between minimizing the level of contention and maximizing connectivity [START_REF] Marina | A Topology Control Approach for Utilizing Multiple Channels in Multi-Radio Wireless Mesh Networks[END_REF][START_REF] Das | Optimization Models for Fixed Channel Assignment in Wireless Mesh Networks with Multiple Radios[END_REF][START_REF] Skalli | Channel Assignment Strategies for Multiradio Wireless Mesh Networks: Issues and Solution[END_REF]. Moreover, channel assignment affects the interference between adjacent channels; such interference exists not only for 802.11b/g, but -contrary to common belief -also for 802.11a when the distance of antennas is small [START_REF] Cheng | Adjacent Channel Interference in Dual-Radio 802.11a Nodes and Its Impact on Multi-hop Networking[END_REF][START_REF] Angelakis | Adjacent Channel Interference in 802.11a: Modeling and Testbed Validation[END_REF], which occurs when they are located in the same mesh node. Finally, channel assignment influences the connectivity of mesh nodes with wired network gateways, which is a key application of wireless mesh networks.

Prior work on channel assignment considered minimizing the interference [START_REF] Ramachandran | Interference-Aware Channel Assignment in Wulti-Radio Wireless Mesh Networks[END_REF][START_REF] Ko | Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks[END_REF][START_REF] Subramanian | Minimum-Interference Channel Assignment in Multi-Radio Wireless Mesh Networks[END_REF]. On the other hand, the channel assignment procedure proposed in this paper considers an optimization objective that is a function of the end-to-end (e2e) throughput, which accounts for the 802.11 MAC sharing of the wireless channel. The works of [START_REF] Das | Optimization Models for Fixed Channel Assignment in Wireless Mesh Networks with Multiple Radios[END_REF][START_REF] Kodialam | Characterizing the capacity region in multiradio multi-channel wireless mesh networks[END_REF][START_REF] Alicherry | Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks[END_REF][START_REF] Ye | End-to-end throughput aware channel assignment in multi radio wireless mesh networks[END_REF][START_REF] Avallone | A Channel Assignment Algorithm for Multi-Radio Wireless Mesh Networks[END_REF][START_REF] Giannoulis | Congestion Control and Channel Assignment in Multi-Radio Wireless Mesh Networks[END_REF][START_REF] Merlin | Resource Allocation in Multi-Radio Multi-Channel Multi-Hop Wireless Networks[END_REF] consider the throughput for channel assignment. [START_REF] Rad | Joint optimal channel assignment and congestion control for multi-channel wireless mesh networks[END_REF][START_REF] Giannoulis | Congestion Control and Channel Assignment in Multi-Radio Wireless Mesh Networks[END_REF][START_REF] Merlin | Resource Allocation in Multi-Radio Multi-Channel Multi-Hop Wireless Networks[END_REF]] also consider a utility-based framework: [START_REF] Rad | Joint optimal channel assignment and congestion control for multi-channel wireless mesh networks[END_REF] for joint congestion control and channel assignment, assuming a known network topology, [START_REF] Giannoulis | Congestion Control and Channel Assignment in Multi-Radio Wireless Mesh Networks[END_REF] for joint congestion control and channel assignment, and [START_REF] Merlin | Resource Allocation in Multi-Radio Multi-Channel Multi-Hop Wireless Networks[END_REF] for joint congestion control, channel allocation, and scheduling, for which a greedy heuristic assuming orthogonal channels is proposed. Our work differs in that we present a utility-based optimization framework for joint channel assignment and topology control which is based on the e2e throughput. The application of a utility-based framework to congestion control is fundamentally different than the application to channel and topology control, since the latter is a discrete problem.

The work of [START_REF] Alicherry | Joint Channel Assignment and Routing for Throughput Optimization in Multi-radio Wireless Mesh Networks[END_REF] considers the problem of joint channel assignment and routing, while satisfying fairness constraints. Our work differs in that we investigate joint channel assignment and topology control, and our model supports rate diversity and different target objectives. [START_REF] Tang | Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks[END_REF] investigates topology control, and proposes a channel assignment procedure to minimize the aggregate interference, while satisfying a minimum node connectivity. Our approach differs in that we consider utility-based objectives for topology control, which are functions of the e2e throughput. Other works assume full connectivity between nodes that are within range [START_REF] Marina | A Topology Control Approach for Utilizing Multiple Channels in Multi-Radio Wireless Mesh Networks[END_REF][START_REF] Das | Optimization Models for Fixed Channel Assignment in Wireless Mesh Networks with Multiple Radios[END_REF][START_REF] Subramanian | Minimum-Interference Channel Assignment in Multi-Radio Wireless Mesh Networks[END_REF], or assign a common channel to one interface of all mesh nodes [START_REF] Ramachandran | Interference-Aware Channel Assignment in Wulti-Radio Wireless Mesh Networks[END_REF]. The former approach can lead to low transmission rates, which significantly reduce the network's performance. On the other hand, assigning a common channel to all nodes reduces the available interfaces and the chance for more intelligent channel assignment, which is significant since practical mesh networks contain nodes with a few (typically 3-4) interfaces. The work in this paper also differs from our previous work [START_REF] Dionysiou | Utility-based Channel Assignment and Topology Control in Wireless Mesh Networks[END_REF] where channel assignment considered the per link throughput, rather than the e2e throughput of flows.

The channel assignment problem in mesh networks with multi-radio nodes is known to be NP-hard [START_REF] Raniwala | Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks[END_REF]. For this reason, channel assignment is typically based on heuristics which assign channels to interfaces or links based on some order or rank; the rank can depend on traffic load, distance to gateway, interference level, etc. In order of decreasing rank, interfaces are assigned the "best" channel according to some criteria [START_REF] Raniwala | Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks[END_REF][START_REF] Raniwala | Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network[END_REF][START_REF] Das | Optimization Models for Fixed Channel Assignment in Wireless Mesh Networks with Multiple Radios[END_REF][START_REF] Ramachandran | Interference-Aware Channel Assignment in Wulti-Radio Wireless Mesh Networks[END_REF][START_REF] Skalli | Channel Assignment Strategies for Multiradio Wireless Mesh Networks: Issues and Solution[END_REF]. The procedure proposed in this paper also considers assigning channels in some order; however, the order is not fixed or a priori known, but rather is determined during the execution of the channel assignment procedure, and is based on the target objective.

In summary, the proposed channel assignment and topology control approach has the following key features:

-Channel assignment can be performed with different target objectives, which reflect different operator-dependant requirements. -Target objectives are expressed as utility functions of the end-to-end throughput of flows from gateways to nodes, which captures the MAC layer sharing and rate diversity. -The node connectivity is not known a priori. Rather, the node connectivity (network topology) is determined together with channel assignment. -The approach efficiently utilizes multiple wired network gateways, and ensures that for every mesh node there exists at least one path to a gateway. Support for different objectives is motivated by the fact that network operators can have different operation and performance requirements, hence value differently the aggregate throughput achieved by the network and the distribution of throughput across flows. Such flexibility in operating a network is significant for the cost-effectiveness of future wireless access networks, enabling them to adapt to different operator and application requirements. The remainder of the paper is structured as follows: In Section 2 we present an overview of the proposed channel assignment and topology control procedure, and in Section 3 we present the mathematical formulation of the problem, and its extension for multiple paths and for joint channel, topology, and routing control. In Section 4 we present more details for the channel and link selection algorithm, and the end-to-end throughput estimation algorithm. In Section 5 we present and discuss simulation results, and finally, in Section 6 we conclude the paper.

Channel assignment and topology control model

The proposed channel assignment and topology control procedure consists of two modules: the throughput estimation module, and the channel and link selection module, Figure 1. The throughput estimation module estimates the throughput of all end-to-end flows, for a specific channel assignment and node connectivity; this estimation considers the paths for all flows, which are determined by the routing protocol, and the transmission rate, which depends on the rate control algorithm at the transmitters. The channel and link selection module takes as input the target objective, expressed as a utility function, and selects the channel assignment and node connectivity that optimizes the specific objective. Note that the channel selection and throughput estimation modules are independent, hence the proposed channel and link selection procedure can work with some other throughput estimation module. Of course, the performance of the channel assignment depends on the joint operation of the two modules.

We consider a wireless mesh network with a set of nodes N . Each mesh node has multiple radio interfaces. Some nodes, which are referred to as gateway nodes, have wired network connections. The problem we address is to assign channels to mesh nodes and define node pairs that have a communication link, while ensuring that all nodes have a path to at least one gateway. Channel assignment alone does not fully define the node connectivity. Also, an interface's transmission rate depends on the destination interface it communicates with; the transmission rate in turn influences the throughput that is achieved by that link, as well as all other links in the same transmission range that operate on the same channel. Let L be the set of links between nodes, which contains elements of the form (i, j; k), denoting a link between nodes i and j operating on channel k ∈ C; C is the set of available channels. X i denotes the end-to-end throughput of the flow from a gateway to node i. Note that there can exist multiple links between two mesh nodes, operating on different channels and different nodes can communicate with the same node on the same channel.

The channel assignment and topology control problem can be written as

Maximize i∈N U ({X i , i ∈ N }) (1)
over L = {(i, j; k) : i, j ∈ N, k ∈ C} such that ∃ path from a gateway to node i, ∀i ∈ N and

K i ≤ I i , ∀i ∈ N
The path of a flow is determined by the routing protocol.

The aggregate utility U (•) in ( 1) encodes different operator-dependent requirements and objectives. Next we discuss different target objectives that correspond to different expressions for U (•).

Aggregate throughput objective: This objective corresponds to the following aggregate utility:

U ({X i , i ∈ N }) = i∈N X i , (2)
i.e., the aggregate utility is equal to the sum of the end-to-end throughput of all flows from the gateways to the nodes.

Fairness objective: This objective corresponds to the following utility:

U ({X i , i ∈ N }) = i∈N log (X i ) . (3)
This objective tries to achieve fairness among the various end-to-end flows.

Load balancing objective: This objective tries to balance the load across gateways. Let G be the set of gateway nodes, F m be the set of flows that traverse gateway m. The load balancing objective corresponds to the following utility:

U ({X i , i ∈ N }) = m∈G log i∈Fm X i . (4)

Extensions

Multi-path: The formulation in Section 3 assumes that there is a single flow from a gateway to every node i ∈ N . The formulation can be extended to more than one flows to every node, possibly from different gateways. Multiple paths increase the network's redundancy, enabling it to overcome link failures.

Joint channel assignment, topology control, and routing: The formulation in Section 3 assumes that a flow's path is determined by the routing protocol. The following modification corresponds to a joint channel assignment, topology control, and routing problem.

Maximize i∈N U ({X i , i ∈ N })
over L = {(i, j; k) : i, j ∈ N, k ∈ C}, P such that ∃ path from a gateway to node i, ∀i ∈ N and

K i ≤ I i , ∀i ∈ N
where P is the set of paths for all flows to nodes i ∈ N . In the above formulation, a flow's path is not determined externally by the routing protocol, but is determined by the optimization problem.

4 Utility-based channel assignment using the end-to-end throughput estimation

Next we discuss the functionality of the channel and link selection module, and the end-to-end throughput estimation module.

Channel and link selection algorithm

The proposed channel assignment procedure implements a greedy heuristic that tries to maximize the aggregate utility of the mesh network, given by (1). The order in which flows are created is based on the utility the corresponding channel assignment yields, which is estimated during the execution of the algorithm and not known a priori. The pseudo-code for the channel selection procedure, which is executed in some central location, is shown in Algorithm 1. L is the set of links, which contains elements (i, j, ; k) that denote a link between nodes i and j, operating on channel k. U (L) is the aggregate utility for the link set L.

Algorithm 1 Greedy utility-based channel and link selection based on e2e throughput 1: Variables: 2: N unassigned : set of nodes that have not been assigned an end-to-end flow from a gateway 3: L: set of links, which contains elements of the form (i, j, ; k), denoting there is a link between nodes i and j operating on channel k; initially empty 4: U (L): aggregate utility for set of links L 5: pi: ordered set of nodes in the path from a gateway to node i as determined by the routing algorithm 6: M (i): set of links, which contains elements of the form (i, j, ; k), for forming the path from a gateway to link i 7: U ′ (i): aggregate utility if channels are assigned to the links along the path from a gateway to link i 8: Algorithm: 9: repeat 10:

for all i ∈ N unassigned do 11:

pi = ordered set of nodes from gateway to node i, as determined from routing algorithm

12:

for all (i, j) ∈ pi in order from closest to farthest from gateway do

13:

select channel k that yields largest utility then 14:

Mi = Mi + {(i, j; k)}

15:

end select

16:

end for 17:

U ′ (i) = U (L + Mi)
18:

end for

19:

select i ∈ N unassigned with highest U ′ (i) and smallest number of hops from gateway then 20:

L = L + Mi {Assign channels to form a flow from gateway to i}

21:

Remove i from N unassigned

22:

end select

23: until N unassigned not empty

The algorithm considers paths from a gateway to all nodes, as determined by the routing algorithm. The paths, and subsequently the links forming the paths, are created in order of increasing aggregate utility: For all possible paths, channels are assigned in a greedy manner, starting with links in the path that are closest to the gateway (line 12). The path whose assignment would yield the highest utility is then selected (line 19), and the corresponding channel assignments are made (line 20). The procedure ends when all paths are created.

End-to-end throughput estimation

In this section we describe a simple model for estimating the end-to-end throughput of flows in a multi-radio, multi-channel and multi-rate wireless mesh network (WMN) with non-saturated traffic conditions. The WMN is represented as a graph G = (V, E), where V is the set of wireless interfaces and E is the set of directional links between them.

Traffic is generated by UDP senders, which limit their rate to the end-to-end throughput with which the WMN is able to forward their traffic. Each UDP flow has a single, known path that originates at a source interface and is destined to a sink interface of the WMN. Let F be the set of flows in the network. The end-to-end throughput of a flow f ∈ F will be x f = b f T , where b f is the number of bits served by flow f over a period of time T . Let N (v) be the set of wireless interfaces whose transmissions can conflict with interface v's transmissions, due to the CSMA-based access protocol, and includes v. Hence, N (v) contains all interfaces that are inside v's carrier sense range, and use the same channel as v. Transmissions from the interfaces in N (v) determine the aggregate channel occupation time T v seen by v, including the channel occupation time due to its own packet transmissions. T v can be estimated from

T v = u∈N (v) f ∈Fu b f T u,f , (5)
where F u is the set of flows whose packets are forwarded by interface u, and T u,f is the time needed for interface u to forward a single bit from flow f . Each pair (u, f ) uniquely determines the link e over which interface u transmits flow f 's packets; T u,f depends on the link e's transmission rate [START_REF] Jun | Theoretical maximum throughput of IEEE 802.11 and its applications[END_REF].

We use an iterative, water-filling procedure for calculating the values of b f . Initially each flow f has zero b f and is in a non-bottlenecked state. In every round of the procedure [START_REF] Siris | A Simple End-to-End Throughput Model for 802.11 Multi-Radio Multi-Rate Wireless Mesh Networks[END_REF]:

-We increment the number of bits sent by all source interfaces that have at least one non-bottlenecked flow originating from them, by the same amount S. This reflects the fair channel access among contending interfaces in 802.11.

Interfaces may belong to the same or different multi-radio nodes. If more than one non-bottlenecked flows have the same source interface, then the amount S is equally shared among these flows, which increase b f by the same amount. -We calculate the aggregate channel occupation time seen by each interface v ∈ V using [START_REF] Angelakis | Adjacent Channel Interference in 802.11a: Modeling and Testbed Validation[END_REF]. If for some interface v ∈ V holds that T v ≥ T , then all nonbottlenecked flows that either originate, terminate, or traverse the interface are marked as bottlenecked and in case T v > T their b f values are decreased equitably so that either T v = T of b f = 0. This reflects the fact that for any directional link of the WMN we may not increase the total number of bits transmitted over the link if either the transmitter or the receiver of the link perceives a fully occupied channel. Furthermore, the reduction of b f values so that either T v = T of b f = 0 models successfully throughput reduction or even flow starvation in well-known problematic scenarios of CSMA-based protocols like 802.11 DCF, such as information asymmetry, flow-in-the-middle, and near/far hidden terminal scenarios [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in csma multi-hop wireless networks[END_REF].

The above iterative procedure terminates when all flows are marked as bottlenecked; the derived values of b f are used to calculate each flow's throughput.

Performance evaluation

In this section we present simulation results for the proposed channel assignment algorithm, using the network simulator OMNET++. The simulations used the IEEE 802.11b network model. Traffic was generated by UDP senders, which limited their rate to the end-to-end throughput supported by the network. We present results that compare the proposed channel assignment algorithm for the aggregate throughput objective defined by (2), and the fairness objectives defined by [START_REF] Skalli | Channel Assignment Strategies for Multiradio Wireless Mesh Networks: Issues and Solution[END_REF], with an ad hoc channel assignment and node connectivity. The results also include the fairness index given by Fairness Index = (

N i=1 Xi) 2 N N i=1 X 2 i
, where X i is the e2e throughput for the flow to node i and N is the total number of nodes.

Figure 2 depicts the channel assignment for a grid topology with 11 nodes and 3 gateways, for the proposed algorithm using the aggregate throughput and fairness objective, and for two ad hoc channel assignments. Gateway nodes in this and the other topologies investigated have three interfaces, whereas the other mesh nodes have two interfaces. Table 1 shows the corresponding results. The table shows that the throughput objective achieves the highest aggregate throughput, and the highest maximum flow throughput; this is achieved at the cost of fairness, since the aggregate throughput objective achieves the lowest fairness index and the lowest minimum flow throughput. On the other hand, the fairness objective achieves the highest fairness, at the cost of lower aggregate throughput. The two ad hoc channel assignments achieve worst aggregate throughput and fairness compared to the proposed channel assignment algorithm, for both the aggregate throughput and the fairness objective.

Figure 3 shows the channel assignment and node connectivity for the grid B topology, which contains 11 nodes and 2 gateways. Table 2 shows the corresponding simulation results. As in the previous grid topology, the aggregate throughput objective achieves the highest aggregate throughput, at the cost of lower fairness. Also, the aggregate throughput is more than two times the aggregate throughput achieved with the first ad hoc channel assignment, and more than four times the aggregate throughput achieved with the second ad hoc channel assignment. Moreover, in this scenario the lowest minimum flow throughput is achieved with the second ad hoc channel assignment. The fairness objective achieves the highest fairness utility, given by (3) and a high fairness index which is close to the fairness index achieved by the first ad hoc channel assignment. Observe, however, that the fairness objective achieves a significantly higher aggregate throughput compared to the first ad hoc channel assignment.

Figure 4 depicts the channel assignment for a grid with 20 nodes and 3 gateways. Table 3 shows that, as in the previous two topologies, the aggregate throughput objective achieves the highest aggregate throughput, and the highest maximum end-to-end flow throughput. Also, the fairness objective achieves the highest fairness. Comparing the results for this topology, with the results for the previous two grid topologies, we note that the fairness achieved in this grid topology is significantly smaller than the fairness achieved in the previous two topologies; this occurs because this topology has a larger number of nodes, hence has higher contention for channel access, which results in flows having significantly different end-to-end throughput values; this is also the reason that some flows achieve a very small throughput, as indicated by the minimum flow throughput in Table 3. For the aggregate throughput objective, a few flows achieve very high throughput, while the other flows achieve very low throughput, and some of these achieve throughput that is almost zero.

Conclusion

We have presented a utility-based framework for joint channel assignment and topology control in multi-rate multi-hop wireless networks. The framework supports different target objectives, expressed as utility functions of the end-to-end throughput of flows from gateways to nodes. Simulation results show the perfor- mance in terms of aggregate throughput and fairness achieved by the proposed approach, and illustrate the influence of the target objective.

Fig. 1 .

 1 Fig. 1. The channel assignment and topology control procedure consists of two modules: the end-to-end throughput estimation and the channel and link selection module.

2 Fig. 2 .

 22 Fig. 2. Channel assignment and node connectivity for grid A: 11 nodes with 3 gateways (nodes 0,4,11). Available channels: 1, 6, 11.

2 Fig. 3 .

 23 Fig. 3. Channel assignment and node connectivity for grid B: 11 nodes with 2 gateways (nodes 0,11). Available channels: 1, 6, 11.

Table 1 .

 1 Results for grid A

		Aggregate throughput Fairness Ad hoc	Ad hoc
		objective	objective assign.#1 assign.#2
	Aggregate throughput 19,11	14,88 11,95	10,77
	Fairness index	0,491	0,989 0,899	0,983
	Fairness utility	1,478	1,814 0,930	0,665
	Min flow throughput 0,836	1,150 1,051	0,939
	Max flow throughput 6,169	2,174 2,238	1,449

Table 2 .

 2 Results for grid B

		Aggregate throughput Fairness Ad hoc	Ad hoc
		objective	objective assign.#1 assign.#2
	Aggregate throughput 10,16	8,93	4,17	2,98
	Fairness index	0,287	0,932 0,954	0,915
	Fairness utility	-1,627	-0,172 -3,096 -4,464
	Min flow throughput 0,479	0,706 0,358	0,239
	Max flow throughput 6,165	1,333 0,582	0,602

Table 3 .

 3 Results for grid C

		Aggregate throughput Fairness Ad hoc
		objective	objective assignment
	Aggregate throughput 27,99	23,68 21,73
	Fairness index	0,326	0,529 0,498
	Fairness utility	-9,478	-0,514 -2,734
	Min flow throughput 0,009	0,217 0,002
	Max flow throughput 6,161	4,519 5,818

⋆ This work was supported in part by the European Commission in the 7th Framework Programme through project EU-MESH (Enhanced, Ubiquitous, and Dependable Broadband Access using MESH Networks), ICT-215320, http://www.eu-mesh.eu ⋆⋆ V. Siris is also with the Department of Informatics, Athens University of Economics and Business.