Routage avec Contraintes de Délai dans les Réseaux Mobiles Ad hoc

1

Nadir BOUCHAMA

[email protected]

02/03/2009

Laboratoire de Modélisation & d’Optimisation des SystèmesLAMOS

Routage avec Contraintes de Délaidans les MANETS

Application pour la VoIP

Séminaires du LAMOS, Université de Béjaia Nadir BOUCHAMA

2

Plan de l’Exposé..

Réseaux Mobiles Ad Hoc VoIP dans les MANETS: Motivations Facteurs influant la VoIP dans les MANETs Routage avec délai Le protocole DEAN (Delay Estimation in Ad hoc Networks) Composantes du protocole Estimation du délai au niveau MAC: principe et modèles Modèle M/M/1/K : rappel Contribution Routage multi-chemins Conclusion & Perspectives


3

Réseaux mobiles ad hoc

Applications:Militaire, missions de sauvetage, communications de groupes, accès Internet, etc

Caractéristiques: Liens sans fil Une topologie dynamique Ressources limitées et

volatiles (bande passante, énergie, mémoire, CPU)

Vulnérabilité aux attaques

Un réseau mobile ad hoc ou MANET (Mobile Ad hoc NETwork) est un système autonome de plateformes mobiles appelées nœuds qui peuvent se déplacer librement. Ce système peut être isolé ou avoir des passerelles ou des interfaces le reliant à un réseau fixe (Internet, ATM)

http://www.ietf.org/rfc/rfc2501.txt

GW

Internet


4

Introduction….

Au début de l’apparition des réseaux mobiles ad hoc :

Le premier souci est de permettre la connectivité des noeuds

Le principe utilisé est le BEST EFFORT c’est-à-dire « AU MIEUX»

Aucune garantie de livraison des données SEND AND PRAY (envoyer et prier que ça réussisse)

Mais….pour certaines applications ce service n’est pas du tout suffisant

Exemple:

Applications multimédias, téléphonie sur IP, jeux, applications critiques, communications dans un champs de bataille, etc.


5

Routage avec Délai: motivations

• On s’intéresse à la VoIP dans le contexte de gestion de catastrophes: la téléphonie est la première application demandée dans un tel contexte Ex: Imaginer un pompier ou un sauveteur qui communique par échange de messages écrits pas pratique

•Le délai est un facteur commun pour plusieurs applications multimédia


6

Diagramme d’Ishikawa

Protocoles Couche réseau

Protocoles Couche MAC

ProtocolesCouches App. & Prés.

ProtocolesCouche transport

Environnement

Qualité de la VoIP

Support de QoS

Signalisation

Codecs Avec QoS?

HostilitéContrôle de congestion

Estimation des ressources

Multipath?

Disponibilités des ressources

Taux de mobilité

CAC

Modèle d’estimati

on

• C’est un diagramme qui montre les relations cause à effets• proposé en 1943 par le Japonais Kaoru Ishikawa • L’étude que nous avons menée sur quelques dizaines d’articles nous a permisd’identifier les facteurs majeurs pouvant avoir un impact sur la VOIP

Fréquenceordonnanceme

nt


7

Objectifs du Routage avec QoS

Les TROIS objectifs principaux du routage avec QoS sont les suivants:

1. Déterminer dynamiquement un chemin répondant aux exigences de QoS entre une source et une destination ;

2. Optimiser les ressources du réseau (load balancing);3. Permettre une dégradation gracieuse (graceful

degradation) des performances du réseau

http://www.ietf.org/rfc/rfc2386.txt


8

Positionnement

Network requirementsApplication requirements


9

Protocole de routage avec QoS?

•Le routage avec QoS nécessite deux entités:•Protocole de routage (algorithme distribué): récolte et distribution des information sur les ressources;•Algorithme de routage (algorithme local) qui s’intéresse à la recherche d’un chemin faisable (resp. optimal) qui vérifie la QoS connu sous le nom du MCP (Multi Constraint Path) ou MCOP (Multi Constraint Optimal Path) resp.NP-Complet si le nombre de métriques additives 2Utiliser heuristiques


10

MAC

Architecture synoptique du protocole DEAN

Estimation du délai MAC

LLC

Physique

Présentation

SessionTransport

Réseau

AODVRoutage avec QoS

Besoins en QoSApplicatio

n

CAC

File M/M/1/K


11

Estimation du délai de mise en file au niveau MAC:

Question principale: Quel modèle de file d’attente utiliser pour estimer le délai au niveau du 802.11 ?

Recherche Bibliographique:

M/MMGI/1/K Ozdemir et al 2004

M/G/1 Meraihi et al, 2004 Ph.D Thesis

M/G/1/K Ozdemir et al 2004

M/M/1/K Chikh Sarr, 2007 Ph.D Thesis

G/G/1 Bisnik et al 2009


12

File M/M/1/K

Nombre de clients dans la file

Taux d’utilisation du serveur

Temps de séjour dans le système

•L'arrivée de paquet suit une loi exponentielle de paramètre λ•Le taux de service suit également une loi exponentielle de paramètreµ•La taille de la file d'attente est limitée par la valeur K. •La politique d’ordonnancement est FIFO (Premier Arrivé Premier Servi)


13

File M/M/1/K (suite)

Nombre moyen de clients dans le système

Comme la somme est égale au temps de service alors:

D’où:

?

(Loi de Little)


14

Estimation du délai moyen de transmission

Soit p la probabilité de collision sur un lien. La probabilité de réussite de transmission au premier envoi est donc 1-pLa probabilité de réussite de transmission au 2ième envoi est p .(1-p)

Après C tentatives de transmission échouées, la trame est éliminée(Pour le 802.11 C =7 )

Soit X la variable aléatoire qui compte le nombre de tentatives pour une transmission réussie d’une trame

Nombre moyen de retransmissions pour une trame donnée:


15

Délai moyen de transmission (suite et fin)

Sarr a également calculé le backoff moyen:

Enfin, on obtient:

Où:

Temps consommé dans une collision

Temps de transmission réussie d’un paquet de taille m à l’aide du 802.11


16

Echange d’information

Les nœuds échangent des messages HELLO chaque intervalle de temps Δ secondes

Ces messages HELLO contient un information supplémentaire: me taux d’occupation du canal

La valeur du paramètre Δ est cruciale: grande: stabilité des résultats mais mauvais résultats en cas de

mobilité petite : trop d’overhead et de calcul mais bonne réaction à la

mobilité Les auteurs proposent: Δ = 1 seconde

Chaque nœud estime le taux d’occupation du canal à son niveau et envoie l’information dans le paquet HELLO

La taux d’occupation du canal au niveau d’un nœud est donné par: (Ts + Tr ) / Δ


17

Déroulement de DEAN

Phase de

découverte de la route

Phase de

Réponse


18

Organigramme proposé


19

Routage avec délai vs routage multichemins

Le routage multipath peut consolider fortement le délai de bout en bout

Impact du routage multipath sur les applications multimédia dans les MANETs. PFE pour des étudiants de l’USTHB

Il s’agit notamment de voir l’impact sur le délai de bout en bout pour les application multimédia


20

Conclusion & Perspectives

Un protocole de routage avec délai a été présenté Le 802.11 a été modélisé à l’aide d’une file M/M/1/K Le problème d’estimation des ressources est difficile dans les

MANETS Le problème majeur est de trouver un bon modèle d’estimation des

ressources Le routage avec QoS peut considérablement consolider la QoS de la

VoIP mais il n’est pas suffisant Utilité d’une approche holistique

PERSPECTIVES Evaluer la complexité et la consommation en énergie du modèle Comparer les performances quantitativement (sous ns2) par rapport

au routage multichemins Intégrer la solution dans un framework pour tester les performances

pour la VoIP


21

Documents

Routage avec Contraintes de Délai dans les Réseaux Mobiles Ad hoc