content_image/432931.jpg content_image/432930.jpg
## 3 The HYMAD protocol 

## 3.1 Overview 

The core idea in HYMAD is to use whole groups of nodes instead of individual nodes as the focus of a DTN protocol. The analogy is detailed as follows: 

<img src='content_image/432931.jpg'>

Each node u regularly broadcasts a list detailing for each group member v including itself the following el- ements: 

1. The minimal number of hops from u to v . 

2. A list of the messages held by v . 

3. A bit indicating if v is a border node (i.e. in contact with other groups). 

The first two elements are necessary for the inter- group routing protocol. The second one in particular allows a group to agree on what messages it carries and which node (hereafter call the message’s custo- dian) specifically holds it. The last one enables use of an intra-group distance vector routing. As in tradi- tional distance vector algorithms, the number of iter- ative broadcasts necessary for all members of a group to agree on this information is equal to the diameter of the group. 

HYMAD then uses a DTN protocol to transfer mes- sages between groups. The approach is generic and many existing DTN protocols could be employed. In this paper, we use Spray-and-wait [13] to forward mes- sages between disjoint groups. As in Spray-and-Wait, the source of a message will create a certain number of copies of it. In HYMAD however, this source node is part of a group and copies of the message will be distributed among the adjacent groups instead of sim- ply the nodes that the source encounters. If a group has more than one copy, it will, in turn, distribute ex- tra copies to its other adjacent groups. If a group has just one copy it will wait until encountering the desti- nation’s group to transfer it. Once inside the destina- tion’s group, the intra-group routing protocol delivers the message to the destination. 

## 3.2 Intra-group routing 

In HYMAD, the intra-group routing is handled by a simple distance vector algorithm. 

The nodes are dynamically grouped with a dis- tributed network partitioning algorithm. In our imple- mentation, we chose to consider diameter-constrained groups. Groups will accept new members as long as its diameter is less than a maximum diameter parameter ( D max ). If a group’s diameter expands due to internal link failure, then some members are excluded to satisfy the diameter constraint. Ducourthial et al. [6] propose a self-stabilizing, asynchronous distributed algorithm that achieves this using an r $_{−}$operator on a slightly modified distance vector. This algorithm converges in O ( D max ) iterations. The proof of self-stabilization us- ing asynchronous message passing can be found in [5]. The main ideas behind group creation and modifica- tion are illustrated in Fig. 2 for a maximum diameter D max = 2. In the first iteration, node a begins by broadcasting the distance vector ( a : 0). Nodes b , c and d decide they want to join the group and broadcast ( b : 0 , a : 1), ( c : 0 , a : 1) and ( d : 0 , a : 1) respectively. After receiving the broadcast from d , node e also de- cides that it wants to join the group and broadcasts ( e : 0 , d : 1 , a : 2) (or ( e : 0 , d : 1 , c : 1 , a : 2) if c spoke before d ). In the second iteration, a now broadcasts ( a : 0 , b : 1 , c : 1 , d : 1), d realizes that the distance between b and e is greater than D max and therefore chooses to exclude e from the group and broadcasts ( d : 0 , a : 1 , c : 1 , b : 2). Finally e understands that it is not part of the group. After two iterations, the group has stabilized on a, b, c, d . Now lets suppose that at a later date the link between a and c goes down. Node 

<img src='content_image/432930.jpg'>

