No description available.

Large-scale layer-2 Ethernet networks are needed for important future and current applications and services including: metro Ethernet, wide area Ethernet, data center networks, cyber-physical systems, and large data processing. However Ethernet bridging was designed for small local area networks and suffers scalability and resiliency problems for large networks. I will present the architecture and protocols of ROME, a layer-2 network designed to be backwards compatible with Ethernet and scalable to tens of thousands of switches and millions of end hosts. We first design a scalable greedy routing protocol, Multi-hop Delaunay Triangulation (MDT) routing, for delivery guarantee on any connectivity graph with arbitrary node coordinates. To achieve near-optimal routing path for greedy routing, we then present the first layer-2 virtual positioning protocol, Virtual Position on Delaunay (VPoD). We then design a stateless multicast protocol, to support group communication such as VLAN while improving switch memory scalability. To achieve efficient host discovery, we present a novel distributed hash table, Delaunay DHT (D²HT). ROME also includes routing and host discovery protocols for a hierarchical network. ROME protocols completely eliminate broadcast. Extensive experimental results show that ROME protocols are efficient and scalable to metropolitan size. Furthermore, ROME protocols are highly resilient to network dynamics. The routing latency of ROME is only slightly higher than shortest-path latency. / text

In dynamic P2P networks, nodes join and depart from the system frequently, which partially damages the predefined P2P structure, and impairs the system performance such as basic lookup functionality. Therefore stabilization process has to be done to restore the logical topology. This paper presents an approach to relax the requirement on routing tables to provide provably better stability than fixed structured P2P systems. We propose a relaxed Chord that keeps the O(logN) number of hops for greedy lookup, but it requires less stabilization overhead. It allows a tradeoff between lookup efficiency and structure flexibility without adding any overhead to the system. In the relaxed routing structure, each routing entry ("finger") of the node is allowed to vary within a set of values. Each node only needs to keep a certain number of fingers that point to nodes in its anchor set. This relaxation reduces the burden of state management of the node. The relaxed routing scheme provides an alternative structure other than randomized P2P and deterministic P2P, by relaxing on finger selection. It provides good flexibility and therefore extends the system functioning time. / Singapore-MIT Alliance (SMA)

This thesis describes and develops two planarization algorithms for geographic routing and a geographic routing protocol for mobile ad hoc and sensor networks. As all nodes are mobile and there is no fixed infrastructure, the design of routing protocols is one of the most challenging issues in mobile ad hoc and sensor networks. In recent years, greedyface- greedy (GFG) geographic routing protocols have been widely used, which need nodes to construct planar graphs as the underlying graphs for face routing. Two kinds of planarization algorithms have been developed, idealized and realistic planarization algorithms, respectively. The idealized planarization algorithms make the ideal assumption that the original network graph is a unit-disk graph (UDG). On the other hand, the realistic planarization algorithms do not need the original network to be a UDG. We propose an idealized planarization algorithm, which constructs an Edge Constrained Localized Delaunay graph (ECLDel). Compared to the existing planarized localized Delaunay graph [42], the construction of an ECLDel graph is far simpler, which reduces the communication cost and saves the network bandwidth. We propose a Pre-Processed Cross Link Detection Protocol (PPCLDP), which generates a planar spanning subgraph of the original network graph in realistic environments with obstacles. The proposed PPCLDP outperforms the existing Cross Link Detection Protocol [32] with much lower communication cost and better convergence time. In GFG routing protocols, greedy routing may fail at concave nodes, in which case, face routing is applied to recover from the greedy routing failure. This may cause extra hops in routing in networks containing voids. We propose a Hill-Area-Restricted (HAR) routing protocol, which avoids the extra hops taken in the original GFG routing. Compared to the existing Node Elevation Ad hoc Routing [4], the proposed HAR guarantees the packet delivery and decreases the communication cost greatly.

Le routage dans Internet est basé sur des tables dites de routage, formées de blocs d’adresses IP. Cependant, la construction et la maintenance de telles tables de routage nécessitent l’utilisation de protocoles complexes qui ne passent pas à l’échelle en termes de mémoire et d’utilisation CPU. De plus, l’expérience montre que le plan d’adressage IP est insuffisant, car la sémantique d’une adresse IP est à la fois un identificateur et un localisateur. Dans nos travaux, nous proposons un système de réseau recouvrant pair-à-pair libre de toute contrainte topologique et utilisant des coordonnées virtuelles prises dans le plan hyperbolique nommé CLOAK (Covering Layer Of Abstract Knowledge en anglais). Les schémas de routages locaux basés sur des coordonnées virtuelles extraites du plan hyperbolique ont suscité un intérêt considérable ces dernières années. Dans cette thèse, nous proposons une nouvelle approche pour saisir le potentiel de la géométrie hyperbolique. L’objectif est de construire un système extensible et fiable pour créer et gérer des réseaux recouvrants dans Internet. Le système est implémenté comme une infrastructure pair-à-pair structuré basé sur les protocoles de la couche transport entre les pairs. Quant à l’organisation des données dans l’espace virtuel, nous employons la réplication pour améliorer la disponibilité et l’accessibilité des objets de l’overlay potentiellement instable. Nous avons implémenté et évalué différentes méthodes de réplication (réplication radiale, réplication circulaire).A l’aide de simulations, nous évaluons notre proposition à travers un certain nombre de métriques et nous montrons que les réseaux recouvrants pair-à-pair basés sur la géométrie hyperbolique ont de bonnes performances par rapport aux autres DHT existantes tout en introduisant flexibilité et robustesse dans les réseaux recouvrants dynamiques. / Internet routing is based on forwarding tables populated by blocks of IP addresses. However, the construction and maintenance of such tables require the use of complex routing protocols that are typically not scalable in terms of memory and CPU usage. Moreover, experience shows that the IP addressing plane is insufficient due to the semantic of an IPaddress being both an identifier and a locator. In this paper, we propose a P2P overlay system of freed topology and using virtual coordinates taken from the hyperbolic plane named CLOAK(Covering Layer Of Abstract Knowledge en anglais). Local knowledge routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years. In this thesis we propose a new approach for seizing the power of the hyperbolic geometry. We aim at building a scalable and reliable system for creating and managing overlay networks over the Internet. The system is implemented as a structured peer-to-peer infrastructure based on the transport layer connections between the peers. Concerning data organisation in the virtual space, we use replication strategy for improve overlay objects disponibilty and accessibility in context potentially unstable. We have implemented and evaluated various replication methods (radial replication, circular replication). Using simulations, we assess our proposal across a certain number of metric and show that overlay Peer-to-Peer network based on the hyperbolic geometry have good performances in comparison with other existent DHT while introducing suppleness and robustness in the dynamic overlay network.