Distributed multicasting algorithm in a wide area network

ABSTRACT

This paper proposes a new multicasting algorithm that allows for message transfer from the source to the multicasting destination by using routing in the source. The routing algorithm uses a tree of trunks and nodes from the source to the multicasting destination. The bounds on the trunks and nodes occupancy are used to balance the occupancy of the trunks and nodes. The bounds on the number of trunks and nodes in the tree limit the number of paths considered by the algorithm. The message transfer time is calculated and the path with the shortest transfer time is chosen. The multicasting algorithm performance is analyzed by using the elapsed time of message transfer in the network and the waiting time to begin transfer in the nodes.

REFERENCES

• 1: Jo-Mei Chang , N. F. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.251-273, Aug. 1984 [doi>10.1145/989.357400]
• 2: J. Crowcroft , K. Paliwoda, A multicast transport protocol, Symposium proceedings on Communications architectures and protocols, p.247-256, August 16-18, 1988, Stanford, California, United States
• 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: S. E. Deering, Multicast routing in internetworks and extended LANs, Symposium proceedings on Communications architectures and protocols, p.55-64, August 16-18, 1988, Stanford, California, United States
• 5: G. N. Frederickson , R. Janardan, Space-Efficient and Fault-Tolerant Message Routing in Outerplanar Networks, IEEE Transactions on Computers, v.37 n.12, p.1529-1540, December 1988 [doi>10.1109/12.9731]
• 6: Jason Gait, A Kernel for High-Performance Multicast Communications, IEEE Transactions on Computers, v.38 n.2, p.218-226, February 1989 [doi>10.1109/12.16498]
• 7: J. Hagouel, "Source Routing and a Distributed Algorithm to Implement it," Proc. IEEE INFOCOM (April 1983)pp. 115-123.
• 8: K. G. Shin , M.-S. Chen, Performance analysis of distributed routing strategies free of ping-pong type looping, IEEE Transactions on Computers, v.36 n.2, p.129-137, Feb. 1987 [doi>10.1109/TC.1987.1676875]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Routing and layout

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

General Terms:
Algorithms, Verification