SDN网络中的CPP（Controller Placement Problem ）控制器放置问题（一）
近年来，软件定义网络(SDN)不仅成为数据中心和广域网络的关键元素，而且也成为车载专用网络和5G等下一代网络架构的关键元素。SDN的特征是解耦的数据和控制平面，以及逻辑集中的控制平面。SDN中的集中式控制平面提供了多个机遇和挑战。SDN控制平面的一个关键设计选择是控制器的放置，这将影响各种网络问题，从延迟、从弹性、从能源效率到负载平衡等等。
SDN网络架构
SDN的关键思想是数据和控制平面的解耦，并提供一个集中的控制平面。因此，旧式交换机转换为纯转发元素，其转发表（在SDN中称为流表）由SDN控制平面填充。数据和控制平面之间定义良好的开放接口为可编程网络和网络创新铺平了道路。SDN控制平面监视和配置整个网络，便于测试单个新的路由协议或从单个控制点执行新的流量工程策略。SDN控制平面包括一个或多个控制器（见图1），通过(a)与南向协议（例如，OpenFlow[4]），(b)通过北行协议与应用通信，以及(c)通过东西通信协议（例如，SDNi[15]）相互通信。
CPP问题
（1）控制器部署几个？
（2）控制器部署在哪儿？
（3）控制器与交换机之间的映射关系？
CPP的几个方面值得关注。CPP可以通过不同目标的来检查，如网络响应性、容错性、弹性、QoS、负载平衡、能效、可靠性等
大多数研究是选择其中一个或者多个目标对CPP问题进行优化
CPP经典公式
CPP经典公式输出为控制器的个数，位置及S-C映射关系
代表控制器
是否存在，
代表交换机与控制器之间的映射关系。
在SDN中，CPP的以下整数线性规划(ILP)公式对于理解是很重要的，因为它代表了SDN CPP公式的最基本的形式。几乎所有其他的公式都可以看作是它的一个扩展。
经典的CPP公式的目的是最小化最大的交换机控制器延迟，如（1）所示。相应的约束条件被列出在（2)-(6）中。控制器容量约束（2），它确保映射到控制器的交换机的需求总和不超过其容量。约束（3）是控制器交换机控制器映射约束，它确保每个交换机完全分配给一个控制器。约束（4）保证仅在控制器存在时才将交换机映射到控制器。控制延迟约束（5），即对于每一对交换机-控制器映射，交换机与其控制器之间的延迟不超过延迟阈值。主要决策变量的二进制性质。
以上公式优化目标主要是交换机与控制器之间的时延，对于其他约束及目标并未考虑。在具体研究过程中需要进行补充，比如控制器之间的时延可以表示为两控制器之间距离和等。
可用约束
- 位置：控制器在交换机上，放置在整个交换机位置区域的任何位置，而不一定与交换机一起配置
- 控制器类型：作为控制模型可动态调整
- 交换负载：根据SDN类型划分对于具有单域的网络，来自SDN交换机的控制负载包括由其产生的包负载。然而，对于多域网络，SDN交换机的控制负载被视为其产生的包负载以及来自属于不同域的邻近交换机的负载的总和。
- 控制器处理时延：基于排队理论更现实地将其建模为M/M/1队列（如果单个控制器服务于每个交换机）或M/M/M/M队列（如果交换机的控制负载可以跨控制器拆分）
- 交换机之间的距离（链路权重）：一般为直线距离，实际精确计算
- 故障后场景：流量流向问题
- 同步处理成本：控制器之间网络信息同步带来的时延
- 控制器数量：作为输出
- 控制器容量：考虑控制器容量（以及开关负载）通常与控制器负载平衡作为CPP目标同步。
- 流量配置：动态配置
- 最近的控制器分配：多目标交换机映射控制器
- 网络故障：控制器、链路两方面的着手
优化方法
方法包括整数线性规划(ILP)方法、二次规划(QP)方法和博弈论方法
ILP优点：运行时间较短
单目标CPP大多使用ILP方法来解决，而多目标CPP通常使用博弈论或蛮力方法求解。
启发式解决方案的方法：
求解次优cpp解的方法主要有各种各样的基于图论的方法，元启发式的方法（基于模拟的退火和进化算法），然后是贪婪的方法。
贪婪算法是最流行、易于设计和快速的方法之一，尽管代价是陷入局部最优
模拟退火是一种迭代方法，它允许通过在算法的早期阶段移动到更差的解来逃避局部最优。
用于CPP的主要进化算法包括遗传算法、粒子群优化、自适应细菌觅食优化和萤火虫。
SDN中的CPP主要使用图论框架建模，这有助于利用图论中的良好技术，如聚类、网络分区、最小切割、图遍历、集覆盖等
【参考文献】
[1]. T. Das, V. Sridharan and M. Gurusamy, "A Survey on Controller Placement in SDN," in IEEE Communications Surveys & Tutorials, vol. 22, no. 1, pp. 472-503, Firstquarter 2020,