Multiple path routing mechanism for packet communications network

A mechanism for establishing at least one transmission route between a source node and a destination node in a multinode communications network comprises monitoring transmission characteristics of each of the transmission paths among the respective nodes of the network so as to derive a plurality of path metrics representative of the ability of the respective transmission paths of the network to transmit communication signals. Then, feasible transmission routes to be used for the transmission of communication signals from the source node to the destination node are selected as those routes which extend from the source node to the destination node and each of which is comprised of one or more transmission paths among the nodes of the network and the sum of path metrics of transmission paths from neighboring nodes to the destination node is less than the path metric of a transmission path the end nodes of which correspond to the source and destination nodes. Communication signals are then transmitted from the source node to the destination node over the selected feasible transmission routes.

FIELD OF THE INVENTION 
The present invention relates in general to communication systems and is 
particularly directed to a scheme for near optimally routing digital data 
traffic among member nodes of a multinode packet-switched communications 
network in the presence of dynamic transmission path conditions. 
BACKGROUND OF THE INVENTION 
Path selection schemes for routing digital data traffic among member 
stations or nodes of a multinode packet-switched communications network 
typically employ some form of shortest path or minimal delay mechanism 
(commonly termed a path or link metric) for determining which route is to 
be used to transmit data from source to destination. One such scheme, 
known as ARPANET (described in an article entitled "The New Routing 
Algorithm for the ARPANET" IEEE Transactions on Communications, Vol. 
COM-28, May 1980, pp. 711-719), examines the path metrics of all possible 
links between source and destination and selects that path through the 
network whose total link metric total represents the lowest transmission 
delay. By always basing its routing decision on the shortest path metric, 
the ARPANET approach tends to introduce a substantial load imbalance among 
the nodes and subjects the shortest path to considerable traffic 
congestion. 
To take advantage of the substantial capacity of the network that goes 
unused in an ARPANET type of scheme, there has been proposed an optimal 
traffic assignment mechanism in which all paths through the network are 
employed in an effort to minimize that average delay through the network, 
as described in an article entitled "A Minimum Delay Routing Algorithm 
Using Distributed Computation" by R. G. Gallager, IEEE Transactions on 
Communications Vol. COM-25, January 1977, pp. 73-85. In accordance with 
this optimal traffic assignment approach traffic from a source is 
subdivided into subportions which, in turn, are routed over a number of 
different source-to-destination highways. As traffic is subdivided and 
allocated to the different paths through the network the average delay of 
the respective links is examined and adjustments are made (traffic is 
selectively moved to links having lower path delays) so as to iteratively 
converge upon an optimal (lowest) average delay through the network. While 
this latter approach improves upon the use of the resources of the 
network, producing a low steady state delay, it is not readily suited for 
use in a dynamic environment where the connectivity among nodes is subject 
to unpredictable transient degradation or failure. 
SUMMARY OF THE INVENTION 
In accordance with the present invention there is provided a new and 
improved routing mechanism for use in a multinode communication network 
which obviates the drawbacks, yet enjoys the desirable attributes of the 
ARPANET and optimal traffic allocation schemes described above, namely 
speed and maximal use of entire network capacity. To this end the routing 
mechanism of the present invention examines the path metrics of all paths 
that extend from a source node to a destination node. Using the metric of 
the shortest path between the source node and the destination node as a 
reference, the metrics of all the shortest paths from all neighboring 
nodes to the destination node are examined to determine which path, if 
any, yields a metric total that exceeds the reference. A path whose metric 
exceeds that of the reference is eliminated as a possible candidate path 
for routing transmissions between the source and destination nodes. As a 
result, any path that includes a node which is located farther away from 
the destination node than the source node is eliminated as a candidate. 
(This requirement guarantees consistent routes without any loops). 
Once all the `non-feasible` candidate paths have been eliminated, the 
metrics of the remaining `feasible` paths are employed to allocate the 
distribution of traffic between the source node and the destination node 
over all the feasible paths in inverse proportion to the path metric of 
each respective feasible path. As a consequence of this traffic allocation 
process, loading of the feasible paths of the network is effectively 
balanced with minimum average delay. 
In accordance with a further aspect of the present invention, in the event 
of a connectivity failure within the network, the routing mechanism takes 
immediate action to make whatever adjustments to the presently employed 
routing scheme are necessary, so as to insure that the transmission of 
traffic through the network, is, at all times, effectively nearly 
optimally routed. For this purpose, incorporated into the routing 
mechanism is an `event-driven` failure recovery procedure which reassigns 
the routing of traffic from a source node to a destination node by 
coordinating with other nodes in the rerouting process. 
Pursuant to a further feature of the present invention, the routing and 
traffic allocation mechanism may be applied to networks that have been 
configured to operate as virtual circuits or for a network configured to 
provide both datagram and virtual circuit capability. Virtual circuit 
routing is effected in substantially the same manner as the datagram 
mechanism, wherein a loop-free feasible path to the destination is 
defined. This route, preferably having a lowest possible path metric 
total, over which the data packet traffic travels, becomes a permanent 
virtual circuit route. The routing variables that are established in 
accordance with the path metrics are used to select from among feasible 
paths at each node. The route selection process distributes the load, so 
that the average load carried by the virtual circuit approximates the 
distribution implied by the routing variables. The virtual circuit route 
from source to destination will remain dedicated for that purpose until 
rerouting is required, either due to a link failure along the route or due 
to traffic congestion.

DETAILED DESCRIPTION 
Before describing in detail the particular improved network 
management/routing scheme in accordance with the present invention, it 
should be observed that the present invention resides primarily in a novel 
routing mechanism for controlling the connectivity of the member nodes of 
a communication network employing conventional communications circuits and 
components and not in the particular detailed configurations thereof. 
Accordingly, the structure, control and arrangement of these conventional 
circuits and components have been illustrated in the drawings by readily 
understandable block diagrams which show only those specific details that 
are pertinent to the present invention, so as not to obscure the 
disclosure with structural details which will be readily apparent to those 
skilled in the art having the benefit of the description herein. Thus, the 
block diagram illustrations of the Figures do not necessarily represent 
the mechanical structural arrangement of the exemplary system, but are 
primarily intended to illustrate the major structural components of the 
system in a convenient functional grouping, whereby the present invention 
may be more readily understood. 
For purposes of providing an illustrative example, in the description to 
follow, the communications environment to which the present invention is 
applied is assumed to be a satellite communications system comprised of a 
plurality of communications satellites interlinked with one another and 
with a plurality of associated ground stations. However, it should be 
realized that the invention is not limited to use with this particular 
network or to satellite communications systems only, but is applicable to 
any multinode network in which communications between source and 
destination nodes may take place over multiple routes through the nodes of 
the network. It should also be observed that the network topology can be 
either dynamic (network topology changes with time) or static (network is 
effectively time invariant). 
As pointed out above, the present invention is particularly advantageous 
when incorporated in a communications network where its topology is 
dynamic (e.g. multiple moving vehicle (aircraft, spacecraft, ships and 
land vehicles) where participants (member nodes), distances between nodes 
and links between nodes may vary with time and, consequently, require a 
network routing mechanism that is capable of effectively tracking, in real 
time, changes in network topology, and does not require long periods of 
time (a multiple iteration convergence procedure, as in the 
above-referenced Gallager technique) to accomplish near optimal routing of 
data communications traffic among member nodes. 
In the satellite communications system diagrammatically illustrated in FIG. 
1, a plurality of geographically distributed terrestrial (ground) stations 
GS communicate with one another by means of a multiplicity of 
communication satellites SAT via respective ground-to-satellite (or 
satellite-to-ground) communication paths or links L.sub.GS and 
satellite-to-satellite communication links L.sub.SAT. Namely, the ground 
stations GS and the satellites SAT correspond to the network nodes which 
are linked to one another via transmission paths L.sub.GS and L.sub.SAT. 
Each node (whether it be a ground station GS or a communications satellite 
SAT) contains conventional transceiver, tracking and acquisition and 
signal processing equipment shown in block diagram form in FIG. 2. 
More particularly FIG. 2 illustrates a typical node block diagram the 
central element of which is a packet switch 20 within which the routing 
mechanism is implemented. Coupled with communications bus 23 of packet 
switch 20 (via interface unit 24) is a host computer system 30 which 
executes user processes and is the source and destination of all user 
data. The packet switch either delivers data packets to the host computer 
or it relays the packet to another node. Packet communication is typically 
effected by using a set of layered protocols similar to the seven-layer 
International Standards Organization (ISO) reference model of Open System 
Interconnection (OSI), Data link control is illustrated in FIG. 2 as a 
low-level function of layer 2 of the ISO reference model and serves to 
provide error-free transmission of packets. The data link control may be 
implemented using a standard synchronous data link communication protocol. 
For a more detailed explanation of this seven layer model, as well as a 
number of standard protocols that may be employed in accordance with the 
present invention attention may be directed to the textbook "Computer 
Networks" by Andrew S. Tanenbaum, Prentiss-Hall, Inc. 1981. 
The basic control element within packet switch 20 is a general purpose 
computer referenced in the Figure as control processor 21. Control 
processor 21 is primarily responsible for executing the network layer 
(layer 3) protocols. The network layer is the layer in which the packet 
routes are determined. The adaptive routing mechanism described below is 
executed by control processor 21. 
Associated with control processor 21 is a random access memory 22 in which 
packet buffers, control software and routing tables reside. Memory 22 
provides temporary storage for packets while control processor 21 is 
deciding whether to deliver a packet to host computer 30 or to forward the 
packet to another node. The decision is based upon the address in the 
packet header. As will be explained in detail below, the data link to be 
used for forwarding a packet to another node is selected by looking up the 
best route in the routing table (updated periodically and in the event of 
a link failure) for the destination address in question. 
In addition to the control mechanism FIG. 2 also shows conventional 
satellite communications equipment, which makes up the physical layer 
(layer 1) of the node, in the form of a transceiver unit 40 that contains 
transmitter, receiver, modulator and demodulator units and TT&C (tracking, 
telemetry and control) units interfaced with the packet switch through 
conventional data link control components. As the details of the 
configuration and operation of such equipment are unnecessary for gaining 
an understanding of the present invention they will not be described here. 
Instead, attention may be directed to standard communication texts such as 
"Digital Communications by Satellite" by J. J. Spilker, Prentice-Hall, 
1977. Carrier and bit synchronization may be effected using conventional 
mechanisms using phase-locked loops as described in an article entitled 
"Carrier and Bit Synchronization in Data Communication--A Tutorial Review" 
by L. E. Franks, IEEE Transactions on Communications, Vol. COM-28, August 
1980, pp. 1107-1121. Precise timing of node operation may be implemented 
using techniques described in the articles "Network Timing/Synchronization 
for Defense Communications" by H. A. Stover, pp. 1234-1244 and in the 
paper entitled "Synchronization of a Digital Network" by J. Heymen et al 
pp. 1285-1290, IEEE Transactions on Communications, Vol. COM-28, August 
1980. 
It should be observed that in the description to follow routing updates 
occur in a (loosely) synchronized fashion; however, the mechanism of the 
invention is also applicable using asynchronous updates which would 
require no network timing. Such an asynchronous application of the 
invention allows nodes to issue topology updates asynchronously to each 
other as in the above-referenced ARPANET routing scheme. A minor drawback 
to this method, however, is the fact that, as in the ARPANET technique, 
transient routing loops can occur. 
In order to facilitate an appreciation of the network management/routing 
mechanism of the present invention, it is useful to examine the topology 
of a typical multinode communication network, such as a satellite 
communication system, referenced above, using an exemplary two-dimension 
topology diagram, such as that depicted in FIG. 3. It should be noted, 
however, that the topology of the network to which the present invention 
may be applied is not limited to the example given or to only two 
dimensional topologies. In fact, in a practical environment, such as an 
airborne/spaceborne communications network, it can be expected that the 
topology will be three dimensional and will contain considerably more 
nodes than the network shown in FIG. 3. The two dimensional illustration 
of FIG. 3 is employed merely for reducing the complexity of the 
description. 
More particularly, FIG. 3 diagrammatically depicts the topology of a five 
member station or node network comprising nodes 1, 2, 3, 4 and 5, one of 
which (node 1) is referenced as a source node (S) from which a message to 
be transmitted originates and another of which (node 5) is referenced as a 
destination node (for whom the message from the source node 1 is 
intended). The nodes of the network topology of FIG. 3 are shown as being 
linked by a plurality of communication links CL over which messages are 
conveyed. In the present example of the transmission of a message from 
source node 1 to destination node 5, the communication links that may be 
used for transmitting messages are denoted by subscripts (i,k), the first 
of which (i) corresponds to the node from which the link extends to 
another node and the second of which (k) corresponds to that another node 
to which the link extends. Thus, for example, communication link CL.sub.12 
is a communication link (CL) extending from node 1 to node 2. 
Associated with each communication link CL.sub.ik is a link metric D.sub.ik 
which is representative of the degree of `goodness` of the link between 
adjacent nodes i and k and is based upon a number of communication 
capability criteria, including link delay, data rate, congestion and link 
capacity. Typically, the congestion (in packets per second) on a link 
(i,k) increases with increase in data rate .function..sub.ik (packets per 
second) and decreases with an increase in capacity C.sub.ik (packets per 
second). These effects are incorporated into a link metric D.sub.ik 
(.function..sub.ik), which is repeatedly (periodically) updated at each 
node and propagated to all other nodes of the network using a constrained 
flooding mechanism, so that each node may be advised of the states of all 
other nodes of the network. This flooding mechanism is the so-called 
topology update function, which is implemented by the same conventional 
technique used in the above referenced ARPANET system. A typical link 
metric for link (i,k) is of the form 
EQU T.sub.ik (a,.function..sub.ik)=ad.sub.ik /C.sub.ik +1/(C.sub.ik 
-.function..sub.ik), 
where the first term denotes the normalized propagation plus processing 
delay and the second term is the expected transmission delay including the 
queuing delay. The propagation delay normalization makes the propagation 
delay and congestion terms nominally the same order of magnitude at low 
loads. The term d.sub.ik /C.sub.ik is the actual propagation delay (in 
seconds). Therefore, d.sub.ik is the value of propagation delay as 
measured in number of packets in the pipeline between nodes. The 
asymptotic behavior of the second term for large flows tends to introduce 
instability. Upon investigation it has been determined that a preferred 
definition of the link metric D.sub.ik (a,.function..sub.ik) is: 
##EQU1## 
where F.sub.ik =bC.sub.ik, and b is a scale factor less than one. This 
constrains the maximum value of D.sub.ik (.function..sub.ik) to a 
relatively small value so that instability is not a problem. 
For purposes of generating the link metric any conventional mechanism may 
be employed, such as measuring the average traffic transmitted on a link 
and performing the above calculation. It should be observed, however, that 
the routing mechanism of the present invention does not require the use of 
this or any other particular mechanism for generating the link metric. 
Pursuant to the network management/routing mechanism of the present 
invention the source node uses the link metric updates, as periodically 
supplied from the other nodes of the network, to determine which potential 
communication routes that contain links extending from the source node and 
terminating at the destination node pass through neighbor nodes that are 
effectively closer to the destination node than the source node. For this 
purpose, the communications control processor at each node N.sub.i 
maintains (in memory) a shortest path metric table that contains a list of 
the metrics of all shortest possible paths between that node N.sub.i and 
all potential destination nodes. Using the set of link metrics accumulated 
through topology updates, any (source) node desiring to transmit a message 
to another (destination) node may construct a similar table of shortest 
path metric sums from each neighbor node, each of which totals to a value 
less than the value of the shortest path metric from that source node to 
the destination node. This sum set effectively represents a set of 
`feasible` communication routes through the network from the source node 
to the destination node. 
Using the network topology of the present example illustrated in FIG. 3 
(wherein link metric values of the network links are indicated 
parenthetically), with node 1 as the source node, those neighbor nodes 
which lie closer to the destination node 5 than does node 1, i.e. lie on a 
link whose link metric is less than that of the link between source node 1 
and destination node 5 (a value of 2 in the illustrated topology), are the 
destination node 5 itself (link metric value of zero) and node 2 (link 
metric value of 1). 
Routes R which originate at source node 1 and terminate at destination node 
5 and include such "closer lying" neighbor nodes are designated as 
`feasible` routes. In the present example, these `feasible` routes are the 
route Ra (from source node 1 directly to destination node 5) and route Rb 
(from source node 1-to-neighbor node 2-to-destination node 5). It is to be 
noted that although node 3 is a neighbor node, it lies farther away from 
(i.e. is not closer to) destination node 5 than source node 1 and, 
therefore, any route between source node 1 and destination node 5 that 
passes through node 3 (here route Rc) is excluded from consideration as a 
`feasible` route. As a consequence of this "must lie closer" requirement, 
each potential route will contain no loop (back to the source node). 
For purposes of enabling the control processor at each node to carry out 
the above-described `feasible` route selection procedure with respect to 
L.sub.i neighbor nodes m.sub.1, m.sub.2, . . . , m.sub.L.sbsb.i, the 
manner in which the network topology variables are processed may be 
expressed in accordance with the procedure set forth in Table 1, shown in 
FIG. 4. 
From Table 1 it can be seen that the routing procedure is autonomous in 
that each node determines a set of routing tables with no inputs from 
other nodes (except globally available link metric information received 
during the topology update flooding interval). 
Thus, in the exemplary network topology shown in FIG. 3, for node 1 there 
are three neighbor nodes (2, 3 and 5). The initial step in the feasible 
route selection procedure is to generate a shortest path spanning tree, 
rooted at node 1, to all destinations and similar trees from each neighbor 
of node 1. Each such calculation is accomplished by the procedure 
Shortest.sub.-- Path (m.sub.k, D, M.sub.m.sbsb.k, P.sub.m.sbsb.k, 
.rho..sub.m.sbsb.k, C.sub.min), which is preferably implemented using a 
conventional spanning tree algorithm, such as Dijkstra's algorithm, 
described in an article entitled "A note on two problems in connection 
with graphs", Numerical Math. Vol. 1, 1959, pp. 262-271. Using the 
periodically updated link metric array D and the node index as inputs, the 
Shortest.sub.-- Path algorithm generates an output array M.sub.i which 
contains the minimum metric M.sub.i.sup.j, to each destination node j in 
the shortest path spanning tree from the root node (not to be confused 
with a minimum weight spanning tree). The propagation delay to each 
destination is returned in the array P.sub.i. The propagation delay of 
link (i, m.sub.k) is denoted by D2.sub.im.sbsb.k. This procedure also 
determines the link with maximum utilization (called the bottleneck link) 
and the link with minimum capacity along the shortest path to each 
destination. These are denoted by .rho..sub.i and C.sub.min.sup.i, 
respectively. These shortest path calculations are first calculated using 
node i as the root and then each of its neighbors as the root. From this 
the set of feasible routes can be determined. 
In the present example, therefore, for node 1 and its neighbor nodes 2, 3 
and 5, (and ignoring the path metrics to destination nodes other than node 
5) the following path metrics to destination node 5 will be produced: 
M.sub.1.sup.5 =2 for node 1 as a root node, M.sub.2.sup.5 =1, for node 2 
as a root node, M.sub.3.sup.5 =3 for node 3 as a root node and 
M.sub.5.sup.5 =0 for node 5 as a root node. From these values, a set of 
indices S.sub.i.sup.j into the set of L.sub.i neighbors of node i=1 which 
lie on the feasible routes to destination node j=5 is determined by 
requiring that M.sub.i.sup.j &gt;M.sub.m.sbsb.k.sup.j. This condition states 
that only neighbor nodes closer to the destination node j (here node 5) 
than node i (node 1) are permitted to lie on `feasible` routes. The 
sequence of calculations to make this decision is carried out inside the 
nested-for loops (iterated on j and k). The metric M.sub.m.sbsb.k.sup. j 
is the minimum path metric to the destination node j=5 and is located by 
the application of the shortest path algorithm to find a tree rooted at 
the neighbor node m.sub.k (Shortest.sub.-- Path (m.sub.k, D, 
M.sub.m.sbsb.k)). 
Thus, in the present example, the set of indices S.sub.i.sup.j will exclude 
neighbor node 3 which lies farther away from destination node 5 than does 
node 1. Consequently, route Rc is not considered to be a `feasible` route, 
leaving only route Ra (which extends directly from source node 1 to 
destination node 5) and route Rb (which extends from source node 1 to node 
2, and from node 2 to destination node 5) as `feasible` routes. 
As described above, in addition to determining feasible routes for the 
transmission of traffic between a source and destination node based upon 
updated path metric array tables maintained at each node, the network 
management/routing mechanism according to the present invention also uses 
these path metric arrays to allocate the use of the routes to 
near-optimally balance the loading of the network. To this end, for each 
feasible route a routing variable .phi..sub.ik.sup.j is used to define 
what fraction of the traffic is to be routed over that feasible route. In 
effect the routing variable represents the probability that traffic at 
node i destined for node j will be routed through neighbor node k. From 
Table 1, the metric for a feasible path routed through node m.sub.k is 
EQU w.sub.im.sbsb.k.sup.j =D.sub.im.sbsb.k 
(a,.function..sub.im.sbsb.k)+M.sub.m.sbsb.k.sup.j, 
where D.sub.im.sbsb.k (a,.function..sub.im.sbsb.k) is the link metric for 
link (i,m.sub.k). The minimum path metric M.sub.i.sup.j from source node i 
to destination node j is 
##EQU2## 
In accordance with the feasible path allocation mechanism of the present 
invention routing variables .phi..sub.im.sbsb.k.sup.j &gt;0 are assigned to 
each of the feasible routes such that 
##EQU3## 
and the routing variables for all non-feasible routes are zero, thereby 
guaranteeing loop-free routes. These requirements are representable by the 
sequence: 
for j=1 to n (j.noteq.i) 
##EQU4## 
The heuristic employed for assigning values to .phi..sub.ik.sup.j is 
premised on the apportionment of traffic among feasible routes inversely 
with the magnitude of the path metric for each route. 
More particularly, letting 
##EQU5## 
when w.sub.i.sup.j can be mapped into the routing variables 
.phi..sub.im.sbsb.k.sup.j 's, i.e. 
##EQU6## 
where 
##EQU7## 
Then, .phi. can be written as: 
##EQU8## 
As an example, the function g(k,S.sub.i.sup.j,w.sub.i.sup.j) may be 
defined as 
##EQU9## 
This function maps all n routing variables into positive numbers which sum 
to 1 and the relative values vary inversely with the size of the path 
metric. 
In addition, the .function. estimates are averaged to improve stability. 
When new feasible routes are determined in accordance with the procedure 
set forth in Table 1 widespread changes in routes can occur if there are 
significant changes in path metrics. In situations where the minimum 
metric to destination j from the source node i is nearly equal to the 
minimum metric of one of its neighbors, the above expression for 
g(k,S.sub.i.sup.j,w.sub.i.sup.j) can contribute to instability. In this 
instance stability can be improved by driving the routing variable to 
zero. This is accomplished by making the routing variable proportional to 
(M.sub.i.sup.j -M.sub.m.sbsb.k.sup.j).sup.1/2. Investigation has shown 
that the excellent behavior of the route allocation procedure can be 
obtained by defining the expression g(k, S.sub.i.sup.j, W.sub.i.sup.j) as 
##EQU10## 
where 
##EQU11## 
where 
##EQU12## 
The expression w.sub.m.sbsb.k.sup.j (0) refers to the path metric at zero 
flow. The constant .delta. allows a trade-off between low-load and 
high-load performance with larger values emphasizing low-loads. 
As pointed out above each node carries out a link metric calculation based 
upon traffic flow measurements conducted on the links with which that 
particular node is associated. In order to provide processing stability 
the traffic flow values are preferably averaged over several update 
intervals. If .function..sub.ik is the average flow since the last update, 
then this sample is averaged with previous measurements, namely a running 
accumulation is obtained as 
EQU .function..sub.ik =.alpha..function..sub.ik +(1-.alpha.).function..sub.ik. 
Thus, each new flow measurement value .function..sub.ik produces a new 
updated average value. The time constant of this first order filter 
function may be on the order of several update intervals (e.g. 
.alpha..apprxeq.0.2). Then having computed the value .function..sub.ik, 
node k can determine the new metric for each of its neighbor nodes i, and 
broadcast these updated metrics to all nodes of the network on the next 
topology update. 
In order to provide improved performance with respect to the mapping scheme 
described above, a two-stage heuristic mapping function to be described 
below may be employed. Specifically, this two-stage approach provides 
near-optimum performance when propagation delays become large. As a simple 
example consider the two-node network shown in FIG. 4A. This optimum 
solution as a function of load is to place all traffic on the low-delay 
link until the utilization of this link exceeds .rho..sub.break at which 
point sharing with the alternative path should begin. Assume that the 
zero-flow delay (in seconds) of the minimum delay link is p.sub.1 
+1/C.sub.1 while the corresponding delay for the other link is p.sub.2 
+1/C.sub.2. (The term p.sub.1 denotes the propagation delay in the link.) 
The expression for .rho..sub.break is 
##EQU13## 
This will be applied as a heuristic to the general case where there are 
multiple paths each consisting of several links. The term C.sub.1 (p.sub.2 
+1/C.sub.2 -p.sub.1) will be replaced by C.sub.min (t.sub.2 -p.sub.min). 
The capacity, C.sub.min, refers to the capacity on the link with minimum 
capacity along the path of minimum delay at zero flow, and p.sub.min 
refers to the propagation delay on this path. The term t.sub.2 refers to 
the actual delay (propagation plus transmission) at zero flow on the 
second smallest delay path. 
The two-stage mapping function generates a pair of partial routing 
variables in the first stage, one based on the zero-flow metric and the 
other based on the part of the metric that reflects the transmission plus 
queueing delay which is denoted by queueing. Use of the zero-flow metric 
will dominate at low loads. In fact, it will be used exclusively below a 
certain threshold. The two-node example described above will provide the 
heuristic for decisions to .rho..sub.break. The procedure Route.sub.-- Var 
() specified below in Table 1A (FIG. 4B) defines this heuristic method for 
mapping the metrics into the routing variables. The following development 
of the rationale and equations used in Table 1A illustrates the heuristic. 
Feasible paths will be determined as described above using the conventional 
link metrics, D.sub.ik (.alpha.,.function..sub.ik), in calculating the 
path metrics, so that all nodes will use the same link metrics in making 
these decisions. It is important to note that these metrics are a linear 
combination of the metrics used in calculating the two sets of partial 
routing variables. A separate pair of path metrics is calculated for each 
feasible path to determine the routing variables. The first is the 
zero-flow path metric, w.sub..sigma.im.sbsb.k.sup.j, which is calculated 
by summing the zero-flow link delay, D.sub.ik (i,0), for each link along 
the path. (This is obtained from the metric.sub.-- zero field of the 
topology update packet.) Since it is very important to let the shortest 
delay dominate at low loads, the routing variables will be inversely 
proportional to the square of this metric, i.e. 
##EQU14## 
where M.sub.i.sup.j is calculated as before using D.sub.im.sbsb.k 
(.alpha.,.function.im.sub.k). Similarly, the queueing path metric, 
W.sub.qim.sbsb.k.sup.j, is calculated by summing the queueing link metric, 
D.sub.ik (0, .function..sub.ik), for each link along the path. (This is 
obtained from the metric.sub.-- queue field of the topology update 
packet.) This metric will dominate at high loads and the routing variables 
will be inversely proportional to it i.e., 
##EQU15## 
These weighting factors are used to calculate the zero-flow routing 
variables .phi..sub.0im.sbsb.k.sup.j, by using 
W.sub..sigma.im.sbsb.k.sup.j in 
##EQU16## 
and then substituting this result in the definition of 
.phi..sub.im.sbsb.k.sup.j. The queueing routing variable, 
.phi..sub.qim.sbsb.k.sup.j, is computed by using W.sub.qim.sbsb.k.sup.j 
and then determining .phi..sub.im.sbsb.k.sup.j. 
These routing variables provide near-optimum solutions at low loads and at 
high loads, respectively. By averaging these two routing variables 
near-optimum performance at intermediate loads can be achieved. This 
averaging is done using a heuristic to compute the actual routing 
variables used in routing tables as 
##EQU17## 
to simplify the subsequent notation the subscript i identifying the node 
computing its routing variables has been dropped from .eta..sup.j (.rho.), 
.rho..sub.crit.sup.j and .rho..sub.break.sup.j. The averaging function is 
.eta..sub.j (.rho.) is intended to approach 1 at high loads to utilize 
only the queueing metric and to approach 0 at low loads to utilize only 
the zero-load metric. In fact, for a significant imbalance in the 
propagation delay, .eta..sup.j =0 until relatively high loads for the 
two-node example. Thus, 
##EQU18## 
where 
##EQU19## 
Some further explanation is required to fully define how this heuristic is 
used. The function .rho..sub.crit.sup.j is computed for destination j from 
the set of feasible paths to j. The parameter .rho..sub.break.sup.j is 
calculated using the zero-flow delays of the set of feasible paths to 
calculate 
##EQU20## 
This provides the zero-flow delays of the minimum and maximum delay paths. 
The parameter, C.sub.min, is the capacity of the link with minimum 
capacity along the feasible path to destination j with minimum delay 
t.sub.min. The value of .rho..sub.bot.sup.j.sub.i is equal to the largest 
utilization of any link along each of the feasible paths to destination j, 
i.e., it is the utilization of the bottleneck link. The value used is the 
output of a simple first-order filter which has as its input the currently 
measured value of the bottleneck utilization, i.e. 
##EQU21## 
It should be noted that the filter parameter is the same self-scaling 
parameter used for the link flows. 
The function .eta..sup.j (.rho.) insures that only the zero-flow routing 
variables are used whenever the utilization on the bottleneck link is less 
than .rho..sub.crit.sup.j. This forces almost all of the load onto the low 
delay path which is correct. The function .rho..sub.crit.sup.j is 
saturated at 0.8, because if it were allowed to increase beyond this, the 
slope of .eta..sup.j (.rho.) at larger values of .rho. would begin to 
cause stability problems. The function .eta..sup.j (.rho.) forces the use 
of the queueing variables, .phi..sub.qim.sbsb.k.sup.j, when any link on 
any feasible path becomes a bottleneck (which is the correct action). It 
should also be noted that this function in computed separately for each 
destination, so that a bottleneck is one part of the network may force a 
local use of queuing variables there, while in places where there are no 
bottlenecks the zero-flow variables can be used. 
As described above, the path metric table within each node is updated 
periodically by a network-wide flood mechanism, so that each node will 
possess a current picture of the connectivity and traffic congestion on 
the network links. Using its path metric table each node generates a 
routing table for each destination and an attendant routing variable table 
associated with each set of feasible paths in accordance with the routing 
and traffic allocation mechanisms thus far described. For the most part, 
these tables remain intact until the next topology update. However, in 
accordance with a further aspect of the present invention, in the event of 
a connectivity failure (either on a link or at a node) within the network, 
the routing mechanism does not wait until the next topology update but, 
instead, takes immediate action to make whatever adjustments to the 
presently employed routine scheme are necessary, so as to insure that the 
transmission of traffic through the network, is, at all times, effectively 
nearly optimally routed. 
More particularly, incorporated into the routing mechanism is an 
`event-driven` failure recovery procedure which reassigns the routing of 
traffic from a source node to a destination node by coordinating with 
other nodes in the rerouting process. In the exemplary network topology 
diagram of FIG. 3 the routing of traffic from source node 1 to destination 
node 5 is allocated between feasible routes Ra and Rb (using the routing 
variable .phi..sub.ik.sup.j to apportion the traffic between each route). 
In the event of a failure on either of these routes the most 
straightforward way to reroute the traffic is to simply transmit all of 
the traffic over the remaining route. (In a network topology where there 
is more than one remaining feasible route, the traffic is reapportioned 
over those routes using updated routing variables.) Should the failure 
effectively negate all currently employed feasible routes (or route, where 
only one path is being used), so that no alternate route is currently 
available, a distributed reassignment procedure is implemented which finds 
a nearby alternate feasible route to which traffic can be rerouted. 
In accordance with the invention, when a node detects a failure it 
transmits a message (referenced here as a NO.sub.-- PATH type message to 
be described in detail below) to its neighbor nodes identifying those 
destinations which can no longer be reached by feasible paths through it. 
In the simplest case one of the neighbor nodes will send back a message to 
the failure detecting node indicating that the neighbor has another 
feasible path for these destinations and that all traffic to these 
destinations may be sent through that neighbor node. Any node which 
receives this message will propagate the message if, as a result of the 
message, that neighbor node no longer has a feasible route to the 
destination. The propagation of the message terminates at nodes which have 
alternative feasible routes to the destination. 
A second type of message (termed a PATH message, to be described below) is 
used to inform a node having no feasible route to a destination that a 
feasible route to the destination is available through the node sending 
the PATH message. Any node which receives a PATH message and which has no 
feasible route to the destination will reroute such traffic to the node 
sending the PATH message and will propagate the PATH message. The PATH 
message will continue to propagate to all nodes which cannot provide a 
feasible path to the destination. This procedure will ultimately result in 
loop-free rerouting without having to wait for the global topology update. 
To facilitate an understanding of the event-driven failure recovery 
procedure outline briefly above, attention is directed to the seven node 
network topology diagrammatically illustrated in FIG. 5. In the present 
example, for purposes of simplification, the routing of traffic (indicated 
by the directions of the arrows linking the nodes of the network) to 
destination node 7 only will be considered. In the topology of FIG. 5 a 
link failure has occurred on link L.sub.17 and is detected by node 1. Upon 
detection of the failure node 1 initiates the execution of the 
event-driven failure recovery routine set forth in Table 2, shown in FIG. 
6. 
The first action taken in response to the detection of the failure 
(LNK.sub.-- FAIL (link)) is the call to the routine Unreach.sub.-- Nodes 
(NO.sub.-- PATH, link), set forth below in Table 3, shown in FIG. 7, where 
`link` is the index of the link that has failed (here link L.sub.17). 
The purpose of the routine set forth in Table 3 is to first locate local 
alternate paths for all traffic passing over the route containing the 
`link` index. As mentioned previously, the allocation of traffic to an 
alternate feasible route is a relatively simple matter when, in fact, an 
alternate route already exists locally. In the present example of the 
topology of FIG. 5, however, there is no alternate feasible route, all of 
the traffic from node 1 being transmitted directly from node 1 to 
destination node 7 and, moreover, node 1 finds that it is receiving 
traffic from nodes 2 and 3 destined for node 7. Consequently, it is 
necessary to execute the routine NO.sub.-- PATH, in which a message is 
transmitted from node 1 to all neighbor nodes (here nodes 2 and 3) 
identifying those destinations which can no longer be reached via a 
feasible route through node 1. 
In Table 3, if the variable Old.sub.-- Tables, which indicates whether or 
not this routine was called in the interval between the occurrence of the 
failure and the update of the routing tables, is true, the effect of the 
link failure is examined twice: first, upon the occurrence of the failure 
and, second, after the new routing tables have been installed. (In the 
first `If` statement of Table 3, the link index is stored in the set 
Failed.sub.-- Links for later inspection after the new routing tables are 
installed, scheduled as new events by the routine Resched.sub.-- Events 
(Failed.sub.-- Links) in Table 11, shown in FIG. 16 to be described 
below.) 
Next, all destinations are examined in order to locate nodes that have 
become unreachable as a result of the failure. A list of these unreachable 
nodes is maintained in UR.sub.-- NODES. If the node 7 (`dest`) was not 
reachable before the occurrence of the failure and if the `link` (here 
link L.sub.17) actually carried traffic to the destination node, which, in 
the present example, it did, then .phi..sub.im.sbsb.link.sup.dest 
indicates that a local alternate feasible path can be used for rerouting 
traffic. The routine Rescale.sub.-- .phi. (i, dest, link) rescales the 
routing variables proportionately in order to optimize the load; otherwise 
node 7 (`dest`) is added to the list of unreachable nodes and to the 
NO.sub.-- PATH message packet. After examining all destination nodes, a 
NO.sub.-- PATH data packet is transmitted on all links if the failure has 
caused new nodes to become unreachable. 
In the present example, each of nodes 2 and 3 receives a message from node 
1 that node 1 no longer has a feasible route to destination node 7. On 
receiving this message, node 2 reacts as though its link L.sub.21 (the 
only link from node 2 within a feasible route to node 7) has suddenly 
become useless for the transmission of traffic to node 7, and node 2 
proceeds to send a similar message to node 4. As mentioned previously, a 
node which receives a NO.sub.-- PATH message (here nodes 3 and 4) will 
propagate the message if, as a result of the message, that node no longer 
has a feasible route to the destination node. Otherwise, the propagation 
of the NO.sub.-- PATH message terminates at nodes which have alternate 
feasible routes to the destination (each of nodes 3 and 4 in the present 
example). 
More specifically, the steps of routine New.sub.-- Unreach.sub.-- Nodes (), 
Table 4, FIG. 8, is executed at a node (here nodes 3 and 4) which has been 
informed of the loss of path through the reception of a NO.sub.-- PATH 
message. The node receiving the message examines only those destination 
nodes listed in the message as being unreachable. 
In this routine the sequence number is tested to determine if the original 
failure event (here the failure of link L.sub.17) occurred when Old.sub.-- 
Tables was true and if Old.sub.-- Tables is still TRUE. Otherwise new 
tables may have been installed that obviate the need to respond to the 
failure. .phi..sub.im.sbsb.link.sup.dest is tested to determine if a local 
alternate path is available, and local traffic will be rerouted if such a 
path is available. If no alternative route is available then a NO.sub.-- 
PATH message (indicated by S.sub.-- NO.sub.-- PATH) is transmitted on all 
links except for the one on which the original NO.sub.-- PATH message was 
received. 
In the present example, it will be recalled that each of nodes 3 and 4 have 
received the same NO.sub.--PATH message from node 2 and that node 4, like 
node 3, will have found that it has an alternate feasible route to the 
destination node 7, thereby allowing node 2 to send its traffic over link 
L.sub.24 to node 4. Accordingly, each of nodes 3 and 4 will transmit a 
PATH message indicating that traffic intended for the destination node 7 
can be sent through this node (i.e. node 3 and node 4). In other words, a 
PATH message is used to inform a node (here each of nodes 1 and 2) with no 
feasible route to a destination that a feasible route to the destination 
is available through the node sending the PATH message. All nodes which 
have no feasible route to the destination and receive the PATH message 
will reroute traffic to the node sending the message and will propagate 
the message. The PATH message will continue to propagate through the 
network until it reaches the source of the NO.sub.-- PATH message. The 
routine for responding to a PATH message is set forth in Table 5, shown in 
FIG. 10 
This routine, termed New.sub.-- Reach.sub.-- Nodes (PATH, link) examines 
the PATH message for a list of destination nodes that can be reached by 
directing traffic through the node identified by the link index. Provided 
that the destination node (here node 7) is currently unreachable and the 
appropriate conditions on sequence numbers are satisfied, 
.phi..sub.ik.sup.j is set to 1. Also the destination node is removed from 
the list of currently unreachable nodes, and is added instead to the list 
of reachable nodes in the PATH message to be propagated. 
FIG. 9 depicts the manner in which the network routing scheme of FIG. 5 is 
reconfigured by the execution of the above routines. As shown therein the 
original (failed) link L.sub.17 between nodes 1 and 7 is no longer used 
and the directions of the links between nodes 1 and 3 and between nodes 2 
and 4 have been reversed. In order to simplify the rerouting mechanism, 
the new path assignment routine selects only a single new path at each 
node which, as a result of the failure, had no feasible route through it. 
Pursuant to the invention, in both the original routing mechanism and the 
event-driven failure recover mechanism described above, where more than 
one feasible path is utilized to send traffic to a destination node the 
traffic is apportioned in accordance with a routing variable derived on 
the basis of the path metric tables maintained at each of the nodes. In 
the rerouting Tables set forth above apportionment of the traffic is 
determined in accordance with the subroutine identified as Rescale .phi. 
(i, dest, link). 
In accordance with this rescale procedure if traffic intended for the 
destination node (dest) is allowed to propagate on `link`, then 
.phi..sub.alt represents the fraction of that traffic which is transmitted 
by the feasible routes that do not include `link`. Then each routing 
variable is simply normalized by .phi..sub.alt and .phi..sub.ik.sup.j is 
set to 0. Consequently, local alternate rerouting is accomplished. 
As described above, each of the nodes of the network topology into which 
the routing mechanism of the present invention is incorporated maintains a 
set of tables (e.g. path metrics, routing variables, node status) that 
enable each node to keep track of changing conditions within the network 
in the course of its monitoring of link connectivity and its transmission 
of messages to other nodes of the network. For purposes of systematic 
coordination of the conditions at each of the nodes of the network, table 
entries are updated periodically and dynamically in response to 
connectivity anomalies that require immediate action (event-driven 
failures). Periodic updates are triggered by timer events which are 
loosely synchronized throughout the network. Three timing signals or 
commands are used, START.sub.-- TU, FIN.sub.-- TU AND INS.sub.-- TB, which 
are defined in Table 6, shown in FIG. 11. 
The time interval between START.sub.-- TU and FIN.sub.-- TU is made 
sufficient to allow the flood of topology update messages to have 
propagated to all nodes of the network. In addition, there is sufficient 
time between FIN.sub.-- TU AND INS.sub.-- TB to enable each node to 
compute new routing tables so that all nodes can install the new tables 
upon receipt of the command INS.sub.-- TB. 
In addition to these periodically generated command signals, in the event 
of a link failure (detected by the status monitor at the node) a command 
LNK.sub.-- FAIL is generated to advise the node, and the network, that a 
link failure has been detected (the link is no longer responding). 
The routing mechanism itself is driven by three types of messages listed in 
Table 7, shown in FIG. 12, two which, PATH (used to indicate a reachable 
node) and NO.sub.-- PATH (used to indicate an unreachable node) have been 
described above in connection with rerouting in response to an 
event-driven failure. The third type of message, TOP.sub.-- MSG, is used 
during periodic topology update and is flooded over the entire network to 
allow each node to construct a global topology table. The structure of the 
TOP.sub.-- MSG message is set forth in Table 8, shown in FIG. 13, while 
those of the PATH and NO.sub.-- PATH messages are itemized in Table 9, 
shown in FIG. 14. In addition, Table 10, shown in FIG. 15, contains a list 
of variables employed in the routing mechanism. 
Within Table 10, the sequence number N.sub.s is derived from the time of 
day `time` such that it is incremented by a value of 1 on each routing 
update. This number is used in the topology update messages and is the 
same at all nodes on a given iteration. Since routing table updates for 
all nodes of the network are installed at approximately the same time, in 
response to a flood message, the routing mechanism is effectively 
synchronous. 
Table 11, shown in FIG. 16, sets forth the overall sequence of routines 
that make up the routing mechanism of the present invention. As shown 
therein the topology update (TU) process is initiated at each node at 
approximately the same time with the command START.sub.-- TU. Each node 
determines its local status and causes a flood of this information to all 
other nodes with the execution of (Send.sub.-- Flood (TOP.sub.-- MSG)). 
The updates from the other nodes will arrive at a given node in an 
indeterminate sequence and with unknown timing. Each message (packet) 
arrival triggers the TOP.sub.-- MSG event which causes the local tables to 
be updated with new information (Update.sub.-- Top.sub.-- Tables 
(TOP.sub.-- MSG)). The time window for the installation of the updates is 
sufficiently wide to ensure with a very high probability that topology 
update messages from all the other nodes of the network have been 
received. 
Upon completion of the topology update interval the command FINISH.sub.-- 
TU, which starts the routing update calculation (Multiple.sub.-- 
Path.sub.-- Route ()) is initiated. This routine uses current topology and 
metric information and runs to completion. In the event that a topology 
update message from another node is not received prior to the 
FINISH.sub.-- TU event, it will not affect the current update calculation. 
However, receipt of that message will trigger a TOP.sub.-- MSG event upon 
its arrival and cause appropriate modification of the topology and metric 
tables. In other words, topology update messages will always be accepted 
asynchronously into the routing calculation. Finally, the event INS.sub.-- 
TABLES is generated to cause the newly created routing tables to be 
installed (Swap (new.sub.-- .phi..sub.1.sup.j, 
old.sub.--.phi..sub.1.sup.j.sub.--)). 
The events or routines listed in Table 11 are set forth in the order of 
priority of execution. The first three events (START.sub.-- TU, 
FINISH.sub.-- TU and INS.sub.-- TABLES) are timer-based and are the only 
events which require relatively immediate attention from the node's 
control processor. However, to ensure accuracy of execution, each event 
must be processed without interruption prior to initiating the execution 
of a new event. During the execution of the remaining events (4-7) if a 
timer-based command is generated during the execution of any one of the 
events, the small delay needed to complete processing of the previous 
event will not negatively impact timing. In addition, timer-based events 
do not compete with one another for attention of the control process since 
a significant delay is allotted between the occurrence of each event. The 
timing delay between START.sub.-- TU and FINISH.sub.-- TU is sufficient 
for global propagation of the flood (on the order of 1 second). The timing 
delay between FINISH.sub.-- TU and INS.sub.-- TABLES is also sufficient to 
allow calculation of the routing tables. The time window required will 
depend upon the speed of the control processor assigned to the execution 
of the task. However, execution is given a high priority since it must be 
completed prior to the occurrence of the routing table installation event 
(INS.sub.-- TABLES). 
The events associated with the rerouting of the network in response to a 
link failure, described above (events 5, 6 and 7) are executed on a 
localized basis. 
As described above, Table 11 sets forth the overall sequence of routines or 
the timings of the discrimination of topology and congestion information 
that make up the routing mechanism of the present invention. 
Upon the occurrence of the command START.sub.-- TU command, each of the 
nodes of the network assemblies a message containing a summary of 
characteristics of local status which are required by the other nodes to 
complete the adaptive routing function. This task is carried out by the 
routine ASSEM.sub.-- STATUS (TOP.sub.-- MSG) the routine sequence for 
which is set forth in Table 12, below. These summary messages are flooded 
throughout the network, so that they can be delivered to all destination 
nodes without requiring routing tables. Upon the occurrence of the 
FINISH.sub.-- TU event, it is assumed that all messages have been 
delivered and calculation of the new routing table begins. (As noted 
above, the interval between START.sub.-- TU and FINISH.sub.-- TU is 
sufficient to allow all messages to propagate to their required 
destinations.) The topology data base that is constructed at each node 
during this process as well as the procedure for updating the data base 
using the topology update messages will be explained below. 
The topology update packet for each node, defined as specified in Table 8, 
referenced above, essentially contains the following information: 1-the 
address of the node from which the packet originates; 2-the addresses of 
all directly connected nodes; 3-a congestion metric for each link between 
the nodes; and 4-a sequence number which identifies the time of 
origination of the topology update. These packets are given highest 
priority in flooding them through the network in order to ensure delivery 
within the allocated time interval. 
Errors caused by missing a topology update will not propagate, since each 
node transmits a list of directly connected nodes, not simply changes to 
the connectivity of that node. In order to prevent more serious 
consequences due to update message anomalies, all information is employed 
for constructing the best possible estimate of topology. 
The procedure employed to sample local status and assemble a topology 
update message TOP.sub.-- MSG to be flooded throughout the network is set 
forth in Table 12, as pointed out above. As shown therein, after 
initialization in which the node.sub.-- id and the appropriate sequence 
number are inserted into the message, the primary task of the routine is 
to place the local backbone connectivity and the corresponding link 
metrics in the message. For this purpose, the data structure shown in 
Table 14 is employed. A copy of the data structure, identified as 
Prev.sub.-- Status, contains the current status used on the previous 
topology update while Status contains the current status. 
The sequence contains a pair of loops, both of which iterate over the link 
index k to examine all links that are updated. The first `for` loop 
examines the status of all backbone neighbors and fills in the neighbors 
field of TOP.sub.-- MGS. Initial calculations on link utilization are also 
carried out during this loop. The second `for` loop makes final 
adjustments to link utilization, calculates link metrics, and fills in the 
`metrics` field of TOP.sub.-- MSG. `Status" is then saved as `Prev.sub.-- 
Status` for the next update cycle. 
The calculation of the link metrics may be impacted by the occurrence of 
changes in topology of the network. Such changes include an imminent link 
outage due to nodes about to fail, new nodes or links which have been 
added, or an unpredictable link or node outage that has occurred. 
It is assumed that a predictable link outage can be determined in advance 
of the actual outage by knowledge of the network dynamics. The function 
Link.sub.-- Outage () returns TRUE for several iterations (typically on 
the order of 3) in advance of the actual outage of the link. The metric 
for this link is increased fictitiously over this interval in a monotonic 
fashion in order to drive the flow on this link to zero within the number 
of iterations (3 updates). This is accomplished by multiplying the assumed 
value of link capacity by a factor .beta.&lt;1 (e.g. .beta.=0.6) on each of 
the iterations, as shown in Table 12, shown in FIG. 17. 
For the case of the addition of new links, Table 12 shows that link 
utilization is initialized to a relatively large value (e.g. 0.9) in order 
to limit the usage of a link which might be overwhelming. 
Where a link failure has occurred, the flow in the link must be shifted to 
other links, namely rerouted, as described above. To minimize the 
transient nature of the rerouting procedure, the metric is calculated by 
using an upward adjustment on the utilization of each link. This is 
somewhat predictive because the links will typically have to carry a 
greater load. The capacities on the previous topology and the current 
topology updates are denoted in Table 12 by cap.sub.-- prev and cap.sub.-- 
cur, respectively. The normalized lost capacity is denoted by lost.sub.-- 
p. It should be noted that for the second `for` loop, the p on each link 
is adjusted upward by an amount proportional to the product of the 
lost.sub.-- p and (1-p). The simplest part of the routine is the change in 
p that is made when the link status has not changed since the last 
topology update. In this case, the new value of p is averaged with the 
previous averaging of p according to the simple first-order filter with 
parameter .alpha., as described above. 
It should also be noted that the routine Metric() is employed to compute 
the link metrics after all of the adjustments on the link utilizations are 
completed. 
Topology update packets are then broadcast to all nodes using a flood 
routing mechanism as set forth in Table 13, shown in FIG. 18. 
In this routine, the only state that must be retained is the current 
sequence number N.sub.s and an array of sequence numbers for the last 
accepted topology messages for each node Messages[]. The `if` clause 
detects new messages (those for which the sequence number matches the 
current Ns and the last accepted message from that node did not have the 
sequence number). In this case, Messages[] array is updated to reflect the 
newest accepted message. Then, the procedure Gen.sub.-- Event (TOP.sub.-- 
MSG, pkt.DATA), generates a TOP.sub.-- MSG event which ultimately calls 
the routine Update.sub.-- TOP.sub.-- tables() which, in turn, updates the 
topology data base with the new information contained in the packet. The 
message is then transmitted on all links except the original link on which 
it was received. The `else` clause catches the condition that the message 
has been previously accepted; therefore, it is discarded. Implicit in this 
operation is the fact that the lifetime of a network topology update 
message is the interval between successive START.sub.-- TU events, as 
described above. The sequence numbers change on each START.sub.-- TU 
event. 
The structure of the topology database is shown in Table 14, shown in FIG. 
19. A sequence number for each node allows identification of the topology 
update interval originating the most recently received topology update 
message from each node. Another type of record for each node is 
back.sub.-- top which contains relevant data on the backbone connectivity 
for each node. 
The structure of back.sub.-- top will allow the use of some redundancy in 
the topology updates received from the two nodes at either end of each 
link. The array of sequence numbers is employed to store sequence number 
corresponding to the last topology update received from each neighbor 
node. The primary status is assumed to come from the backbone node in 
question; however, if this topology update message is never received, 
missing details can be filled in by the updates from neighbor nodes. 
Table 15, shown in FIG. 20, sets forth the details of the procedure 
Update.sub.-- Top.sub.--Tables() which is initiated upon the reception of 
a topology update message from a node. This first `for` loop compares the 
back bone neighbor nodes listed in the topology update message with the 
previous database entry for `node`. This comparison reveals all links to 
neighbor nodes that have been deleted since the last update (executed by 
the function Mess.sub.-- Member()). For each deleted link, any remaining 
reference to that link is also deleted from the database entry of the 
neighbor node by the procedure Delete (). Next, the pertinent information 
in TOP.sub.-- MSG is copied into the database entry `node`. This includes 
seq.sub.-- no, no.sub.-- neighbors, and the lists of neighbors and 
metrics. The third `for` loop begins a process of `scrubbing` the database 
to find inconsistent entries. Preference is always given to the most 
recent update during this scrubbing procedure. A link to a neighbor's node 
will be deleted from the topology database if both `node` and `nbrs` 
(neighbors) do not agree that the link exists and the current update has 
been received on both nodes. The function DB.sub.-- Member (TOP.sub.-- DB, 
nbrs, node) checks the entry for `nbrs` to identify that a link exists to 
the `node`. Any inconsistencies are deleted in the `for all` loop. This 
marks all links as DOWN for which the nodes at the two ends of the link 
cannot agree on its status. The purpose of the final `for` loop is to 
update the database for each neighbor node for which the current topology 
update message has not yet been received. If the link (nbrs, node) already 
exists in the database of nbrs, then the link is marked with seq.sub.-- 
no. Otherwise, the link is added to the database routine Add.sub.-- Link 
(TOP.sub.-- DB, nbrs, node, seq.sub.-- no). This routine also sets the 
link metric for the (nbrs, node) link to be the same that was received 
from the `node` for the (node, nbrs) link. These entries are maintained 
until the end of the next update (periodically or event-driven). 
In the foregoing description of the network routing mechanism of the 
present invention, each data packet to be transmitted through the network 
from a source node to a destination node is treated independently of other 
data packets. By so doing, near optimal allocation of the feasible routes 
is achieved in a straight forward manner by distribution of the traffic in 
accordance with the path metric tables that are stored at each node. Where 
messages are subdivided into individual data packets, appropriate header 
information is included in the contents of the packet to permit reassembly 
at the destination. 
In some instances, however, it may be appropriate to transmit information 
from a source to a destination so that it travels the same path and 
arrives at the destination in sequence. In this circumstance, the 
connectivity of the network between a source and a destination node 
assumes the configuration of a virtual circuit, rather than a datagram. 
Pursuant to the present invention, the routing and traffic allocation 
mechanisms described above, may be applied to networks that have been 
configured to operate as virtual circuits or for a network configured to 
provide both datagram and virtual circuit capability. Virtual circuit 
routing is effected in substantially the same manner as the datagram 
mechanism, described previously, wherein a loop-free feasible path to the 
destination is defined. This route, preferably having a lowest possible 
path metric total, over which the data packet traffic travels, becomes a 
permanent virtual circuit route. The routing variables that are 
established in accordance with the path metrics are used to select from 
among feasible paths at each node. The route selection process distributes 
the load, so that the average load carried by the virtual circuit 
approximates the distribution implied by the routing variables. The 
virtual circuit route from source to destination will remain dedicated for 
that purpose until rerouting is required, either due to a link failure 
along the route or due to traffic congestion. The virtual circuit 
mechanism, to be described below, interfaces with the datagram routing 
mechanism detailed above in two locations. Routines are run periodically 
subsequent to each topology update (during the processing of the 
FINISH.sub.-- TU event). These routines depend upon the most recent update 
of the routing variables, so that they must be exercised after the 
Multiple.sub.-- Path.sub.-- Route () procedure is completed. The other 
interface point occurs during event-driven failure recovery. When a link 
has been detected as being nonfunctional (failed) the virtual circuit 
traversing the link must be disconnected and rerouted. This interface 
procedure occurs during the routine Unreach.sub.-- Node(). 
Applying the routing mechanism of the present invention to virtual circuit 
routing, while, at the same time, keeping the loading properly balanced, 
requires the consideration of changes to the virtual circuit routing in 
response to the three events: 1-a new virtual circuit is assigned as a 
result of a request for an end node-to-end node connection; 2-a virtual 
circuit must be disconnected due to completion of the communication or the 
detection of a failure; and 3-a virtual circuit must be rerouted to 
prevent congestion (the equivalent to a disconnect and a connect). 
The routing variables .phi..sub.i.sbsb.k.sup.j established during the 
multiple path routing mechanism update are used to represent the sum of 
both virtual circuit and datagram traffic. Accordingly, virtual circuits 
will be assigned as requested. In order to properly distribute the load, 
it is necessary to know the average load required for all virtual circuits 
and for datagram traffic. In the explanation to follow a virtual circuit 
request for a connect is considered to have a parameter c which identifies 
the expected load required for that virtual circuit. This is used in 
initial virtual circuit assignment in order to minimize congestion. Once 
the virtual circuit has been established, all traffic transmitted over 
that circuit results in an update of the long-term average load in a 
routine identified as vckt.sub.-- in.load, to be described below, which is 
used for subsequent load adjustments. The long-term average has a much 
longer time constant than the link load average used to determine the link 
metric and ultimately the .phi..sub.i.sup.j.sub.k. Additional variables 
for determining the load are the following: 
.gamma..sub.k : the total load on data link k; 
V.sub.i.sup.j : the total virtual circuit load node i destined for node j; 
d.sub.i.sup.j : the total datagram load at node i destined for node j; 
t.sub.i.sup.j : the total load at node i destined for node j, 
(d.sub.i.sup.j +V.sub.i.sup.j); and 
u.sub.imk.sup.j : the virtual circuit load at node i which is destined for 
node j that is routed over link (i, m.sub.k). 
The call setup and disconnect procedures are formulated using four types of 
messages hereinafter denoted VC.sub.-- REQ, VC.sub.-- RSP, VC.sub.-- REJ 
and VC.sub.-- FIN. The message VC.sub.-- REQ is sent initially among the 
nodes in the path to begin the set-up of the transmission. No distinction 
is made between one message that originates internal to a node in an above 
layer and one which is received by way of a data link. This message causes 
an initial local circuit assignment with its state variable set to 
`opening` followed by the transmission of VC.sub.-- REQ to the next node 
in the path. The virtual circuit is considered to be `connected` when a 
VC.sub.-- RSP message is returned from the destination node. Alternately, 
a VC.sub.-- REJ message may be returned which triggers a search for an 
alternate path. Finally, a circuit is `closed` on receipt of a VC.sub.-- 
FIN message. 
Table 16, shown in FIG. 21, below sets forth the sequence of the routine 
Assign.sub.-- New.sub.--VC() for assigning a new virtual circuit in 
response to a VC.sub.-- REQ message. The procedure is initiated by 
updating V.sub.ij and VC.sub.-- Table[] to reflect the incoming link and 
circuit on which the VC.sub.-- REQ message arrived. The datagram routing 
variable .zeta..sub.im.sbsb.k.sup.j has been defined to indicate the 
fraction of datagram traffic destined for node j that is routed over link 
(i,m.sub.k) and implies ample capacity to assign a new virtual circuit 
(i,m.sub.k). Consequently, the link having the largest datagram routing 
variable is initially selected as the preferred link for setting up the 
connection with the `for` loop. If .zeta..sub.best &gt;0, excess capacity is 
available for a new virtual circuit. In this case, an output circuit 
assignment is obtained and the VC.sub.-- Table[] and VC.sub.-- Ret-Table[] 
are updated. Next, a VC.sub.-- REQ message is sent to the next node, 
m.sub.best , to determine whether it may accept a new virtual circuit. If 
it cannot accept a new virtual circuit, the node which requested the 
virtual circuit is notified that none is available, by way of a VC.sub.-- 
REJ message, and the previous assignment is freed up by routine 
Free.sub.-- Ckt.sub.-- Tables(). It is to be observed that if there is no 
available circuit on `best`, then the node sends a dummy VC.sub.-- REJ to 
itself which will ultimately cause recovery to take place. 
If the virtual circuit is accepted by way of receipt of the message 
VC.sub.-- RSP, the load averages V.sub.i.sup.j, .gamma..sub.link and 
u.sub.im.sbsb.best.sup.j must be updated to reflect the addition of a new 
virtual circuit. This is accomplished by the routine Complete.sub.-- 
New.sub.-- VC() set forth below in table 17, shown in FIG. 22. 
Next, the routine Update.sub.-- Tables() sets the circuit state variable to 
`connected`. Once this has been completed, the datagram routing variables 
are changed to reflect the new distribution of the virtual circuit flow by 
the procedure Reassign.sub.-- .zeta.() as set forth in Table 18, shown in 
FIG. 23. 
The purpose of the routine Reassign.sub.-- .zeta.() is to adjust the 
datagram routing variables to make the overall traffic distribution 
(including both datagrams and virtual circuits) closely approximate the 
intended routing variable .phi..sup.j.sub.imk. Based upon the estimated 
average traffic flow over the virtual circuit as well as the datagram 
traffic, this routine calculates the relative excess traffic flow that may 
be assigned to link (i,.sub.mk), after account for the dedicated virtual 
circuit traffic. This relative flow is denoted by: 
##EQU22## 
The above expression assigns a nonnegative proportionality variable 
.psi..sub.im.sbsb.k.sup.j of datagram traffic which is normalized to 
produce the datagram routing variables .zeta..sub.im.sbsb.k.sup.j which 
are nonnegative and sum to 1 for each node (i,j) pair. It should also be 
noted that the link traffic .gamma..sub.k is modified by subtracting the 
previous datagram load x.sub.k and adding the new data gram load. 
If a node receives a virtual circuit reject message VC.sub.-- REJ for a 
circuit it has previously requested, it must either try to reroute the 
circuit or send virtual circuit reject message to the original requesting 
node. This is effected by the procedure Handle.sub.-- VC.sub.-- REJ, set 
forth in Table 19, shown in FIG. 24. The link on which the reject message 
VC.sub.-- REJ was received is added to the list of blocked links. The node 
next looks for the best link, not blocked, for an alternative route. The 
remaining code is substantially the same as the procedure Assign.sub.-- 
New.sub.-- VC() defined in Table 16. 
Once in place, the connection of a virtual circuit is quasipermanent; it 
may need to be disconnected either due to completion of the transmission 
or due to a failure. In the case of a failure, the process is initiated by 
the node detecting that a link has gone down by sending VC.sub.-- FIN 
message, as noted previously. The handling of this message is 
straightforward and defined by the routine Disc.sub.-- VC() set forth in 
Table 20, shown in FIG. 25. 
The virtual circuit finish message may be received on either the 
`link.sub.-- in` or the `link.sub.-- out`; one of the purposes of this 
routine is to propagate the message out on the other link. Consequently, 
the variable `direction` indicates which case is chosen by assuming one of 
the values fwd (forward) or rev (reverse). In addition, a disconnect may 
be generated locally by the node detecting the failure. Using this 
information, the routine first looks up all of the relevant variables in 
the virtual circuit tables using the routine Look.sub.-- Up(). Then, 
.sup.u im.sub.link.sbsb.--.sub.out.sup.j, .nu..sub.i.sup.j and 
.gamma..sub.link.sbsb.--.sub.out are decreased by the amount of the load 
of the virtual circuit that is about to be disconnected. Next, the virtual 
circuit finish messages VC.sub.-- FIN are transmitted. After freeing the 
virtual circuit table entries, the routine Reassign.sub.-- .zeta. (des) is 
executed to adjust the datagram routing variables for the destination 
`dest`. 
In the event that a virtual circuit needs to be rerouted in order to 
prevent congestion in responses to changes in traffic load and network 
topology, the adjustment procedure set forth in Table 21, shown in FIG. 
26, is implemented. This procedure is called periodically after the 
completion of the multiple path routing update mechanism (Multiple.sub.-- 
Path.sub.-- Route ()) which produces an updated set of target routing 
variables .phi..sub.im.sbsb.k.sup.j. Typically, the procedure may reroute 
a small fraction of the virtual circuits in order to better balance the 
load. Since all virtual circuits are candidates for rerouting, the two 
`for` loops iterate for all destinations, j, and all virtual circuits in 
the table V.sub.ij. 
Initially, each virtual circuit is examined to determine that it is still 
routed over a feasible route. If not, the virtual circuit is disconnected 
by accessing the previously defined procedure Disc.sub.-- VC (). In this 
case, the parameter `direction` is set to `both`, so that virtual circuit 
finish messages VC.sub.13 FIN will be sent out on the circuit in both 
directions. For each virtual circuit that is routed over a feasible route, 
the route is checked for proper load balance. Some virtual circuits may be 
disconnected at random with the proability of disconnect increasing if 
there is significantly more virtual circuit traffic on a link than is 
warranted by the routing variable, i.e. a larger value of .delta.1. The 
function `rand` (0,1) produces a random variable which is uniformly 
distributed between the values 0 and 1. The last `if` clause of Table 21 
compares this random variable against a number which is less than 1 and 
which reflects the need to reroute the virtual circuit. A negative value 
.DELTA..sub.1 causes the test to fail and the circuit will not be 
disconnected. The parameter E is chosen to be small, so that the virtual 
circuits are disconnected for this purpose quite infrequently. 
After rerouting the virtual circuit, adjustments to the datagram variables 
are carried out by using the procedure Reassign.sub.-- DG () as set forth 
in Table 22, shown in FIG. 27, which is similar to the procedure 
Reassign.sub.-- .zeta. () of Table 18. The major difference is that the 
procedure of Table 22 updates the datagram routing variables for all 
destinations rather than for a single destination. 
As will be appreciated from the foregoing description, the `feasible route` 
selection scheme in accordance with the present invention obviates the 
drawbacks of conventional traffic allocation schemes, while improving 
speed of route assignment and maximal use of entire network capacity. As a 
consequence of this traffic allocation process, loading of the feasible 
routes of the network is effectively balanced with minimum average delay. 
In addition, the dynamic routing capability may be augmented to establish 
and control the allocation of traffic over virtual circuits within the 
network, which are intended to coexist with dynamic transmission routing. 
In this instance use of the virtual circuits and dynamic feasible routes 
of the network is allocated so as to effectively balance the flow of 
communication traffic over each of the available communication routes. 
While we have shown and described several embodiments in accordance with 
the present invention, it is to be understood that the same is not limited 
thereto but is susceptible to numerous changes and modifications as known 
to a person skilled in the art, and we therefore do not wish to be limited 
to the details shown and described herein but intend to cover all such 
changes and modifications as are obvious to one of ordinary skill in the 
art.