## 3 Problem Description and Formulation
### Problem Formulation  
In this subsection, the controller assignment problem in hybrid SDNs is formulated. According to the problem description and analysis above, SFD-to-controller latency between SFDs and controllers in hybrid SDNs can be simplified to include two main parts: (1) the propagation latency on paths; and (2) queuing latency of the LFDs. For the fist part of SFD-to-controller latency in hybrid SDNs, the propagation latency of one available path \(\alpha\) can be defined as follows:  
\[T_{\alpha}=\sum_{c\in\alpha}\eta_{e}d_{e},\forall\alpha\in A, \tag{2}\]  
where \(\eta_{e}\) is propagation latency of one available path \(e\) per kilometer and \(d_{e}\) is the distance of link \(e\). The set of all latency-constrained available paths between the controllers and the SFDs is denoted by \(A\). For the second part of SFD-to-controller latency in hybrid SDNs, we firstly assume that the message arrival of LFDs is a Poisson process. It has an exponential distribution of the service time in the M/M/1 queue, and it has a parameter \(\mu\) where \(\frac{1}{\mu}\) is the mean service time. Given the message processing rate of an LFD is \(\lambda_{v}\), its queuing latency can be denoted by:  
\[Q_{v}=\frac{\rho_{v}}{\mu_{v}(1-\rho_{v})}-\frac{m_{v}\rho_{v}^{m_{v}}}{\mu_{ v}(1-\rho_{v}^{m_{v}})},\forall v\in LN, \tag{3}\]  
where \(\rho_{v}=\frac{\lambda_{v}}{\mu_{v}}\) and \(m\) is the estimated queue length. Thus, if the control messages are successfully transmitted on path \(\alpha\), the SFD-to-controller latency can be defined as:  
\[R_{\alpha}=T_{\alpha}+\sum_{v\in LN}Q_{v},\forall\alpha\in A. \tag{4}\]  
Figure 2: The control tree of Figure 1.  
However, when the capacity of LFDs is much less than the traffic load, some messages may be dropped because of the limited length of the queue in LFDs. The messages loss rate of an LFDs is denoted by:  
\[\delta_{v}=\frac{1-\rho_{v}}{1-\rho_{v}^{m+1}}\rho_{v}^{m},\forall v\in LN, \tag{5}\]  
where \(\rho\) and \(m\) have the same definition with definition in (3). If the control packages are dropped because of LFDs, they need to be re-sent from the source nodes. As usual, there should be time limitation, and the control messages would resend from the source nodes after this time. In this model, we only considered one-chance re-sending, because repeated re-sending would waste a large number of resources. In this case, more controllers or more SFDs should be considered to be added to the network to improve the situation of networks. Thus, considering the re-transmission of the dropped messages, the SFD-to-controller latency of one path \(\alpha\) can be defined as:  
\[L_{\alpha}=R_{\alpha}+F(1-\prod_{v\in LN}(1-\delta_{v})),\forall\alpha\in A, \tag{6}\]  
where \(F\) is the maximum tolerant time. From this formulation, we can see that the loss rate of control messages in the LFDs is a very important metric to measure the performance of the controller assignment. For in a hybrid SDN, there exist multi-paths for control messages forwarding. It would be wise to choose the path with minimum SFD-to-controller latency. The minimum latency between an SFD and a potential controller is given by the following formula:  
\[\omega(u,c)=\min_{\alpha\in A_{uc}}L_{\alpha},\forall u\in S,c\in C, \tag{7}\]  
where \(A_{uc}\) is the set of latency-constrained available paths between SFD \(u\) and controller \(c\). The objective is to find a good match between the SFDs and the controllers to minimum the average SFD-controller latency:  
\[\min_{\pi}\frac{1}{|S|}\sum_{u\in S}\sum_{c\in C}\omega(u,c)\pi_{uc}, \tag{8}\]  
where the variable \(\pi_{uc}\) denoted whether the SDN device \(u\) is controlled by controller \(c\) or not.