# Least Used

The free spectrum slots, which have been utilized by the smallest number of fiber links in the network, are the focus of the least used spectrum allocation policy [6,7] to satisfy lightpath requests. If several spectrum slot candidates are equally possible, the first fit spectrum allocation policy is used to select the best candidate. Choosing spectrum slots in this way attempts to distribute the load uniformly across the entire spectrum domain.

# Most Used

The spectrum allocation of the most used policy [6,7] is similar to that of the least used policy. Instead of choosing the spectrum resources that have been utilized by the least number of fiber links in the network, this policy selects free slots, which have been utilized by the most number of fiber links in the network. Choosing spectrum slots using this policy is an effort to enhance the reuse of spectrum in the network.

# Exact Fit

If a lightpath request arrives, which requires *c* contiguous slots for lightpath establishment, the exact fit allocation policy [98,161] finds *c* contiguous free slots from the beginning of the spectrum. If there exists exact *c* free slots, which are not more than or less than *c,* it allocates those slots. Otherwise, this spectrum allocation follows the first fit spectrum allocation policy. The exact fit allocation

**Figure 6.6: **Comparison of major spectrum allocation policies in terms of contiguous-aligned available slot ratio in NSFNET [97].

policy tries to suppress the fragmentation effect and improves the contiguous- aligned available slot ratio in the network.

Several studies in the literature have already been conducted to analyze the effect of fragmentation using different spectrum allocation policies [97,161,162]. Figure 6.6 condenses the major spectrum allocation policies. We compare the performance of these spectrum allocation policies in terms of contiguous-aligned available slot ratio under varied traffic load (in Erlangs); the traffic load in the network is defined in Chapter 7 (page number 85). We estimate the relationship between the traffic load and the average slot utilization in NSFNET [6]. The assumptions, including lightpath request distribution and maximum number of occupied spectrum by lightpaths, of this evaluation are explained in Chapter 7 (page number 85). We observe from the literature that the least-used and most-used allocation policies have the highest time complexity [6]. Note that the last fit allocation policy is the same as with the first fit policy, in terms of the contiguous-aligned available slot ratio. We obtain the numerical results via simulation performed on NSFNET We observe that, when the traffic load is low, the contiguous-aligned available slot ratios are comparable for different schemes. The numerical results suggest that the first-last fit and random fit policies yield the highest and lowest contiguous-aligned available slot ratios, respectively, among all spectrum allocation policies, when the traffic load is reasonably high. In other words, we can say that the first-last fit allocation policy offers the lowest fragmentation effect among the spectrum allocation policies considered here. When the traffic load increases more and the network becomes congested, the decrease rate of contiguous-aligned available slot ratio becomes slow with traffic load for any allocation policy.

The above spectrum allocation policies can use any of the routing policies [6,80,81], namely (i) fixed routing, (ii) fixed alternate routing, (iii) least congested routing, and (iv) adaptive routing, to find routes between source- destination pairs. However, the performance of a spectrum allocation policy depends on the selection of a routing policy. The selection of routes can be performed for lightpath requests either before spectrum allocation or during the spectrum allocation.

Fixed routing (FR) [6,80] precomputes a single fixed route for each source- destination pair using some shortest path algorithms, such as Dijkstra’s algorithm [85]. When a lightpath request arrives in the network, it tries to establish a lightpath along the precomputed fixed route. FR checks whether the desired slot is free on each link of the precomputed route or not. The lightpath request is blocked if one link of the precomputed route does not have the desired slot.

In fixed alternate routing (FAR) [6,80], an ordered list of a number of fixed routes for each source-destination pair is maintained in the network. These routes are determined off-line. When a lightpath request arrives, the source node attempts to establish a lightpath through each of the routes from the ordered list in sequence, until a route with the required slots is found. If no available route with required slots is found among the list of alternate routes, the lightpath request is blocked. The computation complexity of this algorithm is higher than that of FR. However, it provides lower call blocking compared to the FR algorithm. Using this algorithm, it may not be possible to find all possible routes between a given source-destination pair, and hence the performance of this algorithm is not optimum in terms of call blocking.

Least congested routing (LCR) [6,80] similar to FAR; it precomputes a sequence of routes for each source-destination pair. Depending on the arrival time of the lightpath request, the least-congested route is chosen from the precomputed routes.

In adaptive routing (AR) [80,81], the route between the source-destination pair is selected dynamically, based on link information in a network. A lightpath request is considered blocked when no route with a desired slot is found between the source-destination pair. Since it considers all possible routes between a source-destination pair, it provides the best performance in terms of call blocking. However, its operational complexity is the highest among other routing policies.

**Exercises**

1. Estimate the fragmentation impact for the link mentioned in Fig. 6.7 using the external fragmentation metric, the entropy-based fragmentation metric, and the access blocking probability metric. Note that, for access blocking probability metric, two types of granularities are used by transponders; three and four slots are considered to satisfy the first and second granularities.

Figure 6.7: Optical link; white and gray slots indicate free and occupied slots, respective.

2. Consider a network and spectrum conditions mentioned in Fig. 6.8. Consider six lightpath requests, which are AB, AC, AD, BC, BD, and DC, arrive in the network sequentially, where each lightpath request is indexed by i € {l,--- ,6}. Compute fragmentation and contiguous-aligned available slot ratio in the network under the following conditions.

Figure 6.8: Network topology.

i The routes of AB, AC, AD, BC, BD, and DC are A-В, A-B-C, A-B- D, B-C, B-D, and D-C, respectively.

ii The first fit allocation policy is used for spectrum allocation.

iii Each request requires two contiguous slots for lightpath establishment, and no spectrum conversion is allowed.

iv No lightpath is tore down after the establishment.

v No gardband is considered.

3. If we consider first-last fit on Exercise 2, does it affect the performance in terms of fragmentation and contiguous-aligned available slot ratio? Provide the analysis. For the first-last fit policy, odd and even indexed lightpath requests are allocated using first fit and last fit, respectively.

**Chapter****7**