Transcript Study of Geographic Routing Protocols for MANETs

IDRM: Inter-Domain Routing
Protocol
for Mobile Ad Hoc Networks
C.-K. Chau, J. Crowcroft, K.-W. Lee, S. H.Y. Wong
Mobile Ad Hoc Networks
(MANET)
 Do not depend on infrastructural support
 A MANET is a mobile, multi-hop wireless network which is
capable of autonomous operation.
Easy to set up (possibly) a short-lived network for a collection
of nodes.
Characteristics
– Energy constrained nodes
– Bandwidth constrained
– Variable capacity wireless links
– Dynamic topology
Motivation
 BGP – Broader Gateway Protocol
 For inter-domain routing in Internet.
 Allows Autonomous Systems to communicate with each
other.
 Opaque Interoperation.
 GOAL- A BGP like solution for inter-domain routing for
MANETs
 Challenges in MANET
 Dynamic Topology Changes
 Newer MANET protocols
Existing Solutions
 BGP- Broader Gateway Protocol
 Why BGP fails in MANETs ?
 Path vector protocol Assumptions Internal Gateway Detection
 Internal Network Knowledge
 The above assumptions do not hold true for MANETs using
reactive/hybrid routing protocols.
 IP prefix aggregation
 BGP Aggregates IP addresses in the domain by IP prefixes (e.g.,
92.168.0.0/16).
 Creation of arbitrary network partitions and merges in MANETs
 IP prefixes may not suitably aggregate the IP addresses in
partitioned MANETs.
Existing Solutions
 Loop detection in Path vector protocol
 Filters path that contain repeated AS numbers.
 May fail in MANETs.
Existing Solutions
 Plutarch and Turfnet
 focus on high level architecture rather than provide a
practical solution to the problem
 SHARP
 uses hybrid routing protocols
 Cluster-based networking
 Self organizing clusters
 Routing backbone among cluster heads
Focuses on single-domain
IDRM
 Modelled on BGP
 Main Feature – Opaque Interoperation
 Allows heterogeneous intra-domain routing protocols
 Allows heterogeneous inter-domain routing policies
 Key Design Points
 Handling Domain level Topology changes
 How to discover partitions and merges?
 IDRM proposes periodic internal gateway detection
 Proactive routing domain- partitions discovered using
route updates
 Reactive routing domain- Maintain soft state by sending
beacons periodically.
 Generate new MANET ID on partition discovery
IDRM
 Computation of MANET ID
 Goal is for each gateway to generate the ID and that the
collision of IDs is low.
 Generate random ID using pseudo random generator with
the IDs of all the gateways as input
 Prefix it by the domain ID to generate a new MANET ID
 Why prefix domain ID ?
 Merging of network partitions
The dynamic allocation of MANET ID prevents the path
vector protocol from detecting a false loop.
IDRM
 Membership Management and Announcement
 Gateway nodes collect the IDs of all the nodes in the
MANET for advertisement to other domains
 Membership Digest
 Contains node ID information(IP address)
 Non-gateway membership
 Proactive routing domain- membership information is
available through the update messages
 Reactive routing domain- initiate membership query
 Policy Support
 Encoding of the domain ID in MANET ID
IDRM
 Data Plane Operations
 A node sends packet to one of the reachable intra-domain
gateway
 A route discovery is initiated in the case of reactive
domain to find the gateway node which has the route to
the destination
 Once the packet reaches the intra-domain gateway, it
checks to see if it is directly connected to the destination,
if it is connected it forwards the packet to the destination.
 If not, the packet is forwarded to the gateway which has
the route to the destination
IDRM- Illustration
 Domain Policies
 A is willing to provide transit service for B, but not for C,
 B,C are willing to provide transit service for others.
IDRM- Illustration
IDRM- Illustration
IDRM- Illustration
 A1 wants to send packets to a0
 Proactive(OLSR)- Based on Link state information a1 know that both the
destination a0 and default gateway a3 are disconnected from the MANET.
 Reactive(DSR) – initiate route discovery, a2 responds
 Forward packet to reachable gateway a2
 A2 forwards the packet to b2
Performance Evaluation
Overhead Analysis
 Proactive Intra-Domain Routing Protocol

= # of hello packets/sec
 Reactive Intra-Domain Routing Protocol


= beaconing rate between pair of gateways
= avg 3 of hops between a pair of nodes
 Inter Domain Routing Protocol
Overhead Analysis

= Connectivity breakage rate of connected pairs of
intra-domain gateways
Limitations
 Scalability
 BGP – Scalable
 IDRM – not scalable
 Isolation of nodes
 Special Hardware requirements
 Multiple radio channels
 Different technology
 Gateway nodes require special hardware
 Computation Overhead
 MANET ID computation
Limitations
 Not Stateless
 Security Issues
 The route updates are not secured
 distribution of IDs of all the nodes and gateways
within its own domain
 requires special mechanism to discover the node IDs
and then pass on this information to other nodes
Conclusion
 IDRM offers a means for heterogeneous MANETs to
interoperate
 Identified challenges of inter-domain routing in MANETs
 Established feasibility of opaque interoperation in IDRM
 IDRM retains the merits of BGP
 Future research direction
References
 C.-K. Chau, J. Crowcroft, K.-W. Lee, S. H.Y. Wong, IDRM:Inter-domain
Routing Protocol for Mobile Ad Hoc Networks.Computer Lab, University of
Cambridge. Technical Report UCAM-CL-TR-708
 Y. Rekhter and T. Li. RFC 1771: a Border Gateway Protocol 4 (BGP-4),
March 1995.
 J. Crowcroft et. al.. Plutarch: an argument for network pluralism. ACM
Computer Communication Review, 33(4):258–266, 2003.
 S. Schmid et al. TurfNet: An architecture for dynamically composable
networks. In Proc. of WAC 2004, October 2004.
 Y. Chen, A. Liestman, J. Liu. Clustering algorithms for ad hoc wireless
networks. In Proc. Ad Hoc and Sensor Networks ’04
 V. Ramasubramanian, Z. J. Haas, and E. G. Sirer. SHARP: A hybrid adaptive
routing protocol for mobile ad hoc networks.In Proc. ACM MOBIHOC, June
2003.