On the broadcast of segmented messages in dynamic networks

This paper makes a systematic attempt to understand the effect of message size on the speed and efficiency of message broadcast. It considers a realistic situation where a single message may be too large to be sent in over a single connection and hence might require to be transmitted in segments. In specific, we look into the push and pull message transfer techniques and investigate in details their effect on broadcast time as well as total number of redundant contacts incurred during the transmission of segmented messages. For such segmentation and a complete graph topology with n nodes, we observe that the time required for broadcast scales as nk-1/k (assuming there are k packets in one message segment) as opposed to log n in the single message epidemic case (k = 1). In order to improve broadcast time and reduce the number of useless contacts we propose different variants of the push and pull message transfer techniques. In this regard we introduce the concept of giveup, which allows a node to terminate broadcast on sensing its neighborhood has received the message. We further study the effect of message segmentation on various types of topologies like d-regular graph, random graph etc. and observe that even for simple push technique, there exists an optimal d for which the dynamics becomes fast. We also simulate our results on real traces and finally provide some suggestions for network designers which we believe will help in faster message dissemination and lesser wastage, especially in case of dynamic networks.