Entropy-Based Fragmentation Metric

In information theory, the amount of information contained in a message can be measured by entropy [156]. Taking this direction, Wright et al. [157] used the concept of entropy as a quantitative metric for measuring spectrum fragmentation. The entropy-based fragmentation metric is defined by (6.2)

Figure 6.2: Illustration of external fragmentation metric.

Figure 6.3: Illustration of entropy-based fragmentation metric.

where S denotes the total number of slots. The concept of the entropy-based fragmentation metric is explained by an example, as shown in Fig. 6.3.

Access Blocking Probability Metric

The access blocking probability metric [158] can be used to estimate fragmentation. In determining the access blocking probability metric, it is considered that blocking is dependent only on the granularities used by the transponders. The access blocking probability metric is defined by (6.3)

where w denotes types of granularities used by transponders. В represents the number of all available slots. Gk represents the number of slots required to sat-

Figure 6.4: Illustration of access blocking probability metric.

isfy the granularity type k. DIV(a,fo) indicates the integer division of ct/b. The concept of the access blocking probability metric is explained by the example shown in Fig. 6.4. In this example, three and four slots are considered to satisfy the two types of granularities (i.e., C| = 3 and C2 = 4).

This subsection compares the different metrics considered for estimating the degree of fragmentation. The different link-oriented fragmentation metrics are summarized in Table 6.1. The external fragmentation metric has the lowest time complexity of all considered metrics as it inspects only the largest block. It recognizes that there is no fragmentation effect if all free slots are contiguous. In this case, the maximum number of available contiguous slots is equivalent to the number of slots in the link, which indicates the initial condition of the link. The disadvantage of the external fragmentation metric is that it ignores the small fragments to focus on the maximum number of available contiguous slots in the link.

Similar to the external fragmentation metric, the entropy-based fragmentation metric is unable to distinguish the case when fragmented slots match the available granularities from the inappropriate fragmented cases. This metric can efficiently estimate relative fragmentation, and so allows comparisons of different arrangements. The time complexity of the entropy-based fragmentation metric is linear to the number of fragments.

The access blocking probability metric can estimate fragmentation more comprehensively than the previous two metrics. When all fragments are smaller than the smallest granularity, the access blocking probability metric finds that the spectrum is completely fragmented. If the spectrum is not fragmented, it returns zero, which indicates that all slots are free and contiguous. As the access blocking probability metric returns a relative value between zero and one, it can

Table 6.1: Summaries of different link-oriented fragmentation metrics.

 Fragmentation metrics Reference Time complexity Observations and comments External fragmentation [154.155] Lowest It ignores the small fragments as it focuses on the maximum number of available contiguous slots in the link. Entropy-based fragmentation [156] Moderate It considers any fragmented slot and estimates relative fragmentation. Access blocking probability [158] Highest It deals with available granularities and tries to avoid situations where these granularities are blocked.

also be used to compare relative levels of fragmentation; the more the spectrum is fragmented, the greater the relative fragmentation is. However, similar to the external fragmentation metric, the access blocking probability metric cannot differentiate whether (i) all slots are free, (ii) all slots are used, and (iii) all free slots are contiguous. This metric has higher time complexity than the other metrics considered here.

To accurately estimate the effect of fragmentation in a single fiber link, some works that use Markov Chain (MC) models [159,160] can be found in the literature. Taking this direction, Kim et al. [159] presented an MC model that attempts to characterize the fragmentation problem in a single fiber link. In addition, their model is able to accurately capture the blocking probability due to the fragmentation effect. The authors in [160] introduced an exact MC model for single-link flexible grid networks and analyzed the blocking probability caused by fragmentation.

We summarize that the above metrics are considered to estimate the fragmentation in each link. However, it is difficult to estimate the overall fragmentation in a network due to the spectrum continuity and contiguity constraints. In the next subsection, we define how fragmentation in a network can be estimated.

Measuring Fragmentation in a Network

The fragmentation in a network can be measured with the help of contiguous- aligned available slot ratio [161]. We use the routes of source-destination pairs to represent the contiguous aligned available slot ratio in the network. The contiguous-aligned available slot ratio is defined by ф = J2d£D^2keKdwdk' where у/(д = Ц-. Wdk is a weight that is proportional to the traffic load of route кKd of source-destination pair dD, where ^ = *• 2 represents the total number of spectrum slots in each link; we assume that all links have the same number of slots. D and Kd represent the set of all the source- destination pairs and the set of routes of source-destination d € A respectively.

Figure 6.5: Illustration of fragmentation in a network.

ydk represents the maximum number of contiguous aligned available slots for route кKd of source-destination pair dD. The fragmentation is defined by

Z = 1 -f

The fragmentation in a network is illustrated in Fig. 6.5. We assume four- node network with five directed links. Each link consists of 10 spectrum slots. We assume six source-destination pairs, which are AB (d = 1), AC (d = 2), AD (d = 3), BC (d = 4), BD (d = 5), and DC (d = 6). 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. Here, Z = 10 and |D| = 6. For the sake of simplicity, we assume that each source-destination pair has one route. The traffic load and the average number of requested slots for each source-destination pair is the same over all the source- destination pairs. Therefore, with lA^I = 1 for all dD, wd = 1/6 is set. We obtain у = 4,721 = 6,yu = 8,741 = 4,751 = 4, and y6i = 4. The contiguous- aligned available slot ratio and the fragmentation in the network are 0.5 and 0.5, respectively.