Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
2000-07-13
2004-04-27
Kizou, Hassan (Department: 2162)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C370S252000, C370S473000
Reexamination Certificate
active
06728270
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates in general to the processing of packet data traffic in a communications system, and in particular to scheduling of data packets and admission control.
BACKGROUND OF THE INVENTION
From the prior-art, there are two concepts known for the provision of quality of service in a packet oriented communications network.
One concept is the so-called Integrated Service Concept that is based on the reservation of resources for dedicated data packet streams. For the reservation of resources peer-to-peer signalling of requirements is needed before a transmission of payload data. All network nodes along a transmission path are requested to reserve corresponding resources. The Integrated Service Concept is described in: D. Clark et al., Supporting Real-time Applications in an Integrated Services Packet Network: Architecture and Mechanisms, Proceedings SIGCOMM 92, August 1992.
A known signalling protocol is the so-called Resource Reservation Protocol RSVP, that is described in: L. Zhang et al., RSVP: A New Resource Reservation Protocol, IEEE Network Magazine, September 1993. RSVP is a receiver-oriented simplex protocol that reserves resources in one direction along a communications path. The receiver of the data flow is responsible for the initiation of the resource reservation.
The so-called TENET scheme is similar to the Integrated Service Concept (see D. Ferrari et al., A Scheme for Real-Time Channel Establishment in Wide Area Networks, IEEE Journal on Selected Areas of Communications, Vol. 8, pp. 368-379, 1990). It provides guaranteed delays for real-time services in a packet-switching wide-area network and allows bandwidth allocation per packet flow. In this scheme, clients declare their traffic characteristics and performance requirements at the time of communications channel establishment. After a channel is established, data packets are scheduled based on deadlines in the hosts and in the network nodes. In order to do so, a scheduler maintains at least three queues: one for deterministic packets, one for statistical packets, and the third for all other type of packets and all local tasks.
Another concept for the provision of quality of service is the so-called Differentiated Service Concept, which aims to simplify the classification and scheduling of packets with quality of service requirements by the use of priority bits in a protocol header. All packets belonging to a specific quality of service class will be marked with a corresponding priority bit combination in the Internet Protocol header. The packet flows are marked with the priority bits and policed according to a Service Level Agreement at the edge of the network. In the interior of the network, the packets are scheduled based on the priority bits. For the Differentiated Service Concept reference is given to S. Blake et al., An Architecture for Differentiated Services, IETF RFC 2475, December 1998.
Admission control of data packet streams and scheduling of the transmission order of data packets in order to minimise deadline violations of real-time or near real-time multimedia applications are important tasks in communication networks containing bottlenecks. In the following, the term ‘real-time’ should be understood also as ‘near real-time’ or, in general, as ‘time-critical’. In heterogeneous networks, bottlenecks appear at network boundaries where traffic from one network is passed to another.
Certain real-time deadlines are usually not passed if only one data packet is delayed. Instead, usually a set of data packets spans up a synchronisation entity that has to arrive at the destination, e.g. to display a part of a multimedia output in time.
Application and intermediate nodes become more and more intelligent and allow for multimedia adaptation. This means that the amount of data bandwidth needed for the transmission of a certain multimedia object or presentation is not fixed. The adaptation process can be done by several means like dropping packets of lower priority, hierarchical multimedia coding, adaptive application, bandwidth adaptation gateways or even active networks that deploy processing elements within network nodes. Thus, in case of congestion, the bandwidth can vary in between a certain interval. The applications or the network itself may fulfil the needed adaptation task to vary the actual transmission rate in order to prevent deadline violations.
The existing admission control and scheduling schemes allow only for low bandwidth utilisation by means of peak rate allocations and delay guarantees that are given for bursty packet sources. Improved schemes are reaching a higher bandwidth utilisation by applying measurement algorithms that predict the actual available bandwidth by measuring the past bandwidth usage. However, measurement based algorithms provide only weak guarantees and only work efficient with a high amount of statistical multiplexing. Especially wireless networks are usually restricted in bandwidth capacity and thus, measurement based and deterministic admission control schemes have poor performances. One reason is that the existing schemes for packet scheduling are treating each packet in the same way. They are not able to detect past deadlines that are relevant for the receiving applications and thus, they cannot trigger processes that turn the current system into an error-free state.
Traditional schemes classify each packet stream into a priority class. In the Integrated Service Concept this priority class belongs to an average delay that packets of a particular stream will experience. In the Differentiated Service approach, this priority class belongs to a traffic type that should have less delay than other ones. The priority class is usually bounded to an average delay, the packet is expected to experience when admitted to that priority class. When considering multimedia streams with variable bit rates (like video streams), the packets of a single stream will not have the same delay requirements over the time. Instead, a scheduling by determination of a delivery deadline for each individual packet as proposed by the present invention provides a better performance than a priority based scheduling.
Therefore, it is an object of the present invention to provide an improved approach to packet oriented communications systems that overcomes these and other problems, in particular to allow a deadline-oriented scheduling of data packets carrying real-time data traffic.
The solution described in the invention is advantageous because of assignments of individual delivery deadlines to payload data packets that are subject to real-time processing. This is especially useful for data packets of a single multimedia stream with variable bit rates, due to different delay requirements that the packets have over the time. The calculation of a delivery deadline for each individual payload data packet allows an optimal scheduling of the payload data packet via a time-stamp based queue. Advantageously, synchronisation control parameters necessary for determination of deadlines are read from a synchronisation control packet SCP that is embedded in an incoming data packet stream. This guaranties an easy processing of control parameters and avoids additional signalling and complex protocol structures.
In a preferred use, apart from synchronisation control parameters, parameters like a packet error rate Pj and a bit rate Rj of a transmission channel for data packets are incorporated in the deadline calculation. In this way, the current system characteristics can be easily taken into account, which results in an improved performance.
It is further advantageous to perform an admission control before delivery deadlines are calculated for payload data packets at a packet scheduler. The decision to admit a real-time processing of a sub-stream of data packets depends on a minimum throughput requirement given by admission control parameters, which can be easily read from an admission control packet ACP. Advantageously, delivery deadline violations for data packets due to thr
Fasbender Andreas
Meggers Jens
Kizou Hassan
Pezzlo John
LandOfFree
Scheduling and admission control of packet data traffic does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling and admission control of packet data traffic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling and admission control of packet data traffic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3192773