## 4 Proposed Method and Problem Formulations
### Problem Formulations
In the subsequent migration phases, there might have the chances of some routers which were already migrated to switches in a previous migration. Hence, fewer routers in the path are set to be migrated in the subsequent migration phases. The stub routers or backup path routers, if not migrated in the all shortest paths migrations, will be migrated in the last phase. The binding of the number of switches to the corresponding SDN controller depends on the traffic volume that a controller can process, and the requirement of minimum latency. One controller is generally sufficient to handle one AS in a multi-domain ISP network. However, the distance between the controller and switches matters such that the minimum round-trip latency is to be considered between controllers and switches [34]. For fail-safe operation and controller load balancing, additional controllers can be attached to the east and west bounds of the master controller, with at least one backup controller. Finding the approach to locate additional controllers in a large network is not within the scope of this paper. Figure 3: Extraction of shortest paths (SPs) from customer endpoint routers to a foreign gateway and breadth-first traversal (BFT) in the shortest path for router upgrades/replacement. RSS, root source switch. The average control path latency (\(\lambda\)) [34] due to \"\(n\)\" number of switches between switch \"\(s\)\" to controller \"\(c\)\" is defined by Equation (5):  
\[\lambda=\frac{1}{n}\sum_{i=1}^{n}\Delta_{s,c}\cdot x_{i}\in\{0,1\} \tag{5}\]  
Equation (5) considers the minimum path cost (\(\Delta\)) for the latency calculation. This average value can be considered a generalized value with respect to the number of switches in the network. Instead of averaging, we consider the actual propagation latency in the shortest path from the switch to the controller by considering the sum of hop-to-hop path cost as a control path latency. In an AS, legacy routing runs interior gateway routing protocols (e.g., Routing Information Protocol - RIP, Open Shortest Path First - OSPF). Based on the ONOS/SDN-IP implementation, any router when replaced with an SDN switch needs to configure directly attached routers with BGP, and establish an iBGP peering session with the BGP speaker. An automatic Python script enables BGP on those routers attached with the SDN switch; these are identified by Equation (6). \[\forall g_{i}\in R,\exists s_{j}:hop\_distance(g_{i},s_{j})=1 \tag{6}\]  
The average iBGP peering traffic latency due to \"\(k\)\" number of switch gateways is defined by Equation (7). \[\phi=\frac{1}{k}\sum_{i=1}^{k}\Delta_{g,c}\cdot y_{i}\in\{0,1\} \tag{7}\]  
Constraints to trigger controller addition is defined by Equation (8). \[\forall c_{j}\in C_{A}^{0},s_{j}\in c_{j},\tau\in(t+1,...,T):\sum_{v_{j}\in S, g_{j}\in R}(\gamma_{v_{j}}^{t}+\Psi_{g_{j}}^{t})\leq\sigma_{j}\cdot z_{j}^{t} \tag{8}\]  
Algorithm 1 identifies the LSSP in an AS of the network, while we implement the network migration and identify the controller location based on Algorithm 2. The simulation consists of several Python functions. The functions and their major tasks are summarized in the comments of the algorithm. ```
Data: Network topology net_data, Customer gateway records cg_data /* Load standard network data (net_data) as an AS (e.g., \"Abilene\") having the number of vertexes \"(\")\" and edges \"E\" for network graph G and also attached customer gateways (CGs).