Transcript MANET Extension of OSPF

OSPF-MDR: Extension of OSPF
for Mobile Ad Hoc Networks
draft-ietf-ospf-manet-mdr-02.txt
Richard Ogier
September 17, 2008
OSPF-MDR - 1
Review of OSPF
•
•
•
•
•
•
Open Shortest-Path First (OSPF) is a standard IP routing protocol that
performs reliable flooding of link-state advertisements (LSAs) that describe
the topology of the network.
Each router creates a router-LSA that describes its links to neighbors, and
originates/floods a new LSA (with a larger sequence number) when the
contents change (subject to MinLSInterval = 5 sec).
OSPF allows multiple areas (clusters) for hierarchical routing. Each router
in an area is provided with the full topology for the area, and Dijkstra’s
algorithm is used to compute a shortest-path tree for the area.
OSPF supports four interface types: point-to-point, broadcast, NBMA, and
point-to-multipoint. OSPF does not support MANET interfaces.
A MANET interface can be considered a generalization of a broadcast
interface in which two neighbors need not be neighbors of each other
(multi-hop network).
OSPF-MDR is an extension of OSPFv3 [RFC 2740], which is a
modification of OSPFv2 [RFC 2328] that supports IPv6.
OSPF-MDR - 2
Review of OSPF (cont.)
•
•
•
•
Each router forms an adjacency
with each new neighbor (except in
broadcast and NBMA networks) by
performing Database Exchange to
synchronize databases.
Each router describes its database
to the other router by sending
Database Description (DD)
packets, which list all LSA headers.
Link State Request packets are
used to request LSAs for which the
neighbor has a more recent
instance.
When all requested LSAs are
received, the neighbor becomes
fully adjacent (neighbor state Full).
OSPF-MDR - 3
Review of OSPF (cont.)
•
RFC 5243 describes a new database exchange optimization that was
originally part of OSPF-MDR, but applies to OSPF in general.
– A router does not list an LSA in DD packets sent to a neighbor, if the
same or a more recent instance of the LSA was listed in a DD packet
already received from the neighbor.
– Reduces the DD overhead by about 50% in large networks.
•
OSPF flooding procedure:
– Each router normally forwards (floods) each new LSA to each
adjacent neighbor (except the one from which it was received).
The case of a broadcast network is considered in the next slide.
– An LSA is retransmitted as a unicast to an adjacent neighbor when
an Ack for the LSA has not been received within RxmtInterval.
OSPF-MDR - 4
Review of OSPF (cont.)
•
To reduce overhead in a broadcast network, OSPF elects a Designated Router
(DR) and Backup Designated Router (BDR):
–
Adjacencies are formed only between the DR/BDR and its neighbors, resulting in O(n)
instead of O(n2) adjacencies.
–
The DR is responsible for flooding new LSAs to all routers on the broadcast network.
–
If a router that is not DR/BDR originates a new LSA or receives a new LSA from another
interface, it forwards the LSA to the DR and BDR, then the DR broadcasts the LSA to all
routers on the network. (The BDR retransmits LSAs as unicasts based on Acks.)
DR
BDR
OSPF-MDR - 5
Brute Force Method for Supporting MANETs
•
•
•
OSPF can support a MANET by treating each neighbor as a point-to-point link,
and forming an adjacency with each neighbor. Every router would forward
(flood) each received new LSA on the MANET interface.
In a network with 100
nodes with average
degree 50, this would
require 2500
adjacencies to be
formed, as shown in
the figure.
This method generates
a huge amount of
overhead, and can
support only very small
networks.
OSPF-MDR - 6
OSPF-MDR Approach
•
•
•
•
Problem: How do we extend OSPF to mobile ad hoc networks while
achieving good performance, low overhead, and maximum scalability?
OSPF uses the Designated Router (DR) and Backup DR to achieve this
goal in broadcast networks, but can we generalize the DR to achieve this
goal in multihop wireless networks?
OSPF-MDR generalizes the DR by selecting a small subset of routers,
called MANET Designated Routers (MDRs) that form a connected
dominating set (CDS).
MDRs achieve scalability in MANETs similar to the way DRs achieve
scalability in broadcast networks:
– MDRs have primary responsibility for flooding LSAs. Backup MDRs
provide backup flooding when MDRs temporarily fail.
– Adjacency reduction may be used, in which adjacencies are formed
only between MDR/BMDR routers and their neighbors.
OSPF-MDR - 7
OSPF-MDR Approach (cont.)
•
•
OSPF’s Hello protocol is modified to provide 2-hop neighbor
information required for MDR selection, and to allow differential Hellos
that list only neighbors whose state has recently changed.
The contents of router-LSAs is flexible:
– Partial-topology LSAs can be used to reduce the size and
origination frequency of LSAs.
– Either partial-topology or full-topology LSAs can be used, with
or without adjacency reduction.
•
•
Simulations show that OSPF-MDR can achieve good performance in
mobile networks with up to 160 nodes with shortest-path routing, and
up to 200 nodes with nearly-shortest-path routing.
The main website for OSPF-MDR is www.manet-routing.org, where
you can find high quality implementation and simulation code.
OSPF-MDR - 8
Basic Idea – Generalize Designated Router to
MANET Designated Routers (MDRs)
•
•
•
•
•
•
•
In an OSPF broadcast network, a single DR
(red) is elected.
Each router becomes adjacent with the DR,
forming a tree with n-1 edges.
The node having the lexicographically largest
value of (DR Level, RtrPri, RID) is elected as
DR, where DR Level can be DR, Backup DR,
or DR Other.
In a multihop wireless network, the DR
generalizes to multiple MDRs (red) which
form a connected dominating set.
For fast convergence, the MDRs select
themselves based on 2-hop neighbor
information, giving preference to nodes with
largest (RtrPri, MDR Level, RID).
Adjacencies are formed between MDRs to
form a connected backbone.
Each non-MDR becomes adjacent with an
MDR neighbor called its Parent.
OSPF-MDR - 9
Also Generalize Backup Designated Router for
Biconnected Redundancy
•
•
•
•
•
•
In an OSPF broadcast network, a Backup DR
is added for redundancy.
The adjacencies of the DR and Backup DR
form a biconnected subgraph.
Each DR Other is adjacent with the DR and
the Backup DR.
In a multihop wireless network, Backup
MDRs are added so that each node is a
neighbor of at least two (Backup) MDRs.
Backup MDRs perform backup flooding for
improved robustness.
Optionally, additional adjacencies may be
added to form a biconnected backbone
consisting of MDRs and Backup MDRs, and
each MDR Other may become adjacent with
a second (Backup) MDR neighbor called its
Backup Parent.
OSPF-MDR - 10
Animation of Simulated Network
•
•
Red nodes are MDRs, lines indicate adjacencies.
The option of uniconnected adjacencies is used.
OSPF-MDR - 11
Modified Hello Protocol
•
A Hello packet includes up to 5 neighbor lists:
– List 1: Down neighbors (only in differential Hellos)
– List 2: One-way neighbors (in state Init)
– List 3: Dependent Neighbors (which become adjacent)
– List 4: Selected Advertised Neighbors (advertised in LSA)
Bidirectional
neighbors
– List 5: Bidirectional neighbors not included in List 3 or 4
•
•
•
A differential Hello includes only neighbors whose list type changed
within the last HelloRepeatCount (default 3) Hellos.
If differential Hellos are used, then a full Hello must be sent every
2HopRefresh (default 3) Hellos, to inform new neighbors of the full state.
Each router keeps track of the following neighbor sets for each neighbor:
– Bidirectional Neighbor Set (BNS): used for MDR selection.
– Dependent Neighbor Set (DNS): used for adjacency formation.
– Selected Advertised Neighbor Set (SANS): used for constructing LSA.
OSPF-MDR - 12
MDR Selection Algorithm
•
•
Phase 1: Create the neighbor connectivity matrix based on information obtained
from Hellos: NCM(j,k) = 1 if neighbors j and k are neighbors of each other.
Phase 2: Decide whether the router is an MDR, select Dependent Neighbors
– If the router has a lexicographically larger value of (RtrPri, MDR Level, RID) than
all of its neighbors, it selects itself as an MDR and selects all MDR neighbors as
Dependent Neighbors, and proceeds to Phase 4.
– Let Rmax be the neighbor with the lexicographically largest value of
(RtrPri, MDR Level, RID).
– Using BFS, compute min-hop paths from Rmax to each other neighbor, using
only intermediate nodes that are neighbors with a larger value of
(RtrPri, MDR Level, RID) than the router itself.
– If all neighbors can be reached in at most MDRConstraint hops (default 3), then
the router is not an MDR.
– Otherwise, the router selects itself as an MDR and selects the following
neighbors as Dependent Neighbors: Rmax and each MDR neighbor that
could not be reached in at most k hops.
– Each MDR router becomes adjacent with its Dependent Neighbors, ensuring
that the backbone of MDRs is connected via adjacencies.
OSPF-MDR - 13
MDR Selection Algorithm (cont.)
•
Phase 3: Decide whether the router is a Backup MDR
– If the router did not select itself as an MDR, it selects itself as a Backup
MDR if there exists a neighbor that cannot be reached from Rmax via
two node-disjoint paths, using the same graph used in Phase 2.
– If biconnected adjacencies are used (AdjConnectivity = 2), the router
selects the following neighbors as Dependent Neighbors: Rmax and each
MDR/BMDR neighbor that could not be reached via two node-disjoint paths.
This ensures that the backbone of MDRs and BMDRs is biconnected.
– Disjoint paths from Rmax to all other neighbors are computed in O(n2) time,
using a simplification of the algorithm of Suurballe and Tarjan [Networks,
1984].
•
Benefits of prioritizing routers according to (RtrPri, MDR Level, RID):
– Allows neighbors to agree on which routers should become MDR.
– Using MDR Level increases stability and lifetime of MDRs and adjacencies.
– Using Router Priority allows certain routers to be more likely to be MDRs.
– Router Priority can be changed dynamically so that the burden of being an
MDR can be shared among all routers.
OSPF-MDR - 14
MDR Selection Algorithm - Example
•
•
•
•
•
•
•
•
•
Node numbers indicate RIDs.
Thin lines indicate bidirectional neighbors.
1
Red nodes indicate MDRs.
Green nodes indicate Backup MDRs (BMDRs).
Red lines indicate adjacencies associated with
MDRs, which form a tree in this case.
2
3
4
Green lines indicate adjacencies added to form
a biconnected subgraph.
Each MDR Other becomes adjacent with one
MDR (Parent) and optionally with another MDR
or BMDR (Backup Parent).
5
6
7
Node 7 selects itself as MDR, since there does
not exist a path from node 8 to node 4 via
neighbors with larger RID.
Node 6 selects itself as Backup MDR, since
there do not exist two disjoint paths from node 8
to neighbors 2, 3, 4, and 7 via neighbors with
larger RID.
8
OSPF-MDR - 15
MDR Selection Algorithm (cont.)
Phase 4: Parent Selection
– An MDR selects itself as Parent, to indicate
to neighbors that it is an MDR.
– A non-MDR router selects an adjacent MDR
neighbor as Parent, if one exists (to avoid
forming a new adjacency when possible);
otherwise it selects Rmax as Parent.
– A Backup MDR selects itself as Backup
Parent, to indicate to neighbors that it is a
BMDR.
– If AdjConnectivity = 2, an MDR Other selects
an adjacent MDR/BMDR parent as Backup
Parent, if one exists.
– The (Backup) Parent is advertised in the
(Backup) DR field of each Hello sent on the
interface.
– A router becomes adjacent with its Parent
and Backup Parent (if it exists and is an MDR
or BMDR), thus ensuring that each router is
connected (or biconnected) to the backbone.
OSPF-MDR - 16
MDR Selection Algorithm (concluded)
•
Phase 5: Optional Selection of Non-Flooding MDRs
– A router that has selected itself as an MDR MAY execute the following steps
to possibly declare itself a non-flooding MDR.
– Compute min-hop paths from Rmax to each other neighbor, using only
intermediate nodes that are neighbors with a smaller value of
(RtrPri, RID) than the router itself.
– If the resulting hop distance to each neighbor is at most MDRConstraint
(default 3), the router is a non-flooding MDR.
– A non-flooding MDR does not immediately forward LSAs, but behaves like a
Backup MDR.
– Phase 5 can reduce flooding overhead dramatically for certain regular
topologies, but the reduction has been found to be less than 15% for
random topologies.
OSPF-MDR - 17
LSA Flooding Procedure
•
•
To exploit the broadcast nature of MANETs, an LSA is processed (and possibly
forwarded) if it is received from any bidirectional neighbor (not just adjacent
neighbors).
A router never forwards an LSA on a MANET interface if either of the following two
conditions is satisfied for all bidirectional neighbors on the interface:
(a) The LSA or an Ack for the LSA has been received from the neighbor (over any
interface).
(b) The LSA was received on a MANET interface, and the neighbor is “covered” by
another neighbor from which the LSA was received (using 2-hop neighbor info).
•
•
•
•
If an MDR receives a new LSA, it floods the LSA back out the receiving interface if
there exists a bidirectional neighbor that does not satisfy condition (a) or (b).
If a Backup MDR or non-flooding MDR receives a new LSA, it waits ½ sec plus
jitter, then floods the LSA back out the receiving interface if there exists a bidirectional
neighbor that does not satisfy condition (a) or (b). (½ sec = BackupWaitInterval)
An MDR Other never floods a received LSA back out the same interface.
An optional step (6) is specified, which avoids redundant forwarding when flooding
occurs over multiple MANET interfaces.
OSPF-MDR - 18
Example of MDR Flooding
•
•
•
•
•
Node 8 originates and floods a new router-LSA.
If node 7 (MDR) receives the new LSA from 8, it
floods the LSA back out the same interface.
If node 6 (BMDR) receives the new LSA from 8,
it waits ½ sec plus jitter. If during this interval it
hears node 7 or 4 forward the LSA, then it does
not flood the LSA since all neighbors are
covered. Otherwise node 6 floods the LSA.
If node 4 (MDR) receives the new LSA from
node 7 or node 6, it floods the LSA.
If node 3 (BMDR) receives the new LSA from
node 7 or node 6, it waits ½ sec plus jitter, then
floods the LSA unless all neighbors are
covered.
1
2
3
4
5
6
7
8
OSPF-MDR - 19
Sending Link State Acknowledgments
•
•
All LS Ack packets sent on a MANET interface are multicast using the IP address
AllSPFRouters.
The following rules are used for acknowledging a received LSA:
–
If the LSA is new, send a delayed Ack on each MANET interface, unless the
LSA is flooded out the interface.
–
If the LSA is a duplicate and was received as a multicast, do not send an
Ack. (Each LSA is Acked only once, unless received as a unicast 
retransmission.)
–
If the LSA is a duplicate and was received as a unicast:
(a) If the router is an MDR (or a BMDR if AdjConnectivity = 2), send an
immediate Ack out the receiving interface.
(b) Otherwise, send a delayed Ack out the receiving interface.
•
•
Reason for sending an immediate Ack in case (a) is to prevent other adjacent
neighbors from retransmitting the LSA.
Optimization: To reduce the number of Acks sent, each delayed Ack is delayed
by at least MinLSInterval (5 sec) and at most RxmtInterval (7 sec), so that the Ack
need not be sent if a new instance of the LSA is received before the scheduled
time for the Ack.
OSPF-MDR - 20
Receiving Link State Acknowledgments
•
•
•
Each router maintains an Acked LSA List for each adjacent neighbor, to keep
track of any LSA instances the neighbor has acknowledged, but which the router
itself has not yet received. This is necessary because, unlike RFC 2328, each
router acknowledges an LSA only the first time it is received as a multicast.
Thus, if a router receives an Ack for a given LSA before it receives the LSA itself,
the router need not forward the LSA to the neighbor that already acked the LSA.
An LS Ack packet that is received from an adjacent neighbor is processed as in
RFC 2328, with the following additional steps:
(1) If the router receives an LS Ack for an LSA that is newer than the database
copy, the LS Ack is added to the Acked LSA List for the sending neighbor.
(2) If a Backup MDR receives an LSA Ack for an LSA for which the
BackupWait Timer is set, the sending neighbor is removed from the list of
neighbors that have not yet been covered.
OSPF-MDR - 21
Routable Neighbors
•
•
•
•
•
•
A bidirectional MANET neighbor is defined to be routable if the SPF
calculation has produced a route to the neighbor. (A quality condition
can also be required.) A routable neighbor need not be adjacent.
Only Full and routable neighbors can be used as next hops in the
SPF calculation, and can be included in the router-LSA originated by
the router.
1
2
routable
The idea is that, since a routable neighbor can be reached through an
acceptable path, it makes sense to take a "shortcut" and forward
packets directly to the routable neighbor.
4
Note that OSPF already allows a non-adjacent neighbor to be used as
a next hop, if both routers are fully adjacent to the DR of a broadcast
network. The routability condition is a generalization of this condition
to MANETs.
5
The network-LSA of an OSPF broadcast network implies that a router
can use a non-adjacent neighbor as a next hop. But a network-LSA
cannot describe the general topology of a MANET, making it
necessary to explicitly include non-adjacent neighbors in the routerLSA.
Allowing only adjacent neighbors in LSAs would either result in
suboptimal paths or would require a large number of adjacencies to
provide optimal paths.
3
DR
1
2
OSPF-MDR - 22
Link State Advertisements
•
•
•
•
The router-LSA contains a point-to-point link for each MANET neighbor that is
advertised.
The choice of which neighbors to advertise in the router-LSA is flexible, subject to
the following two rules:
–
The router-LSA can advertise any neighbor that is Full or routable.
–
If adjacency reduction is used, the router-LSA must advertise all Full
neighbors and all routable neighbors that satisfy the condition for becoming
adjacent (and will therefore become Full).
Main options for router-LSAs (other options are allowed):
–
Minimum LSAs: Advertise only the required neighbors.
–
Full-topology LSAs: Advertise all Full and routable neighbors.
–
Min-cost LSAs: Advertise a subset of neighbors that is sufficient to provide
routing along shortest (minimum-cost) paths. Advertised neighbors are
selected using 2-hop neighbor information obtained from Hellos.
The options are interoperable: Different routers need not select the same option
for the router-LSA or for adjacency reduction.
OSPF-MDR - 23
Link State Advertisements (cont.)
•
Min-Cost LSA Algorithm
– Each router selects the Selected Advertised Neighbor Set (SANS), using the
Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and SANS
for each neighbor (obtained from Hellos).
– A neighbor j is included in the SANS if necessary to provide a min-cost path
from some other neighbor to j, using (RtrPri, RID) to break ties.
– Adjacent neighbors are always advertised (if routable), so are not included in
the SANS.
•
1
Example
– Red nodes are MDRs, red lines are adjacencies
2
– Assume all metrics are 1.
– Adjacencies do not provide a min-cost path from
node 6 to node 1.
– Node 4 includes node 1 in its SANS to provide such
a path. Node 3 does not, since it has a smaller RID.
4
3
5
6
OSPF-MDR - 24
Link State Advertisements (cont.)
•
Each router advertises the following neighbors in its router-LSA:
all Full neighbors, and each routable neighbor j that satisfies any of the
following three conditions:
– The router’s SANS includes neighbor j.
– Neighbor j's SANS includes the router (to ensure symmetry).
– Neighbor j is satisfies the condition for becoming adjacent.
OSPF-MDR - 25
Simulation Results for OSPF-MDR
•
•
Results were obtained using GTNetS simulator with OSPF-MDR version
1.01, available at www.manet-routing.org
Scenario parameters:
– Grid length 500 m (square), radio range 150m, 200 m, 250 m.
– Random waypoint mobility with maximum speed 10 m/s, pause time 0.
– UDP packet size 40 bytes, packet rate 10 packets/s. Source and destination
are selected randomly for each packet.
– Simulated MAC protocol is 802.11b.
•
The following configurations of OSPF-MDR were simulated:
– Default configuration with uniconnected adjacencies and min-cost LSAs,
except using differential Hellos.
– Same except using minimal LSAs.
– Same except using full-topology LSAs.
– Same except using full-topology adjacencies and full-topology LSAs.
OSPF-MDR - 26
Results for range 250 m
OSPF-MDR - 27
Results for range 200 m
OSPF-MDR - 28
Results for range 150 m
OSPF-MDR - 29
Benefits of Adjacency Reduction
•
The following statistics do not increase as the number of nodes increases,
contributing to the low overhead achieved by OSPF-MDR:
– The number of adjacencies per node is dramatically smaller than the
number of bidirectional neighbors per node.
– The number of adjacency changes per node per second is dramatically
smaller than the number of neighbor changes per node per second.
•
•
The following results are for radio range 250 m and maximum speed 10 m/s, and
are independent of the LSA choice.
The results imply that with 200 nodes, there are 2.14/.039 = 55 times as
many adjacency formations with full-topology adjacencies as with
uniconnected adjacencies!
Number of nodes
20
Avg no. nbrs/node
Avg no. adjs/node
40
60
80
120
160
200
11.38 25.82 36.30 50.13 75.87 98.65 125.59
2.60
2.31
2.38
2.26
2.25
2.32
2.13
Nbr changes/node/s
.17
.37
.57
.75
1.22
1.65
2.14
Adj changes/node/s
.035
.036
.046
.040
.032
.035
.039
OSPF-MDR - 30
Summary of Results
•
•
•
•
OSPF-MDR achieves good performance for up to at least 160 nodes with mincost LSAs and up to at least 200 nodes with minimum LSAs.
The results for the number of hops traveled by UDP packets show that routes
obtained with minimal LSAs are only 2.3% to 4.5% longer than with min-cost
LSAs when the range is 250 m, 3.5% to 7.4% longer when the range is 200 m,
and 0.1% to 11.2% longer when the range is 150 m.
Min-cost LSAs achieve dramatically lower overhead than full-topology LSAs
without significantly affecting delivery ratio or path length.
Both adjacency reduction and LSA reduction reduce overhead greatly. For
range 250 m:
–
With no adjacency or LSA reduction, overhead is 929 kbps with only 60 nodes.
–
With uniconnected adjacencies and full-topology LSAs, overhead is 890 kbps with 80
nodes.
–
With uniconnected adjacencies and min-cost LSAs, overhead is less than 500 kbps
with 120 nodes, and less than 800 kbps with 160 nodes.
–
With uniconnected adjacencies and minimal LSAs, overhead is only
637 kbps with 200 nodes.
OSPF-MDR - 31
Commands for running simulations
•
•
•
•
•
•
./random_waypoint_manet-opt seed=8 num_nodes=20 pktrate=10 velocity=10
radio_range=250 alpha=0.5 pause_time=0 HelloInterval=2 RxmtInterval=7
DeadInterval=6 AckInterval=1000 BackupWaitInterval=500 TwoHopRefresh=3
AdjConnectivity=1 LSAFullness=1 diff_hellos start_time=1800 stop_time=3600
num_nodes is 20, 40, 60, 80, 100, 120, 160, 200
radio_range is 150, 200, 250
LSAFullness = 0 for minimal LSAs, 1 for min-cost LSAs, 4 for full LSAs.
AdjConnectivity = 1 for uniconnected adjacencies, 0 for full-topology adjacencies.
stop_time changed to 2700 when num_nodes is 100 or larger.
OSPF-MDR - 32