Wavelength Convertible 3R Regenerator (WC3R) Placement
3.3 WC3R Placement Strategies
3.3.1 Node Ranking Algorithms
The objective of this step is to rank the nodes in the order of importance within a network.
The term “importance” of a node here denotes the degree of demand for wavelength conversion and/or 3R regeneration at that node. Based on different knowledge of the network, two categories of ranking algorithms are developed:
i) Topology information based algorithm
If there is no other knowledge except the network topology and link lengths at the preliminary design stage of WSON, the centrality measures [52], [53] can be applied to quantify the importance of each node in the network. Three centrality-based algorithms are proposed, i.e., degree centrality-based algorithm, closeness centrality-based algorithm, and betweenness centrality-based algorithm.
The degree centrality (CD) firstly serves as an intuitive weight for nodal importance which is defined as the number of links attached to that node. The high-degree node is considered to be traversed by more lightpaths, which results in higher potential wavelength contention. Therefore, such node is among the top candidate locations for wavelength conversion. On the other hand, the link with longer length has more PLI accumulation, thus the node with longer links attached is also required to be highly weighted. Considering the above two facets, the calculation of nodal importance can be given by Eq. (3.7), where the denominator is the normalization factor introduced to make the summation of all node degree centralities equal to one.
However, the degree centrality is defined by using local structure information around the node and it fails to capture the global network characteristic. In order to achieve the latter, two other measures, i.e., closeness and betweenness centralities, are considered here based on the shortest-path. Within the limited knowledge of the network, the shortest-path can be either hop shortest-path (HSP) or length shortest-path (LSP). As mentioned in [7], the hop
count is the major factor related to blocking caused by wavelength assignment conflicts.
This is because it is difficult to find a free wavelength on all hops when the number of hops is large. Thus, the HSP is more preferable in centrality calculation in case of wavelength converter placement. On the other hand, the distance of a path is considered as a good approximation of PLI degradation and is mainly relevant to blocking arising from an inability to route a lightpath within the optical reach [7]. Therefore, the length is preferred to be used as the measure of shortest-path in centrality calculation with respect to regenerator placement.
The closeness centrality (CC) gives the highest score of importance to the node with the lowest average shortest-path distance to all other nodes, i.e., Eq. (3.8) [52]. More specifically, this measure estimates how fast the node can reach all other nodes in the network.
As mentioned above, the closeness value of each node i can be calculated by HSP or LSP, denoted as ܥሺ݅ሻ and ܥሺ݅ሻ, respectively, and wavelength converters are in great demand at the node with higher value of ܥ, whereas the 3R regenerators are preferred to be deployed at the higher ܥ-valued nodes. Based on this consideration, a hybrid closeness centrality ܥሺ݅ሻ is derived to weight each node i for WC3R placement, i.e., Eq.
(3.9), where a coefficient δ ranged from 0 to 1 is used to define their combination ratio.
Moreover, the HSP-closeness and LSP-closeness items in Eq. (3.9) are also normalized to be between 0 and 1, respectively. Thus, the summation of all node ܥ values is equal to one.
The concept of betweenness centrality (CB) highlights the nodes that most frequently lie on the shortest paths between other node pairs shown in Eq. (3.10) [53]. This index reflects the estimate of future traffic load transiting current node by the shortest paths. The betweenness values calculated by HSP and LSP algorithms are correspondingly denoted as ܥሺ݅ሻ and ܥሺ݅ሻ for each node i. Therefore, a hybrid betweenness centrality ܥ, like the hybrid closeness centrality is also proposed in Eq. (3.11) which combines the normalized HSP-based and LSP-based betweenness centralities to assume the value in the interval [0,1].
D( ) j S in( ) e i j( , ) (2 e E e),
C i
¦
l u¦
l i V (3.7)C( ) (| | 1) t V t i sp( , ),
C i V
¦
z d i t i V (3.8)HSP LSP
H C C
C HSP LSP
C C
( ) (1 ) ( )
( ) ,
( ) ( )
j V j V
C i C i
C i i V
C j C j
G G
u u
¦ ¦
(3.9)B
( , )
( ) ,
( , )
i s V s i t V t s i
C i s t i V
s t V
V
z z z
¦
¦
(3.10)sp sp sp
( , ) ( , ) if ( , )= ( , ) ( , );
here ( , )
0 otherwise.
i
s i i t d s t d s i d i t
s t V V
V ® u
¯
HSP LSP
H B B
B HSP LSP
B B
( ) (1 ) ( )
( ) ,
( ) ( )
j V j V
C i C i
C i i V
C j C j
G G
u u
¦ ¦
(3.11)3R λ
CRP
3R λ
( ) (1 ) ( )
( ) ,
( ) ( )
j V j V
I i I i
C i i V
I j I j
G G
u u
¦ ¦
(3.12)ii) Conversion and regeneration prediction algorithm
In many cases, more detailed information about the network can be available in advance such as PLI, traffic pattern, routing, wavelength assignment method, etc., which helps to determine WC3R placement. In other words, the nodes, which may suffer high blocking rate in the absence of wavelength conversion and/or 3R regeneration, can be identified by performing a preliminary simulation with such information. The WC3Rs are preferably allocated at these nodes. Based on this assumption, a novel heuristic method of WC3R placement is conceived, termed as conversion and regeneration prediction (CRP) depicted in Figure 3.2. It firstly assumes that each node has enough WC3Rs with full range wavelength convertibility in the network, thus no lightpath request will be blocked due to the lack of WC3Rs. Then, in each node i, two indices Iλ(i) and I3R(i) are assigned to respectively record the numbers of lightpaths that require wavelength conversion and 3R regeneration at node i when the CRP is running. Initially, they are set to zero in line 1. Upon receiving a lightpath request, the candidate path is calculated by a predefined routing algorithm. Along this path, the resource availability and PLI are evaluated simultaneously. If the wavelength runs out on a link of the path, the program just end the current lightpath provisioning process, i.e., line 7 and 8. The increment by 1 of Iλ(i) or I3R(i) related to current transit node i correspondingly occurs when there is no more continuous free wavelength, or the accumulated PLI, i.e., OSNR or PMD, violates its threshold, i.e., from code line 10 to 15.
Finally, the weight of each node is calculated by Eq. (12) after a large amount of lightpath requests following a given traffic pattern under which lightpath requests arrive and terminate in a dynamic manner.
It is worth noting that the traffic pattern is assumed to be given in advance. This traffic pattern could be achieved through a long-term observation of traffic demand in the network.
When the long-term traffic pattern changes, the replacement of WC3Rs will be desired. For instance, future portable WC3Rs, which are built into plug-and-play line-cards of core node systems in WSON, will enable the adjustment of the number of WC3Rs at a node, and makes
the WC3R replacement among the network possible. To focus on the issue of WC3R placement under given traffic pattern, the detailed issues related to WC3R replacement due to traffic pattern changes are out of the scope of this chapter.
CRP(G(V, E))
Note: Rc is a register used to record the previous node position where the wavelength conversion is required along a path, and at first, Rc is the source.
Assume that each node has enough FRWC3Rs.
1: Set Iλ(n) = 0, I3R(n) = 0 for each n אV;
2: Upon arrival of a request from s to t based on a given traffic pattern:
3: Run the predefined routing algorithm to get the working path p(s,t) (assume p(s,t) consists of q nodes, i.e., p(s,t) = {s=1, …, t=q});
4: Initialize location register: Rc = 1; //Point to the source 5: Set ܱܴܵܰݏ =ܱܴܵܰ and ܲܯܦݏ= 0;
6: for i = 1 to q-1 do:
7: if ݂ሺݏǡݐሻߣ (i,i+1) == 0 then //No free wavelength on link e(i,i+1) 8: break;
9: end if
10: if ݂ሺݏǡݐሻߣ (Rc,i+1) == 0 then //No continuous free wavelength 11: Iλ(i)++ and Rc = i; //between Rc and (i+1)th node 12: end if
13: if ܱܴܵܰ݅ͳ <ܱܴܵܰɅ or ܲܯܦ݅ͳ > α/B then //PLI violation 14: I3R(i)++, ܱܴܵܰ݅ =ܱܴܵܰ, and ܲܯܦ݅ = 0;
15: end if 16: end for
17: if no more incoming request then
18: Calculate CCRP(n) for each node n אV by Eq. (3.12) and output them;
19: else 20: goto 2;
21: end if
Figure 3.2 Pseudo code of CRP algorithm.