# A Dynamic Restructuring Algorithm Based on Flexible PON Slices
## 3 Proposed Algorithm  
Based on the above model, a dynamic restructuring algorithm is proposed for the case when the number of OLTs is greater than 2 (that is, the number of subgraphs is greater than 2). At the beginning of the algorithm, the \(G(V,E)\) is divided into subgraphs of the target number, and the following calculation and adjustment operations are carried out simultaneously for all subgraphs. In this way, in the subsequent calculation, the changing traffic between subgraphs caused by node exchange after each calculation will be considered, and finally a global optimal solution will be obtained. In order to facilitate the description of the proposed algorithm flow, first, the definitions of various parameters used in the algorithm are given. These parameters are shown in Table 1.  
Where \(N=M\times K\), and the edge weight matrix \(E\) satisfies the following conditions:  
\[E(i,j)=\left\{ \begin{array}{cc}E(j,i)&i\
eq j\\ 0&i=j\end{array} \right. \tag{1}\]  
Figure 1: Centralized flexible PON architecture. Figure 2: Network model  
In addition, since _E(i, i)_ = 0 when calculating the traffic between \(i\) and itself. Therefore, _TT(i, X)_ can be calculated as follows regardless of whether \(i\) is in subgraph _X_:  
\[TT(i,X)=\sum_{j\in G_{X}}E(i,j) \tag{2}\]  
_Gex(i,j)_ is defined as the reduction in the total edge weights between \(M\) subgraphs after two nodes are swapped. Since our algorithm initially divides _G(V,E)_ into subgraphs of the target number, the traffic gain after swapping any two nodes is related to the subgraphs they belong to. Assuming that node \(i\) belongs to subgraph \(X\) and \(j\) belongs to subgraph \(Y\), then _Gex(i,j)_ can be calculated as follows:  
\[Gex(i,j)=TT(j,X)+TT(i,Y)-TT(j,Y)-TT(i,X)-2E(i,j) \tag{3}\]  
According to the definition of _Gex_(i,j), if all the _Gex_(i,j) between any nodes in the whole undirected graph _G(V,E)_ are less than or equal to 0, it indicates that any exchange of two nodes will no longer result in the reduction of the total edge weights between subgraphs. Therefore, the proposed DRA sets it as the algorithm end decision condition. Figure 3 shows the flow of the algorithm. The SDN controller firstly obtains the communication relationship between all ONUs through the MAC table of OLTs, and generates the traffic relationship matrix \(E\) between them. Then, it divides all ONUs into M subgraphs, and each subgraph has \(K\) nodes. It should be noted that, in real life, all ONUs have been configured before the controller obtains information, and the current OLT to which it links to can be known. The initial state is \(M\) subgraphs. Therefore, there are two methods for the SDN controller to divide all ONU nodes into \(M\) subgraphs. One is to directly use the obtained \(M\) subgraphs as the initial state to calculate, the other is to disarrange all the nodes and randomly generate M subgraphs as the initial state. Due to the randomness of the arrival of new traffic, the initial state of the two methods is essentially random and both can be used. However, the former is recommended to be used because it does not need to re-randomize, which can reduce the amount of computation of the controller and save computing resources. After _G_(V,E) is divided into M subgraphs, the controller calculates the _Gex_(_i,j_) of any two nodes in all the M subgraphs and swaps the two nodes with the largest _Gex_(_i,j_) until all _Gex_(_i,j_) are less than or equal to 0. The subgraph to which the two nodes swapped in each loop belong is not immutable. Finally, the SDN controller converts the calculated results into instructions using the Openflow protocol and sends them to OLTs, and OLTs inform ONUs to switch wavelength for slice reorganization.