Gérard Chollet
email: gerard.chollet@telecom-paristech.fr

Daniel Régis

Sarmento Caon

Thierry Simmonet

Jérôme Boudy

Daniel R S Caon
email: daniel.caon@telecom-paristech.fr

Thierry Simonnet
email: t.simonnet@esiee.fr

vAssist : Le Majordome des personnes dépendantes

Keywords: Majordome, memex, MyLifeBits, dialogue vocal, VVoIP

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

C'est en 1945 que V. Bush a décrit un appareil électronique (le memex) relié à une bibliothèque et capable d'afficher des livres et de projeter des films [START_REF] Bush | As We May Think[END_REF]. Cet article a inspiré les créateurs du 'World Wide Web' (le web). Le terme 'memex' est une contraction de 'memory extender'. Le web peut-être considéré comme la mémoire du monde; une partie est publique (tout utilisateur d'internet peut y accéder), une partie est privée (seuls certains utilisateurs, et parfois un seul, y ont accès).

Notre mémoire, souvent défaillante, est complétée par celle du web. Des moteurs de recherche nous facilitent l'accès aux informations disponibles sur le web. Il suffit d'utiliser un téléphone portable pour accéder à toutes ces informations.

Des informations personnelles peuvent aussi être collectées et indexées [START_REF] Gemmell | MyLifeBits: a personal database for everything[END_REF]. Cette mémoire peut être disponible sur un serveur personnel local ou distant. C'est notre prothèse mémorielle [11].

Une population visée est celle atteinte de la maladie d'Alzheimer, sous des formes précoces ('Mild Cognitive Impairment') [START_REF] Gitlin | Améliorer la qualité de vie des personnes atteintes de démence: le rôle de l'approche non pharmacologique en réadaptation[END_REF], [START_REF] Armstrong | Using smartphones to address the needs of persons with Alzheimer's disease[END_REF], [START_REF] Rigaud | Un exemple d'aide informatisée à domicile pour l'accompagnement de la maladie d'Alzheimer : le projet TANDEM[END_REF], mais les personnes âgées et d'autres personnes pourront utiliser ce dispositif. Notre hypothèse est qu'un système Majordome adapté aux difficultés des personnes et contrôlé par elles-mêmes pourrait contribuer à leur soutien au domicile en leur fournissant une stimulation cognitive et en jouant le rôle de prothèse cognitive. Le Majordome, conçu pour s'inscrire dans un écosystème d'objets communicants, comporte deux parties: • Quelques scénarios d'usage sont proposés en section 2 ;

• l'architecture de Voix et Vidéo sur IP est détaillée en section 3 ;

• le système de dialogue vocal en décrit en section 4 ;

• les résultats d'évaluation du système de reconnaissance automatique de la parole sont fournis en section 5 ; • suivi par des conclusions et perspectives.

Scénarios d'usage

Supposons que l'on dispose en permanence d'un accès à une prothèse mémorielle personnelle et collective relayé par un Majordome audio-visuel. Quels sont les usages que nous pourrions en faire ? En voici une liste non exhaustive :

•

Voix et Vidéo sur IP

Le Majordome (smartphone) communique avec le serveur en conformité avec le protocole SIP.

SIP (Session Initiation

PABX

Le PABX Asterisk est configuré de manière à offrir toutes les fonctionnalités de téléphonie classique et d'offrir les services de transmission vidéo.

Nous avons également mis en place les services de boite vocale, de manière à banaliser l'architecture et à offrir un service le plus proche possible du téléphone classique.

Un • Pour la vidéo : h261, h263, h263+, h264 Il faut trouver un équilibre entre les facteurs « compression », « délai » et « qualité d'image ». La compression et le délai sont liés. Un facteur de compression élevé entraînera un délai de bufferisation élevé. Les codecs haute définition comme H264 sont actuellement peu adaptés aux transmissions de type visiophonie. Ils sont utilisés pour la télévision HD, application ou le délai de transmission n'est pas critique (flux unidirectionnel).

Nous nous sommes limités à l'utilisation de l'encodage H261 qui offre un ratio performance/délai correspondant à notre besoin.

Client SIP

Un client SIP doit fournir, pour notre application de visiophonie, un service contraint: faible latence et bonne qualité d'image. Un système de QoS doit être établi pour garantir une fluidité constante. Le client SIP doit être en mesure d'équilibrer dynamiquement le taux de compression et la qualité des différents canaux (vidéo et audio) pour s'adapter à la bande passante. Il doit également assurer l'arbitrage entre les flux audio et vidéo. Une application de la surveillance par exemple n'a pas besoin d'une grande qualité de son, mais d'une latence faible, alors que la priorité pour une application de visiophonie est la voix.

Le PABX Asterisk n'assure pas de fonction de traduction de codecs. C'est pourquoi le choix des codecs utilisés et le soft-phone est important. Le protocole SIP permet aux deux clients (appelant et appelé) une auto-négociation afin d'obtenir un couple de codecs pour l'encodage audio et vidéo compatible et optimal.

Nous avons choisi Ekiga comme client SIP pour plusieurs raisons:

• Il est Open-source et peut donc être modifié.

• Il est portable (Linux, Windows).

• Il offre nativement un bon nombre de codecs (H261, H264, Theora, PCMU, GSM ,...) • De par son architecture, l'utilisation de la libglade (bibliothèque de codes) nous permet de modifier l'interface graphique à partir de fichiers XML qui sont crées avec Glade (le constructeur Gnome GUI).

Nous avons travaillé sur le client Ekiga, en intégrant le projet OpenSource et en prenant en charge la version Windows de ce projet.

Nous avons donc contribué en ajoutant une fonction de réponse automatique, qui peut être intéressante pour l'appel de personnes âgées. Cette fonction est débrayable pour garder la possibilité de ne pas répondre à un appel.

Nous avons également modifié l'interface graphique pour la simplifier (l'interface présente 4 gros boutons, sur lequel il est possible d'afficher la photo du correspondant. Les numéro de téléphone sont également pré-programmés évitant ainsi toute possibilité d'erreur dues à la manipulation du clavier et/ou de la souris.

Les premières expérimentations ont montré un délai de transmission sur réseau local de l'ordre de 400ms. Ces délais ont été ramenés a 80ms en utilisant internet, sans QoS.

Limitations et Evolutions

Julius et HTK

Le module de reconnaissance vocale est fondé sur l'usage des Modèles de Markov Cachés classiques (MMC) permettant de modéliser de manière statistique les modèles acoustiques des phonèmes ou/et mots utilisés dans le vocabulaire visé à l'aide d'outils logiciels comme HTK [START_REF] Young | The HTK Book (version 3.4)[END_REF] et Julius [START_REF] Lee | EUROSPEECH. Julius -an open source real-time large vocabulary recognition engine[END_REF]. Les modèles de langage (probabilités linguistiques complémentaires aux probabilités acoustiques) sont implicitement abordés dans l'usage de tels modèles statistiques afin de rendre robuste la reconnaissance des mots dans une phrase donnée (utilisation des statistiques N-grams et des règles de grammaire).

Données et Adaptation

Des stratégies d'adaptation seront mises en oeuvre, en particulier basée sur l'adaptation multi-langue croisée entre langues ayant des matériaux phonétiques riches.

Les travaux de recherche de Tania Schultz [START_REF] Schultz | Multilingual Speech Processing[END_REF], Rania Bayeh [START_REF] Bayeh | Reconnaissance de la Parole Multilingue: Adaptation de Modeles Acoustiques Multilingues vers une langue cible[END_REF] et Gérard Chollet [START_REF] Constantinescu | On cross-language experiments and data-driven units for alisp (automatic language independent speech processing)[END_REF], concernant la reconnaissance de parole multi-linguale et indépendante de la langue, servent de point de départ.

Évaluation

Une première validation des logiciels de reconnaissance automatique de la parole a été réalisée sur des données enregistrées dans le cadre du projet européen CompanionAble (www.companionable.net). Chacun des 22 locuteurs hollandais ont été enregistrés pendant une heure dans une maison expérimentale (SmartHomes) à Eindhoven. Ils ont répétés des phrases prononcées par un 'souffleur'. Le tableau suivant (contenant 37 phrases différentes) donne des résultats obtenus pour un de ces locuteurs, après adaptation des modèles acoustiques à sa voix par MLLR (Maximum Likelihood Linear Regression, technique classique d'adaptation aussi étudiée dans [START_REF] Caon | Experiments on acoustic model supervised adaptation and evaluation by k-fold cross validation technique[END_REF]). Le taux "sémantiquement correct" est une manière de décrire que deux phrases sont au même niveau de sens (e.g. "help me" et "hellep"), donc si "help me" est reconnu au lieu de "hellep", la phrase est 100% correcte (sémantiquement) et le dialogue vocal peut se dérouler sans problème.

La deuxième validation des logiciels a été fait sur 20 des locuteurs (tous âgés), sans répétition de phrases. Une technique d'adaptation classique MAP (Maximum a Posteriori, aussi étudiée dans [START_REF] Caon | Experiments on acoustic model supervised adaptation and evaluation by k-fold cross validation technique[END_REF]) a été appliquée à partir d'un set de 10 phrases d'adaptation pour chaque locuteur. La figure 4 donne les taux de reconnaissance de mots par des modèles de langage 2-gram et 6-gram, avec et sans adaptation des modèles acoustiques. On constate l'amélioration obtenue grâce à l'adaptation et à la précision du modèle de langage. On voit aussi que les locuteurs n'utilisent pas tous le système de reconnaissance avec les mêmes taux de succès. L'infrastructure nécessaire à l'expérimentation d'un majordome mobile est en place. Elle utilise des briques logicielles libres aussi bien pour les télécommunications (PABX -Asterisk) et le traitement automatique de la parole (Julius).

Des résultats expérimentaux ont été obtenus en reconnaissance automatique de la parole sur des donnés enregistrées dans le cadre du projet CompanionAble. Dans le cadre de vAssist, un smartphone (sous Android) sera utilisé. Le serveur Asterisk est opérationnel pour l'expérimentation de services liés aux scénarios d'usage listées en section 2.

  Protocol) L'utilisation d'une infrastructure de VoIP implique la mise en place d'un PABX (autocommutateur) logiciel. Nous avons retenu le produit de DIGIUM [2]. Celui-ci est configuré pour gérer les communications vocales, mais également pour prendre en charge la vidéo. Le réseau local des patients étant en adressage IP privé, un autocommutateur local doit être installé chez chaque patient et raccordé au PABX central. Cette architecture utilisera la topologie en trapèze SIP:

Fig. 1 .

 1 Fig. 1. Architecture en trapèze SIP.

Fig. 2 .

 2 Fig. 2. Déroulement d'un appel. La figure 3 illustre le positionnement des différentes composantes dans le système de couches OSI.

Fig. 3 .

 3 Fig. 3. SIP et les couches OSI.

•

  Nous avons constaté une incompatibilité quant à l'utilisation de Windows Vista. Nous nous sommes concentré sur une cible Windows XP. • Un gros travail a été effectué pour réduire les délais de transmissions (entre 30ms et 80ms) • Le PABX Asterisk est public (à condition d'avoir un compte) et opérationnel avec tout client SIP (Ekiga, X-Lite, linphone, ...): wagram.esiee.fr. • Les services proposés sont les suivants: • Conférence : Changement de canal vidéo par DTMF (appui de la touche du numéroteur) • Messagerie instantanée en cours de conversation. • Interfaçage en cours avec gtalk, msn, aim et yahoo messenger. • Interfaçage avec Julius (ASR) pour la reconnaissance vocale. • IVR vidéo 4 Dialogue vocal La communication entre le client et son majordome se fait de façon naturelle par la voix. Pour cela un moteur de dialogue est installé sur le serveur. Ce moteur utilise un système de reconnaissance open source Julius disponible sur la plate forme Asterisk.

Fig 4 .

 4 Fig 4. Évaluations de 20 locuteurs âgées (micro cravate).

•

  Une plate-forme fixe de divertissement qui regroupe les exercices de stimulation cognitive, la téléphonie, l'accès à internet, la télévision, la vidéoconférence (relation avec l'aidant, la famille et le personnel soignant), la gestion des documents administratifs, médicaux, bancaires, impôts, factures,...

• Un système portable et communicant, le Majordome qui permet au patient d'alerter l'aidant en cas de chute

[START_REF] Baldinger | Tele-surveillance system for patient at home: The mediville system[END_REF]

ou de comportement anormal, de connaître sa localisation en dehors de son domicile, de rester en contact téléphonique avec son aidant, de se faire rappeler ses tâches,... Cet article est structuré comme suit :

  • détecter des situations de détresse, les comportements anormaux,… Certaines de ces fonctionnalités sont déjà disponibles sur des SmartPhones, d'autres sont en cours de développement comme le projet MyLifeBits de Microsoft[START_REF] Gemmell | MyLifeBits: a personal database for everything[END_REF].

	• fournir des recettes de cuisine, se souvenir des plats que l'on a préparés pour
	ses amis, sa famille,...
	• consulter et mettre à jour son agenda, ses rendez-vous, les factures à régler,
	les fêtes à souhaiter,
	• répondre au téléphone, à la messagerie,...
	• rechercher des infos sur le web,
	retrouver son chemin car le Majordome matérialisé par un SmartPhone, relié
	au GPS, connaît notre localisation et peut nous guider,
	• Enregistrer de courtes vidéo ou des photos pour faire un album de son
	proche passé,
	• se souvenir du nom et autres infos sur une personne que l'on rencontre; le
	Majordome est équipé d'une caméra, prend une photo et retrouve ces
	informations,
	• faire des achats; liste des courses, prix,...

  composant essentiel pour la transmission vidéo est le CODEC. Un codec (Code-DECode) est un procédé capable de coder un signal analogique et de décoder un signal numérique. Dans le cas de la VoIP, cela désigne aussi bien la norme que le module chargé d'encoder et de décoder la voix ou l'image. Le codec H264 encode et décode les flux respectant la nome MPEG-4 AVC/H264. Les PABX n'ont pas la charge de traduire les flux en provenance d'un codec d'un client A pour le transmettre vers un autre codec du client B. Il faut donc que l'ensemble des codecs clients ET PABX soient homogènes et inter-opérables. A ce jour les codecs utilisable avec Asterisk sont: • Pour le son : µlaw, alaw, gsm, ilbc, speex, g726, adpcm, lpc10, g729, g723

Tableau 1 .

 1 Résultats pour un locuteur en parlant 37 phrases spécifiques, 10 fois chacune.

	Phrase
	(

prononcée 10 fois par le même locuteur)

	hector ik ga lunchen met kennisen	100	100
	hector ik ga lunchen met buren	100	100
	wolly ik ga uit eten	100	100
	wolly ik ga uit eten met vrienden	100	100
	wolly ik ga uit eten met kennisen	100	100
	ja graag	40	80
	Pourcentage moyenne	86.39	94.44
	Pourcentage plus basse	40	60
	Pourcentage plus haute	100	100
	Phrases	Sémantique
	correctes	correcte
	(%)		(%)
	hellep	100	100
	help me	50	90
	kom naar de keuken	100	100
	kom eens naar de keuken	100	100
	wil je naar de keuken komen	60	60
	...

Acknowledgments

La thèse de Daniel R.S.Caon est en partie financée par le projet européen CompanionAble (FP7/2007-2013, convention de subvention n° 216487).


Keywords: Routing, Sensor Networks, Low Power, Lossy, LOAD

The LLN On-demand Ad hoc Distance-vector Routing Protocol -Next Generation (LOADng) Résumé : Ce document décrit le protocole de routage "distance vector" LOAD -Next Generation (LLN Ad hoc On-Demand). Il s'agit d'un protocole réactif qui s'adresse aux réseaux à faible puissance et fort taux de perte (Low power and Lossy Networks, LLNs). Il est dérivé d'AODV et a été modifié de manière répondre aux besoin de tels réseaux.

Introduction

The LLN On-demand Ad hoc Distance-vector Routing Protocol -Next Generation (LOADng) is a routing protocol, derived from AODV [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF] and extended for use in Low power Lossy Networks (LLNs). A reactive protocol, the basic operations of LOAD include generation of Route Requests (RREQs) by a router (originator) for when discovering a route to a destination, forwarding of such RREQs until they reach the destination router, generation of Route Replies (RREPs) upon receipt of a RREQ by the destination, and forwarding of these RREPs towards the originator. If a route is detected broken, i.e.,if forwarding of a data packet to the recorded next hop on the path to the destination is detected to fail, local route repair can be attempted, or a Route Error (RERR) message can be returned to the originator of that data packet.

Compared to [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], LOADng is simplified as follows:

• Only the destination is permitted to respond to a RREQ; intermediate routers are explicitly prohibited to respond to RREQs, even if they may have active routes to the destination. This eliminates the need for Destination Sequence Numbers, while retaining loop freedom. This also eliminates Gratuitous RREPs. The rationale for this simplification is, that it simplifies protocol operation and reduces message size. Also, except for in cases where the network graph has articulation points, this does not reduce the control traffic overhead incurred.

• A LOADng router does not maintain a precursor list, thus when forwarding of a data packet to the recorded next hop on the path to the destination fails, a RERR is sent only to the originator of that data packet. The rationale for this simplification is an assumption that few overlapping paths are in use concurrently.

Compared to [START_REF] Perkins | Ad hoc On-Demand Distance Vector (AODV) Routing[END_REF], LOADng is extended as follows:

• Optimized Flooding is supported, reducing the overhead incurred by RREQ generation and flooding.

• Different address lengths are supported -from full 16 octet IPv6 addresses over 6 octet Ethernet MAC addresses and 4 octet IPv4 addresses to shorter 1 and 2 octet addresses. The only requirement is, that in a given LLN each device has a unique address, and that all addresses within an LLN are of the same address length.

• Control messages can include a set of TLV (Type-Length-Value) elements, permitting flexible protocol extensions to be developed.

Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOM-MENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [START_REF] Bradner | Key words for use in rfcs to indicate requirement levels[END_REF].

Additionally, this memorandum uses the following terminology:

• A router which implements this routing protocol.

• The address of a router or host, to which a route is sought discovered and maintained.

• The address of a router, which seeks to discover and maintain a route to a Destination.

• A route set up so as to send data packets from the Originator to the Destination. The Forward Route is set up when a LOADng Router forwards Route Reply (RREP) messages.

• A route set up so as to send data packets from the Destination to the Originator. The Reverse Route is set up when a LOADng Router forwards Route Request (RREQ) messages. It is used for forwarding RREP messages, as well as for forwarding data packets.

• The cost (weight) between a pair of LOADng Routers, determined by a LOADng router upon reciept of a packet.

• The sum of the Link Costs for the links that a RREQ or RREP has crossed.

• A link which is marginally usable, i.e.,MAY be used if no other links are available, but SHOULD be avoided if at all possible -even if it entails an ultimately longer path. As an example, a Weak Link might be defined as a link with a significant loss-rate.

This memorandum employs the same notational conventions as in [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF].

INRIA

This protocol:

• Is a reactive routing protocol for Low power and Lossy Networks (LLNs).

• Supports the use of optimized flooding for RREQs.

• Enables any router in the LLN to discover bi-directional paths to any other router in the LLN.

• Supports addresses of any length, from 16 octets to a single octet.

• Is layer-agnostic, i.e.,may be used at layer 3 as a "route over" routing protocol, or at layer 2 as a "mesh under" routing protocol.

• Supports per-path maintenance; if a destination becomes unreachable, rediscovery of that single (bi-directional) path is performed, without need for global topology recalculation.

Protocol Overview and Functioning

The objective of this protocol is for each LOADng router to, independently:

• Be able to discover a bi-directional path to any destination in the network.

• Establish paths only when there is data traffic to be sent along that path.

• Maintain paths only for as long as there is traffic using the path, i.e.,maintain router state only for paths in active use.

• Generate control traffic based on network events only: when a new path is required, or when an active path is detected broken. Specifically, this protocol does not require periodic signaling.

Overview

These objectives are achieved, for each LOADng router, by:

• A LOADng router with a data packet to deliver to a destination, for which no entry in the routing table exists, generates a Route Request (RREQ) encoding the destination address, and transmits this to all of its neighbors.

• Upon receiving an RREQ, a LOADng router will install or refresh an entry in the routing table towards the originator of the RREQ, as well as to the neighbor LOADng router from which the RREQ was received. This will install the Reverse Route.

• Upon receiving a RREQ, a LOADng router will also inspect the indicated destination address:

-If that address is an address of that LOADng router, it will generate a Route Reply (RREP), which is unicast in a hop-by-hop fashion along the installed reverse route.

-If that address is not an address of the LOADng router, it will consider the RREQ as a candidate for forwarding.

• A RREQ considered for forwarding is retransmitted according to the forwarding operation specified for the network. This may be simply classic flooding, or may be an optimized flooding mechanism.

• Upon receiving a RREP, a LOADng router will install a forward route towards the originator of that RREP, as well as to the neighbor LOADng router, from which that RREP was received. This will install the Forward Route.

• Upon receiving a RREP, a LOADng router will also forward it, as unicast, to the recorded next hop along the recorded Reverse Route.

INRIA

Routers and Interfaces

In order for a LOADng router to participate in a LLN, it MUST have at least one, and possibly more, LOADng interfaces. Each LOADng interface:

• Is configured with one or more network addresses.

In addition to a set of LOADng interfaces as described above, each LOADng router:

• Has a number of router parameters.

• Has an Information Base.

• Generates and processes RREQ, RREP and RERR messages.

Information Base Overview

Necessary protocol state is recorded by way of two information sets: the "Routing Set", and the "Route Request Set". The Routing Set contains tuples, representing next-hop and distance towards a destination so as to enable routing. The Route Request Set tracks route discovery processes in progress, so as to enable a LOADng router to eliminate multiple forwards of RREQs.

Signaling Overview

This protocol generates and processes the following protocol packets:

• Generated by a LOADng router when it has a data packet to deliver to a given destination, but when it does not have an entry in its Routing Set, indicating a path to that destination. A RREQ is flooded through the network, possibly employing an optimized flooding mechanism, and contains the address of the sought destination as well as the address of the LOADng router, originating the RREQ. When forwarding a RREQ, a LOADng router's Routing Set is updated so as to reflect the path towards the originator of the RREQ, and the Route Request Set is updated so as to allow suppression of subsequent copies of the same RREQ.

• Generated as a response to a RREQ by the destination sought, i.e.,by the LOADng router using or responsible for the address contained in the RREQ. A RREP is unicast to the originator of the RREQ in a hop-byhop fashion. When forwarding a RREP, a LOADng router's Routing Set is updated so as to reflect the path towards the originator of the RREP.

Protocol Parameters and Constants

The parameters and constants used in this specification are:

LL-LLN-Routers NET TRAVERSAL TIME RREQ RETRIES RREQ RATELIMIT R hold time D hold time INRIA 6 Information Base
Each LOADng router maintains an Information Base, containing several information sets, as described in the following sections. These information sets are given so as to facilitate description of message generation, forwarding and processing rules. In particular, an implementation may chose any representation or structure for when maintaining this information.

Routing Set

A LOADng router's Routing Set records the next hop along a path to each destination, for which such a path is known. It consists of Routing Tuples:

(R_dest_addr, R_next_addr, R_dist, R_time)

where:

• R dest addr is the address of the destination, either the address of an interface of a destination LOADng router, or the address of an interface reachable via the destination LOADng router, but which is outside the LLN;

• R next addr is the address of the "next hop" on the selected path to the destination;

• R dist is the cost of the selected path to the destination with address R dest addr;

• R time specifies when this Tuple expires and MUST be removed.

Route Request Set

A LOADng router's Route Request Set records information about issued route discovery processes. It consists of Route Request Tuples:

(D_src_addr, D_rreq_id, D_time)

where:

• D src addr is the address of the LOADng router, generating a RREQ and thus initiating the route discovery process;

• D rreq id is a sequence number, uniquely identifying each RREQ issued by a given LOADng router. The pair (D src addr, D rreq id) uniquely identifies a RREQ in the network;

• D time specifies when this Tuple expires and MUST be removed.

RR n°7692

7 Packet Format

The packet format, used by this protocol, is described using the notational conventions from [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF]. Example packets are illustrated in A.

The general format for all packets, generated, forwarded and processed by this specification, is as follows:

<packet> := <type> <tlv-block> <message>
where:

• <type> is a 4 bit unsigned integer field and specifies the type of the <message> field specified in 7.2.

• <tlv-block> is specified in 7.1.

• <message> is specified in 7.2.

TLV Block

The TLV Block contains zero or more Type-Length-Value elements (TLVs).

A TLV allows the association of an arbitrary attribute with a packet. The attribute (value) is made up from an integer number of consecutive octets. Different attributes have different types; attributes which are unknown when parsing can be skipped, as specified by flags associated with a given TLV.

<tlv-block> := <tlv-count> (<tlv-type><tlv-flags><tlv-length><tlv-value>)*

where:

• <tlv-count>is a 4 bit unsigned integer field, specifying the number of TLVs included.

• <tlv-type>is a 4 bit unsigned integer field, specifying the type of the TLV.

• <tlv-flags>is a 4 bit field specifying the interpretation of the remainder of the TLV:

bits 0-3: RESERVED

• <tlv-length> is an 8 bit unsigned integer field, specifying the length of the following <tlv-value> field.

• <tlv-value> is a field of length <length> octets.

Message Format

This section specifies the format of the <message> field for message types RREQ, RREP, and RERR.

INRIA

The LLN On-demand Ad hoc Distance-vector Routing Protocol -Next Gen. 11

RREQ and RREP Message Format

The format of Route Request (RREQ) and Route Reply (RREP) messages is identical, as follows:

<message> := <flags> <addr-length> <cost-type> <weak-links> <rreq-ID> <route-cost> <destination> <originator> where:

• <flags>is a 4 bit unsigned integer field and specifies the interpretation of the remainder of the message:

-RESERVED

• <addr-length> is a 4 bit unsigned integer field, encoding the length of the destination and originator addresses (<destination> and <originator>) as follows:

-<addr-length> = the length of an address in octets -1 <addr-length> is thus 1 for 16-bit short addresses [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], 3 for IPv4 addresses, 7 for 64-bit extended addresses [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF] or 15 for IPv6 addresses.

• address-length is a variable whose value is the length of an address in octets, and is calculated as follows:

address-length = <addr-length> + 1

• <cost-type> is a 4 bit unsigned integer field and specifies how the value of the <route-cost> field is calculated as well as the comparison operator '<=' for determining which of two route costs is lower.

• <weak-links> is a 4 bit unsigned integer field and specifies the total number of weak links on the routing path from the originator to the destination.

• <rreq-ID> is an 8 bit unsigned integer field and specifies a sequence number uniquely identifying the particular RREQ when taken in conjunction with the originator.

• <route-cost> is an 8 bit unsigned integer field and specifies the cost of the routing path from the originator to the destination.

• <destination> is an identifier with length equal to address-length, specifying the address of the destination, to which a route is sought.

• <originator> is an identifier with length equal to address-length, specifying the address of the originator, which has initiated route discovery for the destination.

RERR Message Format

The format of a Route Error (RERR) message is as follows:

<message> := <error-code> <addr-length> <source> <destination>

where:

• <error-code> is a 4 bit unsigned integer field and specifies the reason for the error message being generated, according to 4.

• <addr-length> is a 4 bit unsigned integer field, encoding the length of the destination and originator addresses (<destination> and <originator>) as follows:

-<addr-length> = the length of an address in octets -1 <addr-length> is thus 1 for 16-bit short addresses [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF], 3 for IPv4 addresses, 7 for 64-bit extended addresses [START_REF] Montenegro | Transmission of IPv6 Packets over IEEE 802.15.4 Networks[END_REF] or 15 for IPv6 addresses.

• is a variable whose value is the length of an address in octets, and is calculated as follows:

address-length = <addr-length> + 1

• <source> is an identifier with length equal to address-length, specifying the source address of a data packet, for which delivery to <destination> failed. The LOADng router with this address is the ultimate target for the RERR message.

• <destination> is an identifier with length equal to address-length, specifying the address of the destination, which has become unreachable and for which an error is reported.

INRIA

Route Requests (RREQs) are generated by a LOADng router, when it has data packets to deliver to a destination for which there is no matching entry in the Routing Set. The RREQ is transmitted to all directly reachable neighbor LOADng routers, if available by way of link-local multicast. Each RREQ, generated by a LOADng router, includes a Route Request ID (RREQID). The RREQID MUST be unique for each RREQ generated by a router, and RREQIDs for a LOADng router MUST be generated so as to be monotonically increasing.

After originating a RREQ, a LOADng router waits for a corresponding RREP. If no such RREP is received within NET TRAVERSAL TIME milliseconds, the LOADng router MAY issue a new RREQ for the sought destination (with an incremented RREQID) up to a maximum of RREQ RETRIES times. A LOADng router SHOULD NOT originate more than RREQ RATELIMIT RREQs per second.

RREQ Generation

A RREQ message is generated with:

• <addr-length> set to the length of the address, as specified in 7.

• <cost-type> set to indicate how path costs are to be calculated and compared, according to 3.

• <weak-links> set to 0.

• <rreq-ID> set to the next unused RREQID.

• <route-cost> set to the cost associated with the interface over which the RREQ is transmitted, and according to the specification of the <cost-type> included in the RREQ, see 11.

• <destination> set to the address to which a path is sought.

• <originator> set to the address of the LOADng router, generating the RREQ.

RREQ Processing

On receiving a RREQ message, a LOADng router MUST first check if the message is invalid for processing by this LOADng router, as defined in 8.2.1 and, if so, discard the message without further processing. Otherwise, for each received and valid RREQ, the LOADng router MUST process it according to this section.

For the purpose of the processing description below, the following additional notation is used:

• is the comparison operator, specified for the <cost-type> indicated in the RREQ and described in 11.

• is the address of the LOADng router, from which the RREQ was received.

RR n°7692

The RREQ message is processed as follows:

1. If the RREQ was received over a "weak link", increment the <weak-links> field in the received RREQ by one.

2. Find the Route Request Tuple (henceforth "matching Route Request Tuple") in the Route Request Set where: (a) If R dist <= <route-cost> (using the comparison operator, defined for the <cost-type> specified in the RREQ) then the reverse route currently recorded in the Routing Set is better than the route possible via the RREQ. The RREQ is not processed further, and is not considered for forwarding.

•
(b) Otherwise, the reverse route possible via the RREQ is better than the reverse route current recorded in the Routing Set:

i. If for the matching Route Request Tuple:

• D rreq id is greater than <rreq-id> then this RREQ represents a path, older than the one recorded. The RREQ is not processed further, and is not considered for forwarding. ii. Otherwise:

Invalid RREQ Messages

A received RREQ is invalid, and MUST be discarded without further processing, if any of the following conditions are true:

• The address contained in the <originator> field is an address of this router;

• The RREQID, contained in the <rreq-id> field is less than a RREQID previously recorded for the address contained in the <originator> field.

A LOADng router MAY recognize additional reasons for identifying that a RREQ is invalid for processing, e.g., to allow a security protocol to perform verification of RREQ signatures and prevent processing of unverifiable RREQs by this protocol.

RREQ Forwarding

A Route Request (RREQ), considered for forwarding, MUST be updated as follows, prior to it being transmitted:

• The <route-cost> field must be updated according to the cost associated with the interface over which the RREQ is transmitted, and according to the specification of the <cost-type> included in the RREQ, see 11.

RREQ forwarding MAY be undertaken using classic flooding, may employ a reduced relay set mechanism such as [START_REF] Macker | Simplified Multicast Forwarding[END_REF] or any other information diffusion mechanism such as [START_REF] Levis | The Trickle Algorithm[END_REF]. Care must be taken that NET TRAVERSAL TIME is chosen so as to accommodate for the worst-case time that it takes a RREQ to transverse the net, accounting for in-router delays incurring due to or imposed by such algorithms.

RREQ Transmission

RREQs (initially generated or forwarded) are sent to all neighbor LOADng routers. If LOADng is operating as an IP routing protocol, the destination address for this RREQ MUST be the link local multicast address LL-LLN-Routers, and the source address MUST be the address of the interface over which the RREQ is sent.

When a RREQ is transmitted, all receiving LOADng routers will process the RREQ message and MAY consider the RREQ message for forwarding at the same, or at almost the same, time. If using data link and physical layers that are subject to packet loss due to collisions, such RREQ messages SHOULD be jittered as described in [START_REF] Clausen | Jitter Considerations in Mobile Ad Hoc Networks (MANETs)[END_REF].

INRIA

Route Replies (RREPs) are generated by a LOADng router in response to a RREQ where the <destination> corresponds to one of that LOADng router's addresses. RREPs are sent, hop by hop, in unicast towards the originator of the corresponding RREQ, along the Reverse Route installed by that RREQ. A router, upon forwarding a RREP, installs the Forward Route towards the <destination>.

Thus, with forwarding of RREQs installing the Reverse Route and forwarding of RREPs installing the Forward Route, bi-directional paths are provided between the <originator> and <destination> indicated in the RREQ.

RREP Generation

A RREP message is generated by making a copy of the RREQ message, in response to which the RREP is generated, then modifying that copy as follows:

• <type> := RREP • <weak-links> := 0
• <route-cost> := the cost associated with the interface over which the RREP is transmitted, and according to the specification of the <cost-type> included in the RREP, see 11.

For TLVs, included in the <tlv-block> in the RREQ, the specification of these TLVs MUST stipulate if, and under which conditions, these are to be included in the corresponding RREP.

RREP Processing

For the purpose of the processing description below, the following additional notation is used:

• is the comparison operator, specified for the <cost-type> indicated in the RREP and described in 11.

• is the address of the LOADng router, from which the RREP was received.

On receiving a RREP, a LOADng router MUST:

• Find the Route Request Tuple (henceforth "matching Route Request Tuple") in the Route Request Set where:

-D src addr = originator; AND -D rreq id = rreq-id

• If there is no matching Route Request Tuple, then the RREP MUST be discarded, i.e.,it MUST NOT be processed further and it MUST NOT be considered for forwarding.

• Otherwise, if there is a matching Route Request Tuple:

RR n°7692
-Find the Routing Tuple (henceforth "matching Routing Tuple") in the Routing Set where: * R dest addr = <destination> -If there is no matching Routing Tuple, then: * Create a new matching Routing Tuple (the "forward route") with:

• R dest addr = <destination> • R next addr = previous-hop • R dist = infinity • R time = current time + R hold time
-The matching Routing Tuple, existing or new, is compared to the received RREP: * If R dist <= <route-cost> (using the comparison operator, defined for the <cost-type> specified in the RREP) then the forward route currently recorded in the Routing Set is better than the forward route possible via the RREP. The RREP is not processed further, and is not considered for forwarding. * Otherwise, the forward route possible via the RREP is better than the forward route currently recorded in the Routing Set:

• If for the matching Route Request Tuple: D rreq id is greater than <rreq-id> then this RREP represents a path, older than the one recorded. The RREP is not processed further, and is not considered for forwarding. • Otherwise, update the matching Routing Tuple thus: R next addr = previous-hop R dist = <route-cost> R time = current time + R hold time TLVs, included in the TLV block, are processed according to their specification. The RREP is considered for forwarding, see 9.3.

RREP Forwarding

A Route Reply (RREP), considered for forwarding, MUST be updated as follows, prior to it being transmitted:

• The <route-cost> field must be updated according to the cost associated with the interface over which the RREP is transmitted, and according to the specification of the <cost-type> included in the RREP, see 11.

RREP Transmission

A Route Reply (RREP) is, ultimately, destined for the LOADng router listed in the <originator> field, and is forwarded in unicast towards this LOADng router. The RREP MUST, however, be transmitted so as to allow it to be processed in each intermediate LOADng router to:

INRIA

The LLN On-demand Ad hoc Distance-vector Routing Protocol -Next Gen. 19

• install proper forward routes

• permit that <route-cost> and <weak-links> be updated to reflect the path, and

• permit that TLVs included may be processed/added/removed according to their specification.

Route Maintenance

Entries in the Routing Set are maintained by way of four different mechanisms:

• RREQ/RREP exchange, as described in 8 and 9;

• Data traffic delivery success;

• Data traffic delivery failure;

• External signals indicating that an entry in the Routing Set necessitates updating.

The latter three are detailed in this section.

Routing Tuples in the Routing Set contain an expiration time, after which such tuples are to be removed (or, considered as removed) so as to both be conservative in routing state required, and so as to ensure that stale tuples (i.e.,tuples which do no longer reflect a topology, recently verified to be current) disappear.

Routing Tuples for actively used routes (i.e.,a route via which traffic is currently transiting) SHOULD NOT be removed, unless there is evidence that they no longer provide connectivity -i.e.,unless a link on that route has broken.

To this end, one or more of the following mechanisms (non-exhaustive list) MAY be used:

• For very short, predictable, flows, the initial R hold time MAY be set to large enough so as to not require refresh of the route for the duration of the flow. An extension MAY, for example, convey this duration in a TLV, as well as specify appropriate processing of this TLV when processing a RREQ/RREP.

• If a lower layer mechanism provides signals, such as when delivery to a presumed neighbor LOADng router fails, this signal MAY be used to indicate that a link has broken, trigger early expiration of a Routing Tuple from the Routing Set, and to initiate Route Repair (see 10.1) or Route Error Signaling (see 10.2). Conversely, absence of such a signal when attempting delivery MAY be interpreted as validation that the corresponding Routing Tuple(s) are valid, and their R hold time refreshed correspondingly.

• Conversely, for each successful delivery of a packet to a presumed neighbor or a destination, if signaled by a lower layer or a transport mechanism, or each positive confirmation of the presence of a neighbor by way of an external neighbor discovery protocol, MAY be interpreted as validation that the corresponding Routing Tuple(s) are valid, and their R hold time refreshed correspondingly.

Regardless, a LOADng router may experience that a path, currently used for forwarding data packets, is no longer operational, and must act to either rectify this situation locally ( 10.1) or signal this situation to the source of the data packets for which delivery was unsuccessful ( 10.2).

INRIA

Route Repair

If a link breakage is detected, an intermediate LOADng router MAY attempt to repair the route locally, by issuing a RREQ and awaiting an RREP. This RREQ is generated with the intermediate LOADng router's address as <originator> and is generated, processed and forwarded exactly as specified in 8 and 9, and with the same constraints on RREQ generation.

Route Errors (RERR)

If Route Repair is not successful, or if Route Repair is not attempted, a LOADng router MUST generate a Route Error (RERR), and send this RERR along the reverse path to the source of the data packet for which delivery was unsuccessful.

RERR Generation

A RERR message is generated by the LOADng router, detecting the link breakage, with the following content:

• <error-code> = the most appropriate error code from among those recorded in 4;

• <addr-length> = the length of the address, as specified in 7;

• <source> = the source address from the unsuccessfully delivered data packet.

• <destination> = the destination address from the unsuccessfully delivered data packet.

RERR Processing

For the purpose of the processing description below, the following additional notation is used:

• is the address of the LOADng router, from which the RERR was received.

Upon receiving an RERR, a LOADng router MUST update its Routing Set as follows:

• Find the Routing Tuple (henceforth "matching Routing Tuple") in the Routing Set where:

-R dest addr = <destination> -R next addr = previous-hop

• If no matching Routing Tuple is found, the RERR is not processed further, and is not considered for forwarding.

• Otherwise, if one matching Routing Tuple is found, this matching Routing Tuple is updated as follows:

-R time = expired

The RERR message is, then, transmitted to the recorded R next addr towards <destination>.

RERR Transmission

A Route Error (RERR) is, ultimately, destined for the LOADng router listed in the <source> field, and is forwarded in unicast towards this LOADng router. The RERR MUST, however, be transmitted so as to allow it to be processed in each intermediate LOADng router to:

• Allow intermediate routers to update their Routing Sets, i.e.,remove entries for this destination.

• Permit that TLVs included may be processed/added/removed according to their specification.

Cost Types

This specification permits the use of different cost-types for when calculating route costs, and specifies one particularly simplified such cost-type in 11.3 purely intended as an example -while encouraging that more appropriate cost-types be developed for different deployment environments.

The Default <= Comparison Operator

The objective of the <= comparison operator is to be able to determine which of two routes is "best", i.e.,which route has the lowest cost. A link between a pair of interfaces may have a nominal and administratively assigned cost associated (such as, for example, representing a nominal bandwidth), however may also have a dynamic component making an link with an otherwise low cost a less attractive choice -a "Weak Link" -for when establishing a new route (such as, for example, if a high loss-rate is experienced across that link). This may make a longer (in term of cost) route preferable over a shorter route involving such "Weak Links".

To accommodate this situation, this specification includes in RREQs and RREPs, both a <route-cost> element, representing the cost of the route traveled, and a <weak-links> element, counting the number of weak links encountered. When a destination receives multiple copies of the same RREQ, via different paths, the default <= comparison operator is defined so as to prefer paths with fewer weak links, even if such a path has an absolute higher route cost.

Let (WL, RC) be the pair (weak-links, route-cost) received in one RREQ, and let (WL', RC') be the pair (weak-links, route-cost) received in another RREQ. The comparison operator <= is then defined as:

Specifying New Cost Types

When defining a cost-type, the following considerations SHOULD be taken into consideration, and MUST be taken into consideration when requesting a codepoint from IANA for the 1-64 range of the Cost Types registry defined in 3:

• The mechanism for determining when a link qualifies as a "Weak Link".

Examples include when an SNR or SIR is above/below a given threshold, etc. This MAY be by way of lower-layer information, message statistics or any other means.

• The mechanism for determining how to update the <route-cost> field when a RREP or RREQ is transmitted over an interface.

• The <= comparison operator. This MAY be by way of indicating that the definition in 11.1 is used, or an operator MAY be specified using also, e.g., information contained in TLVs; in either case, the comparison operator to use MUST be specified.

Example Cost Type: Hop Count

This section is intended to exemplify of how to specify Cost Types. It represents a simple "hop count" based cost. It is RECOMMENDED to define a more appropriate cost-type for the environment in which the protocol is to operate.

Simple Hop Count

• No link is ever considered as a Weak Link. Consequently, when generating a RREQ or RREP, the <weak-link> element is set to zero, the <weak-link> is never incremented when forwarding.

• When generating a RREQ or a RREP, the <route-cost> is initialized to one, the <route-cost> is incremented by one when forwarding.

  D src addr = originator; AND • D rreq id = rreq-id 3. If there is no matching Route Request Tuple, then: (a) Create new matching Route Request Tuple with: • D src addr := originator • D rreq id := rreq-id • D time = current time + D hold time 4. Find the Routing Tuple (henceforth "matching Routing Tuple") in the Routing Set where: • R dest addr = <originator> 5. If there is no matching Routing Tuple, then: (a) Create a new matching Routing Tuple (the "reverse route") with: • R dest addr = <originator> • R next addr = previous-hop • R dist = infinity • R time = current time + R hold time 6. The matching Routing Tuple, existing or new, is compared to the received RREQ:

INRIAA.

  Update the matching Routing Tuple thus: R next addr = previous-hop R dist = <route-cost> R time = current time + R hold time B. TLVs, included in the TLV block, are processed according to their specification. C. If <destination> corresponds to an address of this LOADng router, then an RREP is generated, see 9.1. D. Otherwise, if <destination> does not correspond to an address of this LOADng router, then the RREQ is considered for forwarding, see 8.3.

  this memorandum does not specify any specific security measures. By way of enabling inclusion of TLVs, development of security measures, appropriate for a given deployment, is however supported.

• (WL,RC) <= (WL',RC') if and only if: RC < RC' OR if RC == RC' INRIA Currently,

RR n°7692

Acknowledgments

The authors would like to acknowledge the team behind AODV, specified in RFC3561 for their contributions. The authors would also like to acknowledge the efforts of K. Kim (picosNet Corp/Ajou University), S. Daniel Park (Samsung Electronics), G. Montenegro (Microsoft Corporation), S. Yoo (Ajou University) and N. Kushalnagar (Intel Corp.) for their work on an initial version of a specification, from which this protocol is derived.

Packet Types

IANA is requested to create a new registry for packet types, with initial assignments and allocation policies as specified in 1.

TLV Types

IANA is requested to create a new registry for TLV types, with initial assignments and allocation policies as specified in 2.

Cost Types

IANA is requested to create a new registry for Cost Types, with initial assignments and allocation policies as specified in 3.

When assigning a new Cost Type, the specification requesting that assignment MUST specify the way in which each LOADng router calculates the <route-cost> field in RREQs and RREPs, as well as the criteria for incrementing the <weak-links> field in RREQs and RREPs. The specification MUST also specify the comparison operations '<=' for determining from among two

Error Codes

IANA is requested to create a new registry for Error Codes, with initial assignments and allocation policies as specified in 4.

Contributors

This specification is the result of the joint efforts of the following contributors -listed alphabetically.

• Thomas Heide Clausen, LIX, France, <T.Clausen@computer.org>

• Axel Colin de Verdiere, LIX, France, <axel@axelcdv.com>

• Ulrich Herberg, Fujitsu Laboratories of America, USA <ulrich.herberg@us.fujitsu.com>


Thomas Clausen
email: thomas@thomasclausen.org

Ulrich Herberg
email: ulrich@herberg.name

INFORMATIQUE ET EN AUTOMATIQUE Delay Tolerant Routing with OLSRv2

Keywords: OLSRv2, MANET, popup, mobility pattern, link buffer

This memorandum proposes a simple mechanism for enabling basic delay tolerant networking with off-the-shelf MANET routing protocols -with the objective being to enable trading off slightly longer data delivery delays against resilience to a temporary lack of connectivity between a router and the ultimate destination of an IP datagram. As part of testing the benefit of said mechanism, an extreme network mobility model is proposed, entitled the "PopUp model": a router appears in the network, and operates normallythen may disable and disappear from the network to appear later elsewhere. Observed to cause severely degraded performance for MANET routing protocols, this model is used for testing the proposed mechanism in OLSRv2-routed MANETs. The proposed mechanism shows to vastly increase the data delivery ration, with reasonably low increases in delays and control traffic overhead incurred.

Routage Tolérant aux Delais avec OLSRv2

Résumé : Ce memorandum présente un mécanisme simple de routage tolérant aux délais pour des protocoles de routage MANET -avec l'objectif d'être capable de balancer des délais de remise de données légèrement plus élevés et la résistance contre un manque de connectivité entre un routeur et la déstination ultime d'un datagramme IP. Afin de tester le bénéfice d'un tel mécanisme, un modèle extrême de mobilité de réseaux est proposé, nommé "modèle popup" : un routeur apparait dans le réseau et fonctionne normalement -puis peut être désactivé et disparaitre du réseau afin de réapparaitre ultérieurement à un autre endroit. Ayant observé une forte dégradation de la performance des protocoles de routage de MANET, ce modèle est utilisé pour tester le mécanisme proposé dans des MANETs tournant le protocole de routage OLSRv2. Le mécanisme proposé augmente largement le taux de remise des données avec des augmentations de délai et de trafic de contrôle relativement basses.

Mots-clés : OLSRv2, MANET, popup, mobilité, tampon de lien

Introduction

IP datagram transmission is based on a delivery principle, commonly known as "best effort": if the routing table contains a "valid route" towards the destination of the datagram, then the datagram is transmitted -otherwise, it is silently dropped. In ad hoc networks, such a "best effort" behavior may be undesired: a route may not be available, but will be shortly, e.g., as the routing protocol converges so as to reflect a changed topology in routing tables. A wireless link may at one point have been considered sufficiently reliable, and thus advertised and used as such, yet over time degrade until being declared as lost and possibly advertised as lost also. Destinations reachable via paths containing this now lost link are unreachable, at least until the routing protocol message exchange and table calculations complete, providing different paths through the network.

In networks in which the topology is dynamic and such transient situations are frequent, it may be preferable to slightly alter the "best effort delivery principle" so as to, colloquially speaking, hold on to an un-transmittable IP datagram for a while, hoping that a route will become available shortly -using graph terminology, may choose to buffer an un-transmittable IP datagram until its routing table indicates that it is in the same connected component as the intended destination. Doing so may increase the data delivery ratio, at the expense of longer delivery delays ("delay tolerant networking") as well as additional state requirements in routers for the buffering process.

This memorandum proposes:

1. A modification to the IP datagrams transmission process, allowing for buffering un-transmittable IP datagrams;

2. A network mobility model, entitled "PopUp Networks", wherein devices appear in the network, disappear, move, then re-appear;

3. A comprehensive set of simulations, studying the behavior of an OLSRv2routed ad hoc network, when exposed to the previous two items.

The proposed PopUp network mobility model is presenting an "extreme" type of network behavior, and is so chosen as it generally results in vastly degraded routing protocol performance, unless special measures are taken. The purpose of this memorandum is to present how, even when faced with such a harsh network mobility model, a relatively simple mechanism can vastly improve the performance an off-the-shelf ad-hoc routing protocol.

Memorandum Outline

The remainder of this memorandum is organized as follows: section 2 provides a basic overview of OLSRv2, and section 3 specifies the proposed modification to the IP datagram transmission mechanism, denoted "Link Buffering", for allowing delay tolerant message delivery. The "PopUp" network mobility model is proposed in section 4. Section 5 presents a performance evaluation of the delay-tolerance mechanism in OLSRv2-routed networks simulated when exposed to the PopUp network mobility model. Section 6 concludes the memorandum.

OLSRvOverview

The Optimized Link State Routing Protocol version 2 (OLSRv2) [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF][START_REF] Clausen | Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)[END_REF][START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF][START_REF] Clausen | The Optimized Link-state Routing Protocol version 2[END_REF] is a successor to the widely deployed OLSR [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR)[END_REF] routing protocol for MANETs. OLSRv2 retains the same basic algorithms as its predecessor, however offers various improvements, e.g., a modular and flexible architecture, and in particular a flexible message format [START_REF] Clausen | Generalized MANET Packet/Message Format[END_REF] by way of TLVs, allowing extensions, such as for security, to be developed as add-ons to the basic protocol whilst retaining backwards and forwards compatibility. OLSRv2 contains three basic processes: Neighborhood Discovery, MPR Flooding and Link State Advertisements. The basic operation of OLSRv2 is detailed in section 2.0.1 to 2.0.3 below.

Neighborhood Discovery (NHDP)

The process, whereby each router discovers the routers which are in direct communication range of itself (1-hop neighbors), and detects with which of these it can establish bi-directional communication, as well as detects its 2-hop neighbors. This, by way of a periodic HELLO message exchange, as specified in [START_REF] Clausen | Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)[END_REF]. NHDP enables routers to apply a hysteresis mechanism for determining when to admit the link to a given neighbor, as well as the ability to signal a link no longer satisfactory as "LOST", triggering recalculation of MPRs and possibly renewed Link State Advertisement.

MPR Flooding

The process whereby each router is able to, efficiently, conduct network-wide broadcasts. Each router designates, from among its bi-directional neighbors, a subset (MPR set) such that a message transmitted by the router and relayed by the MPR set is received by all its 2-hop neighbors. MPR selection is encoded in outgoing HELLOs.

Link State Advertisement

The process whereby routers are determining which link state information to advertise through the network. Each router must advertise links between itself and its MPR-selector-set, in order to allow all routers to calculate shortest paths. Such link state advertisements, carried in TC messages, are broadcast through the network using the MPR Flooding process. As a router selects MPRs only from among bi-directional neighbors, links advertised in TCs are also bi-directional. TC messages are sent periodically, however certain events may trigger non-periodic TCs.

Link Buffering

This section proposes a link buffer mechanism, based on [START_REF] Clausen | Link Buffering for MANETs[END_REF], which allows delaying datagram transmission when the ultimate destination is (temporarily) unavailable in a router's routing table -and then transmit that datagram later, once the destination re-appears.

INRIA

IP Buffering

Traditional IP datagram transmission considers, essentially, two "states" for any destination: either a route exists (transmit) or no route exists (drop). The proposed mechanism changes the default behavior of "drop" to "buffer datagrams for expected later delivery". Table 1 lists the different states, combined with the appropriate action to be taken. Whenever a routing protocol adds or modifies a route to a destination, all buffered IP datagrams to that destination are retransmitted.

L2 Buffering

A variant of the mechanism described in section 3.1 is to consider a third state in addition to "no route" and "route valid", called "route invalid". This state corresponds to the situation where a destination is believed to be present in the network, although the previously selected "next hop" is currently unavailable. This variant requires the link layer (L2) to be aware of, and able to signal to the network layer and the routing table if transmissions to the next hop fail, i.e. the link to the next hop is disconnected. For example, 802.11 [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF] applies such a mechanism using acknowledgments: if a frame is not acknowledged by the destination (of the frame, i.e., the ultimate destination or the intended nexthop), the frame is dropped (after a bounded number of failed attempts with an exponential back-off mechanism). If such a L2 mechanism is in place, IP datagrams can also be buffered in the "route invalid" state.

Flow Chart

Figure 1 depicts the proposed mechanism, for both IP and L2 link buffering. When a datagram is to be forwarded by a router (state "Datagram to be forwarded"), the router verifies whether it has a route towards the destination. If yes, it hands the datagram off for transmission (states "Send datagram" and "Datagram arrives at L2"). If the datagram cannot be sent successfully (e.g. no ACK has been received), the datagram is buffered.

If no valid route exists (state "valid route available?"), the behavior depends on whether the router is the source of the datagram or not. If yes, the datagram is buffered, otherwise it is dropped. The rationale for this differentiation is provided in section 3.4.

Buffering at Intermediate Hops

IP datagrams may traverse several hops (i.e. several routers) from the source to the destination. Invalid routes can appear at any of these routers -in part, as routing protocols do not converge instantaneously on all routers. Typically, the further a router is away from a destination (in terms of hops), the longer is the convergence time for that destination1 . Thus, it is possible that a router forwarding an IP datagram still has a valid route to the destination and forwards it, while another router further along the path towards the destination has a fresher information about that destination and is aware that the destination is no longer available. Consequently, buffering could be performed at any of these "intermediate" routers, however such may lead to a large demand of memory on some routers that are bottlenecks in the network. Consider the example in figure 2, where the gray router (called 'I') buffers datagrams if it does not have a valid routing table entry for their ultimate destinations -requiring vast amount of memory in 'I', or provides a target for denial-of-service attacks.

While these reasons may make it undesirable to allow buffering in intermediate routers, the performance of this mechanism is also evaluated in section 5.

Model Description

In order to test the link buffering mechanism presented in section 3 in extreme conditions (i.e. where the end-to-end delivery ratio of IP datagrams is otherwise low without such a mechanism), the "PopUp" network mobility model is proposed.

The PopUp mobility model is defined as follows: every router in a MANET has two conjunct states (as depicted in figure 3): enabled and disabled.

Whenever a router is "enabled", it operates as usual, i.e., it may exchange control messages of a routing protocol, send and receive data traffic etc. In this state, the router does not move. The router remains for a certain time (denoted enabled_time) in this state. It then switches to the "disabled" state which may involve a change in position: the router can move up to a certain upper bounded distance (denoted max_distance) with infinite speed.

If a router is "disabled", it cannot send or receive any messages from the network (neither data nor control traffic). The router can be considered as being "switched off" and is thus completely unresponsive to any network events. The router stays a maximum time of disabled_time in that state until it returns to the "enabled" state. Note that both enabled_time and disabled_time can be infinite, i.e., that a router can remain in either of these states forever.

Performance Evaluation

This section presents a performance evaluation of unicast data traffic in OLSRv2routed MANETs, both with and without the link buffering mechanism described in section 3. The performance evaluation is undertaken by way of NS2 simulations. Typical metrics such as delivery ratio of data traffic, control traffic overhead, average path length and delay of data traffic are considered.

God Routing Protocol

In order to provide an upper bound in terms of delivery ratio for the simulated scenarios, a "God routing protocol" (denoted "GodRP") has been implemented. The routing protocol uses the "God" object of NS2, and calculates routes to all destination based on their position and radio range, instantaneously and without any signaling. The expected performance of the GodRP is close to the best possible routing protocol, which helps to understand how well a routing protocol could theoretically perform2 .

A variation of the GodRP is included in the simulation as well, which performs link buffering as described in section 3, denoted "GodRP-LB". Note that the variant with link buffering (LB), does not represent an upper bound in terms of data delivery ratio, illustrated in figure 5. Four routers run a link state routing protocol and are arranged in a "strip" topology at time t 0 . Router 1 sends unicast data traffic to router 4. At time t 1 , the link between router 3 and 4 breaks. Due to the non-zero convergence time of link state routing protocols, router 1 may still have a valid route to 4, so it transmits the datagrams. When router 3 receives the datagrams (after being forwarded by router 2), it may have a fresher information about the disconnected link to 4. If no intermediate buffering is used, it will drop the datagram. However, when using intermediate buffering, the datagram is buffered, and delivered later (at time t 2 ). Using GodRP-LB, the datagram will never be delivered in this example from t 1 : at t 1 , Figure 5: GodRP with link buffering ("GodRP-LB") does not represent an upper bound in terms of data delivery ratio for routing protocols with link buffering router 1 will be immediately informed about the link disconnection between 3 and 4, so router 1 will buffer all datagrams. Since at t 2 , router 1 is not longer connected to 2, datagrams will not reach their final destination, router 4.

Graceful Shutdown

In the performance evaluation, a variation of OLSRv2 with link buffering as considered: if a router is gracefully shutdown when transiting from "enabled" to the "disabled" state, it sends a HELLO to inform neighbors that links to the router shutting down should be considered as unavailable. Figure 6 depicts the graceful shutdown process. At time t 0 , all three routers are in the "enabled" state. In the periodic HELLO messages from router 2, it will list both router 1 and 3 as symmetric (SYM) neighbors. Thus, router 1 will list 2 as symmetric neighbor, and 3 as two-hop neighbor reachable via 2. When router 2 is about to be shut down at time t 1 , it sends a HELLO message with all neighbors listed as LOST. Thus, router 1 will remove the 2-hop neighbor entry, and set the link status towards router 2 to HEARD. In addition, router 1 may trigger a HELLO message (and possibly a TC message, if it was selected as MPR by router 2), advertising the lost link.

Without the graceful shutdown mechanism, router 1 would have listed 2 as symmetric neighbor until the link expired. Thus, the graceful shutdown mechanism effectively reduces the convergence time of the routing protocol.

Simulation Settings

NS2 simulations settings are summarized in table 2. Routers behave according to the PopUp mobility model as defined in section 4, in a square area of 1000x1000 meters. On average, the data traffic load is five concurrent CBR streams of 3.2 kB/s between random pairs of routers. The simulation time is 300 seconds, and each data point presented is an average over 30 runs of different scenarios, corresponding to the same abstract scenario description. A random seed was used for every simulation.

The following routing protocol variants are compared: OLSRv2, OLSRv2 with link buffering on L3 only ("OLSRv2-L3-LB"), OLSRv2 with link buffering ("OLSRv2-LB"), OLSRv2 with link buffering and graceful shutdown ("OLSRv2-LB-gf"), OLSRv2 with link buffering also at intermediate routers ("OLSRv2-IM-LB"), the God routing protocol ("GodRP"), God routing protocol with link buffering ("GodRP-LB"). [START_REF] Clausen | The Optimized Link-state Routing Protocol version 2[END_REF] At the beginning of the simulation, all routers are in either "disabled" or "enabled" state randomly with a random enabled_time or disabled_time left before the next state transition.

INRIA

Simulation Results

Figure 7 depicts the unicast data delivery ratio. The God routing protocol -not surprisingly -has a higher delivery rate than OLSRv2, which is due to the zeroconvergence time and less collisions due to the lack of control traffic. However, even with the GodRP, no more than a 35% of delivery ratio with 70 routers is reached. This is because the network, by design, is not fully connected in the PopUp model. The link buffering variants result in significantly higher delivery ratios, with GodRP with link buffering producing the highest data delivery ratio. OLSRv2 with intermediate link buffering produces a data delivery ratio close to that of GodRP-LB. Due to the non-zero convergence time of OLSRv2, buffered datagrams will be delivered only a bit later than with the link buffering variant of the GodRP (which can be observed in figure 8). OLSRv2 without intermediate link buffering has a significantly lower delivery ratio, whereas the graceful shutdown mechanism has a positive effect on the delivery ratio due to the reduced convergence time. Figure 8 depicts the average delay from the moment a datagram has been sent until it arrives at its destination. The delay largely depends on the selected enabled_time and disabled_time values. All buffering variants have significantly higher delays than standard OLSRv2 (at the benefit of a higher delivery ratio). The different buffering variants lead to similarly high delay, however, the delay of OLSRv2-IM-LB is significantly higher than the other protocols. This can be explained with the increased routing stretch -paths towards the destination are longer, as observed in figure 9.

Figure 9 presents the average path length of every data packet from its source to its destination. OLSRv2 has the shortest paths; this can be explained by the lowest delivery ratio amongst the compared protocols (as depicted in figure 7) -destinations further away from the source receive fewer of the transmitted datagrams. For the same reason, the other link buffering variants have a lower path length than GodRP-LB. Comparing GodRP-LB and OLSRv2-IM- Figure 10 shows the accumulated control traffic overhead over the simulation time (GodRP is not included, because the overhead is 0). Not surprisingly, the different link buffering variants of OLSRv2 have no influence on the control traffic. The graceful shutdown mechanism includes transmitting additional HELLOs before shutdown of a router, plus possibly triggered HELLOs and TCs of neighbors of that router.

Figure 11 shows the total number of dropped frames because of collisions during the simulation. For GodRP, almost no collisions appear, since no control traffic congests the network and only little unicast traffic is injected into the network. OLSRv2 without link buffering has the lowest number of collisions, increasing with a growing number of routers in the network -the increasing amount of control traffic leads to most of the collisions. All link buffering variants have a higher collision ratio, which can be explained by the fact that once a router reappears (i.e. changes its state from "disabled" to "enabled"), all datagrams from different sources that have been buffered while it was "disabled", are retransmitted almost the same time, as soon as valid routes towards that destination router are added to the routers that had buffered the datagrams. Again, collisions due to increasing control traffic explain the difference between the link buffering variants of OLSRv2 and GodRP-LB with higher number of routers. The bottleneck effect, that has been described in section 3.4, can be well observed due to the large number of collision when applying intermediate buffering (OLSRv2-IM-LB).

The fact that despite the high number of collision with OLSRv2-IM-LB, the delivery ratio (as depicted in figure 7) is still the highest amongst the OLSRv2 variants, can be explained by the retransmission mechanism of 802.11 [START_REF]Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[END_REF]. Even if more frames are lost due collisions on L2, eventually one may reach the destination if the frame (i.e. the next hop along the route). Figure 12 depicts the total accumulated overhead of unicast data traffic, when counting each L2 (re-)transmission at every router along the path from source to destination.

It can be seen that OLSRv2-IM-LB produces the highest control traffic overhead: The higher delivery ratio despite the higher collision ratio comes at the expense of available bandwidth on the channel.

Conclusion

This memorandum has proposed a "link buffering" mechanism, allowing a router to delay the transmission of an IP datagram if there is no valid route to the destination of that datagram at transmission time, and which is able to complement an off-the-shelf MANET routing protocol for increasing end-to-end de- INRIA livery ratio of datagrams, at the expense of higher delay. In order to test that mechanism, a network mobility model, denoted the "PopUp model" is specified: routers can be either "enabled" or "disabled". In the "disabled" state, routers cannot send or receive any data, but are allowed to change position within a bounded distance.

The off-the-shelf MANET routing protocol OLSRv2 is studied, by way of NS2 simulations, with different variations of the link buffering mechanism and when subject to the PopUp model. These simulations have shown that when using a "link buffering" mechanism, the data delivery ratio can be largely improved. Among the variations of the link buffering mechanism are a variant with buffering on layer 3 only (denoted "OLSRv2-L3-LB"), link buffering on layer 2 and 3 (denoted "OLSRv2-LB"), link buffering on intermediate routers (denoted "OLSRv2-IM-LB"), and a variant with a graceful shutdown mechanism (denoted "OLSRv2-LB-gf"). All link buffering variants yield a much higher end-to-end delivery ratio than without using such a mechanism, but also incur an increased end-to-end delay.

Figure 1 :

 1 Figure 1: Link buffering process for L3 and L2

Figure 2 :

 2 Figure 2: The gray router buffers datagrams that it forwards from the left side to the right side of the network (and vice verse)

Figure 3 :

 3 Figure 3: State diagram of the PopUp model

Figure 4 :

 4 Figure 4: Example of the PopUp mobility model

Figure 6 :

 6 Figure 6: Graceful shutdown

Figure 7 :

 7 Figure 7: Unicast data delivery ratio

Figure 8 :

 8 Figure 8: Average delay per datagram

Figure 9 :

 9 Figure 9: Path length

Figure 10 :

 10 Figure 10: Accumulated control traffic overhead

Figure 12 :

 12 Figure 11: Collisions

3 2 4 3

 34 Outline . . . . . . . . . . . . . . . . . . . . . . . . OLSRv2 Overview 4 2.0.1 Neighborhood Discovery (NHDP) . . . . . . . . . . . . . . 4 2.0.2 MPR Flooding . . . . . . . . . . . . . . . . . . . . . . . . 4 2.0.3 Link State Advertisement . . . . . . . . . . . . . . . . . . Link Buffering 4 3.1 IP Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 L2 Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3 Flow Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.4 Buffering at Intermediate Hops . . . . . . . . . . . . . . . . . . . 6 Routing Protocol . . . . . . . . . . . . . . . . . . . . . . . . 8 5.2 Graceful Shutdown . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5.3 Simulation Settings . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6 Conclusion 13

Table 1 :

 1 Link buffering states and actions

	State	Description	Action
	No Route	No routing information	Buffer IP Data-
		is available for this des-	grams
		tination
	Route Valid A route entry exists for	Transmit	IP
		this destination, and	Datagrams
		the link to the next
		hop towards this des-
		tination is not discon-
		nected

Table 2 :

 2

	Simulation settings
	Parameter	Value
	NS2 version	2.34
	Mobility model	PopUp model
	Area	1000m x 1000m
	Number of routers	20 -70
	Communication range	250m
	Radio propagation model	Two-ray ground
	Enabled time	25 -30s
	Disabled time	25 -30s
	Move distance	100m
	Simulation time	300s
	Avg. number of concurrent CBR streams	5
	Interface type	802.11b
	Radio frequency	2.4 GHz
	OLSRv2 parameters Proposed default values of

RR n°7662

Unless there are unstable links to a "close" destination in terms of hop count, and stable links to a destination far away INRIA

In some cases, a perfect routing protocol would perform better by dropping some packets even if actually routable, e.g. to destinations further away in cases of massive load on the channel. This may lead to a higher delivery ratio for destinations close to the router (i.e. neighbors) if the transmissions contend for the channel.INRIA