## 3 Problem Description and Formulation
### Description of SDN Controller Assignment Problem  
The hybrid SDN WAN consists of SFDs (for example, OpenFlow switches) and LFDs (for example, Open Shortest Path First (OSPF) switches), as shown in Figure 1. It is assumed that multi-controllers have been deployed in a large-scaled hybrid SDN WAN with different locations. The network is divided into multiple control domains, and each of them is charged by only one SDN controller. In WAN, the controllers are usually co-located with regular network nodes, such as SFDs and LFDs, and the in-band model is used for communication between SFDs and controllers. The way of establishing the control relationship between controllers and SDFs is described as followed. Firstly, the controllers decide the set of SFDs in their charge, which is the controller assignment problem. Then, controllers send messages to their SFDs to establish the control relationship. After establishing the relationship, SFDs can find their target controllers to send control requests. As for which paths should be used for routing control messages, it depends on the flow table of SFDs, which is established according to instructions of its charged controller. A hybrid SDN can be denoted by \(G(S,LN,C,E,P)\), where \(S\) is the set of SFDs, \(LN\) is the set of LFDs, \(C\) is the set of controllers, \(E\) is the set of physical links in the network, and \(P\) is the location of controllers. The number of SFDs is \(|S|\) and the number of LFDs is \(|LN|\). The major traffic of switch-controller communications includes two types of control messages: (1) PACKET_IN, and (2) PACKET_OUT or FLOW_MOD [31]. Processing PACKET_IN messages is the most significant part of the working load of controllers [14]. An SDN controller has a limited capacity, which is determined by its access bandwidth, processor, memory size and so on. To avoid the overload of the controllers, a limited number of SFDs is allowed to be assigned to one specific controller. The set of controllers is denoted by \(C=\left\{B_{1},B_{2},...,B_{|C|}\right\}\) where \(B_{c}\) is the capacity of the controller \(c\), and \(|C|\) is the number of controllers. \(P\) is the location of controllers, which is denoted by \(P=\left\{p_{1},...,p_{|C|}\right\}\). Figure 1 illustrates \(S=\left\{4,11,12,14,15,17,19,20,26,29,31\right\}\), \(LN=\left\{1,2,3,5,6,7,8,9,10,13,...,35\right\}\), \(C=\left\{200\text{ Mb/s},100\text{ Mb/s}\right\}\), and \(P=\left\{29,15\right\}\). In the scenario of partial deployment of SFDs, there exist multiple available paths for SFD-to-controller packets forwarding. An available path that is loop-free is generated by the SFD routing configuration under the control of its assigned controller. For example, in Figure 1, the shortest path from Controller 1 to SFD 31 is \(29\to 7\to 33\to 31\). SFDs can choose the node in next hop under the control of controller, and node 29 can choose the next hop from \(\left\{7,33,5,19,23,9,12,10,2\right\}\). Thus, path \(29\to 5\to 25\to 1\to 31\) is another path that can be used for control messages from Controller 1 to SFD 31. However, because of the constraints of latency, not all available paths can be used for