Desktop version

Home arrow Engineering

  • Increase font
  • Decrease font


<<   CONTENTS   >>

: Spectrum Fragmentation Management Approaches Considering Non-Defragmentation

Spectrum fragmentation management approaches are used to handle spectrum fragmentation and increase the admissible traffic levels in the network. Figure 7.1 shows the thematic taxonomy of fragmentation management approaches. Note that non-defragmentation and defragmentation approaches are not mutually exclusive. One can make some schemes considering both nondefragmentation and defragmentation approaches. This chapter presents spectrum fragmentation management approaches considering non-defragmentation. Spectrum fragmentation management approaches considering defragmentation approaches will be explained in Chapter 8.

Non-Defragmentation Approaches

In the non-defragmentation approach, necessary precautions are taken to avoid fragmentation before the establishment of a lightpath. However, no action is taken for in-service lightpaths. Whereas in the case of defragmentation approaches, a necessary action is taken for in-service lightpaths in order to suppress the fragmentation effect. In the non-defragmentation approach, the spectrum is managed in advance to avoid the fragmentation effect. The non-defragmentation

Classification of fragmentation management approaches in EONs

Figure 7.1: Classification of fragmentation management approaches in EONs.

approaches [88,102,163-171] are attractive as they offer lower capital expenditure (CAPEX) and operational expenditure (ОРЕХ). However, these approaches have a lower performance in terms of admissible traffic volume than the de- fragmentation approaches. In the non-defragmentation approaches, the following strategies are used to suppress the spectrum fragmentation.

Partitioning Approaches

In EONs, typically there are two types of partitioning approaches, namely dedicated partitioning and pseudo partitioning, are considered, which are explained in the following.

Dedicated Partitioning

Dedicated partitioning approaches [100,114,162] are the more strict version of the pseudo partitioning approach. In dedicated partitioning approaches, the entire spectrum is divided into a number of partitions based on certain criteria, and each partition is dedicated to a different lightpath group. In the following, the criteria to obtain the number of partitions is explained.

In dedicated partitioning approaches, the route and slot demand are assumed to be given for each lightpath group [ 100,162]. The number of required partitions can be estimated using the graph coloring problem [85]. The approach uses an auxiliary graph where the lightpath groups are considered as nodes and, if two lightpath groups share at least one common link, they are connected by an edge. A lightpath group is formed by a set of lightpaths whose routes are exactly the same. The graph coloring problem assigns a color to each vertex while satisfying the constraint that the same color is not assigned to adjacent vertices; the objective is to minimize the number of colors. Each color corresponds to each partition unit. Minimizing the number of colors is equivalent to minimizing the number of partitions of the entire spectra.

The dedicated partitioning approaches ensure that the number of partitions must be greater than two. The lightpath groups and number of partitions are created in advance; when a lightpath request arr ives, the network checks which category the lightpath request belongs to and assigns it to the appropriate partition. Through careful partitioning, spectrum under-utilization which is caused by unfairness can also be eliminated. The main disadvantage of partitioning techniques is that they fail to offer statistical multiplexing gain. Due to the lack of statistical multiplexing gain, blocking probability can increase in the network if the number of partitions is high [100, 162]. For an example, we estimate the blocking probability, denoted by Ph, using Erlang В loss formula, which is mentioned in (7.1) under a simple traffic model with a Poisson arrival process of mean arrival rate Я and an exponential distribution of the mean lightpath holding time (/?) [172]. If the number of channels is 100 and offered traffic, denoted by E = Яh is 100 [Erlang], the blocking probability is 0.0757. Dividing the same channel resources among four partitions and splitting the traffic among the partitions (25 channels with offered traffic volume of 25 [Erlang]), the blocking probability for each partition becomes 0.1438, which is higher than that of the non-partitioning case.

where m is the number of identical parallel channels.

Figure 7.2 shows the spectrum allocation of lightpath requests based on the dedicated partitioning approach. For this purpose, we consider a three-node network, which is shown in Fig. 7.2(a). We assume that all lightpath requests are categorized into six lightpath groups; the routes of the lightpath groups are given in advance as shown in Fig. 7.2(b). The auxiliary graph, see Fig. 7.2(c), is formed using lightpath groups, where each vertex is represented as a lightpath group. If two lightpath groups share one or more common links, an edge is established between the two vertices of the auxiliary graph. Thereafter, we solve the graph coloring problem [85] to determine the number of partitions, see Fig. 7.2(d). Typically, the number of used colors should be equal to the number of partitions. Thus, the entire spectrum is divided into three partitions and lightpath requests are allocated into those partitions according to the same color, which are shown in Fig. 7.2(e). Figure 7.2(f) shows the spectrum allocation of lightpath requests without considering the dedicated partitioning approach.

In the following section, how lightpath groups and partitions are formed are explained in detail. We define a lightpath group as a set of lightpaths whose routes are exactly the same. We use the term of disjoint lightpaths that do not share any link. The term of non-disjoint lightpaths belong to different lightpath

(a) Physical network,

Figure 7.2: (a) Physical network, (b) routes of lightpath groups given in network, (c) auxiliary graph using lightpath groups (d) one of possible solutions of graph coloring problem, (e) spectrum allocation with dedicated partitions, and (f) spectrum allocation without considering partitions.

group and share a link. Our objective in partition allocation is to determine the minimum number of required partitions that accommodate all lightpath groups in the network with the constraint that lightpaths assigned in the same partition must be disjoint. We transform the partition assignment problem into a graph coloring problem by creating a graph, named lightpath group graph. The lightpath group graph indicates the relationship among the lightpath groups in the network.

Algorithm 1 shows the procedure used to create the lightpath group graph. The lightpath group transformation partition is described as follows. The route of each lightpath group is assumed to be given. A vertex of the lightpath group graph corresponds to a lightpath group per unit slot demand. For an example, a lightpath group that has two unit slot demands, yields two vertices. If two lightpath groups share a common link or more links, an edge is established between the two vertices. By default, vertices that correspond to the same lightpath group are connected by edge(s).

Algorithm 1 Lightpath group graph transformation

Input: All lightpath groups in the network

Output: Lightpath group graph

Step 1: Initialize the set of vertices V = {0} and the set of edges E = {0}.

Step 2: Vertex generation: Generate vertex v that corresponds to each lightpath group per unit slot demand, where v = 1,2, ••• ,|V| for |Vj paths, and then add v to V.

Step 3: Edge establishment: Establish edge (v, u) between vgl/ and иV if the two lightpath groups corresponding to vertices v and и share at least one link, add (v, it) to E.

The graph coloring problem assigns a color to each vertex while satisfying the constraint that the same color is not assigned to adjacent vertices. Each color corresponds to each partition unit. A partition unit is a measurement unit indicating partition size. The minimum number of colors means the minimum number of partition units. After the minimum number of partition units is obtained, partition units that belong to the same lightpath group are put in adjacent order and merged into one partition. Hence, the lightpath group that contains larger slot demand is assigned to more partition units, and thus has a larger size partition.

The graph coloring problem can be formulated as an integer linear programming (ILP), which will be discussed in Chapter 11. From the literature [173], it had been revealed that when the number of lightpath groups and/or size of the traffic volume becomes large, the computational complexity of the ILP increases and it becomes difficult to solve it within a practical time. In that situation, the largest degree first (LDF) algorithm [173] can be applied to solve the graph coloring problem. The LDF algorithm attempts to color the vertices in a descending order of degree. LDF is a sequential coloring heuristic that attempts to color ver?tices on the basis of a specified order by using the minimum indexed color that is not used by adjacent vertices. In sequential ordering, if a vertex receives a particular color once, its color remains unchanged thereafter. The details of the LDF algorithm are presented in Algorithm 2. The time complexity of Algorithm 2 is 0(|V|2), where V is the set of nodes in the network.

Algorithm 2 Largest degree first (LDF)

Step 1: Select the uncolored vertex with the largest degree.

Step 2: Choose the minimum indexed color from the colors that are not used by adjacent vertices.

Step 3: Color the selected vertex using the color described in step 2.

Step 4: If all the vertices are colored, LDF stops. Otherwise, LDF returns to step 1.

Once the partitions are determined, the first-last fit spectrum allocation policy is adopted for spectrum allocation, this has already been explained in Chapter 4 (page number 44). The first-last fit spectrum allocation policy always attempts to choose the lowest indexed slots in the odd number partition from the list of available slots. For the even number partition, it attempts to choose the highest indexed slots from the list of available slots. The first-last fit allocation policy adopted in the partition scheme is expected to provide more contiguous aligned available slots.

The following steps are considered to estimate the overall time complexity of the first-last fit spectrum allocation policy. The time to check the arriving lightpath requests and find appropriate lightpath groups is 0(|Z| log |Z|), where Z is the set of lightpath requests. The time to check the partitions for assigning lightpath groups is 0(|C| log |C|), where C is the set of lightpath groups. The time to perform spectral allocation for Z lightpath requests using a given route is 0(|£||B||Z|) or 0(| V|2|Z|). E, В, V are the sets of links in the network, spectrum slots in each link, and nodes in the network, respectively. In the above steps, the third step is the dominating factor. Therefore, the overall time complexity of the spectrum allocation policy is 0(|V|2|Z|).

Dedicated partitioning approaches presented in the literature divide the spectrum into a number of partitions in advance by assuming traffic demands in order to suppress the fragmentation in the network. Considering that the traffic condition can never be fully predicted, it may happen that a lightpath with a large number of required slots may not be supported by a partition; in this situation, a lightpath request tends to be rejected. This will increase call blocking in the network. In addition, dedicated partitioning approaches fail to offer statistical multiplexing gain. Due to the lack of statistical multiplexing gain, blocking probability can increase in the network if the number of partitions is high. To overcome these issues, pseudo partitioning approaches have been considered, which are explained in the following section.

 
<<   CONTENTS   >>

Related topics