This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomial time for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ESUM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.

This paper proposes a defragmentation scheme using reroutable backup paths in toggled-based quasi 1+1 path protected elastic optical networks (EONs) to improve the efficiency of defragmentation and suppress the fragmentation effect. The proposed scheme can reallocate spectrum slots of backup paths and reroute of backup paths. The path exchange function of the proposed scheme makes the primary paths become the backup state while the backup paths become the primary. This allows utilization of the advantages of defragmentation in both primary and backup paths. We formulate a static spectrum reallocation problem with rerouting (SSRR) in the toggled-based quasi 1+1 path protected EON as an integer linear programming (ILP) problem. The decision version of SSRR is proven to be an NP-complete problem. A heuristic algorithm is introduced to solve the problem for large networks networks where the ILP problem is not tractable. For a dynamic traffic scenario, an approach that suppresses the fragmentation considering rerouting and path exchanging operations is presented. We evaluate the performances of the proposed scheme by comparing it to the conventional scheme in terms of dependencies on node degree, processing time of network operations and interval time between scheduled defragmentations. The numerical results obtained from the performance evaluation indicate that the proposed scheme increases the traffic admissibility compared to the conventional scheme.