Lazy flooding: a new technique for information dissemination in distributed network systems

ABSTRACT

Flooding is a commonly used technique for network resource and topology information dissemination in the data communication networks. However, due to the well-known N-squared problem it causes network delay in response or even congestion. We propose a new flooding technique, called Lazy Flooding; it floods only when links reach a certain status. It significantly cuts down the number of floods and thus improves the data communication network response time. On the other hand, it has negligible effect on the network performance due to the selected flooding.

REFERENCES

• 1: [1] A. Aho and D. Lee, "Hierarchical networks and the LSA N-squared problem in OSPF routing," presented at the GLOBECOM 2000 San Francisco, CA.
• 2: J. Moy, OSPF Protocol Analysis, RFC Editor, 1991
• 3: Roche A. Guérin , Ariel Orda, QoS routing in networks with inaccurate information: theory and algorithms, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.350-364, June 1999 [doi>10.1109/90.779203]
• 4: [4] G. Liu, C. Ji, and V. Chen, "Network management information for light path assessment: Trade-off between performance and complexity," in Proc. IEEE INFOCOM, 2003, pp. 1362-1372.
• 5: Jochen Behrens , J. J. Garcia-Luna-Aceves, Distributed, scalable routing based on link-state vectors, Proceedings of the conference on Communications architectures, protocols and applications, p.136-147, August 31-September 02, 1994, London, United Kingdom
• 6: [6] H. Fujinoki and K. J. Kristensen, "The Directed Reverse Path Join (DRPJ) Protocol: An Efficient Multicast Routing Protocol," Comput. Commun., vol. 24, no. 12, pp. 1121-1133, Jul. 2001.
• 7: Ken Carlberg , Jon Crowcroft, Building shared trees using a one-to-many joining mechanism, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.5-11, Jan. 1997 [doi>10.1145/251007.251008]
• 8: Stephen E. Deering , David R. Cheriton, Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.85-110, May 1990 [doi>10.1145/78952.78953]
• 9: Sung-Ju Lee , William Su , Mario Gerla, Wireless ad hoc multicast routing with mobility prediction, Mobile Networks and Applications, v.6 n.4, p.351-360, Aug. 2001 [doi>10.1023/A:1011478628358]
• 10: Hyojun Lim , Chongkwon Kim, Multicast tree construction and flooding in wireless ad hoc networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.61-68, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346865]
• 11: George Apostolopoulos , Roch Guérin , Sanjay Kamat , Satish K. Tripathi, Quality of service based routing: a performance perspective, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.17-28, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 12: Anees Shaikh , Jennifer Rexford , Kang G. Shin, Evaluating the impact of stale link state on quality-of-service routing, IEEE/ACM Transactions on Networking (TON), v.9 n.2, p.162-176, April 2001 [doi>10.1109/90.917073]
• 13: [13] "Optical Network Management Protocol," Tech Memo. Bell Labs, 2001.
• 14: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 15: [15] D. G. Kendall, "Some problems in the theory of queues," J. Royal Statistical Soc., ser. Serial B, vol. 13, pp. 151-185, 1951.
• 16: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 17: Wayne D. Grover, Mesh-based Survivable Transport Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking, Prentice Hall PTR, Upper Saddle River, NJ, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Design, Performance

Keywords:
flooding, link state advertisement, optical networks, routing