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
Document File: 3 page(s) / 34K

Publishing Venue

IBM

Related People

Bharath-Kumar, K: AUTHOR [+2]

Abstract

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Minimum Spanning Tree Approximation for Multi-Destination Routing

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. Minimal Spanning Tree (MST) Routing Overview. Given a network, a source node, and m destination nodes, the destination-induced network (DIN) is an m + 1 node network (one for each source and destination) with a connection between every pair of nodes and a weight assigned to each connection. The weight assigned between N and N1 is the number of links in the shortest path from N to N1. The DIN contains basic information needed to execute the MST algorithm. The source node may accumulate the DIN if it has access to a copy of the network topology, or it may request it from other nodes. Given the DIN, the source node chooses the entire specification of the routing by choosing which destinations to send to directly and choosing which of those destinations should forward the message to which other destinations. The routing chosen is the best possible routing if one uses only the DIN, namely, the Minimal Spanning Tree of the DIN. One additional improvement to the routing is possible while using the MST of the DIN by using the direct path optimization. For example, while sending a message on two different shortest paths, to different destinations, a node may discover that two paths coincide a portion of the way. In this case, only one copy of the message will be sent to the intermediate node where the bifurcation of the paths starts. Addressing Structure The addressing structure proposed is #Dest, Dest, #RI, and Routing Information, where # Dest: specifies how many immediate destinations

are listed infield Dest. Dest: lists the immediate destinations #RI: specifies the number of bytes in the Routing Information field. Routing Information: is a variable format field whic...