Scheduling Bursts Using Interval Graphs in Optical Burst Switching Networks

Optical Burst Switching (OBS) is considered to be a promising paradigm for bearing IP traffic in Wavelength Division Multiplexing (WDM) optical networks. In OBS networks, a key challenge is to reduce the data loss rate with efficient scheduling algorithms. In this work, we propose novel algorithms for batch scheduling in OBS networks with different optimization criteria. The algorithms effectively consider the strong correlations among the multiple bursts, and employ the proposed interval graphs and min-cost circular flow techniques to achieve optimized network performance in terms of data loss rate in the network. Simulation results show that our algorithms achieve a loss rate which is as much as 20% less than one of the best previously known algorithms, LAUC-VF, and suffer only a minor increase (about 1-hop link propagation) in the data latency.