ACM SIGCOMM '97 
ACM SIGCOMM '97
Applications, Technologies, Architectures et Protocoles de Communications
Cannes, Côte d'Azur, FRANCE
Tutoriaux: dimanche 14 septembre et lundi 15 septembre 1997
Conférence: du mardi 16 septembre au jeudi 18 septembre 1997
ACM SIGCOMM'97 est la conférence annuelle du groupe "Data Communications" de l' ACM (Association for Computing Machinery).
Cette année la conférence est organisée par l'INRIA Sophia Antipolis (France), avec le support de la Région PACA.
Avec l'aide des partenaires industriels : Cisco System, Eutelsat, MCI, Rank Xerox et Ascom.
Programme de la conférence :
Préliminaires
CONFERENCE ACM SIGCOMM'97
Application, Technologie, Architectures et Protocoles de Communications
Palais des Festivals, Cannes, France
du 14 au 18 septembre 1997
| dimanche 14 september 1997 | |
| Tutoriel | |
| lundi 15 september 1997 | |
| Tutoriel | |
| mardi 16 september 1997 | |
| 9:30 | Introduction |
| 11:00 | Routers rapides |
| 14:00 | Réseaux sans fil |
| 16:00 | Architecture inovantes |
| 18:30 | Réception |
| mercredi 17 september 1997 | |
| 9:00 | Communication de groupe |
| 11:00 | Web et TCP : performance |
| 14:00 | Divers |
| 16:00 | Table ronde : réseaux actifs |
| 17:15 | ACM SIGCOMM réunion de travail |
| 19:30 | Banquet |
| jeudi 18 september 1997 | |
| 9:00 | Temps réel |
| 11:00 | Mesures de Performance |
| 12:30 | Session de cloture |
Liste des sessions
Un Cadre pour le Contrôle d'Admission Robuste Basé sur Mesures Le contrôle d'admission basé sur mesures (MBAC) est un mécanisme intéressant pour offrir une qualité de service aux utilisateurs, sans pour autant nécessiter une description a-priori du trafic et une régulation en ligne. Cependant, le processus de mesure représente une source d'erreurs, car on se base sur des paramètres de trafic estimés. Nous étudions l'impact des erreurs d'estimation sur la performance d'un contrôleur d'admission. Nous considérons une séquence de modèles de compléxité croissante qui prennent en compte la corrélation du trafic, la mémoire dans le processus d'estimation, et la dynamique des arrivées et départs de flux. Nous validons nos résultats par simulation. Nous montrons qu'une hypothèse d'équivalence de certitude, qui revient à confondre les vrais paramètres avec les paramètres estimés, peut considérablement compromettre la performance du système. De plus, nous pouvons explicitement quantifier l'impact sur la performance des erreurs de mesure. Nos résultats fournissent une meilleure compréhension de la performance de systèmes proposés, et faciliteront la conception d'algorithmes qui sont robustes aux erreurs d'estimation.
Les services datagramme fournissent un modèle de communication simple, flexible, robuste et qui rend possible le passage a l'échelle; leur utilité a dors et déjà été démontrée à travers le succés de IP, UDP et RPC. Pourtant, la majorité des abondants protocoles de sécurité réseaux sont adaptés à la communication en mode connecté. Les quelques uns qui s'intéressent à la communication en mode non connecté ont tendance soit à se reposer sur la présence de clés permanentes chez les machines distantes, soit à imposer une semantique orientée session (i.e., qui nécessite une phase d'établissement de connection). Par ailleurs, le concept de flots est devenu récemment l'objet d'une grande attention, plus spécialement dans le domaine du routage et de la qualité de service. Un flot charactérise une séquence de datagrammes qui partage un certain nombre d'attributs prédéfinis. Dans ce papier, nous préconisons l'utilisation des flots comme structure de base à la communication en mode non connecté sécurisée. Nous appuyons cette revendication en proposant un nouveau protocole datagramme sécurisé basé sur flots. Notre protocole ne fait intervenir aucun message relatif à un échange de clés, préservant ainsi la nature non connecté de la communication par datagramme, et utilise des états mous, permettant ainsi d'atteindre l'efficacité des shémas orientés session. Nous avons implémenté une instance de ce protocole pour IP dans le noyau du système BSD4.4, dont nous fournissons une description accompagnée des résultats de performances.
Dans cet article, nous proposons un algorithme de régulation qui, à notre connaissance, est le premier à fournir en même temps :
Ce resultat découle de l'introduction , dans les régulateurs du type courbe de service, d'une propriété définie d'équité, propriété essentielle dans le cas du partage de circuit, propriété qui permet de découpler l'allocation de la bande passante et du retard. Nous appelons << Courbe de Service Equitable Hiérarchique, en anglais : Hierarchical Fair Service Curve, (H-FSC) >> la version hiérarchique de l'algorithme qui en decoule.
Nous analysons le comportement du H-FSC et présentons des résultats de simulation qui illustrent ses avantages par rapport àceux proposés jusqu'ici comme le H-PFQ ou le CBQ. Nous présentons également des résultats expérimentaux préliminaires fondés sur un prototype implémenté sous NetBSD.
Un grand intérêt a été porté dernièrement dans les réseaux à la possibilité de combiner la vitesse de commutation du niveau 2 avec les capacités de routage du niveau 3. De nombreuses propositions exploitent cette combinaison, notamment IP Switching[1], Tag Switching[2], ARIS[3], CSR[4], et IP sur ATM[5]. Dans cet article, nous étudions IP Switching et évaluons les performances avancées par Newman et al dans [1] et [6]. En particulier, à partir de neuf relevés de trafic réseau, nous étudions comment IP Switching se comporte dans des environnements de campus, d'entreprise, ou de fournisseur de service. Notre principale découverte est qu'IP Switching atteint une proportion élevée de paquets commutés, plus de 75% dans les environnements étudiés. Nous étudions également l'influence de différents algorithmes d'ordonnancement de flux et différentes dates d'expiration sur les performances d'IP Switching. Certains choix notamment requièrent un espace de VC conséquent. Enfin, nous présentons certaines recommandations quant au choix de ces algorithmes et valeurs, en fonction de l'espace de VC du commutateur considéré et de l'environnement réseau desservi.
Les réseaux actifs accélèrent l'évolution des réseaux en permettant la programmation de l'infrastructure du réseau en fonction d'un utilisateur, d'un paquet, ou selon d'autres critères. Cependant, il y a un compromis entre rendre le réseau programmable et assurer les besoins de sureté et de sécurite propres aux ressources partagées. Cet article décrit l'analyse, l'implémentation et la performance d'un nouveau type de composants des réseaux, le Pont Actif. Le Pont Actif peut être reprogrammé sur le fil, par le biais de modules chargeables appelés Switchlets. En plusieurs étapes, nous étendons ce qui n'est initialement qu'un répeteur à tampons programmables vers un Pont autodidacte, puis un pont supportant les algorithmes générant des arbres recouvrants et enfin un pont supportant les plusieurs algorithmes générant des arbres recouvrants. Afin de démontrer l'usage de la propriété active, nous avons implémenté un algorithme qui opère le glissement coordonné depuis un protocole STP de type DEC vers notre implémentation 802.1D, avec les dispositions nécessaires permettant la reprise automatique en cas de détection d'une erreur dans l'implémentation 802.1D. Ceci montre que le Pont Actif peut se protéger de lui-même contre des défaillances algorithmiques dans les modules chargeables. Notre approche dans le domaine de la sureté et de la sécurité consiste à faire les vérifications et la prévention de manière statique plutôt que dynamique lorsque ceci est possible. En ce qui concerne l'infrastructure du module chargeable, nous nous reposons sur de fortes caractéristiques de vérification de type du language Caml, et avons ainsi atteint des performances convenables. L'implémentation d'un prototype sur une machine HP Netserver LS basée sur un Pentium à 4 processeurs et tournant sous LINUX LAN Eternet à 100 Mbps a atteint un débit ttcp de 15 Mbps entre deux PCs tournant sous LINUX, comparé, sans ponts, a des performances de 45 Mbps.
Nous décrivons dans ce papier l'outil "tcpanaly" qui permet l'analyse automatique d'une implémentation TCP à partir de traces au niveau paquet de cette implémentation. La mise au point de cet outil a nécessité de résoudre plusieurs problèmes, en particulier ceux causés par les erreurs de mesure dans le processus de filtrage des paquets, les différences (parfois très grandes) entre différentes implémentations, et les ambiguités venant de la séparation entre le processus de mesure et l'implémentation mesurée. Nous analysons les raisons pour lesquelles le développement d'un outil général a échoué, et détaillons les différences principales entre 8 implémentations ``classiques'', certaines d'entre elles ayant un comportement tel qu'il mettrait l'Internet à genoux si elles étaient déployées largement. En fait, les mauvaises implémentations de TCP ont toutes été écrites de façon isolée, ce qui indique que l'écriture d'une implémentation efficace n'est pas une chose simple. Ceci veut donc dire que la communauté Internet devrait fournir des programmes de test ainsi que des implémentations de référence pour éviter des problèmes de performance importants dans l'Internet.
"Farcir des bits" est un procédé qui permet de transformer une séquence de bits qui contient des sous-ensembles "réservés" ou "illégaux" en une séquence équivalente, éventuellement plus longue, et qui ne contient pas les occurences génantes. L'augmentation potentielle de taille n'est pas évitable, mais peut être contrôlée en choississant des algorithmes adaptés au contexte. Les algorithmes habituellement utilisés tels que SLIP [RFC1055], PPP [RFC1661] et AX.25 [ARRL84], offrent des augmentations de taille trés variables, qui vont de pas d'augmentation pour certaines séquences au doublements pour d'autres séquences. Le surcoût du au farcissage de bits nous oblige à accroître la complexité du logiciel et du hardware de communication. Des interfaces telles que les émetteurs radio sur les ordinateurs portables ont des contraintes de poids, de taille, et de consommation électrique qui interdisent la complication du matériel et logiciel. La popularité croissante de ces outils ramène sur le devant de la scène le problème du farcissage de bits. Ce papier présente un algorithme de farcissage de bits dont le surcoût maximum est limité. Les performances moyennes de cet algorithme sont voisines de celles de SLIP, mais notre algorithme a l'avantage d'offrir une garantie sur les performances. Dans le pire des cas, le surcoût ne sera que de 8 bits pour au moins 254 paquets. Par exemple, sur un paquet de 1000 octets, notre algorithme rajoute 4 octets, soit un surcoût de 0,4%. Une variante simple de cet algorithme est systématiquement plus performante que SLIP en rajoutant un surcoût toujours inférieur a .0,5%.
Dans cet article, nous étudions l'efficacité du mécanisme de Détection Aléatoire Précoce (DAP) sur trois types de trafic différents: non adaptatif chargé, par rafale, adaptatif. Nous mettons en évidence le fait que DAP conduit à un partage non équitable de la bande passante lorsque les trois types de trafic coexistent au routeur considéré. Cela est attribué au fait que DAP rejette les paquets des connections en compétition proportionnellement à leur utilisation de la bande passante. Nous proposons l'algorithme de Détection Aléatoire Précoce Equitable (DAPE), version modifiée de DAP. DAPE détecte l'apparition de congestion en surveillant la taille moyenne de la file d'attente et décide qu'un packet doit être rejeté lorsque celle-ci dépasse un certain seuil. Avec DAP toutes les connections subissent le même taux de perte de paquets. DAPE, lui, rejette différemment les paquets pour des connections de différentes bande passante grace à des mesures sur chaque connection active. Nous montrons que DAPE procure une meilleure protection pour les connections par rafales. De plus, DAPE permet de mieux isoler les connections non adaptatives. Ces améliorations sont mises en évidence par des simulations de traffic UDP et TCP. DAPE ne fait aucune hypothèse sur l'architecture des files d'attente. Le cout des mesures pour chaque connection active dans DAPE est seulement proportionnel à la taille totale de la mémoire et est indépendant du nombre de connections.
Cet article démontre l'existence, et détermine explicitement la bande passante efficace d'une classe de sources fluides non Markoviennes qui sont caractérisés par de multiples débits de transmission pendant lesquels leurs distributions sont arbitraires. L'étendue des modèles présentés couvre un plus grand nombre de type de traffic que leurs homologues sources fluides Markoviennes et ont un espace d'états réduit. La bande passante efficace, comme une fonction du débit dégradé de la probabilité de perte asymptotique, est implicitement dérivable en raison du pré-requis suivant: le rayon spectral d'une matrice non-négative est égal à l'unité. On montre que la fonction de bande passante efficace est soit strictement croissante, soit constante et égale au débit moyen. Les sources de la deuxième catégorie qui sont caractérisées, généralisent la notion de traffic CBR (à débit constant). De plus, une étude de la limitation de bande passante efficace dans un environnement sans perte est incluse; elle montre que la valeur de limitation, sous certaines restrictions clairement identifiées, est inférieure au débit crête de la source. Sous ces restrictions, une source peut avoir des besoins en bande passante réduits, même s'il présente un débit crête élevé.
Nous discutons les résultats d'une étude des caractéristiques dynamiques au niveau paquet de connections Internet. Les mesures ont été obtenues en observant 20 000 transferts TCP entre 36 sites différents. Ces transferts de 10 Koctets chacun ont été observés à la fois à la source et à la destination, ce qui permet d'observer les caractéristiques des connections ``dans chaque sens'', et de vérifier qu'effectivement ces caractéristiques ne sont pas symmétriques. Nous caractérisons la fréquence d'évènements rares comme la réception de paquets hors séquence, la duplication ou la corruption de paquets. Nous développons un algorithme robuste d'estimation à la destination du débit du goulot d'étranglement, qui évite certains problèmes observés avec la techniques des paires de paquets. Nous analysons le processus de pertes, montrons que les pertes ne sont pas indépendentes, et de plus que la distribution de la durée d'un évènement de perte à une variance infinie. Finalement, nous évaluons l'efficacité des délais comme indicateurs de congestion, et observons que les périodes de congestion ont des durées qui peuvent couvrir un grand nombre d'échelles de temps.
La plupart des algorithmes actuels de régulation équitable sont plus adaptés aux circuits filaires qu'aux canaux sans-fil, dont les flots de paquets sont sensibles au retard et au débit. Car les supports sans-fil ont deux caractéristiques propres :
Par ailleurs, dans les réseaux cellulaires de paquets, la station de base se charge la plupart du temps elle-même de la régulation de tous les paquets de la cellule, en émission comme en réception; et ce, bien que la station de base n'ait qu'une connaissance limitée du processus d'arrivée des flots à émettre. Dans cet article, nous proposons un nouveau modèle de régulation équitable pour le sans-fil, fondé sur une adaptation du modèle fluide de file d'attente équitable, adaptation qui permet de traiter les rafales d'erreurs survenant localement. Nous décrivons un algorithme idéal de régulation équitable du sans-fil qui fournit une implémentation sous forme de paquets du modèle fluide dans l'hypothèse ou l'on connait parfaitement les conditions courantes du canal. Avec cet algorithme, nous déduisons le débit minimal et les limites du retard. Nous décrivons enfin un protocole pratique de régulation du sans-fil qui se rapproche étroitement de l'algorithme idéal, qui résoud plusieurs problèmes d'accès au support sans-fil liés à l'implémentation et qui emploie une prédiction de canal mono-étape simple. A l'aide d'un grand nombre de simulations, nous montrons que le protocole affiche les propriétés souhaitées parmi celles retenues dans le modèle de file d'attente équitable fluide pour le sans-fil.
Beaucoup d'applications reposent sur la disponibilité de services de communications dont la rapidité et la fiabilité ont un niveau de contrôle et de coût acceptable. Nous présentons un schéma de remise en service de canaux en temps-réel, dans un délai garanti, après une ou plusieurs défaillances de composants d'un réseau maillé. Pour assurer le succès de la reprise du service et éviter d'avoir à réétablir les canaux, ce qui prend du temps, des canaux supplémentaires de secours sont disposés a priori. De ce fait, une connexion en temps-réél consiste en un canal primaire et un ou plusieurs canaux de secours. Lors d'une défaillance du canal primaire, l'un des ses canaux de rechange est activé et devient un nouveau canal primaire. Nous proposons un protocole efficace qui fournit une solution intégrée (commutation de canal, réallocation de ressource etc.) au problème de la reprise sur panne. Nous dévelopons également une méthode de partage de ressources qui réduit de manière significative le surcoût des canaux de réserve. Les résultats de simulation montrent qu'une bonne couverture des reprises sur incident peut être atteinte moyennant une dégradation de 10 à 30% de la capacité utile du réseau pour des pannes ordinaires. De plus, le niveau de tolérance aux fautes de chaque connexion peut être contrôlé pour mesurer son degré de nature critique, ce qui forme l'une des caractéristiques originales du schéma proposé.
Un certain nombre d'analyses de HTTP/1.0 et de propositions ont influencé la conception de HTTP/1.1. Les objectifs principaux de HTTP/1.1 comprennent:
Deux mécanismes dans HTTP/1.1, à savoir les connexions persistentes et le chaînage, servent à atteindre ces objectifs. Nous décrivons l'impact de ces mécanismes sur les performances client et serveur en utilisant une plateforme de test simple. Nous décrivons les performances TCP et temps réel obtenues entre un serveur Jigsaw HTTP/1.1 et un robot libwww utilisant HTTP/1.0, HTTP/1.1 avec connexions persistentes, et HTTP/1.1 avec requêtes chaînées. Nous évaluons également l'impact de l'agorithme TCP de Nagle sur HTTP/1.1. Nos tests, bien que peut être un peu articiels et biaisés en faveur de HTTP/1.1, sont, nous le pensons, représentatifs du comportement typique des browsers. Les résultats montrent que dans tout les cas, HTTP/1.1 avec chaînage est meilleur que HTTP/1.0, même quand l'implémentation de HTTP/1.0 utilise plusieurs connexions en parallèle. Le gain en performance exprimé en nombre de paquets transmis est d'au moins deux, parfois beaucoup plus. Le gain exprimé en temps écoule est moins important, mais quand même significatif. Tous les tests de HTTP/1.1 avec chaînage donnent de meilleures performances qu'avec HTTP/1.0 avec connexions multiples.
Cet article examine les informations de routage inter domaine échangées entre les fournisseurs d'accès aux principaux points publics d'interconnection internet des Etats-Unis. L'instabilité du routage internet, ou la rapide fluctuation des informations de connectivité du réseau est un des problèmes les plus cruciaux auquel est confrontée la communauté d'ingénieurs de l'Internet. Des niveaux élèves d'instabilité du réseau peuvent conduire à des pertes de paquets, des délais accrus, et une convergence lente. Dans des cas extrêmes, une telle instabilité a provoqué des pertes totales de connectivité interne dans des réseaux large zone nationaux. Dans cet article, nous décrivons différentes tendances inattendues en matière d'instabilité du routage et examinons un certain nombre d'anomalies et pathologies observées dans l'échange d'information de routage inter-domaine. Cet article presente une analyse de tous les paquets BGP échangés entre les routeurs frontaliers aux points d'interconnection de la dorsale Internet publique sur une période de neuf mois. Nous montrons que le volume des mises à jour de routage est supérieur de plusieurs ordres de grandeur à celui attendu, et que la majorité des informations de routage présente des anomalies. De plus, notre analyse révèle certaines tendances surprenantes et certains comportements systématiques inappropriés du routage Internet. Enfin, nous avançons un certain nombre d'explications à ces anomalies et évaluons leur possible impact sur l'infrastructure de l'Internet.
Les applications multi-points sont en pleine expansion et vont rendre crucial le besoin de sécurité dans la multi-diffusion. La multi-diffusion ne s'adapte pas au modèle point-a-point sur lequel sont basés la plupart des protocoles de sécurité réseaux. Comme nous allons le voir, la sécurité de la communication multi-diffusion (ou de groupe) est traitée de manière fondamentalement différente de celle de la communication point-à-point (ou bidirectionnelle). Ces différences peuvent résulter en des problèmes de passage à l'échelle pour des applications multi-points typiques. Dans ce papier, nous analysons et modélisons les différences entre la sécurité point-à-point et la sécurité multi-point, et nous présentons Iolus: un nouveau cadre pour la multi-diffusion sécurisée à grande échelle. Les protocoles qui se basent sur Iolus peuvent être utilisés pour atteindre un certain nombre d'objectifs de sécurité. Ils peuvent être utilisés soit de manière directe pour sécuriser la multi-diffusion soit pour fournir une gestion de clés à d'autres applications qui prennent en compte la sécurité. Dans ce dernier cas, les protocoles basés sur Iolus peuvent fournir une composante de la solution complète. Nous présentons un prototype de notre modèle qui a été utilisé dans le cadre de l'outil de video conférence VIC.
Editeur de texte Réseaux (NTE): Un éditeur
de texte partagé pour le MBone (réseau multipoint virtuel
au dessus de IP)
Mark Handley (Information Sciences Institute, University of Southern
California) et Jon Crowcroft (University College London)
Les sessions multipoints et à coût léger ainsi que les applications ALF fournissent un cahier des charges dans lesquels les outils de conférence multimédia peuvent être mis en oeuvre, mais ils ne donnent pas de solutions spécifiques. Dans ce papier, nous utilisons ces principes de conception pour guider la conception d'un éditeur partagé qui supporte le multipoint, et analysons les conséquences quant au choix de l'approche "sans consistance" pour obtenir de bonnes performances face aux erreurs du réseau et des pertes.
Nous examinons dans ce papier comment utiliser à la fois des méthodes de type retransmission (RETR) d'une part, et ajout de redondance (RED) d'autre part, pour obtenir un mécanisme de transmission multipoint fiable efficace à toutes les échelles. Nous considérons deux scénarios, l'un dans lequel RED est utilisé dans une sous couche transparente sous une couche multipoint fiable qui utilise RETR, l'autre dans lequel RETR et RED sont tous les deux intégrés dans une seule couche qui utilise la retransmission des données de parite pour reconstruire les paquets perdus. Pour évaluer le gain en performance apporte par RED, nous considérons différents types de pertes (pertes correllées dans le temps ou dans l'espace, pertes homogènes ou hétérogènes) et de taux de pertes, pour un nombre de destinations pouvant atteindre 106. Nos résultats montrent que l'ajout de RED à RETR (c'est-à-dire l'ajout de redondance à la retransmission) améliore enormément la performance de la transmission multipoint fiable.
Les mécanismes de cache du World Wide Web utilisent la plupart du temps un modèle naïf, qui suppose que les ressources sont référencées plusieurs fois entre deux modifications. Pire, ce modèle n'offre aucun autre moyen de mettre à jour une entrée du cache que de transférer la totalité de la nouvelle valeur. Quelques auteurs ont déjà proposé de mettre à jour les entrées du cache en ne transférant que les seules différences, ou << delta >> entre l'entrée disponible dans le cache et la valeur courante. Dans cet article, nous tirons parti des traces dynamiques de la totalité du contenu des messages HTTP pour quantifier les bénéfices potentiels des réponses delta-encodées. Nous montrons que, pour un ensemble important de types de contenu HTTP, le delta-encodage peut apporter de remarquables améliorations de la taille et du délai de la réponse. Nous montrons aussi le bénéfice additionnel de la compression de données, et que la combinaison du delta-encodage et de la compression de données produit les meilleurs résultats. Nous proposns des extensions spécifiques du protocol HTTP pour le delta-encodage et la compression de données. Ces extensions sont compatibles avec les implémentations et les spécifications existantes, et autorisent néanmoins l'usage efficace d'une batterie de techniques d'encodage.
La recherche dans une table d'une adresse internet est devenue un challenge en raison de la taille croissante des tables de routage, du trafic accru, des liens haut débit et de la migration à128 bits des adresses IPv6. La recherche d'une route IP requiert le calcul d'un plus long préfixe commun pour lequel des solutions standards telles qu'une table de hachage sont considérées inapplicables. La meilleure solution dont nous avons connaissance, les arbres binaires de type BSD, perd de son efficacité avec le passage à des adresses IP de 128 bits. Notre article décrit un nouvel algorithme de recherche de plus long préfixe commun qui utilise une recherche binaire sur des tables de hachage organisées par longueur de prefixe. Notre mécanisme se comporte très bien avec l'augmentation de la taille des adresses et de la table de routage: indépendant de la taille de la table, il nécessite en temps au plus long (taille des adresses) lectures de table de hachage; ainsi, seulement 5 lectures de table de hachage sont nécessaires pour IPv4 et 7 pour IPv6. Nous introduisons également une Recherche Binaire Mutante (RBM) et d'autres optimisations qui, pour un routeur IPv4 typique de dorsale internet avec plus de 33000 entrées, réduisent considérablement le nombre moyen de lectures jusqu'à moins de 2. Et une de ces lectures peut-être simplifiée en lecture de tableau indexé. Nous espérons un comportement similaire dans le cas moyen pour IPv6.
Nous considérons le problème du support de communication multipoint au niveau de la couche du contrôle d'accès des réseaux de "diffusion et sélection WDM". Nous montrons d'abord que la consommation de bande passante et l'utilisation de canaux apparaît comme deux objectifs conflictuels dans la conception d'algorithmes d'ordonnancement pour du trafic multicast dans cet environnement. Nous présentons ensuite une nouvelle technique pour la transmission de paquets multicast basé sur le concept d'un receveur virtuel, un ensemble de receveurs physiques qui se comportent identiquement en terme d'ajustement. Nous montrons aussi que le nombre k de receveurs virtuels influence naturellement le compromis entre l'utilisation de canaux et la consommation de bande passante. Notre approche découple le problème de détermination de receveurs virtuels à partir de l'ordonnancement des transmissions de paquets. Ceci permettant l'utilisation d'algorithmes d'ordonnancement qui montrer la possibilité de cacher les effets de latence de d'ajustement. En conséquence, nous étudions en particulier le problème de sélectionner de façon optimale les receveurs virtuels, et nous prouvons que cela est NP-complet. Enfin, nous présentons quatre heuristiques de degrés diffirents de complexité pour obtenir des receveurs virtuels qui fournissent un bon compromis entre les deux objectifs conflictuels.
Nous développons une nouvelle technique de transmission multicast pour les applications de vidéo à la demande appelée Skyscaper Broadcasting. Nous discutons les techniques de fragmentation des données, les stratégies de télédiffusion et le design des clients. Nous montrons aussi la validité de notre technique et procédons à des dérivations de nos équations mathématiques pour analyser les besoins en stockage. Nous comparons les performances du système avec des designs récents comme le Pyramid Broadcasting (PB) et le Permutation Based Pyramid Broadcasting (PPB). Notre étude indique que PB offre d'excellents temps d'accès, mais requiert de gros besoins en bande passante disque et capacité de stockage chez le receveur. PPB est capable de résoudre ces problèmes. Cependant ceci est accompli au détriment du temps d'accès et implique une synchronisation complexe. Avec SB nous sommes capables de réaliser le temps d'accès faible de PB en n'utilisant que 20 % de l'espace mémoire demandé par PPB.
Pendant longtemps, la communaut'e Internet a considéré qu'il etait impossible d'effectuer des lectures logicielles de cache de routage assez rapides pour supporter des vitesses de l'ordre du gigabit. Le recherche d'une route IP vers une destination consiste à trouver l'entrée de la table de routage ayant le plus long préfixe commun avec la destination. Cette tache était estimée requérir un support matériel à des fréquence de recherche de l'ordre du million par seconde. Nous présentons une structure de donnée de cache de routage conçus pour des lectures de table rapides. Les tables sont de tailles assez petite pour tenir dans le cache d'un processeur classique. Avec cette table en mémoire caché, un Pentium Pro a 200 MHz ou un Alpha 21164 a 333MHz peuvent effectuer quelques millions de recherches par seconde. Ce qui signifie qu'il est possible de faire une recherche complète de route pour chaque paquet IP à des vitesses de l'ordre du gigabit sans équipement matériel dédié. Les caches de routage sont très petits, une grande table de routage avec 40000 entrées pouvant être compactée en un cache de 150-160 Koctets. Une recherche nécessite typiquement moins de 100 instructions sur un Alpha, utilisant 8 références mémoire pour accéder un total de 14 octets.
Nous présentons une nouvelle discipline d'accès canal appellée acquisition de canal à accès multiple (ACAM, ou FAMA en anglais), dans laquelle l'accès au canal est permis à une seule station à un instant donné, cette station ayant alors la garantie qu'un ou plusieurs paquets de données seront envoyés vers différentes destinations dans collisions. Nous décrivons des protocoles ACAM qui comprennent un senseur non persistent de canal, et un dialogue avec évitement de collision entre source et destination. Nous présentons des conditions sous lesquelles ces protocoles fournissent un accès canal sur, et nous vérifions que ces conditions sont suffisantes, même en présence de terminaux cachés. Nous montrons en fait que les protocoles ACAM doivent utiliser un senseur de canal pour offrir un accès correct. Nous étudions également le débit des protocoles ACAM dans le cadre d'un canal simple avec terminaux cachés; nous montrons que leur performance est meilleure que celle des protocoles ALOHA et CSMA en présence de terminaux cachés.
Soumettre un système d'ordinateurs mobiles à des conditions de réseaux sans fil qui soient à la fois réalistes et reproductibles est un problème difficile. Dans cet article, nous décrivons une technique appelée "modulation de traces" qui recrée les caractéristiques bout-en-bout observées d'un vrai réseau sans fil d'une façon contrôlée et reproductible. Les avantages clé de notre méthode sont la transparence pour les applications, et la prise en compte de la totalité du trafic généré et reçu du système en question. Nous présentons les résultats d'expériences pour vérifier que notre approche est capable de reproduire correctement la performance de réseaux sans fil.
TUTORIAUX, 14-15 septembre 1997
| 14 Septembre |
SUN1 La communication de groupe Mostafa Ammar et Don Towsley |
SUN2 Chase Bailey |
| 15 septembre |
MON1 Don Brutzman, Mike Macedonia, Theresa-Marie Rhyne et Steve McCanne |
MON2 S. Keshav |
La Communication de groupe dans les réseaux
Mostafa Ammar et Don Towsley SUN2
Commerce Electronique
Chase Bailey September 15 MON1
Graphiques 3D à travers les Réseaux
Don Brutzman, Mike Macedonia, Theresa-Marie Rhyne and Steve McCanne
MON2
Gestion de trafic: Concepts, problèmes, et défis
S. Keshav
Mostafa Ammar, Georgia Tech., et Don Towsley, U. Mass.
La demande des applications multimédia (vidéo-conférences, jeux distribués, travail coopératif) pour un support de communication multipoint est énorme. Ce tutorial fait le point sur les développements les plus récents dans ce domaine, ainsi que sur les travaux de recherche. Les aspects les plus importants de la communication de groupe qui seront abordés dans ce tutoriel sont l'escaladabilité le fiabilité, ainsi que le contrôle de congestion. Le tutoriel décrira l'état de l'art dans Internet et dans ATM, au niveau gestion de groupes, routage, et contrôle de bout-en-bout.
Mostafa H. Ammar received his Ph.D. Degree in Electrical Engineering
from the University of Waterloo in Ontario, Canada, 1985. His S.M.(1980),
S.B.(1978) degrees were acquired in Electrical Engineering and Computer
Science at the Massachusetts Institute of Technology, Cambridge, MA. Dr.
Ammar is currently an Associate Professor in the College of Computing at
Georgia Tech. He has been with Georgia Tech since 1985. For the years 1980-82
he worked at Bell-Northern Research (BNR), in Ottawa, Ontario, Canada,
first as a Member of Technical Staff and then as Manager of Data Network
Planning. Dr. Ammar's research interests are in the areas of computer network
architectures and protocols, multipoint communication, distributed computing
systems, and performance evaluation. He is the co-author of the textbook
"Fundamentals of Telecommunication Networks," published by John
Wiley and Sons. Dr. Ammar is the holder of a 1990-1991 Lilly Teaching Fellowship
and received the 1993 Outstanding Faculty Research Award from the College
of Computing. He is a member of the editorial board of IEEE/ACM Transactions
on Networking and Computer Networks and ISDN Systems Journal. He is also
the co-guest editor of a recent issue (April 1997) of IEEE Journal on Selected
Areas in Communication on "Network Support for Multipoint Communication".
He is the Technical Program Co-Chair for the 1997 IEEE International Conference
on Network Protocols. Dr. Ammar is a Senior Member of the IEEE and a member
of the ACM and a member of the Association of Professional Engineers of
the Province of Ontario, Canada.
Don Towsley received the B.A. degree in physics and the Ph.D. degree in
Computer Science from University of Texas in 1971 and 1975 respectively.
From 1976 to 1985 he was a member of the faculty of the Department of Electrical
and Computer Engineering at the University of Massachusetts, Amherst. He
is currently a Professor of Computer Science at the University of Massachusetts.
He has held visiting positions at the IBM T.J. Watson Research Center,
Yorktown Heights, NY (1982-1983), Laboratoire MASI, Paris, France (1989-1990),
and INRIA, Sophia-Antipolis, France (1996). His research interests include
networks and multimedia systems. He currently serves on the Editorial board
of Performance Evaluation and has previously served on numerous editorial
boards including those of the IEEE Transactions on Communications and IEEE/ACM
Transactions on Networking. He was a Program Co-chair of the joint ACM
SIGMETRICS and PERFORMANCE '92 conference. He is a member of ACM, ORSA
and the IFIP Working Groups 6.3 and 7.3. He has received two best paper
awards from the ACM SIGMETRICS annual conferences and has been elected
Fellow of both the ACM and IEEE.
Avec la croissance de l'Internet, un nouveau "business model" basé sur les transactions électroniques est envisageable. De nouveaux marchés globaux et régionaux sont désormais accessibles. Ce tutoriel présentra les techniques utilisées afin de supporter le commerce électronique. Il est centré sur l'étude des problèmes de sécurité, du chiffrement, de l'authentification, des transactions électroniques sécurisées (SET), des certificats, des autorités de certification ainsi que d'autres besoins techniques pour le commerce électronique sur Internet.
Chase Bailey has been working in the telecommunications and internetworking industry for many leading suppliers for over 25 years. His position at Cisco has him leading the effort of analysis of the networking industry's future both in markets and technologies. This long range strategic marketing effort is focused on the growth of the internet and it's effects on the technologies and products required to scale and manage this new global infrastructure.
En dépit du fait que les réseaux et le traitement d'images sont considérés deux disciplines distinctes, une convergence entre eux est ressentie. Par exemple, les deux disciplines dont concernées quand on utilise le 3D comme l'exploration collabortive, la visualisation de l'information et les environnements virtuels à grande échelle (LSVE). Ce tutoriel présente une introduction à une fusion ds deux disciplines pour l'utilisation et le développement d'applications graphiques interactives sur le réseau. Nous allons montrer des exemples de ce qui pourrait être réalisé quand on combine les graphiques 3D interactive avec le Web et/ou des flux d'information via l'Internet. Enfin, nous discutons de l'avancement des travaux concernant la combinaison graphique-réseau à l'IETF, ainsi qu'au consortium VRML et d'autres organismes de standarisation.
Don Brutzman is an Assistant Professor in the Interdisciplinary Academic Group at the Naval Postgraduate School. His research interests include underwater robotics, real-time 3D computer graphics, artificial intelligence and high-performance networking. He is very active in the Virtual Reality Modeling Language (VRML) Community and was Chair of the VRML 97 Symposium. He is a member of the Institute of Electrical and Electronic Engineers (IEEE), the Association for Computing Machinery (ACM) Special Interest Groups on Graphics (SIGGRAPH) and Communications (SIGCOMM), the American Association for Artificial Intelligence (AAAI) and the Virtual Reality Modeling Language (VRML) Consortium.
Mike Macedonia received his Ph.D. in computer science from the Naval Postgraduate School. Currently, he is Vice President in charge of developing virtual environments for commerce, government, and education at the non-profit Fraunhofer Center for Research in Computer Graphics (CRCG) His research interests include multicast data networks, real-time computer graphics and large-scale virtual environments. He also contributed to the United States' National Academy of Sciences report entitled "Virtual Reality: Scientific and Technological Challenges" detailing the networking and communications research needed to continue the development of virtual reality systems.
Theresa-Marie Rhyne is currently a Lead Scientific Visualization Researcher and is responsible for the Research and Development activities at the United States Environmental Protection Agency's Scientific Visualization Center. She is employed by Lockheed Martin Technical Services. Her research interests include visualization toolkit development, collaborative visualization in a networked environment, and the integration of geographic information systems with scientific visualization. She is also a practicing fine artist and art educator in computer graphics. She was the ACM SIGGRAPH 96 Panels Chair and currently serves as a Director at Large on the ACM SIGGRAPH Executive Committee. (Example Graphics at Web site: (http://www.epa.gov/gisvis))
Steve McCanne received his Ph.D. degree in Computer Science from the University of California, Berkeley, in 1996. From 1988 to 1996, he was on the staff at the Lawrence Berkeley National Laboratory where he co-developed the network and application architecture and software that underlies the Internet Multicast Backbone or "MBone'' tools. In 1996, he joined the faculty of the Department of Electrical Engineering and Computer Science at the University of California, Berkeley, where he is currently an Assistant Professor. His research interests include multimedia networking, multicast communication protocols, signal compression, remote collaboration technologies, and network simulation architectures. He is a member of the IEEE, the ACM, the AAAS, and the Internet Engineering Task Force.
La gestion de trafic est un ensemble de mécanismes dont le but est de controler le trafic dans un réseau. Ca s'étend sur plusieurs échelle de temps: de l'ordonnacement et du lissage de trafic à l'échelle la plus rapide, à la planification de la bande passante à l'échelle la plus lente. Ca s'étend aussi sur plusieurs "classes de trafic", une abstraction qui fait référence à un ensemble commus de besoins applicatifs, ainsi qu'aux services réseaux correspondants. Ce tutoriel couvrira la gestion de trafic dans les réseaux larges, y inclus l'Internet, le réseau téléphonique et les réseaux ATM.
S. Keshav is an Associate Professor of Computer Science at Cornell University. Formerly a Member of Technical Staff at AT&T Bell Laboratories, Dr. Keshav received his Ph.D. in Computer Science from UC Berkeley in 1991. He is the author of numerous technical papers, two of which were selected by ACM Sigcomm as being among the most influential papers in computer networking in the past twenty-five years. His book, "An Engineering Approach to Computer Networking" was published by Addison-Wesley in their Professional Computing Series in May 1997.
Information d'enregistrement
Frais d'enregistrement :
NB : Tous les frais suivants sont inclus de la TVA
Enregistrements avant le 1er août 1997
| Membre-ACM | Non-Membre | Etudiants | |
| Conférence |
USD 375 |
USD 450 |
USD 110 |
| Tutoriaux |
USD 300 |
USD 400 |
USD 150 |
Enregistrements après le 1er août 1997
| Membre-ACM | Non-Membre | Etudiants | |
| Conférence |
USD 420 |
USD 500 |
USD 200 |
| Tutoriaux |
USD 350 |
USD 450 |
USD 200 |
L'enregistrement ux tutoriaux courvre les documents et le déjeuner
le jour du tutoriel. Les frais s'entendent par tutoriel.
Tous les frais couvrent pour chaque conférence, la participation
à la conférence, les documents et les déjeunerss'entendent
par conférence, ainsi qu'une invitation nommée dégustation
de vins et fromages le lundi soir, Session au bord de la piscine le mardi
soir, et le banquet de la conférence le mercredi soir.
Tous les paiements doivent être fait en dollars américains
seulement.
Note: On-site registration only with credit card or cash (US Dollars).
Contacter Dany.Sergeant@inria.fr
Contacter Dany.Sergeant@inria.fr
Lieu
Les tutoriaux et la conférence auront lieu dans deux différents endroits :
Lieu des tutoriaux
INRIA Sophia-Antipolis
2004 route des Lucioles B.P. 93
06902 Sophia-Antipolis cedex
FRANCE
Ph: (33) 493.65.77.77; Fx: (33) 493.65.77.66
Tous les matins et tous les soirs une navette assurera le transport entre les hotels de la conférence et le lieu des tutoriaux. Le trajet en navette est de 15 à 20 minutes.
Lieu de la conférence
Palais des Festivals
Esplanade George Pompidou - La croisette
06400 Cannes
FRANCE
Ph: (33) 493.39.01.01; Fx: (33) 493.99.37.34
Tous les hotels de la conférence sont à 5-15 minutes de marche jusqu'au lieu de la conférence.
Les prix et les disponibilités ne sont pas garantis après cette date. Contactez directement les hotels pour faire votre réservation avec les prix SIGCOMM'97.
Le lieu de conférence est accessible à pied de tous les hôtels.
Une navette assurera les trajets entre les hôtels et l'INRIA pendant la durée des tutoriaux. Le bus quittera les hôtels à 8:00 du matin.
50, Boulevard de la Croisette
06400 CANNES
Tel: +33 492 99 70 00
Fax: +33 492 99 70 17
Vous aurez besoin du numéro de votre carte bancaire au moment de
réserver.
simple: 830 FF (petit déjeuner compris)
double: 930 FF (petit déjeuner compris)
38 Rue des Serbes
06400 CANNES
Tel: +33 492 99 79 79
Fax: +33 492 99 79 41
Vous aurez besoin du numéro de votre carte bancaire au moment de
réserver.
simple: 850 FF (petit déjeuner compris)
double: 1020 FF(petit déjeuner compris)
13-15 Rd-Pt Duboys d'Angers
06400 CANNES
TEL: +33 493 39 45 45
FAX: +33 493 38 64 66
simple: 550 FRF (petit déjeuner compris)
double: 700 FRF (petit déjeuner compris)
6 rue de Bone
06400 CANNES
TEL: +33 493 38 79 02
FAX: +33 493 99 07 98
simple: 400 FRF (sans petit déjeuner)
double: 500 FRF (sans petit déjeuner)
1, rue des Orangers
06400 CANNES
TEL: +33 493 39 99 92
FAX: +33 493 68 37 55
simple: 406 FRF (petit déjeuner compris)
double: 512 FRF (petit déjeuner compris)
91 rue Georges Clemenceau
06400 CANNES
TEL: +33 492 98 38 00
FAX: +33 492 98 67 70
simple: 350 FRF (sans petit déjeuner)
double: 500 FRF (sans petit déjeuner)
77 rue d'Antibes
06400 CANNES
simple: 550 FRF (petit déjeuner compris)
double: 700 FRF (petit déjeuner compris)
5 Place de la Gare
06400 CANNES
TEL: +33 493 39 01 17
FAX: +33 493 39 29 57
single: 324 FRF (sans petit déjeuner)
double: 388 FRF (sans petit déjeuner)
Petit déjeuner : 35 FRF
17 Boulevard Marechal Foch
06400 CANNES
TEL: +33 493 39 10 53
FAX: +33 493 38 98 54
simple: 320 FRF (sans petit déjeuner)
double: 380 FRF (sans petit déjeuner)
Petit déjeuner : 35 FRF
5-7 rue Molière
06400 CANNES
TEL: +33 493 38 16 16
FAX: +33 493 68 29 57
simple: 390 FRF (petit déjeuner compris)
double: pas libre
Any specific information request should be made at:
Dany Sergeant
INRIA
2004 route des lucioles - BP93
06902 Sophia Antipolis cedex
FRANCE
Relations Exerieures
Bureau des Colloques
Tel : +33 493.65.77.05
Fax : +33 493.65.79.55
Email : dany.sergeant@sophia.inria.fr
ACM SIGCOMM'97 est composé de 2 jours de tutoriaux et 2 jours 1/2 de session unique. Les tutoriaux auront lieu à l'INRIA, à 15-20 minutes par l'autobus depuis Cannes, et la navette assurera le trajet des hotels aux lieux des tutoriaux. La session unique aura lieu à Cannes, à moins de 15 minutes de marche des hotels.
Vous arriverez à Cannes par voiture, train ou avion.
Voiture : Il y a des panneaux de signalisation dans toute la ville de Cannes pour vous guider jusqu'à la conférence (suivre Palais des Festivals -La Croisette).
Train : La gare SNCF de Cannes est à une distance d'environ 10 minutes des hotels et du lieu de la conférence.
Avion : L'aéroport international est à 40 kilomètres de Cannes. Depuis l'aéroport jusqu'à Cannes, vous avez les choix suivants :
Vous pouvez également consulter la carte de Cannes. Le Palais
des Festivals est un établissement jaune situé aà
la droite du port de Cannes, et à l'extrémité ouest
du boulevard de la Croisette.
Informations Générales
Accès par Internet
L'accès à Internet sera possible durant la conférence.
10 terminaux et 10 branchements Ethernet seront mis à disposition
aux heures d'ouverture du Palais des Festivals.
Pour des raisons de performance, nous pensons autoriser uniquement l'accès
au courrier électronique, ftp et telnet. (et invalider l'accès
au Web.)
L'accès à Internet est mis à votre disposition par MCI.
Secrétariat du Workshop
Les demandes de renseignements relatives à l'organisation doivent être faites auprès de :
Dany Sergeant
INRIA
2004 route des Lucioles
06902 Sophia-Antipolis
FRANCE
Tèl : (33) 493.65.77.05
Fax : (33) 493.65.79.55
Email : dany.sergeant@sophia.inria.fr
Devenez un membre ACM
Comment devenir un membre ACM ?