Method and system for pipelining packet selection
View Patent ↗A method for selecting packets comprises pipelining execution of packet selection processes so that execution of each of the packet selection processes occurs at different levels of a scheduling hierarchy. At least two different packets are selected at two different times in response to execution of the packet selection processes.
1. A method for selecting packets comprising:
initiating a first packet selection process at a first time slot;
initiating a second packet selection process at a second time slot immediately following the first time slot such that execution of the second packet selection process overlaps execution of the first packet selection process at different levels of a scheduling hierarchy;
selecting a first packet at a third time slot in response to the first packet selection process; and
selecting a second packet at a fourth time slot in response to the second packet selection process, the fourth time slot immediately following the third time slot,
wherein each of the first packet selection process and the second packet selection process comprises two or more subprocesses executed to select the first packet and the second packet respectively, and
wherein at least one of the subprocesses in the first packet selection process is different from the subprocesses in the second packet selection process.
2. The method of claim 1 , wherein the first and second packets are selected based on an arrival time of the first and second packets at a corresponding egress queue and a departure time of a previous packet at the corresponding egress queue from a data flow associated with the first and second packets respectively.
3. The method of claim 1 , wherein each of the two or more subprocesses in the first packet selection process and in the second packet selection process is executed in one time slot.
4. The method of claim 3 , wherein each of the two or more subprocesses in the first packet selection process and in the second packet selection process is executed at a different level of the scheduling hierarchy.
5. The method of claim 1 , wherein when a subprocess is selected by the first packet selection process, it is locked and cannot be selected by the second packet selection process.
6. The method of claim 5 , wherein the subprocess is selected from one or more subprocesses at a same level of the scheduling hierarchy by sorting the one or more subprocesses at that level based on a selection criteria.
7. A method for selecting packets comprising:
initiating a first packet selection process at a first time slot;
initiating a second packet selection process at a second time slot immediately following the first time slot such that execution of the second packet selection process overlaps execution of the first packet selection process at different levels of a scheduling hierarchy;
selecting a first packet at a third time slot in response to the first packet selection process; and
selecting a second packet at a fourth time slot in response to the second packet selection process, the fourth time slot immediately following the third time slot,
wherein each of the first packet selection process and the second packet selection process comprises two or more subprocesses executed to select the first packet and the second packet respectively,
wherein when a subprocess is selected by the first packet selection process, it is locked and cannot be selected by the second packet selection process,
wherein the subprocess is selected from one or more subprocesses at a same level of the scheduling hierarchy by sorting the one or more subprocesses at that level based on a selection criteria, and
wherein the selection criteria is one selected in a group comprising an arrival time and a contracted rate.
8. A computer readable medium having stored thereon sequences of instructions which are executable by a system, and which, when executed by the system, cause the system to:
initiate a first packet selection process at a first time slot;
initiate a second packet selection process at a second time slot immediately following the first time slot such that execution of the second packet selection process overlaps execution of the first packet selection process at different levels of a scheduling hierarchy;
select a first packet at a third time slot in response to the first packet selection process; and
select a second packet at a fourth time slot in response to the second packet selection process, the fourth time slot immediately following the third time slot,
wherein each of the first packet selection process and the second packet selection process comprises two or more subprocesses executed to select the first packet and the second packet respectively, and
wherein at least one of the subprocesses in the first packet selection process is different from the subprocesses in the second packet selection process.
9. The computer readable medium of claim 8 , wherein the first and second packets are selected based on an arrival time of the first and second packets at a corresponding egress queue and a departure time of a previous packet at the corresponding egress queue from a data flow associated with the first and second packets respectively.
10. The computer readable medium of claim 8 , wherein each of the two or more subprocesses in the first packet selection process and in the second packet selection process is executed in one time slot.
11. The computer readable medium of claim 10 , wherein each of the two or more subprocesses in the first packet selection process and in the second packet selection process is executed at a different level of the scheduling hierarchy.
12. The computer readable medium of claim 8 , wherein when a subprocess is selected by the first packet selection process, it is locked and cannot be selected by the second packet selection process.
13. The computer readable medium of claim 12 , wherein the subprocess is selected from one or more subprocesses at a same level of the scheduling hierarchy by sorting the one or more subprocesses at that level based on a selection criteria.
14. A computer readable medium having stored thereon sequences of instructions which are executable by a system, and which, when executed by the system, cause the system to:
initiate a first packet selection process at a first time slot;
initiate a second packet selection process at a second time slot immediately following the first time slot such that execution of the second packet selection process overlaps execution of the first packet selection process at different levels of a scheduling hierarchy;
select a first packet at a third tine slot in response to the first packet selection process; and
select a second packet at a fourth time slot in response to the second packet selection process, the fourth time slot immediately following the third time slot,
wherein when a subprocess is selected by the first packet selection process, it is locked and cannot be selected by the second packet selection process,
wherein the subprocess is selected from one or more subprocesses at a same level of the scheduling hierarchy by sorting the one or more subprocesses at that level based on a selection criteria, and
wherein the selection criteria is one selected in a group comprising an arrival time and a contacted rate.
15. A system, comprising:
a switch fabric; and
an egress coupled with the switch fabric to
initiate a first packet selection process at a first time slot,
initiate a second packet selection process at a second time slot immediately following the first time slot such that execution of the second packet selection process overlaps execution of the first packet selection process at different levels of a scheduling hierarchy,
select a first packet at a third time slot in response to the first packet selection process, and
select a second packet at a fourth time slot in response to the second packet selection process, the fourth time slot immediately following the third time slot,
wherein each of the first packet selection process and the second packet selection process comprises two or more subprocesses executed to select the first packet and the second packet respectively, and
wherein at least one of the subprocesses in the first packet selection process is different from the subprocesses in the second packet selection process.
16. The system of claim 15 , wherein the first and second packets are selected based on an arrival time of the first and second packets at a corresponding egress queue and a departure time of a previous packet at the corresponding egress queue from a data flow associated with the first and second packets respectively.
17. The system of claim 15 , wherein each of the two or more subprocesses in the first packet selection process and in the second packet selection process is executed in one time slot.
18. The system of claim 17 , wherein each of the two or more subprocesses in the first packet selection process and in the second packet selection process is executed at a different level of the scheduling hierarchy.
19. The system of claim 15 , wherein when a subprocess is selected by the first packet selection process, it is locked and cannot be selected by the second packet selection process.
20. The system of claim 19 , wherein the subprocess is selected from one or more subprocesses at a same level of the scheduling hierarchy by sorting the one or more subprocesses at that level based on a selection criteria.
21. A system, comprising:
a switch fabric; and
an egress coupled with the switch fabric to
initiate a first packet selection process at a first time slot,
initiate a second packet selection process at a second time slot immediately following the first time slot such that execution of the second packet selection process overlaps execution of the first packet selection process at different levels of a scheduling hierarchy,
select a first packet at a third time slot in response to the first packet selection process, and
select a second packet at a fourth time slot in response to the second packet selection process, the fourth time slot immediately following the third time slot,
wherein each of the first packet selection process and the second packet selection process comprises two or more subprocesses executed to select the first packet and the second packet respectively,
wherein when a subprocess is selected by the first packet selection process, it is locked and cannot be selected by the second packet selection process,
wherein the subprocess is selected from one or more subprocesses at a same level of the scheduling hierarchy by sorting the one or more subprocesses at that level based on a selection criteria, and
wherein the selection criteria is one selected in a group comprising an arrival time and a contracted rate.