OSPF Extensions for Mobile Ad-hoc Networks

Shakir James,sjames@wustl.edu (A survey paper written under guidance of Prof. Raj Jain)

Download

Abstract:

Extending a standard routing algorithm to support mobile networks is better thandesigning a new algorithm from scratch. An extension to a standard is more likely to beadopted by industry and it reduces the overall cost of deployment. The Open Shortest PathFirst (OSPF) routing algorithm is widely used for wired networks. This paper surveysthree proposals to extend OSPF to support Mobile Ad-hoc Networks (MANETs): OSPF MANETDesignated Routers (MDR), Cisco's OSPF extension, and OSPF Multi-point Relaying(MPR).

Keywords:

Open shortest path first, Mobile ad-hoc network, Mobile routing, OSPF-MDR, Cisco'sOSPF extension, OSPF-MPR

Table of Contents

• 1. Introduction
• • 1.1 Related Work
  • 1.2 Organization
• 2. OSPF
• • 2.1 Adjacency Reduction
  • 2.2 Hello Protocol
  • 2.3 Flooding Procedure
  • 2.4 Security
• 3. OSPF-MDR
• • 3.1 Adjacency Reduction
  • 3.2 Hello Protocol
  • 3.3 Flooding Procedure
• 4. Cisco's OSPF Extension
• • 4.1 Adjacency Reduction
  • 4.2 Hello Protocol
  • 4.3 Flooding Procedure
• 5. OSPF-MPR
• • 5.1 Adjacency Reduction
  • 5.2 Hello Protocol
  • 5.3 Flooding Procedure
• 6. Summary
• References
• List of Acronyms

1. Introduction

Traditionally, network routing was concerned with machines and routers connectedtogether by wires. Today network-enabled mobile devices are ubiquitous, so packets arenot only forwarded along fixed paths. In fact, the line between the wired and mobilenetwork is blurring. Users now expect their mobile devices to seamlessly coexist withtheir wired counterparts. We define a mobile ad hoc network (MANET) as a wireless networkwithout a central base station. Due to a lack of central base station, nodes in a MANETmust form peering relationships to collectively make routing decisions.

Many routing protocols for MANETs have been developed such as Optimized Link StateRouting, Dynamic Source Routing, and Ad-hoc On-demand Distance Vector Routing [Jain08]. However, these mobile-only protocols attempt to divide a networkwhere clear divisions no longer exist. Designing a new protocol that supports both awired network and a MANET is a costly alternative. (Assuming a new protocol is everwidely adopted.) Another alternative is to support two separate protocols, one for wiredand the other for MANETs, within a single router. However, this complicatesinteroperability between the two networks. Therefore, the most practical alternative isto extend an existing wired routing standard to support MANETs.

The Open Shortest Path First (OSPF) routing algorithm is a wired protocol thatrepresents a good candidate to extend to support MANETs. OSPF is widely deployed andincludes many innovative features. The protocol's specifications are in the publicdomain; hence the "open" in OSPF. It is used by upper-tierInternet service providers to determine routes within their networks. It supportsmulticast routing, multiple same-cost paths, and the ability to organize a network as ahierarchy [Kurose07].

Although the innovative features of OSPF make it an appealing candidate to extend tothe MANET routing domain, OSPF was designed for wired networks where the topology ispredicable and the medium is relatively reliable. These assumptions do not hold in adynamic and unpredictable MANET. Nodes in a MANET randomly form peering relationships asthey come into communication range. Moreover, packet loss frequently occurs on a wirelessmedium due to path loss, interferences, noise, shadowing, and multipath. Therefore, OSPFneeds to be modified to meet the routing requirements of a MANET, which includeminimizing data exchange and control overhead [Jain08].

1.1 Related Work

The OSPFv2 Wireless Interface Type is a more general proposal to enhance OSPF tosupport wireless networks. The proposal is not limited to MANETs; it supports"wireless, broadcast-capable, multi-hop" networks. Similarto the MANET proposals, the OSPFv2 Wireless Interface Type is not a clean-slate design.It proposes to modify an OSPF-enabled router to connect to both wired and wirelessnetworks. A team at Boeing Company contributed to the OSPFv2 Wireless Interface Typeproposal. [Ahrenholz04]

Boeing also made other contributions to the OSPF extension for MANETs. They evaluated[Henderson05] and analyzed [Spagnolo06a] the performance of MANET extensions. In particular, theyshowed by simulation that OSPF MANET Designated Routers (MDR) and Cisco's extension(Overlapping Relay and Smart peering) "approximate the performance ofeach other" [Spagnolo06b]. This paper complements their work by providing aqualitative comparison of OSPF-MDR and Cisco's extension.

1.2 Organization

In this paper, we examine OSPF extensions for MANETs in the context of three currentInternet engineering task force (IETF) proposals. Section 2 provides some background onOSPF routing setting up a framework for discussion of OSPF extensions for MANETs. Section3 covers the MANET Designates Routers (MDRs) extension. Cisco's OSPF extension and OSPFMulti-point Relaying (MPR) are described in section 4 and 5 respectively. In Section 6,we conclude with a summary.

2. OSPF

Open Shortest Path First (OSPF) uses a link-state routing protocol to find theleast-cost path from a source router to a destination router within a group of routersowned by an organization. As shown in Figure 1, a group of routers using the same routingprotocol is collectively referred to as an Autonomous system (AS). Upon joining the AS, arouter uses the Hello protocol to discover neighboring routers. Then it forms adjacencieswith its new neighbors to exchange routing information.

Figure 1 Connected Autonomous systems (ASs)

The exchange of routing information, called flooding, allows routers to obtain acomplete view of the network topology. The data exchanges are called link-stateadvertisements (LSAs). LSAs are stored by a router in its a link-state database (LSDB).The LSDB represents the complete network topology visible by a router and is used asinput to Dijkstra least-cost path algorithm. Dijkstra's algorithm determines the leastcost path from a router to other nodes. Routers also periodically broadcast updates aboutthe current state of its links to synchronize their LSDBs.

In the following subsections, we describe each step of the routing algorithm infurther detail. Section 2.1 covers a mechanism to reduce adjacency formation. The Helloprotocol is described in 2.2. Section 2.3 details the flooding of link-stateinformation.

2.1 Adjacency Reduction

Two routers that connect to a common network form an adjacency. Only adjacent routersexchange routing information and synchronize their LSDBs. Thus, adjacencies govern theexchange of routing information among routers. If all neighboring routers formedadjacencies then the volume of data exchange will be substantial:O(n²).

The assignment of Designated Routers (DR) provides a mechanism to reduce number dataexchanges to O(n). As shown in Figure 2, one router is elected as theDR and another the Backup Designated Router (BDR). (The BDR reduces downtime in the eventof DR failure.) All routers exchange routing data only with their elected DR and BDR.Then the DR relays the data to other routers. [Cisco05]

Figure 2 The Designated Router (DR) reduces the number of adjacencies

l

The Hello protocol provides a mechanism for electing the network DR. Hello packetscontain a router priority that is used to assign the DR. The first router with thehighest priority becomes the DR, and the router with the second highest, the BDR.However, the primary function of the Hello protocol is to find and maintain connectionsamong neighbors.

Hello packets are broadcasted periodically to advertise a router's presence on anetwork and to ensure two-way communication between itself and it's neighbors. A hellopacket sent by a router contains its DR, BDR, and known neighbors. If a router is listedas a known neighbor in its neighbors Hello packets, then a bidirectional link existsbetween them. Additionally, data describing OSPF capabilities are including in the hellopacket.

2.3 Flooding Procedure

Flooding is the mechanism by which adjacencies synchronize their link-state databases.The process involves the exchanging LSAs. Each LSA contains the state of routersconnections and its known adjacencies. The collection of LSAs forms the LSDB, whichrepresents the complete network topology. LSA are necessary to ensure the data in arouters' LSDB remain synchronized.

Maintaining a synchronized link-state database locally is necessary to run Dijkstra'sleast-cost path algorithm. The algorithm requires the full network topology to calculatea short-path tree. Each router runs the algorithm, with itself as the root, to determinethe shortest path to each destination within its AS. The router's forwarding tableconsists of the next hop along the shortest path to each destination.

2.4 Security

To prevent malicious users from poisoning a router's link-state database, OSPFsupports router authentication. OSPF packets can be authenticated by two methods: simpleand cryptographic. In simple authentication, a preconfigured 64-bit password is includedas plaintext in the OSPF packet header. This method prohibits routers from joining theOSPF network accidently, but does not preclude attackers from snooping passwords.

The cryptographic authentication method is more secure than simple authentication. Ituses a keyed generated by the MD5 algorithm. The sender includes a hash based on apre-shared secret key along with the packet content. The receiver computes the hash(based on the known key for this sender) to verify the sender's authenticity. Sequencenumbers can also be included in the hash to prevent replay attacks.

3. OSPF-MDR

OSPF MANET Designates Routers (MDR) extends the concept of OSPF's DR to reduceflooding overhead. A set of connected MDRs form a connected dominating set (CDS), whichrepresents "an optimized shared backbone" for flooding[Henderson05]. Differential Hellos are also used to reducesize of hello packets and further reduce protocol overhead. [Ogie08] Section 3.1 describes the selection of MDR and formation of theCDS. The Differential Hello extension is discussed in 3.2. Lastly, CDS flooding iscovered in 3.3.

3.1 Adjacency Reduction

Extending the DR and BDR concept from non-wireless OSPF, OSPF-MDR assigns a MANETDesignates Routers (MDRs) and Backup MDRs (BMDR) to reduce protocol overhead and improvescalability. MDRs only form adjacencies with a subset of it neighbors to reduce networktopology, and LSAs are only flooded among adjacencies to reduce overhead. The set ofconnected MDRs form a connected dominating set (CDS). For example in Figure 3, nodes 0,2, 3, 4, and 6 form the CDS.

Similar to OSPF's distributed selection of DR, OSPF-MDR uses data in the Hello packetsto elect the MDR and BMDR. Considering only their directly connected neighbors (theirone-hop neighborhood) the MDR with the largest value of the router priority, MDR level (2 - MDR, 1 - BMDR, and 0 otherMDR), and router ID is elected as the MDR [Baccelli08].

3.2 Hello Protocol

OSPF-MDR uses Differential Hellos to reduce Hello packet overhead. A DifferentialHello packet only includes the neighbors whose state has recently changed. Compared tosending full Hellos, which always include the list of neighbors (full Hello),Differential Hello packets save network bandwidth. Both types of Hello (full andDifferential) are supported in OSPF-MDF. The use of Differential Hello reduces thefrequency at which full Hello packets are sent.

In addition to reducing control overhead, Differential Hellos also allow OSPF-MDR toreact quickly to the dynamic topology of MANETs. When a new node is connected ordisconnected a Differential Hello can be sent inform adjacencies of the change intopology. Since Differential Hellos are smaller they are sent more frequently than fullHello.

3.3 Flooding Procedure

Since the Connected Dominating Set (CDS) is responsible for flooding new LSA, theflooding procedure in OSPF-MDR is called CDS flooding. As shown in Figure 3, each routeris either in the CDS or one hop away from it. MDRs exchange LSA among each other andrelay them its neighbors. Routers ignore LSA from neighbors with which they do not have abidirectional connection.

Figure 3 The Connected Dominating Set (CDS) is responsible forflooding.

4. Cisco's OSPF Extension

Cisco's OSPF extension uses smart peering to reduce flooding overhead. Similar toOSPF-MDR, this extension reduces the size of Hello packets using an Incremental HelloProtocol. Optimized flooding is achieves by using an overlapping relays mechanism basedon OLSR. [Chandra08] Section 4.1 describes the smart peeringprocess, section 4.2 details the Incremental Hello protocol, and 4.3, Overlapping relayflooding.

4.1 Adjacency Reduction

Selection of a DR in OSPF assumes full connectivity among a network, but in MANETspartially connected overlapping meshes are common. In smart peering, a router selectivelyforms a peering relationship (adjacency) with its neighbors. Although this selectivepeering reduces network connectivity, it reduces control overhead and the total number ofadjacencies.

A router peers with a neighbor, forms an adjacency, if the neighbor improves itnetwork reachability. It forms an adjacency if the neighbor provides paths to previouslyunreachable nodes and may choose not to form an adjacency if it does not provide newpaths. Once more, the data in the Hello packets are used to determine whether or not toform an adjacency.

4.2 Hello Protocol

Similar to OSPF-MDR, Cisco's extension seeks to reduce the size of Hello packets nottransmitting the full list of neighbors. In both protocols only neighbors whose stateshave changed recently are transmitted. Although Cisco's proposal is called IncrementalHello Protocol, it is essentially the same as MDR Differential Hello Protocol.

However, there is one minor difference in how the"incremental" updates of neighbors are classified. InOSPF-MDR, Neighbor IDs indicate what type of event triggered the inclusion of theneighbor in the Hello packets. A type field identifies the event in Cisco'simplementation. For example, MDR's Neighbor ID 1 is equivalent to Cisco's Type 3neighbors; both indicate that this neighbors recently disconnected.

4.3 Flooding Procedure

Overlapping relays (OR), based on OLSR, are used for optimized flooding in Cisco'sextension. In OR, a router selects a subset of its neighbors called it active relays thatare allowed to flood its LSAs. Other nodes are called its non-active relays. The routertries to select the smallest set of active relays that allows it to discover all itstwo-hop neighbors. Figure 4, illustrates the active relays for a node 0 are 2 and 4.

To select the smallest subset of active relays are router must know its neighbor'sneighbor; i.e. it's two-hop neighborhood. As shown, in Figure 4, node 0 learns that node5 is an adjacency of node 4 by inspecting node 4's LSA.

Figure 4 Overlapping Relays used for flooding

5. OSPF-MPR

OSPF Multi-point Relaying (MPR) uses an MPR selector set to reduce adjacencies. Unlikethe other two extensions, OSPF-MPR makes not changes to Hello protocol. It minimizesflooding overhead by choosing a flooding MPR set. [Baccelli08] Section 5.1 describes theMPR selector set, section 5.2 covers the minor changes to the Hello protocol, and 5.3,MPR-flooding.

5.1 Adjacency Reduction

Similar to Cisco's extension, OSPF Multi-point Relaying (MPR) only forms adjacencieswith a limited subset of neighbors to improve scalability and reduce control overhead(LSAs). However, OSPF-MPR does not assign a MDR. Instead it uses MPR selector sets, whichis based on OLSR. A router forms adjacencies with a subset of its one-hop neighborscalled its MPR selector set.

Most routers only form adjacencies with its MPR selector set, but some Synch routersalso form adjacencies with neighbors not in their selector set. A router becomes a synchrouter only if it has highest router ID among its known neighbors. Hello packets and LSAcontain router ID of its neighbors. At least one Synch router must exist in theMANET.

5.2 Hello Protocol

In OSPF-MPR no optimization are made to Hello packets. However, extra packet data isin the packets to facilitate MPR selection. In particular, the link costs to routers'adjacencies are added in hello packets. These LSAs are generated periodically in responseto events on the wireless links.

5.3 Flooding Procedure

OSPF-MPR designates a subset of its selector set as its flooding-MPR. The flooding-MPRis responsible for relaying LSA through the MANET, so the procedure is calledMPR-flooding. The flooding-MPR is selected such that the "coveragecriterion" is maintained [Baccelli08]. The criterion states that an LSA mustbe received by all routers two hop counts away from members for the MPR-flooding set.

The routers in the MANET use a distributed selection procedure based on Hello packetsto determine the flooding-MPR. The overhead generated by the selection process isdirectly proportional to the size of the flooding-MPR. Regardless of the size of theflooding-MPR, each router must be two hops away from some router in aflooding-MPR.

6. Summary

We described three IETF proposals to extend OSPF for MANETs: OSPF -MDR, Cisco'sextension, and OSPF-MPR. Each proposal attempts to minimize data exchange and controloverhead through three primary mechanisms: reducing adjacencies, modifying the Helloprotocol, and optimized flooding. OSPF-MDR uses MDRs, Differential Hellos, and CDSflooding. Cisco's extension utilizes Smart peering, Incremental Hellos, and Overlappingrelays. Finally, OSPF-MPR makes use of MPR selector sets and MPR flooding.

Both Cisco's and OSPF-MPR borrow ideas from OLSR, while OSPF-MDR extends OSPF's DRadjacency reduction technique. It is anyone's guess which proposal becomes the standardOSPF extension for MANET. However, Cisco is able to deploy its extension in real routerstoday, so its extension may become the de facto standard.

References