Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-01-26
2001-02-13
Vu, Huy D. (Department: 2735)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S229000, C370S389000, C370S400000, C370S438000
Reexamination Certificate
active
06188698
ABSTRACT:
TECHNICAL FIELD
The present invention generally relates to multimedia networks and more particularly to a packet/cell queueing and transmission scheduling system for transmitting packets from applications of different types over the same network components, according to multiple criteria in order to ensure a suitable quality of service for a wide range of applications.
BACKGROUND ART
The emergence of high speed networking technologies such as ATM cell-based technology, now makes possible the integration of multiple types of traffic like speech, video and data over the same communication network. The communication circuits which may be shared in such network include transmission lines, program controlled processors, nodes or links, and data or packets buffers. An access node in such network should thus be designed for supporting the access of the user existing communication equipments with their corresponding protocols such as X.25, APPN, FDDI . . . as well as for accommodating new equipment supporting ATM. Accordingly, it is essential to know the different requirements of each traffic in order to optimize the different processes. Real-time traffics have more constraining requirements than non-real-time ones i.e. end-to-end delays and jitters. It is necessary to be able to give priority to the real-time packets in order to minimize these delays. Meanwhile, the packet loss must be guaranted both for real-time and non-real-time applications which have reserved bandwidth in the network, while it is not mandatory for non-reserved type of traffic.
Therefore, it is important to provide the network components (i.e. nodes or links) with mechanisms that control the priority of the packets, and process them in order to guarantee the desired quality of service (QOS) to their corresponding connections. It is also important to offer the same service to connections having the same QOS requirements by providing them with a fair share of the network transmission capacities.
Another important objective in multimedia networks is to simplify the configuration and the management of the networks. One common case is to provide a certain flexibility in the definition of the connections by allowing a connection to send a certain amount of excess traffic over the network. This provides an error margin in the network configuration and allows a better resources utilization. In the other hand, well-behaved connections whose traffic profile remains within their contract (based on traffic descriptors) should not suffer from misbehaving connections that send excess traffic. Therefore, the behaviour of a connection that is, the adequacy between the connection's traffic contract and its actual traffic, appears to be also an important criterion to take into account when controlling the transmission of data over the network links.
Traditionally in high speed networks based on bandwidth reservation, there are dedicated functions generally called buffer management and scheduling functions implemented at node or trunk level, and which are responsible for transmitting the packets from one node to another while ensuring that each connection gets the quality of service it has been guaranteed. In a multimedia network that handles data of multiple traffic profiles, a proper buffer management and packet transmission scheme is mandatory for ensuring efficiently the connections' quality of service.
In the prior art, there are many implementations of buffer management and transmission scheduling schemes. Some rely on priority scheduling (e.g. real-time, non-real-time queueing), which resides in implementing priority queues at link level and scheduling the transmission of packets with regard to the priority of the queue from which they originate. With this type of transmission scheme, a connection that sends low priority traffic would be penalized if it shares the (virtual) channel with connections that send high priority traffic.
Other transmission scheduling techniques rely on a so-called fairness among connections. Generally, one queue per connection is implemented and a scheduler transmits packets from the queues in a fair way, using for example a known round-robin scheduler. With this type of scheme, the traffic profile of a connection (e.g. real-time, non-real-time) is usually not considered, which may raise problems of QOS guarantee when connections send traffic of different types.
Typically, transmission scheduling schemes do not use the behaviour of a connection as transmission criterion. This aspect is generally treated by the network congestion control function and more particularly by the traffic policing process which is typically performed at the network access points. One well-known congestion preventive rate-based access control technique is based on the so-called buffered leaky bucket scheme. Some of these leaky bucket congestion control schemes involve the marking of packets entering the network: packets are marked with one of two “colors”, red and green. Green packets represent traffic that is within the connection's reserved bandwidth, and are guaranteed a prespecified grade of service based on some level of delay and loss probability within the network. Red packets, on the other hand, represent traffic sent over and above the reserved rate and can be viewed as an emergency relief mechanism coming to play during an overload period where the instantaneously offered traffic is above the reserved bandwidth. In other words, the amount of traffic in excess of the allocated bandwidth is marked red and sent into the network, instead of being dropped at the source. Red packets allow a source to exploit any unused network bandwidth in order to improve the efficiency of the statistical multiplexing.
Therefore, In multimedia networks, a queueing and transmission scheduling system that provides fairness among connections as well as relying on connections priority and behaviour would ensure more efficiently that each connection gets the quality of service (QOS) it has been guaranteed whatever its traffic profile is. Accordingly, the invention described herein relates to a queueing and scheduling mechanism for transmitting packets sent on a transmission medium in a multimedia network node, and is particularly concerned with effectively providing a suitable quality-of-service for a wide range of traffic applications.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a switching node in a multimedia network that includes a flexible and efficient packet queueing and transmission scheduling system and method.
It is a further object of the invention to provide a queueing and transmission scheduling system and method for use in a multimedia network, that ensures a suitable quality of service for a wide range of applications.
It is still another object of the invention to provide a queueing and transmission scheduling system and method in a multimedia network, that relies on multiple criteria such as connection priority, connection behaviour and fairness.
In brief, according to the invention, these and other objects are accomplished by providing a system and method of packet queueing and transmission scheduling for use in a switching node of a high speed packet switching network, the switching node having a plurality of input and output links for receiving and transmitting packets originated from a plurality of connections from a wide range of applications. The system comprises:
means for classifying each of the plurality of connections as red or green depending on whether said each connection transmits excess traffic or not, so as to achieve a behaviour classification of said plurality of connections;
means for temporarily storing said packets originated from said plurality of connections into a plurality of queues referred to as connection queues, wherein there is one queue per connection and wherein all packets originated from one of said connections are stored into the same queue;
means for determining for each of said connections a priority class indicative of the qual
Berthaud Jean-Marc
Enger Marcus
Fichou Aline
Foriel Pierre-Andre
Galand Claude
Cesari and McKenna LLP
Cisco Technology Inc.
Phan M.
Vu Huy D.
LandOfFree
Multiple-criteria queueing and transmission scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple-criteria queueing and transmission scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple-criteria queueing and transmission scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2590457