JUMBO : protocole de routage unicast dans les réseaux ad-hoc

Johanne Cohen, Éric Fleury, Jens GustedtHAL 2000

TL;DR

This paper introduces JUMBO, a proactive routing protocol for ad-hoc wireless networks that leverages a clique decomposition of the network topology. By maintaining a global view of these cliques, JUMBO aims to efficiently route unicast traffic in dynamic environments, addressing the challenges of node mobility and intermittent connectivity.

What Problem Does This Paper Address?

Ad-hoc wireless networks, characterized by their lack of fixed infrastructure and mobile nodes, present significant routing challenges. Nodes must dynamically discover and maintain routes to each other, adapting to constant changes in network topology due to mobility. Traditional wired routing protocols, which rely on stable network structures, are ill-suited for these environments. Existing reactive routing protocols, which discover routes on demand, can introduce latency. This paper addresses the need for a proactive routing protocol that can efficiently manage unicast communication in such dynamic, infrastructure-less networks.

Methods

The core of JUMBO's approach lies in its novel method of modeling the ad-hoc network as a graph and decomposing it into a set of cliques. A clique, in this context, represents a group of nodes that can all communicate directly with each other. The protocol assumes that each node has knowledge of this clique decomposition. Routing is then performed by forwarding messages from one clique to another, with a designated node within each clique responsible for retransmission. This clique-based routing is designed to be more robust to topology changes than traditional link-state routing. The paper also outlines a distributed algorithm for constructing and maintaining this clique decomposition, ensuring that nodes can update their knowledge of the network structure.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Clique Decomposition for Routing: The fundamental idea is to abstract the dynamic network topology into a more manageable structure of cliques. This simplifies routing by focusing on inter-clique communication rather than individual link states.
  • Proactive Routing with Global View: JUMBO is a proactive protocol, meaning it aims to maintain routing information continuously. This is achieved by having nodes maintain a global view of the clique decomposition, allowing them to route messages without the initial discovery latency of reactive protocols.
  • Distributed Clique Maintenance: The paper proposes a distributed algorithm for nodes to collaboratively build and update the clique decomposition. This is crucial for handling the dynamic nature of ad-hoc networks.
  • Adaptability to HIPERLAN: The protocol is specifically designed with HIPERLAN (High Performance Radio Local Area Network) in mind, a standard for wireless networking that shares characteristics with other ad-hoc network scenarios.

Key Results

The paper presents the theoretical framework for the JUMBO protocol and its clique decomposition approach. It defines the properties that a valid clique decomposition must satisfy (union of cliques covers all edges, and the number of cliques is bounded). An algorithm for distributed clique decomposition is described, and it is claimed that this algorithm ensures the decomposition is valid and satisfies the defined properties. The paper does not present quantitative performance results or simulation data, focusing instead on the algorithmic and theoretical underpinnings of the proposed routing strategy.

Limitations and Future Work

The authors acknowledge that the proposed clique decomposition is initially motivated by multicast routing but is adapted for unicast. They explicitly state that further work is needed to determine the performance of their routing algorithm through simulations and by implementing a prototype over IP. The paper also mentions that while flooding is used for distributing clique information, more efficient diffusion techniques could be explored. The complexity of maintaining the clique decomposition in highly dynamic environments and the overhead associated with the proactive nature of the protocol are potential areas for future investigation.

Summary updated

Abstract

National audience
BibTeX
@inproceedings{cohen2000jumbo,
  author = {Johanne Cohen and Éric Fleury and Jens Gustedt},
  title = {{JUMBO : protocole de routage unicast dans les réseaux ad-hoc}},
  booktitle = {HAL},
  year = {2000},
}
Figure