Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Unique Assignment of Link Weights

IP.com Disclosure Number: IPCOM000110257D
Original Publication Date: 1992-Nov-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 81K

Publishing Venue

IBM

Related People

Bodner, RA: AUTHOR [+8]

Abstract

A spanning tree consists of nodes (i.e., network control processor) and edges. An edge is a link (i.e., transmission medium) that is part of the spanning tree.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Unique Assignment of Link Weights

       A spanning tree consists of nodes (i.e., network control
processor) and edges.  An edge is a link (i.e., transmission medium)
that is part of the spanning tree.

      It is also assumed that there is a representation of the
network's topology (i.e., nodes and links) that is replicated at
every node, and which is dynamically updated with messages that are
termed topology updates.  Each link and edge in this representation
is a composite of a pair of unidirectional links or edges between the
two nodes at either end of the link or edge.

      Some distributed algorithms that build and maintain a spanning
tree in a communications network require all links in the network to
have unique weights and require all nodes to agree on the weights.
This agreement allows such an algorithm to merge two spanning trees
using the potential edge (i.e., a link connecting the two spanning
trees) with highest weight.  While this agreement could be ensured
through administrative procedures, it is desirable to assign link
weights in a manner that avoids administrative coordination at
multiple nodes.

      To solve this problem without coordinated predefinition, each
node has the capability to determine which link has the highest
weight.  Instances of this algorithm executing in different nodes
have the ability to chose the same link in a dynamically changing
configuration.

      In this article, it is assumed that all nodes in a network have
unique names.  Most networking architectures require unique node
names for many reasons, including network management; thus this
algorithm does not impose a new administrative burden but takes
advantage of existing inf...