Minimum Spanning Tree Approximation for Multi-Destination Routing
Original Publication Date: 1983-Nov-01
Included in the Prior Art Database: 2005-Feb-07
The problem of multi-destination routing and protocols to support it are set forth below. An algorithm for multi-destination routing, called Minimum Spanning Tree Routing, provides service that is superior to Direct Path Routing. Introduction In computer networks messages are routed from source nodes to destination nodes using routing tables. A typical routing table at a node specifies the next node on the shortest path to each destination. When transferring a file to multiple destinations, a basic approach is to send a single copy to all destinations, fanning out many copies only when necessary [*]. An addressing structure and an algorithm are described that exploit the structure to obtain better performance for large files in large networks. This algorithm is referred to as the Minimum Spanning Tree (MST) algorithm.