Variable resolution scheduler for virtual channel communication devices

• US 6,208,661 B1
• Filed: 01/07/1998
• Issued: 03/27/2001
• Est. Priority Date: 01/07/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Marshall, John William
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Pezzlo, John
• Application Number:
  US09/004,089
• Time in Patent Office: 1,175 Days
• Field of Search: 370/395, 370/397, 370/412, 370/466, 370/311, 370/229, 370/218, 370/352, 709/100
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The present invention provide for scheduling protocol data units for transmission on a virtual channel. The scheduling is accomplished by first determining a relative theoretical departure time for a protocol data unit. Departure times are identified in each of a plurality of time domains based upon the relative theoretical departure time for the protocol data unit. An identified departure times is selected from a time domain and the protocol data unit is scheduled for transmission during the selected available departure time.

Claims

1. A method of scheduling protocol data units for transmission on a virtual channel, the method comprising the steps of:

determining a relative theoretical departure time for a protocol data unit to be transmitted;

selecting a departure time from one of a series of immediate departure times in an immediate time domain for transmission of the protocol data unit if it is determined that the relative theoretical departure time is included in the immediate time domain and a protocol data unit has not been previously scheduled for transmission at the departure time;

determining if the relative theoretical departure time corresponds to a reserved departure time in a later time domain that follows the immediate time domain if the determined relative theoretical departure time is included in the later time domain, wherein the reserved departure time is reserved from scheduling;

selecting a departure time other than the reserved departure time from available departure times in the later time domain if it is determined that the relative theoretical departure time corresponds to a reserved departure time in the later time domain; and

scheduling the protocol data unit for transmission during the selected departure time.

2. A method according to claim 1 further comprising the step of reserving departure times in the later time domain based upon a porosity associated with the later time domain.

3. A method according to claim 2, wherein said step of reserving departure times in the later time domain comprises the step of storing only unreserved departure times within the later time domain.

4. A method according to claim 3, wherein said step of storing comprises the step of storing only unreserved departure times within each time domain by storing context information for the virtual channels.

5. A method according to claim 1, further comprising the step of designating as used the selected departure time.

6. A method according to claim 1, wherein said step of determining comprises the step of identifying as available an unreserved and unused departure time closest in time to the corresponding relative theoretical departure time in the later time domain.

7. A method according to claim 1, wherein said step of selecting a departure time from one of a series of immediate departure times comprises the step of identifying as available an unused departure time closest in time to the corresponding relative theoretical departure time in the immediate time domain.

8. The method of claim 1, further comprising the step of requesting a departure time with a corresponding relative theoretical departure time, wherein the requests are made by a plurality of controllers each using a different control process.

9. The method of claim 1, wherein said step of determining a relative theoretical departure time for a protocol data unit comprises the step of determining a relative theoretical departure time for a protocol data unit, wherein the protocol data unit originates from one of a plurality of virtual channels each having similar priority.

10. A method according to claim 9, wherein said step of determining a relative theoretical departure time for a protocol data unit, wherein the protocol data unit originates from one of a plurality of virtual channels each having similar priority comprises the step of resolving substantially simultaneous requests for a common departure time from different controllers by providing a Relative Maximum Departure Time for each request which indicates the latest departure time allowed by each controller for the corresponding request.

11. A method according to claim 1, wherein the series of later departure times follows the series of immediate departure times in a time progression over which the immediate and later series of departure times are shifted towards a transmission time so that the later departure times transition to the immediate time domain whereupon unscheduled reserved departure times in the later time domain are made available for scheduling in the immediate time domain.

12. A method according to claim 1, wherein the series of later departure times follows the series of immediate departure times in a time progression over which the immediate and later series of departure times are shifted towards a transmission time so that the later departure times transition to the immediate time domain whereupon scheduled unreserved departure times in the later time domain are made unavailable for scheduling in the immediate time domain.

13. A system for scheduling protocol data units for transmission on a virtual channel, the method comprising:

means for determining a relative theoretical departure time for a protocol data unit to be transmitted;

means for selecting a departure time from one of a series of immediate departure times in an immediate time domain for transmission of the protocol data unit if it is determined that the relative theoretical departure time is included in the immediate time domain and a protocol data unit has not been previously scheduled for transmission at the departure time;

means for determining if the relative theoretical departure time corresponds to a reserved departure time in a later time domain that follows the immediate time domain if the relative theoretical departure time is included in the later time domain, wherein the reserved departure time is reserved from scheduling;

means for selecting a departure time other than the reserved departure time from available departure times in the later time domain if it is determined that the relative theoretical departure time corresponds to a reserved departure time in the later time domain; and

means for scheduling the protocol data unit for transmission during the selected departure time.

14. The system of claim 13 further comprises means for reserving departure times in the later time domain based upon a porosity associated with the later time domain.

15. The system of claim 13, wherein said means for determining comprises means for identifying as available an unreserved and unused departure time closest in time to the corresponding relative theoretical departure time in the later time domain.

16. The system of claim 13, wherein said means for selecting a departure time from one of a series of immediate departure times comprises means for identifying as available an unused departure time closest in time to the corresponding relative theoretical departure time in the immediate time domain.

17. The system of claim 13, further comprising means for requesting a departure time with a corresponding relative theoretical departure time, wherein the requests are made by a plurality of controllers each using a different control process.

18. The system of claim 17, wherein said means for requesting a departure time comprises a means for providing a common interface between means for identifying, selecting and scheduling and the plurality of controllers.

19. The system of claim 13, wherein said means for determining a relative theoretical departure time for a protocol data unit comprises means for determining a relative theoretical departure time for a protocol data unit, wherein the protocol data unit originates from one of a plurality of virtual channels each having similar priority.

20. A system according to claim 13, wherein the series of later departure times follows the series of immediate departure times in a time progression over which the immediate and later series of departure times are shifted towards a transmission time so that the later departure times transition to the immediate time domain whereupon unscheduled reserved departure times in the later time domain are made available for scheduling in the immediate time domain.

21. A system according to claim 13, wherein the series of later departure times follows the series of immediate departure times in a time progression over which the immediate and later series of departure times are shifted towards a transmission time so that the later departure times transition to the immediate time domain whereupon scheduled unreserved departure times in the later time domain are made unavailable for scheduling in the immediate time domain.

22. A computer program product for scheduling protocol data units for transmission on a virtual channel comprising:

a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer readable program code means for determining a relative theoretical departure time for a protocol data unit to be transmitted;

computer readable program code means for selecting a departure time from one of a series of immediate departure times in an immediate time domain for transmission of the protocol data unit if it is determined that the relative theoretical departure time is included in the immediate time domain and a protocol data unit has not been previously scheduled for transmission at the departure time;

computer readable program code means for determining if the relative theoretical departure time corresponds to a reserved departure time in a later time domain that follows the immediate time domain if the determined relative theoretical departure time is included in the later time domain, wherein the reserved departure time is reserved from scheduling;

computer readable program code means for selecting a departure time other than the reserved departure time from available departure times in the later time domain if it is determined that the relative theoretical departure time corresponds to a reserved departure time in the later time domain; and

computer readable program code means for scheduling the protocol data unit for transmission during the selected departure time.

23. The computer program product according to claim 22, further comprises computer readable program means for reserving departure times in the later time domain based upon a porosity associated with the later time domain.

24. The computer program product according to claim 22, wherein said computer readable program means for determining comprises computer readable program means for identifying as available an unreserved and unused departure time closest in time to the corresponding relative theoretical departure time in the later time domain.

25. The computer program product according to claim 22, wherein said computer readable program means for selecting a departure time from one of a series of immediate departure times comprises computer readable program means for identifying as available an unused departure time closest in time to the corresponding relative theoretical departure time in the immediate time domain.

26. The computer program product according to claim 22, further comprising computer readable program means for requesting a departure time with a corresponding relative theoretical departure time, wherein the requests are made by a plurality of controllers each using a different control process.

27. The computer program product according to claim 22, wherein said computer readable program means for determining a relative theoretical departure time for a protocol data unit comprises computer readable program means for determining a relative theoretical departure time for a protocol data unit, wherein the protocol data unit originates from one of a plurality of virtual channels each having similar priority.

28. A computer program product according to claim 22, wherein the series of later departure times follows the series of immediate departure times in a time progression over which the immediate and later series of departure times are shifted towards a transmission time so that the later departure times transition to the immediate time domain whereupon unscheduled reserved departure times in the later time domain are made available for scheduling in the immediate time domain.

29. A computer program product according to claim 22, wherein the series of later departure times follows the series of immediate departure times in a time progression over which the immediate and later series of departure times are shifted towards a transmission time so that the later departure times transition to the immediate time domain whereupon scheduled unreserved departure times in the later time domain are made unavailable for scheduling in the immediate time domain.