Browse Prior Art Database

Dynamically Balanced Data Routing Disclosure Number: IPCOM000113039D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 113K

Publishing Venue


Related People

Foster, RL: AUTHOR [+2]


Disclosed is an algorithm for dynamically determining an efficient routing of data packets for communication to maximize network throughput.

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

Dynamically Balanced Data Routing

      Disclosed is an algorithm for dynamically determining an
efficient routing of data packets for communication to maximize
network throughput.

      Current network technology has the ability to route data
through several different paths.  It has an understanding of traffic
load from a local point of view.  This paper will discuss data
routing that maintains both a local and a remote point of view.  A
specific implementation, namely the Fibre Channel Standard (FCS)
network, will be analyzed.  A simple FCS network is illustrated in
the Figure.  Note that the FCS network can be configured in a
point-to-point scheme, but this paper will discuss the more
interesting network that uses an FCS Fabric.

      For any network, there are 4 cases to examine that represent
the possible data routes from Host A to Host B. These routes are:

one to one,
   one to many,
   many to one, and
   many to many.

      In the cases where the remote host has many adapters, some
knowledge of the remote system is required to maximize network
throughput.  In light of that fact, this paper will examine
dynamically balanced data routing from the AIX* kernel level and the
adapter microcode level.

      Case: one to one.  This is the most trivial of the 4 cases.
There is only one route possible.  Data generated by a protocol in
Host A must travel through Adapter A to Adapter B and Host B.

      Case: one to many.  In this scenario, Host B has multiple
adapters, namely B1, B2, ..., Bn.  Adapter A has the ability to send
data to the adapters on Host B.  Using FCS as an example, Adapter A
has a knowledge of the busy conditions on Adapters B1, B2, ..., Bn.
It would be inefficient for Adapter A to communicate this information
to Host A in order to determine the best routing scheme.  Thus
selecting the best path for the data would be done at the adapter
microcode level.  The FCS adapter microcode would receive a list of
N_PORTs from HOST A for a given protocol.  In the Fibre Channel
Standard is the notion of credits.  When one adapter attempts to
communicate with another adapter, credits are granted in order to
control data flow.

      As an implementation example, an FCS adapter will use a first
no load algorithm to transmit its protocol segment.  Pseudocode logic
is illustrated in the following:

    FOR Adapters B1, B2,..., Bn
     IF (adapter can receive data)

Note that this algorithm does not maintain a history of
transmissions, so a round-robin algorithm must be implemented
elsewhere in order to obtain a balanced routing.

      The round-robin nature of the route must be implemented in the
operating system kernel.  For example, the AIX kernel has a layer
called the InterFace (IF) layer that controls routing to an Adapter
A1, A2,..., An on Host A. In this case, there is only one adapter to