Browse Prior Art Database

Dynamic Determination of Network Topology

IP.com Disclosure Number: IPCOM000115144D
Original Publication Date: 1995-Mar-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 8 page(s) / 321K

Publishing Venue

IBM

Related People

Beaven, PA: AUTHOR [+2]

Abstract

A computer network consists of a set of computers (nodes) interconnected by communication links. A fundamental problem encountered when programs running on the nodes need to communicate (exchange messages) with each other, is the so-called "routing problem". A node in the network will have communication links with one or more "neighboring" nodes and the routing problem becomes that of selecting which outgoing link to send the message along, in order to reach the required destination. Clearly, if there is only one outgoing link the decision is trivial, but depending on the network topology, there may be many outgoing links to choose from and the problem is more complex.

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

Dynamic Determination of Network Topology

      A computer network consists of a set of computers (nodes)
interconnected by communication links.  A fundamental problem
encountered when programs running on the nodes need to communicate
(exchange messages) with each other, is the so-called "routing
problem".  A node in the network will have communication links with
one or more "neighboring" nodes and the routing problem becomes that
of selecting which outgoing link to send the message along, in order
to reach the required destination.  Clearly, if there is only one
outgoing link the decision is trivial, but depending on the network
topology, there may be many outgoing links to choose from and the
problem is more complex.

      A given node may not be directly connected to very other node
in the network, and can only send messages to a remote computer via
one or more intermediate nodes.  Hence, at each node on the path
between the originating node and the destination, a routing decision
has to be made, in order to forward the message.

      Usually the routing decision at a given node is determined by
consulting a local routing table, where the table contains
information relating to the topology of the network.  In its simplest
form the table just indicates which outgoing path is appropriate for
the destination in question.  Hence, for each node the routing
problem becomes that of deciding how to obtain the information to be
loaded into the local routing table.  An additional factor is that
the network topology may change, either by design, or as the result
of a failure.  In either case the routing tables at the network nodes
may need to be updated and this compounds the routing problem.

      The approach to the routing problem described below is
particularly suitable for message queuing technology such as that
found in the IBM queue manager products known as the MQSeries*.

      It is assumed that each node in the network has a Route
management program which implements the following algorithm:
  Algorithm
  1.  Set up an initial "connectivity table" which identifies just
the
       immediate neighbors of the local node.  (The connectivity
table
       contains more information than a simple routing table and is
       described in detail below.)
  2.  When stimulated by a "routing test event" -
      a.  Note the arrival time.  Use thiis time plus T to set an
           expiry time to be used in messages that are sent during
this
           step of the algorithm.  (T is a preset parameter that is
used
           as a timeout value).
      b.  Prepare a message for each neighbor, that contains details
of
           what nodes can be reached via the local node.  (Note that
in
           preparing information for a given neighbor, the route to
that
           neighbor, is not included.)  These messages contain the
 ...