Stochastic control of path optimization for inter-switch handoffs in wireless ATM networks.
One of the major design issues in wireless ATM networks is the support  of Inter-switch handoffs. An inter-switch handoff occurs when a mobile terminal moves to a new base station connecting a different switch. Apart from resource allocation at the new base station, inter-switch handoff also requires connection rerouting. With the aim of minimizing the handoff delay while using the network resources efficiently, the two-phase handoff protocol uses path extension for each inter-switch handoff, followed by path optimization if necessary. The objective of this paper is to determine when and how often path optimization should be performed. The problem is formulated as a semi-Markov decision process. Link cost and signaling cost functions are introduced to capture the tradeoff between the network resources utilized by a connection and the signaling and processing load incurred on the network. The time between inter-switch handoffs follows a general distribution. A stationary optimal policy is obtained when the call termination time is exponentially distributed. Numerical results show significant improvement over four other heuristics.
Figure

1 (b), the switch chosen to perform this function is usually referred to as the crossover switch
[5]. Depending on the performance criteria of the crossover switch discovery algorithms [5]-[6], the end-
to-end path after rerouting may not be optimal. In this paper, we define an optimal path as the best path
among a set of feasible paths that can satisfy the prescribed end-to-end QoS constraints.
A two-phase handoff protocol was proposed in [8] that combines the advantages of path extension
and path rerouting schemes. The two-phase handoff protocol consists of two stages: path extension and
possible path optimization. Referring to Figure 2, path extension is performed for each inter-switch
handoff, and path optimization is performed whenever it is necessary. During path optimization, the
network determines the optimal path between the source and the destination (i.e., the path between the
remote terminal and the current target switch in Figure 2) and transfers the user information from the old
path to the new path. The major steps in the path optimization process generally involve [11]: (1)
determining the location of the crossover switch; (2) setting up a new branch connection; (3) transferring
the user information from the old branch connection to the new one; and (4) terminating the old branch
connection.
Since the mobile terminal is still communicating over the extended path via the current base station
while path optimization takes place, this gives enough time for the network to perform the necessary
functions while minimizing any service disruptions. Notice that the path optimization process described
above is not restricted to the two-phase handoff protocol. It can also be applied to other connection
rerouting protocols where the end-to-end path after rerouting is sub-optimal. In addition, when the mobile
terminal moves to another switch during the execution of path optimization, path extension can still be
used to extend the connection to the target switch. To ensure a seamless path optimization, three
important issues need to be addressed:
1. How to determine the location of the crossover switch?
2. How can the service disruptions be minimized during path optimization?
3. When and how often should path optimization be performed?
For the first issue, a crossover switch determination algorithm based on PNNI (Private Network-to-
Network Interface) standard was proposed in [11]. Five different crossover switch algorithms for wireless
ATM local area networks are proposed in [5]. For the second issue, cell loss and cell mis-sequencing can
be prevented by using appropriate signaling and buffering at the anchor and crossover switches during
path optimization [11].
In this paper, we focus on the third issue. Our work is motivated by the fact that path optimization
does not have to be performed after each inter-switch handoff. Although path optimization can increase
the network utilization by rerouting the connection to a more efficient route, transient QoS degradations
such as cell loss and an increase in cell delay variation may occur. In addition, if there are a large number
of mobile users with high movement patterns, performing path optimization after each path extension
will increase the processing load of certain switches and the signaling load of the network. The decision
to perform path optimization should be based on several factors including: (1) the amount of network
resources (e.g., bandwidth) utilized by the connection; (2) QoS requirements; (3) the remaining time of
the connection; and (4) the signaling load of the network.
To this end, we propose a stochastic model to determine the optimal time to perform path
optimization for the two-phase handoff protocol. The path optimization problem is formulated as a semi-Markov
decision process. Link cost and signaling cost functions are introduced to capture the trade-off
between the network resources utilized by a connection and the signaling and processing load incurred on
the network. The objective is to determine the optimal policy which minimizes the expected total cost per
call. The major contribution of our work lies in the formulation of a general model that is applicable to a
wide range of conditions. Distinct features of our model include: (1) different link cost functions can be
assigned to different service classes (e.g., CBR, VBR, ABR) with different bandwidth requirements; (2)
different signaling cost functions can be used based on the complexity of the path optimization
procedures and the signaling load of the network; and (3) the time between inter-switch handoffs can
follow an arbitrary general distribution.
The rest of the paper is organized as follows. The model formulation of the path optimization problem
is described in Section 2. In Section 3, we describe the optimality equations, the value iteration algorithm,
and the structure of the optimal policy. The implementation issues are described in Section 4. Extension
of the model to include mobile-to-mobile connections and other QoS constraints are described in Section
5. In Section 6, we present numerical results and compare the optimal policy with four other heuristics.
Conclusions are given in Section 7 where further work is also discussed. The proofs of the propositions
stated in this paper are shown in the appendix. For general background on Markov decision processes,
please refer to [14], [15].
2. Model Formulation
Each mobile connection may experience a number of inter-switch handoffs during its connection lifetime.
During each inter-switch handoff, path extension can be used to extend the connection from the current
anchor switch to the target switch. Although path extension is simple to implement, the connection
utilizes more network resources than necessary. Occasional path optimization is required to reroute the
connection to an optimal path. Path optimization is a complex process. It increases the processing and
signaling load of the network. Thus, there is a trade-off between the network resources utilized by the
connection and the processing and signaling load incurred on the network. We formulate the above
problem as a semi-Markov decision process. After each path extension, the network must decide whether
to perform subsequent path optimization. The decision is based on the current number of links of the path
and the locations of the anchor and target switches. The model is described below.
2.1 Semi-Markov Decision Process Model
When an inter-switch handoff occurs, a path extension is performed. After that, a decision must be made
whether to perform subsequent path optimization. Those time instants are called decision epochs.
Referring to Figure 3, the sequence s ,s , represents the time of successive decision epochs. Since
inter-switch handoff only occurs during the call lifetime, the time interval requiring mobility monitoring
is between a call arrival and its termination. The term represents the arrival time of a new call andthe random variable T denotes the call termination time. The random variable f(T )denotes the total
number of inter-switch handoffs that occur before the termination time T .
At each decision epoch, the network must decide whether to perform subsequent path optimization.
PO}denote the action set, where PO corresponds to perform path optimization after
path extension, and NPO corresponds to perform path extension only. We use Y to denote the action
chosen at decision epoch n .
The action chosen is based on the current state of the connection. The state space is denoted by S . For
each state s S, the state information includes the locations of the target and anchor switches, and the
number of links of the current path. The random variable X denotes the state at decision epoch n .
Two cost functions are introduced to account for the network resources utilized and the signaling load
incurred due to an inter-switch handoff. The link cost function reflects the amount of network resources
used during the connection lifetime, while the signaling cost function captures the processing and
signaling load incurred on the network due to path extension and path optimization. The signaling costs
are incurred only at the decision epochs, while the link cost is accrued continuously over the call lifetime.
The function f(s)denotes the link cost rate in state s. If the state is equal to sduring the time
interval (s , s ), then the link cost incurred during that period is equal to (s- s )f(s). The
function b(s, a)denotes the signaling cost incurred when the decision maker chooses action ain state s.
Thus, b(s, NPO)represents the signaling cost of performing path extension, and b(s, PO)represents the
signaling cost of performing path extension and subsequent path optimization. All cost functions are
assumed to be finite and nondecreasing with respect to the number of links of the current path.
A decision rule prescribes a procedure for action selection in each state at a specified decision epoch.
Deterministic Markovian decision rules are functions d : Sfi A, that specify the action choice when the
system occupies state sat decision epoch t< T. That is, for each sS, d(s) A . This decision rule is
said to be Markovian (memoryless) because it depends on previous system states and actions only
through the current state of the system, and deterministic because it chooses an action with certainty. A
policy p specifies the decision rules to be used at all decision epochs. That is, a policy is a sequence of
decision rules, p= (d,d ,). The set of all policies is denoted by P .
Let v (s)denote the expected total cost per call given policy pis used with initial state s . Thus,
denotes the expectation with respect to policy p and initial state s . In (1), the first summation
s
in the right hand side corresponds to the lump sum portion of the signaling cost, each term in the second
summation corresponds to the continuous portion of the link cost incurred at rate f(X)between decision
epochs nand n+ 1 , and the last term corresponds to the link cost incurred at rate f(X )between
decision epoch f(T )and termination time T. In this paper, we assume the call termination time is
exponentially distributed with rate m . In that case, (1) can be written as:
where
c(s, a)= b(s, a)+ Es --m-(1 - e )f(s). (3)
For a proof of this fact, see Proposition 1 in the appendix. The expression in (2) is the expected total cost
of an infinite-horizon semi-Markov decision process with discount rate m . The function c(s, a)in (3) is
the expected total cost between two decision epochs, given the system occupies state s and the decision
maker chooses action ain state s. This cost function is further discussed in Section 2.3.
Since the optimization problem that we consider is to minimize the expected total cost, we define that
a policy p* is optimal in P if vp*(s)vp(s)for all p P.
Let G(tX, Y )denote the cumulative distribution function of the time between decision epochs n
current state X and action Y is chosen. The time between decision epochs corresponds
to the time between inter-switch handoffs. In this formulation, the time between inter-switch handoffs
follows a general distribution and can depend on the location of a particular anchor switch that the mobile
terminal is connected to. We use G(dtX, Y )to represent the time-differential. That is,
A policy is said to be stationary if d = d for all t . A stationary policy has the form p= (d,d,);
for convenience we denote it by d. For a stationary policy d, (2) can be written as:
d  -mt d
s'  S 0
where P[s' s, d(s)]denotes the transition probability that the next state is s' , given the current state is s
and action d(s)is chosen. For a proof of this fact, see Proposition 1 in the appendix. Our objective is to
determine an optimal stationary deterministic policy d* which minimizes (4).
To simplify the analysis, two assumptions are made. First, we assume the distribution of the time
between inter-switch handoffs is independent of the state and action chosen, i.e., G(tX, Y )= G(t).
Second, we assume the mobile terminal is communicating with a remote terminal which is stationary.
That is, we consider a mobile-to-fixed connection. The model formulation for mobile-to-mobile
connection is described in Section 5.1.
2.2 State Transition Probability Function
A state change occurs when there is an inter-switch handoff. The state space S is three dimensional. For
each state (i,j,k) S , i denotes the location of the target switch; j denotes the location of the current
anchor switch; and k denotes the number of links of the current path. Thus,
where Ndenotes the total number of nodes in the network and Lrepresents the maximum number of
links allowed in a path. The number of links of any path is always finite. We assume the number of links
increased by a path extension is bounded by Mwhich is much smaller than L(i.e., M L).
Since the end-to-end delay is proportional to the number of links of the path, a sub-optimal path with
a large number of links not only increases the delay but also increases the call dropping probability and
the congestion level of the network. We impose the condition that whenever the number of links in a
connection is greater than or equal to L- Mand there is an inter-switch handoff, path extension is
performed followed by path optimization with certainty. For convenience, we let K= L- M. Later we
show that path optimization is always performed when the number of links exceeds a certain threshold,
and this threshold is much smaller than K .
Given the current state s= (i,j,k), the available action set is:
{NPO, PO},1 k< K
{PO}, KkL.
Thus, after each path extension, path optimization may be performed if the number of links is less than
K , while path optimization is performed with certainty whenever the number of links is greater than or
equal to K .
Two probability distribution functions are introduced to govern the state changes. Let
p(mi, j)denote the probability that the number of links of the optimal path is m , given that the
locations of the two end-points are i and j , respectively.
q(li)denote the probability that the location of the target switch in the next decision epoch is l , given
that the location of the target switch at the current decision epoch is i .
In ATM networks, source routing is being used for all connection setup requests. That is, the source
switch selects a path based on topology, loading, and reachability information in its database. As
networks grow in size and complexity, full knowledge of network parameters is typically unavailable.
Each single entity in the network cannot be expected to have detailed and instantaneous access to all
nodes and links. Routing must rely on partial or approximate information, and still meet the QoS
demands [16][17]. The ATM Forum PNNI standard [18] introduces a hierarchical process that aggregates
information as the network gets more and more remote. However, the aggregation process inherently
decreases the accuracy of the information and introduces uncertainty. Thus, in large networks it is more
appropriate to model the number of links of a path between two endpoints in a probabilistic manner.
On the other hand, for small networks with periodic routing information update, the number of links
of a path between the two endpoints can be modeled in a deterministic manner. Let (i, j)denote the
number of links of the optimal path between the two endpoints i and j . The functions p(mi, j)and
(i, j)are related by
Let D denote the location of the destination (i.e., the remote terminal), which is assumed to be fixed.
The transition probability that the next state is s' = (i',j',k')given that the current state is s= (i,j,k)
and action a is chosen, is given by:
0, otherwise.
Equation (7) states that if action NPO is chosen, the number of links is increased by m with probability
p(mi, j)after path extension. On the other hand, if action PO is chosen, the number of links is equal to
nwith probability p(ni, D)after path optimization. In both cases, the location of the target switch at the
next decision epoch is equal to i' with probability q(i' i).
2.3 Cost Functions
For each path extension event, the network incurs a fixed signaling cost C > 0 and a variable signaling
cost h (m)where m represents the number of links increased during path extension. The terms C and
h (m)capture the cost of setting up the extended path between the anchor and target switches.
For each path optimization performed, the network incurs a fixed signaling cost C > 0 and a
PO
variable signaling cost h (l)where l represents the number of links reduced during path optimization.
PO
These two terms capture the cost of (1) locating the crossover switch; (2) setting up the new branch
connection; (3) terminating the old branch connection; and (4) updating the connection server about the
status of the existing route.
We assume the link cost rate only depends on the number of links of the current path. That is,
f(s)= f(k)for all s S. Recall from (2) that c(i,j,k,a)denotes the expected total cost between two
decision epochs, given the system occupies state (i,j,k)and action a is chosen. Since the first inter-switch
handoff occurs at time s , the locations of the anchor and target switches are the same at the callsetup time s . Thus, during the time interval (s , s ] , we have i= jand the cost function
c(j,j,k,NPO)= I f(k) (8) t -mt
G(dt). The function I1 f(k)is the expected discounted link cost between two
decision epochs, given that the current number of links is k .
For other decision epochs not equal to s , the locations of the anchor and target switches are alwaysdifferent (i.e., ijif s s). In that case, if action NPO is chosen, then the cost functionM
The function CPE j)is the expected signaling cost for path extension, given that the
locations of the anchor and target switches are i and j , respectively.
For path optimization, we assume the number of links of the optimal path is always less than or equal
to the number of links of the current path, and less than K . For decision epoch snot equal to s, ifaction PO is chosen, then the cost function
where x y= min (x, y). The expression CPO D)is the expected signaling cost for
path optimization, given that the current number of links is k , and the locations of the source and
destination are iand D, respectively.
3. Optimality Equations
In this section, we introduce the optimality equations (sometimes referred to as the Bellman equations or
functional equations) and investigate their properties. We show that solutions of these equations
correspond to optimal value functions and that they also provide a basis for determining optimal policies.
Let v(s)denote the minimum expected total cost per call given state s . That is,
The optimality equations are given by
-mt
a A s'  S 0
-mt
Equation (12) can be expanded as follows:For i=jand 1 k< K,
For
v(i,j,k)= min -c(i,j,k,NPO)+   I2v(l,i,k+ m)p(mi, j)q(li),
c(i,j,k,PO)+    I2v(l,i,n)p(ni, D)p(mi, j)q(li).
For
v(i,j,k)= c(i,j,k,PO)+   I2v(l,i,n)p(ni, D)q(li). (15)
At call setup time s , the locations of the anchor and target switches are the same. Thus in (13), no pathextension or path optimization is performed. For other decision epochs not equal to s , the locations ofthe anchor and target switches are different. If the number of links of the path is less than K , then after
each path extension, the network will decide whether to perform subsequent path optimization. This fact
is stated in (14). Since path optimization is always performed if the number of links is greater than or
equal to K, in (15), the action POis chosen when there is an inter-switch handoff.
If the signaling cost function for path optimization is zero (i.e., C =h (l)=0 ), the problem of
PO PO
finding an optimal policy is trivial. It is optimal to perform path optimization after each inter-switch
handoff. This is because the link cost function is nondecreasing with respect to the number of links of the
current path. After each path optimization, there is a reduction in the number of links. However, if the
signaling cost function for path optimization is nonzero, it is not obvious as to what constitutes the
optimal policy. Note that if m > 0 , the state space is finite, and the cost functions are bounded, then the
solutions for equations (13)-(15) exist. By solving these equations, a stationary deterministic optimal
policy can be obtained.
3.1 Value Iteration Algorithm
There are a number of iteration algorithms available to solve the above optimality equations. Examples
include the value iteration, policy iteration, and linear programming algorithms [14]. Value iteration is the
most widely used and best understood algorithm for solving discounted Markov decision problems. Value
iteration is also called by other names including successive approximations, over-relaxation, and pre-
Jacobi iteration. The following value iteration algorithm finds a stationary deterministic optimal policy
and the corresponding expected total cost.
Algorithm1. Set v (s)= 0 for each state sS. Specify e> 0 and set
2. For each s S, compute v (s)by:
a A s'  S 0
3. If v - v < e , go to step 4. Otherwise increment n by 1 and return to step 2.
4. For each s S, the stationary optimal policy
-mt n
a A s'  S 0
and stop.
There are a number of definitions for the function norm . In this paper, the function norm is
defined as: Convergence of the value iteration algorithm is ensured since the
operation in step 2 corresponds to a contraction mapping. Thus, the function v (s)converges in norm to
v(s). Note that the convergence rate of the value iteration algorithm is linear.
In small networks, if each node maintains perfect information of all nodes and links, then the function
v[i,i,(i, D)]is the minimum expected total cost per call given source iand destination D. On the other
hand, in large networks, the number of links of a path determined by the source is modeled in a
probabilistic manner. In that case, the expression
v(i,i,k)p(ki, D) (16)
is the minimum expected total cost per call given source iand destination D, averaged over the number
of links of the optimal path.
3.2 Structure of the Optimal Policy
We now provide a condition under which the optimal policy has a control limit (or threshold) structure.
The control limit structure states that path optimization is performed with certainty whenever the number
of links of the current path exceeds a certain threshold. For convenience, we let Dg(k)= g(k
for some function g .
Proposition: Given state (i,j,k)S , there exists an optimal policy d* that has a control limit structure:
PO, k* kL
when I1Df(k+ m)-DhPO(k+ m- n)p(ni, D) 0for all msuch that p(mi,
The proof of the above proposition is shown in Proposition 2 in the appendix. The value k* is the
control limit or threshold. Consider the special case where the cost functions are linear. That is,
f(k)= C  k and h (l)= w  l where C and w are positive constant. In this case, if
link PO PO link PO
I C -w  0, then path optimization is always performed when the number of links is greater than or
link PO
equal to k* . An optimal policy with threshold structure facilitates its implementation. For each mobile
connection, the network only has to maintain the information of the minimum number of links to initiate
path optimization for all anchor and target switch pairs. The decision to perform path optimization can be
made via a table lookup.
Note that the optimal policy still maintains a threshold structure for other cost functions as long as
they are convex and nondecreasing. Interested readers can refer to [19] for a proof of this fact. For those
cost functions, the value iteration algorithm described in Section 3.1 can still be used to determine the
minimum expected total cost and the optimal policy.
4. Implementation Aspects
Having identified the different parameters involved in the model, we are now in a position to explain the
steps that need to be taken in order to implement the model. For each mobile connection, during its
connection setup phase, the network controller assigns the cost functions based on the service class and
the signaling load of the network. Different service classes (e.g., CBR, VBR, ABR) with different
bandwidth requirements are assigned different link cost functions to reflect the network resources
consumed. The assigned signaling cost function reflects the complexity of the path optimization
procedures and the current signaling load of the network. By keeping the mobility profile of each user
(i.e., the movement history and call history), the average time between inter-switch handoff as well as the
average duration of the connection can be estimated [20][21].
Given the input parameters (i.e., cost functions and various distributions), the value iteration
algorithm can be used to determine the optimal policy. The optimal policy is then stored in a tabular
format. Each entry of the table specifies the minimum number of links to initiate path optimization for a
specific pair of anchor and target switches. Whenever there is an inter-switch handoff, the network
performs a table lookup at the corresponding anchor and target switch entry. Path optimization is
performed if the number of links is greater than the threshold.
The optimal policy table needs to be updated when there are changes in network topology or
signaling load of the network. The update can be performed off-line. That is, whenever spare processing
capacity is available at the network controller.
5. Model Extensions
In the previous sections, we consider a connection between a mobile terminal and a fixed endpoint. In this
section we extend the above model to a connection between two mobile terminals and take into
consideration other QoS constraints.
5.1 Extension to Mobile-to-Mobile Connection
The problem formulation for mobile-to-mobile connection is similar to that of mobile-to-fixed
connection. Consider mobile terminals 1 and 2 communicating with each other via a wireless ATM
network. Each mobile terminal has its own movement pattern. A path extension is performed when there
is an inter-switch handoff, (initiated from either side), followed by a path optimization if necessary. In
this formulation, the state space needs to include the locations of the two endpoints, as well as the
information of which mobile terminal initiates the path extension. For each state (i,j,j ,k,J) S , i
denotes the location of the target switch; j and j denote the locations of the anchor switches connected
to mobile terminals 1 and 2, respectively; k denotes the number of links of the current path; and J
denotes the identifier of the mobile terminal which initiates the inter-switch handoff.
Since the movement pattern of each mobile user is different, the time between inter-switch handoffs
for each mobile user is also different. Suppose the time between inter-switch handoffs for mobile terminal
r, (r{1, 2}), is exponentially distributed with rate l, then the time between decision epochs is also
r
exponentially distributed with rate l + l .
Since the state space has changed, the cost functions and the state transition probability function have
to be modified accordingly. As the modification is conceptually similar to the functions derived in Section
2, the details are omitted. The optimality equations are
a A 1 2 s'  S
The value iteration algorithm described in Section 3.1 can be used to evaluate the expected total cost and
the optimal policy. The conditions for the optimal policy with a threshold structure can also be derived.
5.2 Extension to QoS Constraints
In Sections 2 and 3, path optimization is triggered based on the number of links of the current path. In
general, a mobile connection can have multiple QoS constraints such as bandwidth, delay, delay jitter,
etc. Suppose the connection has to maintain a delay constraint. In this case path optimization is
performed with certainty if the end-to-end delay after path extension exceeds the delay constraint, while
path optimization may be performed if the delay after path extension is still below the constraint.
To incorporate the delay constraint into the model, the state space needs to be extended to include the
end-to-end delay of the current path. We assume the end-to-end delay of a path is the sum of the delay on
each link of the path. The delay information on each link can be obtained from the network by
measurement. Let zdenote the end-to-end delay of the current path and Ybe the delay constraint. Let
F(i, j)denote the delay of the path between the two endpoints i and j . The optimality equations
described in Section 3 then include the constraint z+ F(i, denote the locations
of target and anchor switches respectively. Note that the value iteration algorithm described in Section 3.1
cannot be used to solve the optimality equations with constraints. However, the optimality equations can
be transformed into primal or dual linear programs, which can then be solved by the simplex algorithm.
Due to the space limitations, please refer to [14] for the details of the transformation.
In summary, multiple QoS constraints can be incorporated into the model by extending the state space
and including the constraint equations into the set of optimality equations. The expected total cost and the
optimal policy can be obtained by transforming the model into a linear programming model.
6. Numerical Results and Discussions
In this section, we compare the performance of the optimal policy with four heuristics. For the first
heuristic, path optimization is performed after each path extension. We denote this policy as always
PO
perform PO or d . For the second heuristic, no path optimization is performed during the connection
NPO
lifetime. We denote this policy as never perform PO or d . For the third heuristic, periodic path
optimization is considered. The use of periodic path optimization has been proposed within the ATM
Forum [22]. For periodic path optimization, after each fixed time period, the network determines if the
connection requires path optimization. Path optimization is performed if an inter-switch handoff has
occurred during the time interval. We assume this fixed time interval is equal to the average time between
inter-switch handoffs. For the last heuristic, we consider the Bernoulli path optimization scheme which
we proposed and analyzed in [23]. For the Bernoulli scheme, path optimization is performed with
probability p after each extension.
opt
The performance metrics are the expected total cost per call and the expected number of path
optimizations per call. The expected total cost per call is defined in Section 2. The expected number of
path optimizations per call given policy p with initial state s is:
where 1[.]denotes the indicator function (i.e.,
6.1 Simulation Model
In the simulation model, a wireless ATM network is modeled as a non-hierarchical random graph.
Random graphs have been used to model ATM networks [24]. Different variations of random graph
models have also been proposed to model the topology of the Internet [25][26]. The generation of a non-hierarchical
random graph consists of the following steps [25]:
1. N nodes are randomly distributed over a rectangular coordinate grid. Each node is placed at a location
with integer coordinates. A minimum distance is specified so that a node is rejected if it is too close to
another node. The Euclidean metric is used to calculate the distance a(i, j)between each pair of
nodes (i, j).
2. A fully connected graph is constructed with the link weight equal to the Euclidean distance.
3. Based on the fully connected graph, a minimum weight spanning tree is constructed.
4. To achieve a specified average node degree1 of the graph, edges are added one at a time with increasing
distance.
If node i and j are connected, then the link weight, denoted as w , is assumed to be equal to:
where b is a uniformly distributed random variable in the range 0 bb . In (19), the first term can be
interpreted as the propagation delay of the link, and the second term approximately models the queueing
delay of the link.
A 20-node random graph generated from the above model is shown in Figure 4. The size of the
rectangular coordinate grid is 100 . 100 . The minimum distance between any two nodes is 15. The
average node degree of the graph is 3. The value of b is 100. Each node represents an ATM switch and
each edge represents a physical link connecting two switches. Since we are only concerned about inter-switch
handoff, base stations are not included in the model.
Based on the above network model, we obtain the adjacency matrix of the network as well as the
number of links of the shortest path between any two nodes. We assume the number of links of the
shortest path estimated by the source is deterministic. The call duration is assumed to be exponential. The
time between inter-switch handoffs follows a Gamma distribution. When there is an inter-switch handoff,
we assume each of the neighboring switches has the same probability to be the target switch (i.e., uniform
distribution).
For each source and destination pair, the value iteration algorithm described in Section 3.1 is used to
determine the minimum expected total cost and the optimal policy. From the optimal policy, the value
iteration algorithm is used again to calculate the expected number of path optimizations by solving (18).
The minimum expected total cost and the expected number of path optimizations are then averaged over
all possible source and destination pairs. We repeat this for 100 random graphs and determine the
averages.
PO NPO
For the two heuristic policies d and d , the expected total cost and the expected number of path
optimizations for each source and destination pair are also determined by the value iteration algorithm.
These values are then averaged over all possible source and destination pairs. Again, we repeat this for
100 random graphs and determine the averages.
For the periodic and Bernoulli path optimization policies, simulation must be used. Given the network
topology, a call is generated with two nodes chosen as the source and destination. Dijskstra's algorithm is
used to compute the shortest path between these two nodes. The destination node is assumed to be
1 The average node degree is defined as the average number of links connected to a node.
stationary. The source node becomes the anchor switch of the mobile connection. During each inter-switch
handoff, the target switch is restricted to be one of the neighboring switches of the current anchor
switch. Path extension is used to extend the connection from the anchor switch to the target switch. Path
optimization is performed periodically for the periodic scheme. For the Bernoulli scheme, path
optimization is performed with probability p after each extension. For each source and destination
opt
simulation runs are performed. The average total cost and the average number of path
optimizations per call are determined. We repeat this for 100 random graphs and determine the averages.
All the cost functions are assumed to be linear. The link cost function f(k)= C  k where
link
. The term C captures the bandwidth used by the connection. Different C can be assigned
link link link
for different traffic classes. The variable cost function for path extension h (m)= w  m where
denotes the number of links increased during path extension. The variable cost function
for path optimization h (l)= w  l where w > 0 and l denotes the number of links reduced during
PO PO PO
path optimization.
6.2 Results

Figure

5 shows the expected total cost versus the link cost rate C . The optimal policy gives the lowest
link
expected total cost compared to the other four heuristics. When the link cost rate is small, there is no
incentive to perform path optimization. The operating point, p , for the Bernoulli policy is close to
opt
NPO
zero. The optimal policy is to perform path extension only. Thus, results of the Bernoulli, d , and
optimal policies are the same. When the link cost rate increases, the optimal policy for some source and
NPO
destination pairs is to perform path optimization. Results of the optimal, Bernoulli, and d policies
PO
diverge, while the results of the Bernoulli and d policies begin to converge.

Figure

6 shows the expected number of path optimizations versus the link cost rate C . Since no
link
NPO
path optimization is performed for the d policy, the expected number of path optimizations is always
equal to zero. Note that since both the call termination rate and the inter-switch handoff rate are constant,
in this case the expected number of inter-switch handoffs is also a constant. Thus, results for the periodic
PO
and d policies are independent of the link cost rate. For the Bernoulli and optimal policies, when the
link cost rate is small, there is no incentive to perform path optimization. The expected number of path
optimizations is small. As the link cost rate increases, some source and destination pairs perform path
optimization after inter-switch handoff. Thus, there is an increase in the number of path optimizations
performed.

Figure

7 shows the expected total cost versus the inter-switch handoff rate l . The expected total cost
increases as the inter-switch handoff rate increases. When l is small (i.e., the average time between inter-switch
ghandoffs is larger than the average call duration), an inter-switch handoff is unlikely to occur
during the connection lifetime. Thus, the results between the five policies are close. As the inter-switch
PO
handoff rate increases, these five curves begin to diverge. The d policy gives the highest expected total
NPO NPO
cost, which is followed by the periodic, d , and Bernoulli policies. Results of the d and Bernoulli
policies are very close. Although we can conclude that the expected total cost increases in l and the
optimal policy always gives the minimum expected total cost, the performance comparisons between the
PO
other four heuristics differ when another set of parameters are chosen. That is, the d policy can
NPO
sometimes have a better performance than the periodic and d policies

Figure

8 shows the expected number of path optimizations versus the inter-switch handoff rate l . The
expected number of path optimizations increases as l increases. Results of the Bernoulli and optimal
policies are quite close. Due to the threshold structure of the optimal policy, path optimization is
performed only after a certain number of inter-switch handoffs. Thus, the expected number of path
PO
optimizations for the optimal policy is smaller than the periodic and d policies.

Figure

9 shows the expected total cost versus the call termination rate m . The expected total cost
decreases as the call termination rate increases, which is intuitive since the link cost is accrued
continuously during the call lifetime. When m is large (i.e., the call duration is short), all the connections
experience a small number of inter-switch handoffs. Thus, the results of all these policies are close. When
the call duration increases, the results begin to diverge. We can see a significant cost difference between
the optimal policy and the other heuristics when the call duration is long (i.e., m is small).

Figure

shows the expected number of path optimizations versus the call termination rate m . The
expected number of path optimizations decreases as m increases. Due to the threshold structure of the
optimal policy, path optimization is performed only after a certain number of path extensions. Thus, the
expected number of path optimizations performed for the optimal policy is much smaller than the
PO
periodic and d policies.
In the previous results, we assume the time between inter-switch handoffs follows a Gamma
distribution. We also consider exponential and hyper-exponential distributions for the time between inter-switch
handoffs. For a fair comparison, the average time between inter-switch handoffs is the same for
various distributions. Figures 11 and 12 show the minimum expected total cost of the optimal policy
versus l and C , respectively. These results indicate that the expected total cost is relatively insensitive
link
to the distributions of the time between inter-switch handoffs.
6.3 Sensitivity Analysis
In order to calculate the minimum expected cost, the optimal policy table needs to be determined. The
policy obtained depends on the values of different parameters (e.g, l, m, C , and C ). Although the
link PO
parameters C and C can be determined by the network, the values of land may not always be
link PO
estimated correctly by the mobile terminal during call setup. If that is the case, the optimal policy may not
indeed be the optimal one. In this section, we are interested in determining the percentage change of the
expected cost per call to the variation of the average call duration and the average time between inter-switch
handoffs. The procedures for the sensitivity analysis consist of the following steps:
1. Given the actual call termination rate m and other cost and mobility parameters, we first determine the
minimum expected total cost, denoted as Cost (optimal).
2. Let m^ denote the estimated call termination rate and D denote the percentage change of the average
call duration. These parameters are related by the following equation:
Based on the estimated call duration rate m^ and other parameters, the sub-optimal policy is
determined. From this sub-optimal policy and other cost and mobility parameters (i.e., l, m, etc), the
sub-optimal expected total cost, denoted as Cost (sub-optimal), is computed.
3. The change in the expected total cost with respect to the variation of the call duration is characterized
by the cost ratio, which is defined as: Cost (sub-optimal) / Cost (optimal).
The results for different m are shown in Figure 13. When the average call duration is over-estimated by
more than -40 %, the cost ratio is almost equal to one, which implies that the optimal policy is insensitive
to the change of the average call duration. However, within the (-90, -50)percentage range, there is an
increase in the cost ratio. The cost ratio can be as high as 1.53 for These results imply that if
there is uncertainty in estimating the average call duration, it may be better to over-estimate the value in
order to reduce the cost ratio difference.
We use the similar procedures described above to investigate the percentage change of the expected
total cost to the variation of the time between inter-switch handoffs. Figure 14 shows the cost ratio versus
the percentage change in average time between inter-switch handoffs for different l . Within the
percentage range of interest, the cost ratio is always less than 1.07 (i.e., 7%). Within the (-50, 100)
percentage range, the cost ratio is less than 1.01 (i.e., 1%). These results imply that the optimal policy is
relatively insensitive to the change of the average time between inter-switch handoffs.
6.4 Discussions
In our simulation studies, we found the value iteration algorithm to be very efficient and stable. The
number of iterations is quite predictable from point to point, changing slowly as the independent
parameter changes. In general, the number of iterations to convergence does not depend on the cost
parameters (C , C , C ), but depends on the values of land m. As an example, for the optimal
link PO PE
policy in Figure 9, the value iteration algorithm required only 24 iterations to converge when
but it required 170 iterations when Note that there are other iteration algorithms available (e.g,
policy iteration algorithm) which have a higher rate of convergence. Interested readers can refer to [14]
for details.
In this paper, the wireless ATM network is modeled as a non-hierarchical random graph. One
question that arises is whether the results will differ if some other network topologies are being used. The
answer is affirmative. The relative performance between the four heuristics will change if another
network topology is being used. This is essentially the same as changing the values in the functions
p(mi, j)or (i, j). However, the optimal policy will always give the lowest expected total cost
compared to the other four heuristics.
7. Conclusions
In this paper, we have addressed the issue of when to initiate path optimization for the two-phase handoff
protocol. The path optimization problem is formulated as a semi-Markov decision process. A link cost
function is used to reflect the network resources utilized by a connection. Signaling cost function is used
to capture the signaling and processing load incurred on the network. The time between inter-switch
handoffs follows an arbitrary general distribution. When an inter-switch handoff occurs, based on the
current state information, the network controller decides whether to perform path optimization after path
extension.
We have presented the value iteration algorithm which determines the expected total cost and the
optimal policy. Under certain conditions, we have shown the existence of an optimal policy which has a
threshold structure. That is, path optimization is always performed when the number of links of the path
is greater than a certain threshold. The threshold structure of the optimal policy facilitates the
implementation. When an inter-switch handoff occurs, the decision of performing path optimization can
be made by a simple table lookup.
The performance of the optimal policy has been compared with four heuristics. Simulation results
indicate that the optimal policy gives a lower expected cost per call than those heuristics. These results
imply that by using the optimal policy, the mobile connection maintains a good balance between the
network resources utilized and the signaling load incurred on the network during its connection lifetime.
We have also performed sensitivity analysis for the optimal policy with respect to the variation of the
average call duration and the average time between inter-switch handoffs. Results indicate that the
optimal policy is relatively insensitive to the change of the average time between inter-switch handoffs. If
there is uncertainty in estimating the average call duration, it may be better to over-estimate the value in
order to reduce the cost ratio difference.
Future work includes extending the proposed model to analyze the (1) mobile-to-mobile connection
scenario; (2) multicast connection in which a group of mobile users are communicating with each other;
and (3) path optimization problem with QoS constraints. Although the proposed model captures the
trade-off between the network resources used and the handoff processing and signaling load incurred on
the network, the model is not without drawbacks. In our formulation, the call duration is exponentially
distributed. Although the exponential distribution is valid for voice traffic, this may not be appropriate for
multimedia applications [27][28]. This also points to the need for new analytical models for general call
durations.

Appendix

Proposition 1: Assume the cost, transition probabilities, and sojourn times are time homogeneous. If the
termination time of a finite-horizon semi-Markov decision process is exponentially distributed with mean
then it is equivalent to an infinite-horizon semi-Markov decision process with discount rate m . That
is, we must show that (1) is equivalent to
where
c(s, a)= b(s, a)+ Es --m-(1 - e )f(s).
Proof: For clarity, we will analyze the three terms in (1) separately. Let
where
For the first term in (1),
dt.
If m represents the last decision epoch before termination, then
By interchanging the order of summation, we have
dt.
p-msn
For the second term in (1), we have
dt.
By interchanging the order of summation, we obtain,
For the third term in (1),
pT
If n represents the last decision epoch before termination, then
ts f(Xn)dtme-mtdt .
By interchanging the order of integration, we have,
Substitute (22)-(24) into (21), we obtain:
Recall c(s, a)denotes the expected total cost between two decision epochs, given that the system
occupies state sat the first decision epoch and that the decision maker choose action ain state s. Since
the cost, transition probabilities, and sojourn times are assumed to be time homogeneous,
at -mt
c(s, a)= b(s, a)+ Es - e f(s)dt
Substitute (26) into (25), we have
The discrete-time version of this result can be found in Chapter 5 of [14].
For stationary deterministic policy d :
d d-mt1 d
-mt d
Lemma 1: For each state (i,j,k) S , the expected total cost v(i,j,k)is a nondecreasing function with
respect to the number of links k .
Proof: The proof of this lemma is by induction. We must show v(i,j,k)-v(i,j,k+ 1) 0. Recall
-mt
v(i,j,k)= c(i,j,k,PO)+   I2v(l,i,n)p(ni, D)q(li).
From (9) and (10), it is clear that c(i,j,k,a) c(i,j,k+ 1,a)for all k . Hence,
v(i,j,k)< c(i,j,k+ 1,PO)+   I2v(l,i,n)p(ni, D)q(li)
Thus, v(i,j,k) v(i,j,k+ 1)for K k< L.
c(i,j,K- 1,PO)+    I2v(l,i,n)p(ni, D)p(mi, j)q(li)
c(i,j,K- 1,PO)+   I2v(l,i,n)p(ni, D)q(li)
c(i,j,K,PO)+   I2v(l,i,n)p(ni, D)q(li)
v(i,j,K).
For We need to show
From (14),
v(i,j,k)= min -c(i,j,k,NPO)+   I2v(l,i,k+ m)p(mi, j)q(li),
c(i,j,k,PO)+    I2v(l,i,n)p(ni, D)p(mi, j)q(li).
Let a* denote the optimal action of state (i,j,k+ 1). If
c(i,j,k+ 1,PO)+    I2v(l,i,n)p(ni, D)p(mi, j)q(li)
On the other hand, if
c(i,j,k+ 1,NPO)+   I2v(l,i,k+1 +m)p(mi, j)q(li)
To complete the proof, we need to show v(j,j,k)-v(j,j,k+ 1) 0for 1  k< K. From (13),
c(j,j,k+ 1,NPO)+  I2v(l,j,k+ 1)q(lj)
v(j,j,k+ 1).
Thus, by the principle of induction, for each state (i,j,k) S , the expected total cost v(i,j,k)is a
nondecreasing function in k .
Proposition 2: For (i,j,k)S , there exists an optimal policy d* that has a control limit (or threshold)
structure:
PO, k* kL
when I1Df(k+ m)-DhPO(k+ m- n)p(ni, D) 0for all msuch that p(mi,
Proof: Let
r(i,j,k)=  I1 f(k+ m)p(mi, j)+   I2v(l,i,k+ m)p(mi, j)q(li)
Thus, the action PO is chosen if r(i,j,k) 0 and the action NPO is chosen if r(i,j,k)< 0 . Let k^ be the
smallest ksuch r(i,j,k)0 . For convenience, let Dr(i,j,k^)= r(i,j,k^
Since v(i,j,k)is a nondecreasing function in k , Dv(l,i,k^ + m)0 . Thus, Dr(i,j,k^) 0 when
for all msuch that p(mi,
Then
Dr(i,j,k)=   I2Dv(l,i,k+ m)p(mi, j)q(li)+  I1Df(k+ m)p(mi,
Since v(i,j,k)is a nondecreasing function in k , Dv(l,i,k+ m)0 . Thus,
(k+ m) (K - 1)
I1Df(k+ m)- DhPO(k+ m- n)p(ni, D) 0
for all msuch that p(mi, . Thus, by induction, the optimal policy has a threshold structure when
I1Df(k+ m)-DhPO(k+ m- n)p(ni, D) 0for all msuch that p(mi,

Acknowledgments

The authors would like to thank the anonymous reviewers as well as Martin Puterman and Henry Chan
for their comments on an earlier draft of this paper.


--R

Special Issue on Wireless ATM












Discrete Stochastic Dynamic Programming.
Introduction to Stochastic Dynamic Programming.


The ATM Forum Technical Committee



The ATM Forum Wireless ATM Working Group






--TR
A quantitative comparison of graph-based models for Internet topology
Performance evaluation of connection rerouting schemes for ATM-based wireless networks
Performance evaluations of path optimization schemes for inter-switch handoffs in wireless ATM networks
Route optimization in mobile ATM networks
QoS routing in networks with inaccurate information
Performance evaluation of path optimization schemes for inter-switch handoff in wireless ATM networks
Markov Decision Processes

--CTR
Dilek Karabudak , Chih-Cheng Hung , Benny Bing, A call admission control scheme using genetic algorithms, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Shilpa Yogesh Tisgaonkar , Chih-Cheng Hung , Benny Bing, Intelligent handoff management with interference control for next generation wireless systems, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
path optimization;inter-switch bandoff;connection rerouting;wireless ATM