Routing Broadcast Packets Along a Minimum Diameter Tree

Abstract

In traditional computer networks, such as X.25 and TCP/IP networks, packets generally traverse the lowest cost route going from one source to one destination. In recent years, new classes of computer and video services have emerged that transfer multiple copies of a packet from one source to many destinations (multicast or broadcast).

This paper models the broadcast routing problem in a mesh computer network as a graph theory problem with a cost function that has to be minimized. The paper proposes a new criterion for routing broadcast packets when each node in the network may be a source of broadcast packets directed to the other nodes. Constraining broadcast packets to follow a single spanning tree, it is shown that a minimum diameter spanning tree is a suitable choice for routing purposes. A heuristic for generating a minimum diameter spanning tree is presented.