# An Efficient Dynamic Load Balancing Scheme Based on Nash Bargaining in SDN
## 2 Analysis and Modeling
### Model Construction
#### 2.2.1 Load Balancing Degree  
When an unknown flow enters the switch, it needs to send PACKET-IN messages to the controller to query the forwarding policy. The controller responds to the switch request, delivers the flow table items, and installs a new routing rule to the switch. The controller load is mainly composed of maintenance management domain information, flow table installation, and inter-domain controller synchronization overhead.  
Maintaining management domain information overhead  
In SDN network architecture, distributed controllers manage switches centrally. In order to maintain global network information, controllers need to communicate with switches periodically to collect information such as traffic and the hops of switches in their management domain. As shown in Equation (1), the traffic required to maintain the management domain is related to the polling switch speed, the connection relationship between switches and controllers, and the number of hops between devices.  
\[\Psi_{c_{i}}=\sum_{k=1}^{N}vx_{ki}d_{ki} \tag{1}\]  
Among them, \(\Psi_{c_{i}}\) denotes the traffic required by controller \(c_{i}\) to maintain the management domain, \(v\) denotes the average rate of the controller polling switch in the control domain, \(x_{ki}\) denotes the connection relationship between switch \(s_{k}\) and controller \(c_{i}\), and \(d_{ki}\) denotes the hops between device \(k\) and \(i\).  
When a new flow arrives at the switch, the switch sends a flow request to the controller. The controller formulates the flow table rule according to the flow request and delivers the rule to the corresponding switch. The generated flow table installation overhead is shown in Equation (2),  
\[\mathrm{Y}_{c_{i}}=\sum_{k=1}^{N}\lambda_{k}x_{ki}d_{ki} \tag{2}\]  
where \(\mathrm{Y}_{c_{i}}\) represents the flow table installation cost generated by controller \(c_{i}\), and \(\lambda_{k}\) represents the flow request rate of switch \(s_{k}\).  
When the data flows through different control domains, the controllers need to perform state synchronization to maintain the consistency of the SDN global network view. The inter-domain controller synchronization overhead generated by this process is shown in Equation (3),  
\[\Gamma_{c_{i}}=\sum_{c_{i}\
u_{i}\in\mathbb{C}}\tau d_{ij} \tag{3}\]  
where \(\Gamma_{c_{i}}\) represents the inter-domain controller synchronization cost of controller \(c_{i}\), and \(\tau\) represents the average rate of polling the controller, because the controller does not synchronize all the information of the switch, so it satisfies \(\tau<v\).  
The load of controller \(c_{i}\) is a linear addition of the above three parts, as shown in Equation (4).  
\[L_{c_{i}}=\Psi_{c_{i}}+Y_{c_{i}}+\Gamma_{c_{i}} \tag{4}\]  
The average load of the controller is shown in Equation (5).  
\[\overline{L}=\frac{1}{M}\underset{i=1}{\overset{M}{\sum}}L_{c_{i}} \tag{5}\]  
In statistics, the coefficient of variation is usually used to characterize the degree of dispersion between data, expressed as the ratio of the standard deviation of the data to the mean, which is a normalized measure of the degree of the dispersion of the probability distribution. Therefore, the coefficient of variation is used in SDN to measure the load balancing degree of the controller, as shown in Equations (6) and (7),  
\[\sigma=\frac{1}{M}\sqrt{\underset{i=1}{\overset{M}{\sum}}\left(L_{c_{i}}- \overline{L}\right)^{2}} \tag{6}\]  
\[LBD=(1-\frac{\sigma}{\overline{L}})\times 100\% \tag{7}\]  
where \(\sigma\) is the standard deviation and \(LBD\) is the load balancing degree. The larger the \(LBD\) value, the more balanced the load.