Batch Scheduling in Optical Networks

Yan Wang, Xiaojun Cao, Adrian Caciula, Qian HuJournal of Optical Communications and Networking 2013 · DOI

TL;DR

This paper tackles the challenge of efficiently scheduling data bursts in optical networks, which often compete for limited wavelength channels. They introduce a novel "batch scheduling with discrete-time buffers" problem, modeling it with integer linear programming and proposing heuristic algorithms that significantly reduce data blocking compared to traditional methods, especially when using Fiber Delay Lines (FDLs).

What Problem Does This Paper Address?

Optical networks, particularly those using Optical Burst Switching (OBS) or Optical Packet Switching (OPS), face a significant challenge in managing the high volume of data bursts that arrive and compete for the same wavelength channels within a router. Traditional scheduling approaches often treat each burst independently, leading to inefficient resource utilization and data loss (blocking). While job-machine scheduling in traditional computing has explored batching tasks to improve efficiency, optical networks present unique constraints. Specifically, optical RAM for buffering is not yet feasible, and instead, Fiber Delay Lines (FDLs) are used. FDLs offer a fixed, discrete buffering time, creating a new type of scheduling problem: "job-machine scheduling with discrete-time buffers." This paper aims to address this by developing optimal and near-optimal solutions for batch scheduling in optical networks, both with and without the use of FDLs.

Methods

The authors approach this problem by first establishing the connection between classical job-machine scheduling and batch scheduling in optical networks. They then formally define and prove the NP-completeness of the "job-machine scheduling with discrete-time buffers" (JDB) problem.

For optimal solutions, they develop mathematical models using integer linear programming (ILP). These models are formulated for two scenarios:

  1. Batch scheduling without FDLs: This is modeled as a variation of the job-machine scheduling problem with non-identical machines and arbitrary K (number of machines/wavelengths).
  2. Batch scheduling with FDLs: This incorporates the discrete buffering times of FDLs into the ILP formulation.

Recognizing the computational complexity of ILP for real-time optical network operations, the paper also proposes polynomial-time heuristic algorithms. Their primary heuristic, Section-Based Batch Scheduling (SBS), works by:

  • Dividing the time window into "sections" based on burst arrival and departure events.
  • Calculating a "congestion degree" for each section, indicating how many bursts are competing for a wavelength.
  • Prioritizing bursts with a higher "Con_Sum" (sum of congestion degrees across sections they are involved in) for scheduling or delaying.
  • For the FDL case, SBS attempts to resolve contention by assigning bursts to available FDLs in a best-fit manner.
  • For the no-FDL case, bursts with high Con_Sum are dropped.

Datasets

Not discussed in the paper. The evaluation uses a simulated network topology (NSFNET 14-node) and parameters, rather than specific datasets.

Key Insights and Ideas

  • FDLs introduce a new scheduling paradigm: The discrete and fixed nature of FDL buffering fundamentally changes the scheduling problem, making it more complex than traditional RAM-based buffering.
  • Batch scheduling is crucial for optical networks: By considering groups of bursts together, batch scheduling can exploit correlations to significantly improve wavelength utilization and reduce blocking.
  • Heuristics are essential for real-time operation: The NP-complete nature of the optimal problem necessitates efficient heuristic algorithms for practical deployment in high-speed optical routers.
  • FDLs offer a performance boost, but with tradeoffs: While FDLs can dramatically reduce blocking probability, they introduce additional end-to-end delay for data bursts.
  • Batch Window Size matters: There's an optimal range for the batch window size; too small limits the benefits of batching, while too large can increase control packet delay and reduce the effectiveness of subsequent scheduling stages.

Key Results

  • Optimal Solutions: The paper provides ILP formulations for optimal batch scheduling, both with and without FDLs.
  • Heuristic Performance: The proposed SBS heuristic algorithm (with and without FDLs) performs close to the optimal ILP solutions.
  • Blocking Probability Reduction:
    • Batch scheduling without FDLs reduces blocking probability by up to 15% compared to LAUC-VF.
  • Batch scheduling with FDLs can reduce blocking probability by up to 30% compared to LAUC-VF.
  • Throughput Improvement: Batch scheduling, especially with FDLs, leads to higher network throughput.
  • Delay Tradeoff: Using FDLs in SBS results in slightly higher control packet delays compared to SBS without FDLs, and a noticeable increase in data unit end-to-end delay compared to LAUC-VF. The paper suggests that for delay-sensitive applications, extensive FDL use might not be ideal.

Limitations and Future Work

  • Complexity of FDL Scheduling: The paper acknowledges the complexity of co-scheduling wavelengths and FDLs.
  • Delay Impact: The increased end-to-end delay introduced by FDLs is a significant tradeoff that needs careful consideration for delay-sensitive applications.
  • Batch Window Size Optimization: The paper suggests that optimal BW depends on factors like offset time and routing policies, hinting at further research in this area.
  • Future Work: The authors mention that a separate work will present studies on feedback FDLs. They also suggest that the admission process for bursts (deciding whether to enter batch scheduling) can be integrated into their models to manage delays and QoS requirements.

Summary updated

Abstract

Batch scheduling accommodates a group of tasks with the start/end time constraints to maximize the revenue from scheduling tasks over a number of servers, which has been extensively studied in the context of job–machine scheduling. In optical networks, batch scheduling refers to the process of scheduling a group of data units (i.e., the jobs) competing for the same set of wavelength channels (i.e., the machines). Classical job–machine scheduling studies have considered both the case of a pure-loss system, and the case with waiting rooms (i.e., buffers), which are generally in the form of random access memory (RAM). In optical networks, the buffering is achieved by feeding the optical signal into a fixed length of fiber, namely, a fiber delay line (FDL), since optical RAM is not yet available. The unique feature of the discrete and predefined buffering time in fact instantiates a new type of problem, namely, job–machine scheduling with discrete-time buffers. In this work, we comprehensively study batch scheduling in optical networks. We show that batch scheduling with and without FDLs corresponds to two different instances of the job–machine scheduling problem. While proving their NP-completeness, we mathematically model both cases using integer linear programming formulations to provide an optimal scheduling. Given the timeliness request for on-line batch scheduling and the dramatic problem size in optical networks, we also propose polynomial-time heuristic algorithms, which are shown to be near optimal in our simulations.
BibTeX
@article{wang2013batch,
  author = {Yan Wang and Xiaojun Cao and Adrian Caciula and Qian Hu},
  title = {{Batch Scheduling in Optical Networks}},
  journal = {Journal of Optical Communications and Networking},
  year = {2013},
  doi = {10.1364/jocn.5.000116},
}
Figure