Impact of Fragmentation on Spectrum Allocation Policies
This section discusses the major spectrum allocation policies, which are first fit, random fit, last fit, first-last fit, exact fit, least used, most used, and presents the impact of fragmentation when the network uses these spectrum allocation policies. We assume that lightpath requests arrive in the system sequentially, and they are established one by one if they share the same link. More than one request can be established in parallel if they do not share any common link. To evaluate the fragmentation effect, we use the contiguous-aligned available slot ratio metric due to its simplicity.
The first fit spectrum allocation policy [98,99] indexes all the spectrum slots and maintains a list of indexes of available and used spectrum slots. For each allocation, it tries to select the lowermost indexed available slot and use it for lightpath provisioning. When the lightpath is released, the used slots are added to the list of freed slots. By choosing spectrum in this way, lightpaths are crammed into fewer spectrum slots, which helps to increase the contiguous-aligned available slot ratio in the network. Employing this policy does not require any global information of the network. This policy is recognized as suitable for spectrum allocation. This is because it provides higher contiguous-aligned available slot ratio and its computation time complexity is low.
The random fit policy [6, 98] maintains a list of free spectrum slots. When a lightpath request arrives in the network, the policy arbitrarily chooses an available spectrum slot and uses it for lightpath provisioning. After slots are assigned, the list of free slots is refreshed by removing the just-assigned slot from the available list. Once a lightpath is released, the just-released slot is added to the list of free slots. By selecting spectrum slots in a random manner, the network operator tries to reduce the possibility that some specific spectrum slots are often used. In this case, allocated spectrum slots are uniformly distributed over entire spectra.