Scheduling WDM PON with tunable lasers with different tuning times

1. A method for allocating network traffic requests on multiple wavelength optical network units (ONUs) of a wavelength division multiplexing (WDM) passive optical network (PON), the method comprising:

determining whether an allocation is for a preemptive schedule or a non-preemptive schedule;

for the preemptive schedule, assigning wavelengths to requests;

sorting the requests and the wavelengths;

postponing the requests by a laser tuning time associated with each ONU;

optimizing the preemptive schedule by filling in idle times; and

moving an unscheduled part of one of the requests to a next wavelength when a remaining time on one of the wavelengths assigned with the request is insufficient to satisfy the request.

2. The method according to claim 1 , further comprising one or more of:

sorting the requests in descending order of a size of each request; and

sorting the wavelengths in ascending order of an available time for each wavelength.

3. The method according to claim 1 , wherein postponing the requests comprises postponing scheduling of all requests and a last request on each wavelength by the laser tuning time associated with an ONU currently being allocated.

4. The method according to claim 1 , wherein filling in the idle times comprises allocating a time duration between a u w and l, where a u w is a latest job completion time when a laser is to be tuned to a wavelength other than a current one and l is a predefined limit for the latest job completion time.

5. The method according to claim 4 , wherein filling in the idle times further comprises allocating a time duration between a l w and a u w , where a l w is a latest job completion time when the laser is tuned to the current wavelength.

6. The method according to claim 4 , further comprising prioritizing requests by size when allocating the requests to the wavelengths between a u w and l.

7. The method according to claim 4 , wherein filling in the idle times further comprises scheduling a request on a wavelength when a remaining available time duration after a u w is sufficient to accommodate the request.

8. The method according to claim 1 , further comprising one or more of:

for the non-preemptive schedule, sorting the requests in descending order of a size of each request and the wavelengths in ascending order of an available time for each wavelength;

performing a search in order of wavelengths starting from a first wavelength; and

assigning each request to the wavelengths to which the request temporally fits.

9. The method according to claim 8 , further comprising determining the allocation to be feasible when all requests are scheduled before a predefined limit for latest job completion time.

10. The method according to claim 9 , further comprising reducing the latest job completion time by allocating time duration between a l w and a u w to requests when a laser is tuned to a current wavelength, where a l w is a latest job completion time when the laser is tuned to the current wavelength and a u w is a latest job completion time when the laser is to be tuned to a wavelength other than the current wavelength.

11. The method according to claim 10 , further comprising prioritizing requests based on a descending order of a size of each request.

12. The method according to claim 10 , further comprising allocating remaining requests for a time duration between a u w and l based on descending order of a size of each request and an ascending order of an available time for each wavelength, where l is a predefined limit for the latest job completion time.

13. An apparatus for allocating network traffic requests on multiple wavelength optical network units (ONUs) of a wavelength division multiplexing (WDM) passive optical network (PON), comprising:

a memory configured to store instructions and also store network information data associated with the WDM PON;

a processor coupled to the memory, wherein the processor is adapted to execute the instructions, which when executed configure the processor to:

determine whether an allocation is for a preemptive schedule or a non-preemptive schedule;

for the preemptive schedule:

assign wavelengths to requests;

sort the requests in descending order of a size of each request and the wavelengths in ascending order of an available time for each wavelength;

for the non-preemptive schedule:

sort the requests in descending order of a size of each request and the wavelengths in ascending order of an available time for each wavelength;

assign each request to the wavelengths to which the request temporally fits;

postpone the requests by a laser tuning time associated with each ONU; and

optimize the schedules by filling in idle times.

14. The apparatus according to claim 13 , wherein the processor is further configured to fill in the idle times in the preemptive schedule based on allocation of a time duration between a u w and l first and allocation of a time duration between a l w and a u w second, where a l w is a latest job completion time when a laser is tuned to a current wavelength, a u w is the latest job completion time when the laser is to be tuned to a wavelength other than the current one, and l is a predefined limit for the latest job completion time.

15. The apparatus according to claim 13 , wherein the processor is further configured to fill in the idle times in the non-preemptive schedule based on allocation of a time duration between a l w and a u w to requests when a laser is tuned to a current wavelength and allocation of remaining requests for a time duration between a u w and l based on descending order of a size of each request and an ascending order of an available time for each wavelength, where a l w is a latest job completion time when a laser is tuned to a current wavelength, a u w is the latest job completion time when the laser is to be tuned to a wavelength other than the current one, and l is a predefined limit for the latest job completion time.

16. The apparatus according to claim 13 , wherein the ONUs of the WDM PON include at least one of wavelength-tunable sources and/or multi-wavelength sources.

17. The apparatus according to claim 13 , wherein the ONUs include at least one of a full-range laser source and a limited-range laser source.

18. The apparatus according to claim 17 , wherein the laser source includes one or more of a multi-frequency laser, a distributed feedback (DFB) laser diode (LD) array, a gain-coupled DFB array, a chirped-pulse WDM, a distributed Bragg reflector (DBR) array, a sampled grating DBR, or an external cavity laser etalon.

19. A computing device comprising:

a memory configured to store instructions for allocating network traffic requests on multiple wavelength optical network units (ONUs) of a wavelength division multiplexing (WDM) passive optical network (PON),

a processor coupled to the memory, wherein the processor is adapted to execute the instructions, which when executed configure the processor to:

determine whether an allocation is for a preemptive schedule or a non-preemptive schedule;

for the preemptive schedule:

assign wavelengths to requests;

sort the requests in descending order of a size of each request and the wavelengths in ascending order of an available time for each wavelength;

for the non-preemptive schedule:

sort the requests in descending order of a size of each request and the wavelengths in ascending order of an available time for each wavelength;

sort each request to the wavelengths to which the request temporally fits;

postpone all requests and a last request on each wavelength by the laser tuning time associated with an ONU currently being allocated; and

reduce an overall latest job completion time.

20. The device according to claim 19 , wherein the processor is further configured to:

reduce an overall latest job completion time for the preemptive schedule by an action to:

allocate a time duration between a u w and l first and allocating a time duration between a l w and a u w second, where a l w is a latest job completion time when a laser is tuned to a current wavelength, a u w is the latest job completion time when the laser is to be tuned to a wavelength other than the current one, and t is a predefined limit for the latest job completion time; and

reduce an overall latest job completion time for the non-preemptive schedule by an action to:

allocate a time duration between a l w and a u w to requests when a laser is tuned to a current wavelength and allocating remaining requests for a time duration between a u w and l based on descending order of a size of each request and an ascending order of an available time for each wavelength.

21. The device according to claim 20 , wherein the processor is further configured to:

for the preemptive schedule:

prioritize requests by size when allocating the requests to the wavelengths between a u w and l; and

for the non-preemptive schedule:

prioritize requests based on a descending order of a size of each request for all wavelengths.

22. The device according to claim 19 , wherein the processor is further configured to:

schedule a request on a wavelength if a remaining available time duration after a u w is sufficient to accommodate the request.