Article Preview
Top1. Introduction
Distributed networks can be described by a group of nodes that establish two-way communication channels. In settings with limited resources, it is often useful to model the communication between nodes in a network in order to develop efficient protocols. One example of such a protocol is group key agreement, in which a single message must be distributed to all members of the group in a secure and efficient manner. Consequently, as a precursor to the development of key agreement protocols, a method to model the message distribution time to all members of a group is a vital part of evaluating protocols built on this message distribution model.
Generally, group message distribution is initiated by a single node in the network who wishes to transmit a copy of a single message to every member of the group. There are several ways of performing this message distribution: (1) via point-to-point exchanges between the source node and every other node in the network, or more efficiently, (2) by recursively distributing the message from the source node to nearby neighboring nodes, who then in turn re-distribute the message on behalf of the source to their nearby nodes (this process repeats recursively until every node in the network receives the message). Our model relies on approach (2) for performance reasons. Furthermore, the recursive message distribution naturally produces a spanning tree topology over the connected network of nodes (see the timeline in Figure 1 for an illustration of this result).
In this work, we model the message distribution process with a Markov chain and then compute the expected message distribution time in this type of group-based communication setting. Our model captures a network and message distribution scenario with the following properties:
- •
A fixed network (group) size,
- •
A limitation on the number of connections which can be made by any single node,
- •
The probability that two nodes successfully establish a communication link, and
- •
For a message M that requires m - 1 exchanges to transfer, the probability that each exchange in the transmission is successful.
Our model is then verified via Monte Carlo simulations and useful trends are used to derive parameterized equations for computing the approximate message distribution time. We then conclude with a discussion of related work and motivating applications to which our model may be applied.
The model we present is by no means a first attempt at quantifying the performance of message distribution in ad-hoc (and related) networks. Similar Markov-based analyses have been performed for ad-hoc networks (Groenevelt et al. (2005)). Kong and Yeh (2008) also study the same problem, but include node mobility in their analysis, which is distinct from our fixed location ad-hoc network. The problem of message distribution latency has also been framed in different contexts, including both epidemic routing (Zhang et al. (2007)) and rumor spreading (Trpevski et al. (2010)). While constructed under related scenarios, these models are developed for different purposes with noticeable analytical differences. We discuss all of these related works at length in Section 5.
Top2. Group Message Distribution Model
Before presenting our model, we formalize the problem statement. We assume a network of n nodes, where each node can potentially establish communication with any other node. One node, denoted as 
, is assumed to contain a message M which is to be distributed to all other nodes in the network. In order to send the message from one node 
to another 
, two steps need to occur: