Research On Parallel Spectrum Defragmentation Algorithm For Elastic Optical Network

In an elastic optical network,dynamically setting up and tearing down services generates a large number of small spectrum blocks.These small spectrum blocks that are called spectral fragments are not aligned on the link nor are they continuous in the spectrum.Spectrum fragmentation will reduce the efficiency of the spectrum resource utilization of the network,resulting in a large number of services being blocked,thereby reducing network performance.In order to make full use of network spectrum resources,network managers need to perform spectrum defragmentation on the network to reduce spectrum fragmentation and improve network performance.Among them,spectrum defragmentation is to adjust the routes and spectrum of existing services to reduce spectrum fragmentation in the network.According to different adjustment methods,spectrum defragmentation can be divided into serial spectrum defragmentation and parallel spectrum defragmentation.Among them,the parallel spectrum defragmentation performs routing and spectrum adjustment simultaneously,while the serial spectrum defragmentation performs routing and spectrum adjustment in turn.Compared to serial spectral defragmentation,parallel spectral defragmentation takes less time and is faster.Therefore,this thesis focuses on parallel spectrum defragmentation based on preset routes and online rerouting.The traditional fixed-route spectrum defragmentation only adjusts the spectrum position of the service without changing the route of the service.The processing process is simple,but the effect of the finishing is not ideal.The spectrum defragmentation based on the preset route adjusts the spectrum position and route of the service at the same time,and the effect of the finishing is better.Therefore,this dissertation focuses on the parallel spectrum defragmentation problem of pre-configured routing.Firstly,an integer linear programming model of the problem is established.Through the analysis of this model,we design two parallel spectral defragmentation algorithms—Lagrange relaxation-based heuristic algorithm and branch-and-bound heuristic algorithm.Among them,the heuristic algorithm based on Lagrangian relaxation reduces the distance between the upper and lower bounds of the business moving distance and obtains the final moving distance of the business.The heuristic algorithm based on the branch and delimitation calculates the distance of the moving of the business by calculating the maximum weight independent set of the business moving distance.Simulation experimental results show that both heuristic algorithms can get better spectral defragmentation effect.Moreover,the heuristic algorithm based on Lagrangian relaxation can obtain the approximate solution of the problem in a shorter time,while the heuristic algorithm based on branch and bound can obtain the optimal solution of the problem.Spectrum defragmentation based on preset routes can achieve good results,but it ignores the conditions of the links that have been used by the service in the network.As a result,the service may not find a suitable route in all the alternative routes to move forward,resulting in the network.The use of spectrum resources is inefficient.Aiming at this problem,combined with the characteristics of spectrum channels in service transmission in actual networks,this paper designs an on-line rerouting parallel spectral defragmentation algorithm based on layered graphs.The algorithm reroutes services online in the spectrum layered map to move as much as possible the high-frequency band traffic to the idle low-band spectrum,thereby reducing spectrum fragmentation in the network.The experimental data show that the algorithm can get better spectral defragmentation effect.