Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-11-08
2003-08-19
Chin, Wellington (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S230000
Reexamination Certificate
active
06608815
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the Connection Admission Control (CAC) finctions in a broadband Integrated Service Digital Network (TSDN) using cell/packet-based technologies of, either Asynchronous Transfer Mode (ATM) switch designs for both satellite and terrestrial applications, or new Internet Protocol (IP) router designs with Grade or Service (GoS) concepts such as differentiated service or Multi-Protocol Label Switching (MPLS) architectures.
BACKGROUND OF THE INVENTION
New generations of broadband ISDN technologies that integrate many of the communications services required by the user (i.e., voice, data, moving images, etc.) have recently emerged in communications networks. Information from a large number of calls is transported via fixed-sized packets (or cells in ATM terminology) and then multiplexed onto a single medium whose capacity (in bits per second) is either expressed in a physical size (i.e, link capacity) or a virtual quantity (i.e. effective bandwidth allocation). At connection set-up, the user declares a set of traffic parameters and a required Quality of Service (QoS) from which the carrier must decide whether or not it is possible to establish a path of sufficient bandwidth between the sender and receiver that will satisfactorily accommodate the user's requirement, Connection Admission Control (CAC) is the traffic control function within the network that performs this decision CAC typically depends on a resource allocation algorithm that determines if there are sufficient network resources (including bandwidth and buffer memory) throughout the communication path. In the event of insufficient resources the connection is denied.
Several prior art CAC models have been developed for determining solutions to the effective bandwidth (or effective cell rate) in large network traffic, however the software implementation of these algorithms has generally been too complicated to meet the real-time requirement for the bandwidth solution and the CAC “go
o-go” decision. In order to reduce computation time, many network designers have resorted to simplified approximations such as the “on-off” fluid flow approximation used in U.S. Pat. Nos. 5,862,126 and 5,917,804 (Shah et al, Jan. 19, 1999 and Jun. 29, 1999). Others have chosen empirical models such as the fuzzy logic decisions used in U.S. Pat. No. 5,341,366 (Soumiya et al, Aug. 23, 1994), and the methods for controlling priority levels in both U.S. Pat. No. 5,267,232 (Katsube et al, Nov. 30, 1992), and Canadian Patent Application No. 2,208,096 (M. Aida, Dec. 18, 1997). The bandwidth solutions developed in all of the known prior art CAC models, whether complex solutions or simplified approximations, are implemented in software only.
Other prior art schemes are described in references [1] to [7] listed at the end of this section. All such schemes are relatively complex in one or more of the following aspects
(a) Computation Speed
The CAC algorithms described in references [1], [3] and [5] are too complicated for real-time applications, such as: Terabit switch/router designs or Low Earth Orbiting satellite access/switching applications, where a relatively large amount of connections need to be processed or handed-off within a few seconds. In such real-time applications, a faster low-level CAC method that would be more suitable for hardware implementation is desirable.
(b) Robustness
When the network is down for some reason, the CAC solutions described in references [1], [3] and [5] may not offer sufficient robustness to recover the same connection on a link due to their complicated method for calculating the effective cell rate (ECR).
(c) Flexibility
As the Internet market grows, major carriers are paying more and more attention to fractal (self-similar) traffic, in addition to the non-self-similar traffic. References [1] and [5] describe a CAC implementation for non-self-similar cases only. Reference [3] describes a case for a self-similar application, however, neither this reference nor any other known report has described the implementation of self-similar cases. Given that data and video traffics are self-similar in nature, as shown in reference [3], and that these traffics are expanding at a considerable pace, there is clearly a need for a CAC implementation that handles both self-similar and non-self-similar traffic at the same time.
(d) Reliability
Careless (or malicious) users may, inadvertently or deliberately, provide a set of traffic parameter values that could render a complicated CAC algorithms invalid, possibly causing the processor performing the computation to crash. In this respect, the complexity of the CAC solutions as described in references [1], [3] and [5] may not permit the system to be sufficiently reliable for mission-critical applications such as telebanking and telemedicine.
(e) Accuracy
The Average Burst Size (ABS) is a traffic parameter that neither the ATM Forum Specifications described in reference [4], nor other known prior art CAC solutions have taken into account. Conventional CAC methods assume that the ABS and the Maximum Burst Size (MBS) are relatively the same, which is not accurate. As a result of this assumption, present CAC solutions based solely on the input descriptor MBS tend to over-estimate the effective bandwidth, leading to low bandwidth and buffer efficiency. It is desirable to have a CAC implementation that takes both ABS and MBS into account to more effectively remedy this problem.
(f) Automation
Existing CAC solutions such as those described in references [1] and [5] rely on complementary manual tuning of the CAC formula by a trained network operator. This manual operation is not a cost-effective approach to network management. It is therefore desirable to have a more cost-effective self-tuned CAC implementation.
Prior Art References
[1] Harry G. Perros and Khaled M. Elsayed, “Call Admission Control Schemes: A Review,”
IEEE Communications Magazine
, November 1996.
[2] Mehrvar, H. R. and Le-Ngoc, T., “Estimation of Degree of Self-Similarity for Traffic Control in Broadband Satellite Communications,”
CCECE
'95, Montreal, September 5-8, (1995).
[3] I. Norros, “On the use of Fractional Brownian Motion in the Theory of Connectionless Networks,”
JSAC
, Vol. 13, No. 6, 1995, pp. 953-962.
[4] ATM Forum,
UNI
3.0
Specification
, 1993.
[5] R. J. Gibbens and P. J. Hunt, “Effective Bandwidths for the Multi-type UAS. Channels”
Queueing Systems
9, 1991, pp. 17-28.
[6] A. G. Greeberg, R. Srikant, W. Whitt, “Resource Sharing for Book-Ahead and Instantaneous-Request Calls”
IEEE/ACM Trans. On Networking
, pp. 10-pp22, February, 1999.
[7] Y. Chen, Z. Deng, and C. L. Williamson, “A Model for Self-Similar Ethernet LAN Traffic: Design, Implementation and Performance Implementations”,
University of Saskatchewan, Dept. of Computer Science, working paper
, 1997.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an improved apparatus and method for Connection Admission Control (CAC) solution, that solves the self-similar implementation problem in order to satisfy both fractal (self-similar) and non-self-similar traffic requirements in emerging broadband ISDN networks, such as virtual satellite networks and new internet protocol designs.
It is another object of the invention to simplify and reduce the mathematical calculations of the CAC solution, thereby minimizing the computational time to allow for a real-time implementation.
It is a further object of the invention to provide a minimum hardware implementation of the CAC solution that uses logarithmic operations in a pure additive/subtractive process to speed up the CAC computation at a real-time rate unmatched by traditional software approaches.
It is another object of the invention to provide a hardware implementation that permit
Duan Fengchun
Huang Jun
Chin Wellington
Drinker Biddle & Reath LLP
Fox Jamal A.
Spacebridge Networks Corporation
LandOfFree
Method and apparatus for connection admission control in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for connection admission control in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for connection admission control in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3105684