Table de routage | EPFL Graph Search

Une table de routage est une structure de données utilisée par un routeur ou un ordinateur en réseau et qui associe des préfixes à des moyens d'acheminer les paquets vers leur destination. C'est un élément central du routage IP. Contenu et fonctionnement La table de routage contient :

les adresses du routeur lui-même ;
les adresses des sous-réseaux auxquels le routeur est directement connecté ;
les routes statiques, c'est-à-dire configurées explicitement par l'administrateur ;
les routes dynamiques, apprises par des protocoles de routage dynamique comme BGP, OSPF, IS-IS, etc. ;
une route par défaut.

Quand plusieurs routes sont possibles, la route la plus spécifique sera utilisée, c'est-à-dire celle qui aura le préfixe le plus long. Si plusieurs routes avec le même préfixe existent, l'arbitrage a lieu en fonction du type de route : les routes directement connectées auront la priorité sur les autres, les routes statiques et dynamiques sont départagées par une dist

Routing in large-scale buses ad hoc networks

Michel Sède

A Disruption-Tolerant Network (DTN) attempts to route packets between nodes that are temporarily connected. Difficulty in such networks is that nodes have no information about the network status and contact opportunities. The situation is different in public bus networks because the movement of buses exhibits some regularity so that routing in a deterministic way is possible. Many algorithms use a Contacts Oracle that provides the exact meeting times and durations between all nodes. However, in a real vehicular environment, an oracle is not always accurate, and deterministic routing gives poor results. In this paper, we present BLER, a routing algorithm that achieves effective routing in a buses environment. BLER, compared to other algorithms, performs routing at bus line level instead of bus level; it uses specific bus lines information to achieve good performances. We evaluate BLER on real traces of the bus network of Shanghai, and compare it to other routing algorithms. Performances provide good results for this kind of DTNs.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2008

Scalable routing protocols with applications to mobility

Ljubica Blazevic

In this thesis we study two routing problems related to mobility. The first problem concerns scalable multicast routing when there is a large number of multicast groups with a small number of receivers. Existing dense and sparse mode routing protocols have the following problems when the number of groups is large, but the groups are small: (1) high overhead in control traffic (dense mode), (2) poor utilization of backbone links and (3) complexity of management of single core routers (sparse mode). Our solution to this problem is the Distributed Core Multicast (DCM) routing protocol. DCM is an extension of the core-based tree approach and its architecture is based on several core routers per multicast groups. We explain the objectives achieved with DCM: (1) avoiding state information in backbone routers, (2) avoiding triangular routing across expensive backbone links, (3) scaling well with the number of multicast groups. DCM can be applied to support host micromobility in a large single Internet domain network, where every mobile host is assigned a multicast address in a domain it visits. The advantages of the multicasting-based approach for supporting host mobility are low latency and minimal disruption during handover. The second problem studied in this thesis concerns scalable routing in a large scale mobile ad hoc network. Ad hoc networks have gained increasing popularity in recent years because of their ease of deployment. No wired base station or infrastructure is needed, and mobile nodes communicate with each other using multi-hop wireless links. In ad hoc networks, routing protocols are challenged by the establishment of and the maintenance of multihop routes in the face of mobility, bandwidth limitation and power constraints. Routing protocols that rely on state concerning all links on the network, or all links on a route between a source and a destination result in poor scaling properties in larger mobile ad hoc networks. Position-based routing protocols are better suited for large mobile ad hoc networks. These protocols use the positions of nearby nodes and of packet's destination to make the packet forwarding decisions. We present a scalable routing protocol for a large mobile ad hoc network that is called terminode network. We call the nodes terminodes because they act as network nodes and terminals at the same time. Our routing scheme is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TRR is activated when the destination is remote and it uses the location of the destination obtained either via location management or by location tracking. TLR acts when the packet gets close to the destination and it uses routing tables that are built by nodes for close terminodes. The use of TRR results in a scalable solution that reduces dependence on the intermediate systems, while TLR allows to increase the probability of reaching the destination, even when it has moved considerably from the location that was known at the source. We use simulations to demonstrate terminode routing's scalability in different sized mobile ad hoc networks.

EPFL2002

Routing for Wireless Sensor Networks: From Collection to Event-Triggered Applications

Daniel Camilo Rojas Quirós

Wireless Sensor Networks (WSNs) are collections of sensing devices using wireless communication to exchange data. In the past decades, steep advancements in the areas of microelectronics and communication systems have driven an explosive growth in the deployment of WSNs. Novel WSN applications have penetrated multiple areas, from monitoring the structural stability of historic buildings, to tracking animals in order to understand their behavior, or monitoring humans' health. The need to convey data from increasingly complex applications in a reliable and cost-effective manner translates into stringent performance requirements for the underlying WSNs. In the frame of this thesis, we have focused on developing routing protocols for multi-hop WSNs, that significantly improve their reliability, energy consumption and latency. Acknowledging the need for application-specific trade-offs, we have split our contribution into two parts. Part 1 focuses on collection protocols, catering to applications with high reliability and energy efficiency constraints, while the protocols developed in part 2 are subject to an additional bounded latency constraint. The two mechanisms introduced in the first part, WiseNE and Rep, enable the use of composite metrics, and thus significantly improve the link estimation accuracy and transmission reliability, at an energy expense far lower than the one achieved in previous proposals. The novel beaconing scheme WiseNE enables the energy-efficient addition of the RSSI (Received Signal Strength Indication) and LQI (Link Quality Indication) metrics to the link quality estimate by decoupling the sampling and exploration periods of each mote. This decoupling allows the use of the Trickle Algorithm, a key driver of protocols' energy efficiency, in conjunction with composite metrics. WiseNE has been applied to the Triangle Metric and validated in an online deployment. The section continues by introducing Rep, a novel sampling mechanism that leverages the packet repetitions already present in low-power preamble-sampling MAC protocols in order to improve the WSN energy consumption by one order of magnitude. WiseNE, Rep and the novel PRSSI (Penalized RSSI, a combination of PRR and RSSI) composite metric have been validated in a real smart city deployment. Part 2 introduces two mechanisms that were developed in the frame of the WiseSkin project (an initiative aimed at designing highly sensitive artificial skin for human limb prostheses), and are generally applicable to the domain of cyber-physical systems. It starts with Glossy-W, a protocol that leverages the superior energy-latency trade-off of flooding schemes based on concurrent transmissions. Glossy-W ensures the stringent synchronization requirements necessary for robust flooding, irrespective of the number of motes simultaneously reporting an event. Part 2 also introduces SCS (Synchronized Channel Sampling), a novel mechanism capable of reducing the power required for periodic polling, while maintaining the event detection reliability, and enhancing the network coexistence. The testbed experiments performed show that SCS manages to reduce the energy consumption of the state-of-the-art protocol Back-to-Back Robust Flooding by over one third, while maintaining an equivalent reliability, and remaining compatible with simultaneous event detection. SCS' benefits can be extended to the entire family of state-of-the-art protocols relying on concurrent transmissions.

EPFL2018