Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2002-10-04
2004-01-27
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
Reexamination Certificate
active
06683852
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods and apparatus for improving routing in packet networks and, more particularly, to methods and apparatus for improving generic call admission control and for reducing computational loads associated with route selection.
BACKGROUND OF THE INVENTION
It is known that ATM (Asynchronous Transfer Mode) technology has been undergoing intense standardization efforts in recent years under both the ITU (International Telecommunications Union) and the ATM Forum. For example, a set of specifications relating to routing and signaling protocols for an ATM private network-to-network interface (PNNI) has been developed by the ATM Forum, i.e., ATM Forum, “Private Network-Network Specification Interface 1.0,” af-tm-0055.000 (March 1996).
In the PNNI framework, network nodes (switches) constantly send updates on the status of their local links to all other nodes in the network. These updates are sent periodically and/or triggered by changes in link attributes such as the available bandwidth or cell rate (AvCR) of the link. While some link attributes, such as available bandwidth, change frequently as calls arrive and depart, certain others remain relatively constant. For example, administrative weights (AW) associated with links fall into the latter category. These weights can be manipulated by network operators via the network management system and are meant to guide the route selection algorithms in selecting least AW cost paths. Based on the updates received, each network node constructs its own topological view of the network. Routes through the network are independently computed by each originating (source) node based on its view of the network. Upon a call origination, the source node needs to check if the candidate route satisfies the requirements of the current call in terms of, for example, quality of service (QoS) requirements given its traffic descriptors. QoS requirements include, for example, bandwidth and delay requirements. This check is referred to as generic call admission control (GCAC). In addition, network nodes along the path of the call (intermediate nodes) perform their own call admission control referred to as local call admission control (LCAC).
It is known that there are numerous performance issues in PNNI routing. They can be broadly categorized as addressing two types of limiting resources, namely: real-time resources, e.g., call processor (CPU) utilization in the switch control complex; and the cell transport resources, e.g., transmission bandwidth of a link. The demands for real-time resources stem from handling call set-up/teardowns including path selection at the source switches, performing call admission control at the local switches, and processing incoming and outgoing link state advertisements. The performance is measured primarily in terms of the amount of real-time resources required to handle a given load and the resultant processing delay characteristics. Given a network, this performance is a strong function of the design/implementation of the related algorithms, the computational cost of the chosen algorithms and the settings of the tunable parameters. Limiting transport resources include switch cell buffers and link bandwidth required to support the desired QoS of the admitted calls.
Due to the source routing nature of PNNI, the design of the routing algorithm has a direct impact on how efficiently the network links are utilized. Further, given a distributed architecture in which switches, possibly from different vendors, independently compute routes, ill-advised route selections may result in excessive crankbacks or rejections of call set-up requests and, subsequently, create unnecessary real-time load on the call processors associated with the node or switch.
Under the PNNI architecture, a source switch has to select a candidate path such that there is a reasonably high probability for all the switches along the accepted path to accept the call. Otherwise, as mentioned above, a substantial amount of crankback or rejection can result which unnecessarily consumes network and switch resources while increasing call set-up delays. It is therefore necessary for a source switch to estimate the availability of various resources at other switches within the network. It is known that such estimation can only be based on the limited and possibly outdated information derived from previous switch update advertisements. The exact penalty and tradeoff depends on the frequency of link state update advertisements and the algorithms used for GCAC at the source switch and LCAC at the intermediate switches.
Assume a link of capacity C and homogenous connections (calls) arriving at the link. Let N
max
denote the maximum number of connections that can be supported on the link according to the LCAC. Let ebw
lcac
=C/N
max
denote the effective bandwidth connection according to LCAC. Similarly, let ebw
gcac
denote the per-connection effective bandwidth according to GCAC. Let N(t) denote the current number of connections admitted to the link. Then C−N(t)*ebw
lcac
is the available bandwidth, denoted as AvCR, at the link and is the value advertised in the link state update by the node to which the link is coupled. Note that in GCAC, it is this AvCR value that is compared to the effective connection bandwidth computed by the GCAC. Thus, the probability that a connection is blocked by the GCAC is given by:
P
b
l
o
c
k
=
P
©
-
N
(
t
)
*
e
b
w
l
c
a
c
<
e
b
w
g
c
a
c
)
=
P
(
N
(
t
)
*
e
b
w
l
c
a
c
<
C
-
e
b
w
g
c
a
c
)
=
P
(
N
(
t
)
>
N
max
-
e
b
w
g
c
a
c
/
e
b
w
l
c
a
c
)
&AutoLeftMatch;
These relationships suggest that if ebw
gcac
>ebw
lcac
, the GCAC is conservative as compared to LCAC, and if N
max
is much larger than ebw
gcac
/ebw
lcac
, which is typically the case, then loss of utilization due to GCAC may be negligible. However, if the ebw
gcac
is estimated by the source node to be too conservative, i.e., using a higher effective bandwidth than necessary so that there is a buffer, there is a risk that links associated with intermediate switches would not be utilized. On the other hand, if GCAC is aggressive compared to LCAC, then depending on the difference, there can be an undesirably large number of crankbacks. In fact, even if the GCAC and the LCAC are exactly the same, i.e., ebw
gcac
=ebw
lcac
, it is still possible to get crankbacks due, for example, to delays in the link state updates reaching all network nodes and the fact that the updates are typically only generated when there are significant changes in the network state.
Since a path chosen by a source node will likely pass through more than one link in order to get to the destination node, the available bandwidth associated with the path is characterized by the link having the smallest available bandwidth, as illustrated by the P
block
equation above. Thus, in order for the source node to characterize a path as sufficient to set-up the call on, the relationship AvCR≧ebw
gcac
must be satisfied for each link. Various ATM classes of service choose an equivalent bandwidth (ebw
gcac
) definition. For example, as suggested in the above-referenced PNNI standard, the CBR (constant bit rate) class uses the PCR (peak cell rate) as an equivalent bandwidth. The VBR (variable bit rate) class uses the relationship of SCR[1+(PCR/SCR)], where SCR is the sustained or mean cell rate. The ABR (available bit rate)
Nagarajan Ramesh
Wang Yung-Terng
Chin Wellington
Lucent Technologies - Inc.
Schultz William
LandOfFree
Call admission control methods and apparatus for improving... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Call admission control methods and apparatus for improving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Call admission control methods and apparatus for improving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3268258