Predictable disruption tolerant networks and delivery guarantees

Report (2006)

This article studies disruption tolerant networks (DTNs) where each node knows the probabilistic distribution of contacts with other nodes. It proposes a framework that allows one to formalize the ... [more ▼]

This article studies disruption tolerant networks (DTNs) where each node knows the probabilistic distribution of contacts with other nodes. It proposes a framework that allows one to formalize the behaviour of such a network. It generalizes extreme cases that have been studied before where (a) either nodes only know their contact frequency with each other or (b) they have a perfect knowledge of who meets who and when. This paper then gives an example of how this framework can be used; it shows how one can find a packet forwarding algorithm optimized to meet the 'delay/bandwidth consumption' trade-off: packets are duplicated so as to (statistically) guarantee a given delay or delivery probability, but not too much so as to reduce the bandwidth, energy, and memory consumption. [less ▲]

A scalable and decentralized fast-rerouting scheme with efficient bandwidth sharing

in Computer Networks (2006), 50(16), 3043-3063

This paper focuses on the protection of virtual circuits (Label Switched Paths, LSPs) in a (G)MPLS (Generalised Multi-Protocol Label Switching) network. The proposed algorithm is designed to protect ... [more ▼]

This paper focuses on the protection of virtual circuits (Label Switched Paths, LSPs) in a (G)MPLS (Generalised Multi-Protocol Label Switching) network. The proposed algorithm is designed to protect traffic with strong delay requirements such as EF (Expedited Forwarding) ordered aggregates in a DiffServ domain. Indeed, for this type of application, we need fast restoration in case of failure. The duplication of all the packets in a 1 + 1 end-to-end restoration scheme consumes a large amount of bandwidth. Furthermore, end-to-end recovery with bandwidth sharing schemes are usually considered to be far too slow. Local fast-rerouting is a solution which can compete with restoration times and bandwidth consumption offered by SONET self-healing rings. Our scheme includes a sophisticated resource aggregation mechanism based on the concepts of "backup-backup aggregation" and "backup-primary aggregation". The path selection algorithm is also designed to efficiently reduce the resource usage. Moreover, when considering LSPs at different preemption levels, our algorithm is able to correctly calculate the amount of bandwidth that can be preempted despite the sharing of resource. We show that our approach, though local, can compete with the state-of-the-art end-to-end recovery schemes in terms of resource consumption. The major contribution of our scheme, the "backup-primary aggregation", was then also used in the context of end-to-end recovery and improved its performance substantially. To be able to save a maximum amount of bandwidth in a decentralised implementation, the nodes that compute backup LSPs need to obtain a certain amount of link-state information. We propose a solution where the nodes learn almost all the information they need with RSVP messages. This drastically reduces the information that needs to be flooded in the whole network and is the first scalable decentralised solution capable of sharing a large amount of bandwidth. (c) 2005 Elsevier B.V. All rights reserved. [less ▲]

Prédiction de mobilité par le mobile ou par le point d'accès: comparaison sur base de traces réelles

in CFIP'2006 (2006, November)

Le problème de la prédiction de mobilité se définit comme le fait de deviner quel sera le prochain point d'accès rencontré par un terminal mobile lors de son déplacement dans un réseau sans fil. Les ... [more ▼]

Le problème de la prédiction de mobilité se définit comme le fait de deviner quel sera le prochain point d'accès rencontré par un terminal mobile lors de son déplacement dans un réseau sans fil. Les prédictions faites permettent d'améliorer la qualité de service fournie par le réseau en lui permettant de prendre des mesures pro-actives (telles des réservations de ressources). Les agents de prédiction se classent principalement en deux catégories: les agents liés à un mobile particulier (responsables d'anticiper les déplacements de celui-ci) et ceux liés à un point d'accès (prédisant le prochain point d'attache de tous les terminaux y étant connectés). Cet article vise à comparer les deux méthodes à l'aide de traces réelles tirées d'un réseau WiFi de grande taille. Il montre que certains postulats souvent admis (comme le fait que les habitudes de mouvement du week-end sont différentes de celles du reste de la semaine) doivent être revus. [less ▲]

A scalable heuristic for hybrid IGP/MPLS traffic engineering - Case study on an operational network

in 14th IEEE International Conference on Networks (2006, September)

In current IP networks, a classical way to achieve traffic engineering is to optimise the link metrics. This operation cannot be done too often and can affect the route of a lot of traffic. Multiprotocol ... [more ▼]

In current IP networks, a classical way to achieve traffic engineering is to optimise the link metrics. This operation cannot be done too often and can affect the route of a lot of traffic. Multiprotocol Label Switching (MPLS) opens new possibilities to address the limitations of IP systems concerning traffic engineering thanks to explicit label-switched paths (LSPs). This paper proposes a new method based on simulated annealing meta-heuristic to compute a set of LSPs that optimise a given operational objective. The hybrid IGP/MPLS approach takes advantage of both IP and MPLS technologies and provides a flexible method to traffic engineer a network on a day to day basis. We illustrate the capabilities of our method with some simulations and a comparison with other techniques on an existing operational network. The results obtained by setting up a small number of LSPs are nearly optimal and better than by engineering the IGP weights. Moreover, although it could be combined with a static setting of the latter, SAMTE alone gives already the same results as this combination in much less CPU time, which thus allows an administrator to keep its initial and meaningful IGP metrics in his network. [less ▲]

Multiple Description Coding versus Transport Layer FEC for Resilient Video Transmission

(2006, August)

Video content delivery is a challenging task due to its large bandwidth requirements and its sensitivity to transmission errors. In this context, simultaneously providing scalability and resilience ... [more ▼]

Video content delivery is a challenging task due to its large bandwidth requirements and its sensitivity to transmission errors. In this context, simultaneously providing scalability and resilience against transmission errors is of paramount importance. Layered video coding coupled with multicast video transmission employing no feedback provides the required scalability features and reduces the network burden. However, it is not easy to provide reliability in such environments. This is crucial to mobile users as error rates on wireless links can be high. To compensate for transmission errors, redundancy must be added to the video content. This can be added at the application layer by the employed video coding system, or can be added transparently by the transport layer. In this paper, we compare the performance obtained with a scalable wavelet-based video codec that adds redundancy using multiple description coding with the equivalent system adding redundancy at the transport level, using forward error correction. [less ▲]

How well do traffic engineering objective functions meet TE requirements?

in Lecture Notes in Computer Science (2006, May), 3976

We compare and evaluate how well-known and novel networkwide objective functions for Traffic Engineering (TE) algorithms fulfil TE requirements. To compare the objective functions we model the TE problem ... [more ▼]

We compare and evaluate how well-known and novel networkwide objective functions for Traffic Engineering (TE) algorithms fulfil TE requirements. To compare the objective functions we model the TE problem as a linear program and solve it to optimality, thus finding for each objective function the best possible target of any heuristic TE algorithm. We show that all the objective functions are not equivalent and some are far better than others. Considering the preferences a network operator may have, we show which objective functions are adequate or not. [less ▲]

TOTEM: A Toolbox for Traffic Engineering Methods

Poster (2006, April)

In this document, we propose a demonstration of TOTEM, a TOolbox for Traffic Engineering Methods. This toolbox integrates a series of tools for intra-domain and inter-domain traffic engineering of IP and ... [more ▼]

In this document, we propose a demonstration of TOTEM, a TOolbox for Traffic Engineering Methods. This toolbox integrates a series of tools for intra-domain and inter-domain traffic engineering of IP and MPLS networks. It provides an open source software that allows an operator to test methods coming from the academic research. A researcher can also use the toolbox to compare and promote new TE algorithms. The toolbox is designed to be deployed either as an on-line tool in an operational network, or as an off-line traffic engineering simulator. [less ▲]

A survey of optimal network congestion control for unicast and multicast transmission

in Computer Networks (2006), 50(3), 448-468

In the last few years, there has been a large body of literature on congestion control based on optimization and control theories. This paper provides an overview of optimization flow control starting ... [more ▼]

In the last few years, there has been a large body of literature on congestion control based on optimization and control theories. This paper provides an overview of optimization flow control starting from the first original papers, and traces the development in a unified framework, from unicast to multicast, from theory to algorithms to implementation issues. The optimal congestion control problem is formulated, both for unicast and multicast. Decentralized theoretical solutions are derived by applying duality theory. Based on these results, actual generic algorithms and implementations are proposed for solving these problems in a distributed way. Some alternative methods not based on duality theory are also reviewed. Finally the complementary problem of choosing suitable utility functions in the optimization problem is addressed. (c) 2005 Elsevier B.V. All rights reserved. [less ▲]

The Critical Neighbourhood Range for Asymptotic Overlay Connectivity in Ad Hoc Networks

in Ad Hoc & Sensor Wireless Networks (2006), 2(2), 169-187

We first motivate the use of ad hoc overlays. In particular, we argue that overlay routing could play a role in the spreading of ad hoc networks. We then define a simple criterion for neighbourhood: two ... [more ▼]

We first motivate the use of ad hoc overlays. In particular, we argue that overlay routing could play a role in the spreading of ad hoc networks. We then define a simple criterion for neighbourhood: two overlay nodes are neighbours if and only if there exists a path between them of at most R hops, and R is called the (overlay) neighbourhood range. A small R may result in a disconnected overlay, while an unnecessarily large R would generate extra control traffic. We are interested in the minimum R ensuring overlay connectivity, the so-called critical R. We study conditions on R to achieve asymptotic connectivity of the overlay almost surely, i.e. connectivity with probability 1 when the number of nodes in the underlying ad hoc network tends to infinity (so-called dense networks) or when the size of the field tends to infinity (socalled sparse networks), under the hypothesis that the underlying ad hoc network is itself asymptotically almost surely connected. For dense networks, we derive a necessary and sufficient condition on R, and for sparse networks we derive distinct necessary and sufficient conditions that are however asymptotically tight. These conditions, though asymptotic, shed some light on the relation linking the critical R to the number of nodes n, the field size the radio transmission range r and the overlay density D (i.e., the proportion of overlay nodes). These conditions can be considered as approximations when the number of nodes (resp. the field) is large enough. Since r is considered as a function of n or l , we are able to study the impact of topology control mechanisms, by showing how the shape of this function impacts the critical R. [less ▲]

Entropy-based knowledge spreading and application to mobility prediction

(2005, October)

The low quality of service provided by wireless networks does not facilitate the setup of long-awaited services, such as video conversations. In a cellular network, handoffs are an important cause of ... [more ▼]

The low quality of service provided by wireless networks does not facilitate the setup of long-awaited services, such as video conversations. In a cellular network, handoffs are an important cause of packet losses and delay jitter. These problems can be mitigated if proactive measures are taken. This requires each cell to guess the next handoff of each mobile terminal, a problem known as mobility prediction. This prediction can occur thanks to some clues (such as signal strength measurements) giving information about the terminals motion. For example, a clue that locates on which road a mobile is moving is likely to be interesting for all the prediction-enabled cells along that road ---and should therefore be sent to them. This paper proposes a new method aimed at selecting the most relevant clues and finding where to propagate those clues so as to optimize mobility predictions. The pertinence of a clue is measured using information theory and by means of decision trees. This pertinence estimation is exchanged between the cells and allows to build a"relevance map" that helps determine where clues should be sent. It is adapted to the characteristics of wireless terminals such as low bandwidth and processing power. [less ▲]