Secure implementing a virtual network on the SDN data plane

The paper continues the investigations on the implementation of virtual networks on the SDN data plane which is modeled by a graph of physical connections between network nodes. A virtual network is defined as a set of ordered host pairs (sender, receiver), and it is implemented by a set of host-host paths that uniquely determine the switch settings. The opportunities to transmit a packet are limited by the host weights (priorities): a packet can be only transmitted from a host to a host if the sender has at most the same priority as the recipient, and thus, a set of paths is permissible if its every subset connects permissible host pairs. In the paper, it is proven that differently from the case when every host pair is permissible, in the graph with priorities a permissible path implementation does not exist for every set of permissible hosts. Moreover, it is shown that is some cases when such an implementation exists, the implementation is not possible without paths with cycles where packets can move infinite and without duplicate paths when a host can get the same packet several times. Using the notion of a perfect set of paths a criterion is established when every permissible set of hosts can be safely implemented by a set of paths without cycles but possibly with duplicate paths.