Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-08-03
2003-09-30
Olms, Douglas (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S230000, C370S395200
Reexamination Certificate
active
06628612
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to apparatus for connection admission control, to apparatus for resource control in networks, and to corresponding methods, and to software for carrying out such methods.
BACKGROUND TO THE INVENTION
Connection Admission Control is one of a number of known techniques for managing and controlling traffic and congestion in connection-orientated networks. In particular, it is used in ATM (a synchronous transfer mode) networks to provide quality of service (QOS) guarantees. It is not limited to use in ATM networks.
Connection Admission Control (CAC) procedures are used to decide if a request for an ATM connection can be accepted, based on the network capacity and the attributes of both the requested connection and existing connections. This is one application which requires that an equivalent bandwidth be determined accurately both for the new connection and for the existing connections. It is important that there is always enough bandwidth so that quality of service guarantees for the existing connections and the requested connections, can be met.
CAC procedures may be used at an access mode at the edge of an ATM network to enable control of access to the entire route through the ATM network as route selection is made. A second level, may be used at each node along the selected route through the ATM network, to confirm that a respective link beyond that node, can admit the connection.
An estimate of the bandwidth required by the connection, and knowledge of the available bandwidth on each link is required. The CAC algorithm at the network edge uses parameters available from the routing database, and characteristics of the connection being requested (available from signalling information) to determine if an individual link is likely to accept or reject the connection. The link
ode is included if it is likely to accept the connection, and excluded from the route selection algorithm if it is unlikely to accept the connection.
After path selection is done, each node along the chosen route executes its own CAC algorithm, using factors such as link capacity, buffering capability or queuing architecture, traffic descriptors, QOS requirements and capacity allocated to different types of traffic or different connections.
Some of these parameters are fixed and some are variable. Queue size and the desired QOS are examples of fixed parameters, whereas the traffic descriptor and current available link capacity are dynamic parameters. The calculation is complex because connections typically use variable rates of ATM cell flow. Such flows can be described statistically using parameters such peak cell rate, and mean burst size. By calculating an effective capacity, also known as effective bandwidth, for individual connection, many connections can share the bandwidth of an individual link more efficiently, without having to provide the peak bandwidth for all connections.
Many algorithms have been proposed for determining the effective capacity of the requested connections, and of existing connections. Some are described in an article entitled “Performance Evaluation of Connection Admission Control Techniques in ATM Networks” by Jamoussi et al, published in a 1996 IEEE journal. This article notes that a good CAC algorithm strives to achieve a balance of the following objectives:
QOS guarantee, execution speed, link efficiency, and simplicity.
A useful summary of admission techniques is an article by Perros and Khaled in IEEE communications magazine November 1996, “Call Admission control schemes, a review”. One known technique is shown in an article by Guerin et al entitled “Equivalent capacity and its application to bandwidth allocation” from the IEEE journal on selected areas in communications. Vol 9, no. 7. It involves determining an approximation for the equivalent bandwidth of an individual connection by using a known relationship between parameters of the connection, size of buffer at the Admission control node, and a quality of service matrix which may be probability of overflow, ie cell loss ratio (CLR).
This relationship is complex, and so can only be evaluated by numerical or iterative methods which are too computationally intensive to be usable in a practical network with sufficient accuracy. Accordingly, in Guerin et al, a major factor in this complex relationship, is approximated rather than evaluated. This enables the relationship to be evaluated using normal algebraic methods without requiring a lengthy numerical analysis or iterative method.
To calculate the aggregate equivalent bandwidth of the numerous connections already admitted, so that the available bandwidth can be determined, Guerin et al proposes taking the minimum of two approximations. The first is a static approximation, and the second is a fluid flow approximation. The result is always greater than the real equivalent capacity. The static approximation is representative of the bandwidth required for a large numbers of connections, when the effects of statistical multiplexing become significant. The fluid flow approximation is more representative of actual connection behaviour and so is more useful when the number of connections is small. The static approximation is the sum of the mean bandwidths of the individual connections, which can be measured, plus a proportion of the standard deviation of the aggregated connection. The proportion reflects the desired quality of service, or risk of dropping a connection.
The fluid flow approximation is more difficult to calculate. In Guerin a straightforward summation of the values calculated for individual connections is made. This implies an assumption of a linear relationship between the equivalent bandwidth and the number of connections. In Guerin et al different equivalent capacity values can be calculated for each of several different traffic classes, hence the equivalent bandwidth will depend on both the number of connections, and the traffic class. Nevertheless, the relationships remain linear.
Under particular conditions, such as bursty data traffic, with low numbers of connections, these known methods may overestimate the equivalent capacity by 100 per cent or more. Furthermore, they are still computationally intensive, which can affect the post-dialing delay (PDD), and affect the channel density of nodes in the network.
SUMMARY OF THE INVENTION
According to a first aspect of the invention there is provided admission control apparatus for controlling admission of connections to a network, the apparatus comprising:
circuitry for receiving a request for admitting a connection to the network,
circuitry for determining whether to admit the requested connection according to whether a bandwidth used would exceed a maximum bandwidth allowed for at least a portion of the network,
circuitry for determining the bandwidth used, by determining an aggregate equivalent bandwidth of all connections in the portion of the network, by determining a static approximation and a flow approximation, the flow approximation having a non-linear relationship to the number of connections.
Using a non linear relationship enables the equivalent available capacity for a number of connections to be determined more accurately with less computational resources. In this context, controlling admission is intended to encompass both controlling whether a connection becomes admitted, and once admitted, whether it remains admitted to the network.
Preferred Features
Preferably, the connections may be of more than one type, and the determination of the flow approximation is made according to the type of the connection.
Preferably the apparatus further comprises a look up table accessible according to the number of connections, for providing an incremental value of equivalent bandwidth for use in the determination of the flow approximation. This can reduce the amount of calculation which needs to be done in real time when a connection is requested. This enables PDD to be reduced, or more connections to be handled for a given amount of processing power in a given time.
Gibbs Graeme A
Gvozdanovic Rade
Sabry Martin
Tang Cho Y
Barnes & Thornburg
Nortel Networks Limited
Olms Douglas
Wilson Robert W.
LandOfFree
Derivation of equivalent bandwidth of an information flow does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Derivation of equivalent bandwidth of an information flow, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Derivation of equivalent bandwidth of an information flow will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044299