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: 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. 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 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 Each node u regularly broadcasts a list detailing for each group member v including itself the following el- ements: Figure 2: Self-stabilizing groups: convergence in two iterations 3.2 Intra-group routing 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). c d a b e 1 c d a b e 1’ c d a b e 2 c d a b e 2’ In a’s group or trying to join Not in group Agree that they are not in same group Agree that they are in same group Differ on group composition DTN HYMAD Node Group of nodes A node has mes- sage m One node in the group has message m and all other nodes in the group know that. Two nodes meet Two disjoint groups become con- nected.