Dynamic multi-hop multipath RMSA and traffic grooming in OFDM-based sliceable elastic optical networks

2.1.Number of spectrum slots

The number of spectrum slots for establishing a lightpath for provisioning a connection request includes the number of spectrum slots for data transmission, the number of reserved spectrum slots (if any), and the number of guard band slots (if any), where the reserved slots are reserved using the spectrum reservation scheme employed in [13]. The number of data slots is calculated based on the bandwidth requirement of the connection request, the selected modulation format, and the symbol rate per subcarrier. The number of guard band slots for the lightpath depends on whether the optical grooming mechanism is used. If the optical grooming mechanism is not used, guard band slots are required around the data slot(s). On the other hand, when the optical grooming mechanism is employed, no guard band is needed to separate the lightpath from the side-by-side lightpath along the common portion of the routes of the two lightpaths [16,35]. Let f(p) denotes the sum of the number of spectrum slots for carrying the traffic of a lightpath p and the number of spectrum slots (if any) reserved on lightpath p. Let the number of guard band slots at link l on lightpath p be gl(p). Let the total number of spectrum slots required to establish lightpath p be denoted by ψ(p) which is calculated as follows:

Fig. 2.

A lightpath p in a network with 5 nodes.

For example, lightpath p in Fig. 2 originated at node 1 and terminated at node 5 along route 1−4−5 consists of two physical hops, i.e., h(p)=2. The status of spectrum slots 31 through 37 are shown in Fig. 2. The status of the rest of spectrum slots are not shown. Suppose that slot 34 at links (1,4) and (4,5) is allocated to lightpath p for carrying traffic and that slots 33 and 35 at the two links are allocated as guard bands, i.e., f(p)=1, g(1,4)(p)=2, and g(4,5)(p)=2. Thus, the total number of spectrum slots required to establish lightpath p in Fig. 2 is calculated as ψ(p)=2×1+2+2, i.e., ψ(p)=6.

The total number of spectrum slots required to establish a lightpath p is normalized to a value between 0 and 1 by dividing it by its largest possible value. The widest lightpath can occupy all spectrum slots supported by a sliceable transponder. Let St denote the number of spectrum slots supported by a sliceable transponder. This paper uses one of the K shortest routes between the originating and terminating nodes to establish a lightpath. Let H be the hop count of the route with the largest number of physical hops among the K shortest routes between any pair of nodes. The largest possible number of spectrum slots for establishing a lightpath is StH. The normalized number of spectrum slots required to establish a lightpath p, ψ˜(p), is calculated as follows:

Suppose that two shortest paths between any pair of nodes in the example network in Fig. 2 are used for establishing lightpaths, i.e., the value of K is 2. For the example network shown in Fig. 2, the route with the largest number of physical hops among the K (K=2) shortest routes between any pair of nodes is 3, i.e., H=3. Suppose that the number of spectrum slots supported by a sliceable transponder is 10, i.e., St=10 which is also the largest possible number of spectrum slots for establishing a lightpath. Thus, the normalized number of spectrum slots required to establish lightpath p in Fig. 2 is calculated as ψ˜(p)=6/(10×3)=0.2, i.e., ψ˜(p)=0.2.

2.2.Spectrum fragmentation

Spectrum fragments of various sizes in terms of spectrum slots are created as lightpaths are established and torn down dynamically. Compared with a spectrum fragment of small size, a spectrum fragment of large size is more flexible for provisioning upcoming connection requests with different bandwidth requirements. A spectrum fragment of large size also has larger number of alternatives for accommodating a connection request with a given bandwidth requirement. It is preferable to use a smaller spectrum fragment to establish a lightpath to provision a connection request leaving spectrum fragments of larger sizes for upcoming connection requests.

This paper defines the fragmentation cost of a lightpath as the sum of the sizes of the spectrum fragments created by the lightpath. Let ϕl(p) be the fragmentation cost of lightpath p at link l, which is the sum of the numbers of contiguous free spectrum slots (if any) with immediate lower and higher spectrum indices than the spectrum slots used by lightpath p at link l. Let the number of contiguous free spectrum slots (if any) with immediate lower indices than the spectrum slots used by lightpath p at link l be denoted by xl(p) and the number of contiguous free spectrum slots with immediate higher indices than the spectrum slots used by lightpath p at link l be denoted by yl(p). If the lowest indexed spectrum slot is allocated to lightpath p at link l, xl(p) is zero. Similarly, if the highest indexed spectrum slot is allocated to lightpath p at link l, yl(p) is zero. Let ϕ(p) be the fragmentation cost of lightpath p, which is calculated as follows:

The fragmentation cost of lightpath p is normalized to a value between 0 and 1 by dividing it by its largest possible value. The largest possible value of the fragmentation cost of a lightpath p is less than the number of spectrum slots on an optical fiber multiplied by H. Let the number of spectrum slots on an optical fiber be denoted by Sf. The normalized fragmentation cost of lightpath p, ϕ˜(p), is calculated as follows:

For the example network and lightpath p in Fig. 2, the number of contiguous free spectrum slots with immediate lower indices than the spectrum slots used by lightpath p at link (1,4) is 0, i.e., x(1,4)(p)=0. the numbers of contiguous free spectrum slots with immediate higher indices than the spectrum slots used by lightpath p at link (1,4) is 1, i.e., y(1,4)(p)=1. Similarly, the numbers of contiguous free spectrum slots with immediate lower and higher indices than the spectrum slots used by lightpath p at link (4,5) are respectively 1 and 1, i.e., x(4,5)(p)=1 and y(4,5)(p)=1. Thus, the fragmentation cost of lightpath p in Fig. 2 is calculated as ϕ(p)=0+1+1+1=3, i.e., ϕ(p)=3. Suppose that the number of spectrum slots on an optical fiber is 320, i.e., Sf=320. Recall that the route with the largest number of physical hops among the K (K=2) shortest routes between any pair of nodes in the example network is 3, i.e., H=3. The normalized fragmentation cost of lightpath p in Fig. 2 is calculated as ϕ˜(p)=3/(320×3), i.e., ϕ˜(p)=1/320.

2.3.Spectrum misalignment

The concept of spectrum “misalignment” has been described in [31,32] as one that breaks the continuity of available spectrum slots between a link and a neighbor link when a lightpath is established. The definition of the number of spectrum misalignments in [32] counts the number of breaks of spectrum continuity created due to the establishment of the lightpath. While the definition in [31] adds the number of spectrum misalignments created and deducts the number of spectrum misalignments vanished due to the establishment of the lightpath. We are concerned with the effect of the spectrum misalignments created by a lightpath on the provision of upcoming connection requests. Thus, this paper adopts the definition in [32].

Let αl(p) denote the number of misalignments created at link l on lightpath p. The total number of misalignments created by lightpath p, α(p), is calculated as

Fig. 3.

(a) A lightpath p in a network with 5 nodes. (b) Misalignments created due to the allocation of slots 33, 34, and 35 to lightpath p at link (1,4). (c) Misalignments created due to the allocation of slots 33, 34, and 35 to lightpath p at link (4,5).

For example, Fig. 3(b) shows that, when spectrum slots 33, 34, and 35 are allocated to lightpath p at link (1,4), the spectrum continuity of free slots 33 and 34 between links (2,1) and (1,4) are broken and that the spectrum continuity of free slots 34 and 35 between links (1,4) and (4,3) are broken. Figure 3(c) shows that, when spectrum slots 33, 34, and 35 are allocated to lightpath p at link (4,5), the spectrum continuity of free slot 35 between links (3,4) and (4,5) is broken and that the spectrum continuity of free slots 34 and 35 between links (4,5) and (5,3) are broken. Thus, the allocation of spectrum slots 33, 34, and 35 to lightpath p creates a total of 7 misalignments, i.e., α(p)=7.

The total number of misalignments created by lightpath p is normalized to a value between 0 and 1 by dividing it by the maximum number of misalignments that can be created by a lightpath. To find the maximum possible number of misalignments, we assume that the degree of all of the nodes in the network are D, where D is the largest degree of the nodes in the network. The maximum number of spectrum slots that can be used to establish a light path is the maximum number of spectrum slots supported by a transponder St. The maximum number of misalignments that can be created at the first or the last link on a lightpath is St(D−1+D−2), i.e., St(2D−3). The maximum number of misalignments that can be created at one of the rest of the links on the lightpath is 2St(D−2). Thus, the maximum number of misalignments that can be created by a lightpath p with H physical hops is

The largest degree of the nodes in the network in Fig. 3 is 3, i.e., D=3. Again. suppose that the number of spectrum slots supported by a sliceable transponder is 10, i.e., St=10 which is also the largest possible number of spectrum slots for establishing a lightpath. Recall that the route with the largest number of physical hops among the K (K=2) shortest routes between any pair of nodes in the example network is 3, i.e., H=3. The normalized number of misalignments created by lightpath p is calculated as α˜(p)=7/(10(4×3−6+2(3−2)(3−2))=7/80, i.e., α˜(p)=7/80.

The larger the number of spectrum misalignments in the network, it is more difficult for an RSA/RMSA algorithm to find a routing path that satisfies the spectrum continuity constraint. Thus, it is preferable to use a lightpath that yields smaller number of spectrum misalignments to provision a connection request. Hopefully, the RSA/RMSA algorithm has higher probability to successfully find lightpaths(s) to provision upcoming connection requests.

In recent years, the channel slicing and stitching technology [6] has been proposed to remove the spectrum continuity constraint such that misaligned spectrum slots can be allocated to a lightpath. If this technology is adopted in an EON network in which all nodes are equipped with sufficient number of splitting components and stitching components such that splitting process and stitching process can be performed whenever required even at intermediate nodes along any routing path, the spectrum continuity constraint can be completely removed and the spectrum-misalignment term in the lightpath weight can be dropped. However, if the splitting process or stitching process cannot be carried out at any of the nodes when required (i.e., the spectrum continuity constraint must be observed at the node for certain pair of links), the spectrum-misalignment term can be used to reflect this effect to some extent. Example situation where splitting process may not be able to be performed is that each node in the network is equipped with a limited number of slicers [2,18] or that only a subset of the nodes in the network are equipped with slicers [2]. In the EON networks considered in this paper, the channel slicing and stitching technology is not adopted.

2.4.Lightpath weight of a lightpath p

Calculation of the lightpath weight of a lightpath p depends on whether p is an existing lightpath or a candidate lightpath to be established. Let z(p) be the lightpath weight of a lightpath p. For a candidate lightpath p, its lightpath weight is calculated as the sum of the normalized fragmentation cost, normalized number of misalignments, and normalized number of spectrum slots of lightpath p, i.e.,

For an existing lightpath p, grooming traffic onto p electrically does not create additional spectrum fragmentation or misalignment or occupy extra spectrum slots. Among different existing lightpaths that can be used to provision the traffic, it is desirable to use an existing light path that occupies smaller number of spectrum slots. Therefore, the normalized number of spectrum slots of existing lightpath p is used as its lightpath weight, i.e.,

3.1.Auxiliary graph

An auxiliary graph is constructed based on the topology of the network, a target bandwidth to be satisfied, and the resource status of the network. The target bandwidth for constructing an auxiliary graph is either the remaining bandwidth of a connection request to be satisfied or the bandwidth of a maximum bandwidth path from the source node to the destination node of the connection request, whichever is smaller. The target bandwidth for constructing an auxiliary graph is denoted by bt. Each node in the network has a corresponding vertex in the auxiliary graph. The edges in the auxiliary graph are classified into single-lightpath edges and multi-lightpath edges.

3.1.1.Single-lightpath edge

It is preferable to use an existing lightpath with sufficient residual bandwidth to provision a connection request. If there is at least one existing lightpath from node i to node j with residual bandwidth greater than or equal to the target bandwidth bt, select the one with the least lightpath weight with ties broken arbitrarily and add a single-lightpath edge from vertex i to vertex j. Otherwise, try to find all candidate lightpaths, including candidate lightpaths using optical grooming and without using optical grooming, with just enough number of spectrum slots to support a bandwidth of bt along the K-shortest physical paths from node i to node j. The spectrum reservation scheme used in [13] is employed to reserved spectrum slots. If at least one such candidate lightpath is found, select the one with the largest capacity and add a single-lightpath edge from vertex i to vertex j. Ties are broken by choosing the candidate lightpath with the least lightpath weight with further ties broken arbitrarily.

Figure 4(a) show a network with 5 nodes. Suppose that an existing lightpath with residual bandwidth greater than or equal to the target bandwidth bt or a candidate lightpath with a capacity greater than or equal to the target bandwidth bt can be found between each of the following node pairs: (1,2), (1,4), (2,1), (3,1), (4,1), (4,3), (5,1), (5,3), and (5,4), where (s,d) is a source-destination pair with source node s and destination node d. A directed single-lightpath edge is added between each of these node pairs in the auxiliary graph as shown in Fig. 4(b).

Fig. 4.

(a) A network with 5 nodes. (b) Auxiliary graph with only single-lightpath edges. (c) Auxiliary graph with single-lightpath and multi-lightpath edges.

3.1.2.Multi-lightpath edge

An attempt is made to add a multi-lightpath edge from vertex i to vertex j only when a single-lightpath edge has not been added. The flowchart for trying to add a multi-lightpath edge from vertex i to vertex j is presented in Fig. 5.

Fig. 5.

The flowchart for trying to add a multi-lightpath edge from vertex i to vertex j in the auxiliary graph.

All exiting lightpaths from node i to node j are sorted according to their residual bandwidths with ties broken by giving priority to existing lightpaths with lower lightpath weights. Select one or more existing lightpaths until the aggregated residual bandwidth is greater than or equal to the target bandwidth bt or the upper limit on the number of existing lightpaths L is reached. In this paper, the value of L is selected to be 5. If the aggregated residual bandwidth of the selected existing lightpath(s) is greater than or equal to bt, a multi-lightpath edge from vertex i to vertex j is added in the auxiliary graph to represent the set of selected existing lightpath(s).

If the aggregated residual bandwidth of the selected existing lightpath(s) is less than bt, one or more candidate lightpaths are needed such that the aggregated residual bandwidth of the selected existing lightpath(s) and candidate lightpath(s) is greater than or equal to bt. Note that no single candidate lightpath is able to provide a bandwidth of bt since no single-lightpath edge from vertex i to vertex j was added. Find all candidate lightpaths, including candidate lightpaths using optical grooming and without using optical grooming, along the K-shortest physical paths from node i to node j and sort them in descending order of their capacities with ties broken by giving priority to candidate lightpaths with lower lightpath weights. The spectrum reservation scheme used in [13] is employed to reserved spectrum slots. Select one or more candidate lightpaths until the sum of the residual bandwidths of the selected existing lightpath(s) and capacities of the selected candidate lightpath(s) is greater than or equal to bt or there no candidate left to be selected. If the sum of the residual bandwidths of the selected existing lightpath(s) and capacities of the selected candidate lightpath(s) is less than bt, no multi-lightpath edge from vertex i to vertex j is added.

If the sum of the residual bandwidths of the selected existing lightpath(s) and capacities of the selected candidate lightpath(s) is greater than or equal to bt, it is possible that one or more selected existing lightpaths can be removed such that the aggregated bandwidth of the remaining selected lightpaths is still greater than or equal to bt since the lightpaths are selected in two different stages. It is obvious that none of the candidate lightpath(s) can be removed since they are selected in the second stage. If the aggregated capacity of the selected candidate lightpath(s) is greater than or equal to bt, all selected existing lightpath(s) can be removed. Otherwise, sort the previously selected existing lightpath(s) in descending order of their residual bandwidths and select one or more existing lightpaths until the sum of the residual bandwidths of the selected existing lightpath(s) and capacities of the selected candidate lightpath(s) is greater than or equal to bt. The rest of the previously selected existing lightpaths (if any) that are not selected at this stage are removed. A multi-lightpath edge from vertex i to vertex j is added in the auxiliary graph to represent the set of selected lightpath(s).

In Fig. 4(b), no single-lightpath edge was added between each of the following node pairs: (1,3), (1,5), (2,3), (2,4), (2,5), (3,2), (3,4), (3,5), (4,2), (4,5), and (5,2). An attempt is made to find a set of lightpaths with aggregated bandwidth greater than or equal to bt between each of these node pairs. Suppose that this attempt is successful for each of the following node pairs: (1,3), (2,5), (3,2), (3,4), (3,5), (4,2), and (5,2). A directed multi-lightpath edge is added between each of these node pairs as shown in Fig. 4(c). Figure 4(c) also shows that no edge appears between each of the following node pairs: (1,5), (2,3), (2,4), and (4,5).

3.2.The algorithm

When a connection request (s,d,b) with source node s, destination node d, and requested bandwidth b arrives, the proposed dynamic multi-hop multipath RMSA and traffic grooming algorithm constructs one or more auxiliary graphs and tries to find one or more paths to provision the connection request. Let br be the remaining bandwidth of the connection request to be satisfied, which is initially b. An upper limit Nsd is placed on the number of source-to-destination paths in the auxiliary graphs used to provision a single connection request to prevent the coexistence of too many lightpaths in the network since a larger number of lightpaths requires more spectrum for guard bands. A source-to-destination path in an auxiliary graph will be referred to as an sd-path for simplicity. Let nsd denote the number of sd-paths found so far in the algorithm.

Two types of auxiliary graphs are used in the algorithm for finding one or more sd-paths to provision the connection request. The first type of auxiliary graphs consists of only single-lightpath edges among the node pairs. The second type of auxiliary graphs contains both single-lightpath and multi-lightpath edges among the node pairs. Let Ω denote the type of auxiliary graphs. The value of Ω is either S representing the first type or B denoting the second type. Let AG(Ω,bt) denote an auxiliary graph of type Ω, in which the set of lightpaths represented by each edge is found based on a target bandwidth of bt.

Algorithm 1

Multi-hop algorithm

The proposed dynamic multi-hop multipath RMSA and traffic grooming algorithm is given in Algorithm 1. The proposed algorithm consists of a single-path phase and a multi-path phase. The term “single-path phase” is referring to the process of finding a single sd-path in the auxiliary graph. Similarly, the term “multi-path phase” is referring to the process of finding multiple sd-paths in the auxiliary graphs. The two phases are combined into a single iterative procedure (the Repeat-Until loop, lines 2 through 28). The first iteration of the algorithm is the single-path phase and the rest iterations belong to the multi-path phase. The multi-path phase is performed only when the single-path phase is unable to find a sd-path to provision the connection request.

Each iteration of the multi-hop algorithm consists of two parts. The first part of each iteration corresponds to the first loop of the For loop (lines 12 through 26) in which Ω=S. The second part consists of the second loop of the For loop in which Ω=B. In the first part, the algorithm uses an auxiliary graph consisting of only single-lightpath edges to try to find a sd-path. The second part is executed only when the first part is not able to find a sd-path. In the second part, the algorithm uses an auxiliary graph containing both single-lightpath edges and multi-lightpath edges to try to find a sd-path.

The target bandwidth bt for constructing an auxiliary graph need to be determined before constructing an auxiliary graph. In the first iteration, the target bandwidth bt for constructing an auxiliary graph is set to the requested bandwidth b (line 1). In the rest iterations, the target bandwidth bt is determined at the beginning (lines 4 through 9) of each iteration.

At the beginning of each iteration except the first iteration, the algorithm finds the bandwidth of a maximum bandwidth path from the source node s to the destination node s by constructing a slightly different auxiliary graph and solves a max-bandwidth path problem [19] (lines 4 and 5). The auxiliary graph consists of both single-lightpath and multi-lightpath edges among the node pairs based on a target bandwidth of br with a slight different criterion in adding a multi-lightpath edge between a node pair. A multi-lightpath edge is added between a node pair regardless of whether the total bandwidth of the selected existing lightpath(s) and candidate lightpath(s) is greater than or equal to the target bandwidth or not. The weight assigned on each edge is the total bandwidth of the set of lightpaths represented by the edge. This auxiliary graph will be referred to as a bandwidth-based auxiliary graph. The algorithm then finds a path with the maximum bandwidth from source node s to destination node d using the bandwidth-based auxiliary graph by solving a max-bandwidth path problem [19].

Let bˆ denote the bandwidth of the max-bandwidth path from node s to node d. If bˆ is zero (lines 6 through 8), the connection request is blocked since there is not enough available bandwidth to fully provision the connection request. Otherwise (line 9), the target bandwidth bt for constructing an auxiliary graph is set to bˆ or the remaining bandwidth to be satisfied br, whichever is smaller.

Then the first part of each iteration (the first loop of the For loop) tries to find a sd-path from source node s to destination node d in an auxiliary graph consisting of only single-lightpath edges among the node pairs (lines 13 and 14). If no sd-path can be found, the algorithm continues with the second part of the current iteration (the second loop of the For loop). On the other hand, if a sd-path can be found in the first part (line 15), the algorithm (i) uses the lightpaths represented by the edges along the sd-path to provision (or partially provision) the connection request (line 16), (ii) increments the number of sd-paths by one (line 17), (iii) updates the remaining bandwidth to be satisfied (line 17). If the remaining bandwidth to be satisfied is zero, accept the connection request and terminate the algorithm (lines 18 through 19). If the number of sd-paths reaches the upper limit Nsd and the remaining bandwidth is not completely satisfied, block the connection request and terminate the algorithm (lines 20 and 21). If the requested bandwidth is not completely fulfilled and the number of sd-paths is less than the upper limit Nsd, proceed to the next iteration in the Repeat-Until loop (line 22). The second part of each iteration (the second loop of the For loop) employs an auxiliary graph consisting of both single-lightpath edges and multi-lightpath edges among the node pairs to try to find a sd-path from node s to node d (lines 13 and 14). The rest operations of the second part of each iteration are the same as those of the first part of each iteration. The algorithm continues iteratively until the requested bandwidth is completely fulfilled or the connection request is blocked.

Figure 4 can be used as an example to briefly explain the proposed multi-hop multipath RMSA and traffic grooming algorithm. Let node 1 be the source node and node 5 be the destination node of an incoming connection request with a bandwidth requirement of b. Suppose that the first iteration of the Repeat-Until loop is not able to find any sd-path with sufficient bandwidth to provision the connection request, i.e., both the first and second loop of the For loop are unable to find a sd-path. The algorithm enters the second iteration of the Repeat-Until loop. The algorithm finds the bandwidth, bˆ, of a maximum bandwidth path from node 1 to node 5, which must be less than b since the first iteration of the Repeat-Until loop is unable to find a sd-path with sufficient bandwidth. Hence, the target bandwidth bt for constructing an auxiliary graph is set to bˆ. The algorithm then proceeds to the For loop. Suppose that the first loop (Ω=S) of the For loop constructs an auxiliary graph as shown in Fig. 4(b). No sd-path from node 1 to node 5 can be found in the auxiliary graph shown in Fig. 4(b). The second loop (Ω=B) of the For loop constructs an auxiliary graph as shown in Fig. 4(c). Suppose that a shortest sd-path 1−2−5 is found in the auxiliary. The set of the lightpaths represented by the single-lightpath edge (1,2) and multi-lightpath edge (2,5) is used to partially provision the connection request. The algorithm then proceeds to the next iteration of the Repeat-Until loop until the condition (br=0 or nsd=Nsd or STOP=true) in line 28 of the algorithm is satisfied.

5.1.Simulation model

Two network topologies are used in our performance study, namely, the 14-node NSFNET with 21 bidirectional links and the 24-node USNET with 43 bidirectional links as shown in Figs 6(a) and 6(b) respectively. Each link consists of two optical fibers one in each direction. The lengths of the fibers in terms of kilometers are shown on the links in the figures. The total number of available spectrum slots on each fiber is 320 and the width of each spectrum slot is 12.5 GHz. For a lightpath without employing the optical grooming mechanism, guard bands are added on both sides of the traffic slot(s). The width of each guard band is one spectrum slot.

The number of SBVTs in each node is 48 multiplied by the degree of the node. Each SBVT consists of 3 sub-transponders. Each SBVT is able to support up to 10 sub-carriers and 4 modulation formats, namely, BPSK, QPSK, 8-QAM, and 16-QAM. For simplicity, it is assumed that SNR (signal to noise ratio) loss in the EON nodes can be compensated such that transmission reach for a given modulation format is a fixed distance. Techniques for compensation of SNR losses due to various components in the nodes have been discussed in [22]. With the above assumption, the transmission reach for QPSK is selected to be 7,200 Km [7]. The transmission reaches for BPSK, 8-QAM, and 16-QAM are chosen respectively to be 14,400 Km, 3,600 Km and 1,800 Km according to the half-distance law [4].

Connection requests are assumed to arrive at the network according to Poisson process with a mean arrival rate of λ per time unit. Holding times of connection requests are assumed to be exponentially distributed with a mean of one time unit. Bandwidth requirement of each connection request is randomly selected among 10 Gbps, 40 Gbps, 100 Gbps, and 160 Gbps.

The source and destination nodes of each connection request are selected in the following manner. For the NSFNET topology, measured traffic data [21] is used to derive the probabilities for selecting source and destination nodes. The probability that a node is selected as the source node of a connection request is calculated as the ratio of the amount of outgoing traffic of the node to the total amount of outgoing traffic of all nodes. Given a selected source node i, the probability that node j, j≠i, is selected as the destination node is computed as the ratio of the amount of traffic from node i to node j to the total amount of outgoing traffic of node i.

Fig. 6.

(a) The topology of the 14-node NSFNET with 21 bidirectional links. (b) The topology of the 24-node USNET with 43 bidirectional links.

For the USNET topology, a guideline for generating non-uniform traffic [26] is used to derive the probabilities for selecting source and destination nodes. The nodes are classified into “Large” nodes and “Small” nodes. Six of the nodes, namely, nodes 5, 6, 8, 10, 15, and 16, are selected as “Large” nodes and the rest of the nodes are “Small” nodes. Traffic distribution among the nodes is as follows: Large-Large: 40%, Large-Small: 40%, Small-Small: 20%. The probabilities for selecting source and destination nodes are calculated based on the traffic distribution.

5.2.Comparison of bandwidth blocking ratios

Fig. 7.

Comparison of bandwidth blocking ratio.

Figures 7(a) and 7(b) compare the bandwidth blocking ratios. It can be observed that all three versions of the proposed MHMP algorithm yield lower bandwidth blocking ratios than the MP-MSU algorithm proposed in [13]. The main reason is that the edge weight on each edge in the auxiliary graph used in the proposed MHMP algorithm is related to the lightpath weights of the set of the lightpaths represented by the edge, which in turn is related to the number of spectrum slots occupied by the lightpaths, spectrum fragmentation, and spectrum misalignment of the set of lightpaths represented by the edge. Whereas spectrum fragmentation and spectrum misalignment are not considered in the MP-MSU algorithm proposed in [13]. The proposed MHMP algorithm uses the minimum-weight sd-path in the auxiliary graph to provision a connection request implying that lightpaths with less number of spectrum slots, less spectrum fragmentation, and less spectrum misalignment are selected to provision the connection request. Thus, the lightpaths along the minimum-weight sd-path induce less spectrum fragmentation and less spectrum misalignment leading to more useful available spectrum resource for provisioning upcoming connection requests resulting in lower bandwidth blocking ratio.

Comparing the proposed MHMP algorithm with different values for the limit on the number of sd-paths in the auxiliary graphs, when the traffic load is low, in general, the higher the limit on the number sd-paths in the auxiliary graphs the lower the bandwidth blocking ratio. In other words, the MHMP-inf algorithm yields lower bandwidth blocking ratio than the MHMP-3 algorithm and the MHMP-3 algorithm yields lower bandwidth blocking ratio than the MHMP-1 algorithm. The reason is that spectrum resource in the network is abundant when the traffic load is low. With abundant spectrum resource, the proposed MHMP algorithm with higher limit on the number sd-paths is able to use more lightpaths to try to fulfill more connection requests resulting in lower bandwidth blocking ratio. However, when the traffic load is medium to high, spectrum resource in the network is somewhat rare to rare. The proposed MHMP algorithm with lower limit on the number sd-paths uses spectrum resource relatively more conservatively leaving more spectrum resource for upcoming connection requests. Thus, the proposed MHMP algorithm with lower limit on the number sd-paths is able to yield lower bandwidth blocking ratio.

5.3.Comparison of spectrum utilization factors

Fig. 8.

Comparison of spectrum utilization factors.

Figures 8(a) and 8(b) show the spectrum utilization factors. It can be observed that, when the traffic load is low, all three versions of the proposed MHMP algorithm yield lower spectrum utilization factors than the MP-MSU algorithm proposed in [13]. The reason is that the proposed MHMP algorithm prefers to utilize residual bandwidths of existing lightpaths to provision connection requests, whereas the MP-MSU algorithm does not give priority to using residual bandwidths of existing lightpaths. When the traffic load is low, it is likely that residual bandwidths of existing lightpaths can be found to provision connection requests without establishing new lightpaths resulting in lower spectrum utilization factors for the three versions of the proposed MHMP algorithm than the MP-MSU algorithm proposed in [13].

As the traffic load increases, residual bandwidths of existing lightpaths and available spectrum slots along sd-paths with smaller number of hops become scarce. Giving priority to using residual bandwidths of existing lightpaths may need to use residual bandwidths of existing lightpaths along sd-paths with larger number of hops requiring more bandwidth for provisioning connection requests. Thus, when the traffic load is high, all three versions of the proposed MHMP algorithm yield higher spectrum utilization factors than the MP-MSU algorithm proposed in [13]. This phenomenon is more evident as the limit on the number sd-paths increases for the proposed MHMP algorithm. The proposed MHMP algorithm with larger limit on the number sd-paths yields higher spectrum utilization factor.

5.4.Comparison of sub-transponder utilization factors

Fig. 9.

Comparison of sub-transponder utilization factors.

Figures 9(a) and 9(b) compare the sub-transponder utilization factors. It can be observed that all three versions of the proposed MHMP algorithm yield lower sub-transponder utilization factors than the MP-MSU algorithm proposed in [13] except when the traffic load is high in the USNET topology. The reason is that all three versions of the proposed MHMP algorithm prefer to use residual bandwidths of existing lightpaths to provision connection requests; i.e., sharing sub-transponders of existing lightpaths is preferable than using free sub-transponders to establish new lightpaths. The MP-MSU algorithm proposed in [13] also employs electrical grooming mechanism; however, no preference is given to using residual bandwidths of existing lightpaths. Hence, all three versions of the proposed MHMP algorithm use electrical grooming mechanism significantly more frequently than the MP-MSU algorithm. Therefore, all three versions of the proposed MHMP algorithm yield lower sub-transponder utilization factors than the MP-MSU algorithm.

When the traffic load is high in the USNET topology, the proposed MHMP algorithm having a limit on the number of sd-path of three or infinity yields higher sub-transponder utilization factor than the MP-MSU algorithm. This is because the USNET topology has larger number of nodes and links compared with the NSFNET topology. Hence, there are more alternatives for finding an sd-path between each pair of nodes in the USNET topology. When the traffic load is high, the residual bandwidths of existing lightpaths and available spectrum slots are scarce along sd-paths with smaller number of hops and smaller number of concatenated lightpaths. The MHMP-3 and MHMP-inf algorithms allow more sd-paths to be used to provision each connection request than the MHMP-1 and MP-MSU algorithms. Therefore, in the USNET topology, it is more likely that the MHMP-3 and MHMP-inf algorithms use sd-paths with larger number of concatenated existing lightpaths or new lightpaths at high traffic load to provision connection requests resulting in occupying larger number of sub-transponders.

5.5.Comparison of average number of existing lightpaths per request

Figures 10(a) and 10(b) show the average number of existing lightpaths per request. It can be observed that all three versions of the proposed MHMP algorithm yield higher average number of existing lightpaths per request than the MP-MSU algorithm proposed in [13]. This is because all three versions of the proposed MHMP algorithm prefer to use electrical grooming mechanism to groom traffic of connection requests onto existing lightpaths with residual bandwidths. In contrast, the MP-MSU algorithm proposed in [13] does not give priority to using electrical grooming mechanism although it also employs electrical grooming mechanism.

The two figures also show that the average number of existing lightpaths per request increases as the traffic load increases. As the traffic load increases, on the average, the residual bandwidth of each existing lightpath decreases since the average bandwidth of the traffic carried by each existing lightpath increases when the traffic load increases. With smaller average residual bandwidth in each existing lightpath, it is likely that a larger number of existing lightpaths is used to fulfill a connection request.

Comparing the three versions of the proposed MHMP algorithm, the average number of existing lightpaths per request increases as the limit on the number of sd-paths increases, i.e., the MHMP-inf algorithm yields higher average number of existing lightpaths per request than the MHMP-3 algorithm and the MHMP-3 algorithm yields higher average number of existing lightpaths per request than the MHMP-1 algorithm. The average number of sd-paths used to provision a connection request increases as the limit on the number of sd-paths increases. A larger number of sd-paths is likely to contain a greater number of existing lightpaths. Thus, the average number of existing lightpaths per request increases as the limit on the number of sd-paths increases.

Fig. 10.

Comparison of average number of existing lightpaths per request.