Packet prioritization processing technique for routing traffic in a packet-switched computer network

• US 6,798,743 B1
• Filed: 03/22/1999
• Issued: 09/28/2004
• Est. Priority Date: 03/22/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Berl, Steven, Ma, Qingming, Shi, Zhanhe, Agasaveeran, Saravanan
• Primary Examiner(s): Duong, Frank
• Application Number:
  US09/274,091
• Time in Patent Office: 2,017 Days
• Field of Search: 370/229, 370/230, 370/231, 370/235, 370/351, 370/389, 370/395.21, 370/395.32, 370/395.4, 370/395.41, 370/395.42, 370/412-419, 370/400, 370/468, 370/477
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A two-phase packet processing technique is provided for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes. During Phase I, packets are retrieved from the router input interface and classified in order to identify the associated priority level of each packet and/or to determine whether a particular packet is delay-sensitive. If it is determined that a particular packet is delay-sensitive, the packet is immediately and fully processed. If, however, it is determined that the packet is not delay-sensitive, full processing of the packet is deferred and the packet is stored in an intermediate data structure. During Phase II, packets stored within the intermediate data structure are retrieved and fully processes. The technique of the present invention significantly reduces packet processing latency, particularly with respect to high priority or delay-sensitive packets. It is easily implemented in conventional routing systems, imposes little computational overhead, and consumes only a limited amount of memory resources within such systems.

Claims

1. A method for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the network including at least one router, the router including at least one input interface having at least one input interface and at least one output inter, the method comprising:

preprocessing a first packet from said input interface to determine if said fast packet is delay sensitive, wherein said preprocessing includes classifying said fist packet;

storing said first packet in an intermediate data structure before fully processing said first packet in response to a determination that said first packet is not delay sensitive, said intermediate data structure being used for queuing packets which have been preprocessed but which have not yet been processed sufficiently to be routed to an output interface queue;

preprocessing a second packet from said input interface while said first packet is queued in said intermediate data structure; and

fully processing said second packet while said first packet is queued in said intermediate data structure in response to a determination that said second packet is delay sensitive, said fully processing including processing said second packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

2. The method of claim 1 further comprising fully processing said first packet in response to a determination that the first packet is delay sensitive, said fully processing including processing said first packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

3. The method of claim 1 further comprising storing said second packet in said intermediate data structure, before fully processing said second packet, in response to a determination that said second packet is not delay sensitive.

4. The method of claim 1 wherein fully processing includes Forwarding Information Base (FIB) look-up processing.

5. The method of claim 4 further including:

retrieving said first packet from said intermediate data structure;

fully processing said first packet; and

storing the fully processed first packet into an appropriate output interface queue.

6. The method of claim 1 wherein said preprocessing includes determining an associated priority level of said first and second packets.

7. The method of claim 6 wherein a packet is determined to be delay sensitive if the associated priority level of the packet is at least of priority P, and wherein the packet is determined not to be delay sensitive if the associated priority level of the packet is less than priority P.

8. The method of claim 7 wherein said priority P is a highest priority.

9. The method of claim 6 wherein said storing includes storing said first packet in said intermediate data structure in an order based upon an associated priority level of said first packet.

10. The method of claim 1 further including checking each respective input interface line at least once for packets to preprocess before retrieving and processing packets from said intermediate data structure.

11. The method of claim 1 further including preprocessing additional packets from said input interface after a desired number of packets from said intermediate data structure have been retrieved and fully processed.

12. The method of claim 1 further including retrieving and fully processing packets queued in said intermediate data structure after a desired number of packets from said input interface have been preprocessed.

13. The method of claim 12 further comprising continuing to retrieve and fully process packets queued in said intermediate data structure if:

said desired number of packets from said input interface have been processed, and

an interrupt signal indicating an arrival of additional packets at said input interface is not received.

14. The method of claim 12 wherein said retrieving includes retrieving and processing packets from sail intermediate data structure in an order relating to each packet'"'"'s associated priority level.

15. The method of claim 1 further comprising preprocessing additional packets from said input interface if:

an interrupt signal is received indicating an arrival of additional packets at said input interface, and

a desired number of packets from said intermediate data structure have been retrieved and fully processed.

16. The method of claim 1 wherein the intermediate data structure comprises a plurality of queues, and wherein each of the plurality of queues is associated with a respective priority level.

17. A computer program product for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the network including at least one router, the router including at least one input interface having at least one input interface and at least one output interface, the computer program product comprising:

a computer usable medium having computer readable code embodied therein, the computer readable code comprising;

computer code for preprocessing a first packet from said input interface to determine if said first packet is delay sensitive, wherein said preprocessing includes classifying said first packet;

computer code for storing said first packet in an intermediate data structure before fully processing said first packet in response to a determination that said first packet is not delay sensitive, said intermediate data structure being used for queuing packets which have been preprocessed but which have not yet been processed sufficiently to be routed to an output interface queue;

computer code for preprocessing a second packet from said input interface while said first packet is queued in said intermediate data structure; and

computer code for fully processing said second packet while said first packet is queued in said intermediate data structure in response to a determination that said second packet is delay sensitive, said fully processing computer code including processing said second packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

18. The computer program product of claim 17 further comprising computer code for fully processing said first packet in response to a determination that the first packet is delay sensitive, said fully processing computer code including computer code for processing said first packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

19. The computer program product of claim 17 further comprising computer code for storing said second packet in said intermediate data structure, before fully processing said second packet, in response to a determination that said second packet is not delay sensitive.

20. The computer program product of claim 17 wherein fully processing computer code includes computer code for Forwarding Information Base (FIB) lookup processing.

21. The computer program product of claim 20 further including:

computer code for retrieving said first packet from said intermediate data structure;

computer code for fully processing said first packet; and

computer code for storing the fully processed first packet into an appropriate output interface queue.

22. The computer program product of claim 17 wherein said preprocessing computer code includes determining an associated priority level of said first and second packets.

23. The computer program product of claim 22 wherein a packet is determined to be delay sensitive if the associated priority level of the packet is at least of priority P, and wherein the packet is determined not to be delay sensitive if the associated priority level of the packet is less than priority P.

24. The computer program product of claim 23 wherein said priority P is a highest priority.

25. The computer program product of claim 22 wherein said storing computer code includes computer code for storing said first packet in said intermediate data structure in an order based upon an associated priority level of said first packet.

26. The computer program product of claim 17 further including computer code for checking each respective input interface line at least once for packets to preprocess before retrieving and processing packets from said intermediate data structure.

27. The computer program product of claim 17 further including computer code for preprocessing additional packets from said input interface after a desired number of packets from said intermediate data structure have been retrieved and fully processed.

28. The computer program product of claim 17 further including computer code for retrieving and fully processing packets queued in said intermediate data structure after a desired number of packets from said input interface have been preprocessed.

29. The computer program product of claim 28 further comprising computer code for continuing to retrieve and fully process packets queued in said intermediate data structure if:

said desired number of packets from said input interface have been processed, and

an interrupt signal indicating an arrival of additional packets at said input interface is not received.

30. The computer program product of claim 28 wherein said retrieving computer code includes computer code for retrieving and processing packets from said intermediate data structure in an order relating to each packet'"'"'s associated priority level.

31. The computer program product of claim 17 further comprising computer code for preprocessing additional packets from said input interface if:

an interrupt signal is received indicating an arrival of additional packets at said input interface, and

a desired number of packets from said intermediate data structure have been retrieved and fully processed.

32. The computer program product of claim 17 wherein the intermediate data structure comprises a plurality of queues, and wherein each of the plurality of queues is associated with a respective priority level.

33. A router for routing traffic in a packet-switched integrated services network which supports a plurality of different service classes, the router comprising:

a processor;

at least one input interface;

at least one output interface; and

memory having at least one intermediate data structure;

the router being configured or designed to preprocess a first packet from said input interface to determine if said first packet is delay sensitive, wherein said preprocessing includes classifying said first packet;

the router being configured or designed to store said first packet in an intermediate data structure before fully processing said first packet in response to a determination that said first packet is not delay sensitive, said intermediate data structure being used for queuing packets which have been preprocessed but which have not yet been processed sufficiently to be routed to an output interface queue;

the router be configured or designed to preprocess a second packet from said input interface while said first packet is queued in said intermediate data structure; and

the router being configured or designed to fully process said second packet, while said first packet is queued in said intermediate data structure, in response to a determination that said second packet is delay sensitive, said fully processing including processing said second packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

34. The router of claim 33 wherein the router is further configured or designed to fully process said first packet in response to a determination that the first packet is delay sensitive, said fully processing including processing said first packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

35. The router of claim 33 wherein the router is further configured or designed to store said second packet in said intermediate data structure, before fully processing said second packet, in response to a determination that sad second packet is not delay sensitive.

36. The router of claim 33 wherein fully processing includes Forwarding Information Base (FIB) look-up processing.

37. The router of claim 36 wherein the router is further configured or designed to:

retrieve said first packet from said intermediate data structure;

fully process said first packet; and

store the fully processed first packet into an appropriate output interface queue.

38. The router of claim 33 wherein said preprocessing includes determining an associated priority level of said first and second packets.

39. The router of claim 38 wherein a packet is determined to be delay sensitive if the associated priority level of the packet is at least of priority P, and wherein the packet is determined not to be delay sensitive if the associated priority level of the packet is less than priority P.

40. The router of claim 39 wherein said priority P is a highest priority.

41. The router of claim 38 wherein said storing includes storing said first packet in said intermediate data structure in an order based upon an associated priority level of said first packet.

42. The router of claim 33 wherein the router is further configured or designed to check each respective input interface line at least once for packets to preprocess before retrieving and processing packets from said intermediate data structure.

43. The router of claim 33 wherein the router is further configured or designed to preprocess additional packets from said input interface after a desired number of packets from said intermediate da structure have been retrieved and fully processed.

44. The router of claim 33 wherein the router is further configured or designed to retrieve and fully process packets queued in said intermediate data structure after a desired number of packets from said input interface have been preprocessed.

45. The router of claim 44 wherein the router is further configured or designed to continuing to retrieve and fully process packets queued in said intermediate data

said desired number of packets from said input interface have been processed, and

an interrupt signal indicating an arrival of additional packets at said input interface is not received.

46. The router of claim 44 wherein said retrieving includes retrieving and processing packets from said intermediate data structure in an order relating to each packet'"'"'s associated priority level.

47. The router of claim 33 wherein the router is further configured or designed to preprocess additional packets from said input interface if:

an interrupt signal is received indicating an arrival of additional packets at said input interface, and

a desired number of packets from said intermediate data structure have been retrieved and fully processed.

48. The router of claim 33 wherein the intermediate data structure comprises a plurality of queues, and wherein each of the plurality of queues is associated with a respective priority level.

49. A system for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the network including at least one router, the router including at least one input interface having at least one input interface and at least one output interface, the system comprising:

means for preprocessing a first packet from said input interface to determine if said first packet is delay sensitive, wherein said preprocessing includes classifying said first packet;

means for storing said first packet in an intermediate data structure before fully processing said first packet in response to a determination that said first packet is not delay sensitive, said intermediate data structure being used for queuing packets which have been preprocessed but which have not yet been processed sufficiently to be routed to au output interface queue;

means for preprocessing a second packet from said input interface while said first packet is queued in said intermediate data structure; and

means for fully processing said second packet while said first packet is queued in said intermediate data structure in response to a determination that said second packet is delay sensitive, said fully processing means including processing said second packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

50. The system of claim 49 further comprising means for fully processing said first packet in response to a determination that the first packet is delay sensitive, said fully processing means including means for processing said first packet sufficiently to enable the second packet to be routed to an appropriate output interface queue.

51. The system of claim 49 further comprising means for storing said second packet in said intermediate data structure, before fully processing said second packet, in response to a determination that said second packet is not delay sensitive.

52. The system of claim 49 wherein the intermediate data structure comprises a plurality of queues, and wherein each of the plurality of queues is associated with a respective priority level.