Thread based scalable routing for an active router

• US 7,145,913 B2
• Filed: 02/13/2002
• Issued: 12/05/2006
• Est. Priority Date: 02/15/2001
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Polychronopoulos, Constantine, Kim, Hwangnam, Craig, David, Han, Sung-wook, Ha, Sungwon
• Primary Examiner(s): Phunkulh, Bob A.
• Application Number:
  US10/076,203
• Publication Number:
  US 20020114338A1
• Time in Patent Office: 1,756 Days
• Field of Search: None
• US Class Current: 370/401
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

In the present scalable system routing method, received packets are associating with threads for processing the received packets. While a previously received packet is being processed, arrival of an interrupt is checked. If there is an interrupt, a thread is created associating the interrupt is created. Then, a determination of whether the thread associated with the interrupt has a priority that is higher than the priority of a thread associated with the previously received packet is made. If the thread associated with the interrupt has a higher priority than the previously received packet, the thread associated with the previously received packet is saved in a Shared Arena storage area. However, if the thread associated with the interrupt does not have a higher priority than the previously received packet, the thread associated with the interrupt is queued. Because threads are attached to the packets, the threads can now be suspended and resumed without having to disable interrupts, which includes periods during a context switch. As a result, a more flexible and efficient scheduling routing method can be implemented.

Claims

1. A method usable in an active router to route received packets, said method comprising the steps of:

associating threads with received packets for processing the received packets; and

while processing a previously received packet,

checking for the arrival of an interrupt;

creating a thread for associating said interrupt;

determining whether the thread associated with the interrupt has a priority that is higher than the priority of a thread associated with said previously received packet;

if the thread associated with the interrupt has a higher priority than said previously received packet, saving the thread associated with the previously received packet in a Shared Arena storage area;

if the thread associated with the interrupt does not have a higher priority than said previously received packet, queuing the thread associated with the interrupt.

2. The method according to claim 1, wherein the interrupt is an event indicating the arrival of a packet or expiration of a timer.

3. The method according to claim 1, wherein a thread is associated with each received packet or a group of received packets.

4. The method according to claim 1 further comprising a step of processing said thread associated with the interrupt, wherein the Shared Arena is accessible during said step of processing a previously received packet, said step of determining whether the thread associated with the interrupt has a priority that is higher than the priority of a thread associated with said previously received packet, and said step of processing said thread associated with the interrupt.

5. The method according to claim 1, wherein the thread associated with the previously received packet saved in the Shared Arena is preempted by the interrupt having a higher priority, and the processing of the received packet is suspended in the Shared Arena.

6. The method according to claim 1 further comprising the step of processing the interrupt.

7. The method according to claim 6, wherein during said step of processing of the interrupt, further interrupts of lower or equal priority are disabled.

8. The method according to claim 6, wherein when said step of processing of the interrupt has ended, the method further comprises the steps of:

determining whether there is a pending interrupt or thread having a higher priority than the thread saved in the Shared Arena;

if there is a pending interrupt or thread having a higher priority than the thread saved in the Shared Arena, processing the next interrupt or thread; and

,

if there is no next interrupt or thread having a higher priority, resuming the processing of the thread associated with the previously received packet saved in the Shared Arena.

9. The method according to claim 8, wherein prior to resuming the processing of the thread, the method further comprises the step of setting an identifier of a currently running thread.

10. The method according to claim 1, wherein said step of associating threads with received packets further comprises the step of enqueueing said threads to a nonblocking priority run queue accessible for parallel access.

11. The method according to claim 10, wherein said run queue includes an age value and a pointer that are updated with an operation to either add or remove a thread from said run queue, and said age value is used only to ensure one parallel operation at a time and a pointer indicating either an adding or removing of a thread.

12. The method according to claim 10, wherein said run queue is an array of nonblocking Last-In-First-Out (“

LIFO”

) or First-In-First-Out (“

FIFO”

) data structures.

13. A system usable in an active router to route received packets comprising of:

a packet priority level process scheduling threads and processing and routing the packets according to their priority;

an interrupt priority handling process for handling an interrupt and associating threads with received packets and scheduling said packets during a processing of a previously received packet associated to a thread; and

,

a Shared Arena for storing the thread associated with the previously received packet before the processing of the interrupt;

wherein said Shared Arena is a communication mechanism between said packet priority level packet process and said interrupt priority handling process.

14. The system as defined in claim 13 further comprising a nonblocking priority run queue accessible for parallel access.

15. The system as defined in claim 13, wherein the thread saved in the Shared Arena is suspended until the processing of the interrupt has ended.

16. The system as defined in claim 13, wherein the thread saved in the Shared Arena may be resumed when returning to packet priority level processing.

17. The system as defined in claim 16 further comprising a plurality of processors, and the interrupt is processed on one processor and the resumed thread is processed on another processor.

18. A router for routing received packets, said router comprising a set of instructions to:

associating threads with received packets for processing the received packets; and

while processing a previously received packet,

checking for the arrival of an interrupt;

creating a thread for associating said interrupt;

determining whether the thread associated with the interrupt has a priority that is higher than the priority of a thread associated with said previously received packet;

if the thread associated with the interrupt has a higher priority than said previously received packet, saving the thread associated with the previously received packet in a Shared Arena storage area;

if the thread associated with the interrupt does not have a higher priority than said previously received packet, queuing the thread associated with the interrupt.