

Mikler, Armin, Honavar, Vasant and Wong, Johnny (1995) UtilityTheoretic Heuristics for Intelligent Adaptive Routing in Large Communcation Networks. Technical Report TR9514, Department of Computer Science, Iowa State University.
Abstract
UtilityTheoretic 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
miklerhonavarwong@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 realtime instance
of a multicriterion quasioptimization 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 nearoptimal (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
utilitytheoretic 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 timeframe of interest). We derive bounds on the cost of a suboptimal path (relative to the cost of an optimal path) as well as the probability that a resulting route between a randomly chosen sourcedestination pair is suboptimal. We then present a modified heuristic function that
is guaranteed to eliminate suboptimal 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 postdoctoral 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 IRI9409580.
The authors wish to thank Yong Zhao, Karthik Balakrishnan, Rajesh Parekh, and ChunHsien Chen (all doctoral students in Computer Science at Iowa State University), and Mary Oman (a postdoctoral 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,
utilitytheoretic 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 utilitytheoretic 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 multicriterion
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 uptodate 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 resourceconstrained multicriterion 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 utilitytheoretic
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.
UtilityTheoretic Heuristics for Routing
Routing messages in large communication networks so as to optimize
some desired set of performance criteria presents an instance of
resourcebounded, multicriteria, realtime, quasioptimization problem.
Our proposed solution to this problem involves the use of utilitytheoretic
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 utilitytheoretic 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 nonnegative 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 suboptimal routes. A primary
purpose of the preceding analysis as well as the analysis that follows is
to develop a class of utilitytheoretic heuristics that would be useful
in routing messages along nearoptimal 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 realvalued 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
preferenceorders 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 suboptimal 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 nonzero. 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 socalled
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 suboptimal 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 SubOptimal Routing Using
Let the probabilities of a suboptimal 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 suboptimal routes in an Nnode
grid network
is given by:
The probability is computed as:
where and are the probabilities
of suboptimal 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 sourcehotspotdestination 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 suboptimal routing decisions in the scenario
described in Case 3
in terms of
the number of such sourcehotspotdestination configurations
that are possible
in an network.
The resulting probability of suboptimal 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 suboptimal 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 preferenceorders 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 .
Suboptimal 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, sourcehotspotdestination configurations corresponding to scenarios described in Case 2 and Case 3 can result in
suboptimal 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
sourcehotspot 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 SubOptimal 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 sourcehotspot 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 suboptimal route in a sourcehotspotdestination 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 suboptimal route in an
otherwise uniform cost network with a single hotspot due to routing decisions
based on is bounded by .
Eliminating SubOptimal Routing Decisions in Case 2 Using a Utility Function
As shown by the preceding analysis, can result in a suboptimal
routing decision in a sourcehotspotdestination configuration corresponding
to the scenario in Case 2. In particular,
any routing decision in a configuration corresponding to Case 2 will
result in a suboptimal 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
sourcedestination 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 sourcehotspotdestination 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, selfmanaging
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 uptodate 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 uptodate.
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 utilitytheoretic heuristic
decision functions for guiding messages along a nearminimumdelay 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
utilitytheoretic 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
suboptimality of a path. We have established an upper bound
on the probability that a path between a
randomly chosen sourcedestination pair is suboptimal by considering
configurations of uniformly loaded grid networks with single hotspots
under the assumption that each sourcedestination 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 utilitytheoretic 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 utilitytheoretic 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
utilitytheoretic heuristics be designed for different sets of performance
criteria for such complex and dynamic
networks so that they become essentially autonomous and selfmanaging?
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 loadbalancing 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 utilitytheoretic
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 nonuniform (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 utilitytheoretic 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 realtime  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 spatiotemporally distributed
dynamic computing and communication environments.
19
Bertsekas, D. and Gallager, R. Data Networks. 2nd
ed. PrenticeHall, Englewood Cliffs, NJ. (1992).
Comer, D. Internetworking with TCP/IP; Principles,
Protocols, and Architectures. PrenticeHall, 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. 615644.
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. 297301.
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. 196202.
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
Quo Vadis  A Framework for Intelligent Routing in Large Communication Networks.
Tech. Rep. TR9424, 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. 6675.
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
Quo Vadis  Adaptive Heuristics for Routing in Large Communication Networks.
Tech. Rep. ISU CSTR 9510, Department of Computer Science, Iowa State
University (1995).
Mikler, A.R., Wong, J.S.K., and Honavar, V.G.
An ObjectOriented Approach to Modeling and Simulation of Routing in Large
Communication Networks,
Tech. Rep. ISU CSTR 959, Department of Computer Science, Iowa State
University (1995).
Narendra, K.S., and Annaswamy, A.M. Stable Adaptive Systems. PrenticeHall, Englewood Cliffs, NJ. (1992).
Pearl, J. Heuristics: Intelligent Search
Srategies for Computer Problem Solving. AddisonWesley, Reading,
MA. 1984.
Perlman, R. Interconnections, Bridges and
Routers. AddisonWesley, Reading, MA. 1992.
Tanenbaum, A.S. Computer Networks.
PrenticeHall, 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
HighSpeed Communications Networks. In: Conard, J.W. (ed.), Broadband Communications
Systems. Auerbach Publications (1993), pp. 97105.
Contact site administrator at: ssg@cs.iastate.edu
