Title of Invention


Abstract Methods and system for providing line grain call admission control network a communication network are disclosed. Under some embodiments, the fine grant control methodizes proxibility of coll serviced by the network oil a call class basis.
Full Text Wireless Network
Field of the Invention
This invention relates to wireless wide area networks and, more particularly, to
call admission control in such networks.
Discussion of Related Art
Subscribers are adopting wireless communications in increasingly large
numbers. Wireless wide area networks service such calls via Mobile Switching
Centers (MSC's), other switches, and other components.
To keep the MSCs and other switches from getting overloaded, the
admission of new calls is controlled via a process known as "Call Admission
Control." In this fashion, some guarantee on call processing delay can be given
to a very large percentage of the calls processed by the switch. For example, a
quality of service (QoS) metric may be established (e.g., calls will suffer less
than 200 ms of call, setup latency), and through the control of new calls, the QoS
metric can be guaranteed for call setups in progress. Call admission control
involves reducing (or throttling) the call arrival. In short, with call admission
control some calls are dropped before processing rather than potentially
saturating the system by attempting to handle the call.
A conservative call admission control policy can prevent the switch
from getting overloaded but at the expense of throughput. An aggressive call
admission control policy can increase the throughput but may be unable to meet
the QoS metric (as a consequence of not detecting congestion fast enough).
In a distributed system, throttling can be implemented in multiple ways
based on the ability of the peer entity and the communication protocol among
the entities. For example, the peer entity may be capable of receiving explicit
feedback through the control/signaling protocol to reduce the call rate or the
peer entity may have to implicitly inter from expired timers for calls that were
not responded to by the switch. Some systems may effectively look at the most

WO 2004/053643 PCT/US2003/038865
utilized component (i.e., the closest to being saturated) and throttle the calls
To control call admissions, software logic is typically used to determine
when the number of calls arriving into the switch or MSG is in danger of
saturating the switch. The call admission control logic will "drop calls" to
prevent such saturation. To date, many call admission control policies have
been ad hoc, There ia a need in the art for an improved method and system for
controlling call admissions to the network.
The invention provides methods and systems for providing fine grain.
call admission contral into a communication network.
According to one aspect of the invention, the fine grain control
maximizes the aggregate revenue for the service provider.
According to another aspect of the invention, an allocatable call
admission budget for the communication network is obtained. A set of call
classes for the communication network, are identified in which each class has a
corresponding call arrival rate, revenue and cost. Pot each call class a
corresponding profitability metric is determined. A corresponding throttling
fraction is determined for each call class in which the throttling fraction is a
function of the profitability metric and the allocatable call admission budget.
The throttling fractions for each class are provided to a call admission control
server to throttle calls for each class accordingly.
Under another aspect of the invention, the call arrival rate is a historical
Brief Description of the Drawings
In the Drawing,
Figure 1 is a system diagram of an exemplary wide area wireless
Figure 2 is a diagram illustrating network and switch components that

WO 2004/053643 PCT/US2003/038865
may lead to congestion or saturation of a network switch;
Figure 3 is a diagram of a network management server according to
certain embodiments of the invention;
Figure 4 is a flow chart illustrating logic for calculating of throttling
rates according to certain embodiments of the invention
Figure 5 illustrates call arrival rates and smoothed call arrival rates.
Detailed Description
Preferred embodiments of the invention provide a method and system
for controlling call admissions to a switch in a wireless wide area network using
fine grain control. Under certain embodiments, the calls are characterized
according to classes, and each class has a corresponding metric to be optimized.
For example, the metric may be revenue to the service provider, or it may be a
ratio of revenue to cost of servicing such a class of call (i.e., profitability
metric). Optimal throttling rates for each class of calls may be calculated
accordingly to thus provide improved revenue to the service provider. Under
one preferred embodiment, throttling fractions are determined based on the
arrival rates i of the corresponding classes of calls, the metric to be optimized r,
and the processing cost S of the call. These parameters are considered in view
of an upper bound of utilization-a level which if exceeded may result in
saturation of the switch or which may hinder satisfaction of QoS guarantees.
The throttling fractions are then used by the call admission control logic to
throttle calls according to their class.
Figure 1 illustrates an exemplary wireless wide, area network in which
embodiments of the invention may be realized. The specific example of figure 1
is a simplified 3G network in accordance with the CDMA 2000 proposal, but
persons skilled in the art will appreciate that the invention may be realized in
any telecommunication network utilizing call admission control policies.
In the exemplary network, mobile stations 102 communicate over an air
interface 103 with a radio access network (RAN) 104. The RAN 104 includes
Base Transceiver Stations (BTS) 106 that are in radio contact with the mobile

WO 2004/053643 PCT/US2003/038865
station and that are in fixed line communication with a Base Station Controller
(BSC) 108. The BSC 108 controls the radio equipment used to communicate
with the mobile stations. This function is collectively referred to as Radio
Resource Management, and it encompasses the management of handoffs of the
roaming mobile stations 102 within a BSC and the allocation of radio channels
for both voice and data traffic.
The RAN 104 communicates with a Packet Data Serving Node (PSDN)
116 which in turn communicates with IP Backbone 118.
The BSC communicates with a Mobile Switching Center (MSC) 112,
which is a standard Local End Office with enhanced call processing software
(including mobility management) and (optional) hardware that can perform
transcoding and rate adaptation functions. For example, certain embodiments of
the invention may use the MSC described in U.S. Pat Appl. Ser. No.
09/721,329 filed on Nov. 22, 2000 (which is hereby incorporated by reference
in its entirety) and assigned to the assignees of the present invention with the
modifications described herein. Likewise, other MSCs may be used with the
modifications described herein.
Typically, signaling information between the BSC and the MSC is
conveyed in accordance with a predefined protocol, and voice/data is conveyed
over bearer circuits in accordance with other protocols. Among other things, the
MSC 112 provides mobility management functionality. This function consists
of manage meat of mobile station parameters such as the location of a mobile
station, mobile identity and authentication. Handoffs between BSCs and
between MSCT8 are controlled by the MSC. The MSC communicates with the
Public Switched Telephone Network (PSTN) 114 using known signaling and
bearer circuit protocols.
The Mobile Switching Center (MSC) receives call setup requests from
mobile users via the RAN and incoming call requests from other PSTN
endpoints to mobile users. The actual signaling interfaces and the associated
signaling protocols depend on the specific network topology. For example in a
CDMA 2000 network, outgoing calls from mobile subscribers in a MSC area

WO 2004/053643 PCT/US2003/038865
arrives at the MSC through the IOS/IS-634 signaling interface from the RAN,
whereas incoming calls from the PSTN arrive through ISUP protocol. In next
generation systems, call set-up requests may also arrive at the MSC from the
PDSN originating from either IP-enabled handsets or newer generation RANs
that generate IP traffic (both signaling and bearer). The specific computing task
performed by the MSC depends on the signaling protocol, call type,
caller/callee information etc. The aggregate computational resource usage of the
MSC depends on the call arrival rates at each signaling interface.
Figure 2 shows a simplified architectural diagram of select internal
software modules of an exemplary MSC 112, The simplified diagram is used to
help illustrate the numerous types of call arrivals that axe handled by a switch
112 and that are a potential source of saturation of the switch.
The architecture includes an IP Message Handler (IPMH) 208, which
handles messages from a PDSN or a new generation RAN that generates IP
traffic, a SS7 Message Handler 210 which handles SS7 messages from
BSC/RAN 104, a Communications Session Manager (CSM, more below) 202, a
Visitor Location Register (VLR) 206, a Media Gateway (MGW) control process
204, and call admission control (CAC) server 212,
The IPMH 208 and SS7 Message Handier 210 each handle messages
from their associated links under the control of the CSM 202 and CAC Server
212. In relevant part, the CAC Server sends control messages via software
communication channels 214, 216 to instruct the message handlers about
various throttling rates for specific classes of calls. The message handiers in
turn throttie incoming calls accordingly, For example, if the IPMH 208 were
instructed to throttle 20% of calls of a certain class, under certain embodiments
the IPMH would randomly throttle 20% of such calls by effectively preventing
such calls to be "set-up" or established. The message handlers also use the
communication channels 214, 216 to convey various forms of statistical
information to the CAC Server 212.
The CSM 202 terminates the- signaling protocols and performs the
session and mobility management functions. To do so, the CSM communicates

WO 2004/053643 PCT/US2003/038865
to the message handlers 208, 210, the VLR 206, and the MGW via
communication channels 218, 220, 222, and 224.
The VLR 206 performs subscriber record lookups for all active
subscribers at the MSC 112.
The MGW control process 204 sends commands to the media gateway
that control the termination and switching of the actual bearer (voice/data)
The CAC Server 212, in relevant part, is responsible for call admission
control of the system. The CAC Server, of certain embodiments, is implemented
as a module as part of an Operations, Administration, Management, and
Provisioning system (OAM&P, more below). It includes logic (more below) to
compute throttle functions in an efficient way. The throttle functions are used to
control che throttling for a next measurement window (which may be controlled
in a variety of ways, e.g., periodically or only when certain thresholds are
reached). The throttle functions (or values) are conveyed to the message
handlers, e.g., IIPMH 208, so that they may actually perform such throttling. As
explained below, the throttling functions may be associated with classes of calls
that the message handlers may discriminate. Under certain embodiments, the
throttling functions are determined via an optimization procedure such as one to
optimize a profitability metric for the system. Other methods of determining
throttling functions may also be used, which might provide improvements to
such metrics, but perhaps sub-optimally. Under certain embodiments, the CAC
Server collects various statistics from the message handlers and the CSM via
channels 214, 216 and 226. The CAC Server may also implement smoothing
logic (more below) to determine certain relevant statistics such as smoothed
arrival rates of various classes of calls.
Figure 3 shows an exemplary switch architecture including select
hardware components and illustrating the layered nature of an exemplary
software architecture. In this instance, call admission control logic is
implemented in a call admission control server 302, which is part of a network
management server 300, The CAC server 302 obtains event detail records from

WO 2004/053643 PCT/US2003/038865
an Event Collector 304 in the network management server 300. The Event
Collector receives event detail records from the individual hardware modules of
the switch 112, and in this fashion may collect various forma of statistics. For
example, as illustrated, the CAC Server may collect statistics, for example, from
the SS7 signaling module 210 and the CSM module 202. The network
management server also accepts network configuration parameters and certain
of these may be conveyed to the CAC Server 302. For example, under certain
embodiments, an upper bound UB of switch utilization may be provided by an
administrator. The utilization in turn may be a form of measure or calculation of
various monitored performance statistics, e.g., memory and CPU utilization at
the switch, queue length and delay, etc.
The CAC server 302 enforces throttling comral through a Policy
Interface 306 exposed by the OAM&P system 308. For example, the CAC
Server may calculate various throttling functions for various classes of calls and
convey such to the appropriate message handlers and modules, e.g., IPMH 208
SS7 MH 210. Thereafter, the message handlers may analyze each incoming call
to determine its corresponding class and subject it to its throttling logic, e.g.,
dropping certain fractions of calls in some way, e.g., weighted random
For example, for a given throttling fraction i1, where 'i' is the class of
call, the throttling logic within the CAC Server will calculate or determine a
corresponding function and will instruct the appropriate message handler to
permit only that fraction of calls for that class to be admitted. The message
handler will drop other calls within the corresponding time window (i.e., the
intervening time before a subsequent control message is received by the
message handler).
One embodiment of the logic uses the following parameters to determine
corresponding throttling values:
• P is the number of revenue classes in consideration
• t is the throttle value associated with class i and by definition is
greater than or equal to zero and less than or equal to one.

WO 2004/053643 PCT/US2003/038865
• li is a smoothed estimate of the arrival rate for calls of class i
(more below
regarding smoothing)
• t, is the revenue per call associated with class i
• St is the cpu time required (or more generically the "cost") to set
up calls of type i
• UB is an upper bound on the utilization of the switch, which
preferably should not be exceeded, to honor QoS delay requirements on call
The total revenue generated over all the classes P of calls may be
represented with the following equation, Consequently, maximizing, the
following equation maximizes revenue.

However, though service providers will desire to maximize the above
revenue equation, they should maintain the following constraint to satisfy QoS.
The constraint effectively states that the cost on the system should be less than
the pre-established upper bound (UB).

One efficient way to solve the above is to transform the throttling
variable with a new variable, Specifically, by defining a new, transform variable
t * according to the following equation

and substituting t * into the total revenue equation, the maximization problem
may be restated as follows:

WO 2004/053643 PCT/US2003/038865
subject to the constraints that:

Various values for ti * may then be found by solving the system of
equations, and the ti * may transformed back to ti , which may then be used in
control messages to the message handlers, as outlined above.
Figure 4 is a flow chart showing exemplary logic for solving ti *
according to one embodiment of the invention. The logic starts in 400 and
proceeds to 405 in which the metric being optimized (e.g., revenue, ti) is
divided by its corresponding cost Si, for each class. In 410 the ratios are ranked
in descending order. When the metric r is revenue, the ratios and descending
order correspond to a tanking of corresponding revenue per unit cost for each
In 415, a check is made to determine whether the t* have been
determined for all classes, If they have the logic ends in 499. Until the last class
(with the lowest ratio) is analyzed to determine its corresponding t* , the logic
will flow through the "No" branch and proceed to 420. In 420, the following
equation is solved for the current class i1 being considered;

If one thinks of UB as the budget that may be allocated, this equation
effectively determines if the budget allows the current class to be fully serviced,
in which case the class i will have its * allocated its corresponding iSi;. But, if
the full amount needed to serve the class being considered cannot be granted,
then the allocation gives the class as much of the resources as remains (j,e., the

WO 2004/053643 PCT/US2003/038865
upper bound minus the summation of all previously allocated t*).
In 425, the t* are transformed back to t values which may then be
utilized by the call admission control logic 302 to instruct corresponding
message handlers accordingly. The logic then loops back to 415 to consider the
next class in the metric per unit of cost order.
In this embodiment, the call access control policy imposes one QoS
constraint on all classes of calls. The estimated throttling factors are also non-
preemptive and static. In alternate embodiments, it is possible to add utilization
constraints specific to each call type. It is also possible to implement dynamic
throttling with call preemption. By doing this, lower revenue producing calls in
progress can be preferentially dropped for higher revenue producing calls under
a utilization bound restriction.
In some embodiments, it may be preferable to use a statistically
smoothed call arrival rate for the various l. Figure 5 illustrates call arrival
measurement windows used for determining throttling values in certain
embodiments. The length of the measurement windows should be long enough
to represent a reasonably good statistical sampling period, l(c) is the call arrival
rate at the current arrival window. In order to avoid false alarms or missed
congestion, it is imperative to smooth the call arrival rate by taking into account
the current arrival rate and the arrival rates of past measurement windows. In
this case,l(rc) represents the smoothed arrival rate of the current window and
l (sp) represents the smoothed arrival rate of the past arrival window.
The smoothed arrival rate of the current window is modeled by the

where wc and wp represent the weighing factors for the current and past
windows and should add to 1. The weights may be set and re-established by the
system. For example, wc may be set to 0.8 and wp may be set to 0.2. Of course,
other forms of exponential smoothing may be employed In addition the call
arrival rates may be based on historical statistics. For example, Che rates may be

WO 2004/053643 PCT/US2003/038865
set to correspond with the time of day or the time of year.
At end of current window, the smoothed arrival rate of the past window
should be approximately equal the arrival rate of the current window as
Thus, using the above approach and assuming that the optimizable
metric is revenue, calls from a class having higher revenue per unit cost may be
throttled differently than calls from a class with lower revenue per unit cost.
Also, since cost is factored into the analysis, it may not be the case that calls
with simply the highest revenue are prioritized.
Analogously, the call throttling may consider other criteria such as
priority. For example, emergency calls may have special throttling procedures
to allow the calls through. As an example of revenue classes, consider two types
of customers: Type 1 customer has a monthly flat subscription fee and is
allowed "unlimited" number of calls during the month. Thus the per call
revenue for the service provider is 0, since the call is free. Type 2 customer is
not a member of this flat fee and pays a premium revenue on a per call basis.
One of the main aspects of the above embodiments is the formulation of
the "revenue-based" call admission control as a linear programming problem
(LP). The decision variables of the LP are the throttle values for the various
revenue classes. Another key aspect of the above embodiments is the simple
linear algorithm to determine the "optimal" solutions to the LP.
Traditionally LPs are solved using algorithms that are high degree polynomials
in computational complexity. In several described embodiments, however, such
computational complexity is avoided, thus reducing load and enhancing
efficiency of the MSC or switch.
At certain points in the description above, logic was described which
created a throttling function. This terminology was used to show that the actual
determination of a throttling value may be distributed in many ways. For
example, the CAC Server may have logic to partially or fully determine the

WO 2004/053643 PCT/US2003/038865
value. In the former case, the final determination may be made by a
corresponding message handler.
The above embodiments provided throttling fractions in various ways.
One preferred embodiment, for example, calculated optimal, or near optimal
values, using a linear programming approach. Alternative embodiments
however may provide throttling fractions in other ways. For example, throttling
fractions may be provided by a look-up table in which all or a subset of the
above parameters, e.g., arrival rates, and class, may be indices into the table or
other data structure.
It will be further appreciated that the scope of the present invention is
not limited to the above-described embodiments, but rather is defined by the
appended claims, and that these claims will encompass modifications of and
improvements to what has been described.
What is claimed is:

WO 2004/053643 PCT/US2003/038865
1. A method of controlling call admissions in a communication network,
obtaining an allocatable call admission budget for the communication
identifying a set of call classes for the communication network, wherein
each class has a corresponding call arrival rate, revenue, and cost
for each call class determining a corresponding profitability metric,
assigning a corresponding throttling fraction for each call class wherein
the throttling fraction is a function of the profitability metric and the allocatable
call admission budget;
providing the throttling fraction for each class to a call admission control
server to throttle calls for each class accordingly.
2 , The method of claim 1 wherein unallocated call admission budget is defined
as the allocatable call admission budget minus the transformed throttling
fraction of any class for which a transformed throttling fraction has been
assigned, and wherein in descending order starting from the class having the
highest profitability metric and proceeding through the class with the lowest
profitability metric, the transformed throttling fraction for each class is
determined as the minimum of unallocated call admission budget and the
product of the call arrival rate and cost for the corresponding class.
3. The method of claim 1 wherein each call class has a corresponding revenue
metric per call and the profitability metric is the revenue metric divided by the
corresponding cost.
4. The method of claim 1 wherein the call arrival rate is a smoothed average
call arrival rate.
5. The method of claim 1 wherein the call arrival rate is a historical metric.

WO 2004/053643 PCT/US2003/038865
6. The method of claim 1 wherein the act of assigning a corresponding throttling
fraction t for each call class i includes the acts of
modeling the allocation of resources as a linear programming problem,
in which, the throttling fractions ti for each call class i are decision, variables of
the linear programming problem, and wherein the linear programming problem
is solved by transforming the throttling fractions to a transformed throttling
fraction ti" according to the equation

wherein li is an estimate of a call arrival rate for class i and Si is an estimate of
cost to service a call in class i.

Methods and system for providing line grain call admission control network a communication network are disclosed.
Under some embodiments, the fine grant control methodizes proxibility of coll serviced by the network oil a call class basis.


Patent Number 214243
Indian Patent Application Number 00959/KOLNP/2005
PG Journal Number 06/2008
Publication Date 08-Feb-2008
Grant Date 07-Feb-2008
Date of Filing 24-May-2005
# Inventor's Name Inventor's Address
PCT International Classification Number H04Q 7/12
PCT International Application Number PCT/US2003/038865
PCT International Filing date 2003-12-04
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 10/310,329 2002-12-05 U.S.A.