Scheduling and admission control of packet data traffic

ES 2 394 623 T3

DESCRIPTION

Admission control and planning of packet data traffic.

Field of Invention

The present invention relates generally to packet data traffic processing in a communication system, and in particular to packet data scheduling and admission control.

Background of the Invention

From the prior art, two concepts are known for the provision of quality of service in a packet oriented communication network.

One concept is the so-called Integrated Services Concept, which is based on reserving resources for dedicated continuous streams of data packets. For resource reservation, requirement signaling is necessary between peer entities prior to a payload data transmission. All network nodes along a transmission path are requested to reserve corresponding resources. The Concept of Integrated Services 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 well-known signaling protocol is the so-called RSVP Resource Reservation Protocol, which is described in: L. Zhang et al., RSVP: A New Resource Reservation Protocol, IEEE Network Magazine, September 1993. RSVP is a simplex oriented protocol. to receivers, which reserves resources in one direction along a communications path. The receiver of the data flow is responsible for initiating the resource reservation.

The scheme called TENET is similar to the Integrated Services 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 a 379, 1990). It provides guaranteed delays for real-time services on a packet-switched wide area network and enables bandwidth allocation per packet stream. In this scheme, customers declare their traffic characteristics and performance requirements at the time of communication channel establishment. After a channel has been established, data packets are scheduled based on deadlines at the hosts and at the network nodes. To do this, a scheduler maintains at least three queues: one for deterministic packages, one for statistical packages, and the third for all other package types and all local tasks.

Another concept for the provision of quality of service is the so-called Differentiated Services Concept, which aims to simplify the classification and planning of packets with quality of service requirements through the use of priority bits in a protocol header. All packets belonging to a specific QoS class will be marked with a corresponding combination of priority bits in the Internet Protocol header. Packet flows are marked with priority bits and monitored according to a Service Level Agreement at the edge of the network. Inside the network, packets are scheduled based on priority bits. For the Concept of Differentiated Services, reference is provided S. Blake et al., An Architecture for Differentiated Services, IETF RFC 2475, December 1998.

The admission control of continuous streams of data packets and the planning of the order of transmission of data packets in order to minimize violations of deadlines of multimedia applications of real time or near real time are important tasks in the communication networks that contain bottlenecks. Hereinafter, the term "real time" should also be understood as "near real time" or, in general, as "time sensitive". In heterogeneous networks, bottlenecks appear at network boundaries where traffic from one network is passed through to another.

Typically, certain real-time deadlines are not passed in case only one data packet is delayed. Instead, typically a set of data packets encompasses a synchronization entity that must reach the destination, for example, to display a part of a multimedia output in time.

The application and intermediate nodes are becoming increasingly intelligent and allow multimedia adaptation. This means that the amount of data bandwidth required for the transmission of a certain multimedia object or presentation is not fixed. The adaptation process can be performed by various means such as lower priority packet skipping, hierarchical multimedia encoding, 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 within a certain interval. Applications or the network itself can fulfill the adaptive task required to vary the actual transmission speed in order to avoid deadline violations.

Existing scheduling and admission control schemes allow only low bandwidth utilization through peak rate assignments and delay guarantees that are provided for

ES 2 394 623 T3 burst packet sources. Improved schemes are achieving higher bandwidth utilization by applying measurement algorithms that predict actual available bandwidth by measuring past bandwidth usage. However, measurement-based algorithms provide only weak guarantees and only work effectively with a high amount of statistical multiplexing. In particular, wireless networks are typically limited in bandwidth capacity, and therefore deterministic, metric-based admission control schemes perform poorly. One reason is that existing package planning schemes treat each package in the same way. They cannot detect past deadlines that are relevant to receiving applications, and therefore cannot trigger processes that convert the current system to an error-free state.

Traditional schemes classify each stream of packets into a priority class. In the Integrated Services Concept, this priority class belongs to an average delay that the packets of a particular stream will experience. In the Differentiated Services approach, this priority class belongs to a type of traffic that should present a lower delay than others. The priority class is typically tied to an average delay the packet is expected to experience when admitted into that priority class. When considering multimedia streams with varying bit rates (such as video streams), the packets in an individual stream will not exhibit the same delay requirements over time. In contrast, a scheduling by determining a delivery deadline for each individual package, as proposed by the present invention, provides better performance than a scheduling based on priorities.

Liebeherr et al. describe in "Work conserving vs, non-work conserving packet scheduling: An issue revisited", 1999 7th International Workshop on Quality of Service, London, UK, May 31 to June 4, 1999, ISBN: 0-78035671-3, a scheduler that uses a tunable speed control mechanism. The scheduler is based on readiness, where each packet is timestamped with a deadline that is set equal to a sum of its arrival time and a linked delay.

Therefore, it is an object of the present invention to provide an improved approach for packet-oriented communication systems, which overcomes these and other problems, in particular to allow time-bound planning of data packets carrying data traffic. in real time.

This objective is achieved by the teachings of the independent claims. Other preferred embodiments are given in the dependent claims.

The solution described in the invention is advantageous thanks to the assignments of individual delivery deadlines for payload data packets that are subject to real-time processing. This is especially useful for data packets of a single multimedia stream with varying bit rates, due to the different delay requirements that packets have over time. Calculating a delivery deadline for each individual payload data packet enables optimal planning of the payload data packet through a timestamp-based queue. Advantageously, from a synchronization control packet SCP which is inserted into an incoming stream of data packets, synchronization control parameters necessary for the determination of deadlines are read. This ensures easy processing of control parameters and avoids additional signaling structures and complex protocols.

In a preferred use, apart from timing control parameters, parameters such as a packet error rate Pj and a bit rate Rj of a transmission channel for data packets are incorporated into the calculation of the deadlines. In this way, the characteristics of the current system can be easily taken into account, which results in improved performance.

Furthermore, it is advantageous that admission control can be easily performed based on one or more admission control parameters R1 read from an admission control packet ACP, which is inserted in a continuous stream of data packets. A decision to support real-time processing of a continuous substream of data packets depends on a minimum throughput requirement provided by those admission control parameters. Advantageously, congestion due to throughput failures in nodes or network applications can be avoided, for the reason that data packets requiring a higher throughput than available are not supported for real-time processing. Additionally, the intake control can take into account a maximum flow parameter Rh. Therefore, the intake controller can choose a more cost-effective flow rate than the minimum required flow rate R1 for a continuous subflow of data packets, up to the maximum flow rate Rh and as a function of the available flow rate.

A network operator may charge different amounts for different throughput rates provided to the customer. In order to increase the operator's profits, said choice of a flow rate for a continuous subflow can be based on a profit function provided by an operator, said profit function indicating, for example, the cost per flow rate for the communication system, a network node or a transmission channel.

ES 2 394 623 T3

In addition, an upper throughput limit Rh can prevent buffer overflows in the communication system or the receiver of the data packet stream by ensuring that the data packets are not transmitted too quickly.

In one embodiment of the invention, it is further advantageous to perform admission control before delivery deadlines for payload data packets are calculated in a packet scheduler. The decision to support real-time processing of a continuous sub-stream of data packets depends on a minimum throughput requirement provided by admission control parameters, which can be easily read from an ACP admission control packet. Advantageously, data packet delivery deadline violations due to throughput failures can be avoided, for the reason that data packets requiring a higher throughput than available are not supported for real-time processing. In addition, unnecessary calculations of delivery deadlines are avoided.

In one embodiment of the invention, it is advantageous that the intake control takes into account a maximum flow parameter Rh. This allows the choice of a more cost-effective flow rate than the minimum required flow rate R1 for a continuous subflow, up to the maximum flow rate Rh and depending on the available flow rate.

Furthermore, an upper throughput limit Rh can prevent buffer overflows in the communication system or the receiver of the data packet stream, since it is ensured that the data packets are not transmitted too quickly.

In one embodiment of the invention, it is advantageous to reject a continuous sub-stream of data packets, which is not supported for real-time processing, and send it to the packet scheduler, as this still allows best-effort processing. In this way an omission of data packets and a corresponding loss of information can be avoided.

In one embodiment of the invention, data packets that are rejected by real-time processing are sorted in the packet scheduler into a second FIFO queue in their order of appearance. This allows best-effort processing according to a first-in-first-out strategy, for data packets from the second FIFO queue.

In one embodiment of the invention, data packets from the first EDF queue are further processed according to their delivery deadlines, and data packets from the second FIFO queue are processed according to a first-in-first-in strategy. leave. Advantageously, this triggers the additional processing of data packets under the established quality of service requirements.

In one embodiment of the invention, an output interface OI prioritizes data packets in the first EDF and the second FIFO queue. Advantageously, a data packet blocking in one queue can be avoided by choosing a priority strategy, which guarantees to some extent data packet reads from both queues.

In one embodiment of the invention, through a modified admission control packet, throughput capacity feedback is sent back along the transmission path of the continuous subflow of data packets. Advantageously, this allows intermediate nodes of the communication system or a traffic source to adapt the traffic to the available throughput capacities. In this way, rejections of data packets for real-time processing can be largely avoided. Using a modified admission control packet can avoid signaling overhead and complex protocol structure.

In one embodiment of the invention, timing control parameters are received from an underlying network protocol header. This enables payload encryption and authentication, and supports the use of so-called IPv4, IPv6, and IPSec Internet protocols, since the reading of timing control parameters is not prevented.

In one embodiment of the invention, deadline violations can be detected. Advantageously, this allows an activation of countermeasures to ensure the real-time processing of the data packets.

In one embodiment of the invention, an adaptation of payload data packets takes place. This allows the maintenance of delivery deadlines for data packages. It also supports efficient use of the packet scheduler and other system resources, and can avoid rejecting or skipping data packets.

In one embodiment of the invention, admission control parameters are received from an underlying network protocol header. This enables payload authentication and encryption, and supports the use of so-called IPv4, IPv6, and IPSec Internet protocols, since the reading of admission control parameters is not prevented.

ES 2 394 623 T3

In an embodiment of the invention, a network node that processes data traffic in real time further comprises a determination unit for determining a currently available throughput V, and decision means for a decision on a real-time processing of a stream of incoming data traffic. By means of the determining unit and the decision means, it is possible to perform admission control before deadlines for payload data packets are calculated in a packet scheduler. Advantageously, violations of delivery deadlines for data packets due to throughput failures can be avoided, since data packets requiring a higher throughput than available are not supported for real-time processing. In addition, unnecessary calculations of delivery deadlines are avoided.

In one embodiment of the invention, the network node further comprises a transfer unit for forwarding data packets that are admitted for real-time processing to the first EDF queue, and for forwarding data packets that are rejected for processing in real time to a second FIFO queue. This ensures that all types of traffic can be processed. Data packets rejected for real-time processing can be further processed with best-effort quality.

Additionally, an exit interface OI prioritizes data packets in the first EDF and the second FIFO queue. Advantageously, a data packet lock on one queue can be avoided by choosing a priority strategy, which guarantees data packet reads from both queues to some extent.

In an embodiment of the invention, the network node further comprises a deadline violation manager and an adaptation unit. Thus, countermeasures in opposition to delivery deadline violations can be easily activated in order to ensure real-time processing of data packets. A preferred countermeasure is the adaptation of payload data packets, which allows for the maintenance of delivery deadlines. It also supports efficient use of system resources, and can avoid data packet rejection or skipping.

In one embodiment of the invention, the network node further comprises a radio base station. In a cellular communication network, and in particular in a radio access network, the available frequencies are limited resources. This results in limited bandwidths of the communication channels. Advantageously, the present invention effectively supports the provision of quality of service to clients requesting multimedia services in real time. In particular, the radio base station can accept only those clients whose communication requests can be satisfied.

In one embodiment of the invention, a throughput capacity feedback is sent back along the transmission path of a continuous sub-stream of data packets through a modified admission control packet. Advantageously, this allows intermediate nodes of the communication system or a source of traffic to adapt the traffic to the available throughput capabilities. In this way, rejections of data packets for real-time processing can be largely avoided. Using a modified admission control packet can also avoid signaling overhead and complex protocol structure.

In one embodiment of the invention, it is advantageous to perform admission control before calculating deadlines for payload data packets. There is no need to calculate deadlines if the throughput requirements for real-time processing of a continuous sub-stream of data packets, which are provided by admission control parameters, indicate, under consideration of available throughput capacities, that these deadlines cannot be kept. Advantageously, violations of delivery deadlines for data packets due to throughput failures can be avoided, since data packets requiring a different throughput than available are not supported for real-time processing.

In one embodiment of the invention, data packets that are rejected for real-time processing are sorted into a second FIFO queue in their order of appearance. This allows simple best effort processing according to a first-in-first-out strategy for these data packets.

In one embodiment of the invention, data packets are prioritized for reading from the first EDF queue and the second FIFO queue. Advantageously, a data packet lock on one queue can be avoided by choosing a priority strategy, which guarantees data packet reads from both queues to some extent.

In one embodiment of the invention, deadline violations can be detected. Advantageously, this allows an activation of countermeasures to ensure the real-time processing of the data packets.

In one embodiment of the invention, a payload data packet adaptation is performed. This enables the maintenance of delivery deadlines for data packets, particularly in the event of congestion or traffic load peaks. It also supports efficient use of system resources, and can avoid the rejection or skipping of data packets.

ES 2 394 623 T3

In one embodiment of the invention, admission control parameters and / or timing control parameters are received from an underlying network protocol header. This enables encryption and authentication of the payload, and supports the use of so-called IPv4, IPv6, and IPSec Internet protocols, since the reading of admission control parameters is not prevented.

From the following detailed description, taken in conjunction with the figures, a method, system, and computer program of the present invention will be further understood and appreciated. The following figures are shown:

Brief description of the drawings

Figure 1a a video stream with different sync entities, Figure 1b another video stream with different sync entities, Figure 1c a data packet stream with an ACP admission control packet and control packets synchronization SCPs, Figure 2a parameters contained in an SCP, Figure 2b parameters contained in an ACP, Figure 3 tasks of an admission controller in a flow chart, Figure 4 a functional view of a package scheduler, Figure 5 tasks of a package scheduler in a flow chart.

Detailed description of the invention

Figure 1a shows a continuous flow of payload data packet traffic along a time axis t. The stream can be sent by a traffic source or an intermediate network node in a communication system, or it can be received in a network mode such as a packet scheduler or admission controller, or it can be received from an application. software such as a media viewer. The payload data packet stream consists of several payload data packets 1, 2, and 3, which are sent or received over time.

Depending on the characteristic of the payload, there are data packets that correspond to each other and that constitute a so-called synchronization entity SE. The data packets belonging to a synchronization entity SE have in common that all of them together must reach their destination within a fixed time interval, due to real-time requirements. Furthermore, each SE synchronization entity should have the property of being processed by the receiving application independently of any other packet from a successive SE synchronization entity.

When considering video communication, a synchronization entity SE could consist of one or more video frames, depending on the real-time characteristics and the playback buffer at the receiver. In connection with voice over Internet protocol streams, the synchronization entity SE could even be a single packet. In a so-called WWW World Multimedia Mesh session, the synchronization entity SE may consist of data packets representing a complete web page including all objects such as images and the structure of the document in HTML Hypertext Markup Language.

In Figure 1a, all payload data packets 1 belong to a first sync entity SE 1, all payload data packets 2 belong to a second sync entity SE 2 and all data packets 3 of payload belong to a third synchronization entity SE 3. This configuration places restrictive delay requirements with respect to overall end-to-end delays on a packet scheduler receiving the continuous stream of data packets in a communication network.

Figure 1b shows, in an alternative traffic scenario, a video stream that has two video frames within a sync entity. The first video frame comprises payload data packets 1, the second frame comprises payload data packets 2. This scenario forces the receiver to temporarily store two sync entities before playing them. In this case, the synchronization entity SE 1 overlaps with the synchronization entity SE 2.

Figure 1c shows a continuous stream of data packets with no overlapping sync entities. Certain SCP, ACP control data packets are inserted into the stream by a traffic source or an intermediate gateway. A synchronization control packet SCP precedes a synchronization entity SE, and differentiates one from another. It contains synchronization control parameters related to the successive SE synchronization entity.

In a preferred embodiment of the present invention, a traffic source additionally inserts ACP admission control packets into the packet stream. An ACP admission control package includes parameters that characterize a continuous underflow of data packets in relation to their throughput requirements for real-time processing. A continuous subflow will be interpreted as a set of data packets

ES 2 394 623 T3 succeeding an ACP admission control package to another admission control package. Alternatively, the number of data packets assigned to an admission control packet could be included in the admission control packet as a control parameter that defines the continuous sub-stream by its length.

If real-time data traffic and other data traffic such as best effort traffic are mixed in a stream of packet data, the identification of payload data packets as belonging to a certain synchronization entity SE or a certain continuous subflow can be preferably used through a number that is included as a parameter control in the synchronization control packet SCP or in the ACP admission control packet and defining the length of the synchronization entity or continuous subflow.

ACP admission control packets can be sent repeatedly while maintaining data transmission. In this way, a traffic source can use ACP admission control packets to signal changes in the use of its resources.

In another embodiment of the present invention, the admission controller sends back a modified ACP admission control packet to the packet source. This mechanism enables intermediate nodes or the packet source to react to negative admissions of data packets for real-time processing.

ACP admission control packets can also be repeated at arbitrary time intervals, in order to update resource reservations. The ability to send them repeatedly is especially useful in networks where the routing path of a multimedia stream may change, such as in the fixed network portion of a mobile communication network. A copy of the actual ACP admission control packet can then be forwarded from dedicated control nodes, or it can even be repeated within the stream of packets at regular time intervals to allow control nodes to bottleneck. the determination of actual resource requirements.

In another embodiment of the present invention, the timing control parameters and the admission control parameters are inserted from the traffic source or an intermediate gateway into the header of an underlying network protocol. This is especially useful when using payload authentication and encryption mechanisms. Internet protocols such as IPv4 and IPv6 allow the insertion of an optional header extension that can carry admission control and timing control parameters. When the so-called IPSec protocol is used, the Internet Protocol header is authenticated by means of an additional authentication header. Therefore, the reading of the intake control and timing control parameters is not prevented.

In another embodiment of the present invention, an intermediate station between the source and the packet scheduler has key knowledge of the transmitted data packet stream. It is a trusted device for the end user, such as a mobility gateway maintained by a network provider. In this case, a special header and payload encryption are used for transmission over a wireless link when so-called IP tunneling takes place between communication participants.

The present invention, with the help of the synchronization information contained in the synchronization control packet SCP, allows the determination of an individual delivery deadline for each payload data packet of a synchronization entity SE, for example, in a package planner. Figure 2a shows a preferred embodiment of the content of a sCp timing control packet. It contains as parameters a number N of packets belonging to its referred synchronization entity SE, a total size S of all the payload data packets of this synchronization entity SE and a maximum transmission time I, in which the full SE sync entity must go through the packet scheduler.

Alternatively, the maximum transmission time I could be defined as the time in which the synchronization entity SE must reach its final destination. In this case, the packet scheduler would be allowed to use only a part of this transmission time for the processing of the synchronization entity SE.

Additionally, the synchronization control packet SCP may contain an identifier ID that refers to the admission control packet ACP belonging to it. This identifier can be used to verify if a sync entity belongs to a certain continuous subflow.

Additionally, the timing control packet may contain other parameters, which support the identification of payload data packets as belonging to its control parameters. This could be necessary if the order of transmission of data packets were to be changed during their transmission from a traffic source or an intermediate network node to the packet scheduler, to another network node, or in general to a device or a network node. application, which uses the timing control parameters.

Assuming that the transmission order of the data packet is not changed, the packets belong to a specific synchronization entity SE when succeeding a synchronization control packet SCP and do not have a

ES 2 394 623 T3 index greater than N, starting from the first packet that directly succeeds the synchronization control packet SCP. In order to distinguish SE synchronization entities belonging to different packet flows, data packets can also be marked with a flow label by means of an underlying network protocol. The synchronization control packet SCP carries the same flow label as its data packets.

In general, a synchronization control packet SCP contains parameters necessary to determine delivery deadlines for payload data packets belonging to a synchronization entity SE. Depending on the type of traffic and the corresponding applications, in a certain embodiment of the present invention, the synchronization control packet SCP may contain only one parameter such as an absolute or relative time value for a time limit. In another scenario, a synchronization control packet may contain additional control parameters used, among other aspects, for a redistribution of the order of data packets. Therefore, the content of the synchronization control packet SCP, as shown in Figure 2a, should only be interpreted as one possible embodiment.

Figure 2b shows a preferred embodiment of admission control parameters contained in an ACP admission control packet. An ACP admission control packet generally contains throughput parameters that characterize throughput requirements due to real-time constraints for processing a continuous sub-stream of data packets by a packet scheduler. A flow requirement in the sense of the present invention can be either a fixed requirement or an average requirement, and can be provided either by fixed flow rate parameters or by average flow rate parameters.

Parameter R1 provides the lowest required flow rate that is necessary for real-time processing of the continuous subflow. If this minimum requirement cannot be met, the continuous subflow must either be rejected for real-time processing, or it must be processed under a best effort strategy. For example, a mobile terminal, through this parameter, could request certain data throughput conditions to be provided by the radio communication base station of the access network. The radio base station then decides whether the mobile station can be accepted as a client.

Additionally, by means of an optional parameter Rh a higher desired flow can be requested. This allows the intake controller, or in general a network node or an application, to choose a flow rate within the given range of minimum required flow R1 and maximum desired flow Rh. Such a choice could be based on a gain function provided by a network operator, for example a linear gain function indicating cost or benefit per throughput, or it could be based on other cost estimates. Said choice of a certain throughput according to a gain function could also influence one or more continuous sub-streams of data packets, or general communications connections, that have already been supported by the admission controller for real-time processing. in the packet scheduler, each with a certain throughput. Their flow rates could be reduced in order to increase the flow rate that is available for a continuous subflow, or in general a communications connection, that is currently under the intake process by the intake controller. Therefore, the profit for a network operator can be increased by satisfying the most valuable flow requirements from a monetary point of view up to the higher flow value Rh.

Also, the Rh limit of the data throughput might be required due to buffer limitations or processing speed restrictions in the data packet destination application. Exceeding the maximum data throughput condition could cause, among other things, buffer overflow errors or rejection of payload data packets at the receiver site.

Another optional parameter is a maximum scheduling tolerance D for use in case of payload data packet delivery deadline violations. Parameter D provides the tolerance by which either a single payload data packet, or a sync entity, or the entire continuous subflow could be delayed.

Furthermore, an optional type parameter T characterizes the type of data traffic, eg MPEG, Voice over IP or others. According to the type of traffic, a packet scheduler can select an appropriate adaptation method for payload data packets in case of deadline violations.

Additionally, the ACP admission control packet may contain an identifier ID that will be used to identify timing control packets that belong to the streaming subflow controlled by the ACP admission control packet.

Additionally, the admission control packet may contain other parameters, which support the identification of data packets as belonging to it. This could be necessary if the order of transmission of data packets were changed during their transmission from a traffic source or an intermediate network node to the packet scheduler, a network node, or in general, to the device or application that uses admission control parameters.

ES 2 394 623 T3

Figure 3 describes, in a preferred embodiment of the present invention, the admission control. An ACP admission control packet is received at an admission controller 10, or in general, at a network node or an application. The ACP admission control packet refers to a successive continuous subflow carrying data traffic in real time. The intake controller reads intake control parameters R1, Rh, T from the intake control package ACP 20. In one embodiment, the controller reads only the minimum flow parameter R1. In another embodiment, shown in Figure 3, the controller reads the three parameters R1, Rh, T.

The admission controller then determines the currently used throughput Vc in the controller 30. This can be done, among other things, by counting a number of bits that are currently transmitted by the admission control per unit time. In particular, the currently used throughput measurement could take into account only real-time data traffic, since the delivery of other types of traffic can be easily delayed without any violation of time constraints. In the latter case, the packet scheduler could provide the currently used throughput parameter Vc, since the packet scheduler knows the type of traffic currently being processed.

In the next step 40, the intake controller determines the available flow rate V by calculating the difference between the maximum available flow rate Vmax in the controller and the currently used flow rate Vc. The admission controller knows the maximum throughput capacity Vmax either as a set value, from a look-up table, by messaging channel measurements or by request.

The controller then compares the available flow rate V with the required flow rate R1 50. If the available flow rate V is greater than or equal to the required flow rate R1, the controller can support real-time processing of the data packet continuous sub-stream that belongs to to the ACP admission control package. In the embodiment shown in figure 3, the intake controller further calculates a minimum M of the available flow rate V and the maximum desired flow rate Rh 60. In the next step 70, the intake controller chooses a more valuable flow rate for the continuous subflow from a range provided by the minimum required flow R1 and by the minimum M. This can be done by a choice according to a gain function provided by a network operator, eg a linear throughput benefit function.

In another embodiment, the controller could preliminarily choose a monetarily valuable flow rate from the range provided by the minimum required flow rate R1 and the maximum flow rate Rh. If the chosen throughput value is not available, the controller can trigger an adaptation of continuous subflows that have already been supported for real-time processing in the packet scheduler in order to make that chosen throughput value available. A packet scheduler 80 is sent data packets from a continuous sub-stream that has been supported for real-time processing. The information, if supported for real-time processing, can be provided from the admission controller to the scheduler either through signaling or through the use of a dedicated transmission channel or a dedicated port in the packet scheduler, reserved for real-time traffic. If a throughput rate has been chosen, it can be communicated to the packet scheduler or an exit interface OI in a similar manner in order to be considered for further processing of the continuous sub-stream.

Data packets in a streaming substream that has not been supported for real-time processing are rejected. One way of doing this rejection is the omission of data packets by the admission controller with or without subsequent notification to another participant such as the traffic source, an intermediate gateway or the receiver. One form of notification may be to send from the admission controller a modified ACP admission control packet containing a negative acknowledgment, although other signaling mechanisms could also be used. Alternatively, data packets that are subject to rejection can be temporarily stored, and a negotiation with the sender (traffic source or gateway can be initiated (for example, through an exchange of admission control packets). intermediate) on flow requirements. In another embodiment of the invention, data packets of a continuous sub-stream are sent to a packet scheduler for regular processing rather than real-time processing. This is followed by regular processing, for example a best effort approach or a FIFO (first in-first out) strategy . The information, if the data packets that are sent to the packet scheduler are supported for real-time processing, is provided, as described above, to the scheduler either through signaling or through the use of a channel. transmission channel or a dedicated port, for this transmission.

In the embodiment of the present invention shown in FIG. 3, the feasibility of an adaptation of data packets that are currently scheduled for real-time processing in the packet scheduler and that occupy the currently available throughput Vc is checked 90, and If feasible, it is executed to increase the available throughput V in the packet scheduler 110. If adaptation is not feasible, the continuous subflow is eventually rejected 100.

An adaptation of payload data packets that are currently scheduled for processing in

ES 2 394 623 T3 time, for example, in a queue of the type earliest-deadline-first EDF, it can be performed, for example, or by using a different compression scheme or more effective, or by omitting certain packets or other mechanisms depending on the type of traffic. The appropriate adaptation method is chosen considering the type of data traffic T, such as reducing the resolution of an MPEG video stream, omitting some Voice over IP packets, converting 256-color images to 16-color images , and so on. Typically, these well-known adaptation methods can be performed "on the fly" and result in a higher available flow rate V.

After said adaptation, the currently used flow rate Vc is determined 120, and the available flow rate V is calculated 130. Next, a final decision is made according to the criteria described above 50 and which include the above-described choice of a value 60, 70 flow rate, on the intake 80 or rejection 100 of the continuous subflow for real-time processing.

Figure 4 shows a packet scheduler that includes an AC admission controller to admit or reject a continuous subflow of data packets for real-time processing, a first EDF queue for supported data packets for real-time processing, and a second FIFO queue for data packets to be processed according to a best effort strategy such as first in-first out. The second FIFO queue is used for data packets, which are rejected for real-time processing. Other embodiments of the packet scheduler may include more than one timestamp-based EDF queue and more than one FIFO queue, for example, in order to increase the capacity of the scheduler.

By sending a continuous substream of data packets to the first EDF queue, the admission controller supports data packets for real-time processing. The first EDF queue is time stamp based and operates according to a closest deadline first type strategy. Each data packet ordered in the EDF queue gets a timestamp, the value of which is set to a deadline for the delivery of the data packet, which can be calculated from synchronization control parameters provided by a control packet. synchronization. For reading, the EDF queue always provides the data packet with the closest delivery deadline. Therefore, the EDF queue can keep track of all delivery deadlines and corresponding data packets for direct access processing of a data packet with the closest delivery deadline, or alternatively, it can reorder the packets of payload data according to its delivery deadlines after each new data packet transmitted to the EDF queue in order to provide, in a kind of sequential processing, always the data packet with the closest delivery deadline, at the exit of the EDF queue.

The packet scheduler includes an output interface OI, which prioritizes data packets contained in the queues for further processing. This comprises choosing a queue, reading a data packet from this queue, and providing the data packet for further processing. Different strategies are possible for choosing a queue, such as either always preferring the EDF queue until it is empty or until a certain threshold is reached, or a strategy that is based on a fixed rate of reads per queue , or a strategy for dynamically determining a reading speed, for example, taking into account the type of traffic T. The provision of data packets for further processing can be done by transmission of data packets over a communication channel, by polling mechanisms or others.

Figure 5 shows a packet scheduler tasks for an incoming stream of data packets that is sent from an admission controller. If continuous subflow is supported for real-time processing 210, an individual delivery deadline is calculated for each payload data packet 230. Admission for real-time processing can be acknowledged by the packet scheduler either through signaling messages received from the admission controller or through the arrival of a data packet via a dedicated communication channel. or on a dedicated port reserved for real-time traffic. In the embodiment shown in Figure 5, all data packets received in the packet scheduler and admitted for real-time processing are forwarded to EDF queue 220, and all other data packets are forwarded at 250 and they are sorted into a second FIFO queue in their order of appearance 260, which is operated according to a best effort strategy.

The packet scheduler reads timing control parameters from a SCP timing control packet received on the EDF queue, to compute an individual delivery deadline for each payload data packet sent to the EDF queue. In a preferred embodiment, this deadline represents the last delivery time allowed by the packet scheduler. Alternatively, the deadline could represent a late arrival time at the destination of the data packet. For the deadline, an absolute time or a timer-based time value can be used. In the next step 240, the payload data packet is ordered in the EDF queue and a timestamp of the EDF queue is set to the delivery deadline. The payload data packets arranged in the queues are prepared for further processing, eg by an exit interface OI, according to the description above.

ES 2 394 623 T3

In a preferred embodiment of the invention, the delivery deadline for an individual payload data packet is calculated from synchronization control parameters S, N and I. In addition, a number i of the packet is used for the calculation , and a current arrival time t of the package. Additionally, a packet error rate Pj and a bit rate Rj of a channel j are used in the calculation, for which the packet scheduler schedules the transfer of packets for subsequent transmission. These latter values ​​indicate how quickly the real-time queue empties.

The number i is the sequence number of a packet in a SE sync entity, with ie {1..N}. It is determined, for example, in the packet scheduler, by counting the incoming payload data packets belonging to a certain synchronization entity SE.

The time value t represents an arrival time of the individual payload data packet to the admission controller. It can be determined by the admission controller and signaled to the packet scheduler. Alternatively, a packet scheduler arrival time could be used instead, if this time is not significantly different. In the latter case, the packet scheduler determines the arrival time of the packet.

In general, the packet error rate Pj is recovered from link layer measurements. For example, in a so-called WCDMA system, the packet error rate Pj of a channel can be determined from a signal-to-noise ratio by a so-called closed-loop power control.

In other embodiments of the present invention, an error rate per time slot, per client, or per network may be used to determine the delivery deadline. In a preferred embodiment, selective repeat is used as link layer error correction.

The bit rate Rj can be determined in the admission controller or in the packet scheduler, for example, by counting the incoming bits.

In a preferred embodiment of the invention, the deadline for each payload data packet is calculated as follows:

term limits ⁼ t +1 (N - i +1) * SN * (1 - Pj) * Rj 'with ie {1..N}.

In another preferred embodiment, the packet scheduler detects delivery deadline violations for ordered payload data packets in the EDF queue by comparing its delivery deadlines with a real-time value, for example, the time that a data packet in the EDF queue, determined by using a system time. If a violation is detected, a payload data packet adaptation is performed according to the methods previously described.

Different real-time applications allow different delay tolerances. One way to carry out adaptation in this context is to use the admission control parameter D, which defines a delay tolerance for a specific continuous sub-stream of data packets. If a certain level of deadline violation is detected, an adaptive platform can degrade one or more continuous subflows into a steady state.

The present invention can be embodied in a network node of a communication system, generally comprising a packet scheduler and an admission controller. In particular, the present invention can be embodied in said network node by means of a packet error rate determination unit, which determines the packet error rate Pj of the communication channel j used for an additional transmission of packets. of data from the network node, by means of a bit rate determination unit, which determines the bit rate Rj of said channel, by means of a timer, which determines a current arrival time t of a data packet to the network node, through evaluation means, which evaluate control parameters I, S, N, Rh, R1, D, T provided by data packets control unit SCP, ACP inserted in a data packet traffic flow, by means of a calculation unit, which calculates delivery deadlines, and by means of a first EDF queue, which receives data packets to be scheduled according to their deadlines.

In another embodiment, the first EDF queue may contain a sorting unit, which sorts data packets in the first EDF queue, and which assigns calculated delivery deadlines, such as timestamps, to these data packets. The sorting unit works according to a strategy of the type nearest deadline first.

Furthermore, the network node may include a determination unit, which determines an available throughput.

ES 2 394 623 T3 currently V, for example, according to the method previously described. A decision means supports an incoming traffic flow or a continuous subflow of data packets for real-time processing after they have checked throughput requirements provided by admission control parameters and the available throughput V. Additionally, the decision means can include, for example, a gain function through a look-up table in order to choose a more valuable throughput rate from the monetary point of view, for a traffic flow or a continuous subflow. . The decision means can admit or reject a real-time processing of data packets according to the method described above.

A second FIFO queue can receive data packets, which are rejected for real-time processing. A transfer unit builds an interface for a distribution of data packets, continuous subflows or traffic flows towards the appropriate queue, that is, a rejected continuous subflow towards the second FIFO queue, and an admitted continuous subflow towards the first EDF queue.

An exit interface can prioritize all queues according to the method already described.

The network node may further include an adaptation unit for adapting at least one payload data packet. The adaptation can be done for data packets contained in the first EDF queue, or also for data packets arriving at the network node. In addition, the network node may include a deadline violation manager, which monitors delivery deadlines for ordered payload data packets in the first EDF queue, and initiates an adaptation of payload data packets in the first EDF queue. case of a violation of a delivery deadline in order to return to a stable state of the system. The adaptation can also be activated through the decision means, for example based on a profit function in order to optimize the operator's profit.

In another preferred embodiment, packet scheduling and admission control is performed at a radio base station of a packet switched radio access cellular network. Alternatively, the invention can also be used in applications run on end-user terminals.

In another embodiment, the present invention can be implemented as a computer program (also referred to as an application) or a computer program product for use with a processing device such as a computer, mobile phone, or other communication device. The delivery of the computer program to said processing device can be carried out, among other alternatives, by means of ROM read-only memory devices, the so-called CD-ROM disks, floppy disks, hard disks, through a communications medium such as a network, through a modem or by radio communication through an air interface.

In addition to normal operation of the processing device, parts of computer program software code, respectively the computer program product by its stored program, perform packet admission planning and / or control, if the computer program runs on the processing device.

In general, said computer program carries out, during execution, instructions in the sense of the above-described method for planning and / or packet admission control.

In particular, for admission control, the software code parts of the computer program, which is loaded into a memory of a digital computer and executed in the latter, first carry out the step of detecting a control packet. ACP admission in a continuous stream of data packets. This can be done by comparing a known structure of the ACP admission control packet with a structure of a currently received data packet. If an ACP intake control package is found, its Rh, R1 control parameters are read. In the next stage, an available flow rate V in the processing device is calculated as a difference from a total flow rate Vmax that can be managed by the processing device and which is provided as a fixed value to the application, and a currently occupied flow rate, the which can be provided by the processing device, for example, by link layer measurements. In a further step, the computer program compares the required flow rate R1 with the available flow rate V. If the available flow rate V is less than the required flow rate R1, the continuous subflow belonging to the intake control package ACP is rejected. In any other case, a flow rate value is chosen from a range provided by the required flow rate R1 and a second flow rate value. Said second flow value is the minimum available flow rate V and the highest desired flow rate Rh. In another embodiment, the second flow rate value is provided as previously described from the processing device by a gain function. After choosing this flow rate value, continuous subflow is supported for real-time processing.

In another embodiment, the parts of software code that perform the admission control generate a modified admission control packet, which comprises throughput capabilities such as Vmax and V of the processing device. Said modified admission control packet is sent back along the transmission path of the substream due to the reasons previously described.

ES 2 394 623 T3

Additional software code parts of the computer program or, alternatively, software code parts of another computer program perform a package scheduling run. First, a timing control packet is detected in a continuous stream of data packets. Next, its N, I and S timing control parameters are read. For each payload data packet belonging to a synchronization entity SE to which the synchronization control packet SCP refers, a delivery deadline is calculated after they are determined, for example by measurements or by routing routines. polling from the processing device, a packet error rate of a transmission channel j that is predicted for a transmission of payload data packets from the packet scheduling application, a bit rate of that channel, and a timer value t, indicating a current arrival time of payload data packets to that application. Payload data packets are arranged in the order of their deadlines in an EDF queue, which provides a timestamp for each data packet interval. Each timestamp in an interval is individually set to the calculated delivery deadline of that data packet ordered in the interval.

In another preferred embodiment of the invention, delivery deadlines are calculated only for those data packets that are supported for real-time processing.

Data packets that are rejected for real-time processing by the computer program can be sorted into a second FIFO queue in order to be processed according to a best effort strategy.

Furthermore, the computer program may instruct the processing device to perform a prioritization of both queues during packet data reads in order to facilitate processing of supported data packets for real-time processing.

In another embodiment, pieces of software code of the computer program instruct the processing device to monitor delivery deadlines of ordered payload data packets in the first EDF queue by comparing a real-time value that provides a time either absolute or relative to the delivery deadlines stored in the time indications. By doing this, the computer program can detect deadline violations. In another step, a payload data packet adaptation of the first EDF queue may be carried out, or alternatively, it may be requested from a separate application.

In order to also handle continuous streams of data packets using payload data encryption or other security mechanisms, the computer program may provide pieces of software code to read timing control parameters and / or control parameters. admission from the header of an underlying network protocol, additionally or alternatively to reading them from an SCP ACP data packet itself.

Although the invention has been described in relation to what are presently considered to be practical and preferred embodiments, it is not limited to the disclosed embodiments, but rather is intended to encompass various modifications and equivalent arrangements included within the scope of The claims.