Introduction
OSPF (Open Shortest Path First) is one of the main intra-domain routing protocols in the Internet. OSPF4MANET is a research effort, extending OSPF in a way such that it can be used also in networks exhibiting a more dynamic topology than traditional wired networks. This includes, in particular, OSPF Autonomous Systems containing areas which look like wireless mesh networks, mobile ad hoc networks — with the general case being more complex internetworks containing both wired and wireless mesh networks.
Wired/wireless internetwork
A MANET interface for OSPF
OSPF4MANET focuses on the design, development and performance evaluation of a “MANET interface” for wireless networks, to be added to the other interfaces defined in the specifications of OSPF (OSPFv2 in RFC2328, OSPFv3 for IPv6 in RFC5340) for wired networks. The resulting extended version of OSPF is thus expected to operate in a compound autonomous system, federating both wired and wireless networks.
OSPF basics
As explicitly stated in its name, OSPF is designed to route data packets over the “Shortest Path First“, i.e., the route with least cost (according to a certain metric) available between source to destination in a given network topology.
A link-state routing protocol, OSPF requires that all routers in a network hold a complete, consistent view of the network topology. Based on this topology knowledge, routers are able to compute network-wide optimal routes to all possible destinations, and thus to take consistent forwarding decisions for any received data packet.
OSPF ensures consistency of topology information held by all routers by enforcing pair-wise synchronization between routers: two routers having synchronized their link-state database, and updating subsequently changes to the other, are said to be adjacent — adjacencies are thus the links over which link-state updates are sent.
OSPF operation thus can be summarized in two main principles:
- Control traffic (link-state advertisements, LSAs) is sent over synchronized links (adjacencies).
- User traffic (data packets) is sent over shortest paths, computed among synchronized links.
OSPF4MANET has the double objective of preserving these two core principles of OSPF while adapting the protocol operation to the specific conditions of wireless mesh and mobile ad hoc networks. Other alternatives have been explored, designed, implemented and evaluated as complementary proposals.
OSPF sends user traffic over shortest paths, and control traffic over synchronized links — OSPF4MANET preserves both properties in MANET scenarios
Techniques for the OSPF extension for MANETs
The MANET extension of OSPF relies on the optimization of information exchange and the use of reduced network overlays to improve the operations related to link-state routing: (i) neighbor sensing, (ii) LSA flooding, (iii) adjacency synchronization, and (iv) local topology description for shortest path tree computation. Different techniques for decentralized overlay construction and maintenance are proposed, evaluated and implemented in the MANET extension for OSPF for the different link-state operations:
- Multi-Point Relays (MPRs), in which a router selects among its 1-hop neighbors a subset of relays, able to reach all its 2-hop neighbors, based on the neighborhood information collected via Hello exchange.
- Synchronized Link Overlay Triangular (SLOT), in which pairs of routers agree to include the link between them in a distributed overlay for link-state synchronization purposes, based on the neighborhood information collected via Hello exchange. This overlay is expected to connect all routers in the network by reducing the number of involved links and the rate of link change.
SLOT overlay (blue) in a wireless mesh network (red for links).
- Smart Peering (SP), specified in RFC5820, in which routers synchronize the link between them if a global path of synchronized links between them does not (yet) exist. This technique relies on global topology information stored in the network-wide link-state database.
Some of these techniques are inspired in mechanisms used and tested in the Optimized Link State Routing protocol (OLSR – RFC3626 and OLSRv2 – RFC7181). The combination of these techniques for the different link-state operations has led to the design and analysis of variants of the MANET extension of OSPF, and for exploration of different trade-offs between link-state control traffic and quality of computed data paths, resulting in the design and standardization of MPR-OSPF, an extension to OSPFv3.
MPR-OSPF
MPR-OSPF is the extension of OSPF for MANET that preserves the two core principles of OSPF routing in wireless mesh scenarios. It is standardized in RFC5449. MPR-OSPF uses the notion of Multi-Point Relaying for optimizing the main OSPF tasks over MANETs. Based on the 2-hop neighborhood information collected via Hello messages, a router selects (i) a set of Flooding MPRs, expected to reach every 2-hop neighbor of the router, and (ii) a set of Path MPRs, expected to include neighbors involved in the shortest paths from every 2-hop neighborhood of the router to the router itself. These two sets are the same for the hop count metric, and may differ if other metrics are used.
- Adjacencies. A node becomes adjacent to its multi-point relays (Flooding MPRs and Path MPRs) and its MPR selectors (i.e., those neighbors that selected the node as Flooding or Path MPR). Adjacency selection is persistent, meaning that once two neighboring nodes have been synchronized, the adjacency is maintained as far as the nodes remain neighbors.
- Flooding. A router only forwards LSAs coming from Flooding MPR selectors, and only sends LSA acknowledgements if the LSA was sent by an adjacent neighbor.
- Topology description. A router advertises Path MPRs and Path MPR selectors in its Router-LSAs. Both are adjacent neighbors according to the adjacency rule; advertising them in Router-LSAs is thus compliant with OSPFv3 specification (RFC5340).
- Neighbor sensing. Hello messages report, for every neighbor of the sending router, its status as Flooding MPR, its status as Path MPR and the cost of node-to-neighbor and neighbor-to-node links.
MPR-OSPF is the MANET extension of OSPF that reduces control traffic (flooding, adjacency-forming, topology description) while preserving the core principles of OSPF operation
Other MANET extensions of OSPF
If the two core principles of OSPF routing are not respected when operating over MANETs, other configurations become possible. The combination of other overlay generation techniques lead to different MANET extensions of OSPF that explore additional trade-offs between optimality of user data paths, reduction of control traffic and preservation of OSPF legacy.
- SLOT-OSPF explores total decoupling of adjacency forming (based on the SLOT technique) from flooding and topology description (based on Flooding MPRs and Path MPRs, respectively). This allows to reduce substantially the overall control traffic, at the expense of seriously degrading the quality of user traffic routing.
- MPR+SP also decouples adjacencies from flooding/topology description. However, although it does not synchronize all reported links, it reports in Router-LSAs all adjacent links. MPR+SP thus uses Smart Peering for adjacency-forming purposes, performs flooding over Flooding MPRs (computed over the Smart Peering overlay) and reports both Path MPRs and Smart Peering neighbors in Router-LSAs. Use of SP reduces to the minimum the control traffic due to link-state synchronization. Inclusion of Path MPRs ensures that theoretical shortest paths are included in the reported link-state, and inclusion of adjacent Smart Peering links ensures that synchronized links are taken into account in shortest path computation.
How to extend OSPF? What to preserve, what to remove?
Evaluation of the different configurations and extensions, MPR-OSPF (RFC5449), the others (MPR+SP, SLOT-OSPF), together with other IETF standards (e.g. OR/SP, RFC5820), allow to examine the impact of the core principles of OSPF (P1–shortest, synchronized paths for user traffic, P2–synchronized links for control traffic) in routing performance in mobile ad hoc networks. Evaluation of these variants and MPR-OSPF allows to observe that:
- Ensuring that reported links allow to compute “shortest paths” computation for user traffic proves beneficial,
- Synchronization of all reported paths (in Router-LSAs) is costly and not necessarily effective,
- Reporting (in Router-LSAs) synchronized links has a positive impact in routing quality.
Implementation
- OSPFv3 Extension for Wireless Ad-hoc Networks. Source code (C++) and corresponding documentation are publicly available at the INRIA GForge repository.
Related Publications
Cordero, Juan Antonio; Yi, Jiazi; Clausen, Thomas; Baccelli, Emmanuel
Enabling Multihop Communication in Spontaneous Wireless Networks Book Chapter
In: Haddadi, Hamed; Bonaventure, Olivier (Ed.): Recent Advances in Networking, Chapter 9, pp. 413-457, ACM SIGCOMM, 2013.
@inbook{Cordero2013,
title = {Enabling Multihop Communication in Spontaneous Wireless Networks},
author = {Juan Antonio Cordero and Jiazi Yi and Thomas Clausen and Emmanuel Baccelli},
editor = {Hamed Haddadi and Olivier Bonaventure},
url = {http://sigcomm.org/education/ebook/SIGCOMMeBook2013v1_chapter9.pdf},
year = {2013},
date = {2013-08-01},
booktitle = {Recent Advances in Networking},
pages = {413-457},
publisher = {ACM SIGCOMM},
chapter = {9},
keywords = {},
pubstate = {published},
tppubtype = {inbook}
}
Cordero, Juan Antonio; Philipp, Matias; Baccelli, Emmanuel
Routing across Wired and Wireless Mesh Networks: Experimental Compound Internetworking with OSPF Proceedings Article
In: Proceedings of the 8th IEEE International Wireless Communications and Mobile Computing Conference (WCMC 2012), 2012.
@inproceedings{Cordero2012b,
title = {Routing across Wired and Wireless Mesh Networks: Experimental Compound Internetworking with OSPF},
author = {Juan Antonio Cordero and Matias Philipp and Emmanuel Baccelli},
url = {https://www.researchgate.net/publication/236883800_Routing_Across_Wired_and_Wireless_Mesh_Networks_Experimental_Compound_Internetworking_with_OSPF},
doi = {10.1109/IWCMC.2012.6314296},
year = {2012},
date = {2012-08-01},
publisher = {Proceedings of the 8th IEEE International Wireless Communications and Mobile Computing Conference (WCMC 2012)},
abstract = {As wireless mesh networks are deployed, a new concept emerges: compound internetworks, i.e., internetworks that contain both wired networks and wireless mesh networks. Routing is one of the key challenges that arises in compound internetworks: indeed, while specific routing protocols are typically used for wired networks on one hand, and for wireless mesh networks on the other hand, it has been observed that operating a single routing protocol to manage a compound internetwork as a whole brings several advantages. In this realm, the IETF has thus standardized protocol extensions to Open Shortest Path First (OSPF, the routing protocol used by more than 50 % of the wired routers in today's Internet), enabling OSPF to operate simultaneously on wired networks, and on wireless mesh or moderately mobile ad hoc networks (MANETs). This paper evaluates the performance of OSPF coupled with such a protocol extension for MANETs on an experimental compound internetwork testbed. This paper reports on experiments carried out with OSPF operating simul-taneously over Ethernet and 802.11b. Despite the limitations of the testbed, these experiments provide both a proof-of-concept and complementary results compared to prior work in the domain, which was mostly based on simulations, and focused on wireless ad hoc network scenarios only.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
As wireless mesh networks are deployed, a new concept emerges: compound internetworks, i.e., internetworks that contain both wired networks and wireless mesh networks. Routing is one of the key challenges that arises in compound internetworks: indeed, while specific routing protocols are typically used for wired networks on one hand, and for wireless mesh networks on the other hand, it has been observed that operating a single routing protocol to manage a compound internetwork as a whole brings several advantages. In this realm, the IETF has thus standardized protocol extensions to Open Shortest Path First (OSPF, the routing protocol used by more than 50 % of the wired routers in today's Internet), enabling OSPF to operate simultaneously on wired networks, and on wireless mesh or moderately mobile ad hoc networks (MANETs). This paper evaluates the performance of OSPF coupled with such a protocol extension for MANETs on an experimental compound internetwork testbed. This paper reports on experiments carried out with OSPF operating simul-taneously over Ethernet and 802.11b. Despite the limitations of the testbed, these experiments provide both a proof-of-concept and complementary results compared to prior work in the domain, which was mostly based on simulations, and focused on wireless ad hoc network scenarios only.
Cordero, Juan Antonio; Jacquet, Philippe; Baccelli, Emmanuel
Impact of Jitter-based Techniques on Flooding over Wireless Ad hoc Networks: Model and Analysis Proceedings Article
In: pp. 2059-2067, IEEE Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM 2012)., Orlando, FI, United States., 2012, ISSN: 0743-166X.
@inproceedings{Cordero2012,
title = {Impact of Jitter-based Techniques on Flooding over Wireless Ad hoc Networks: Model and Analysis},
author = {Juan Antonio Cordero and Philippe Jacquet and Emmanuel Baccelli},
url = {https://www.researchgate.net/publication/236883781_Impact_of_Jitter-based_Techniques_on_Flooding_over_Wireless_Ad_hoc_Networks_Model_and_Analysis},
doi = {10.1109/INFCOM.2012.6195587},
issn = {0743-166X},
year = {2012},
date = {2012-03-25},
pages = {2059-2067},
publisher = {Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM 2012).},
address = {Orlando, FI, United States.},
organization = {IEEE},
abstract = {Jitter is used in wireless ad hoc networks to reduce the number of packet collisions and the number of transmissions. This is done by scheduling random back-off for each packet to be transmitted and by piggybacking multiple packets in a single transmission. This technique has been standardized by the IETF in RFC 5148. This paper investigates on the impact of the standardized jitter mechanism on network-wide packet dissemination – i.e. flooding, an important component for many protocols used today. A novel analytical model is introduced, capturing standard jitter traits. From this model is derived accurate characterization of the effects of jittering on flooding performance, including the additional delay for flooded packets on each traversed network interface, the reduction of the number of transmissions over each network interface, and the increased length of transmissions, depending on jitter parameters. This paper also presents an analysis of the use of jitter in practice, over an 802.11 wireless link layer based on CSMA. The analytical results are then validated via statistical discrete event simulations. The paper thus provides a comprehensive overview of the impact of jittering in wireless ad hoc networks.
},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Jitter is used in wireless ad hoc networks to reduce the number of packet collisions and the number of transmissions. This is done by scheduling random back-off for each packet to be transmitted and by piggybacking multiple packets in a single transmission. This technique has been standardized by the IETF in RFC 5148. This paper investigates on the impact of the standardized jitter mechanism on network-wide packet dissemination – i.e. flooding, an important component for many protocols used today. A novel analytical model is introduced, capturing standard jitter traits. From this model is derived accurate characterization of the effects of jittering on flooding performance, including the additional delay for flooded packets on each traversed network interface, the reduction of the number of transmissions over each network interface, and the increased length of transmissions, depending on jitter parameters. This paper also presents an analysis of the use of jitter in practice, over an 802.11 wireless link layer based on CSMA. The analytical results are then validated via statistical discrete event simulations. The paper thus provides a comprehensive overview of the impact of jittering in wireless ad hoc networks.
Cordero, Juan Antonio; Baccelli, Emmanuel; Jacquet, Philippe; Clausen, Thomas
Wired / Wireless Compound Networking Book Chapter
In: Wang, Xin (Ed.): Mobile Ad-Hoc Networks: Applications, Chapter 16, InTech, 2011, ISBN: 978-953-307-416-0.
@inbook{Cordero2011,
title = {Wired / Wireless Compound Networking},
author = {Juan Antonio Cordero and Emmanuel Baccelli and Philippe Jacquet and Thomas Clausen},
editor = {Xin Wang},
url = {www.intechopen.com/download/pdf/12891},
doi = {10.5772/882},
isbn = {978-953-307-416-0},
year = {2011},
date = {2011-01-30},
booktitle = {Mobile Ad-Hoc Networks: Applications},
publisher = {InTech},
chapter = {16},
keywords = {},
pubstate = {published},
tppubtype = {inbook}
}
Cordero, Juan Antonio; Clausen, Thomas; Baccelli, Emmanuel
MPR+SP: Towards a Unified MPR-based MANET Extension for OSPF Proceedings Article
In: Hawaii International Conference on System Sciences, 2011.
@inproceedings{Fuertes2011,
title = {MPR+SP: Towards a Unified MPR-based MANET Extension for OSPF},
author = {Juan Antonio Cordero and Thomas Clausen and Emmanuel Baccelli},
url = {http://www.thomasclausen.net/wp-content/uploads/2015/12/2011-HICSS-MPRSP-Towards-a-Unified-MPR-based-MANET-Extension-for-OSPF.pdf},
doi = {10.1109/HICSS.2011.313},
year = {2011},
date = {2011-01-01},
publisher = {Hawaii International Conference on System Sciences},
abstract = {Heterogeneous networks combining both wired and wireless components – fixed routers as well as mobile routers – emerge as wireless mesh networks are being deployed. Such heterogeneity is bound to become more and more present in the near future as mobile ad hoc networking becomes a reality. While it is possible to cope with heterogeneity by employing different routing protocols for the fixed / wired part and for the wireless / ad hoc part of the network, this may lead to sub-optimal performance, e.g. by way of longer routing paths due to these routing protocols sharing prefixes and ”connecting” the network only at distinct gateways between the two routing domains. Thus, the establishment of a single unified routing domain, and the use of a single routing protocol, for such heterogeneous networks is desired. OSPF is a natural candidate for this task, due to its wide deployment, its modularity and its similarity with the popular ad hoc routing protocol OLSR. Multiple OSPF extensions for MANETs have therefore been specified by the IETF. This paper introduces a novel OSPF extension for operation on ad hoc networks, MPRSP, and compares it with the existing OSPF extensions via simulations, which show that MPR+SP outperforms prior art.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Heterogeneous networks combining both wired and wireless components – fixed routers as well as mobile routers – emerge as wireless mesh networks are being deployed. Such heterogeneity is bound to become more and more present in the near future as mobile ad hoc networking becomes a reality. While it is possible to cope with heterogeneity by employing different routing protocols for the fixed / wired part and for the wireless / ad hoc part of the network, this may lead to sub-optimal performance, e.g. by way of longer routing paths due to these routing protocols sharing prefixes and ”connecting” the network only at distinct gateways between the two routing domains. Thus, the establishment of a single unified routing domain, and the use of a single routing protocol, for such heterogeneous networks is desired. OSPF is a natural candidate for this task, due to its wide deployment, its modularity and its similarity with the popular ad hoc routing protocol OLSR. Multiple OSPF extensions for MANETs have therefore been specified by the IETF. This paper introduces a novel OSPF extension for operation on ad hoc networks, MPRSP, and compares it with the existing OSPF extensions via simulations, which show that MPR+SP outperforms prior art.
Baccelli, Emmanuel; Cordero, Juan Antonio; Jacquet, Philippe
Optimization of Critical Data Synchronization via Link Overlay RNG in Mobile Ad Hoc Networks Proceedings Article
In: pp. 402-411, IEEE Proceedings of the 7th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS’2010)., San Francisco, CA, United States., 2010, ISSN: 2155-6806.
@inproceedings{Baccelli2010b,
title = {Optimization of Critical Data Synchronization via Link Overlay RNG in Mobile Ad Hoc Networks},
author = {Emmanuel Baccelli and Juan Antonio Cordero and Philippe Jacquet},
url = {https://www.researchgate.net/publication/224204276_Optimization_of_Critical_Data_Synchronization_via_Link_Overlay_RNG_in_Mobile_Ad_Hoc_Networks},
doi = {10.1109/MASS.2010.5663945},
issn = {2155-6806},
year = {2010},
date = {2010-11-01},
pages = {402-411},
publisher = {Proceedings of the 7th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS’2010).},
address = {San Francisco, CA, United States.},
organization = {IEEE},
abstract = {In practice, ad hoc networks are still too unreliable for standard mobile and vehicular communications. It is thus important to complement current protocols in this context, with schemes guaranteeing the exchange of critical data when needed. A promising approach in this realm is to use an overlay subgraph, over which critical messages are exchanged and acknowledged in a peer to peer fashion. Overlay nodes' local databases remain thus synchronized over time, at least concerning critical data. This paper elaborates on the problem of performance, related to the discovery and maintenance of such overlay networks in a mobile ad hoc context. We analyze SLOT, an overlay selected based on a Relative Neighbour Graph (RNG) scheme. We then apply SLOT to a standard IP protocol: OSPF, a popular routing protocol which has recently been extended, with RFC 5449 and RFC 5614, to work also on mobile ad hoc networks, and which makes use of a similar overlay synchronization subgraph. This paper compares the performance of these existing OSPF mechanisms with that of SLOT-OSPF, a novel OSPF extension for mobile ad hoc networks using SLOT. Simulations show that SLOT-OSPF produces drastically less control traffic than RFC 5449 or RFC 5614, allowing SLOT-OSPF to function correctly while the other existing approaches stall, when the number of routers in the domain is large.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In practice, ad hoc networks are still too unreliable for standard mobile and vehicular communications. It is thus important to complement current protocols in this context, with schemes guaranteeing the exchange of critical data when needed. A promising approach in this realm is to use an overlay subgraph, over which critical messages are exchanged and acknowledged in a peer to peer fashion. Overlay nodes' local databases remain thus synchronized over time, at least concerning critical data. This paper elaborates on the problem of performance, related to the discovery and maintenance of such overlay networks in a mobile ad hoc context. We analyze SLOT, an overlay selected based on a Relative Neighbour Graph (RNG) scheme. We then apply SLOT to a standard IP protocol: OSPF, a popular routing protocol which has recently been extended, with RFC 5449 and RFC 5614, to work also on mobile ad hoc networks, and which makes use of a similar overlay synchronization subgraph. This paper compares the performance of these existing OSPF mechanisms with that of SLOT-OSPF, a novel OSPF extension for mobile ad hoc networks using SLOT. Simulations show that SLOT-OSPF produces drastically less control traffic than RFC 5449 or RFC 5614, allowing SLOT-OSPF to function correctly while the other existing approaches stall, when the number of routers in the domain is large.
Cordero, Juan Antonio
Adjacency Persistency in OSPF MANET Proceedings Article
In: Proceedings of the 4th IET China-Ireland International Conference on Information and Communication Technologies (CIICT’2010)., 2010.
@inproceedings{Cordero2010,
title = {Adjacency Persistency in OSPF MANET},
author = {Juan Antonio Cordero},
url = {https://www.researchgate.net/publication/46388530_Adjacency_Persistency_in_OSPF_MANET},
year = {2010},
date = {2010-10-01},
publisher = {Proceedings of the 4th IET China-Ireland International Conference on Information and Communication Technologies (CIICT’2010).},
abstract = {Link-state routing remains as one of the most challenging issues in ad hoc networking, due to the special conditions and requirements that hold in such networks, which cannot be handled by classical routing protocols. In the last decade, several efforts have been deployed either to design new routing solutions adapted to ad hoc conditions, either to extend existing solutions for wired networks to the domain of wireless mobile scenarios. This paper elaborates on the latter alternative, focusing on the standard OSPF MANET extension RFC 5449. It analyzes the impact and interest of the persistency principle to the main OSPF MANET operations, in particular the adjacency synchronization and the other operations that relate to it (flooding and route construction). The presented results show that such persistent approach is appropriate for managing adjacencies in the context of RFC 5449, and significant improvements might be achieved by extending the persistent principle into the topology selection mechanism.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Link-state routing remains as one of the most challenging issues in ad hoc networking, due to the special conditions and requirements that hold in such networks, which cannot be handled by classical routing protocols. In the last decade, several efforts have been deployed either to design new routing solutions adapted to ad hoc conditions, either to extend existing solutions for wired networks to the domain of wireless mobile scenarios. This paper elaborates on the latter alternative, focusing on the standard OSPF MANET extension RFC 5449. It analyzes the impact and interest of the persistency principle to the main OSPF MANET operations, in particular the adjacency synchronization and the other operations that relate to it (flooding and route construction). The presented results show that such persistent approach is appropriate for managing adjacencies in the context of RFC 5449, and significant improvements might be achieved by extending the persistent principle into the topology selection mechanism.
Cordero, Juan Antonio; Baccelli, Emmanuel; Jacquet, Philippe
OSPF over Multi-Hop Ad Hoc Wireless Communications Journal Article
In: International Journal of Computer Networks and Communications , vol. 2, no. 5, pp. 38-56, 2010, ISSN: 0975-2293.
@article{Fuertes2010-IJCNC,
title = {OSPF over Multi-Hop Ad Hoc Wireless Communications},
author = {Juan Antonio Cordero and Emmanuel Baccelli and Philippe Jacquet},
url = {http://airccse.org/journal/cnc/0910ijcnc03.pdf},
issn = {0975-2293},
year = {2010},
date = {2010-09-01},
journal = {International Journal of Computer Networks and Communications },
volume = {2},
number = {5},
pages = {38-56},
abstract = {Efficient OSPF (Open Shortest Path First) operation on multi-hop ad hoc wireless networks has become desirable, as wireless community mesh networks and vehicular networks emerge using OLSR (Optimized Link State Routing), a link state MANET routing protocol similar to OSPF in many aspects. OSPF is already extensively deployed and well known in wired IP networks, and could provide simple, seamless unification of wired and wireless IP networking routing-wise, if extended to operate efficiently on ad hoc networks. The IETF has thus proposed three different MANET extensions to the OSPF protocol, allowing heterogeneous networks encompassing both wired and wireless routers, which may self-organize as multi-hop wireless subnetworks, and be mobile. Two of these extensions are based on techniques derived from multi-point relaying (MPR). In the following, we compare and analyze these two extensions and we propose a unique, merged approach which out-performs the existing extensions.
},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Efficient OSPF (Open Shortest Path First) operation on multi-hop ad hoc wireless networks has become desirable, as wireless community mesh networks and vehicular networks emerge using OLSR (Optimized Link State Routing), a link state MANET routing protocol similar to OSPF in many aspects. OSPF is already extensively deployed and well known in wired IP networks, and could provide simple, seamless unification of wired and wireless IP networking routing-wise, if extended to operate efficiently on ad hoc networks. The IETF has thus proposed three different MANET extensions to the OSPF protocol, allowing heterogeneous networks encompassing both wired and wireless routers, which may self-organize as multi-hop wireless subnetworks, and be mobile. Two of these extensions are based on techniques derived from multi-point relaying (MPR). In the following, we compare and analyze these two extensions and we propose a unique, merged approach which out-performs the existing extensions.
Cordero, Juan Antonio
MPR-based Pruning Techniques for Shortest Path Tree Computation Proceedings Article
In: Proceedings of the 18th IEEE International Conference on Software Telecommunications and Computer Networks (SoftCom)., 2010.
@inproceedings{Cordero2010b,
title = {MPR-based Pruning Techniques for Shortest Path Tree Computation},
author = {Juan Antonio Cordero},
url = {https://www.researchgate.net/publication/224190067_MPR-based_pruning_techniques_for_Shortest_Path_Tree_computation},
year = {2010},
date = {2010-09-01},
publisher = {Proceedings of the 18th IEEE International Conference on Software Telecommunications and Computer Networks (SoftCom).},
abstract = {Multi-Point Relaying (MPR) is a well-known relay pruning algorithm that has proved to be useful for efficient dissemination in Mobile Ad hoc Networks (MANETs). But this technique may be useful for other tasks in MANET link-state routing as well. In particular, the approach is attractive for the selection of topology information to be flooded across the network. Requirements for such topology selection are however different from those applying for efficient dissemination, so approaches in such direction need to address these requirements and adapt or complement the MPR mechanism accordingly. This paper analyzes the main asymptotic properties of MPR and MPR-based topology selection algorithms, and provides sufficient conditions for the correctness of MPR-based topology selection. It examines as well in detail the MPR-based topology selection algorithm of MPR-OSPF, Path MPR, and shows that this algorithm may be unable, in certain conditions, to preserve optimal routes in its topology selection. The paper concludes by proposing and validating a modification of the Path MPR algorithm to overcome this sub-optimal performance.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Multi-Point Relaying (MPR) is a well-known relay pruning algorithm that has proved to be useful for efficient dissemination in Mobile Ad hoc Networks (MANETs). But this technique may be useful for other tasks in MANET link-state routing as well. In particular, the approach is attractive for the selection of topology information to be flooded across the network. Requirements for such topology selection are however different from those applying for efficient dissemination, so approaches in such direction need to address these requirements and adapt or complement the MPR mechanism accordingly. This paper analyzes the main asymptotic properties of MPR and MPR-based topology selection algorithms, and provides sufficient conditions for the correctness of MPR-based topology selection. It examines as well in detail the MPR-based topology selection algorithm of MPR-OSPF, Path MPR, and shows that this algorithm may be unable, in certain conditions, to preserve optimal routes in its topology selection. The paper concludes by proposing and validating a modification of the Path MPR algorithm to overcome this sub-optimal performance.
Baccelli, Emmanuel; Cordero, Juan Antonio; Jacquet, Philippe
Using Relative Neighborhood Graphs for Reliable Database Synchronization in MANETs Proceedings Article
In: pp. 1-6, Proceedings of the 5th IEEE SECON Workshop on Wireless Mesh Networks (WiMesh 2010)., Boston, MA, United States., 2010.
@inproceedings{Baccelli2010,
title = {Using Relative Neighborhood Graphs for Reliable Database Synchronization in MANETs},
author = {Emmanuel Baccelli and Juan Antonio Cordero and Philippe Jacquet},
url = {https://www.researchgate.net/publication/224155213_Using_Relative_Neighborhood_Graphs_for_Reliable_Database_Synchronization_in_MANETs},
doi = {10.1109/WIMESH.2010.5507907},
year = {2010},
date = {2010-06-01},
pages = {1-6},
publisher = {Proceedings of the 5th IEEE SECON Workshop on Wireless Mesh Networks (WiMesh 2010).},
address = {Boston, MA, United States.},
abstract = {Achieving reliable communication of critical data on mobile ad hoc networks is a must before MANETs can be considered practical for standard mobile and vehicular communications. This paper thus focuses on schemes that complement existing ad hoc broadcast mechanisms (inherently unreliable), which can guarantee the full diffusion of critical messages, when necessary. An interesting approach in this domain is the use of an overlay network, over which critical messages are acknowledged peer to peer, in order to verify the actual dissemination. This paper elaborates on the problem of performance, related to the discovery and the maintenance of such an overlay network, in a mobile ad hoc context. We present an analysis of a novel algorithm, SLOT (Synchronized Link Overlay - Triangular), an overlay selected based on a Relative Neighborhood Graph (RNG) scheme, and we compare its performance with that of other existing algorithms, in the context of the industry-standard IP routing protocol OSPF, which uses alternative overlay algorithms to synchronize link state databases of routers. The results presented in this paper show that SLOT outperforms other existing overlays by necessitating drastically less control traffic in order to function, enabling OSPF to scale to larger mobile ad hoc topologies.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Achieving reliable communication of critical data on mobile ad hoc networks is a must before MANETs can be considered practical for standard mobile and vehicular communications. This paper thus focuses on schemes that complement existing ad hoc broadcast mechanisms (inherently unreliable), which can guarantee the full diffusion of critical messages, when necessary. An interesting approach in this domain is the use of an overlay network, over which critical messages are acknowledged peer to peer, in order to verify the actual dissemination. This paper elaborates on the problem of performance, related to the discovery and the maintenance of such an overlay network, in a mobile ad hoc context. We present an analysis of a novel algorithm, SLOT (Synchronized Link Overlay - Triangular), an overlay selected based on a Relative Neighborhood Graph (RNG) scheme, and we compare its performance with that of other existing algorithms, in the context of the industry-standard IP routing protocol OSPF, which uses alternative overlay algorithms to synchronize link state databases of routers. The results presented in this paper show that SLOT outperforms other existing overlays by necessitating drastically less control traffic in order to function, enabling OSPF to scale to larger mobile ad hoc topologies.
Baccelli, Emmanuel; Cordero, Juan Antonio; Jacquet, Philippe
Multi-Hop Relaying Techniques with OSPF on Ad Hoc Networks Proceedings Article
In: Proceedings of the 4th IEEE International Conference on Systems and Networks Communications (ICSNC – SoftNet 2009), 2009.
@inproceedings{Baccelli2009b,
title = {Multi-Hop Relaying Techniques with OSPF on Ad Hoc Networks},
author = {Emmanuel Baccelli and Juan Antonio Cordero and Philippe Jacquet},
url = {https://www.researchgate.net/publication/232640050_Multi-point_Relaying_Techniques_with_OSPF_on_Ad_Hoc_Networks},
year = {2009},
date = {2009-09-01},
publisher = {Proceedings of the 4th IEEE International Conference on Systems and Networks Communications (ICSNC – SoftNet 2009)},
abstract = {Incorporating multi-hop ad hoc wireless networks in the IP infrastructure is an effort to which a growing community participates. One instance of such activity is the extension of the most widely deployed interior gateway routing protocol on the Internet, OSPF (Open Shortest Path First), for operation on Mobile Ad hoc Networks (MANETs).Such extension allows OSPF to work on heterogeneous networks encompassing both wired and wireless routers,which may self-organize as multi-hop wireless subnetworks, and be mobile. Three solutions have been proposed for this extension, among which two based on techniques derived from multi-point relaying (MPR). This paper analyzes these two approaches and identifies some fundamental discussion items that pertain to adapting OSPF mechanisms to multi hop wireless networking, before concluding with a proposal for a unique, merged solution based on this analysis.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Incorporating multi-hop ad hoc wireless networks in the IP infrastructure is an effort to which a growing community participates. One instance of such activity is the extension of the most widely deployed interior gateway routing protocol on the Internet, OSPF (Open Shortest Path First), for operation on Mobile Ad hoc Networks (MANETs).Such extension allows OSPF to work on heterogeneous networks encompassing both wired and wireless routers,which may self-organize as multi-hop wireless subnetworks, and be mobile. Three solutions have been proposed for this extension, among which two based on techniques derived from multi-point relaying (MPR). This paper analyzes these two approaches and identifies some fundamental discussion items that pertain to adapting OSPF mechanisms to multi hop wireless networking, before concluding with a proposal for a unique, merged solution based on this analysis.
Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe; Nguyen, Dang
RFC5449 - OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks Miscellaneous
2009, (http://tools.ietf.org/html/rfc5449).
@misc{Baccelli2009,
title = {RFC5449 - OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks},
author = {Emmanuel Baccelli and Thomas Clausen and Philippe Jacquet and Dang Nguyen},
url = {http://www.thomasclausen.net/wp-content/uploads/2015/12/rfc5449.txt.pdf},
doi = {10.17487/RFC5449},
year = {2009},
date = {2009-02-01},
publisher = {IETF - Exp. RFC},
organization = {The Internet Engineering Task Force},
abstract = {This document specifies an OSPFv3 interface type tailored for mobile ad hoc networks. This interface type is derived from the broadcast interface type, and is denoted the "OSPFv3 MANET interface type". This memo defines an Experimental Protocol for the Internet community.},
note = {http://tools.ietf.org/html/rfc5449},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
This document specifies an OSPFv3 interface type tailored for mobile ad hoc networks. This interface type is derived from the broadcast interface type, and is denoted the "OSPFv3 MANET interface type". This memo defines an Experimental Protocol for the Internet community.
Cordero, Juan Antonio
On MPR-OSPF Specification and Implementation in Quagga/GTNetS Technical Report
INRIA Research Report, no. 6827, 2009.
@techreport{Cordero2009,
title = {On MPR-OSPF Specification and Implementation in Quagga/GTNetS},
author = {Juan Antonio Cordero},
url = {https://hal.archives-ouvertes.fr/inria-00359138/document},
year = {2009},
date = {2009-02-01},
number = {6827},
institution = {INRIA},
type = {Research Report},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe; Nguyen, Dang
Integrating VANETs in the Internet Core with OSPF: the MPR-OSPF Approach Proceedings Article
In: International Conference on ITS Telecommunications (ITST), Sophia Antipolis, France, June 2007, 2007.
@inproceedings{Clausen2007,
title = {Integrating VANETs in the Internet Core with OSPF: the MPR-OSPF Approach},
author = {Emmanuel Baccelli and Thomas Clausen and Philippe Jacquet and Dang Nguyen},
url = {http://www.thomasclausen.net/wp-content/uploads/2015/12/2007-ITST-Integrating-VANETs-in-the-Internet-Core-with-OSPF-the-MPR-OSPF-Approach.pdf},
doi = {10.1109/ITST.2007.4295864},
year = {2007},
date = {2007-06-01},
publisher = {International Conference on ITS Telecommunications (ITST), Sophia Antipolis, France, June 2007},
abstract = {Solutions for mobile ad hoc routing have matured over the last decade. Building atop these foundations, new challenges are set for MANETs, such as integration in the Internet core. On this topic, this paper designs and evaluates MPR-OSPF, an extension of the OSPF protocol enabling its operation on networks that may include both MANET nodes and usual fixed routers. Automatic integration of different types of vehicular ad hoc networks (VANETs) in the IP infrastructure is then possible using the classic OSPF framework. Techniques used therefore are derived from OLSR, the MANET routing protocol that is the most compatible with traditional IP environments.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Solutions for mobile ad hoc routing have matured over the last decade. Building atop these foundations, new challenges are set for MANETs, such as integration in the Internet core. On this topic, this paper designs and evaluates MPR-OSPF, an extension of the OSPF protocol enabling its operation on networks that may include both MANET nodes and usual fixed routers. Automatic integration of different types of vehicular ad hoc networks (VANETs) in the IP infrastructure is then possible using the classic OSPF framework. Techniques used therefore are derived from OLSR, the MANET routing protocol that is the most compatible with traditional IP environments.
Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe
Ad-hoc and Internet Convergence: Adapting OSPF-style Database Exchanges for Ad-hoc Networks, Proceedings Article
In: Proceedings of the Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), London, UK., Proceedings of the Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), London, UK., 2004.
@inproceedings{Clausen2004b,
title = {Ad-hoc and Internet Convergence: Adapting OSPF-style Database Exchanges for Ad-hoc Networks,},
author = {Emmanuel Baccelli and Thomas Clausen and Philippe Jacquet},
url = {http://www.thomasclausen.net/wp-content/uploads/2015/12/2004-HetNets-Ad-hoc-and-Internet-Convergence-Adapting-OSPF-style-Database-Exchanges-for-Ad-hoc-Networks.pdf},
year = {2004},
date = {2004-10-01},
booktitle = {Proceedings of the Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), London, UK.},
publisher = {Proceedings of the Conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), London, UK.},
abstract = {The OSPF routing protocol is, currently, the predominant IGP in use on the fixed Internet of today. This routing protocol scales (in principle) ”world wide”, under the assumptions of links being relatively stable, network density being low (relatively few adjacencies per router) and mobility being present at the edges of the networks only. Recently, work has begun towards extending the domain of OSPF to also include ad-hoc networks – i.e. dense networks, in which links are short-lived and all nodes are mobile. In this paper, we focus on the convergence of the Internet and ad-hoc networks, through extensions to the OSPF routing protocol. Based on WOSPF, a merger of the ad- hoc routing protocol OLSR and OSPF, we examine the feature of OSPF database exchange and reliable synchro- nisation in the context of ad-hoc networking. We find that the mechanisms, in the form present in OSPF, are not suitable for the ad-hoc domain. We propose an alternative mechanism for link-state database exchanges in wireless ad-hoc networks, aiming at furthering an adaptation of OSPF to be useful also on ad-hoc networks, and evaluate our alternative against the mechanism found in OSPF. Our proposed mechanism is specified with the following applications in mind: (i) Reliable diffusion of link-state information replacing OSPF acknowledgements with a mechanism suitable for mobile wireless networks; (ii) Reduced overhead for performing OSPF style database exchanges in a mobile wireless network; (iii) Reduced initialisation time when new nodes are emerging in the network; (iv) Reduced overhead and reduced convergence time when several wireless OSPF ad hoc network clouds merge.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The OSPF routing protocol is, currently, the predominant IGP in use on the fixed Internet of today. This routing protocol scales (in principle) ”world wide”, under the assumptions of links being relatively stable, network density being low (relatively few adjacencies per router) and mobility being present at the edges of the networks only. Recently, work has begun towards extending the domain of OSPF to also include ad-hoc networks – i.e. dense networks, in which links are short-lived and all nodes are mobile. In this paper, we focus on the convergence of the Internet and ad-hoc networks, through extensions to the OSPF routing protocol. Based on WOSPF, a merger of the ad- hoc routing protocol OLSR and OSPF, we examine the feature of OSPF database exchange and reliable synchro- nisation in the context of ad-hoc networking. We find that the mechanisms, in the form present in OSPF, are not suitable for the ad-hoc domain. We propose an alternative mechanism for link-state database exchanges in wireless ad-hoc networks, aiming at furthering an adaptation of OSPF to be useful also on ad-hoc networks, and evaluate our alternative against the mechanism found in OSPF. Our proposed mechanism is specified with the following applications in mind: (i) Reliable diffusion of link-state information replacing OSPF acknowledgements with a mechanism suitable for mobile wireless networks; (ii) Reduced overhead for performing OSPF style database exchanges in a mobile wireless network; (iii) Reduced initialisation time when new nodes are emerging in the network; (iv) Reduced overhead and reduced convergence time when several wireless OSPF ad hoc network clouds merge.
Baccelli, Emmanuel; Clausen, Thomas; Jacquet, Philippe
OSPF-style Database Exchange and Reliable Synchronization in the Optimized Link State Routing Protocol Proceedings Article
In: IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), San Jose, USA, Oct. 2004, 2004.
@inproceedings{Clausen2004bb,
title = {OSPF-style Database Exchange and Reliable Synchronization in the Optimized Link State Routing Protocol},
author = {Emmanuel Baccelli and Thomas Clausen and Philippe Jacquet},
url = {http://www.thomasclausen.net/wp-content/uploads/2015/12/2004-IEEE-SECON-OSPF-style-Database-Exchange-and-Reliable-Synchronization-in-the-Optimized-Link-State-Routing-Protocol.pdf},
doi = {10.1109/SAHCN.2004.1381921},
year = {2004},
date = {2004-10-01},
publisher = {IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), San Jose, USA, Oct. 2004},
abstract = {The Optimized Link-State Routing protocol (OLSR) is a proactive link-state routing protocol. While similar to the well-known Internet routing protocol OSPF, OLSR is designed to be simple, and to maintain connec- tivity in face of highly dense and dynamic networks, while being ressource-economic (battery, bandwidth etc.) These characteristics make OLSR suitable as an underlaying routing protocol in a wide range of ad-hoc sensor networks. In this paper, we introduce an extension to OLSR: OSPF-style database exchange and reliable synchroniza- tion. The goal of this extension is to provide a mechanism, through which nodes in an ad-hoc sensor network can de- tect and correct discrepancies in their link-state databases. We qualify why the mechanism, found in OSPF, is not directly applicable for ad-hoc sensor networks, describe an adopted mechanism, accomplishing the same goal, and evaluate the performance of this mechanism in comparison to the database exchange mechanism found in OSPF. We finally discuss some applications of database exchange and reliable synchronization in ad-hoc sensor networks.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The Optimized Link-State Routing protocol (OLSR) is a proactive link-state routing protocol. While similar to the well-known Internet routing protocol OSPF, OLSR is designed to be simple, and to maintain connec- tivity in face of highly dense and dynamic networks, while being ressource-economic (battery, bandwidth etc.) These characteristics make OLSR suitable as an underlaying routing protocol in a wide range of ad-hoc sensor networks. In this paper, we introduce an extension to OLSR: OSPF-style database exchange and reliable synchroniza- tion. The goal of this extension is to provide a mechanism, through which nodes in an ad-hoc sensor network can de- tect and correct discrepancies in their link-state databases. We qualify why the mechanism, found in OSPF, is not directly applicable for ad-hoc sensor networks, describe an adopted mechanism, accomplishing the same goal, and evaluate the performance of this mechanism in comparison to the database exchange mechanism found in OSPF. We finally discuss some applications of database exchange and reliable synchronization in ad-hoc sensor networks.
