Using novel distributed heuristics on hexagonal connected dominating sets to model routing dissemination

ABSTRACT

As future wireless networks become more diverse, there are important performance limits when network conditions become more extreme. An important performance limit in dense networks is the scalability of routing and of topology updates dissemination in particular. In previous work [16], the expected performance of diverse approaches to topology update schemes using flat flooding, Multi-Point relays (MPRs), and Connected Dominating Sets (CDSs), has been modeled and analyzed. Analysis showed that one representative of the analyzed CDS models, the CDS-based Hexagon one, offered order of magnitude less overhead in dense networks with a small increase in routing stretch. To our knowledge, other existing distributed CDS heuristics cannot match the performance of this model. In this work, we are advancing the CDS-HEX topology dissemination approach from the limited-scope centralized scenarios with strict symmetrical relays placement to any general dynamic scenario with totally random placement of nodes. We propose novel heuristics to approximate the theoretically optimal CDS-HEX for dynamic environments. We are showing that: a) although the distributed scheme operates sub-optimally compared to its centralized ancestor, it is still superior to the MPR scheme in key metrics, b) the set-up overhead of the more sophisticated distributed CDS-HEX is not significantly higher than this of MPRs, while the steady state overhead of CDS-HEX turns to be lower, and c) simulations verify all the closed analytical formulae and asymptotic results of previous analysis and provide additional insight on metrics that cannot be analytically measured.

REFERENCES

• 1: S. Bohacek, "A Component-Based Performance Model of a Generalized OLSR," ARL-CTA TR, Sept.'07.
• 2: Philippe Jacquet , Pascale Minet , Paul Mühlethaler , Nicolas Rivierre, Increasing Reliability in Cable-Free Radio LANs Low Level Forwarding in HIPERLAN, Wireless Personal Communications: An International Journal, v.4 n.1, p.51-63, January 1997 [doi>10.1023/A:1008861218989]
• 3: A. Laouiti, A. Qayyum, L. Viennot, "Multipoint relaying: an efficient technique for flooding in mobile wireless networks," In 35th HICSS'01, IEEE Computer Society, '01.
• 4: C. Adjih, P. Jacquet, LViennot, "Computing connected dominated sets with multipoint relays", http://www.inria.fr/rrrt/rr-4597.html, 2002.
• 5: T. Clausen , P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC Editor, 2003
• 6: T. Clausen, C. Dearlove, P. Jacquet, "The Optimized Link State Routing protocol version2," draft-ietf-manet-olsrv2-04.txt, July' 07.
• 7: T. Clausen, C. Dearlove, J. Dean, C. Adjih, "Generalized MANET Packet/Message Format, "draft-ietf-manet-packetbb-09.txt, Sep. '07.
• 8: T. Clausen, C. Dearlove, "Representing multi-value time in MANETs", draft-ietf-manet-timetlv-01.txt, June '07.
• 9: T. Clausen, C. Dearlove, B. Adamson, "Jitter considerations in MANET," work in progress draft-ietf-manet-jitter-01.txt, June'07
• 10: J. Moy, "OSPF Version 2," RFC 2328, April 1998.
• 11: R. Coltun , D. Ferguson , J. Moy, OSPF for IPv6, RFC Editor, 1999
• 12: M. Chandra, A. Roy, "Extensions to OSPF to support mobile ad hoc networking," draft-chandra-ospf-manet-ext-05, Aug. '07.
• 13: R. Ogier, P. Spagnolo, "MANET Extension of OSPF using CDS Flooding," draft-ogier-manet-ospf-extension-09.txt, March 2007.
• 14: M. Striki, A. McAuley, R. Morera, "Topology Dissemination and Representation for Link State Routing Protocol: Alternatives to OLSR and OSPF", ARL-CTA 1 TR, Sept.'07.
• 15: M. Striki, "Using Novel Distributed Heuristics on Hexagonal Connected Dominating Sets to model Routing Dissemination," ARL-CTA TR, Dec. '08.
• 16: M. Striki, A. McAuley, R. Morera, "Modeling Topology Dissemination for Routing in Future Force Networks", MILCOM'08, San Diego, California, 19--24 Nov. 2008.
• 17: Philippe Jacquet , Anis Laouiti , Pascale Minet , Laurent Viennot, Performance of Multipoint Relaying in Ad Hoc Mobile Routing Protocols, Proceedings of the Second International IFIP-TC6 Networking Conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; and Mobile and Wireless Communications, p.387-398, May 19-24, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Documentation, Experimentation, Measurement, Performance, Reliability, Theory, Verification

Keywords:
analysis, connected dominating sets, distributed routing, hexagons, routing dissemination, routing overhead, simulations, stretch