Method and router in a packet network with priority classes

• US 6,407,999 B1
• Filed: 06/08/1998
• Issued: 06/18/2002
• Est. Priority Date: 10/08/1996
• Status: Expired due to Fees

• Current Assignee: Nokia Telecommunications Oy (Nokia Corporation)
• Original Assignee: Nokia Telecommunications Oy (Nokia Corporation)
• Inventors: Olkkonen, Mikko, Huusko, Sami
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US09/091,169
• Time in Patent Office: 1,471 Days
• Field of Search: 370/389, 370/390, 370/395, 370/396, 370/397, 370/399, 370/412, 370/414, 370/416, 370/418, 370/447, 370/465, 370/468, 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/413, 370/395.1, 370/395.2, 370/395.21, 370/395.41, 370/395.42, 370/395.43
• US Class Current: 370/389
• CPC Class Codes: H04L 2012/5607 Radio
• CPC Class Codes: H04L 2012/561 Star, e.g. cross-connect, concentrator, subscriber group equipment, remote electronics
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and an equipment for packet prioritization when routing data packets is presented. Several priority classes are defined for the packets, and a first threshold value and a second, higher, threshold value is defined for each prioity class. In association with each packet, the oldest packet of a given prioritiy class is selected, and if the packet is older than the second threshold value of the priority class concerned, the packet is discarded, and the next priority class is selected. If the packet is older than the first threshold value of the priority class concerned, at least one packet of this priority class is transmitted until the oldest packet in the priority class is younger than the first threshold value of the priority class concerned, whereupon the next priority class is selected.

Claims

1. A method of routing packets in a router of a packet network, the method comprising:

defining several priority classes for the packets;

defining a first propagation delay threshold value and a second, higher, propagation delay threshold value for each of the several priority classes;

selecting from each of the priority classes, an oldest packet;

determining an estimate of a propagation delay of at least one of the packets;

lowering a priority of at least one packet, if the estimate of the propagation delay associated with that at least one packet is higher than the second threshold value of a present priority class associated with that at least one packet;

transmitting at least one packet of the present priority class if the estimate of the propagation delay associated with that at least one packet is higher than the first threshold value but lower than the second threshold value of the present priority class; and

selecting a next priority class;

wherein the first threshold value equals an average propagation delay determined for the priority class minus an estimated propagation delay of the packet in other parts of the network, and the second threshold value is a maximum propagation delay defined for the priority class, wherein the maximum propagation delay is based on a delay that a majority of the packets has to fall short of minus the estimated propagation delay of the packet in other parts of the network.

2. The method of claim 1, wherein the transmitting the at least one packet includes transmitting a predetermined number of packets including the at least one packet, wherein the predetermined number does not exceed a number of packets included in the present priority class.

3. The method of claim 1, wherein the transmitting the at least one packet is performed until a propagation delay estimate associated with the oldest packet in the present priority class is less than the first threshold value of the present priority class.

4. The method of claim 1, wherein the lowering of the priority of at least one packet is performed by discarding that at least one packet.

5. The method of claim 1, further comprising determining the priority class of the at least one packet based on a quality of service of a connection associated with the at least one packet.

6. The method of claim 1, wherein the estimate of the propagation delay of the at least one packet is a moving average of propagation delays of the packets of the present priority class associated with the at least one packet.

7. The method of claim 1, further comprising using the propagation delay of the at least one packet as the estimate of the propagation delay associated with that at least one packet.

8. The method of claim 1, wherein the packet network is a General Packet Radio Service network and the router is at least one of a Serving General Packet Radio Service Support Node and a General Packet Radio Service Gateway Support Node.

9. A router in a packet network, the router comprising:

means for receiving and transmitting a plurality of packets;

means for assigning a priority class to each of the plurality of packets in such a way that a first threshold value and a second, higher, threshold value is associated with each priority class;

means for selecting an oldest packet from each priority class;

means for determining an estimate of a propagation delay corresponding to at least one packet in a present priority class;

means for lowering a priority of at least one packet if the estimate of the propagation delay of that at least one packet is higher than the second threshold value of the present priority class;

means for selecting at least one packet if the estimate of the propagation delay is higher than the first threshold value of the present priority class, but lower than the second threshold value of the present priority class; and

means for selecting a next priority class.

10. A router in a packet network, the router comprising:

means for defining several priority classes for the packets;

means for defining a first propagation delay threshold value and a second, higher, propagation delay threshold value for each of the several priority classes;

means for selecting from each of the priority classes, an oldest packet;

means for determining an estimate of a propagation delay of at least one of the packets;

means for lowering a priority of at least one packet, if the estimate of the propagation delay associated with that at least one packet is higher than the second threshold value of a present priority class associated with that at least one packet;

means for transmitting at least one packet of the present priority class if the estimate of the propagation delay associated with that at least one packet is higher than the first threshold value but lower than the second threshold value of the present priority class; and

means for selecting a next priority class;

wherein the first threshold value equals an average propagation delay determined for the priority class minus an estimated propagation delay of the packet in other parts of the network, and the second threshold value is a maximum propagation delay defined for the priority class, wherein the maximum propagation delay is based on a delay that a majority of the packets has to fall short of minus the estimated propagation delay of the packet in other parts of the network.

11. The router of claim 10, wherein the router is operable to transmit a predetermined number of packets including the at least one packet, wherein the predetermined number does not exceed a number of packets included in the present priority class.

12. The router of claim 10, wherein the router is operable to perform transmission of the at least one packet until a propagation delay estimate associated with the oldest packet in the present priority class is less than the first threshold value of the present priority class.

13. The router of claim 10, wherein the router is operable to lower the priority of at least one packet by discarding that at least one packet.

14. The router of claim 10, further comprising means for determining the priority class of the at least one packet based on a quality of service of a connection associated with the at least one packet.

15. The router of claim 10, wherein the estimate of the propagation delay of the at least one packet is a moving average of propagation delays of the packets of the present priority class associated with the at least one packet.

16. The router of claim 10, further comprising means for using the propagation delay of the at least one packet as the estimate of the propagation delay associated with that at least one packet.

17. The router of claim 10, wherein the packet network is a General Packet Radio Service GPRS network and the router is at least one of a Serving GPRS Support Node and a GPRS Gateway Support Node node.