BPA: Approximation Batch-Processing Algorithm for Static Lightpath Requests in Elastic Optical Networks

One of the major obstacles we face in the elastic optical network (EON) is the fragmentation which degrades the quality of service by underutilizing the spectrum resources. Typically, proactive fragmentation management approaches have been considered to overcome the above issue. In proactive fragmentation management approaches, batch formation is a major concern for performance improvement. This letter proposes an approximation static Batch Processing Algorithm for lightpath requests in EONs, named BPA, to enhance resource utilization. BPA generates temporary batches of the lightpath requests by accommodating as many lightpath requests as possible until the batch capacity is exhausted. After that, the last request from each temporary batch is replaced with the same number of hops of requests that require more slots to form batches. This reduces the number of batches by utilizing the slots left in each batch. We prove that BPA is a factor 2WL approximation, where
${L}$
is the ratio of the maximum number of hops to the minimum number of hops of requests, and
${W}$
is the batch capacity. Numerical results indicate that BPA outperforms the conventional heuristic algorithm as the number of requests increases.