## 3 Problem Description and Formulation
### Description of SDN Controller Assignment Problem
\begin{table}
\begin{tabular}{c l} \hline \hline
**Parameter** & **Meaning** \\ \hline \(d_{p}\) & The latency of path \(p\). \\ \(\eta_{e}\) & Propagation latency of per kilometer of link \(e\in E\). \\ \(d_{e}\) & The distance between the source and the destination of link \(e\). \\ \(\mu_{v}\) & The service efficiency of the LFD \(v\). \\ \(T_{a}\) & The propagation latency of one available path \(a\). \\ \(m_{v}\) & The estimated queue length of the LFD \(v\). \\ \(\lambda_{v}\) & The message processing rate of the LFD \(v\). \\ \(Q_{v}\) & The queuing latency of \(v\). \\ \(R_{a}\) & The SFD-to-controller latency of the path \(a\) for successful transmission. \\ \(\delta_{v}\) & The messages loss rate of the LFDs \(v\). \\ \(L_{a}\) & The SFD-to-controller latency of the path \(a\). \\ \(F\) & The maximum tolerant time for the control message re-sending. \\ \(l(u)\) & The load of the SFD \(u\). \\ \(\omega(u,c)\) & The minimum latency between SFD \(u\) and a potential controller \(c\). \\ \hline
**Variables** & **Meaning** \\ \hline \(\pi_{uc}\) & Binary variables, which denote whether the SFD \(u\) is assigned to the controller \(c\) or not. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Cont. control message forwarding. The set of all latency-constrained paths between the controllers and the SFDs is denoted by \(A=\{p|d_{p}<D\}\), where \(d_{p}\) is the latency of path \(p\) and \(D\) is the maximum latency constraint of control messages. In the hybrid SDN WANs, each controller manages a portion of the SFDs and creates a control tree rooted at each controller, as shown in Figure 2. It is a control tree for Figure 1 when two controllers are placed at SFD 29 and 15. Seven SFDs \(\{4,12,14,19,20,29,31\}\) are under the control of Controller 1, and four SFDs \(\{11,15,17,26\}\) are under the control of Controller 2. Besides, the chosen paths for SFD-to-controller communication are also shown in the control tree. For example, SFD 11 uses path \(11-16-18-26-15\) to communicate with its controller. Controllers 1 and 2 use the path \(29-2-15\) to communicate with each other. The process of creating the control tree consists of four phases. Firstly, the controllers announce their presence. Secondly, they choose the control paths that are used for the control messages forwarding from all the latency-constrained available paths. Thirdly, based on the selected control messages forwarding paths, the capacity of controllers and the PACKET_IN load of SFDs, the matches between controllers and SFDs are decided. The assignment of SFDs to controllers is denoted by:  
\[\tau=\{\pi_{uc}|u\in S,c\in C\}, \tag{1}\]  
where \(\pi_{uc}\) is a binary that denotes whether SFD \(u\) is assigned to controller \(c\) or not. Finally, the control paths are established between the SFDs and its assigned controller. The latency of control messages is an important performance indicator of a hybrid SDN WAN. It describes the time taken for the control messages to travel across the network between the controller and the SFDs. The control message latency consists of processing latency, transmission latency, propagation latency, and queuing latency. The processing latency is the time taken by routers to process the header of the control messages which can be ignored in WANs. The propagation latency is the time taken for the control messages to be forwarded over a path which is one of the most important latencies in the WANs. The queuing latency is the time taken for the control messages to be queued in the routing queues. In this scenario, the control messages are transmitted among the data packets that form the actual payload on the same physical channel. The queuing latency in LFD and SFD is different. If the arrival rate of packets is faster than the process rate of the LFD, they are put into  
Figure 1: A hybrid SDN network with two controllers. SDN: Software-defined networking. a First-In-First-Out (FIFO) queue. The queuing latency that control messages experience in the queue is increased.