Browse Prior Art Database

New Routing Algorithms for Large Interconnected Networks

IP.com Disclosure Number: IPCOM000108624D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 112K

Publishing Venue

IBM

Related People

Bar-Noy, A: AUTHOR [+2]

Abstract

Consider a super-network that is composed of n networks. Each network is autonomous and all nodes within a network have full knowledge about its topology. Networks are connected by boundary nodes which are the end-points of links connecting two networks. It is assumed that each node knows the weights of all the links connecting its network to the adjacent networks. In addition, all nodes know the connectivity structure of the super-network. Furthermore, we assume that every network in the super-network is always internally connected, i.e. there is a path from any node to any other node, such that the path is wholly contained inside the same network to which the nodes belong. We assume that source-routing is used in the network.

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

New Routing Algorithms for Large Interconnected Networks

       Consider a super-network that is composed of n networks.
Each network is autonomous and all nodes within a network have full
knowledge about its topology.  Networks are connected by boundary
nodes which are the end-points of links connecting two networks.  It
is assumed that each node knows the weights of all the links
connecting its network to the adjacent networks.  In addition, all
nodes know the connectivity structure of the super-network.
Furthermore, we assume that every network in the super-network is
always internally connected, i.e. there is a path from any node to
any other node, such that the path is wholly contained inside the
same network to which the nodes belong.  We assume that
source-routing is used in the network.  Thus, the sender of the
message selects the route and appends the route to the message and no
intermediate node can change it.

      In this article, we address the following question: how much
topology information about each network should be distributed to
other networks in order to achieve efficient routing?  We define
routing efficiency as the ration of the weight of the computed path
and that of the best path between two nodes.

      At one end of the spectrum of possibilities for routing in this
environment is the scheme (1) where each node keeps full information
about the distances (or shortest path weights) between every pair of
boundary nodes in each network (we refer to this as Strategy 1).  The
route computation to a remote node is performed by first computing a
path to the closest boundary node in the destination network (by
using the local topology database and the boundary node distances for
each network), and forwarding the packet to this node.  This boundary
node then computes the shortest path to the destination node using
its local topology. Alternatively, the collaboration protocol
described in (2) can be used to determine the particular boundary
node in the destination network that is on the optimal path.

      At the other end of the spectrum is a scheme which uses only
supernetwork connectivity information to route messages to nodes in
other networks (we refer to this as Strategy 5). This gives a path
which has the minimum number of super-network hops from the source to
the destination.  It is clear that the routing efficiency of this
path could be very poor when compared to the best path.

      We study a range of strategies between these two extremes which
provide us with some flexibility in achieving acceptable performance.
More specifically, we describe three new strategies in this article.
In Strategy 2, the maximum, the minimum and th...