The InnovationQ application will be updated on Sunday, May 31st from 10am-noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

Minimum Spanning Tree Approximation for Multi-Destination Routing

IP.com Disclosure Number: IPCOM000047508D
Original Publication Date: 1983-Nov-01
Included in the Prior Art Database: 2005-Feb-07

Publishing Venue


Related People

Bharath-Kumar, K Jaffe, JM [+details]


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.