Implementation of distributed and parallel computing in the SDN network

The paper discusses the execution of a program of tasks on the SDN data plane, modeled by a finite connected undirected graph of physical connections; the execution is understood in the sense of the object-oriented programming paradigm as consisting of objects and messages that objects can exchange. Objects are implemented in hosts. Several different objects can be implemented in one host and the same object can be implemented in several hosts. Messages between objects implemented in different hosts are transmitted in packets which are routed by switches based on identifiers assigned to packets that is on a set of values of some packet parameters in the packet header. Two problems are tackled in the work: 1) minimizing the number of identifiers, 2) setting up switches to implement the paths that packets should take place. These tasks are solved in two cases: A) a packet intended for some object must get into exactly one host in which this object is implemented, B) a packet can get into several hosts, but the desired object must be implemented in one and only one of them. It is shown that problem 1 in case A is equivalent to the set covering problem, and the minimum number of identifiers in the worst case is $\min\{ n, m \}$ where $n$ is the number of objects, and $m$ is the number of hosts implementing objects. In case B, the problem is a special modification of the set covering problem, the hypothesis is proposed that the minimum number of identifiers in the worst case is $\min\{\lfloor lb(n + 1)\rfloor, m\}$. So far, an upper bound is $O( \min \{ \ln (\min \{ n, m \}) \cdot \ln ( n, m ) \})$. To solve problem 2 in cases A and B, algorithms for switches’ setting are proposed which have the complexity $O( m )$ and $O( k m )$, respectively, where $m$ is the number of the edges of the graph of physical connections and $k$ is the number of the required packet identifiers.