|
 ABSTRACT
A broadcast packet is for delivery to all nodes of a network. Algorithms for accomplishing this delivery through a store-and-forward packet switching computer network include (1) transmission of separately addressed packets, (2) multidestination addressing, (3) hot potato forwarding, (4) spanning tree forwarding, and (5) source based forwarding. To this list of algorithms we add (6) reverse path forwarding, a broadcast routing method which exploits routing procedures and data structures already available for packet switching. Reverse path forwarding is a practical algorithm for broadcast routing in store-and-forward packet switching computer networks. The algorithm is described as being practical because it is not optimal according to metrics developed for its analysis in this paper, and also because it can be implemented in existing networks with less complexity than that required for the known alternatives.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Baran, P., Boehm, S., and Smith, P. On Distributed Communication. Tech. Rep., Vol. 1-9, Rand Corp., Santa Monica, Calif., 1964.
|
| |
2
|
Cerf, V.G. Obtaining broadcast communication from nonbroadcast transmission media. Private communication, Sept, 1976.
|
 |
3
|
B. P. Cosell , P. R. Johnson , J. H. Malman , R. E. Schantz , J. Sussman , R. H. Thomas , D. C. Walden, An operational system for computer resource sharing, Proceedings of the fifth ACM symposium on Operating systems principles, p.75-81, November 19-21, 1975, Austin, Texas, United States
|
| |
4
|
|
| |
5
|
Danthine, A.A.S., and Eschenauer, E.C. Influence on packet node behavior of the internode protocol. 1EEE Trans. Comm. COM- 24, 6 (June 1976), 606-614.
|
| |
6
|
Farber, D.J., and Larson, K,C. The structure of a distributed computing system--the communication system. Proc. Symp. Computer-Communications Networks and Traffic, Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., April 1972, pp. 21-27.
|
| |
7
|
|
| |
8
|
|
| |
9
|
Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
|
| |
10
|
|
| |
11
|
|
| |
12
|
McQuillan, J.M. Adaptive routing algorithms for distributed computer networks. Ph.D. Th., Harvard, BBN Rep. 2831, May 1974; available as AD781467, N.T.I.S., Springfield, Va.
|
| |
13
|
Paoletti, L.M. AUTODIN. In Computer Communication Networks, R.L. Grimsdale and F.F. Kuo, Eds. (Proc. NATO Advanced Study Inst. Comptr. Comm. Networks, Sussex, U.K., Sept. 1973), Noordoff Int. Publ., Leyden, 1975.
|
| |
14
|
Roberts, L.G., and Wessler, B.D. The ARPA computer network. In Computer Communication Networks, N. Abramson and F. Kuo, Eds., Prentice-Hall, Englewood Cliffs, N.J., 1972.
|
CITED BY 61
|
|
|
|
|
Lawrence C. N. Tseung , Keh-Chiang Yu, The implementation of guaranteed, reliable, secure broadcast networks, Proceedings of the 1990 ACM annual conference on Cooperation, p.259-265, February 20-22, 1990, Washington, D.C., United States
|
|
|
B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cory J. Hoelting , Dale A. Schoenefeld , Roger L. Wainwright, A genetic algorithm for the minimum broadcast time problem using a global precedence vector, Proceedings of the 1996 ACM symposium on Applied Computing, p.258-262, February 17-19, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
Stephen Deering , Deborah L. Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, The PIM architecture for wide-area multicast routing, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.153-162, April 1996
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stephen Deering , Deborah Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, An architecture for wide-area multicast routing, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.126-135, Oct. 1994
|
|
|
|
|
|
|
|
|
|
|
|
Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
Antonio Carzaniga , Alexander L. Wolf, Forwarding in a content-based network, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mohammad Hosseinabady , Abbas Banaiyan , Mahdi Nazm Bojnordi , Zainalabedin Navabi, A concurrent testing method for NoC switches, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
|
|
|
|
|
|
|
|
|
Dejan Kostić , Alex C. Snoeren , Amin Vahdat , Ryan Braud , Charles Killian , James W. Anderson , Jeannie Albrecht , Adolfo Rodriguez , Erik Vandekieft, High-bandwidth data dissemination for large-scale distributed systems, ACM Transactions on Computer Systems (TOCS), v.26 n.1, p.1-61, February 2008
|
|
|
Ling-Jyh Chen , Chen-Hung Yu , Tony Sun , Yung-Chih Chen , Hao-hua Chu, A hybrid routing approach for opportunistic networks, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.213-220, September 11-15, 2006, Pisa, Italy
|
|
|
Teijiro Isokawa , Shin'ya Kowada , Yousuke Takada , Ferdinand Peper , Naotake Kamiura , Nobuyuki Matsui, Defect-tolerance in cellular nanocomputers, New Generation Computing, v.25 n.2, p.171-199, November 2007
|
|
|
Jaime Lloret , Miguel Garcia , Diana Bri , Juan R. Diaz, A group-based content delivery network, Proceedings of the third international workshop on Use of P2P, grid and agents for the development of content networks, June 23-23, 2008, Boston, MA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jun Li , Jelena Mirkovic , Toby Ehrenkranz , Mengqiu Wang , Peter Reiher , Lixia Zhang, Learning the valid incoming direction of IP packets, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.2, p.399-417, February, 2008
|
|
|
|
INDEX TERMS
Primary Classification:
G.
Mathematics of Computing
G.2
DISCRETE MATHEMATICS
G.2.2
Graph Theory
Subjects:
Path and circuit problems
Additional Classification:
C.
Computer Systems Organization
C.2
COMPUTER-COMMUNICATION NETWORKS
C.2.1
Network Architecture and Design
Subjects:
Packet-switching networks
F.
Theory of Computation
F.2
ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2
Nonnumerical Algorithms and Problems
Subjects:
Routing and layout
General Terms:
Algorithms,
Design,
Measurement,
Performance,
Standardization,
Theory
Keywords:
broadcast packets,
broadcast protocols,
computer networks,
reverse path forwarding,
routing,
store-and-forward packet switching
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf