Methods and devices for prioritizing in handling buffers in packet networks

• US 5,555,264 A
• Filed: 11/14/1994
• Issued: 09/10/1996
• Est. Priority Date: 03/20/1992
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktienbolaget L.M. Ericsson
• Inventors: Sallberg, Hans K. M., Blaabjerg, Soren
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/307,611
• Time in Patent Office: 666 Days
• Field of Search: 370/13, 370/17, 370/58.1, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/61, 370/85.6, 370/94.1, 370/94.2, 340/825.06, 340/825.5, 340/825.51, 371/5.1, 371/5.5
• US Class Current: 370/414
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5646 Cell characteristics, e.g. loss, delay, jitter, sequence integrity
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5678 Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/1553 Interconnection of ATM switching modules, e.g. ATM switching fabrics
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Methods and devices for handling a buffer in packet networks, particularly in regard of loss and delay of packets, which belong to predetermined or implicitly given loss priority classes and delay priority classes. When a packet arrives at the buffer, its loss priority and delay priority classes are determined. For each loss priority class, there is a predetermined threshold value, and a total filling level of the buffer, i.e., the total number of packets stored, is compared to the threshold value of the packet'"'"'s loss priority class. If the threshold value is larger than the total filling level, the packet is buffered in order to be forwarded; otherwise, the packet is lost. In determining whether a packet is to be buffered or lost, the packet'"'"'s delay priority is not taken into account. In forwarding packets from the buffer, those packets that belong to higher delay priority classes are chosen in the usual way before packets belonging to lower delay priority classes. This is done such that packets belonging to all delay priority classes can be warranted a specific minimum service level by associating each such class with a maximum time period, within which at least one packet of the delay class considered will be forwarded if such a packet is available in the buffer.

Claims

1. A method for handling in a packet network a buffer, in which arrived packets are stored before they are forwarded, in particular in a switch device,

each packet belonging to a certain loss priority class of at least two loss priority classes and

each packet also belonging to a certain delay priority class of at least two delay priority classes, the delay priority classes being intended to give different delays for the packets belonging to said classes, such that longer delays are allowed for packets belonging to delay priority classes having a lower delay priority,

the method comprising, for each arrived packet, the following steps:

a) determining the loss priority class of the packet,

b) determining whether the present total number of packets stored in the buffer is smaller than a threshold value associated with the loss priority class of the packet,

c) if the determination in b) gives the answer yes, storing the packet in the buffer and otherwise discarding the packet,

for each arrived packet also determining the delay priority class of the packet and

in forwarding packets from the buffer, choosing packets belonging to a higher delay priority class before packets belonging to a lower delay priority class.

2. A method for handling in a packet network a buffer, in which arrived packets are stored before they are forwarded, in particular in a switch device,

each packet belonging to a certain loss priority class of at least two loss priority classes and

each packet also belonging to a certain delay priority class of at least two delay priority classes, the delay priority classes being intended to give different delays for the packets belonging to said classes, such that longer delays are allowed for packets belonging to delay priority classes having a lower delay priority,

the method comprising, for each arrived packet, the following steps:

a) determining the loss priority class of the packet,

b) determining whether the present total number of packets stored in the buffer is smaller than a threshold value associated with the loss priority class of the packet,

c) if the determination in b) gives the answer yes, storing the packet in the buffer and otherwise discarding the packet,

for each arrived packet also determining the delay priority class of the packet and

in forwarding packets from the buffer, choosing packets belonging to a higher delay priority class before packets belonging to a lower delay priority class

wherein with each lower delay priority class time intervals having predetermined lengths are associated, such that a packet from a lower delay priority class is chosen instead of a packet from a higher delay priority class, if no packet from the lower delay priority class has been sent during the time interval having the predetermined length associated with the delay priority class thereof and if such a packet is available.

3. A device for handling in a packet network a buffer memory, in which arrived packets are stored before they are forwarded, in particular in a switch device,

each packet belonging to a certain loss priority class of at least two loss priority classes and a threshold value being associated with each loss priority class,

each packet also belonging to a certain delay priority class of at least two delay priority classes, the delay priority classes being intended to allow different delays for the packets belonging to said classes, such that longer delays are allowed for packets belonging to delay priority classes having a lower delay priority,

the device comprising

an input on which the arrived packets arrive,

the buffer memory,

an output on which arrived packets are forwarded,

a logic unit for determining those packets to be stored in the buffer memory comprising

a) means for determining the loss priority class of an arrived packet,

b) means for determining if the present total number of packets stored in the buffer memory is less than the threshold value associated with the loss priority class of the arrived packet and for forwarding, when this condition is satisfied, a signal thereof to

c) means for storing the arrived packet in the buffer memory, and

d) means for determining for each arrived packet the delay priority class of the arrived packet and

another logic unit for determining which packet is to be sent from the buffer memory comprising

means for choosing packets belonging to a higher delay priority class before packets belonging to a lower delay priority class and for transferring the selected packets to the output for forwarding.

4. A device for handling in a packet network a buffer memory, in which arrived packets are stored before they are forwarded, in particular in a switch device,

each packet belonging to a certain loss priority class of at least two loss priority classes and a threshold value being associated with each loss priority class,

each packet also belonging to a certain delay priority class of at least two delay priority classes, the delay priority classes being intended to allow different delays for the packets belonging to said classes, such that longer delays are allowed for packets belonging to delay priority classes having a lower delay priority,

the device comprising

an input on which the packets arrive,

the buffer memory,

an output on which the packets are forwarded,

a logic unit for determining those packets to be stored in the buffer memory comprising

a) means for determining the loss priority class of an arrived packet,

b) means for determining if the present total number of packets stored in the buffer memory is less than the threshold value associated with the loss priority class of the arrived packet and for forwarding, in the case that this condition is satisfied, a signal thereof to

c) means for storing the arrived packet in the buffer memory, and

d) means for determining for each arrived packet also the delay priority class of the packet and

another logic unit for determining which packet is to be sent from the buffer memory comprising means for choosing packets belonging to a higher delay priority class before packets belonging to a lower delay priority class wherein each lower delay priority class is associated with time intervals having predetermined lengths, such that instead of a packet from a higher delay priority class a packet is chosen from a lower delay priority class if no packet from the lower delay priority class has been forwarded during the time interval with the predetermined length associated with the delay priority class thereof and if such a packet is available, and

means for transferring a chosen packet to the output for forwarding.

5. A method for handling in a packet network a buffer, in which arrived data packets are stored before they are forwarded, each packet belonging to a respective one of at least two delay priority classes, comprising the step of,

in forwarding packets from the buffer, choosing packets belonging to a higher delay priority class before packets belonging to a lower priority class wherein each lower delay priority class is associated with time intervals having predetermined lengths, such that instead of a packet from a higher delay priority class a packet is chosen from a lower delay priority class, if no packet from the lower delay priority class has been sent during the time interval having the predetermined length associated with the delay priority class thereof and if such a packet is available.

6. A device for handling in a packet network a buffer memory, in which arrived packets are stored before they are forwarded, each packet belonging to a respective one of at least two delay priority classes, comprising

an output on which the packets arrive,

the buffer memory,

an output on which the packets are forwarded from the buffer memory,

a logic unit for determining which packet is in turn to be forwarded from the buffer memory, comprising

means for choosing packets belonging to a higher delay priority class before packets belonging to a lower delay priority class wherein each low delay priority class is associated with time intervals having predetermined lengths, such that instead of a packet from a higher delay priority class a packet is chosen from a lower delay priority class, if no packet from the lower delay priority class has been sent during the time interval having the predetermined length associated with the delay priority class thereof and if such a packet is available, and

means for transferring the chosen data packet to the output for forwarding.

7. A device according to claim 6, further comprising memory means associated with each delay priority class for storing addresses to the data packets which belong to this delay priority class and which are stored in the buffer.

8. A device according to claim 7, further comprising queue arranging means for storing, for arrived data packets, which are stored in the buffer memory, the addresses to these data packets in the corresponding memory means associated with the delay priority class, to which each data packet belongs, and for further placing the addresses to stored data packets belonging to a delay priority class in a definite order in the memory means associated with this delay priority class.

9. A device according to claim 8, wherein the queue arranging means places addresses, in a sequential order, which corresponds to a time order, in which the data packets having these addresses have arrived.

10. A device for handling in a packet network a buffer memory, in which arrived packets are stored before they are forwarded, each packet belonging to a respective one of at least two delay priority classes, comprising

an output on which the packets arrive,

the buffer memory,

an output on which the packets are forwarded from the buffer,

a logic unit for determining which packet is in turn to be forwarded from the buffer memory, comprising

means for selecting packets belonging to a higher delay priority class before packets belonging to a lower delay priority class based on lists stored in a memory for each delay priority class, each list accommodating addresses to the data packets, which belong to this delay priority class and which are stored in the buffer memory, and

means for transferring a chosen data packet to the output for forwarding.

11. A device according to claim 10, further comprising queue arranging means for storing, for arrived data packets, which are stored in the buffer memory, the addresses to these data packets in the corresponding memory associated with the delay priority class, to which each data packet belongs, and for further placing the addresses to stored data packets belonging to a delay priority class in a definite order in the memory associated with this delay priority class.

12. A device according to claim 11, wherein the queue arranging means places addresses, in a sequential order, which corresponds to a time order, in which the data packets having these addresses have arrived.