Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-06-25
2004-02-03
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S230000, C370S231000
Reexamination Certificate
active
06687254
ABSTRACT:
FIELD OF INVENTION
The invention generally relates to a system for buffering packets in a packet-switched digital communications device. More particularly, the invention relates to a buffering system and related method for use at a queueing point in a communications device which employs a multi-class, connection-orientated, communications protocol such as an asynchronous transfer mode (ATM) communications protocol.
BACKGROUND OF INVENTION
Packet-switching communication devices which effect statistical multiplexing, such as ATM network nodes or switches, typically store in the same memory buffer all packets which need to be transmitted over a given link or line. The amount or size of the memory buffer is fixed, and thus an important issue relates to how the memory should be managed to ensure that traffic flows such as virtual circuit connections are provided with some degree of ‘fairness’ in the use of this limited resource. The situation is further complicated in ATM networks since a connection can be associated with one of a variety of traffic classes, which have varying QoS requirements, and connections within a particular ATM traffic class can be set up with various cell loss ratios (a QoS characteristic). Thus, the memory should be managed to at least provide minimum guaranteed quality of service (QoS) to the various traffic classes, as well as optimal use of the memory above and beyond the minimum QoS. It should be noted that the memory used in such devices typically tends to be very fast, and very expensive, state-of-the-art devices, thereby precluding the option of merely adding more and more memory.
A common prior art buffer management scheme is to “hard partition” the memory, by allocating one fixed portion of a memory buffer to each traffic class. Thus, when a partition group is full, cells belonging to the corresponding traffic class are discarded. While this approach is easy to implement and can operate very quickly, its primary disadvantage is that buffer space which has been allocated to other traffic classes but otherwise unused at that instant is not employed, such that an opportunity is lost to provide service to that connection above and beyond the minimum QoS guarantee. In effect, hard partitioning the memory makes it difficult to take advantage of the bursty nature of many types of digital communications.
At the other extreme, using a finitely sized memory in an unregulated manner so that it is completely shared amongst the various connections, e.g., on a first-come first-served basis, could lead to starvation situations. This is also due to the bursty nature of digital traffic, which could potentially cause temporary buffer congestion. In addition, it is not possible to prioritize memory use in such a shared buffer system to ensure that minimum QoS guarantees are met for particular types of traffic flows.
Thus, system designers often have to balance the sharing of physical resources between various types of digital traffic and the isolation thereof. On the one hand, it is desired to share the memory buffer as much as possible in order to minimize the cost thereof, on the other hand, it is desired to isolate the flow of one virtual connection or group thereof so as to prevent the impact or influence of same on other virtual connections.
SUMMARY OF INVENTION
The invention seeks to facilitate this balance between the sharing of physical memory resources amongst distinct and various types of traffic flows and the logical isolation thereof. One aspect of the invention provides a buffering system for use in a digital communications device, comprising a memory for storing messages, such as packets or cells, and a controller connected to the memory for determining whether to store or discard messages based on predetermined discard criteria. The controller also includes means for storing messages in the memory and building the requisite queueing structures. In the system, the memory is logically partitioned into plural reserved buffer spaces allocated to predetermined groups of traffic flows (hereinafter “traffic groups”) and a shared buffer space. The controller is enabled to logically fill each reserved buffer space up to a predetermined state of congestion before logically storing messages belonging to the corresponding traffic group in the shared buffer space.
In the preferred embodiment, each traffic group is associated with a bound on its utilization of the shared buffer space. The bound includes (a) a limit on an absolute number of messages that a traffic group can store in the shared buffer space, and (b) a threshold relating to a degree of occupancy of the shared buffer space as a whole. The shared buffer space becomes congested when the bound is reached or exceeded. When a reserved buffer space reaches its predetermined state of congestion and the corresponding traffic group experiences shared space congestion, incoming messages associated with that traffic group are discarded. In the preferred embodiment, reserved buffer space congestion is defined relative to a given message, thus it is possible for a reserved buffer space to be filled to capacity yet not be in a state of congestion. In this instance, the controller is enabled to store messages in the shared buffer space.
The preferred embodiment is deployed the context of a connection-orientated communications protocol, such as the ATM protocol, wherein a traffic group comprises a group of virtual circuits associated with a single traffic class (hereinafter “connection group”). (In alternative embodiments traffic groups may comprise other types of digital traffic flows, not necessarily virtual circuits or connections.) Each reserved buffer space is preferably sized to provide a minimum guaranteed quality of service to the corresponding group of virtual connections. Under such circumstances, the shared buffer space can be viewed as an idle resource and the shared space access limit and threshold described above represent mechanisms for prioritizing this resource amongst connection groups and/or their associated traffic classes.
In the preferred embodiment, each connection group is further logically subdivided into one or more sub-groups. Each such sub-group is provisioned with a size threshold for the number of messages that the connections thereof may store in the memory. The reserved buffer space may become congested when the sub-group size threshold associated with a particular message is reached. That particular message may be discarded if the corresponding connection group experiences shared space congestion, otherwise the message may be stored in the shared buffer space. Defining multiple sub-groups within a connection group facilitates the provision of various message loss ratio guarantees since the probability of message loss is dependant upon the probability that the reserved buffer space assigned to the connection group is full (which is static for all subgroups) unioned with the probability that a sub-group size threshold is exceeded (which can be selected per sub-group). Messages which are placed within the shared buffer space thus represent service above the QoS level provided by corresponding reserved buffer space.
The sub-group size thresholds of a given connection group may define in aggregate a logical memory space larger than the physical buffer space allotted to the given connection group. This further enables the buffering system to take advantage of the bursty nature of many types of digital traffic.
In the preferred embodiment, connections within a connection group are also provisioned with a size threshold for the number of messages that may be stored in the memory. The reserved buffer space may become congested when the connection size threshold associated with a particular message is reached. That message may be discarded if the corresponding connection group experiences shared space congestion, otherwise the message may be stored in the shared buffer space. The connection size thresholds facilitate the isolation of non-conformant connection. If desired, connection size thresho
Davis Tom
Giroux Natalie
Ho Esmond
Pezeshki-Esfahani Hossain
Predrag Kostic
(Marks & Clerk)
Alcatel Canada Inc.
Chin Wellington
Jain Raj
LandOfFree
Flexible threshold based buffering system for use in digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flexible threshold based buffering system for use in digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible threshold based buffering system for use in digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3282502