3.4 Discussion 3.3 Inter-group routing 4 Results on Rollernet data 4.1 Methodology We evaluate HYMAD’s performance on Roller- net [14], a highly connected and extremely mobile con- nectivity trace. The Rollernet experiment involved equipping 62 participants of the regular Sunday after- noon rollerblading tour through Paris with contact log- gers (Intel iMotes). In order to witness different behav- With this in place, when a node wants to send a message, it simply adds it to its own list of messages. Through the intra-routing protocol, in O ( D max ) time, the group’s border nodes will become aware of the new message and request copies to forward it on to the ad- jacent groups. 4 Choosing a diameter parameter for the group self- stabilization algorithm involves a trade-off. On the one hand, increasing it will expand each node’s individual “knowledge horizon” of the actual network topology. Fewer copies will cover a larger portion of the network, which will naturally lead to faster delivery. On the other hand, this comes at the cost of increasing the convergence time and overhead of the group service. Ideally, the convergence speed should be considerably faster than the speed of topology changes. In a sense, extreme mobility may fundamentally limit a node’s possible knowledge of the network’s topology. The increased overhead results from each node regularly broadcasting a list of all messages in its group. Larger groups mechanically lead to longer control messages. If one is willing to incur the extra cost, the diameter can be set to encompass the entire network. In such a situation, HYMAD resembles a resilient MANET rout- ing protocol using store-and-forward for message trans- fers. Furthermore, in many mobile wireless scenarios, there are underlying social dynamics at work which can sometimes drive nodes to gather into loose communi- ties. D max should be chosen so as to allow the expected number of members per social group to neatly fit into one self-stabilizing group. Conversely, when a border node receives copies of a new message from an adjacent group it can either: When a border node learns that its group has ac- quired copies of a message that a neighboring group does not possess, it has the following choices: Border nodes take care of most of the inter-group DTN routing. Indeed, the periodic broadcast protocol described in 3.2 puts them in the unique position of knowing both the composition of two adjacent groups as well as the messages they hold. Border nodes may request the custodian of a message to transfer one of more copies to it. An internal link failure may cause a group to split into several separate sub-groups due to its diameter in- creasing. In such a situation, each sub-group only has a fraction of the messages of the original group. Fortu- nately this is not really a problem. Firstly, the intra- group protocol detailed in 3.2 ensures that nodes will update their message lists accordingly when removing nodes from their group member lists, thereby prevent- ing a sub-group from advertising messages it does not have or any other such incoherences. Secondly, cer- tain subgroups may still be connected to each other. If either sub-group has more than one copy of some mes- sages, these will be copied over the other sub-group. In any case HYMAD recovers gracefully from group splits. c now only receives the broadcasted distance vector ( d : 0 , a : 1 , b : 2) from d . It then understands that it is no longer part of the group. As is obvious from this example, a given topology can result in very differ- ent groups depending on the order in which the nodes speak. In this paper, we used this algorithm in a proac- tive fashion where each node node periodically runs the algorithm and broadcasts its distance vector. Group composition therefore changes in reaction to topology changes rather than routing needs. • If the message’s destination is in the neighboring group, request the message from its custodian and pass it on. • If its group has more than one copy of the mes- sage, request min ( 1 , ⌊ n$_{c}$ n$_{b}$ ⌋) copies from its cus- todian and pass them on. ( n c is the number of copies and n b the current number of border nodes in the group). The idea is to fairly spread a group’s copies among its adjacent groups. • Otherwise do nothing • If the destination is in its group, forward the mes- sage to it using the inter-group routing protocol. • Otherwise, randomly select a group member to be the custodian for the copies. This is done to spread the burden over members of a group.