Browse Prior Art Database

Trade-Off Optimization for Multi-Destination Routing

IP.com Disclosure Number: IPCOM000047509D
Original Publication Date: 1983-Nov-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 36K

Publishing Venue

IBM

Related People

Bharath-Kumar, K: AUTHOR [+2]

Abstract

A multi-destination routing procedure is proposed for achieving a trade-off between a Direct Path (DP) algorithm, which minimizes the delay in routing messages to multiple destinations at the cost of utilizing more than the optimum number of link traversals, and a Minimum Spanning Tree (MST) algorithm, which minimizes the number of link traversals used at the cost of increased routing delays, the objective of this procedure being to provide the best network utilization consistent with good user satisfaction. In computer networks, messages are routed from source nodes to destination nodes by the use of routing tables. A typical routing table at a node specifies the next node on the shortest path to each destination. When sending a message from a source to multiple destinations, two approaches may be considered.

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

Trade-Off Optimization for Multi-Destination Routing

A multi-destination routing procedure is proposed for achieving a trade-off between a Direct Path (DP) algorithm, which minimizes the delay in routing messages to multiple destinations at the cost of utilizing more than the optimum number of link traversals, and a Minimum Spanning Tree (MST) algorithm, which minimizes the number of link traversals used at the cost of increased routing delays, the objective of this procedure being to provide the best network utilization consistent with good user satisfaction. In computer networks, messages are routed from source nodes to destination nodes by the use of routing tables. A typical routing table at a node specifies the next node on the shortest path to each destination.

When sending a message from a source to multiple destinations, two approaches may be considered. The DP routing algorithm (described in
[*]) causes copies of the message to be sent by the shortest paths from the source to the respective destinations, without regard to the number of link traversals, and in those instances where a node N is on the shortest path to several destinations, the addressing structure specifies that the message shall be forwarded by N to the several destinations. The MST algorithm (described in the preceding article) endeavors to choose routes which will minimize the number of link traversals used, even though this may cause some destinations to receive their copies of the message through paths other than the shortest ones, thereby delaying such messages. To obtain better delay performance, given the MST routing, the trade-off procedure herein proposed finds the destination whose delay performance is degraded most by the MST routing and changes its route to the optimal delay route as determined by DP routing. This can be repeated to achieve the desired delay performance at the cost of link utilization, without totally sacrificing either criterion for the other. Let s be the source node in a network, D the destination node set, and m the number of elements in D. The following represents m different trade-off algorithms, parameterized by the va...