Pedro Vale Pinheiro

Shivam Jain
email: shivam.jain.iitr@gmail.com

Fernando Boavida
email: boavida@uc.pt

A Comparative Study of Network Mobility Paradigms

Keywords:

Effective solutions for the mobility of whole networks are essential for ubiquitous Internet access. Different network mobility paradigms have different consequences in terms of signalling load, performance and scalability. In this paper, a comparison of three network mobility paradigms is presented, namely the legacy-compatible, the infrastructure-centric and the end-nodecentric network mobility paradigms. The study is unprecedented not only because the three paradigms encompass most of the existing network mobility solutions, but also because it involves scenarios with up to 22,800 routers, 11,250 networks, more than 27,000 nodes (fixed and mobile) and up to 16 levels of network mobility nesting. The obtained results point to the very good potential of the end-node-centric network mobility paradigm.

Introduction

Moving entire networks raises problems that are not trivial, due to the potentially large number of flows involved in such movement. The problem can be considerably more complex in nested scenarios, where mobile networks exist inside other mobile networks.

Several solutions for network mobility have been proposed in the recent past. Despite their differences in detail, they fall into one of three paradigm classes: i) legacy class (LC), with no impact on end-nodes in order to maximize compatibility with legacy networks and nodes; ii) infrastructure-centric class (IC), in which mobile routers take up the management of most of the mobility-related tasks on behalf of the end-nodes, and iii) end-node-centric class (EC), in which end-nodes are aware of their mobility condition and perform most of the mobility functions, making mobility as transparent as possible to the networks.

The NEMO Basic Support Protocol, specified in RFC 3963 [START_REF] Devarapalli | Network Mobility (NEMO) Basic Support Protocol[END_REF], belongs to the first paradigm class. NEMO has been developed in order to provide a basic solution for network mobility, having as main requirement complete mobility transparency, that is, requiring no need for any modifications to the nodes.

The well-known limitations of NEMO -of which lack of route optimization is the main one -have led to a whole class of more elaborate network mobility proposals, with the common characteristic that they rely on additional functionality on the part of the networking infrastructure (e.g., mobile routers, routers, agents, etc.) which, for instance, take up the burden of performing route optimization on behalf of the mobile nodes they give access to. These proposals -which we collectively designate as infrastructure-centric paradigm -aim at minimal impact on the end-nodes, as opposed to the network.

The third network mobility paradigm is based on mobility awareness on the part of end nodes. In this case, nodes have enough 'intelligence' to know if they are mobile or not and to react accordingly.

Naturally, each of the above-mentioned paradigms has different consequences on the performance, scalability and signalling load of each particular mobility solution. These translate into different behaviour in terms of round trip time, route optimisation time and signalling overhead. In order to clearly identify and assess these consequences, a large-scale comparative study has been performed and the results are presented in this paper.

A clear option to compare paradigms instead of comparing particular network mobility solutions has been made for several reasons. First, it is not practical to compare the large number of specific solutions that exist. Second, the differences between solutions belonging to the same paradigm class are minor and can only have very limited impact on the results. Last, but not least, comparing paradigms provides a more independent and general view on the consequences of architectural choices, as opposed to detailed and often irrelevant views of very particular proposals and/or implementations.

Another important aspect of the presented study is the fact that it has an unprecedented scale. Typically, proposals are accompanied by some form of assessment involving tens of nodes and few networks. In contrast, in the present case we are interested in analyzing the consequences of the mobility paradigms at a very large scale, in generalised mobility environments, such as the one foreseen for the future Internet, in which it is anticipated that a very large percentage of nodes and networks will be mobile.

Before presenting the simulation study, a brief description of the various network mobility paradigms and a comparative analysis are made in section 2. In section 3 the simulation scenarios are detailed, followed by a presentation and discussion of extensive simulation results in section 4. The objective of this discussion is to clearly identify the advantages and drawbacks of each paradigm under study. Section 5 summarises the key findings and identifies guidelines for further work.

Network mobility paradigms

Network mobility can be achieved by implementations obeying to different architectural approaches or paradigms. The chosen paradigm will impact the effectiveness and efficiency of the actual solution and, thus, it is important to carefully analyse the existing paradigms before generalised, large-scale deployment takes place.

This section provides an overview of existing network mobility paradigms. It also places existing proposals for network mobility in the presented paradigm landscape, thus providing a clear high-level view of relevant work. As the purpose of the paper is to assess and compare paradigms, we will not go into the detail of each particular proposal, as this detail can easily be found in the literature.

Legacy paradigm

The idea behind the Legacy-compatible (LC) network mobility paradigm is to readily allow network mobility without the need to change mobile network nodes (MNN) and correspondent nodes (CN). The NEMO Basic Support Protocol [START_REF] Devarapalli | Network Mobility (NEMO) Basic Support Protocol[END_REF] is the reference solution for this paradigm.

Whenever a packet destined to the mobile network prefix (MNP) arrives at the home network, a home agent (HA) encapsulates the packet and sends it to the care-ofaddress (CoA) of the mobile router (MR) over a tunnel (the MRHA tunnel). The MR will then decapsulate the packet and deliver it to the MNN. Conversely, packets from an MNN to a CN are encapsulated, sent from the MR to the HA over the MRHA tunnel, decapsulated at the HA and routed to the CN.

Although extremely simple and fully compatible with legacy devices, the NEMO Basic Support solution suffers from several important problems, such as triangular routing, potential bottleneck in the home network and amplified sub-optimality in nested mobile networks, as thoroughly discussed in [START_REF] Ng | Network Mobility Route Optimization Problem Statement[END_REF], [START_REF] Ng | Network Mobility Route Optimization Solution Space Analysis[END_REF] and [START_REF] Bernardos | NEMO: Network Mobility in IPv6[END_REF]. Virtually all problems affecting the LC paradigm have to do with lack of route optimization.

Infrastructure-centric paradigm

In the case of the infrastructure-centric (IC) network mobility paradigm, most of the tasks inherent to network mobility -with emphasis on route optimisation -are carried out by infrastructure elements, such as mobile routers, home agents and correspondent entities. The main idea behind this paradigm is that end nodes are as unaffected as possible by mobility, at the cost of higher infrastructure complexity. Nevertheless, in contrast with the LC paradigm, changes to correspondent nodes are allowed, in order to support route optimisation.

Route optimisation mechanisms differ, depending on the type of mobile network node. Typically, in the case of local fixed nodes (LFN) and local mobile nodes (LMN), all traffic to/from these nodes must be optimized by some network element, such as a mobile router, a transit router, or a special purpose agent, which, in this context, we will designate MR for simplicity. This means that MRs must keep track of all LFN-CN optimisations and must perform route optimisation, using the return routability mechanism, whenever the mobile network moves. For visiting mobile nodes (VMN), the MR must somehow provide a temporary address to the node and enable that address to be routable inside the moving network. Also, typically, nested networks are treated by MRs as VMNs.

Several network mobility proposals fall into the infrastructure-centric paradigm class. Examples are Optimised Route Cache (ORC) [START_REF] Wakikawa | Optimized Route Cache Protocol (ORC)[END_REF] [6], Path Control Header (PCH) [START_REF] Na | Route Optimization Scheme based on Path Control Header[END_REF] [8], Global HA to HA [START_REF] Thubert | Global HA to HA protocol[END_REF] and Mobile IPv6 Router Optimisation for Network Mobility (MIRON) [START_REF] Bernardos | MIRON: MIPv6 Route Optimization for NEMO[END_REF] [11] [START_REF] Bernardos | Route Optimisation for Mobile Networks in IPv6 Heterogeneous Environments[END_REF].

End-node-centric paradigm

In the case of the end-node-centric (EC) network mobility paradigm, nodes are aware of their mobility condition. This means that end nodes play an active part in mobility management tasks, such as route optimisation, relieving mobile routers from them. For this to be possible, when a mobile router acquires a new care-of-address (CoA) it informs its inside network, so that all the mobile network nodes may then use the MR's CoA as their own CoA. From this point onward, mobile nodes decide when to optimise routes and perform optimisation by themselves. On the other hand, mobile routers largely limit their role to plain routing.

Up to the present, only one network mobility proposal uses the EC paradigm. Optimised Mobility for Enhanced Networking (OMEN) was proposed by the authors and first presented in [START_REF] Vale Pinheiro | OMEN -A New Paradigm for Optimal Network Mobility[END_REF]. In addition to detailed description of OMEN, reference [START_REF] Vale Pinheiro | OMEN -A New Paradigm for Optimal Network Mobility[END_REF] also provides preliminary validation and assessment of the proposal, in a limited way and for small-scale scenarios.

Although it is based on an innovative paradigm, OMEN exclusively relies on existing protocols. Instead of creating a new protocol for informing MNNs of their MR's CoA, OMEN uses Neighbor Discovery (RFC4861) [START_REF] Narten | Neighbor Discovery for IP version 6 (IPv6)[END_REF]. Thus, either as response to a router solicitation message or by its own initiative, an MR can send router advertisement messages that will be used by MNNs to learn their CoA. The CoA will be carried in a new option. As the definition of new options is already accounted for in RFC4861, there is no need to change the protocol. On the other hand, route optimisation uses standard MIPv6 mechanisms.

Preliminary analysis

The end-node-centric paradigm eliminates several problems inherent to the legacy and infrastructure-centric paradigms.

One of the issues with the IC paradigm is to decide if and when to perform route optimisation, as it is recognized that not all traffic needs it. In fact, in some cases route optimisation may not be advisable, as the process takes longer than the traffic flow itself, as is the case of DNS traffic.

Another issue is that the load put on mobile routers may be excessive, as all the route optimisation work for all MNNs must be performed by their MR. For small mobile networks this may be acceptable, but in large ones the burden may be too high for mobile routers. Of course, the processing power of router devices has been increasing over the time, but the lighter the mobile router the smaller and the more energy-efficient it can be, and these are important factors when mobility is concerned.

The advantage of the EC paradigm mobility-awareness is that the nodes themselves can take decisions on whether to perform route optimization or not, depending on their needs, and will not be subject to a global, general-purpose, undifferentiated 'route optimisation'. Whenever a node is informed that it is under a mobile network, it can be given all the needed information for it to perform route optimisation, using the existing mechanisms of MIPv6. This, of course, does not preclude legacy nodes from using plain, sub-optimal NEMO Basic Support mechanisms or any other solution that they implement and understand.

The advantage of passing the responsibility of route optimisation to the mobile nodes is that it allows MRs to be extremely light, taking care of network access tasks and MRHA tunnel handling, thus leading to lower complexity and lower processing needs. The price to pay for this approach is very low. LMNs need to be updated, in order for them to take advantage of mobility. VMNs and MRs will also have to perform very few EC-specific tasks. On the other hand, there is no need to change any of the protocols in order to adapt hem to the EC paradigm, as it either uses existing capabilities of existing protocols, or it resorts to local processing in MRs and MNs.

Of course, the potential advantages of the end-node-centric network mobility paradigm may only be apparent and significant in generalised mobility scenarios, such as the one anticipated for the future Internet, where a vast amount of networks and nodes will be mobile. Thus, it is essential to study and compare the behaviour of the three network mobility paradigms in large-scale scenarios, which, naturally, can only be done by simulation due to the necessarily high number of involved networks and nodes. The simulations set up and the results of such study are presented in the following sections.

Simulations setup

The comparison of the LC, IC and EC paradigms in a large-scale scenario was only possible because three critical requirements were met: large processing power, a realistic and flexible network mobility emulation tool capable of running in a parallel processing environment and, last but not least, a set of scenarios suitable for drawing conclusions on the behaviour of the various paradigms under study in terms of round trip time, route optimisation time and signalling overhead. In the next sub-sections we will briefly present the mobility emulator and describe the simulation scenarios. The simulation results are presented and discussed in section 4.

The mobSim network mobility emulator

A network mobility emulator tool -named mobSim [START_REF] Vale Pinheiro | mobSim -A Network Mobility Simulation Tool for Very Large-Scale Scenarios[END_REF] -was especially built for this study due to the following reasons: 1) the large-scale of the study required the use of a cluster and the tool should be built and optimised for parallel execution; 2) the simulation detail should be as high as possible, ranging from protocol fields implementation to high-level mobility mechanisms and allowing for a configuration granularity ranging from individual hosts to routers, networks and global scenarios; 3) total flexibility to define the simulation scenarios, from the global dynamic behaviour to topologies, with any mix of mobile and fixed networks and nodes, any number of networks and any number of levels of nested mobility; 4) ability to perform any simulation using the exact same parameters, conditions and settings for the three paradigms under study.

Table 1 presents the standard functionality implemented by mobSim. This functionality is used to construct generic implementations of the paradigms under study. It should be noted that mobSim actually implements the specified mechanisms down to packet field level, and that all messages are actually generated and sent between emulated devices, thus maximising the fidelity of the tool. Configurable delays include the time for data link layer handoff, the time needed for acquiring a new IP address (through DHCP), the binding update procedure time, the binding acknowledgement procedure time, line speed, HoTi time, CoTi time, HoT time, CoT time, encapsulation and decapsulation times. The LC paradigm implementation closely follows the NEMO basic support specification (RFC 3963). In the case of the IC paradigm implementation, mobility functions -including route optimisation -are performed by mobile routers, on behalf of mobile nodes. The actual approach is a mix of the most important features of the proposals in [START_REF] Wakikawa | Optimized Route Cache Protocol (ORC)[END_REF] and [START_REF] Bernardos | Route Optimisation for Mobile Networks in IPv6 Heterogeneous Environments[END_REF]. In the case of the EC paradigm implementation, mobility functions are carried out by end-nodes, closely following the specification presented in [START_REF] Vale Pinheiro | OMEN -A New Paradigm for Optimal Network Mobility[END_REF].

Simulation scenarios

Fig. 1 presents the base topology of the overall network used in all simulation scenarios. This base topology is made up of fixed and mobile networks, and can change in the course of a simulation, as mobile networks change their point of attachment, in non-nested and/or nested configurations. For simplicity, networks are represented by their border router only. Moreover, end-nodes are not depicted.

The overall network consists of a tree-like structure with seven levels. This organisation was chosen due to its natural ability to model network mobility nesting in the mobile part of the network, as well as different path lengths in the fixed part of the network. Level 1 of the hierarchy comprises 50 routers. Every level 1 router is directly connected to the other 49 level 1 routers. Each of these routers is connected to 5 level 2 routers. In turn, each level 2 router is connected to 3 level 3 routers, and so on, according to the diagram shown in Fig. 1. With this configuration, there are 456 routers under each level 1 router. In addition, the number of end-nodes under each level 1 router was configured to be between 225 and nearly 54,000. In total, the simulated network had 22,800 routers, 11,250 networks, and more than 27,000 end nodes (fixed and mobile). Seventeen simulation scenarios were used. For scenario 1, no mobile nesting was used, i.e., all mobile networks were directly connected to fixed networks. For scenarios 2 to 17, one to sixteen levels of nesting (i.e., mobile networks inside mobile networks) were used, respectively. In all scenarios, up to 1,000 mobile nodes could be transmitting and/or receiving packets at the same time, although, in the course of the simulation runs, all mobile nodes were active at some point in time. Each mobile node transmitted a total of around 140 packets. The exact same conditions and settings were used for each of the paradigms under study.

In addition to the above, several delay parameters were used for all simulations, aiming to represent the time taken to perform the various actions associated with mobility procedures (e.g., table look up and update, security verifications, etc.). The chosen values are an approximation of actual values measured in a lab implementation, and were the following: DHCP delay -300 ms; Return Routability delay -200 ms; HoTi, CoTi, HoT or CoT messages processing delay -100 ms; MAC-layer handoff delay -500 ms; MR-HA tunnel setup delay -10 ms; BU or BA messages processing delay -10 ms.

Another important aspect of the simulations was that, for the EC paradigm, different ratios of number of nodes not performing route optimisation and number of nodes performing it were used. For instance, a ratio of 1:2 means that for each node not performing route optimisation two other nodes perform it. On the other hand, by design, in the case of the IC paradigm, route optimisation is performed for all nodes, whether their traffic requires it or not. This, of course, has influence in the performance of the mobile routers and on the amount of necessary signalling.

Finally, it is important to note that the objective of all simulations was to obtain results that could clearly show the impact of each paradigm on networks and routers. This impact can only be measured if no other factors distort the results. This is why all scenarios assumed unloaded networks. Naturally, if a given paradigm has poorer performance than another in an unloaded network, its behaviour will be even worse in networks with background traffic for which, possibly, some links will have little available capacity and some network elements will be overloaded. Moreover, there was no intention to perform stress tests to the various paradigms under study, in order to identify their limits and, thus, the number of packets transmitted per node was relatively low. Stress tests will be performed in future work.

Simulation results

Several simulation sets were run, each with a particular feature in mind, namely the effect of each paradigm on the average round-trip time (RTT), average route optimisation time and signalling overhead. The following sub-sections present and discuss the results of each set in detail

Average round-trip time

This set comprised a considerable number of simulations, each for each of the paradigms under study and for each scenario (1 to 17). In addition, each simulation was run for the following ratios of nodes not performing route optimisation and nodes performing route optimisation: 1:1, 1:2, 1:10, 1:100 and 1:1000. Fig. 2 presents the results for the 1:10 ratio.

It is possible to see that, as expected, the average round-trip time increases with the level of nesting for the case of the LC paradigm -as opposed to the case of the IC and EC paradigms -as in the LC paradigm there is no route optimization: as the level of nesting increases so increases the number of tunnels inside tunnels and, consequently, the number of networks that have to be traversed by the packets in order to reach the destination. Note that, for visibility purposes, the maximum value in Fig. 2 is cut at 2 seconds, although the LC RTT values go up to 23.4 seconds.

!" #" $" %" &" '" (" )" *" +" #!" ##" #$" #%" #&" #'" #(" ,-"./0"1234" !5!%" #5&+" $5)+" &5&%" (5#&" )5)$" *5)(" #!5$" ##5%" #%5!" #&5$" #)5!" #)5+" #+5(" $#5!" $$5'" $%5&" 6-"./0"1234" !5!&" !5)$" !5'(" !5)%" !5'+" !5(*" !5''" !5)!" !5(%" !5))" !5)#" !5*+" !5)!" !5*%" !5*)" !5)&" !5)#" 7-"./0"1234" !5!&" !5$%" !5$!" !5$&" !5$*" !5$*" !5$$" !5%$" !5$*" !5%&" !5$+" !5%'" !5%'" !5%!" !5%'" !5%%" !5%'" Fig. 3 presents the evolution of the average RTT, for three levels of nested mobile networks, as the number of nodes performing route optimization increases, according to the ratios 1:1, 1:2, 1:10, 1:100 and 1:1000. As the number of nodes requiring optimization increases, the EC paradigm gets better than the IC paradigm in terms of RTT. The reason is that the impact on MRs gets lower and lower in the case of the EC paradigm as MRs simply become routing devices, as opposed to the case of the IC paradigm, for which MRs have to perform all routing optimization operations for all nodes. This extra load on mobile routers leads to poorer IC RTT in all cases, except in the 1:1 case, for which the EC RTT is worse due to the fact that half of the packets do not follow an optimal path, as opposed to the IC case where all packets follow optimal paths.

!"!# !"$# !"!%# !"!%%# !"!%%%# &'## %()$# %(*)# %(*+# %(*!# %(*!# ,'# %()-# %(.# %($-# %(!$# %(!!# %# %(

Average route optimisation time

The second batch of simulations aimed at determining the average route optimisation time as a function of the number of nodes requiring it. Fig. 4 presents this evolution, for up to 51 nodes.

!" #" $" %" &" '" (" )" *" +" #!" ##" #" ##" $#" %#" &#" '#"
!"#$%&'()*+,-)".&/+*%&0&+.&1%2".314&

5"3%&.#*6%7&

,-"./0"1234" 5-"./0"1234" It is apparent that, as more requiring route optimisation are present, the average route optimisation time increases steadily in the case of the IC paradigm and remains more or less constant in the case of the EC paradigm. This is due to the fact that in the case of the IC paradigm the mobile routers' processing load is higher, as all the tasks concerning route optimisation are performed by these network elements, as opposed to the EC paradigm, for which route optimisation tasks are performed by the end-nodes themselves.

Signalling overhead

The final set of simulations addressed the issue of signalling overhead, resulting from the transmission of HoTi, CoTi, HoT, CoT, BU and BA messages, according to RFC 3775, during route optimisation processes. Signalling overhead increases with the number of moves of mobile routers and with the number of route optimisation operations.

Fig. 5 presents the signalling overhead for a scenario in which the point of attachment of a mobile router was changed 5 times, for different optimisation ratios. As can be seen, the simulation results clearly confirm that the signalling overhead of the EC paradigm is always lower than the one for the IC paradigm, due to the fact that IC performs route optimisation for all nodes, regardless their need for route optimisation. As the percentage of nodes requiring route optimisation increases, the signalling overhead of the EC paradigm approaches that of the IC paradigm.

!"#!$ !#!$ !#%$ !#&$ !#!"$ !#!""$ '($$ !!")$ !!")$ !!")$ !!")$ !!")$ !!")$ *($ !"!)$ !"&)$ !"+)$ !",)$ !"-)$ !!")$ ./0/$1/23405$ !"")$ !"")$ !"")$ !"")$ !"")$ !"")$

Conclusion

We have presented a comparison of three network mobility paradigms -the legacycompatible paradigm, the infrastructure-centric paradigm, and the end-node-centric paradigm -that span the existing solutions for network mobility. The comparison targeted a very large scenario, having in mind generalised mobility environments anticipated for the future Internet. The obtained simulation results clearly point to several conclusions. The first conclusion is that the legacy paradigm has several performance limitations and, consequently, will hardly scale. Clearly, this paradigm was developed for allowing network mobility despite the presence of legacy nodes.

The simulation results concerning the infrastructure-centric paradigm clearly show that the concentration of functionality in network elements affects the overall performance of these elements and, consequently, the quality characteristics of endto-end communication.

On the other hand, the performed simulations have clearly shown that the endnode-centric paradigm has very good potential and should be explored in the future. By relieving mobile routers and other infrastructure elements from several mobility tasks, significant benefit can be achieved in terms of round trip time, route optimisation time and signalling overhead. All simulation results confirmed this.

The presented comparative study opens up a large field for further research. Naturally, stress tests to the paradigms can be performed. The study of their behaviour under different network loads will surely be carried out in the near future. Last but not least, the implementation and detailed study of an end-node-centric network mobility solution -as a follow up of the preliminary solution proposed in [START_REF] Vale Pinheiro | OMEN -A New Paradigm for Optimal Network Mobility[END_REF] -is a natural step.

Fig. 1 .

 1 Fig. 1. Overall network topology.

Fig. 2 .

 2 Fig. 2. Average RTT, for the three paradigms, all scenarios and optimization ratio of 1:10.

Fig. 3 .

 3 Fig. 3. Average RTT for three levels of nested mobile networks and different route optimization ratios

Fig. 4 .

 4 Fig. 4. Average time for route optimization, as a function of the number of nodes requiring it

Fig. 5 .

 5 Fig. 5. Signalling overhead for 5 moves and for different optimization ratios

Table 1 .

 1 mobSim standard functionality.

	IPv6 basic support (RFC 2460	MIPv6 (RFC 3775)
	Hop limit	Binding update
	Next Next header implementations	Binding acknowledgement (binding accept,
	ICMPv6 (RFC4443)	reject)
	ICMP echo, reply, unreachable,	Return routablity procedure
	time exceeded	Home test init (HoTi)
	IPv6 encapsulation (RFC2473)	Care-of test init (CoTi)
	Mobility Header (RFC3775)	Home test (HoT)
	Type 2 routing header	Care-of test (CoT)
	Home address option (specific for T2RH)	Nonce utilisation (RFC3775 section 5.2.2)
		Binding refresh
	Neighbor Discovery (RFC 4861)	NEMO basic support (RFC 3963)
	Router advertisement	Bidireccional tunnel (MRHA tunnel)
	Router solicitation	Binding update
		Binding acknowledgement
		Home agent implementation
		Mobile router implementation

Acknowledgments. This work was partially financed by project PTDC/EIA-EIA/116173/2009 (CoFiMoM) of the Portuguese Foundation for Science and Technology (FCT) and the Centre for Informatics and Systems of the University of Coimbra (CISUC). The authors would also like to thank Pedro Vieira Alberto, Luis Pinto and Pedro Almeida, from the Laboratory of Advanced Computing (LCA) of the University of Coimbra, for providing access the Milipeia cluster, without which this work would not have been possible.


Kayhan Zrar Ghafoor
email: kayhan@ieee.org

Alberto J Gonzalez
email: alberto.jose.gonzalez@upc.edu

Ramon Piney
email: ramon.piney@upc.edu

Andre Rios
email: andre.rios@upc.edu

Jesus Alcober
email: jesus.alcober@upc.edu

Kamalrulnizam Abu Bakar

Fuzzy Redundancy Adaptation and Joint Source -Network Coding for VANET Video Streaming

Keywords: VANET, video streaming, network coding, Multiple Description Coding, fuzzy inference system

Video communication VANETs has many applications, such as emergency video transmission or inter-vehicle entertainment. However, delivering video to high mobile vehicles faces challenges such as packet loss due to intermittent connectivity and channel variations. Thus, designing a reliable approach for video streaming over such harsh scenarios is needed. Hence, we propose a reliable approach based on random practical network coding and source coding. This approach integrates the benefits of network coding with Multiple Description Coding to achieve robust streaming over VANET. Furthermore, we propose a redundancy controller based on fuzzy inference system to adjust the amount of redundant packets based on vehicular traffic density and SNR of the channel. Simulation shows the proposed approach achieves better protection against packet loss, application layer throughput and video quality.

Introduction

VANETs integrate ad hoc network and WLAN to achieve vehicle to vehicle communications. This inter-vehicle communication fosters the deployment of innovative wireless communication applications based on real time media streaming. These communications have several applications ranging from road safety to entertainment. Furthermore, IEEE 802.11 standard supports video communication over vehicular networks [START_REF] Singh | Wireless LAN performance under Varied Stress Conditions in Vehicular Traffic Scenarios[END_REF]. These networks deal with different traffic scenarios, such as during late night time, rush hour, dense and sparse traffic (e.g. in highways), which cause unstable vehicular network topology. Thus, the communication link will last for a short time due to high mobility of vehicles and dynamic topology. On the other hand, the communication channel between vehicles are prone to packet loss due to high variations (low SNR) together with different forms of fading.

In video communication between vehicles, random and bursty errors may be frequent. One bit error may extend over several packets due to dependency among the frames of a compressed stream. These bursts of errors are accepted [START_REF] Lee | Adaptive UEP and packet size assignment for scalable video transmission over burst error channels[END_REF] as are more severe than random errors. One way of making reliable and robust video communication between vehicles is by using error resilient approaches like Network Coding (NC). In [START_REF] Ahlswede | Network information flow[END_REF] showed that NC can provide robustness and high throughput in wired or wireless networks. The upshot of NC is encoding incoming packets at intermediate nodes. The receiver starts decoding once enough number of coded packets are received. However, a single packet loss can cause a generation of coded packets to be lost. Therefore, NC should be used with a proper error resilient approach for video streaming over VANET-like scenarios. In addition, NC has the potential to increase robustness against packet losses in wireless ad hoc networks [START_REF] Guo | Efficient Error Recovery with Netowrk Coding in Under Water Sensor Networks[END_REF]. The error resilient capability of NC depends on the number of encoded packets which are produced by intermediate nodes. The usefulness of this redundancy might be varied with vehicular network traffic conditions such as sparse and dense scenarios. In sparse scenarios, number of redundant packets should be increased appropriately to compensate packet losses while in dense scenarios it should be decreased to mitigate bandwidth overload. Thus, we can optimize the redundancy of NC considering vehicular traffic density. Redundancy also can be tuned with error rate of the communication channel. We propose a redundancy controller based on a fuzzy inference system [START_REF] Mamdani | Application of Fuzzy Logic to Approximate Reasoning Using Linguistic Synthesis[END_REF], which can effectively adjust the amount of redundant packets to the desired target value.

Multiple Description Coding (MDC) encodes a video file into a number of different independent sub-streams.Thus, MDC can be used to reduce the effects of packet loss [START_REF] Goyal | Multiple description coding: compression meets the network[END_REF]. Unlike previous works, which not consider coded packet loss problem of NC, inefficiency of MDC and adjusting the NC redundancy with respect to vehicular traffic conditions and channel error rate variations, we propose fuzzy based NC redundancy control and combined random NC with MDC to achieve reliable video streaming over VANET.

This paper is organized as follows. Section 2 describes related work and details the proposed joint source-network coding. In section 3, we propose NC fuzzy controller based on fuzzy logic. The vehicles communication model is described in section 4. Video transmission end to end delay is investigated in section 5. A simulation setup and performance evaluations are highlighted in section 6. Finally, this paper ends with a conclusion in section 7.

Related Work

In recent years, several protocols, approaches and mechanisms are developed for vehicular networks. However, almost all of them deal with short message communication between vehicles. In [START_REF] Gao | V3: a Vehicle-to-Vehicle Live Video Streaming Architecture[END_REF], investigated an architecture for video streaming over VANET whereas no real video data are used in their simulation. In [START_REF] Xie | Performance study of live video streaming over highway vehicular Ad hoc networks[END_REF], two routing protocols are discussed: Source Based Forwarding (SBF) and Receiver Based Forwarding (RBF). They have used real video data to simulate video streaming over VANET. They also used different traffic conditions for forwarding data between vehicles.

In addition, the challenge of video streaming over VANET can be interpreted by the high channel errors in vehicular traffic conditions. The high packet loss and limited communication range of the vehicles incur frequent link disconnection and uneven network partition. Authors in [START_REF] Park | Delay analysis of car-to-car reliable data delivery strategies based on data mulling with network coding[END_REF] have combined data mulling technique with three strategies, NC, erasure coding, and repetition coding. Specially, vehicles in the opposite direction are exploited as data mules to relay multimedia data to other vehicles to overcome intermittent connectivity in sparse vehicular scenarios. However, the analysis of the delay for relaying multimedia data is based on mathematical model. Literature on fuzzy inference system exist in variety disciplines of wireless ad hoc networks. Some authors [START_REF] Chen | An Entropy-Based Fuzzy Controllers QoS Routing Algorithm in MANET[END_REF] have used entropy based fuzzy logic to construct the new metric-entropy and fuzzy controllers with the help of entropy metric to reduce the number of route reconstruction so as to provide QoS guarantee in the ad hoc networks. T. C Chiang et al. in [START_REF] Chiang | A knowledge-based Inference Multicast Protocol using Adaptive Fuzzy Petri nets[END_REF] have introduced fuzzy Petri net agent to be implemented in each node to learn and to adjust itself to fit the dynamic conditions in a multicast ad hoc networks. In our fuzzy based redundancy controller, two metrics has been used to adjust the value of redundant packets.

Multiple Description Coding Approach

Video coding schemes such as MDC [START_REF] Wang | Multiple Description Coding for Video Delivery[END_REF] or Scalable Video Coding (SVC) are used to enhance error resiliency. SVC divides the video file into layers referred to as base layer and enhancement layers. The base layer is the most important layer while the enhancement layers are referenced to the base layer. The enhancement layers can not reproduced independently to the base layer. In contrast to SVC, MDC splits (Figure 1) the video signal into multiple sub-streams where each of the sub-streams (descriptors) can be reproduced independently. The receiver can make a reconstruction of the video file when any of the sub-streams is received. The quality of the reconstructed video file is proportional to the number of descriptors received. Thus, the more descriptors are received, the better the perceived video quality. Therefore, MDC is preferable in extreme environments like VANET because it provides increased resilience to packet losses by multiple streams that can be decoded independently. The main parts of MDC system are the splitter and the merger. The splitter is implemented in the source vehicle. The first step of MDC encoder is the pre-processing of the video stream in order to obtain the different N descriptions at the video source, which can be coded and displayed independently. Next, each encoded descriptor is ready to be transmitted.

Random Linear Network Coding Approach

This work proposes to use Random Linear Network Coding (RLNC). When NC is applied in the video source, the video packets are divided into generations with the same decoding deadline [START_REF] Chou | Practical Network Coding[END_REF]. This approach regards each generation as a vector and applies linear combinations before transmitting the native packets.In more detail, let N 1 , N 2 , N 3 , , N K K native packets are in a generation. The video source applies linear combination on these K native packets, the output is j coded packets which are referred to as

Y 1 , Y 2 , Y 3 , • • • , Y j , where Y j = K i=1 e i,j N i,j and j = 1, 2, 3, • • • , h.
The set of coefficients e j,i = (e j,1 , e j,2 , e j,3 , • • • , e j,K ) ∈ GF (2 q ) denotes the encoding vector which are randomly selected at the source node to encode the native packets.

Intermediate nodes collect the encoded packets of the specific generation, and then re-encode the stored packets. When an intermediate node has received u encoded packets of a given generation, then it will select a new brand of coefficients

ζ f = (ζ f,1 , ζ f,2 , ζ f,3 , • • • , ζ f,u ) from GF (2q). Thus, the outgoing packets of intermediate nodes are X 1 , X 2 , X 3 , • • • , X k , where X k = u i=1 zeta f,i Y i . It is worth
to observe that the new brand of coefficients with respect to the native packets is

γ k = (γ k,1 , γ k,2 , γ k,3 , • • • , γ k,j ) where γ k,f = u i=1
e j,i zeta f,i ,then the intermediate nodes embed it in the header of outgoing re-encoded packets.

When the destination has received K coded packets, it first checks the linear independence of the coefficients in the header of the received coded packets. Next, it builds K × K matrix using the coded packets. The rows of the formed matrix are represents the coefficients of coded packets. Afterwards, it first computes the inverse of the coefficients matrix and then multiplies it with the received coded packets.

Proposed Joint Source Coding and Network Coding Approach

The wireless nodes are communicating based on TCP/IP including 802.11 MAC layer. In the protocol stack each protocol layer adds all necessary information to the incoming data. In application layer, the specific header is added whenever the data is passed to the next layer. The source and destination IP addresses and port numbers are added by network and transport layers respectively. These addresses ensure end to end delivery of the packet. In case of link disconnection the network layer drops the packet. On the other hand, MAC and physical layers deals with nearby host communications. Fast channel variation at physical layer will produce packet loss at other layers. Thus, in order to increase robustness of video streaming over VANET, the protocol stack should be modified by embedding coding approaches so that it can tackle packet losses. This can be achieved by joint source coding and NC for video streaming.

The overall block diagram of the proposed joint source-network coding is depicted in Figure 2. In our video streaming environment, a single video source transmits descriptions to a group of receivers over VANET. The MDC is applied for robust transmission over error-prone VANET. The MDC generates several descriptions which are independently decodable. These descriptions are passed down to the next protocol layers for end to end delivery. On the other hand, we implemented the RLNC between network and MAC layer running over an IEEE 802.11 MAC protocol. The reason of this embedding are: 1) processing at lower layers (physical and MAC layers) are faster than upper ones, 2) provide transparent NC operations to upper protocol layers. At the NC shim layer, each description is divided into numbers of generations, this division depends upon the size of generations and MDC descriptions. The outgoing coded packets are recognized by adding generation-ID and description-ID into its header. This information is useful for the receiver to merge generations and descriptions at the NC and application layers respectively. If receivers collects enough linearly independent coded packets, the decoder part of NC can obtain original data belonging to that generation.

It is well known fact that there is a level of dependency among video frames; loss of one frame may cause other frames to be useless and undecodable. In other words, in certain network conditions a receiver may not decode the original packets which are belonging to the same generation, because it does not receive enough innovative packets based on its maximum flow capacity. In these network conditions, MDC can compensate the effect of coded packet loss by decoding the video, albeit with lower data rate. This is because one description is divided to multiple generations while in NC loss of one generation severely affect the whole video file due to tight correlation between generations to reproduce original video file. Therefore, the reliable approach is proposed to improve the video streaming service by reducing the multiple packet losses over VANET.

Proposed Fuzzy Logic Redundancy Control

We know that fuzzy logic simulates the interpretation of uncertain sensory information as sensed by human brain.The appropriate decision making of fuzzy inference system depends on the precise design of membership functions and fuzzy inference rules. However, in VANET the right decision making is difficult due to uncertain movement of vehicles and SNR value of the communication channel.Therefore, fuzzy inference system has been applied to control the amount of redundant packets for improving network load.Concretely, the first step of designing a fuzzy controller is to determine the impact of each input/output parameters and the range of values that each variable can have. The next step is to determine membership functions to the input and output parameters based on the defined range and to design a rule base for the fuzzy inference system. One main characteristic of the fuzzy controller is that it is modifiable. It is easy to tune rules, membership functions, value range or even change the system parameters to enhance its performance. Selection of the most relevant input variables is important.Furthermore, the fuzzy inference system consists of fuzzification , knowledge rule base and defuzzification. A group of rules can be used to represent knowledge base for articulating the control action in linguistic form. The inputs to the fuzzy controller to be designed for adjusting the amount of redundancy are: i) SNR of the communication channel and ii)vehicular traffic density. These two variables make the node's to optimize and adjust the amount of redundancy and then improves the network performance (bandwidth utilization). The overall process involved in calculation of redundant packets is described next.

Fuzzification of Inputs and Outputs

In order to control the amount of redundant packets,which are produced by using NC operations, the source and intermediate nodes encode m received packets out of all K packets it has received so far [START_REF] Wang | How Practical is Network Coding[END_REF]. The ratio m/K is refereed to as the coding density (output parameter) and it is used to adjust the degree of redundancy as a function of two input parameters (traffic density and SNR).

The redundancy controller is based on the fuzzy logic. This is because it simplifies the design of stable controller which employed two input variables and also the alterations are easy to perform to the rule inference system in order to enhance the performance of the controller. It is worth to mention the developed controller is implemented in source node and intermediate nodes in a distributed way. We are using traffic density and communication channel SNR in our redundancy controller (see Figure 3 a,b,c). The reason of this selection is that higher traffic density variation in vehicular environment yields high communication channel fluctuation, hence change of SNR. All nodes in a distributed way estimate the channel condition in the form of channel SNR. Furthermore, each node calculates the traffic density based on the proposed method in [START_REF] Balon | Increasing Broadcast Reliability in Vehicular Ad Hoc Networks[END_REF] (see section V). The specific node counts its neighbouring nodes based on the handshaking between them and then adjusts the value of redundancy using fuzzy controller. Moreover, the triangular and trapezoidal functions are chosen as the membership function since they have been extensively used in real-time applications due to their simple formulas and computational efficiency.

Fuzzy Inference Engine

The fuzzy controller is designed based on 9 rules which are presented in Table I. Channel SNR is presented on a horizontal axes and traffic density is presented on a vertical axes.In order to demonstrate the designed fuzzy controller, One rule is used to show how the algorithm works and the outputs of each rule are combined for generating the controller decision [START_REF] Mamdani | Application of Fuzzy Logic to Approximate Reasoning Using Linguistic Synthesis[END_REF].Consider a rule "If SNR is Low and Traffic Density is very sparse, the change in coding density is very high" as an example of calculating output of the specified rule. Our fuzzy inference system considers a case where SNR is 2.22 dB and traffic density is 12.9 car/km(this value is increased to 13). The output is 0.891(0.9).This value (0.9) represents the coding density, i.e the intermediate nodes encode 9 packets (in our simulation 10 is total number of packets in each generation ) out of all received packets. This high redundancy is because low value of SNR and sparse traffic density.This output is achieved by using Mamdani's fuzzy inference method [START_REF] Mamdani | Application of Fuzzy Logic to Approximate Reasoning Using Linguistic Synthesis[END_REF]. Figure 4 depicts the tuning behavior of the redundancy controller.

Defuzzification

Defuzzification refers to the way a crisp value is extracted from a fuzzy set as a representation value. Our fuzzy controller takes the centroid of area strategy for defuzzification.

Delay Constraint of Video Transmission

Consider maximum number of video packets,M, that can be transmitted in a communication session (source to destination) and satisfy maximum allowable delay T. The overall video packet delay (T) consists of three components: 1) the time that it takes for encoding and decoding of generations in NC operations T N C , 2) the time needed to split the video file at the source and merge it at the destination T M DC ; and 3) the delay introduced due to video packet transmission from sender to receivers, i.e., the sum of packetization delay, propagation delays over intermediate links and queuing delays in intermediate vehicles T t . In order to fulfil a video decoding deadline constraint, the worst case scenarios should be considered when calculating maximum allowable video packet delay. Thus, it is necessary to calculate each delay during a communication session.

The delay caused by NC operations is incurred at the encoder and decoder T N C = T Encoding + T Decoding . This encoding and decoding delay depends on the number of native packets in each generation. The descriptions are divided to a number generations of the same size, referred to as the native generations (g 1 , g 2 , g 3 , • • • , g r ). The time needed to encode the native packets of each generation is denoted by T Encoding while T Decoding is the time to decode all collected coded packets at the receiver. The decoding delay is shown in (2) under the assumption that the packets are uniformly and periodically received over a frame.

T Decoding = TW aiting + T Retrieval . (1)
T Decoding = ( m n × 1 f × n ) + z (2)
For encoding packets at the source and intermediate nodes, it is important to collect enough number of packets belonging to the same generation to produce coded packets. Therefore, the encoding timeT Encoding depends on the number of packets of a given generation. Table II shows all parameters related to delay.

The main parts of the MDC source coding are the splitter and merger which provide particular processing of the video sequences at the source and destinations respectively. Thus, the time needed for MDC operations is as follow:

TMDC = T Splitter + TMerger (3)
Therefore, delay parameters should be chosen to satisfy the delay constraint:

T ≥ T M DC + T N C + T t (4)
5 Performance Evaluation

Simulation Setup

In this section, we present simulation setup to evaluate the performance of the proposed reliable joint coding approach. The simulation is performed using NS-2 simulator (with default values for MAC and physical layer configuration parameters) integrated with Evalvid [START_REF] Evalvid | [END_REF]. Furthermore, the MDC simulation has been experimented to generate video descriptions [START_REF]Multiple Description Coding (MDC)[END_REF]. Two different video streaming approaches have been experimented: one was proposed joint coding approach (JSNC) and the other was the NC approach.The SUMO tool [START_REF]SUMO Mobility Model[END_REF] has been employed to create the vehicular scenario, and to generate mobility traces of the simulated vehicles. SUMO interposes vehicles in each lanes at a given traffic rate. This mobility model allows us to simulate vehicular scenarios such as speed deceleration/accelerations and different vehicular traffic conditions. The vehicle which is assigned as video source is generated first in one route (each route has its own parameters such as speed, acceleration). All vehicles in our simulations have a transmission range of 200 meter and 6 Mbps channel capacity. The roadway used is a two-lane road of 5 km length. Vehicles enter the road according to a Poisson distribution and travel at a speed between (10-23) m/second. The simulation is run for 100 seconds, resulting in a total of 125 vehicles generated (Figure 2). In the simulation, the CIF bit stream has been used with resolution 352x288 pixels and 300 frames (Foreman). The CIF Foreman sequence is encoded with a quality 35.68 dB. The encoder includes three types of frames: Intra frames (I-frames) that are independent on other frames, and inter frames that use either P-frames or B-frames temporal prediction from other frames. A number of mutually dependent frames form a group of pictures (GOP). In our experiment, the GOP size is set to 12 frames.

Simulation Results and Discussions

We consider three different metrics in our evaluation: average Peak Signal to Noise Ratio (PSNR); protection efficiency: average packet loss rate, which represents the robustness of the protocol against packet losses; and application layer throughput: this throughput depends upon packet losses at the lower layers.

Figure 5 a) shows that the overall video quality is higher for proposed approach than that of NC approach. When vehicles are travelling with low speed, the value of PSNR is slight different for both approaches. This is because at low velocity the wireless channel is stable and intermittent connectivity occurs less frequently. As velocity of vehicles increases, the disconnectivity rate between source vehicle and receiver increases frequently as well as the high channel variation leads to coded packet loss. A coded packet loss in one generation causes multiple packet loss of it. As result, the average video quality of the proposed approach is higher than that of the NC approach.

To compare the packet loss rate of the proposed approach with other approach, the video source transmits video packets in a given period of video communication session. The source vehicle transmits the video coded packets from source to receiver by applying NC operations. In the next communication session, we have repeated the video transmission by applying the proposed approach. Subsequently, during off line analysis, we have computed the average packet loss rate through a comparison of receiver and source trace files. We observed that the instantaneous packet loss rate is increasing in both approaches and the overall packet loss rate is lower for proposed approach than that of NC approach as depicted in Figure 5 b). Initially, there is a small difference of instantaneous packet loss values for the proposed approach and networks coding approach due to less channel variation (less bit error rate and fading of the channel) as well as less frequent link disruption and hence less number of packet losses. As mobility increases the channel instability (high bit error) and intermittent connectivity increases as well. As a result packet loss increases in both approaches. However, the NC has more coded packet loss than proposed approach at high speed. This is because one coded packet losses has a potential to generate multiple coded packet losses. On the other hand, the MDC increases error resilient of NC by generating multiple descriptions.

We observed similar trends in application layer throughput as we vary the velocity from low to high in Figure 5 c). The NC approach shows significant decrease in throughput due to high speed of vehicles which leads to high coded packet losses, while application layer throughput in our approach does not change as much at high velocity of vehicles. This is because high coded packet losses (due to high speed) at the lower layers reduces effective application layer throughput as well as increases the variation of bandwidth.

Conclusions

In this paper, we have proposed joint source coding and NC for reliable video streaming over vehicular networks. In this approach, the NC operations are implemented above MAC layer while MDC operations are embedded in application layer. The MDC descriptions are adapted with NC generations. This two stage of coding increases the robustness of video streaming in vehicular networks. Moreover, the NC redundancy are adjusted using fuzzy inference system controller, the tuning was based on vehicular traffic density and SNR of the communication channel .The mathematical analysis for latency is derived to constrain end to end delay. NS-2 extensive simulations were successfully carried out for significant gains in terms of average video quality, application layer throughput and average packet loss rate. The video streaming with NC has been compared to the proposed joint coding approach and the proposed scheme gives better performance.

Fig. 1 .

 1 Fig. 1. MDC encoding and decoding system.

Fig. 2 .

 2 Fig. 2. Proposed joint source-network coding (dark blocks ).

Fig. 3 .

 3 Fig. 3. Membership function for a) SNR ; b) Traffic Density; c) Coding Density

Fig. 4 .

 4 Fig. 4. Correlation between input and output parameters.

Fig. 5 .

 5 Fig. 5. a)Video quality for different vehicle speeds; b)Instantaneous packet loss rate for different vehicle speeds; c)Application layer throughput for different vehicle speeds

Table 1 .

 1 Rule-based redundancy control

	TrafficDensity / SNR Low M edium Large
	Sparse	VHigh	High Medium
	Dense	High Medium Low
	V Dense	Medium Low	VLow

Table 2 .

 2 Delay Related Parameters

	P arameters Description
	n	total number of packets for a given generation
	m	encoded packets out of n native packets
	f	frame rate (number of frames per second)
	1/(f × n)	inter-arrival time between successive native packets
	m/n	coding density
	z	time needed to inverse coefficient matrix
	TW aiting	time needed to collect enough coded packets

This work was supported by the i2CAT Foundation and the Spanish Government (MICINN) under research grant TIN2010-20136-C03.


Efthymios Koutsogiannis

Lefteris Mamatas
email: emamatas@ee.duth.gr

Ioannis Psaras
email: i.psaras@ee.ucl.ac.uk

Storage-Enabled Access Points for Improved Mobile Performance: An Evaluation Study

Keywords: user-centric networking, delay-tolerant networking, opportunistic routing

Due to existing networking paradigms and people communication habits, Internet is characterized by: (i) information that associates more and more with network edges, while corresponding traffic doesn't, (ii) a considerable amount of unexplored network resources that resides near mobile users, while their connectivity is usually poor and expensive in terms of financial cost and resource consumption. To address the above challenges, we introduce a cooperative networking scheme where Home Access Points are equipped with storage capabilities and offer connectivity to mobile users. Whenever connectivity sharing is unavailable, the access points store the pending data and transmit it once connectivity becomes available. We explore how storage-enabled opportunistic routing algorithms can handle periods of intermittent connectivity. We experiment with realistic scenarios based on real network configurations and mobility maps. Our results demonstrate the potential of the proposed paradigm as well as guide us to define its follow-up evolution steps.

Introduction

Research on Opportunistic Mobile Networks and DTNs has been mainly concerned with storage and energy constraints for mobile devices and optimization of connectivity opportunities between encounters. The more the encounters and data-exchanges between the mobile nodes, the more the energy and storage needed. The Delay-Tolerant and Opportunistic Networking research has focused mainly on mobile-only devices. That is, researchers have been investigating ways to optimize communication opportunities between the mobile devices themselves 3 . This is indeed the case in rural areas, for instance, where connectivity points to the network are rare, or in case of applications that do not require Internet connectivity (e.g., distributed online social networks [START_REF] Xu | Twittering by cuckoo: decentralized and socioaware online microblogging services[END_REF]).

In this study, we focus on metropolitan environments, where there are plenty of connectivity points to the Internet. We extend the operational spectrum of Opportunistic Networks and DTNs and consider Home Access Points (APs or HAPs) as integral part of these networks. We consider storage a cheap resource that can easily be integrated in future APs and evaluate the performance of existing DTN protocols in this setting. In particular, given that connectivity opportunities to APs/HAPs and therefore the Internet now increase, we investigate whether and to which extend the storage and energy constraints can now be somewhat relaxed.

We motivate our study based on the following facts:

-New applications and people communication habits call for approaches that go beyond the traditional client-server model. Users are increasingly active in uploading content to social networking sites, for instance, or hosting data, e.g., in P2P file-sharing platforms. Moreover, it is shown that Internet traffic is growing faster at the network edge than at the core [START_REF] Leavitt | Network-Usage Changes Push Internet Traffic to the Edge[END_REF]. In other words, future networks call for user-centricity, where applications demand that content is closer to the user. -Internet traffic forecasts show that mobile users are expected to double-up every year through 2014 4 . Similar studies show that the amount of usergenerated content is going to increase massively 5 and furthermore, that most of it will be generated by mobile devices, e.g., smart-phones et simila. This urges the need for easy access to the Internet for mobile users, since content has to be readily available. -Statistics show that the vast majority of households (e.g., 70% in UK) own a broadband connection6 , which remains unexploited most of the day. It is obvious that an area of dense connectivity can be formed if the HAPs' network and storage resources are being shared between home-and mobileusers. -User-Provided Networks and connectivity sharing schemes have already been investigated and implemented (e.g., FON [3]). In our previous studies [START_REF] Psaras | On Demand Connectivity Sharing: Queuing Management and Load Balancing for User-Provided Networks[END_REF], [START_REF] Mamatas | Incentives and Algorithms for Broadband Access Sharing[END_REF] we have presented algorithms for connectivity sharing among home-and guest-users and proved that careful design can guarantee seamless connectivity sharing for the home-user.

In this study, we explore the performance benefits of extending the users' connectivity graph to include neighbor HAPs, exploiting this way local unused resources. An occupied HAP that temporarily cannot forward packets from guestusers to the Internet may store the packets until a connection opportunity is available. The stored packets can be forwarded to another HAP in range, or relayed to a mobile node that may find another connectivity point.

We focus on the evaluation of DTN routing protocols, when the opportunistic network infrastructure is extended to also include HAPs, whenever and wherever these are available. We have built a realistic scenario, where mobile users walk around the center of London. We assume that existing FON subscribers (i.e., we used the database from maps.btfon.com) employ the proposed paradigm. We apply different usage scenarios to the home-users (e.g., periodic use, away for the day, away for work) in order to emulate their on-off behavior in terms of connectivity offering. We assume that whenever the home-user is transmitting/receiving data the HAP is not available to the guest user. Therefore, the connection is available for guests whenever the home connection is idle. At this stage, we explore how existing opportunistic routing algorithms behave in this particular context; we evaluate the following well-known algorithms: Epidemic [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], First contact [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF], Spray and Focus [START_REF] Spyropoulos | Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility[END_REF], Spray and Wait [START_REF] Spyropoulos | Spray and wait: Efficient routing in intermittently connected mobile networks[END_REF] and MaxProp [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF]. We elaborate on these results in order to draw design guidelines for new algorithms, especially designed and optimized for the proposed paradigm. Our target is to identify the necessary properties that need to be integrated into opportunistic routing protocols in order to operate as efficiently as possible under this new setting, i.e., when storage resources are part of the HAP and are offered to mobile users. We leave these designs as our immediate future work task.

Our findings indicate that: (i) integrating storage capabilities to HAPs substantially increases connectivity opportunities for mobile nodes, (ii) service quality for mobile users increases with the number of available HAPs and their respective storage resources, (iii) there is a lot of space for improvement for opportunistic routing protocols, performance-wise, (iv) among the evaluated algorithms Spray and Focus is the most efficient, since it balances better between performance and overhead, and (v) an efficient routing algorithm for this new networking paradigm could offload routing sophistication or routing state info from mobile devices to HAPs, in order to reduce energy consumption at mobile users, without compromising performance.

In Section 2, we discuss the related work in terms of other broadband access sharing schemes and opportunistic routing algorithms. In Section 3, we describe our experimental setup and the associated methodology and in Section 4 we present our experimental results. We conclude the paper in Section 5, where we also discuss our future work.

Related work

Broadly speaking, our study balances between User-Provided Networks and Opportunistic or Delay-Tolerant-Networks. Below, we briefly provide background, state of the art information on these areas and highlight how the present study advances research beyond the state of the art.

State of the Art

User-Provided Networks. UPNs have been recently proposed [START_REF] Sofia | User-provided Networks: Consumer as Provider[END_REF] as an umbrella framework for Broadband Access Sharing. Citywide Ubiquitous Wi-Fi Access sharing issues have been investigated in the past [START_REF] Thraves | Driving the Deployment of Citywide Ubiquitous WiFi Access[END_REF] and have shown that commercial deployment of such initiatives is indeed possible.

Famous commercial deployments include the FON Community, the OpenSpark Community and the Wifi.com 7 . Each of these deployments has a different starting point, incentive-wise, and therefore, comprises different scalability and efficiency properties. For instance, Wifi.com is based on a social networking approach, while FON is based on a business model that explicitly allocates resources to home-and guest-users. Recent studies have also investigated the wireless interface's capabilities to share resources [START_REF] Solarski | An Experimental Evaluation of Urban Networking using IEEE 802.11 Technology[END_REF].

The success of the above initiatives clearly shows that users are keen on giving away a portion of their bandwidth in order to have access when out of home or office. In our opinion, whatever the Broadband Access Sharing scheme, it has to balance between two fragile service-points: (i) the guarantee to the homeuser for seamless sharing, performance-wise and (ii) the mobile-users' quality of experience. The former point has been our focus in previous studies [START_REF] Psaras | On Demand Connectivity Sharing: Queuing Management and Load Balancing for User-Provided Networks[END_REF], [START_REF] Mamatas | Incentives and Algorithms for Broadband Access Sharing[END_REF]. The latter constitutes our target in the present study, where we elaborate on the functionality of an efficient routing mechanism in order to achieve lower latency and reduced transmission redundancy. Hence, our target is increased responsiveness, efficient storage management and longer battery life for mobile devices.

Opportunistic Networks and DTNs. A lot of research has taken place recently to deal with routing issues in intermittently connected networks. Here, we briefly present the most prevalent DTN routing algorithms.

In Epidemic routing algorithm [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], a node copies a message to every other node it encounters. Variations of this algorithm include Randomized flooding and Utility-based flooding. Randomized flooding or Gossiping (random-flood) is quite similar to Epidemic although each message is copied with probability p < 1. In the Utility-based flooding, a message is copied only if the node encountered has a utility value higher than the current by some threshold U th .

MaxProp [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF] is another flooding-based mechanism which removes the messages once a copy is delivered. Moreover, MaxProp prioritizes both messages to be transmitted and dropped based on previous encounters.

Resource Allocation Protocol for Intentional DTN (RAPID) [START_REF] Balasubramanian | DTN routing as a resource allocation problem[END_REF] treats DTN routing as a resource allocation problem. It uses a utility function that: (i) assigns a value based on the metric being optimized to every packet and (ii) first replicates packets that increase the utility function.

Other approaches use a controlled replication or spraying. In Spray and Wait [START_REF] Spyropoulos | Spray and wait: Efficient routing in intermittently connected mobile networks[END_REF], a small fixed number of copies are distributed (sprayed) to different relays (i.e., the first few encountered). Each relay waits until it encounters the destination itself. A more sophisticated variation is Spray and Focus [START_REF] Spyropoulos | Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility[END_REF] which operates like Spray and Wait during spraying. Each relay, instead of waiting, can forward its copy to a potentially more appropriate relay, using a utility-based scheme.

For a complete survey on DTN routing protocols, we refer the reader to [START_REF] Small | Resource and performance tradeoffs in delay-tolerant wireless networks[END_REF] and [START_REF] Psaras | Delay-/Disruption-Tolerant Networking: State of the Art and Future Challenges Technical Report[END_REF]. In addition, related work on exploiting WLAN hotspots in order to enhance opportunistic web access and offload cellular traffic can be found in [START_REF] Pitkänen | Opportunistic Web Access via WLAN Hotspots[END_REF] and [START_REF] Han | Cellular traffic offloading through opportunistic communications: a case study[END_REF], respectively.

Progress Beyond the State of the Art

To release the boundaries that keep these two research fields separated and unleash the communication opportunities of the corresponding framework, we highlight the following:

-UPNs exploit connectivity sharing opportunities only. Broadband access is only one of the available resources that can be shared between home and mobile users. In this study, we explore the potential of sharing storage resources as well, given that storage is available at the HAPs. That is, we extend the sharing capabilities of UPNs to include storage resources as well.

-DTN routing research has been mainly concerned with encounters between mobile nodes only. Although in case of DTN nodes, both connectivity and storage resources are shared between the nodes, they do not consider collaborating with fixed points of the infrastructure. Here, we extend this trend to a boundless framework, where mobile nodes can also take advantage of both connectivity and storage resources of HAPs.

Experimental Setup and Methodology

We simulate a realistic mobility setup. We have chosen a geographical area in the center of London sized 2160m x 1600m, see Fig. 1. This area covers 349 different streets and 1876 landmarks. We have gathered detailed information from [3] regarding the exact position and the number of BTFON users in this particular area (i.e., 118 users). We parsed all this information into the ONE simulator [START_REF] Keränen | The ONE Simulator for DTN Protocol Evaluation[END_REF].

We extended the ONE simulator with better support for wired networks and two new types of nodes: (i) the home-user that owns a HAP, and (ii) a server node, which hosts data for the mobile users (e.g., social profile photos). We assume that all home-users are permanently connected to a server node (e.g., a server farm) situated in Gower Street (see Fig. 1).

Mobile nodes are moving in the area and transmit periodically data (every 60 to 80 seconds, according to a uniform distribution) to the server node. Message sizes follow the uniform distribution [100kB, 200kB] (e.g., a typical social profile photo). Their movement is restricted to the streets in the map, according to the map route movement model and the shortest path algorithm in ONE simulator.

All nodes (mobile and static) have storage capabilities, but static nodes, i.e., HAPs, comprise extensive storage resources. In our setup, mobile nodes and HAPs have 30MB of storage available. These are only indicative figures and serve as pointers for future settings. As already mentioned, the HAP is only available to mobile users, whenever the home-user is idle. This practically means that when the home-user is using his Internet connection, only storage capabilities are offered to the mobile nodes within range. We assume three representative home-user profiles: (i) users that are idle for 8 hours per day only (e.g., during working hours), (ii) users that are permanently idle (e.g., they are absent), and (iii) users that are only periodically using their connection throughout the day (i.e., according to a normal probability distribution: 1-3 hours at home and 1-2 hours away). Nodes periodically transmit beacons to recognize each other's presence. Fig. 1, shows our experimental setup. The server is referenced as snode, mobile-guests as g-nodes and home-users as h-nodes.

At this stage of investigation, we evaluate how existing opportunistic routing algorithms behave in this particular scenario, where HAPs offer storage resources apart from only connectivity. We selected five representative storage-enabled algorithms, namely: Epidemic [START_REF] Vahdat | Epidemic routing for partially connected ad hoc networks[END_REF], First contact [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF], Spray and Wait [START_REF] Spyropoulos | Spray and wait: Efficient routing in intermittently connected mobile networks[END_REF], Spray and Focus [START_REF] Spyropoulos | Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility[END_REF] and MaxProp [START_REF] Burgess | MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks[END_REF]. Our target is to identify key requirements and design guidelines for a customized algorithm that exploits efficiently not only connection opportunities, but storage resources as well.

Since a crucial aspect is to maximize energy efficiency of the mobile nodes, a maximum data delivery ratio should be combined with minimum communication / storage overhead and latency. In this context, we measure the following:

-OverheadRatio = P acketsRelayed-P acketsReceived P acketsReceived , which captures packet delivery ratio with respect to the number of packets relayed.

-AverageLatency, which captures the average packet latency that increases with the number of hops the packet crosses. -AverageBuf f erT ime, which reflects the average time the packets are buffered, in order to evaluate protocol storage efficiency.

Experimental Results

The experimental scenarios presented in the next section were designed in order to allow for:

-Studying the impact of the proposed extended networking scheme on the performance of a representative opportunistic routing algorithm. In this context, the Epidemic8 protocol was evaluated in various deployment levels by increasing the number of HAPs in Scenario 1. In Scenario 2, evaluation is based on different usage profiles that home-users adopt. The purpose is to show the advantages of the proposed framework, i.e., the extension of mobile network's boundaries to also include storage-equipped HAPs.

In this first scenario, we explore the performance of a representative opportunistic routing protocol and more specifically Epidemic with 100 mobile-users, where the availability of HAPs is gradually increased (0-100). Home-users can be perceived as points of guaranteed message delivery to the destination server. We observe in Fig. 2(a), that as the number of home-users increases, the average Latency declines, since less time is needed to reach a connectivity point to the Internet. Consequently, the average buffering time declines as well, as is shown in Fig. 2(b), owing to timely message delivery. The peak in measurements (i.e., Figures 2(a), 2(b)) for 5 home-users can be justified as follows: most of the first five HAPs in our database are situated in peripheral streets. Hence, they have low interaction probability with mobile nodes and consequently they do not get involved in the replication process. Therefore, average buffering time increases (Fig. 2(b)), since mobile nodes need to carry data for more time. Clearly, there are still more delivery probabilities than in the case of zero home-users (Fig. 2(a)), where the server is the only data delivery point. In conclusion, increasing the availability of storage-equipped HAPs enhances network's connectivity, thus average Latency and Buffering time decrease. Here, each home-user adopts one of the three usage-profiles described in Section 3.1. This scenario intends to study the behavior of a representative opportunistic routing protocol in a topology consisting of 118 home-users with different usageprofiles. We discriminate the cases according to home-users' percentage that follows each of the three usage profiles: A) away for 8 hours, B) always away, C) periodically away (1-3 hours at home, then 1-2 hours away). Moreover, we simulated the cases where (A, B, C) percentages are: i) (0, 100, 0), ii) [START_REF] Han | Cellular traffic offloading through opportunistic communications: a case study[END_REF]40,40), iii) (10, 10, 80), iv) (0, 0, 100), while guest-users vary (10-100).

We conducted a series of experiments where increasing home users with usage profiles (i) and (iii), causes lack of connectivity, while increasing the number of guest-users allows for more routes and improved message delivery in terms of time. In these experiments, we observed that data remains stored at homeusers available for: i) delivery to the server when connection will be up, ii) transmission to a guest-user in the vicinity, iii) transmission to a home-user in the vicinity. Fig. 3(b) presents average buffering time, which decreases as mobile nodes increase, while the four graphs coincide. Clearly, usage-profile has small impact on buffering time, since the number of home-users is sufficiently large. On the contrary, average Latency graphs vary, and their values increase when periodic nodes increase, while increasing guest-users decreases average Latency as depicted in Fig. 3(a). We report, although not present it here due to space limitations, that Overhead ratio is not influenced by usage-profile. Usage-profiles appear to have significant impact on average Latency, while Epidemic protocol manages to deliver messages, though with a high overhead. In this scenario, we aim to compare the functionality of all five protocols and highlight the most efficient strategy, in the extended opportunistic networking paradigm introduced herein. The topology consists of 118 HAPs constantly available, while mobile nodes vary .

Spray and Wait introduces the highest average Buffering time (see Fig. 4(b)), which is not affected by the number of guest-users, while Spray and Focus achieves the lowest. Both algorithms were configured with 6 message copies, therefore their behavior at spraying phase is identical; consequently, the focus phase is responsible for the significant reduction of buffering time, as opposed to the wait phase. Fig. 4(a), depicts the average Latency, where Spray and Focus is again outperforming the rest of the protocols. First contact is the worst performing algorithm, since the first encountering node has no guarantee to deliver the message immediately. The Overhead ratio in Fig. 4(c) evinces the efficiency of Spray and Focus mechanism compared to the others. As expected Epidemic did not perform well with regards to overhead owing to mere flooding.

Therefore, increasing guest-users' number improves the average latency, except from First Contact. Furthermore, it also reduces average buffering time at the expense of overhead. In summary, regarding the impact of guest-users' number, Spray and Focus is the most efficient of the tested algorithms. The speed of mobile nodes, together with connectivity opportunities, the message size and links' bandwidth are critical to protocol's efficiency. Increased speed allows for more encounters with other nodes, although it reduces the communication time. Using realistic settings, we evaluate the performance of the five protocols with regards to speed differentiation, for 10 guest-(maximum supported number for the specific configuration) and 118 home-users available.

Increasing speed (1 to 20 m/s) allows for increased data relaying due to more encounters and reduces the average buffering time (Fig. 4(e)). Spray and Focus has the best performance, even though it is the only algorithm whose buffering time increases with speed; this is due to utility function's inability to adapt to increased encounters. This result shows the potential improvement of the specific algorithm in this context. Average latency in Fig. 4(d) is highly decreased for low speeds (5 m/s), while further speed increase does not affect the results. Fig. 4(f) depicts the overhead ratio, where Epidemic routing has the highest overhead ratio in contrast to Spray and Focus. In conclusion, Spray and Focus is the best performing algorithm in this scenario with regards to all evaluation parameters.

Conclusions

We have proposed and investigated a cooperative networking scheme, in the context of User-Provided Networks, where storage resources are offered to mobile users, until bandwidth at HAPs becomes available to transmit mobile users' data. Storage-enabled nodes and access points are a key feature of our opportunistic networking paradigm. We evaluated the impact of this scheme on the performance of opportunistic routing and compared the performance of five wellknown DTN routing protocols in a realistic simulation setting. The proposed networking scheme avails in terms of latency and buffering time, although overhead ratio is sometimes increasing. Since mobile devices are involved, an efficient routing protocol that achieves high delivery ratio and low overhead is crucial. We have concluded that Spray and Focus [START_REF] Spyropoulos | Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility[END_REF] is the most suitable for the aforementioned scheme, amongst the evaluated protocols.

These preliminary results indicate that a new DTN routing protocol suitable for this environment can achieve improved overall performance. Its functionality should allow for reduced latency, communication and storage overhead, in conjunction with high delivery ratio, even in case of opportunistic routing (few and sparse HAPs). We argue that the basic guidelines for the design of the algorithm are: (i) Route data through HAPs with a higher probability than mobile nodes in order to alleviate the latter's storage and energy constraints. (ii) Exploiting HAP density and offloading sophistication or routing state info from mobile nodes to HAPs will further enhance performance e.g., via encounter prediction. (iii) Integration of Spray and Focus functionality in order to perform efficiently when mobile nodes are dominant in the topology. (iv) Dynamic configuration of message redundancy according to feedback from encounters and time scales [START_REF] Karvo | Time scales and delay-tolerant routing protocols[END_REF], will allow for low overhead in conjunction with the desired delivery rate. As a next step we intend to integrate these observations in a new protocol.

Fig. 1 .

 1 Fig. 1. Experimental Scenario

Fig. 2 .

 2 Fig. 2. Scenario 1: Impact of Home-Users' Number

Fig. 3 .

 3 Fig. 3. Scenario 2: Impact of Home-Users' Usage-Profiles

4. 4

 4 Scenario 4: Impact of Guest-Users' Speed.

Fig. 4 .

 4 Fig. 4. Scenario 3: (a), (b), (c), Scenario 4: (d), (e), (f)

Vehicular DTNs[START_REF] Bychkovsky | A Measurement Study of Vehicular Internet Access Using in Situ Wi-Fi Networks[END_REF] and Infostations[START_REF] Goodman | INFOSTATIONS: a new system model for data and messaging services[END_REF] can be considered as exceptions here, since these deployments are not constrained by energy and/or storage depletion in most cases

http://www.cisco.com/en/US/netsol/ns827/networking solutions sub solution.html

http://newsroom.cisco.com/dlls/2009/prod 102109.html

http://www.statistics.gov.uk/cci/nugget.asp?ID=8

URLs: http://www.btfon.com, http://open.spark.fi, http://www.wifi.com

Epidemic protocol was selected for these scenarios and more specifically Epidemi-cOracle version, which upon message delivery removes that message from all nodes.

The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013 FP7-REGPOT-2010-1, SP4 Capacities, Coordination and Support Actions) under grant agreement n o 264226 (project title: Space Internetworking Center-SPICE ).