Analysis and performance of complete homogeneous communication networks

Abstract

In this paper we address a fundamental problem in communication systems. A fully-connected system is modelled by a complete graph, where all nodes have identical capacities. A message is owned by a singleton. If he/she decides to forward the message simultaneously to several nodes, he/she will take longer (exactly, the number of simultaneous nodes times a single forwarding scheme). The only rule in this communication system is that a message can be forwarded by a node only if it fully known. The makespan is the completion time, precisely when the message is fully known by all nodes. The average waiting time is the average among the completion time of all individual nodes. The problem under study is to select the communication strategy that minimizes both the makespan and average waiting time. Intuition and current design of real networks say that oneto- many systems should perform better than one-to-one systems, however this is not usually true. A previous study claims that a sequential or one-to-one forwarding scheme minimizes the average waiting time, but they do not offer a proof. Here, a formal proof is included. Furthermore, we show that the sequential strategy minimizes the makespan as well. The paper is closed with comments on potential applications in scheduling of parallel machines, content delivery networks, peer-to-peer systems and rumour spreading.