Hardware implementation of channel scheduling algorithms for optical routers with FDL buffers

• US 6,804,255 B1
• Filed: 10/12/2000
• Issued: 10/12/2004
• Est. Priority Date: 10/12/2000
• Status: Expired due to Fees

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Zheng, Si Qing, Xiong, Yijun, Vandenhoute, Marc L. J.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ferris, Derrick W
• Application Number:
  US09/689,584
• Time in Patent Office: 1,461 Days
• Field of Search: 370/351, 370/352, 370/355, 370/357, 370/386, 370/401, 370/464, 370/465, 370/437, 370/468, 398/45, 398/48, 398/49, 398/51, 398/52, 398/53, 398/54
• US Class Current: 370/468
• CPC Class Codes: H04Q 11/0062 Network aspects
• CPC Class Codes: H04Q 11/0071 Provisions for the electrical-optical layer interface
• CPC Class Codes: H04Q 2011/0064 Arbitration, scheduling or medium access control aspects

Abstract

A system and method for implementing channel scheduling algorithms in an optical router wherein a scheduler operates pursuant to an algorithm and is capable of determining the availability of outbound data channels capable of carrying a data packet of duration B. The scheduler is further capable of selecting one channel from available data channels and assigning the data packet to the selected channel. The scheduler then updates state information of the selected data channel, but if no data channel is available to carry the data packet the data packet is dropped.

Claims

1. A method for implementing channel scheduling algorithms in an optical router, the method comprising the steps of:

storing a set of channel unscheduled times from which a channel is free and corresponding channels S_M at an associative process P_M;

storing a set of voids/gaps and a corresponding channels S_G at an associative processor P_G;

determining availability of outbound data channels capable of carrying a data packet of duration B;

selecting one channel from available data channels;

assigning the data packet to the selected channel; and

updating state information of the selected data channel, wherein the state information of a data channel includes channel unscheduled times for which the data channel has voids/gaps.

2. The method for implementing channel scheduling algorithms in an optical router according to claim 1, further including the steps of:

if no data channel is available to carry the data packet, determining whether a time delay L is capable of being introduced to shift the arrival time of the data packet via fiber delay line (FDL), from t to (t+L); and

if a time delay L is capable of being introduced, assigning the data packet a delay time equal to L and assigning the data packet to an appropriate outbound data channel.

3. The method for implementing channel scheduling algorithms in an optical router according to claim 1, wherein the selecting of a channel further comprises selecting a fiber and a wavelength from the outbound data channel group to transmit the data packet.

4. The method for implementing channel scheduling algorithms in an optical router according to claim 1, wherein the data packet is of a variable length.

5. The method for implementing channel scheduling algorithms in an optical router according to claim 2, wherein the selecting of a channel further comprises selecting a fiber and a wavelength from the outbound data channel group to transmit the data packet.

6. The method for implementing channel scheduling algorithms in an optical router according to claim 2, wherein the data packet is of a variable length.

7. The method for implementing channel scheduling algorithms in an optical router according to claim 1, wherein scheduled time of routing for each data packet that has not been transmitted is scheduled with a relative time based upon the start processing time of the data packet.

8. The method for implementing channel scheduling algorithms in an optical router according to claim 1, wherein if a void created by the insertion of a data packet on a channel is less than or equal to a duration Δ

the void is not included in the state information as being available to carry a data packet.

9. The method for implementing channel scheduling algorithms in an optical router according to claim 1, further comprising performing a parallel search of the set of voids/gaps and the corresponding channels S_G at associative process P_G for the smallest available void/gap and the corresponding channel capable of accommodating a packet of duration B.

10. The method for implementing channel scheduling algorithms in an optical router according to claim 9, further comprising performing a parallel search of the set of channel unscheduled times from which the channel is free and the corresponding channels S_M at associative processor P_M for an unscheduled time and corresponding data channel.

11. The method of claim 10, further comprising the step of generating control signals for associative processors P_M and P_G at a control processor.

12. An apparatus for implementing channel scheduling algorithms in an optical router, the apparatus comprising:

means for determining availability of outbound data channels capable of carrying a data packet of duration B, wherein such means for determining availability comprises;

an associative processor P_G capable of storing a set of voids/gaps and corresponding channels S_G and performing a parallel search of the set of voids/gaps and corresponding channels S_G for an available void/gap and corresponding channel capable of accommodating the data packet of duration B;

an associative processor P_M capable of storing a set of channel unscheduled times from which a channel is free and corresponding channels S_M; and

conducting a parallel search of the set of channel unscheduled times from which a channel is free and corresponding channels S_M for an unscheduled time interval and corresponding channel capable of accommodating the data packet;

means for selecting one channel from available data channels;

means for assigning the data packet to the selected channel; and

means for updating state information of the selected data channel.

13. The apparatus for implementing channel scheduling algorithms in an optical router, according to claim 12, further including:

if no data channel is available to carry the data packet, means for determining whether a data channel would be available if a time delay is introduced to shift the arrival time of the data packet via a fiber delay line (FDL);

means to shift the arrival time of the data packet by a time delay via a fiber delay line and to assign the data packet to an appropriate outbound data channel if the outbound data channel would be available; and

means for dropping the data packet if no data channel is available to carry the data packet.

14. The apparatus according to claim 12, wherein the data packet is of a variable length.

15. The apparatus according to claim 12, wherein scheduled time of routing for each data packet that has not been transmitted is scheduled with a relative time based upon the start processing time of the data packet.

16. The apparatus according to claim 12, wherein the associative processor P_G does not store voids/gaps of a channel if such void/gap is less than or equal to a duration Δ

.

17. The apparatus according to claim 12 wherein, if multiple voids/gaps are available to accommodate the data packet of duration B, the smallest available void gap is selected.

18. The apparatus according to claim 17 wherein the search of the set of void/gaps and corresponding channels S_G and the search of the set of channel unscheduled times from which a channel is free and corresponding channels S_M is conducted simultaneously.

19. The apparatus of claim 13, further comprising means of generating control signals for associative processors P_M and P_G via an arithmetic-logic unit.

20. The apparatus according to claim 12 wherein, if multiple voids/gaps are available to accommodate data packet of duration B, the smallest available void gap is selected.

21. The apparatus according to claim 12 wherein associative processor P_L is further capable of searching the set of possible time delays S_L for a time delay L which is capable of being introduced such that in available gap and corresponding channel may be utilized to accommodate the data packet.

22. The apparatus according to claim 12, wherein a new reference time for each data packet under consideration is set to a time t=0 upon starting the channel scheduling process and the state information of the data channel group are updated simultaneously according to the new reference time of t=0.

23. The apparatus according to claim 12, wherein the means for selecting one channel from the available data channels further comprises means of selecting the channel via a round robin method.

24. The apparatus according to claim 12, wherein the means for selecting one channel from the available data channels further comprises means of selecting the channel via a random method.

25. The apparatus according to claim 12, wherein the means for selecting one channel from the available data channels further comprises means of selecting the channel via a predetermined method.

26. The apparatus according to claim 12, wherein the means for selecting one channel from the available data channels further comprises means of selecting the channel via a latest available unused channel method with void filling.