Batch scheduling in optical networks with feedback/feed-forward fiber delay lines

摘要

Batch scheduling has been extensively studied in the context of Job-machine scheduling, where a group of time-constrained tasks are scheduled to run over a limited number of servers, with the goal of maximizing the overall revenue from successfully scheduled tasks. Depending on whether buffers are employed, batch scheduling can be in the form of a pure-loss system or system with buffers. In optical burst/packet switching networks, bursts/packets (i.e., tasks) that simultaneously arrive or locate within the same time window can be treated as a batch, and scheduled over a limited number of available wavelengths (i.e., servers). Due to the unavailability of Random Access Memory in optical networks, buffering is generally achieved with Fiber Delay Lines, which can only offer discrete and predefined duration of buffering. The discrete feature of FDLs hence leads to a new Job-machine scheduling with Discrete-time Buffers (JDB) problem, which can be shown to be NP-Complete. In this work, we study how to optimally co-schedule FDLs and wavelengths in the batch scheduling process over two types of FDL architectures, namely feed-forward and feedback FDLs. We mathematically model the JDB problem over both feed-forward and feedback FDLs, and propose a heuristic algorithm to enable fast on-line scheduling. The performance of proposed schemes over feed-forward and feedback FDLs are simulated and compared.