| A network partition is formed when a set of network nodes is divided into non-overlapping subsets of nodes. Hence, each member of a network partition, known here as an island, consists of network nodes that do not belong to any other island. Within each island, one or more nodes, known here as reflectors, are responsible for communicating all content that is either originating from the island or destined toward that island. Inter-partition networking addresses the problem of communications among the islands of a network partition through their reflectors. Inter-partition networking and its related optimization problems have not been a focus for researchers in the context of overlay networks. Overlay networks bring a new dimension to the problem. In overlay networks, any node within a partition is a potential candidate for inter-partition communication. In this case, the key problem is which nodes should be selected as reflectors in order to achieve the best possible networking performance. In this work, we focus on providing multicast connectivity across the Internet by inter-partition networking. We prove that the inter-partition optimization problem (under certain constraints) is NP-hard. We propose an algorithm to solve this problem in polynomial time by relaxing one of the constraints. Finally, under another contribution of this work, we estimate the optimum solution by deriving the probability distribution function of the inter-partition network capacity, both analytically and numerically. We show that our estimate becomes more accurate as the number of nodes increase. |
