COMP9334 Revision Problems for Week 10A
Chun Tung Chou April 15, 2021
1. In this question, you will formulate an integer programming problem for the controller placement problem in software defined networking (SDN). We briefly discussed this problem in the beginning of the lecture in Week 8B, see pages 2-3 of the lecture notes for that week.
In SDN, there are two types of “boxes”: (1) Simple packet switches; and (2) Controllers. At each node of the network, there is a simple packet switch. However, we do not need to have a controller at each network node. We only need to place controllers at some of the network nodes, and one controller can be used to control multiple switches. Since a controller needs to communicate with those switches that it controls, the communication delay between a controller and a switch under its control must not be too big.
For the controller placement problem, you are given:
• A network (N,E) where N is the set of nodes and E is the set of edges. There is a simple packet switch at each node in N. We assume there are n nodes and they are indexed by 1, 2, …, n.
• The commuication delay dij between nodes i and j in the network, for all i, j ∈ N . This means that if a controller is placed at node i, then the communication delay between this controller and a switch at node j is dij.
• The maximum allowable delay D between a controller and the switches that it controls.
The requirements are:
• Each switch must be controlled by a controller.
• The delay between a controller and any switch that it controls cannot exceed D.
Formulate an integer programming to minimise the number of controllers required sub- ject to the above requirements.
1