Efficient and reliable broadcast is achievable in an eventually connected network(Extended Abstract)

ABSTRACT

We deal with communication networks whose topology changes arbitrarily subject to the restriction that no edge-cut in the network persists forever. Up to now, no formal-ground rules have been proposed for such networks, and no protocol has been proved to possess any desirable property. We introduce a new proof methodology, in the sense that link-behavior in such networks is axiomatized. Our methodology is exemplified on broadcast protocols. A reliable broadcast protocol must deliver copies of a message to all nodes in a communication network, in finite time and in the correct order. No existing broadcast protocol with a reasonable cost is reliable, and in fact, one is inclined to believe that a communication protocol cannot be reliable, unless it knows in advances which links will fail in the future, or sends the information along all links. However, we present a new broadcast protocol which does achieve reliability with minimum cost. Moreover, in stable networks, minimum delay is achieved, too. As a by-product, we achieve a new reliable routing protocol. The main idea of our protocol is to perform the broadcast along a dynamic tree, such that the father of each node is the neighbor which has received the maximum number of messages. This guarantees that the tree will eventually reconnect each sub-network to its complement.

REFERENCES

• 1: B.Awerbuch, "A Reliable Broadcast Protocol", M.Sc. Dissertation, Electr. Eng. Depart., Technion, Haifa, July 1982 (in Hebrew).
• 2: E. Gafni and D.P. Bertsekas: "Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology", IEEE Trans. on Comm., Vol. COM-29, pp. 11-18, January 1981.
• 3: Yogen K. Dalal , Robert M. Metcalfe, Reverse path forwarding of broadcast packets, Communications of the ACM, v.21 n.12, p.1040-1048, Dec. 1978 [doi>10.1145/359657.359665]
• 4: Yogen Kantilal Dalal, Broadcast protocols in packet switched computer networks., 1977
• 5: J.Jaffe and F.Moss, "A Responsive Distributed Routing Protocol", IEEE Trans. on Comm., Vol. COM-30, No. 7, part II,pp. 1758-1762, July 1982.
• 6: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 7: J.M. McQuillan, I. Richer and E.C. Rosen, "The New Routing Algorithm for the ARPANET", IEEE Trans. on Comm., Vol. COM-28, No. 5, May 1980.
• 8: P. Merlin and A. Segall: "Failsafe Distributed Routing Protocol", IEEE Trans. on Comm., Vol. COM-27, pp. 1280-1288, September 1979.
• 9: A. Segall: "Distributed Network Protocols", IEEE Trans. on Inf. Theory, January 1983.
• 10: A. Segall and B. Awerbuch: "A Reliable Broadcast Protocol", IEEE Trans. on Comm. Vol. COM-31, No. 7, pp. 895-901, July 1983.
• 11: U.Vishkin, "A Distributed Orientation Algorithm", IEEE Trans. on Inf. Theory, June 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

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
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Performance