Packet prioritization processing technique for routing traffic in a packet-switched computer network
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
52 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
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. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
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. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
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. - View Dependent Claims (50, 51, 52)
-
Specification