archives

Utility-Theoretic Heuristics for Intelligent Adaptive Routing in Large Communcation Networks


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Mikler, Armin, Honavar, Vasant and Wong, Johnny (1995) Utility-Theoretic Heuristics for Intelligent Adaptive Routing in Large Communcation Networks. Technical Report TR95-14, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

Utility-Theoretic Heuristics for Intelligent Adaptive Routing
in Large Communication Networks
Armin R. Mikler, Vasant Honavar and Johnny Wong
Department of Computer Science
Iowa State University
Ames, IA 50011, USA
mikler|honavar|wong@cs.iastate.edu
Abstract
Utility theory offers an elegant and powerful theoretical framework for
design and analysis of autonomous adaptive communication networks.
Routing of messages in such networks presents a real-time instance
of a multi-criterion quasi-optimization problem in a dynamic and
uncertain environment. In this paper, we examine several heuristic decision
functions that can be used to guide messages along a near-optimal (e.g., minimum delay) path
in a large network.  We present an analysis of properties of such
heuristics under a set of simplifying assumptions about the network topology
and load dynamics. In particular, we identify the conditions under which one such
utility-theoretic heuristic function is guaranteed to route messages along an optimal
(minimum delay) path in a
network with uniform load except for a single hotspot (when it is assumed that the network load stays constant during the time-frame of interest). We derive bounds on the cost of a sub-optimal path (relative to the cost of an optimal path) as well as the probability that a resulting route between a randomly chosen source-destination pair is suboptimal. We then present a modified heuristic function that
is guaranteed to eliminate sub-optimal routes under the same set of assumptions
about network topology, load, and load dynamics. We conclude with a brief
discussion
of the relevance of the theoretical results presented in the paper to the
design of intelligent autonomous adaptive communication networks and an outline
of some directions of future research.
_______________________________________________________________________
Armin Mikler is currently a post-doctoral fellow at the Scalable Computing Laboratory of
the Ames Laboratory (U.S. Department of Energy) at Iowa State University, Ames, IA 50011.
Vasant Honavar is grateful to the National Science Foundation for its support of his research through the grant NSF IRI-9409580.
The authors wish to thank Yong Zhao, Karthik Balakrishnan, Rajesh Parekh, and Chun-Hsien Chen (all doctoral students in Computer Science at Iowa State University), and Mary Oman (a post-doctoral fellow at Ames Laboratory) for their helpful comments on earlier drafts of the paper.
Introduction
With the unprecedented growth in size and and complexity of communication
networks, the development of intelligent and adaptive approaches to
network management (including such functions as routing, congestion control,
etc.) have assumed considerable theoretical as well as practical significance.
Knowledge representation and heuristic techniques of artificial intelligence,
utility-theoretic methods of decision theory, as well as techniques of
adaptive control offer a broad range of powerful tools for the design of
intelligent, adaptive, and autonomous communication networks. This paper
develops and analyzes some utility-theoretic heuristics for adaptive routing
in large communication networks.
Routing  in a communication network refers to the task of
propagating a message
from its source towards its destination. A routing algorithm has to, among
other things, select at each node, for each message received by, or originating
at that node,
a neighboring node to which the message is to be sent (unless the receiving
node happens to be the destination). Such a routing algorithm may be
required to meet a diverse set of often conflicting
performance requirements (e.g., average
message delay, network
utilization, etc.).  This makes routing an instance of a multi-criterion
optimization problem.
In general, for a network node to be able to always make an optimal
routing decision
(as dictated by the relevant performance criteria)
it requires not only up-to-date and complete knowledge
of the state of the entire network (including such things as network connectivity
and load at each node) but also, an accurate prediction of the behavior of the
network during propagation of the message through the network (in other words,
a precise knowledge of the dynamics of the network).  A moment's reflection
shows that this is impossible in practice.
Thus, a routing algorithm must be capable of adapting to network state
changes in almost real time in an effort to optimize the desired performance
criteria.
In practice, all routing decisions in large communication networks are based
on imprecise, uncertain knowledge of the current network state. This
imprecision or uncertainty is a function of the network dynamics,
the memory available for storage of network state information at each node,
the frequency of, and propagation delay associated with,
update of such state information. This makes the routing task, a resource-constrained multi-criterion optimization problem. Resource limitations (e.g.,
memory for storing network state information at each node) generally will
not permit storage and use of a precise description of the state of the
entire network. Thus, the routing decisions, in practice, have to be based
on knowledge of network state over a local neighborhood supplemented perhaps
by a summary of the network state as viewed from a given node.
Motivated by these considerations, a class of adaptive heuristic
routing algorithms have been developed over the past few years
. Experiments demonstrate
that such algorithms have a number of interesting properties including:
automatic load balancing and message delay minimization. To date, the
design of such algorithms has relied primarily on intuition
and experimentation, in the absence of an adequate theoretical framework
for analysis and design of appropriate heuristics. The work described in
this paper is a tentative step toward the development of such a framework.
In what follows, we draw upon concepts of utility theory
to design and analyze utility-theoretic
heuristics for routing in large communication networks. Various
heuristics are designed and their properties
are precisely analyzed in section 2. The relevance and limitations of the
main results of the paper and some directions for further research are
discussed in section 3.
Utility-Theoretic Heuristics for Routing
Routing messages in large communication networks so as to optimize
some desired set of performance criteria presents an instance of
resource-bounded, multi-criteria, real-time, quasi-optimization problem.
Our proposed solution to this problem involves the use of utility-theoretic
heuristics. The heuristic function enables each node  in the network
to select a
best neighbor in its neighborhood to route a message  (which it
has received or generated) towards
its destination. Ideally, this decision is to be performed so as to optimize
a set of desired performance criteria. Utility theory offers an elegant
theoretical framework for exploring the design and analysis of such
heuristic functions. This section briefly reviews the key concepts of
utility theory in the context of routing in large communication networks,
provides examples of utility-theoretic heuristics, and presents a precise
characterization of their properties.
For the purpose of this analysis,
it is assumed that the network is a regular rectangular grid (with adjacent
nodes being unit distance of each other). Additional assumptions concerning
load and load dynamics are made as necessary.
Guiding a Message Using Rewards
Since each node has to route each message that it receives towards its
destination, it needs some directional guidance to accomplish this
objective. We can model this in terms of a reward function
that assigns a reward to a message upon reaching its destination.
Then it is natural to think of each node
as receiving a partial reward corresponding to each message
that is routed through it towards an appropriate destination node.
Such a reward function rewards each node for making a particular
routing decision. Since the primary objective of the reward function
is to guide messages toward their destinations, we could use a variety of
functions that assign rewards to a node  according to some inverse function
of the distance to the destination  of the message  being routed
through . The values of partial rewards that will be received by a
node  for routing a message destined for  can be represented
using a reward landscape .
Let  denote the Manhattan (or
city block) distance between a node  and  (This
makes sense in a grid network but other network topologies might call for
the use of other distance measures).
We define the partial reward for node  as follows:
where  is a reward function chosen
such that .
There are many possible choices for the reward function
A particular example of  is given by
where  and  are the dimensions of the grid network.
The corresponding reward landscape for an  grid network with
destination node  is shown in Figure . Note that
the results that follow are independent of any particular choice of
so long as the reward is an increasing function of distance between the node
and the destination.
With a slight abuse of notation, assuming additive rewards, we can define
a cumulative reward  that is obtained by a message  traveling
along a path  (from its source  to its destination
) as follows:
Routing Messages Along Optimal Paths in a Uniformly Loaded Network Using Rewards, Penalties, and Payoffs
At each node along its path, the message incurs a penalty.
Such penalty incurred by a message  at each intermediate node
along a path  can be modeled by a cost .
It is assumed that  is non-negative and bounded from above
by
some constant  for all messages and for all nodes in the
network. That is,
. It is further assumed
that the penalty
remains constant during the time it takes to make a routing
decision for message  at node .
If cumulative delay is a performance criterion that is
to be minimized by the routing algorithm a natural interpretation of
is the delay suffered by a message (on account of load) at
. (However, since delays can become unbounded when there is
queueing, it may be necessary to discard some messages in order to
keep the delay bounded at the expense of message loss. Alternatively,
feedback could be used to discourage messages being routed through
. We will not address these issues in this paper.) If cumulative
load is the criterion to be minimized,
is bounded by the maximum utilization .
The total penalty or cost incurred along a path  is given by:
We can now define the net partial payoff  received by a message
when it reaches the node  on its way to its destination
as follows:
Correspondingly, the total payoff along a path  is given by:
Let  be a minimum cost path from a source  to a
destination . The cost  along this path is given by:
In the discussion that follows, in order to simplify our analysis,
we proceed under the assumption that the network is uniformly loaded.
(The implications of this assumption are discussed in section 3). This
assumption is captured by the following definition:
If  (),
we refer to the network as a uniform cost network.
In a uniform cost network a routing algorithm which propagates a message
such that  is maximized at every intermediate
step will yield an optimal path  with cost .
Proof of Lemma
Since in a uniform cost network, , the partial reward  from
equation  can be written as
Thus,  can be maximized at each intermediate node along a path
simply by maximizing .
Let  be the number of nodes on a path .
As message  is propagated
along a  such that  is maximized at every intermediate step,
in a regular grid network,
the property of the reward function (i.e.,
) guarantees that  is propagated along
a shortest path (as measured by the number of hops)  from the source  of the message  to its destination
Thus, from equation  we have:
Since  is a minimum hop (shortest) path, it follows that .
It needs to be emphasized that the assumptions of this analysis are
difficult to meet exactly in any realistic scenario. If nothing else, even
if the network started off with uniform load, the act of routing a message
from one node to another will perturb this uniformity.
It is easy
to see that if the uniform load assumption is
not met, a routing algorithm that simply selects a neighboring node that
has the largest partial reward cannot guarantee that the resulting paths
are minimum cost paths.
However, if deviations from the uniform cost assumption
are ``small'' enough to not deflect a message from an optimal
path (considering additional delay that is encountered by a message as
a result of being routed along a minimum length path - as dictated by
the reward function as opposed to a longer path that might have a lower
cumulative delay),
the result
continues to hold.  It is also worth pointing out
that in large networks with hard to predict network dynamics, routing
decisions have to be based on imprecise knowledge of network state and
dynamics and there is no way to get around sub-optimal routes. A primary
purpose of the preceding analysis as well as the analysis that follows is
to develop a class of utility-theoretic heuristics that would be useful
in routing messages along near-optimal routes in such networks.
Extensions of Lemma  to networks that are
only approximately uniform cost networks, locally uniform cost
networks, or probabilistically uniform cost networks are therefore
of interest. However, we will not explore such extensions in this
paper.
In section 2.3 that follows,
we relax the uniform cost assumption by allowing a single hotspot
(or a node with a high load) in an otherwise uniformly loaded network.
Routing with Utilities
Utility is a measure that quantifies a decision maker's
preference for one action over another (relative to some criteria
to be maximized) .
The utility function may be composed of several parts
that model different types of payoffs, and weight the
various parts as necessary to reflect the preferences of the
decision maker. When the result of an action is uncertain, it is
convenient to use the expected utility of each action to pick
actions which maximize the expected utility.
The utility  of node   (with respect to
a destination ) is computed by one of its
neighboring nodes, ,
as  attempts to route a
message  that it has received (or generated),
along a desired (e.g., minimum cost) path, to 's destination, .
It is typically
a real-valued function of the (usually limited) network state information
available at node , the message , and perhaps other parameters.
Thus, each node
can use utilities of its neighbors to pick one that offers the
highest utility value. Thus a node
preference-orders its neighbors  according
to their respective utilities. We say that the router at
is indifferent to
the choice between two neighbors  and say
if  (where  is the destination of the message
being routed by ).
We denote the indifference between two nodes as
.  We say that a neighboring node  is preferred (by the router
at ) over another neighbor  if . We denote
this preference by
In our treatment of uniform cost networks in section 2.2,
the partial payoff  implicitly served as the utility
for the purpose of routing messages along minimum cost paths.
That is, we set . Let us call this utility function .
is a utility function which is given by .
Note that the use of the naive utility function
guarantees minimum cost paths
only if a uniform cost
network is assumed. The uniform cost assumption renders the cost
component in the payoff function irrelevant to the routing
decision. This is no longer true when the network is not a uniform
cost network. In what follows, we relax the uniform cost assumption
by allowing a single hotspot (a node with a high load relative
to its neighbors) in an otherwise uniform cost network.
A hotspot, , in an otherwise uniform cost network is a single
network node which has a higher load than its
neighbors so that a message  traveling through it incurs a cost
(whereas the same message if it were to travel through
a node  where , it would incur a cost ).
The neighborhood  of a node  is the set of nodes ,
such that there exists a direct communication link  from  to .
Thus, in a regular rectangular grid, each node (with the exception of the boundary nodes)
has exactly 4 neighbors.
Note that since the costs  are bounded by , it follows that . Further note that the above definition of a hotspot does not say anything
about the relative difference in costs  and . A more realistic definition of a hotspot might insist that the cost of routing a message through a
hotspot is significantly large relative to routing the same message
through a node in the neighborhood of the hotspot. Also, when a network deviates
substantially from the uniform cost
assumption, it is more useful to focus on the load distribution in the vicinity
of a node rather than hotspots per se. However, to make the analysis
mathematically tractable, the discussion that follows focuses
on routing in an otherwise uniform cost networks with a single hotspot.
Routing in an Otherwise Uniform Cost Network with a Single Hotspot
As the uniform cost assumption is relaxed by allowing a hotspot
with cost  in the network, it is easy
to show that relying on partial payoffs alone as utilities
for routing messages can result in sub-optimal routes.
Consider a grid network with node coordinates increasing as a message
travels east and south. From the uniform cost assumption, we have
Let , , , and  be the x and
y coordinates of 's source and destination, respectively. Let
and  be the x and y coordinates of a hotspot in one of the following
configurations:
or
In this case, clearly, the probability that a shortest path from  to  passes
through the hotspot  is non-zero. Hence, there exists a node
with  that must decide how to route
so as to minimize the total
cost incurred by . As we show below,
if this decision is based on a preference ordering
induced by the naive utility function  given by  (as in section
2.2 above), messages can be routed through the hotspot thereby incurring
a higher cost than they would have otherwise.
For the discussion below, we assume that the reward functions chosen guarantee
that
in the network such that
whenever
This ensures that the cost  of a node , (and
in particular) does not offset the guidance provided through
unless two nodes with equal rewards are being compared.
In the following we distinguish 4 canonical cases. We focus in our
analysis
on configuration  above. Similar arguments hold
for configuration .
Case 0
Case 0 combines 4 scenarios of placing nodes , , and  in the
grid network, each of which presents a trivial routing problem.
In these scenarios, at least two of the nodes , , and  are
identical, that is:
, and
Clearly, in scenarios 1 and 2, no routing decisions are needed as the message
source coincides with the destination. Whenever the message source
coincides with the hotspot as in scenario 3, the routing algorithm will
select a neighbor  with the highest utility. Hence,
the routing algorithm performs as in the case of a uniform cost
network (without hotspots). For scenario 4, Assumption  assures that
yields the highest partial reward , despite the
fact that the cost incurred by hotspot conditions reduces its partial payoff.
Hence, routing decisions can be made without taking cost  into
consideration, as in the case of a network without hotspots.
Case 1
Let  denote the number of minimum hop paths from a node
to node .  is given by:
Case 1 encompasses all placements of nodes , , and , such that
or
where
(see Case 3)
An example of Case 1 scenarios is shown in Figure .
Here, the hotspot
does not share either the x or y coordinates of  or .
That is, .
In this configuration, the
number of minimum hop paths from  to  is ,
and
any such partial path would lead to a minimum cost path if all nodes
that neighbor the hotspot (i.e., ) take action to
route  so as to circumvent . Thus, the utility function
given by  is guaranteed to route  on a minimum cost path
to its destination . This follows from the existence of
since minimum hop
paths that avoid going through the hotspot.
In a uniform cost network with a single hotspot  located
such that ,
a routing algorithm which propagates a message  such that
is maximized at every intermediate step
will yield an optimal path  with cost .
Proof of Lemma
Clearly, the only nodes at which a decision has to be made to circumvent
are  or
and , respectively. Since
, there exist nodes  and
with coordinates  and ,
respectively, that lie on a minimum hop path from  to .
Since  it follows that
. Hence, a routing decision in
or  that maximizes the partial payoff will choose  or
to propagate  towards .
Since , and  is propagated along
a minimum hop path, Lemma  guarantees that  is routed along an
optimal path .
Case 2
Here, , , and  are placed such that
or
(see Figure ), i.e.;
Assuming the former, there exists
a node  with coordinates  with
from which the
number of minimum hop routes .
Since in a uniform cost network ,
the naive utility function  can guide a message
through , thereby committing to a path  with cost .
Assuming that  is only routed using utilities to choose among
minimum hop routes,
the additional cost   is inflicted on
by . If  is permitted to deflect from a minimum hop route,
the additional cost  is inflicted by
itself or due to the extended length of  in circumventing
Case 3
This scenario consists of all placements of , , and
such that  or
(see Figure ).
Since there is only a single optimal path  from  to , i.e.,
, message  must either visit  or
deflect from the minimum hop path in order to circumvent .
, however is not sufficiently informative to guarantee an
optimal routing decision. Hence,
may be routed along a path  for which .
In the following we assume that a node  upon
receiving a message  from a neighbor node
will refrain from propagating  back to .
This is a natural assumption that is meant to avoid the so-called
bouncing of messages back to a node from which it was routed.
In a uniform cost network with a single hotspot ,
a routing algorithm based on  will deflect a
message  at most once in order to circumvent  provided
bouncing is avoided (via Assumption ).
Proof of Lemma
Consider a node  with
coordinates  such that
(Similar analysis holds for the case where
Node  can deflect  to a node  with coordinates
, such that
Clearly, .
Since , . Hence there must
exist a node  with
which lies on a minimum hop path  from  to
such that .
The choice of the reward function
guarantees that .
In a grid,
such that  (since the reward
function ensures that the rewards vary inversely with the Manhattan distance).
Since , . This limits
the routing choices for message  at  to  and , of which, by
assumption ,
has to be chosen (since otherwise  will be bounced back to ,
which had routed the message to  to begin with thereby violating
assumption ). This ensures that from ,  is sent along
a minimum hop path  to the destination . Since ,
Lemma  guarantees that  is propagated along
without further deflection.
The preceding analysis sets the stage for the following theorem which
bounds the cost of a suboptimal path in an otherwise uniform cost network
with a single hotspot.
In a uniform cost network with a single hotspot  with
(where ),
a routing algorithm which propagates a message  such that
is maximized at every intermediate step
is guaranteed to yield a path  with cost  such that
Proof of Theorem
In Case 1, Lemma  guarantees that a routing
algorithm based on
will find a minimum cost path if , , and
are placed such that
Hence,  and thus .
Case 2 involves a node  with
coordinates  such that
or
. Now
must decide whether to route message  through  or to
deflect  from a minimum hop path. Routing through  will result in
a path cost  which is sub-optimal by an amount . That is,
If  chooses to deflect  so as to circumvent ,
is propagated along a path . Let  be the length (in
number of hops)
of the minimum hop path  from  to  via  and
be the length of path . Deflecting from
path  in a grid topology yields a path  with
. Lemma  guarantees that
is deflected at most once, .
Hence .
In Case 3, the cost  for a minimum cost path
between  and  is given by
. Hence,
If  coincides with either  or , the hotspot
cannot be circumvented and . (That is, the minimum cost path
has to necessarily pass through the hotspot in this case).
Clearly,  and .
Therefore, .
The Probability of Sub-Optimal Routing Using
Let the probabilities of a sub-optimal path due to Cases 1, 2, and 3 be
, , and , respectively.
Only Cases 2 and 3 can result in
suboptimal paths when routing decisions are
based on . Thus, .
The probability of sub-optimal routes  in an N-node
grid network
is given by:
The probability  is computed as:
where  and  are the probabilities
of sub-optimal paths when  and , respectively.
In equation ,  is the set of all possible placements of
and  such that
, the set of hotspot placements  such that
lies strictly between  and  and .
, the set of hotspot placements  such that
lies strictly between  and  and .
Let  be a node with coordinates  such that
in the case where
(  if ), with
(or  correspondingly).
Let
and
(respectively)
be the number
of minimum hop paths from  to
and from  to .
The probabilities  and
are given by:
where  is the probability of a particular configuration of
, , and  in the  grid (assuming each such
configuration to be equally likely).
It is clear that a message in transit from a source to a destination in
a source-hotspot-destination configuration corresponding to the scenario in
Case 3 will be routed through a hotspot if routing decisions at each node
are based on . Depending on the relative difference between  and
, this may or may not yield an optimal path. Thus, we can establish
an upper bound on the
number of possible sub-optimal routing decisions in the scenario
described in Case 3
in terms of
the number of such source-hotspot-destination configurations
that are possible
in an  network.
The resulting probability of sub-optimal path arising out of
a node placement corresponding to to Case 3, namely ,
is given by:
and  count the number of possible node
placements in each row and column of the grid network that constitute a Case 3
scenario. Equation  represents an upper bound on  as it
counts some of the trivial scenarios listed under Case 0.
The preceding analysis can be summarized in the form of the following
corollary:
The expected penalty for choosing sub-optimal routes in a
otherwise
uniform cost network with a single hotspot due to routing decisions
based on  is bounded by .
Eliminating Suboptimal Routing Using A Modified Utility Function
So far, routing decisions in node  are based on the simple utility
function  given by  which preference-orders nodes  in
according to the payoffs . Note that
, is determined solely from local information
available when a message  arrives at , such as the reward , and the cost .
Sub-optimal routing scenarios discussed above arise primarily as a result of
a lack of knowledge at  at the time it is routing a message  to a neighbor , regarding
the likely cost of completing the path from  to the destination of ,
namely, . As shown in section 2.4, source-hotspot-destination configurations corresponding to scenarios described in Case 2 and Case 3 can result in
sub-optimal routes (i.e., ) when routing decisions are based on .
In what follows, we explore modifications of  to obtain a utility function
which is guaranteed to eliminate suboptimal routing decisions that arise in
source-hotspot destination placements corresponding to the scenarios in
Case 2 and Case 3. We proceed in two steps: First, we define a utility function
that eliminates suboptimal routing decisions that arise in scenarios
corresponding to Case 3. We then
modify  by introducing a cost estimator function to obtain a utility
function  designed to eliminate suboptimal routing decisions that arise
in Case 2 scenarios as well.
Eliminating Sub-Optimal Routing Decisions in Case 3 Using a Utility Function
Let  be a utility function given by:
exploits the fact that messages are to be routed in
a uniform cost network with a single hotspot.
If routing decisions are based on the preference ordering
induced by  in an otherwise uniform cost network with a
single hotspot, every message originating in a source  and a destination
that correspond to a source-hotspot destination placement described
in Case 3
is guaranteed to be propagated
along an optimal path  between  to .
Using ,  can decide whether or not to propagate
through a hotspot  in its neighborhood or to circumvent the
hotspot by routing  through
a different neighbor . In other words, the preference ordering
induced by  ensures that at a node neighboring a hotspot in a Case 3
scenario we have:
and
Thus all routing decisions based on  in Case 3 scenarios result in
optimal (minimum cost) routes. In other words, in
equation ,  is reduced to .
It is easy to see that  does not eliminate the possibility of a sub-optimal route in a source-hotspot-destination configurations corresponding to the
scenario in Case 2, leaving  in equation  unchanged.
The preceding analysis is summarized by Corollary 2:
The expected cost penalty associated with a sub-optimal route in an
otherwise uniform cost network with a single hotspot due to routing decisions
based on  is bounded by .
Eliminating Sub-Optimal Routing Decisions in Case 2 Using a Utility Function
As shown by the preceding analysis,  can result in a sub-optimal
routing decision in a source-hotspot-destination configuration corresponding
to the scenario in Case 2. In particular,
any routing decision in a configuration corresponding to Case 2 will
result in a sub-optimal path  if it results in the propagation of a
message  to a node
such that  or
. Routing decisions based
on a preference ordering induced by  can lead to such a situation
since in a neighborhood  of  such that ,
provided .
Note that Case 2 scenarios include
all placements of , , and , such that
, such that .
These observations suggest the possibility of using
an estimate of the cost along paths from  to  as
a component of a modified utility function  so as
to induce a preference ordering between nodes (where no such preference
ordering is induced by ) so as to eliminate suboptimal routing
decisions altogether. In other words,  should be able to induce
a preference ordering among nodes  and  in the neighborhood of
a node  (the node making the routing decision for a message ) such that:
and
We now proceed to define a cost estimator function  as follows:
A cost estimator function  estimates
the cost  of a minimal cost path to a destination
from a node .
It would be nice if the cost estimator function defined above helps  to
induce the desired preference ordering necessary to guarantee routing along
an optimal path in the scenario corresponding to Case 2. We capture this
property by defining what are called  cost estimator functions.
A cost estimator function is said to be admissible if forall nodes
in
the network,
for all nodes ,  in the neighborhood
of , the following conditions hold:
and
We define a utility function  as follows:
In the discussion that follows, we make the following assumptions.
The cost estimator function
used in equation 15 is admissible.
Clearly, the estimate returned by  must be based, at the very
least, on some knowledge of the current cost distribution in the network.
In general, more precise estimates would require knowledge of the network dynamics. If costs associated with each node are allowed to change with time, as would be the case in a more realistic routing task, since
is computed at the time a message  is being
considered for propagation through , to a
destination ,
has to change with time as well (so as to reflect the changes in
the costs associated with various nodes in the network).
However, the representation of network cost distribution
cannot be specific to a particular destination node  since
is specified independently for each message. Thus we need
an intermediate representation of the costs associated with each
node in the network at a given time which the cost estimator function
can use. Any such representation, in order to be useful in
practice in large networks, must not require the storage and update at
(or broadcast to)
each node, of cost values for all the nodes in the network
regions of the network. Ideally, it must adequately summarize the load
values in large regions of the network as viewed from a given node.
These considerations (among others)
led us to define a view, , which is
maintained in every node in the network
In a rectangular grid network, this view consists of four components,
one for each of the four directions - north, south, east, and west.
Thus we have:
Each component
represents a weighted average of costs  along the minimum
hop path from  to the border of the grid network in the direction specified
by .
Consider two nodes,  and , located such that  and
is to the east of , i.e.,
. Then
is given by:
,, and  are computed using analogous formulae.
Note that the views summarize the costs associated with nodes along a general
direction. Given the recursive nature of view computation, views take a certain
time
to stabilize after major load changes in the network. This requires a careful
choice of frequency of view update etc. The reader is refered to
for a discussion of this and
related issues.
In the discussion that follows, we assume that sufficient
time has elapsed for the view computation to stabilize before the view
is used in the computation of cost estimates using .
In practice, this assumption need not be satisfied exactly so long as
the views are adequately precise to ensure the admissibility of the
cost estimator function defined below.
Assuming that  is located such that .
Let  and  denote the
distance from  to  in  and  direction, respectively.
is given by:
The estimator defined by equation  is one of several
alternatives that are possible. We will not delve into a consideration of
alternative definitions of  in this paper. It is easy to verify that
the estimator given by equation  is in fact, admissible.
In what follows, we
revert back to the primary focus of this section, namely, utility functions
for making optimal routing decisions in an otherwise uniform cost network with
a single hotspot.
For all nodes  in the network,
for each message  from a source  to a destination  that reaches
a node ,
the routing decision at  based on the preference ordering
induced by  will route  along
a path  selected only from the set of
minimum hop paths from  to , unless  and
Proof of Lemma :
Consider a routing decision to be made for message  by a node . Since  and ,
there must exist at least one node  such that  and
(i.e.,  is closer to the destination ()
than ). For Lemma  to hold, we have to show that the router at
, based on the perference ordering induced by , will necessarily
route  to such a node . That is,  must ensure that  will
not route  through a node  such that . In other words, in this scenario we have to
show that  as per the preference ordering induced by .
Note that by Assumption   and
, and  (This follows from
the fact that  and  are one hop from each other,  and  are one hop from each other,
and  and  are two hops from each other). Since ,
equation  guarantees that . By equation
, and thus . Thus we have
which implies . This implies that  routes  through . Since  and
(where  is a minimum hop path from  to ),
this proves lemma . .
The preceding discussion sets the stage for Theorem  that establishes a
major property of the utility function , namely, that it eliminates
suboptimal routes in an otherwise unformly loaded grid network with a single
hotspot.
In a uniform cost network with a single hotspot  with an associated
cost  (where ),
a routing algorithm which makes routing decisions at each node based on a
preference ordering induced by
is guaranteed to propagate each message  along a minimum cost path .
Proof of Theorem
Consider the placement of  and , such that
. (Analogous arguments hold for other
source-destination configurations).
For nodes , , and
for which , ,
and , as per preference ordering
induced by  for a message to be propagated from ,
Hence, a message will be propagated through the network along
a minimum cost partial path until a routing decision
has to be made which involves a node  with coordinates
or .
At this point, the utility of  is below that of some
with coordinates
on account of the relative values of the cost estimates
and .
This causes the message  to be propagated to a node  with coordinates
We can now show that  will always circumvent
and is propagated along . We will consider each of the four cases
in turn.
Since routing in Case 0 scenarios is equivalent to routing in the absence
of hotspots, we have . Hence, a message  will travel along a
minimum delay path .
As an example for Case 1 scenarios, we have .
Consider the two possible routing decisions  and  with
coordinates  and
respectively. Since both  and  offer
a minimum cost path to , either decision will cause the message  to be
routed along an optimal
path .
Since  for  or  and
,  will circumvent  while
approaching . Lemma 4 assures us that  will propagate messages
only along a minimum hop path
and since given the same number of hops, a path that circumvents a hotspot
is necessarily of a lower cost than a path that goes through a hotspot,
we can say that for all source-hotspot-destination configurations that
correspond to the Case 1 scenario,  guarantees that  is propagated
along an optimal path .
In a Case 2 scenario, the routing algorithm has to
choose at a node , a neighbor from among
nodes  and  with coordinates
and
. Clearly, a routing decision that
would yield  will result in a suboptimal path  since
We can now prove that a routing decision based on the preference ordering
induced by  will necessarily select
over  thereby circumventing .
Clearly,
. Since all nodes to the east of  have cost ,
equation  yields . It follows therefore
that the east view computed
at  is . Correspondingly, the south view
computed in  is . As  does not
impact the south view of  or the east view of ,
we have . Since  and  have the same
distance from , we have . Therefore the
preference ordering between  and  for routing decisions in  is determined
by the relative values of  and . In other words,
is prefered over  if .
and  are given by:
is then given by:
Since  it suffices to consider the difference
which simplifies to
Now,  and  should
be prefered over . This is the case when
Since ,
. As  and , we must have .
Therefore,  and a routing decision based on
will route the message  to  on its way to the destination .
For Case 3 senarios,  uses  which, by Corollary , will yield
an optimal path .
This proves Theorem   .
Discussion and Summary
Decision theory and artificial intelligence provide a range of tools that can be useful in the design of intelligent, adaptive, self-managing
communication networks. Decision and control tasks that arise in such networks
(e.g., routing decisions made at each node, actions taken to balance the
load across the entire network, etc.) have to attempt to satisfy as closely
as possible, multiple, and often conflicting, performance criteria.
Examples of such performance criteria include:
network throughput, maximum tolerable delay, maximum tolerable message loss,
average delay, degree of load balancing, etc.
Conventional routing and
control mechanisms rely on relatively up-to-date information about the
state of the entire network. Hence,
in large communication networks
with thousands of nodes distributed over a wide
area,
they entail tremendous resource overhead in terms of
memory needed at individual nodes, computation time for making decisions, and
network bandwidth needed to keep the information up-to-date.
The overall effect of this phenomenon include:
reduced utilization of the network (in terms of network
bandwidth used to actually transmit messages as opposed to information needed
for network management) and/or deterioration in the quality of routing and
control decisions as measured by some performance metric.
This requires an understanding of the complex interactions
that exist between different measures of network performance and resource
requirements and the development of a coherent framework that facilitates a smooth
tradeoff of some of the performance measures and resource requirements against
others on demand.
In this paper, we have formulated some simple utility-theoretic heuristic
decision functions for guiding messages along a near-minimum-delay path in
a large network. We have analyzed some of the interesting properties of
such heuristics under a set of simplifying assumptions regarding network
topology and load dynamics. For a regular grid network with uniform load
(with the exception of a single hot spot), we have identified the
precise conditions under which a simple and computationally efficient
utility-theoretic heuristic decision function is guaranteed to route a message
along a minimum delay path when it is assumed that the change in
network load is negligible during the time it takes to make a routing decision.
We have derived an upper bound on the
sub-optimality of a path. We have established an upper bound
on the probability that a path between a
randomly chosen source-destination pair is sub-optimal by considering
configurations of uniformly loaded grid networks with single hotspots
under the assumption that each source-destination pair is equally likely.
We have also designed a modified heuristic function that is guaranteed to
yield optimal routes under the same set of assumptions about network topology,
load, and load dynamics. The latter is very similar in spirit to
utility functions that were developed (mostly based on intuition rather than
sound mathematical foundations)
and experimentally studied in .
Indeed, the study of utility-theoretic heuristics which is described
in this paper, was, at least in part, motivated by a desire to formulate the
heuristc routing functions and to understand the
experimental results in more precise mathematical terms.
Some natural questions to ask at this point include:
How realistic or practical are the various assumptions that were made in our development and analysis of utility-theoretic heuristics for routing? How can the results be applied
(if at all) to more realistic communication network environments in which
assumptions regarding network topology, load, and load dynamics
do not hold? How can the analysis be extended to such scenarios? How can
computationally efficient
utility-theoretic heuristics be designed for different sets of performance
criteria for such complex and dynamic
networks so that they become essentially autonomous and self-managing?
Although this paper does not provide complete and satisfactory answers
to all these questions, we believe that it constitutes a useful (albeit perhaps tentative) first
step in that direction. In this context, a few comments are in order.
Results of a wide range of experiments using heuristics that are very
similar in spirit to  display the property of automatic
load balancing .
This suggests that
the simplifying assumption of uniform network load (except at a hot
spot) is useful at least as a crude first approximation of a more realistic
scenario. A hotspot is typically caused in such a network due to
extensive influx of traffic to a particular network node (or group of nodes)
or a node or link failure (which is generally assumed to be rare in modern
communication networks). However, the behavior
of the routing functions compensates for this change by redistributing traffic
away from the hot spot. Also, given this behavior, it is reasonable to
assume that the probability of several hotspots occurring simultaneously
within close proximity of each other in such a network is generally quite small.
A possible exception to this scenario would be a hotspot region (caused for
example, by a failure of an entire subnetwork as could occur in the event
of a major natural disaster). When the hotspots are not in close proximity
of each other, the single hotspot assumption holds at least locally in
a large network. Similarly, the uniform load assumption is also likely
to hold (given the load-balancing tendency of the heuristic routing
functions), at least locally (except for the discontinuity introduced by
a hotspot), in a large network.
These observations suggest that
our analytical results are likely to be useful (at least in qualitative terms) to
guide the design utility-theoretic
heuristics for a
a more complex network. Of course, this does not mean that it is not
worthwhile to extend our analysis to a range of increasingly complex
scenarios by removing some of the simplifying assumptions. Some obvious
cases to consider include: allowing irregular grids; allowing non-uniform (but
relatively smooth) load distribution - except at a hotspot, allowing multiple
hotspots or contiguous hotspot regions (of various shapes), etc.
It is perhaps worth emphasizing that the utility function  developed
in this paper yields minimum delay paths if certain assumptions regarding
network topology, load, and load dynamics hold - by making use of the
measured uniform load in the network (and hence the delay per link).
Thus, the performance of such utility-theoretic heuristics critically
depends on the existence of an adequately precise estimator of
delay (or some other performance measure) that would result from a particular
routing choice. A wide range of such estimators are possible,
depending (among other things) on what can be assumed regarding the
network topology, load, and network dynamics. It might be useful to analyze
a range of such estimators and the resulting heuristics based on different
sets of such assumptions - especially since
a useful strategy for designing good heuristics
for complex problems is based on solution of simplified or relaxed versions of the original problem .  Other interesting
research directions include: investigation of methods for adaptation
that enable the tuning of heuristics - perhaps parameterized in some
manner - using appropriate measurements of network performance as feedback
in real-time - perhaps drawing upon the rich literature on adaptive
control ; and techniques for learning
that construct new heuristics or modify existing heuristics)
as a function of measured network behavior or as a function of
information gathered through directed experiments initiated by the
network during otherwise idle periods.
The task of making decisions based on incomplete and
uncertain information is by no means limited to communication
networks. Load distribution and task scheduling in distributed computing
environemnts are other examples of decision mechanisms that are attempting
to maximize certain performance criteria without having access to
global information upon which there decisions can be based.
The tradeoff between the quality of decisions and the
resource overhead associated with knowledge acquisition and
maintenance is critically important to understand in any complex
dynamic environment. Thus, techniques similar to the ones used in
this paper might find use in analyzing spatio-temporally distributed
dynamic computing and communication environments.
19
Bertsekas, D.  and Gallager, R.  Data Networks.  2nd
ed.  Prentice-Hall, Englewood Cliffs, NJ. (1992).
Comer, D.  Internetworking with TCP/IP; Principles,
Protocols, and Architectures.  Prentice-Hall, Englewood Cliffs, NJ. (1988).
Fishburn P.C. Utility Theory for Decision Making
John Wiley  Sons, Inc., New York. (1970).
French, S. Decision Theory:an introduction
to the mathematics of rationality. Halsted Press, New York. (1986).
Honavar, V. Toward Learning Systems That Integrate Multiple
Strategies and Representations. In: Honavar, V. and Uhr, L. (ed.) Artificial Intelligence and Neural Networks: Steps Toward Principled Integration, Academic Press, Boston (1994), pp. 615-644.
Langley, P. Elements of Machine Learning, Morgan Kaufmann, Palo Alto, CA. (1995).
Mikler, A.R., Honavar, V.G., and Wong, J.S.K.
Simulating a Traveller:  A Heuristic Approach to Routing in Large
Communication Networks.  Proceedings of the European Simulation
Symposium, Dresden, Germany (1992), pp. 297-301.
Mikler, A.R., Honavar, V.G., and Wong, J.S.K.
Quo Vadis - A Framework for Adaptive Routing in Very Large Communication Networks. In: Alspector, J., Goodman, R., and Brown, T.X. (ed.) Proceedings of the International Workshop on Applications of Neural Networks to Telecommunications, Lawrence Erlbaum, Hillsdale, New Jersey (1993), pp. 196-202.
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
Quo Vadis - A Framework for Intelligent Routing in Large Communication Networks.
Tech. Rep. TR94-24, Department of Computer Science,
Iowa State University (1994). To appear in:
The Journal of Systems and Software.
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
Quo Vadis - Adaptive Heuristics for Routing in Large Communication Networks.
Proc  of the 3rd International Conference on Telecommunication Systems,
Modeling and Analysis, Washington, D.C.
(1995), pp. 66-75.
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
Quo Vadis - Adaptive Heuristics for Routing in Large Communication Networks.
Tech. Rep. ISU CS-TR 95-10, Department of Computer Science, Iowa State
University (1995).
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
An Object-Oriented Approach to Modeling and Simulation of Routing in Large
Communication Networks,
Tech. Rep. ISU CS-TR 95-9, Department of Computer Science, Iowa State
University (1995).
Narendra, K.S., and Annaswamy, A.M. Stable Adaptive Systems. Prentice-Hall, Englewood Cliffs, NJ. (1992).
Pearl, J.  Heuristics:  Intelligent Search
Srategies for Computer Problem Solving.  Addison-Wesley, Reading,
MA.  1984.
Perlman, R.  Interconnections, Bridges and
Routers.  Addison-Wesley, Reading, MA. 1992.
Tanenbaum, A.S.  Computer Networks.
Prentice-Hall, Englewood Cliffs, NJ. 1988.
Von Neumann, J. and Morgenstern O. Theory of Games
and Economic Behavior. John Wiley  Sons, Inc., New York. 1964.
Wong, J.S.K.  and Mikler, A.R.  Routing Algorithms for
High-Speed Communications Networks. In: Conard, J.W. (ed.), Broadband Communications
Systems. Auerbach Publications (1993), pp. 97-105.

Subjects:All uncategorized technical reports
ID code:00000106
Deposited by:Staff Account on 28 September 1995



Contact site administrator at: ssg@cs.iastate.edu