System for and method of differentiated queuing in a routing system

• US 20020191622A1
• Filed: 06/18/2001
• Published: 12/19/2002
• Est. Priority Date: 06/18/2001
• Status: Active Grant

• Current Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Zdan, Michael A.
• Granted Patent: US 7,020,143 B2
• Time in Patent Office: Days
• US Class Current: 370/401
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service

Abstract

The invention relates to a method for routing Internet traffic. The method generally includes the steps of receiving a packet from multimedia network, allocating a message block header for the packet, wherein the header is used to hold behavior aggregate values for internal router mapping, and queuing and routing the packet to a differentiated services network domain in a manner that ensures a specific QoS.

Claims

1. A method of routing packets within a communication system, comprising the steps of:

receiving a packet from a communications network;

allocating a message block header within said received packet;

associating a predefined default value for said message block header;

identifying a quality-of-service value associated with said received packet;

metering the received packet to determine whether resources are available to properly route the packet while complying with a service level agreement associated with said classified qualify-of-service;

in response to a determination that said packet cannot be routed in compliance with said service level agreement, dropping said packet;

otherwise, routing said packet

2. The method of claim 1 further comprising the steps of:

determining whether said identified quality-of-service value is different than said associated predefined default value for said message block header; and

in response to said determination, overwriting said message block header with said identified quality-of-service value.

3. The method of claim 1 wherein said step of routing said packet further comprises the steps of:

determining whether an outgoing device driver is available for said quality-of-service value; and

in response to a determination that said outgoing device driver is unavailable, queuing said packet within one of a plurality of primary queues associated with said identified quality-of-service value.

4. The method of claim 3 wherein said step of queuing said packet further comprises the steps of:

assigning a predefined threshold value with each of said plurality of primary queues;

monitoring each of said plurality of primary queues to determine whether the capacity level associated with said queue exceeds said predefined threshold value; and

queuing any additional packets, in response to said determination, to one of a plurality of secondary queues associated with said identified quality-of-service value.

5. The method of claim 4 wherein certain of said plurality of secondary queues are assigned to one of said plurality of primary queues.

6. The method of claim 5 wherein one of said plurality of secondary queues is an expedited forwarding queue, further comprising the steps of queuing said packet identified as expedited forwarding value within said expedited forwarding queue.

7. The method of claim 3 wherein said plurality of primary queues comprises of:

a high priority egress queue;

a medium priority egress queue; and

a low priority egress queue.

8. The method of claim 1 wherein packets identified with particular one of said quality-of-service value is guaranteed a predefined bandwidth within said communication system.

9. A packet router within a packet communication network for providing differentiated services based on a service level agreement associated with a plurality of incoming packets to be processed and routed within said packet router, comprising:

a ingress driver for receiving said plurality of incoming packets;

a classifier coupled to said ingress driver for classifying each of said plurality of packets with a particular behavior aggregate value wherein said behavior aggregate value is indicative of the internal routing treatment to be provided by said packet router for said each packet;

a meter coupled to said classifier for evaluating some of said plurality of packets and discarding certain ones of said packets wherein the service level agreement associated with said identified behavior aggregate value cannot be guaranteed;

a differentiated queuing block coupled to said meter and said classifier for handling said plurality of packets; and

a egress driver coupled to said differentiated queuing block for transmitting some of said plurality of packets over said packet communications network.

10. The packet router of claim 9 wherein said ingress driver further comprises means for allocating a message block header for each of said packets for storing said behavior aggregate value.

11. The packet router of claim 10 wherein said egress driver comprises means for stripping said message block header within each of said packets before transmitting each of said packet over said communications network.

12. The packet router of claim 10 wherein said classifier further comprises a table for mapping a differentiated services code point (DSCP) stored within each of said packets to an associated behavior aggregate value and means for storing said behavior aggregate value within said message block header.

13. The packet router of claim 9 wherein said classifier further comprises a filter for determining whether particular ones of said plurality of packets need to be evaluated by said meter and forwarding such determined packets to said meter.

14. The packet router of claim 9 wherein said differentiated queuing block further comprises a plurality of primary queues for queuing some of said packets when resources within said egress driver are not available.

15. The packet router of claim 14 wherein some of said packets are classified as expedited forwarding, assured forwarding or best efforts forwarding and wherein said plurality of primary queues further comprises:

a high priority egress queue for queuing packets that are classified expedited forwarding;

a medium priority egress queue for queuing packets that are classified assured forwarding; and

a low priority egress queue for queuing packets that are classified best effort forwarding.

16. The packet router of claim 15 wherein said differentiated queuing block further comprises a plurality of secondary queues for queuing some of said packets when certain one of said primary queues exceeds a predefined threshold content value.

17. The packet router of claim 16 wherein said plurality of secondary queues further comprises:

an expedite forwarding queue for queuing packets that are classified expedited forwarding;

an assured forwarding queue for queuing packets that are classified assured forwarding; and

a best effort queue for queuing packets that are classified best efforts forwarding.

18. The packet router of claim 17 wherein each of said secondary queues further comprises a token bucket meter for keeping track of the bandwidth rate available for said associated behavior aggregate value.

20. The apparatus of claim 19 wherein said means for routing said packet further comprises:

a plurality of primary queues;

means for determining whether an outgoing device driver is available; and

in response to a determination that said outgoing device driver is unavailable, means for queuing said packet within one of said plurality of primary queues.

21. The apparatus of claim 20 wherein said means for queuing further comprises:

a plurality of secondary queues;

means for assigning a predefined threshold value with each of said plurality of primary queues;

means for monitoring each of said plurality of primary queues to determine whether the capacity level associated with said queue exceeds said predefined threshold value; and

means for queuing any additional packets, in response to said determination, to one of said plurality of secondary queues.

22. The apparatus of claim 21 wherein certain of said plurality of secondary queues are assigned to particular one of said plurality of primary queues.

23. The apparatus of claim 21 wherein said plurality of secondary queues comprises:

an expedited forwarding queue;

an assured forwarding queue; and

a best effort queue.

24. The apparatus of claim 20 wherein said plurality of primary queues further comprises:

a high priority egress queue;

a medium priority egress queue; and

a low priority egress queue.

19. An apparatus for providing differentiated service routing within a packet communication system, comprising the steps of:

means for receiving a packet from a communications network;

means for allocating a message block header within each of said received packet;

means for assigning behavior aggregate value for each of said received packets;

means for metering some of said received packets to determine whether resources are available to properly route said packets while complying with a service level agreement associated with said behavior aggregate value;

in response to a determination that a particular packet cannot be routed in compliance with said service level agreement,

means for dropping said packet;

otherwise, means for routing said packet.