JP2000165447A - Method and system for scheduling data packets in a telecommunications network - Google Patents

Abstract

(57) [Summary] [Problem] A service provider and a network operator have their own Qo.
It is possible to select and configure an S target. SOLUTION: In preparing a data packet schedule in a telecommunications network, a first buffer means (16) for receiving and storing data packets representing one or more sessions is provided at a node (2) of the network. In order to avoid overflow of the first buffer means (16) during congestion, a second buffer means (18) for buffering data packets at the start of a trigger state is provided.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and system for scheduling packets in a telecommunications network, and more particularly, to meet predetermined quality service objectives set by a service provider operating the telecommunications network. A method and system for scheduling data packets in a telecommunications network being sought.

[0002]

BACKGROUND OF THE INVENTION Time-critical traffic on packet-switched networks is increasing. This traffic is traditional real-time services such as telephone, as well as video-on-
It includes new services including demand, multicast video and virtual reality applications.

There are also many non-time-critical applications, such as web browsing and file transfer, where delays still affect user perception of service quality.

For such applications to be successful, the network must have a sufficient quality of service (Qo) with respect to some quality criteria, such as packet delay and packet loss rates.
S) must be given to the user session. Q
Assurance for oS can be achieved through a combination of effective admission control and real-time scheduling.

However, the services described above typically have a relatively abrupt traffic profile, and when a session is set up, if the customer wants to transmit data over a certain network, the Cannot accurately depict the traffic profile of those customers. Therefore, unless peak bandwidth admission control is used, it is inevitable that transient congestion time will occur in the network.

A. Varma and D.M. Stilad
is, "Hardware Configuration of Fair Waiting Algorithm for Asynchronous Transfer Mode Network", IEEE Communication Magazine, No. 3.
5, pages 54-68, December 1997, a traffic scheduling system must have certain desirable characteristics summarized as follows. (A) The system needs to be able to handle individual data traffic streams individually. (B) The system must be able to provide local delay guarantees for each traffic stream, and therefore be able to provide implicit end-to-end delay guarantees. (C) There is a need to make effective use of the available bandwidth. (D) The system must be simple to implement in hardware to meet the demands of high-speed links. (E) The system needs to be scalable in that the system must be able to work with a very large number of sessions over a wide range of link speeds. (F) The system needs to be able to fairly and reasonably allocate bandwidth between traffic streams.

[0007] Many previous and current packet scheduling systems are designed to meet the above requirements, two of which are briefly described below. The first system is a first-in first-out (F
(IFO) system. In a FIFO system,
Each packet (or cell-rela)
y) In the base protocol, cells) are stored in the outgoing transmission buffer in the order of arrival of each packet or cell. The size of the outgoing buffer determines the maximum delay that a packet will experience on a particular link. If the buffer is full when the packet arrives, the packet is simply dropped. FIF
The O system is simple to implement, but because it is not possible to isolate flows and process individual traffic streams separately and is not always fair over all user sessions, real-time application Not good for support. This lack of fairness is significant because a single large volume traffic stream can generate so much traffic capacity that it severely degrades service to all other sessions of the link or network.

A second scheduling system is a fair queuing (FQ) system, which is described in the document entitled "Analysis and Simulation of Fair Waiting Algorithm", SIGCOMM'89, 1989 Minutes. Dermers, S.M. Keshav and S.M. It was introduced by Shenker. In a fair standby system, the available bandwidth is shared equally among all contention sessions, so that users with moderate bandwidth requirements do not suffer from the extreme demands of other users . As a result of the bandwidth equalization, these fairness waiting techniques typically provide satisfactory QoS for sessions that have less bandwidth requirements than fair share. The concept of fair waiting is
It is then augmented to allow for a weighted bandwidth allocation called Weighted Fair Wait (WFQ), which allows access to the more general available bandwidth by traffic streams. In this WFQ approach, the scheduler can assign different weights to each session. This approach has resulted in a wide range of modification approaches aimed at improving the fairness of the original WFQ system, minor details of implementation, or minor perceived scalability deficiencies.

However, in all of these variations, fairness is an essential goal of scheduling discipline, and the idea of fairness is given on a very small time scale. Focusing on fairness and a small time scale means that fairness is not the actual degree of QoS perceived by the user, but rather from the amount that can be measured directly by the network.
It tends to obscure the fact that it is an attempt to infer oS. It is impossible for a user to know the quality of service received by other users or the bandwidth received by other users. Therefore, fairness is not a direct measure of QoS perceived by the user. Fairness is a measure of how the network allocates resources during periods of congestion,
That is, the degree to which the user cannot directly perceive. Fairness is not a guarantee of good service quality; for example, a given link may carry two real-time sessions, both of which may simultaneously have bursts of data rate slightly more than half the link capacity . If each session is allocated half of the available bandwidth, the queue for both sessions will continue to grow until packets no longer reach within their delay limits. Therefore,
The effective throughput is zero and both users are dissatisfied. However, the system has the required Qo for a single customer.
It has plenty of capacity to provide S, which can reduce the satisfaction of other customers compared to "fair" cases.

When the load of the system is light, it is possible to make the QoS requests of all sessions normally respond. However, during periods of congestion, some sessions or all sessions will receive services that do not meet their QoS requirements. Therefore, it is necessary to determine which traffic streams should receive degraded service for loss, delay, or both. This is a unique issue with real-time bandwidth scheduling.

[0011] A more appropriate degree of QoS is considered to be the percentage of customers who are under-served at any time during a session or during congestion (this may be frustrating for the service provider). To reflect the number of potential customers). The service provider will want to minimize the number of complaints received from customers regarding the perceived QoS. Therefore, the network and the scheduling system it uses should strive to maximize the number of users who are receiving the service they like rather than strive for fairness that the customer is unaware of. This can be done by network admin to protect user QoS for ongoing sessions.
The reason for implementing session controls is analogous. However, such a schedule creation system also needs to provide a mechanism to perform fairness when the service provider considers it important. In this way, a decision on the desire for fairness in the network may be left to the service provider as a decision on business.

[0012] Scheduling systems such as FIFO and FQ do not achieve the objectives described above. In FIFO systems, due to only one session of misbehavior, all traffic streams receive poor service as measured by a fraction of the group of dropped or excessively delayed packets per traffic stream. Would. In an FQ system, if all traffic streams burst at the same time, they are all treated equally and all receive degraded service. Fairness on a very small time scale is important for real-time services such as multimedia data, MPEG video streaming and Internet Protocol (IP) telephones and non-real-time services such as file transfer (FTP) and web browsing operations (HTTP). Is not necessarily a good measure of the performance of the schedule creation system.

[0013]

It is an object of the present invention to provide a scheduling infrastructure that allows service providers and network operators to select and implement their own QoS targets. A new approach to managing transient congestion is provided by the present invention. Rather than aiming for good performance by maximizing fairness, the present invention provides an infrastructure that allows for selectable QoS approaches, including maximizing the number of good served users. Provide structure. This object is achieved by selecting a session that stands in the middle of a period of congestion, with a degraded service arrow. On a short time scale, this proposal of the present invention provides a great lack of fairness, providing very poor service for a small number of sessions and sufficient resources for the remaining sessions. However, the present invention provides a packet scheduling system that can obtain fairness over a medium time scale on the order of seconds, but still provide substantially better overall service quality than FQ systems. . The present invention supports QoS goals ranging from the traditional concept of fairness to maximizing the number of users receiving excellent service over the entire session. This is not addressed by any of the existing scheduling disciplines such as FIFO or FQ.

[0014]

SUMMARY OF THE INVENTION Accordingly, in a first aspect of the present invention, a system for scheduling data packets in a telecommunications network receives a packet of data representing one or more sessions. A step of storing in a first buffer means at a node of the network, a step of monitoring a used capacity or an occupancy rate of a packet stored in the first buffer means; To avoid overflow, trigger condition (trigger condition)
at the start of the ION)
Buffering means in the buffer means.

The trigger condition is a differential-based threshold such that a data packet is buffered in the second buffer means when the rate of increase in the amount of data stored in the first buffer means exceeds the differential-based threshold. You may. Alternatively, the trigger condition is a first condition caused by the arrival of the data packet in the first buffer means.
The first or subsequent capacity threshold of the buffer means may be exceeded. The first data packet to the first buffer means that exceeds the first or subsequent capacity threshold may be buffered in the second buffer means, if there is a subsequent arriving packet of the session to which the first data packet belongs. It may also be buffered in the second buffer means.

According to a second aspect of the present invention, in a system for scheduling data packets in a telecommunications network, a first system is located at a node of the network and receives a data packet representing one or more sessions. Buffer means and a second buffer means arranged at the node of the network, wherein the data packet is transmitted at the start of the trigger condition so as not to overflow in the first buffer means during a congestion period. There is further provided a system adapted to be buffered in a second buffer means.

According to a third aspect of the invention, data for scheduling packets representing one or more sessions in a telecommunications network according to the quality of service criteria set by a telecommunications service provider. In a packet scheduling system, first buffer means for receiving and temporarily storing data packets of one or more sessions transmitted on the telecommunication network, and wherein the first buffer means comprises a network congestion period. A second buffer means for buffering a data packet at the start of a trigger condition set in the first buffer means due to the arrival of the data packet in the first buffer means so as not to overflow during And a data packet scheduling system comprising:

[0018]

BRIEF DESCRIPTION OF THE DRAWINGS The preferred embodiments are described below, by way of example only, with reference to the accompanying drawings, in which: FIG.

FIG. 1 shows a packet switch or node 2 which forms part of a telecommunications network such as a packet switched network.
It is shown. The exchange 2 has a number of input ports 4, a number of output ports 6, an input port 4 and an output port 6.
It has a switching structure 8 connected between them. A routing processor 10 is coupled via link 12 to switching structure 8, which controls the routing or exchange of data packets between any one of the input ports 4 and any one of the output ports 6. work. Data packets entering switch 2 are received on any one of input ports 4 on input link 14. The data packet is then switched by the switching structure 8 to one of the output ports 6. The data packets are then processed according to how these input packets are handled by either the first buffer means 16 or the second buffer means 18 located at each one of the output ports 6. (This will be described later). Apart from the dropped packets, all data packets are
From each of the first buffer means 16 to the output port 6
Leave. Alternatively, the first buffer means 16 and the second buffer means 18 may be arranged at each of the input ports 4.

FIG. 2 shows a more detailed view of the first buffer means 16 and the second buffer means 18. All sessions (a session is a series of packets dedicated to one particular user for one application) are preferred, unless the system or even the network or even the switches of the network are congested. Is received by the first buffer means 16 which is a single short FIFO queue and is represented as an α queue. α
The queue length is chosen so that any packets that pass straight through the α queue will meet the most stringent delay requirements of any particular session. The length of the α queue is
Corresponds to the longest delay that can be considered "good service" in terms of delay. At the onset of congestion, if the level of the α queue rises due to the arrival of packets from a particular session and exceeds the capacity threshold T _{onset, 1} , it is determined that packets from this session contribute to the possibility of α queue overflow. , This packet from the session and subsequent packets are time stamped and buffered in a second buffer means 18 (hereinafter referred to as β queue). Exceeding the capacity threshold T _{onset, 1} represents a trigger condition such that a portion of the group of packets intended to be received in the α queue is buffered in the β queue. The β cue may be significantly longer than the α cue. Subsequent capacity threshold T _{onset, j} (j
Beyond> 1), further sessions are buffered in the β queue as well. The length of the α queue and the setting of each threshold T _{onset, j} (j> 1) are determined by the memory size in bytes. Each time the threshold is exceeded, a predetermined amount of memory in the α queue is stored and output there. It will be used by data packets that are ready just to be sent out on the link.

A wide range of possible algorithms are used to select sessions or packets of sessions to be transferred from the α queue to the β queue or buffered in the β queue before reaching the α queue depending on the desired characteristics. Is also good. Such algorithms include: (A) Random: Sessions are randomly selected from those currently in progress. While such a selection seeks to spread the performance degradation throughout their lifetime over all sessions, it is not simultaneous across all sessions.
The packets for the session may be randomly selected, for example, according to a random number generated by the system as being associated with a particular count associated with those packets. (B) Fairness: The session with the most packets in the α queue when the threshold is exceeded is selected.
Such a choice tends to penalize sessions with higher instantaneous bandwidth requirements than fair sharing.
It tries to be fairly instantaneous in deciding which sessions to penalize, but has the benefit of minimizing the number of sessions affected at the same time. In this case, each packet of each session stored in the α queue is identified, recorded by the α queue, and then counted. (C) Next packet: The session of the packet that is not already in the β queue and first exceeds the first or subsequent capacity threshold or the session of the packet that exceeds the first capacity threshold is selected. Such a choice is between fairness (the next packet arriving is likely to be from the session with the highest instantaneous bandwidth) and randomizing the disadvantageous session. Is a mixture of It has the additional advantage of being the simplest algorithm to compose. (D) History: A session that was in the β queue at a certain stage in the past but is now in the α queue is selected. Such a decision seeks to preserve the disadvantaged state of the already disadvantaged session. It seeks to minimize the amount of detriment to other sessions during the entire period, and thus maximize the number of users receiving good service over the entire session. The above algorithm can be implemented in either software or hardware.

FIG. 3 shows a number of sessions stored in the second buffer 18, ie the β buffer. A timeout threshold t _expire is set and t
All packets stored in the β queue longer than _expire are discarded. For example, in the β queue of FIG.
The oldest packets stored therein are discarded in the order entered in the β queue. If the beta queue overflows because the packets stored in the beta queue exceed its memory capacity, the system either drops newly arriving packets from various sessions, or
The oldest packet in the queue may be pushed out or discarded. The latter approach seeks to minimize the age of the packets in the queue, and thus maximize the chances that the packets sent will meet their end-to-end delay requirements.

A number of timeout thresholds t _{expire, j}
May be set according to the format of the data traffic stored in the second buffer means 18. For example, if the data traffic consists of video or voice packets, a small t _expire is set because the delayed packets of the real-time stream are of very limited value,
This only serves to delay subsequent packets. At other extremes, the packet may represent a file transfer from a server on the Internet. In this case, t _expire may be increased because the information need not be delivered in real time. Thus, smaller delays are more acceptable than packet drops that would require retransmission at a later time.

When the length or occupancy of the α queue packet decreases until the memory currently used for the α queue decreases to a specific size until the decreasing threshold T _abate , the packet of the β queue moves in the direction of returning to the α queue. . Packets from a session stop being redirected to the β queue when no packets from the session remain in the β queue. All packets moved from the β queue to the α queue are marked as “delayed”. There are many algorithms that determine which packet goes first from the β queue to the α queue,
These are: (A) FIFO: This is the simplest β queue algorithm to implement, and simply moves packets to the α queue in the order of arrival at the β queue when the length of the α queue drops to T _abate . The number of packets from each session in the β queue needs to be recorded so that it knows when the α queue stops transferring sessions. For example, the most recent session stored in the β queue, session 20, has three packets, so that the last or third packet of session 20 is α
When transferred to the queue, the α queue or first buffer means 16 will be notified that it is the last packet of the session. Therefore, any subsequent packets of session 20 that enter the α queue will only be forwarded after the first three packets of session 20 have been forwarded or output from the α queue. This record also applies to the algorithms described in (b), (c) and (d) below. (B) FIFO-FIFO: This is the case where each session transferred to or buffered in the β queue is maintained separately. α queue is T
_{When dropped} below _abate , packets from the first session in the β queue are moved to the α queue, ie, sessions are handled in first-in first-out order. Packets from this session are given priority over other sessions contained in the β queue. Within a session, packets are also transferred in a first-in, first-out order to preserve the sequence state within the session. (C) LIFO-FIFO: Each session transferred to or buffered in the β queue is maintained separately. When the α cue _drops below T _abate ,
Packets from the session most recently placed in the β queue are moved to the α queue, ie, the session is handled in a last-in first-out manner. Packets from this session are given priority over other sessions contained in the β queue. However, within a session, packets are still forwarded in a first-in, first-out order to preserve the sequence state within the session. Such an algorithm seeks to maximize the number of sessions that receive an acceptable delay performance at any time. (D) Fairness When the length of the α queue is equal to or less than T _abate , the packet is _transmitted from the β queue to the α using the fair standby method.
Transferred to queue. In this way, sessions in the β queue still use the residual bandwidth left by the session using the α queue. Such measures seek to impartialize currently disadvantaged sessions. Note that all packets leave output port 6 via the α queue.

The packet leaving the second buffer means 18 is marked so that it can be identified by another node or switch in the network. At subsequent nodes, these packets may make an initial selection of buffering to a second buffer output stage during periods of congestion. In this manner, if congestion occurs simultaneously at one or more points in the network, the network can adjust which sessions are disadvantaged. For example, if a session is buffered at one node in the second buffer means 18, the first packet or subsequent packets sent from that session to the other node (s) of the network will have its header , Which indicates that the session to which it belongs was previously buffered. Thus, other nodes can choose to continue buffering the session.

Another embodiment of the present invention is shown in FIGS. The input port 4, output port 6 and switching structure 8 are represented as in FIG. The first buffer means 16 is in the form of an output queue and receives data packets representing one or more sessions from either the second buffer means 18 or the third buffer means 19. Each of the second buffer means 18 and the third buffer means 19 of this alternative embodiment comprises a series of per-session queues 2.
Consists of one. That is, data packets from each session are received at individual queues 21 and stored there. Note that the second buffer means 18 and the third buffer means 19 are simple subsets of a single collection of percession queues 21. These queues 2
1 is a second buffer means or a third buffer means 1
9 can be dynamically reclassified as any part. Generally, the packets stored in the persession queue 19 of the third buffer means 19 are forwarded to the first buffer means 16 according to a selected scheduling discipline such as FIFO or fair standby as described above. You. The packet in the permission queue of the buffer means 19 is output from the first buffer means 16 to the output link 1.
5 is polled or read at a rate much higher than the rate at which packets are read. Next, the packet of the first buffer means 16 is sent to the output link 15 by FIFO.
They are sent out in order. Second and third buffer means 18,
19 can be configured as a logical queue. As in the first embodiment, at the onset of congestion, when the level of the first buffer means rises due to the arrival of packets from the third buffer means, one or more capacity thresholds T _{onset , j} (J> 1). If the capacity of the buffer means 16 exceeds _{the first} threshold T _{onset, 1} for a particular packet arriving at the buffer means 16, this means that the session belonging to that packet will Represents trigger conditions that are subsequently buffered in each queue. This helps to prevent the first buffer means 16 from overflowing. If the capacity threshold is subsequently exceeded, further sessions are buffered in the second buffer means 18. Buffering of data packets from various sessions may be performed according to any of the algorithms described above, ie, random, fair, next packet or history algorithms.

The timeout threshold, t _expire, is set for packets buffered in the second buffer means, so that any packets buffered longer than t _expire are discarded. Various timeout thresholds t _expire may be set depending on the type of buffered data stream such as audio, video or web browsing as in the previous embodiment.

When the length of the first buffer means has decreased to the decreasing threshold T _abate , the packet is moved from the second buffer means 18 to the first buffer means 16. This is a FIFO, FIFO-FIFO or LI
The most recent session may be performed from the buffer means 18 to the buffer means 16 by means of the algorithm described above in connection with the first embodiment, such as the FO-FIFO, but preferably using the LIFO-FIFO algorithm.
To be forwarded to Each packet in the newest session is forwarded in the order in which they entered their respective persession queue so that the sequence is maintained.

In another embodiment, the third buffer means stores the packet of the session in the persession queue 21.
May be used as a first buffer means for outputting the data directly to the output link 15 from the CPU. In this embodiment, as in the previous embodiment, no output buffer is required. The capacity threshold T _{onset, j} is based on the current logical content of the third buffer means, ie the sum of the capacity occupied by the individual sessions in each of the persession queues 21. Thus, any packet for a particular session that exceeds the threshold is to be processed according to any of the situations described above.

An experiment of a simulation is performed,
The results of these experiments are described below. FIG. 6 shows a simulation set up, wherein a number of traffic sources 1-N, indicated by reference numeral 22, generating MPEG data streams from a video server
Are multiplexed together and directed to a single data link 26 and sent to a sink 28. Sink 28 acts in this simulation as discarding the packet. Any other type of server capable of multiplexing larger volumes of traffic may be used in this example as well.

Reference: Statistical properties of MPEG video traffic and their impact on traffic modeling in ATM systems. Proceedings of the 20th Annual Conference on Local Computer Networks, 1995, 3rd.
Pages 97-406 (MPEG trace at ftp: // f
tp-info3. informatic. uni-w
uerzhurg. de / pub / MPEG). R
The frame size from the actual MPEG trace given by ose is used for this simulation source. Table 1 summarizes the characteristics of the MPEG source. All sources are 4M at 25 frames per second
It has a peak speed of bps and a duration of 1600 seconds (except for the news1 trace which is 1260 seconds). They are started randomly for a time period of 1600 seconds and measurements are taken between 1600 and 3200 seconds. MPE
When the G trace ends, it repeats. Since the frame is transmitted with a minimum packet size of 40 bytes, 1
It is divided into 500 byte packets.

[0032]

[Table 1]

The following measurements are collected for each session: -End-to-end delay for each packet-actual packets dropped-degraded packets (50ms> delayed packets)-degraded frames (frames related to degraded or dropped packets)-degraded Seconds (1 related to degraded frames)
Seconds duration)

If the frames of the session have not been degraded, the session has received "good service" during any particular second. If there is a session that has not received “good service”, this is considered to have received “degraded service”. The system of the present invention is implemented based on these simulation experiments to provide as many sessions as possible to receive good service during a particular transient congestion period. The second buffer means 18, ie, the β queue, is provided with the LIFO-FI
Follow the O principle. Packets from the β queue are transferred to the α queue only when the α queue is empty, in other words, only when T _abate is 0. The threshold _{Tonset, j} for transferring a packet to the β queue is LL / (3 + j−
1) (where L is the length of the α queue in this simulation). If no packets from a source (or session) are in the β queue, such a source is removed from the forwarding list. In an ideal network with a variable number of ongoing sessions, the threshold assignment can be made dynamically by simply replacing the number of sessions in the simulation with the number of ongoing sessions. The packet timeout threshold, t _expire, is set to 400 ms.

In this set of experiments, the simplest method of choosing which session to transfer to the β queue is chosen. The method is such that the session of the first packet exceeding T _{onset, j} is chosen to be transferred to the β queue. The β queue uses the oldest packet pushing mechanism at the time of this overflow.

Table 2 lists a set of simulation experiments used to compare the performance of the algorithm or method of the present invention, termed double queue (DQ), with real FIFO and fair standby methods. Is shown. Define round robin (DR) for fair wait comparison
R) technique is used, but is extended to include older packet discards (extended DRR) to make a fairer comparison with DQ.

[0037]

[Table 2]

The DRR technique is described in "Effective Fair Waiting Using Deficit Round Robin", IEEE / ACM Transactions, Networking, Vol.
In 1996, in the literature entitled pp. 375-385, M.M. Shredhar and G.W. Introduced by Vargese.

As mentioned earlier, a packet has 50
If it is delayed for more than ms, it is discarded. This is used as an estimate of the maximum delay allowed before the frame is not displayed to the viewer or user. t _expire = 4
Packets waiting longer than 00 ms are discarded by the extended DRR and DQ algorithms. However, MPEG frames that arrive too late for display may still be useful for decoding subsequent frames that are not delayed so badly.

All queues are given the same total buffer size and the bit rate used in each simulation experiment is kept constant. The size of the α queue implemented in DQ will change when the link transfer rate is changed to give a maximum packet delay of 50 ms. It should also be noted that the worst service delay overhead in the DRR introduced by the round robin scheduling method is less than the 50 ms good service delay threshold.

In Experiment 1, shown in Table 2, all twenty heterogeneous MPEG sources are multiplexed to link 26. Four representative sessions, numbered 3, 10, 14 and 20, are arbitrarily selected to provide FIFO, extended DRR
And a detailed comparison between the DQ scheduling algorithm.

FIG. 7 shows session 3 (represented by graph 30), session 10 (represented by graph 32) when the link transmission rate is 10 Mbps (comparable to the total average presentation rate of 9.5 Mbps). 4 shows a graph of the cumulative probability distribution for session 14 (represented by graph 34) and session 20 (represented by graph 36). The dropped packet is considered to have an infinite delay in FIG. The case of heavy loading was chosen to exaggerate differences between algorithms during congestion. A line is drawn at the 50 ms good service critical point. It can be seen that the DQ algorithm gives the highest part of the packet that experiences less than 50 ms delay. This is achieved by giving a packet a delay of more than 50 ms. Assuming that the service provided to such a packet has already degraded, the amount of delay exceeding 50 ms is considered to be of little relevance.
Note that enhanced DRR gives session number 20 better service than other sessions (usually because it is not operating on its fair share of bandwidth as expected from fair-wait-based discipline). I do. Note that this also applies to the DQ algorithm.

FIG. 8 shows that the transmission speed on the link 26 is 12
Shown is a plot of the maximum packet delay per second for the source or sessions 3, 10, 14, and 20, respectively, as simulated, as it increases to Mbps. Plots 38, 40, 42 and 44
Are for sessions 3, 10, 14, and 20, respectively. 50m to show good service interruption point
A line is drawn on the s mark. The time range shown has been chosen to include multiple periods of transient congestion for comparison between the various algorithms. The FIFO is fair at the packet level, and all session packets are FIFO
On the base, the same delay is experienced on average when passing through the node 24. Extended DRR is a little better, but cannot allocate good service when many of the sessions have to share bandwidth so that they do not receive as much of their required service. The priority property of the FQ gives a longer delay to the burst of packets than in the FIFO method. Thus, these extra delays can degrade packets from a particular session, even when the link is not congested as shown in trace 38 at the top of source 3 in FIG. The selected DQ discipline will maximize the instantaneous number of sessions receiving good service, so that one of the sessions will experience very poor delay performance, so that the other session will take 1925 seconds It can be seen that the service quality deterioration is avoided in the time of 1975 seconds.

A better illustration of the level of QoS by all of the 20 sessions is given in FIG. 9, which is the percentage of all sessions that simultaneously receive good service during a similar 1 second period. Plot 46
Is shown. FIFO and extended DRR algorithms are 18
It should be noted that in 55 seconds, 1925 seconds and 1975 seconds, many sessions are provided with degraded service. These QoS diagrams may be represented in binary form, either when the service is good or degraded. The binary representation of services per session generally provides everything needed for comparison between each of the scheduling disciplines. FIG.
Shown is such an indication 48 for the extended DRR algorithm and an indication 50 for the DQ algorithm over the entire measurement time scale for each session at a link transmission rate of 2 Mbps. Vertical bars are drawn for each degraded second that any particular session receives. The more white space on the graph, the better the service the session is receiving. All results shown in the following figures use this comparison method. From FIG.
It can be seen that the DQ method reduces the number of sessions affected by congestion at any particular time compared to the extended DRR.

The transmission speed is 10 Mbps shown in FIG.
12 and the difference between the extended DRR and DQ becomes even more apparent.
Plots 52 and 54 are for the extended DRR and DQ algorithms of FIG.
And 58 are for the extended DRR and DQ algorithms of FIG. 12, respectively. It is clear that the DQ method gives better service to most sessions even under extreme overload conditions compared to the extended DRR algorithm. Even if these experiments or simulations provided the simplest possible implementation of the DQ approach,
It can provide significantly better performance for real-time services than extended DRR can.

Referring to Table 2, Experiments 2 and 3 use 4 and 40 sources, respectively, and are performed to determine the scalability of the DQ algorithm. Experiment 2 adds the complexity of having the peak bit rate of any session greater than the link transmission rate, thus starting to fill the α queue. FIG.
In FIG. 3, four sources are used, and even when given an unmanageable load, the DQ algorithm shown in plot 60, especially if slightly worse for sources 3 and 4, It can be seen that it works similarly to the extended DRR algorithm shown at 62. Experiment 3
In, both scheduling disciplines gave good performance at almost all times and were not shown in this case. For extended DRR, 13 sessions received degraded service when a single congestion occurred, but only one session received degraded service using the DQ algorithm during the same period. No longer. In the DQ algorithm, there is only one second during which a session has degraded service, but the extended DR
Using R results in a degraded service in one other second. Therefore, it can be concluded that the DQ approach scales fairly well when compared to the extended DRR.

Twenty homogenous sources were used in Experiment 4 to check for fairness over a medium time scale. The session consists of 20 copies of the race trace starting at a random time over a period from 0 to 1600 seconds. FIG. 14 shows the extended DRR for each session when extended DRR is considered to be a very degraded service but provides fairness for each session.
And degraded seconds slots 64 and 66, respectively, for the DQ algorithm. Qualitatively, DQ
The algorithm also provides fair service to each session over the entire length of the simulation, rather than instantaneously. As can be seen from the previous description, the overall QoS of each session is much better in DQ than that provided by the extended DRR.

[0048] In general, it is understood that when there is no congestion, all approaches compared provide good service. However, the longer the period of congestion, the greater the difference between the three algorithms. FIG. 15 shows a plot 68 of the degraded packet percentage for the FIFO, DRR, enhanced DRR and DQ algorithms for various average presentation loads (standardized to link transmission rate). .
Apart from achieving its goal of providing good service to as many sessions as possible during periods of transient congestion,
The DQ algorithm also minimizes the overall rate of degraded packets. Even under the simple embodiment of the DQ approach, the rate of degraded packets is 1 Erlang
g) It must be noted that the oversubscribed load is approaching above, and therefore close to the optimal value. This is also a short FI
As with FO queues, short FIFO queues have the disadvantage that if the offered load is close to but less than the transmission link speed, it will cause unnecessary losses during transient congestion periods. Also, short FIFO queues drop packets randomly rather than selectively, as in DQ.

During transient congestion conditions, all packets entering the normal FIFO queue receive similar degraded service. If congestion is caused by a small number of sessions, fair wait provides relief for other sessions.
However, the results mentioned above indicate that this is not always the case when transient congestion is often caused by many sessions and the combined traffic fills the queue. Fair waiting divides the bandwidth equally, thus degrading the service of a very large number of sessions and therefore a very large number of packets. The DQ algorithm degrades the service of the session required for it to get good service for the majority of the session during periods of congestion, and thus also outperforms fair standby to improve throughput. I have.

As mentioned earlier, the service provider receives a “perfect” service to minimize the number of complaints the user feels when making a connection and receiving poor QoS, ie, congestion. You may want to maximize the number of users who don't show a sign. this is,
This is accomplished by recording the connections transferred to the β queue at some stage in the “target” list or file and increasing the probability that they will be transferred again the next time the system becomes congested. Thus, the degradation will not spread evenly between users over a considerable time scale, increasing the probability of a connection being unaffected by congestion. The probability of transferring a connection in the target list or file can be increased to one, in which no new connections are transferred until all previously transferred connections have now been transferred. Another alternative is to take into account several factors, including the current data rate as well as the presence of a target list or file connection.

If the goal of the service provider is to maximize the number of satisfied customers at any time in time, the optimal strategy is to transfer the highest speed session (redi).
Rect). If the statistics of a given connection change significantly over time, the above approach of repeatedly targeting a particular user for the entire connection may not be appropriate. Rather, the session is removed from the target list or file after some time t _target . This results in a series of defective services on the time scale of t _target , but can increase the total number of high QoS customers for the hour and minute.

Telecommunications enforcement agencies may require more rigorous assurance of fairness over a medium time scale than provided by the previously described DQ implementation. This is also possible by recording the transferred connection or session. At this time, the possibility that these sessions will be transferred again is small. Similarly, there is a trade-off of the total number of minutes of high QoS customers that can be achieved.

If other service disciplines are considered for the β queue, except for the previously described LIFO-FIFO system, greater flexibility can be provided. For example, the β queue would be able to use fair wait. Let L denote the set of slow users that require less than fair share bandwidth. In pure fair standby, L sessions are allocated their entire bandwidth, and the remaining bandwidth is allocated to the remaining sessions. In a hybrid DQ / FQ system, the set of sessions G (t) selected to receive good service at time t is fairly divided in residual bandwidth after service to G (t) users. Performs the role of L as described above. If G (t) = 1 for all t, ie, α
If the size of the queue is set to zero, this hybrid approach reduces to fair wait. Conversely, if G (t) is a set of all users, it becomes FIFO. However, G
Making (t) a strict superset of L, keeping the total instantaneous bandwidth still less than the output link capacity, and increasing the number of satisfied customers without penalizing any well-behaved users. Often possible.

As an alternative to using an over-threshold-based method of initiating the transfer of a session from the α queue to the β queue, there is a wide range of possible trigger conditions. One example is that if the rate of increase in the amount of data stored in the α queue exceeds the derivative-based threshold,
This involves the use of a derivative-based approach in which the data packets are transferred to a second buffer means. Fuzzy based approaches can also be used. Therefore, when the amount of packets stored in the α queue reaches a predetermined increase rate, the packet (s) of the session (s) is transferred to the β queue.

FIG. 16 is a flow chart 1 illustrating the steps or processes associated with receiving a packet representing a session on an output link to output port 6 or node 24.
00 is shown. At step 102, the received packets are time stamped to allow buffers 16 and 18 to store the packets in a particular sequence based on time. At step 104, the checker is checked to see if other packets associated with the session are in the β queue forwarding list. If there is no previous packet in the β queue, a determination is made at step 106 whether the received packet, if it was in the α queue, has exceeded the capacity threshold. If the packet does not exceed the capacity threshold, it is stored in the α queue at step 108, or if it exceeds the capacity threshold, the stream or session identifier is placed on the β queue transfer list at step 110, and then at step 112 Capacity threshold is used. Then, in step 114, the packet
Stored in the queue. Returning to step 104, if the previous packet from the session is already in the β queue forwarding list, the received packet is immediately re-stored in the β queue in step 114.

FIG. 17 is a flowchart 200 illustrating the processes and steps involved when a packet is transferred from a β queue (ie, second buffer means 18) to an α queue (ie, first buffer means 16). Is shown. At step 202, a determination is made whether there is a packet in the β queue, and if not, step 204 does nothing. If there are any packets to wait for, in step 206 the oldest packet is taken from the latest session that is transferred to the β queue (LIFO-FIF).
O). At step 208, if the packet is too old
A determination is made whether _expired has been _exceeded . If so, the packet is discarded at step 220 and a determination is made at step 222 as to whether the discarded packet was the last packet from the session. If it is the last packet, step 224
, The session belonging to the packet is removed from the β queue forwarding list, and then the previous α queue decrease threshold is enforced at step 226. The process then returns to step 202. If the discarded packet is not the last packet from that session in the β queue, the process returns to step 202 again. Referring back to step 208, if the packet is not too old and within the time limit set by t _expire , the packet is stored in the α queue at step 210,
At step 212, a determination is made whether the stored packet is the last packet from a session in the β queue. If it is not the last packet, the process does nothing at step 214. If it is the last packet in the β queue belonging to the session, the session is removed from the β queue forwarding list in step 216 and the previous α queue decrement threshold is enforced in step 218.

FIG. 18 shows the process associated with storing session packets from the third buffer means in the first buffer means and the first buffer means such packets or sessions at the beginning of congestion. A flowchart 300 is shown illustrating the steps involved in handling (see FIGS. 4 and 5). An incoming packet is received at one of the output ports 6 of the third buffer means 19. At step 302, a check is made as to whether the packet has been temporarily stored in any one of the third buffer means of the persession queue 21. Per-session queues
If a packet is stored in any one of the queues 21, the packet is selected in step 304 from one of these queues according to the selected scheduling discipline, and then in step 306 to the first buffer means 16 or the output queue. Is stored. If the selected packet exceeds the current capacity threshold of the first buffer means 16 in step 308, the session to which the particular packet belongs is identified in step 310 and the per-session queue of the second buffer means 18 is identified. Buffered into one. Again at step 308, if the packet does not exceed the current capacity threshold, the process proceeds to step 3
Return to 02. In step 312, the first buffer unit 1
The next capacity threshold set at 6 is used and evaluated for further packets entering the first buffer means 16. In this connection, step 30
Step 8 is repeated to test whether the incoming packet has continuously exceeded the capacity threshold.

At step 302, if the packet is not waiting in the third buffer means 19, the process _proceeds to step 314, where it determines whether the capacity of the first buffer means has _fallen below the reduction threshold T _abate. Is determined. If so, a determination is made at step 316 as to whether any packets are temporarily stored in any one of the second buffer means in the persession queue. If the capacity of the first buffer means has not _fallen below T _{abate in} step 314, the process returns to step 302. If there are any packets waiting in the second buffer means 18 in step 316, the latest stream or packet from the session identified as part of the logical queue forming the second buffer means is retrieved in step 318. It is. If there are no packets waiting in the second buffer means 18, the process returns to step 302. At step 320, a determination is made whether the packet retrieved from the second buffer means is too old or has _exceeded its timeout threshold, t _expire . If the packet has been in the second buffer means too long and has exceeded its timeout threshold, the packet is discarded at step 322, or if it has not exceeded its timeout threshold, the packet is skipped at step 324. 1 buffer means 16. Then, in step 326, a determination is made as to whether the most recently retrieved packet is the last packet of that particular stream or session stored in any one of the persession queues 21 of the second buffer means 18. Done. If so, the stream is then identified in step 328 as being part of the stream originating from the third buffer means 19 and then
At 30 the previous capacity threshold is used or enforced. If the most recently retrieved packet at step 326 is not the last packet for that particular stream or session, the process proceeds to step 302
Return to At step 330, after the previous capacity threshold has been implemented, the process also returns to step 302.

It will also be appreciated that various modifications and adaptations to the preferred embodiment described above can be made without departing from the scope and spirit of the invention.

[Brief description of the drawings]

FIG. 1 is a schematic diagram of a system and a packet switch or a node of a telecommunications network realizing the system according to a first embodiment.

FIG. 2 is a schematic diagram illustrating the buffering of data packets in a second buffer means intended for the first buffer means.

FIG. 3 is a schematic diagram illustrating the transfer of a data packet from a second buffer means to a first buffer means for transmission on an output link from the first buffer means.

FIG. 4 is a schematic diagram of a system and a packet switch or node of a telecommunications network realizing the system according to a second embodiment of the present invention;

FIG. 5 is a schematic diagram showing first, second and third buffer means and handling of a data packet reaching the node of FIG. 4;

FIG. 6 is a block diagram of a system for simulating multiple traffic sources input to a node having first buffer means and second buffer means.

FIG. 7 is a series of plots showing the cumulative probability distribution of packet delay for multiple sessions using FIFO, enhanced DRR and DQ simulations.

FIG. 8 shows a series of plots of maximum packet delay per second versus simulation time for multiple sessions with increased link transmission rates using FIFO, enhanced DRR and DQ simulations.

FIG. 9: “Good service” in 1 second period for each of FIFO, extended DRR and DQ simulations
7 is a plot of a number of sessions that receive the same.

FIG. 10 shows plots for FIFO, enhanced DRR and DQ simulations of degraded service received by all sessions, respectively.

FIG. 11 shows plots for each of the extended DRR and DQ simulations showing the number of degraded seconds for each of the sessions shown in FIG. 8 with reduced line rates.

FIG. 12 is a plot similar to FIG. 9, but with the line transmission rate further reduced.

FIG. 13 is a view similar to FIGS. 9 and 10 showing degraded seconds for various sets of sessions at low line rates.

FIG. 14 is a plot showing degraded seconds for a further set of various sessions using enhanced DRR and DQ simulations at increased line rates.

FIG. 15: FIFO, DRR, extended DRR and D for various average presentation loads normalized to link transfer rate
5 is a plot of the overall percentage of degraded packets for the Q algorithm.

FIG. 16 is a flowchart illustrating a process associated with receiving a packet of a session on a link associated with a node.

FIG. 17 is a flow chart showing a process involved when a packet is transferred from the second buffer means to the first buffer means.

FIG. 18 is a flowchart illustrating a process associated with handling one or more packets arriving at the third buffer means of FIG.

[Explanation of symbols]

 2 node 16 first buffer means 18 second buffer means

 ──────────────────────────────────────────────────続 き Continued on the front page (72) Inventor David Andrew Hays Australia, Victoria, Pascoebar South, MacKeon Avenue 2/19 (72) Inventor Michael Peter Ramsewick Australia, Victoria, Glen Iris, Renwick Street 34 (72) Inventor Lasilane Leister Henry Andrew Australia Victoria, Watsonia, Black Street 10F term (reference) 5K030 HA08 KA03 KX11 KX18 LC01 LC18 MB15

Claims (59)

[Claims] 1. A method for scheduling a data packet in a telecommunications network, comprising: receiving a packet of data representing one or more sessions and storing it in a first buffer means at a node of the network. Monitoring the used capacity or occupancy of the packet in the first buffer means; and transmitting the data packet to the node at the start of a trigger condition to prevent the first buffer means from overflowing during a congestion period. Buffering the second buffer means in the above. 2. The method according to claim 1, wherein a data packet stored in either said first buffer means or said second buffer means is associated with said node from said first buffer means. A method characterized by outputting to a link. 3. The method of claim 2, wherein said link is an output link to said node. 4. The method according to claim 1, wherein the packet is received and the received packet is stored in a third buffer before being transferred to the first buffer. The method further comprising the step of: 5. The method of claim 4, wherein the packets are stored according to the session to which each packet belongs.
A method according to claim 4, wherein said data is transferred from said third buffer means to said first buffer means according to a schedule creation rule. 6. The method according to claim 4 or 5, wherein each session has a respective packet stored in a persession queue of either the second buffer means or the third buffer means. A method comprising: 7. The method according to claim 1, wherein said trigger condition is triggered when a rate of increase in the amount of data stored in said first buffer means exceeds a differential-based threshold. A method wherein the data packet is at a differential based threshold such that it is buffered in said second buffer means. 8. The method according to claim 1, wherein the triggering condition is the first or later of the first buffer means due to the arrival of a data packet to the first buffer means. The capacity threshold is exceeded. 9. The method according to claim 8, wherein said first and subsequent capacity thresholds are exceeded.
The first data packet of said buffer means is buffered in said second buffer means. 10. The method according to claim 9, wherein successively arriving packets of the session to which said first data packet belongs are buffered in said second buffer means. . 11. The method according to claim 8, wherein the session with the largest data packet of the first buffer means sets the one or more capacity thresholds of the data packet to the first buffer means. The method of claim 2 wherein said second buffer means is buffered when exceeding by arrival. 12. The method according to claim 11, wherein a subsequent data packet for a session having the largest data packet stored in said first buffer means is transferred to said second buffer means, and transferred. Further comprising the step of temporarily storing the stored data packets sequentially in said second buffer means. 13. The method of claim 8, wherein the session having a packet exceeding the first or subsequent capacity threshold and not temporarily stored in the second buffer means. And subsequent packets arriving from the session are also buffered in the second buffer means. 14. The method according to claim 8, wherein the session previously stored or buffered temporarily in said second buffer means and having a data packet in said first buffer means is performed in said first or second buffer means. The method of claim 2 wherein said buffer is buffered in said second buffer means when a subsequent capacity threshold is exceeded. 15. The method according to claim 1, wherein a time-out threshold is set in said second buffer means, said time-out threshold being set to said second buffer means being longer than said time-out threshold. A method wherein any stored packets are discarded. 16. The method according to claim 15, wherein a data packet newly arriving at said second buffer means is discarded at the start of overflow of said second buffer means. Method. 17. The method according to claim 1, wherein a time-out threshold is set according to a type of a stream represented by a data packet stored in the second buffer means. And any packets stored in said second buffer means longer than their respective timeout thresholds are discarded. 18. The method according to claim 15, wherein at the start of the overflow of the second buffer means, the oldest packet stored in the second buffer means is removed from the second buffer means. A method characterized by being disposed of. 19. The method according to any one of claims 1 to 18, wherein the method further comprises: when the occupancy of the first buffer means is less than or equal to a decreasing threshold. The method further comprising forwarding the data packets held in the buffer means to the first buffer means. 20. The method according to claim 19, wherein when a packet from a particular session is not stored in said second buffer means, a subsequently arriving packet from said particular session is said first packet. A method characterized by being stored in a buffer means. 21. The method according to claim 19, wherein packets are transferred from said second buffer means to said first buffer means on a first-in first-out (FIFO) basis, and the order in which packets arrive at said second buffer means. The method according to claim 1, wherein the packet is forwarded. 22. The method according to claim 19, wherein packets from each session are transferred from said second buffer means to said first buffer means on a FIFO-FIFO basis, whereby said second buffer means. The first recorded session is transferred to the first buffer means first, and the packets are transferred in the order in which the packets arrived at the second buffer means in each transferred session. A method characterized by being performed. 23. The method according to claim 19, wherein packets from each session are transferred from said second buffer means to said first buffer means on a LIFO-FIFO basis, whereby said second buffer means. The last session is transferred first, and the packets are transferred in the order in which the packets arrive in the second buffer means in each session. 24. The method according to claim 19, wherein the packet is forwarded using a fair standby system, and
A session of data packets stored in said buffer means having a residual bandwidth left by said session stored in said first buffer means. 25. A method as claimed in any one of claims 21 to 24, wherein the number of packets from each transferred session is recorded. 26. A method as claimed in any one of claims 1 to 25, comprising: attaching a time stamp to each data packet stored and buffered in said second buffer means. Features method. 27. The method according to any one of claims 1 to 26, wherein the second
Providing one or more packets stored in the buffer means of the network, wherein the session is so recorded at another node of the network where the one or more packets are received. A method of providing an identification label for confirming that the operation has been completed. 28. A system for scheduling data packets in a telecommunications network, comprising: first buffer means located at a node of the network for receiving data packets representing one or more sessions; Second buffer means located at the node of the first buffer means, wherein a data packet is transmitted to the second buffer means at the start of a trigger condition so as to avoid overflow of the first buffer means during a congestion period. The system characterized by being buffered. 29. The system according to claim 28, wherein a data packet of either said first buffer means or said second buffer means is output from said first buffer means to a link associated with said node. A system characterized in that: 30. The system according to claim 29, wherein said link is an output link to said node. 31. The system according to claim 28, further comprising a third buffer means for receiving the data packet before transferring the received packet to the first buffer means. A system characterized by doing so. 32. The system according to claim 31, wherein said data packets are stored in said third buffer means according to a session to which each packet belongs, and said data packets are stored in said third buffer means according to a schedule creation rule. A system characterized by being transferred to a means. 33. The system according to claim 31, wherein each session has a respective packet stored in a persession queue of either the second buffer means or the third buffer means. A system characterized by: 34. The system according to any of claims 28 to 33, wherein the trigger condition is when the rate of increase in the amount of data stored in the first buffer means exceeds a derivative-based threshold. A system according to any of the preceding claims, wherein the data packet is at a differential-based threshold such that it is buffered in said second buffer means. 35. The system according to any one of claims 28 to 33, wherein the trigger condition is the first or later of the first buffer means due to the arrival of a data packet to the first buffer means. A system wherein the capacity threshold is exceeded. 36. The system according to claim 35, wherein a first data packet of said first buffer means exceeding said first and subsequent capacity thresholds is buffered in said second buffer means. A system characterized by the following. 37. The system according to claim 36, wherein successively arriving packets of the session to which said first data packet belongs are buffered in said second buffer means. . 38. The system according to claim 35, wherein the session with the largest data packet of the first buffer means sets the one or more capacity thresholds of the data packet to the first buffer means. A system for buffering the second buffer means when exceeding by arrival. 39. The system according to claim 38, wherein subsequent data packets belonging to a session having the largest data packet in said first buffer means are transferred to said second buffer means, and said second buffer means A system characterized by being temporarily stored in the means in order. 40. The system according to claim 35, wherein a session having a packet exceeding the initial or subsequent capacity threshold and not temporarily stored in the second buffer means is stored in the second buffer means. A system wherein the buffered and subsequent packets arriving from the session are also buffered in the second buffer means. 41. The system according to claim 35, wherein the session previously stored or buffered temporarily in the second buffer means and having data packets in the first buffer means is the first or the first. A system wherein the buffer is buffered in the second buffer means when a subsequent capacity threshold is exceeded. 42. The system according to any one of claims 28 to 41, wherein a timeout threshold is set in said second buffer means, said timeout threshold being set to said second buffer means being longer than said timeout threshold. A system wherein any stored packets are discarded. 43. The system according to claim 42, wherein a data packet newly arriving at said second buffer means is discarded at the start of overflow of said second buffer means. system. 44. The system according to any one of claims 28 to 43, wherein the time-out threshold is set according to the type of stream represented by the data packet stored in said second buffer means. And any packets stored in said second buffer means longer than their respective timeout thresholds are discarded. 45. The system according to claim 42 or 44, wherein at the start of overflow of said second buffer means, the oldest packet stored in said second buffer means is removed from said second buffer means. A system characterized by being discarded. 46. A system as claimed in any one of claims 28 to 45, wherein said first buffer means retains in said second buffer means when the occupancy is less than or equal to a decreasing threshold. The data packet being transferred is transferred to the first buffer means. 47. The system according to claim 46, wherein when a packet from a particular session is not stored in said second buffer means, a subsequently arriving packet from that session is transmitted to said first buffer means. A system characterized by being stored in a memory. 48. The system according to claim 46, wherein packets are transferred from said second buffer means to said first buffer means on a first-in first-out (FIFO) basis, and the order in which packets arrive at said second buffer means. The system is characterized in that the packet is forwarded by: 49. The system according to claim 46, wherein the packets from each session are FIFO-FIFO
A session transferred by reference from the second buffer means to the first buffer means, whereby the session first recorded in the second buffer means is first transferred to the first buffer means. Wherein the packets are transferred in the order in which the packets arrive in the second buffer means in each transferred session. 50. The system according to claim 46, wherein the packets from each session are LIFO-FIFO.
By reference, the second buffer means is forwarded to the first buffer means, whereby the last session is forwarded to the second buffer means first, and within each session packets are transferred to the second buffer means. A system wherein packets are transferred in the order in which the buffer means arrives. 51. The system of claim 46, wherein packets are transferred using a fair standby system, and sessions of data packets stored in said second buffer means are stored in said first buffer means. A system having a residual bandwidth left by a session. 52. The system according to any one of claims 48 to 51, wherein the number of packets from each transferred session is recorded. 53. A system according to any one of claims 28 to 52, wherein each data packet stored and buffered in said second buffer means is time stamped. A system characterized by the following. 54. The system according to any one of claims 28 to 53, comprising providing one or more packets belonging to a session and stored in said second buffer means. And wherein the one or more packets are provided with an identification label that identifies to another node of the network that the packet is received that such a session has been recorded. 55. The system according to any one of claims 28 to 54, wherein said first buffer means is a FIFO buffer. 56. The system according to claim 28, wherein said first buffer means and said second buffer means comprise one or more persession queues, and wherein said trigger condition is said first buffer. A system wherein the capacity threshold is exceeded at the beginning of or after the means, wherein the sum of the capacities of the individual sessions stored in the queue of the first buffer means exceeds a predetermined threshold. 57. A packet switch in a packet switched network having a system for scheduling data packets according to any one of claims 28 to 56, wherein one or more of the data switches receive data packets transmitted from respective information sources. The one or more ports forward the packet to another node of the network, wherein each of the one or more ports includes the first buffer means and the And a second buffer means. 58. A data packet scheduling system for scheduling packets representing one or more sessions in a telecommunications network according to the quality of a service standard set by a telecommunications service provider. First buffer means for receiving and temporarily storing data packets of one or more sessions transmitted on the network, and wherein the first buffer means does not overflow during a network congestion period. A second buffer means for buffering the data packet at the start of the trigger state set in the first buffer means due to the arrival of the data packet in the first buffer means. Data packet schedule creation system. 59. A method and system for scheduling data packets as described below with reference to the accompanying drawings.