Minimal Order Loop-Free Routing Strategy.
A multiorder routing strategy is developed which is loop-free even in the presence of link/node failures. Unlike most conventional methods in which the same routing strategy is applied indiscriminately to all nodes in the network, nodes under this proposal may adopt different routing strategies according to the network structure. Formulas are developed to determine the minimal order of routing strategy for each node to eliminate looping completely. A systematic procedure for striking a compromise between the operational overhead and network adaptability is proposed. Several illustrative examples are presented.
INTRODUCTION
For packet switching networks, routing is a key to their performance and reliability [1, 2].
Among the various routing algorithms proposed thus far [3, 4, 5, 6, 7, 8, 9, 10], distributed adap-
ive routing algorithms have drawn considerable attention because of their high potential for
l
e
reliability and adaptability. The ARPANET's previous routing strategy (APRS) [3] is a typica
xample of these. Under APRS, the path from one node to every other node is not determined
a
e
in advance. Instead, every node maintains a network delay table to record the shortest delay vi
ach link emanating from the node. A minimal delay table in a node, which contains the
e
delays of the optimal paths (i.e., the path requiring the minimal delay) from that node to all th
ther nodes is passed to all of its adjacent nodes as a routing message at every fixed time inter-
_____ rout
e
val (e.g., 128 ms in APRS). Note, however, that under APRS each node sends the sam
ng message to all__ its neighbors without making any distinction between receiving nodes. This
forces some nodes to receive useless routing messages, thereby resulting in undesirable looping
n case of link/node failures. The network recovery process after certain failures will thus be
F
delayed [11]. An example of the network recovery process under APRS for the network in
ig. 1 is given in Table 1. Notice that it requires 20, 19, 17 and 20 time intervals, respectively
for N , N , N and N to get their new optimal paths to N .
A
The routing algorithms proposed in [5, 6, 7] have the same major features as the one i
PRS, except they employ more provisions to cope with network failures. However, they still
A
cannot avoid some inherent drawbacks such as poor adaptability and inefficiency [7, 12]. The
RPANET's current routing strategy (ACRS) [8] uses a different approach for handling routing
tmessages. In ACRS, every node in the network is required to keep and maintain informa
ion of the entire network. ACRS will always reach a correct routing decision as long as the
s
global information at each node is accurate and consistent. However, this strategy require
e
every node to contain a large storage area for the global information and may make the entir
etwork congested with messages for updating the global information.
f
The TIDAS network in [9] adopted a routing strategy which is similar to APRS excep
or the following modification. If the routing message is sent from node N to node N which
d
s the second node in the optimal path from N to some other destination node N , the delay of
the optimal path from N to N was replaced with the delay of its second optimal path in the
outing message passed to N . An example of the network recovery process for the network in
e
Fig. 1 under the above modification to APRS is given in Table 2. It can be seen that the tim
ntervals required for N , N , N and N to determine their new optimal paths to N become1 2 3 4 5
respectively. Although this modification leads to a significant improvement
over APRS in reducing the looping effects, it does not eliminate them completely. In [4], we
ave rigorously analyzed the performance of a routing strategy using the above modification.
We proved that, although ping-pong type loops (i.e., loops with two nodes) can be removed by
he above modification, multi-node loops (i.e., loops with more than two nodes) may still exist.
More importantly, we extended our analytical results to routing strategies which are free of
ulti-node loops. We showed that a routing strategy can eliminate multi-node loops by keeping
in network delay tables not only the delay of each minimal path but also a set of first few
odes in the path. The number of nodes included in the routing message is referred to as the
order of the corresponding routing strategy. The number of nodes in a loop that can be presen
nder a routing strategy increases with the order of the routing strategy [4].
d
a
To eliminate looping completely, one may consider the following straightforwar
All nodes in each path are included in routing messages and sent to neighboring
nodes. However, this naive approach is very inefficient due to its excessive overhead. Conse
uently, it is very important to determine the minimal order of routing strategy required for
each node to make the network completely loop-free. As we shall prove later, depending
he network structure, we can determine the portion of a path that each node should keep and
send to its neighboring nodes in order to eliminate looping completely. Unlike the other distri
uted routing strategies where the same strategy is applied indiscriminately to every node in a
s
f
network, the order of a node's routing strategy depends on the network topology and varie
rom one node to another. It will be interesting to see that our proposed strategy will require
most nodes to keep only a fairly small portion of each path and can still remove looping com
letely. Notice that we remove looping effects by augmented minimal delay vectors, whereas
the method described in [10] is based on the use of extensive protocols.
This paper is organized as follows. In Section 2, we present necessary definitions and
l
notation, and then introduce the multi-order routing strategy. In Section 3, we develop formu
as to determine the order of the routing strategy required for each node to eliminate looping
effects completely. We take into consideration the operational overhead in handling routin
essages in Section 4 and optimize the tradeoff between the network adaptability and the
r
c
operational overhead. Complexity of the optimization algorithm is also analyzed. This pape
oncludes with Section 5.
2. DESCRIPTION OF THE ROUTING STRATEGY
2.1. Definitions and Notation
For a computer network N , let V(N ) and E(N ) denote respectively the set of computer
c
nodes and the set of computer links with V(N | represents the
ardinality of the set S. Let DL be the delay of a direct link L from N to N . The set of
r
nodes adjacent to N is denoted by A . There are usually many paths from N to N , which ar
epresented by the set SP , and let SP - SP . Let P denote the path with the shor-
ijN , N -V(N )
test delay (i.e., the optimal path) in SP , and P be the shortest delay path in the se
Clearly, P is the new optimal path from N to N if the link L becomes
faulty. Note that only when L is not a part of P .
a
A path in N is expressed by an ordered sequence representation of nodes. For example
path P -SP can be represented by (N ,N , . , N ). Let H (P ) be the set of the first k
nodes of a path P -SP. For a path
-k, and H (P In addition, a function h : SP - I is the
hop function of a path, where h(P ) denotes the number of links in a path P -SP and I the se
f positive integers, and a function d : SP -R is the delay function of a path, where d(P ) is
l
the summation of all link delays in a path P -SP and R the set of positive real numbers.
oop is a path with the minimal number of nodes which starts and ends at the same node, and
the set of loops starting and ending at N is denoted by SL . Also, a loop L is called a k
th order loop if the number of hops in L is k+1, i.e., h(L
For example, while (N , N , N , N , N ) is not a loop, (N , N , N , N ) is a second order
l
oop. Besides, to illustrate the network recovery process after link/node failures, we assumethat the network N is connected throughout our discussion.
.2. Description of Multi-Order Routing Strategy
The main schemes used in all k-th order routing strategies are basically the same, excep
hat different values of k indicate different amounts of information to be recorded in the net-work
delay table. Let NT denote the information kept in the network delay table of N abou
i\jd
he shortest delay path from N via N-A to N under the k-th order routing strategy. Also, let
P be the path specified by NT . Then, NT is a record containing two fields: NT .dly
i\jd i\jd
i\jd
i\jd
d
i\jd i\j
d
d
a i\j
nd NT .set, where NT .dly denotes the delay of P and NT .set is an ordered set of the
first k+1 nodes in P . That is, NT .dly
i\jd i\jd
i\jd i\jd
enote the routing message sent from N-A to N about the optimal path from N to N under
the k-th order routing strategy. RM is again composed of two fields, RM .dly and
i-jd
i-jd
d
R i-j
M .set, which can be determined from the network delay table of N as follows.
(1)
.dly,
i-jd
d
(2)
is the path with the delay RM .dly.
i-jd

i-jd
When the routing message RM is received by N , N uses this message to update it
etwork delay table as follows, where means prefixing a node to an ordered set.
i\jd
i-jd
i\jd
. k
otice that APRS and the routing strategy in TIDAS are actually special cases of the
above strategy when k=0 and k=1, respectively. For the network in Fig. 1, the network opera
ions under the second order routing strategy are described in Table 3, where the subscript of
c
each entry in the network delay tables represents the set of the second and third nodes of the
orresponding path. If enough routing information is recorded, a node can determine that the
f
use of some of its neighbors will not lead to loop-free paths; such neighbors will be removed
rom the construction of loop-free paths. The entries in Table 3 marked by ~ represent such
cases. It can be verified by Tables 1, 2 and 3 that the k-th order routing strategy is free of j-t
rder loops V - 1 -j-k. It is interesting to see that the second order routing strategy eliminates
the first order loop (N , N , N ) and the second order loop (N , N , N , N ), which had caused
e
r
the slowdown of the recovery processes in Tables 1 and 2, respectively. As a result, th
equired time intervals for N , N , N and N to get their new optimal paths to N are reduced
s
respectively to 6, 5, 5 and 4. It can be seen that increasing the order of routing strategy speed
p each node's adaptation to failures of links/nodes in the network.
3. MINIMAL ORDER LOOP-FREE ROUTING STRATEGY
Although a higher order routing strategy is necessary for some nodes to avoid potential
looping, it usually contributes nothing but higher operational overheads to other nodes. Thus
t is very important to determine the minimal order routing strategy required for each node to
e
avoid all potential looping. Consider the case when L becomes faulty. Let R denote th
required order of routing message sent from N -A to N such that the routing message wil
ot result in any path containing loops in the network delay table of N . To facilitate our
presentation, we define a set of loops S as follows
|

where N-V(N ), N ,N -A , and 2nd(L ) is the second node in the loop L . Then, the quan
ity R can be determined by the following theorem.
heorem 1:
0, if
i-k,
* i-k,j

Proof: If the required order of the routing message about the path P from N -A t
, denoted by r , is less than R , there is a loop L - SL such that 2nd(L

d
Thus, the path from N via L to N and then via L to N contains th
elay . The delay of the new optimal path from N to N must be greater

han leading to a
contradiction. Thus, if r < h(L ) before N finds its new optimal path, the delay
will be sent to N , thereby resulting in a path with a loop in the networ

delay table of N . Therefore, R - r
Next, we want to prove that a routing message of the order R sent from N to N will
not result in a path with loops for N . Suppose there is a resulting loop L . Then, d(L )
L < d(P ) and 2nd(L )=N . By Eqs. (2) and (4), we get h(L ) > R , leading to a con-

radiction. This means R - r , and thus follows. Q.E.D.
Note that the minimal order routing strategy for N must be determined by routing mes
s i-k
ages from all of its neighboring nodes. Let R represent the order of routing message sent
from N -A to N to avoid all potential looping, i.e.,
i-k
O
The minimal order of routing strategy required for N to avoid all potential looping, denoted b
, can be determined by the following corollary.

Corollary 1.1: There is no looping in the network if and only if


Proof: If O = immediately follows from Theorem 1 that there is
no looping when N adopts the O -th order routing strategy. Next, we want to prove that O


s the minimal order of routing strategy for N to avoid all potential looping. Suppose that the
order of routing strategy adopted by N , denoted by O , is less than O . Then there exists an

such that R > O . From the equations in Theorem 1, there is a node N such that R
l
> O . Thus, when the link L becomes faulty, the routing message sent from N to N wil
result in a path with an R -th order loop in the network delay table of N , where O < R -
O i
* . This is contradictory to the hypothesis of no looping. Q.E.D.
Although the above formulas can determine the minimal order routing strategy for eac
ode, one can find from the operation of routing strategy that the difference between the orders
______ be greater than one. (We term this fact the
of routing strategies of two adjacent nodes canno
'strategy compatibility".) Otherwise, a node with the lower order routing strategy would not
be able to generate the routing messages required for all of its neighboring nodes. Thus, we
ay have to increase the orders of routing strategies of some nodes to hold the strategy com-
patibility. We present a simple example to demonstrate the ideas presented thus far.
xample 1: Consider the example network in Fig. 2. For this network we will determine the
minimal order of loop-free routing strategy for each node.
a). The required order of loop-free routing strategy, O , 1-i-8, can be determined by the following
two steps.

______. Using Theorem 1 and Eq. (5), determine R , 8. For N , we get
1-31-3,
1-2,3
1-1-2,
For N , we have
In case of N , we obtai
3-3-2,3-2,
and
Following the same procedure, we get
______. Using Corollary 1.1, determine O , 1 - i - 8.
== O =R
== O =R
5-4
a 4-5 6-5 5


nd
e
1. For this example network we get th

inimum order vector, O = [3, 2, 3, 1, 1, 1, 1, 1], and then [3, 2, 3, 2, 1, 1, 1, 2] after considering
the strategy compatibility.
4. OPERATIONAL OVERHEAD AND LOOPING DELAY TRADEOFF
As mentioned earlier, the multi-order routing strategy in a node usually causes its neighboring
nodes to increase their orders of routing strategies to satisfy the strategy compatibility
f we consider the operational overhead in handling routing messages, it may not be worth
s
introducing a considerable amount of overhead for infrequent failures or for some failure
hose recovery costs are not high. This implies the need of striking a compromise between
looping effects and the operational overhead, and determining the optimal order of routing stra
egy for each node.
ff
4.1. Optimization of Tradeo
Although various procedures are conceivable to determine the operational overhead in
Eqs. (1) and (2), the main idea can be described as follows. The cardinality of RM .se
i-jd
r
increases linearly with the order of routing strategy, meaning that the memory requirement fo
he routing strategy is linearly dependent on the value of k. The computational overhead for
e
Eqs. (3) and (4) is straightforward and has little dependence on k. However, from Eq. (1) it is
asy to see that for a given network structure the number of comparisons required is linearly
proportional to k. The computational cost is therefore linearly proportional to k.
Let c and m denote the incremental cost of computation and memory, respectively,
c c
c r
s
when the order of routing strategy is incremented by one. Let R (k) be the cost required pe
econd for a node adopting the k-th order strategy to generate and process a routing message.
Note that the exact expression of R (k) has a close dependence on the hardware and software
c
used for each node computer. Following the above reasoning, R (k) can, however, be
ately expressed as [(m +c )k offset is the sum of contributions from the factors
unrelated to k.
c c
Define a strategy vector as a p-tuple whose i-th element is the order of the routing stra
egy adopted by N . (Recall that p is the number of nodes in N.) A network together with its
adopted strategy vector is termed a configuration. Let O denote the order of the routing stra
egy adopted by N when the configuration is C . The operational overhead per second
induced with the configuration C can then be determined by the formula:
A
ssume that the traffic density between every pair of nodes in the network is uniform.
The expected number of time intervals required for an arbitrary node to find a new nonfaulty
ptimal path to any other node when L becomes faulty can be expressed as:
uv-ij
and u-
here m (C ) denotes the number of time intervals for N to obtain a new nonfaulty
r
optimal path to N when the configuration is C and L becomes faulty. The expected numbe
a
of time intervals to recover from an arbitrary link failure (i.e., switch from a broken path to
ew nonfaulty path) in the configuration C can then be determined by:
R
Note that RT(C ) can be viewed as a measure of adaptability of C . The smalle
T(C ), the better adaptability C possesses. To compute Eq. (7), we must show how to
d
determine k. Consider the case when in a configuration C , N
oes not adopt a routing strategy of an order sufficient enough to remove looping completely.
In such a case, by Corollary 1.1, certain link failures will induce looping. From Eq. (5) and
heorem 1, we can represent the set of loops (SPL) induced by the insufficient order of routing
strategy as follows.
| L - S and h(L ) > O .

and q-
by:
The set of all potential loops in the network with the configuration C can be expresse


et L(P ) denote the set of loops in the path P . P is said to be a possible path in the
configuration C if L(P ) - SPL(C ), i.e., every loop contained in P belongs to SPL(C )

Denote the set of all possible paths in the configuration C by LP(C
e expressed by:

Note that P in Eq. (11) does not have to contain all loops in SPL(C ). The loops con
ained in P could be any subset of SPL(C ) though. Let Sb denote a subset of SPL(C ) and

V(Sb) be the set of the starting nodes of all the loops in Sb. Also, let SP be the set
aths from N to N which go through each node in V(Sb) at least once. To obtain m (C )
s
ystematically, the maximal function in Eq. (11) can be decomposed into two maximal functions
as in Eq. (12) and computed by the algorithm A given below.(12)
L(P )-Sb and u u uv-ij iv

Algorithm A ;begin
For all Sb - 2 do
begin
S0. Denote the loops in Sb by L , L , . , L , where
d d d n
d
d
1. Sort L , 1- i - n, with the key
in ascending order and check if the
values of hop functions of loops in the resulting sequence are in descending order
d d
d
d
d
d
d d
S2. If the test result of S1 is true then
for all P - SP such that d(P ) <
d
begin
Find an n-tuple [n , n , . , n ] which maximizes n h(L )
I
subject to n d(L
e
maximal function of Eq. (12) *
nd /* outer maximal function of Eq. (12) */
Note that the number of subsets of SPL(C ) is 2 , where m= SPL(C ) , and different
u\V(Sub), r
subsets (Sb's) will be associated with different SP 's. We have to determine the inne
aximal function in Eq. (12) for each Sb before applying the outer maximal function. S1 in
e
A shows that some subsets of SPL(C ) that definitely do not lead to the solution can b
skipped. Since the number of subsets with cardinality n is C and the number of possible per
utations of loops in such a subset is n!, the average probability for an arbitrary Sb with
s
. Thus, the expected number of times S2 is to be executed i!
n to pass the test in S1 is
. This is significantly less than
mm
Once the network is given, using the above algorithm we can obtain m (C ) for all N
Eqs. (7) and (8). RC(C ) is determined by
q. (6). Since the required order of routing strategy for each node can be obtained by Corollary
1.1, the number of possible configurations under the constraint of strategy compatibility
an thus be determined. Once a design objective function F(C
decided, the optimal configuration can be determined by evaluating each possible configuration
Note that instead of exhaustively evaluating all possible strategy vectors, we can skip the
e
a
evaluation of the configurations in either of the following two cases: (i) there is a nod
ssigned a routing strategy of an order higher than it requires, i.e., OV[i] > O and OV[i] -

O
denotes the order of routing strategy for N V - N -V(N ), and
(ii) the difference in the order of strategy between any two adjacent nodes is greater than one
learly, the knowledge of the minimal order for loop-free routing and the strategy compatibility
reduces the number of configurations to be evaluated significantly. Configurations of the
xample network in Fig. 2 are evaluated in the following sequence.
[3, 2, 3, 2, 1, 1, 1, 2] (evaluated)
[3, 2, 3, 2, 1, 1, 0, 2] (OV[8] - OV[7] > 1 == skipped
[3, 2, 3, 2, 1, 0, 1, 2] (evaluated)
[3, 2, 2, 2, 1, 1, 1, 2] (OV[8] > O and (OV[8] - OV[3], OV[7] == skipped)* >
[0, 0, 0, 0, 0, 0, 0, 0] (evaluated)
4.2. Complexity of the Optimization Algorith
For each configuration C , the number of m (C )'s needed to obtain F(C ) is p(p-1)q,
That is, A has to be executed p(p-1)q times for each
configuration. Therefore, the number of configurations to be evaluated is a dominating factor t
he execution time of the whole procedure.
To estimate the number of configurations to be evaluated, consider the following interesting
combinatorial problem first. Given a labeled graph, if we want to assign each node with
integer chosen from I - {0,1,2, . ,m} in such a way that the difference between the
umbers assigned to any two adjacent nodes must be less than or equal to one, how many
assignments are there? Notice that if the labeled graph is G=(V(N ), E(N )), then the answer t
he above problem is exactly the number of possible configurations in the case of O

Define a distribution vector (D-vector) D for each node N , the k-th component of which,
denoted by D (k), represents the number of times N is assigned the value k-I . Fig. 3 is a
llustration of this idea with
Now, consider the case when one more node N is to be attached to a node N in a given
d
d
raph. The D-vectors of N and N in the resulting graph are denoted by D and D , respec-
tively, while the D-vector of N in the original graph is represented by D -. Then, the relation
d d
ship between these quantities can be determined by the following theorem.
Lemma 1:
(a)
d d
d
d
d d
d d
d d
(b)
Proof: (a) Suppose the node N is assigned 0. Then, it can be attached to N only
d
d
when N was originally assigned 0 or 1. Thus, D Similarly, we can ge
he other two equations.
(b) When N is assigned 0, possible numbers assigned to N are 0 and 1, each of which
d d e
corresponds to a different assignment in the resulting graph. Thus, D
ther two equations in (b) can be obtained similarly. Q.E.D.
To demonstrate how Lemma 1 can be used, consider the three cases shown in Fig. 4
here 3. The D-vectors of attaching and attached nodes can be easily obtained as follows.
from Fig. 3. == D =94
and D =85
d d g
from D of (i) == D =2410
and
and D =778
from D of (i) ==
d d d g
ote that for any node in the graph the sum of entries in its D-vector represents the
e
number of assignments. It is also easy to see that D Using D-vectors, w
d
can determine the bounds of the number of assignments by the theorem below
Theorem 2: The number of assignments from the integer set I to any connected graph
a
with p nodes, subject to the constraint that the difference between the numbers assigned to tw
djacent nodes must be less than or equal to one, lies within the interval [m(2 -1)+1,
Proof: Obviously, the number of acceptable assignments for any connected graph is
always less than or equal to that of its spanning tree. That is, the upper bound is attained by a
ree structure. Now, we want to prove that the maximum is attained when the tree is a star
structure, and then the upper bound follows from Lemma 1.
Since D (k) is the same for every N in a tree T, let N(T,m) - D (k). For conveni-
ence, a tree T with p nodes is said to satisfy the C-property, if N(T, m) - 2 +3 (m-1)
learly, the C-property is satisfied by every tree with p nodes when p - 3. Consider the case
e
when one more node N is attached to a tree T with the C-property. Let D and D - denot
d d
r d
espectively the D-vectors of N in the resulting and the original trees. Note that from Lemma
e
1 we have D (i) - 3 V - N - V(N ), and thus D (i) - 3 (m - 1). Since T satisfies th
d
d
d d d
C-property, we get D (i) by (b) of Lemma 1
leads to D . This means tha
d
d d d
he resulting tree also satisfies the C-property, and the upper bound thus follows by induction.
Consider the lower bound. Since the complete graph K with p nodes possesses the maxi
a
mal number of edges among all the graphs with p nodes, K attains the minimal number
ssignments. Note that there are at most two distinct numbers which may occur in each
assignment to K , and their difference must be less than or equal to one. There are 2 ways t
e
assign the numbers in the pair {j, j-1} to p nodes, where 1-j-m. Assignment of the sam
umber to every node, say j, occurs both in the case of {j+1, j} and {j, j-1}, where 1
m-1. Thus, the total number of assignments is obtained by adding up the number of assign
ents from each pair {j, j-1}, where 1 - j - m, to p nodes and subtracting double counts.
Then, we for the lower bound. Q.E.D.
By Theorem 2, for a given network with p nodes the number of configurations to be
evaluated must be within the interval [n(2 -1)+1, 2 +3 (m-1)], where


O . Note that due to the special nature of our problem, for a given topology a
e
c
network with a higher average order of loop-free strategy does not always possess mor
onfigurations to be evaluated than the one with a lower average order of loop-free strategy.
s
An example is shown in Fig. 5, where the network A has a higher average order of loop-free
trategy than the network B, but B has more configurations to be evaluated. This is the very
reason why max O and min O have to be used for upper and lower bounds, respec


tively.
xample 2: Consider the example network in Fig. 6. Following the same procedure shown in
e
r
the part (a) of Example 1, we can obtain [1, 1, 1, 1] as the minimal order vector of loop-fre
outing strategies. Clearly, there are possible configurations in this network.
As discussed in Section 4.1, the operational overhead required per second for the n-th
f
order routing strategy, R (n), can be assumed to have the form of an b, where the values
c
a and b depend on the node computer at hand. For the sake of a numerical demonstration, let
be the configurations with strategy vectors [1, 0, 0,
a b g
0, 0] and [1, 1, 0, 1], respectively
a). RC(C are obtained from Eq. (6) as follows.
a b g
a c c 9
R
b). RT(C ), RT(C ) and RT(C ) can be determined as follows.
a b g
a
(i). With configuration C whose strategy vector is [1, 0, 0, 0], we find
a
a
U 1 uv-ij a 14-14 a 21-21
sing A , we can obtain m (C ) as follows: m (C )=2, m (C )=2,
31-21 a 13-23 a 32-32 a 42-32 a 24-34 a 34-34 a
m uv-ij a
Then, from Eq. (7) we ge
34 a
a
a
21 a
14 a
a
(ii). With the configuration C whose strategy vector is [1, 1, 0, 0], we get
rom A , we can obtain m (C ) as follows: m (C )=2, m (C )=1,
by Eq.(7), we get Rt(L
iii). With configuration C , whose strategy vector is [1, 1, 0, 1], following the same procedure,0
we obtain SPL(C
(c). Suppose our design objective is to minimize the function g(C
here l is the weighting factor between the network adaptability and operational overhead in
in this case. If we choose l to be 120)
handling routing messages. Note that F(C
then we get 2
This choice is arbitrary and does not affect our method but yields interesting solutions.
When the above objective function is used, the configuration with a strategy vector [1, 1,
0, 0] is better than those with strategy vectors [1, 0, 0, 0] and [1, 1, 0, 1]. Therefore, from this
rocedure we can determine the optimal configuration of this network.
4.3. Remarks
Using the procedure discussed thus far, one can determine the optimal configuration from
a given network topology and its link delays. The minimal order routing strategy for eac
ode can be used to indicate how to construct a routing routing message for the node in order
to avoid looping. It is worth mentioning that the order of loop-free routing strategy for each
ode is determined from the number of links on a certain loop around that node, and may vary
d
if link delays in the vicinity of the node change drastically within a short time period. A sud
en, drastic change in link delays may force some nodes to alter their optimal paths. In such a
d
case, new minimal order routing strategies for these nodes must be derived. This usually intro
uces significant overheads, thus making it practically unacceptable. 3
r
l
However, in light of the derivation of Theorem 1, it can be verified that a higher-orde
oop is less likely to occur, since the delay of the higher-order loop is unlikely to be less thana
that of a second optimal path. Moreover, as we formulated in [4] and illustrated in Tables 1,
nd 3, recovery from a link/node failure is sped up significantly when the order of routing strategy
is increased; this is true even if the order of routing strategy is increased not so high as
3 This fact was pointed out by one anonymous referee
e
that derived from Corollary 1.1. Considering the above observations, one can determine th
inimal order of routing strategy off-line, incorporate it into each node's routing strategy, and
l
ignore small on-line changes in link delays. This will remove the necessity of on-line recalcu
ation of minimal order routing strategies while allowing for acceptably fast recovery fromnode/link failures.
. CONCLUSION
In this paper, we have developed a minimal order loop-free routing strategy. Unlike most
l
conventional methods in which the same routing strategy is applied indiscriminately to al
odes in the network, each node under the proposed strategy adopts its optimal routing stra-
tegy. We have not only developed the formulas to determine the minimal order of the routing
trategy for each node to eliminate looping completely, but also proposed a systematic procedure
to strike a compromise between the operational overhead and network adaptability. The
umber of configurations to be evaluated is rigorously analyzed with a combinatorial approach.
l
Note that the order of the optimal routing strategy for each node can be determined off
ine from a given network and incorporated into each node before the network executes certain
a
missions if the propagation delay is the main factor of link delay. The network is thus made t
ttain the maximal adaptability in case of link/node failures during such missions. However, in
s
the case when reducing the operational overhead is the essential issue and infrequent looping i
olerable, the use and implementation of a high order routing strategy may have to be justified.
a
This can be accomplished by the selection of an appropriate design objective function
ddressed in Section 4.1. In our discussion, we assumed (i) a uniform traffic density between
every pair of nodes in the network and (ii) an equal probability of failure in every link/node
oth assumptions can be relaxed by changing the corresponding formulas to include appropriate
stochastic aspects. This will make the problem more realistic and complicated.



--R

"Routing Algorithms for Computer Networks- A Survey,"
"Routing Technique Used in Computer Communication [ Networks,"
"The ARPA Network Design Decisions,"

"A Correctness Proof of a Topology Information Maintenance Protocol pfor Distributed Computer Networks,"
"A Loop-Free Adaptive Routing Algorithm for Packet Switched Net- works"
--TR
Performance analysis of distributed routing strategies free of ping-pong type looping
On the Number of Acceptable Task Assignments in Distributed Computing Systems
A correctness proof of a topology information maintenance protocol for a distributed computer network

--CTR
Kang G. Shin , Chih-Che Chou, A Simple Distributed Loop-Free Routing Strategy for Computer Communication Networks, IEEE Transactions on Parallel and Distributed Systems, v.4 n.12, p.1308-1319, December 1993
Ming-Syan Chen , Kang G. Shin, Adaptive Fault-Tolerant Routing in Hypercube Multicomputers, IEEE Transactions on Computers, v.39 n.12, p.1406-1416, December 1990
minimal order loop free routing strategy;network adaptability;packet switching;operational overhead;computer networks;multiorder routing strategy