A Distributed Switching Algorithm

The key to handling multiple switching cards is synchronizing the time during which cards stay in an ad hoc network. To enable cards in an ad hoc network to communicate with any other node in that network, there must exist an overlap in the time periods for which the members stay connected to the ad hoc network. We present a simple and efficient distributed algorithm that ensures concurrent connectivity among cards in an ad hoc network for at least a brief time period every switching cycle. The algorithm aims to converge the switching times for all the cards in an ad hoc network. Therefore, it tries to achieve synchronized switching to and from the ad hoc network for all members of that network. This solution is valid for single hop ad hoc networks. We do not attempt to solve the problem for multihop networks.

Notation: We use the following variables for describing our algorithm:

• $ATP_i$ : Activity (Time) Period in network $i$ . This is the duration the node stays connected to network $i$ .

• $\delta_i$ : The time taken to switch to network $i$ . This depends on the overhead of the switching protocol.

• $SC$ : Switching Cycle. This is the time interval for cycling through all networks. It is a constant fixed by the MultiNet software, and is known to all the nodes. It is the aggregation of the activity time periods and switching delay of all the networks, along with the sleep time, if any.

• $TEATP_i$ : This is the time elapsed inside $ATP_i$ . It can be anywhere from 0 to $ATP_i$ .

Algorithm Description: When a MultiNet node switches to a network $j$ where it has not yet formed an ad hoc network with any other node, it stays on the network for at least 2*$SC$ time to hear announcements from other nodes in $j$ . It also announces itself in the beginning of this interval. Thereafter the MultiNet node announces itself every $SC$ time interval in network $j$ . An announcement carries information about $ATP_j$ and $TEATP_j$ for the announcer. Nodes use this announcement to synchronize their time with the leader of the ad hoc group

We define a leader of an ad hoc network to be a node with the largest MAC address in that ad hoc network. So, if a MultiNet node hears an announcement from another MultiNet node with a bigger MAC address, it marks the announcer as its leader and changes its $ATP$ and $TEATP$ to that of the leader. Since the node knows the $SC$ , which is the same for all nodes, it is able to synchronize with the leader. It also stores the MAC address of the leader so that if the leader changes in the future, it can resynchronize itself with a new leader. If the announcement is from another MultiNet node with a smaller MAC address, the receiving node announces its $ATP$ and $TEATP$ after a random time interval in the range of 0 to WaitTime. WaitTime is less than or equal to minimum of the amount of time left to finish the network active time period, i.e $ATP_j$ $-$ $TEATP_j$ , of the node that triggered the announcement and the announcer. If nodes on a network stop hearing the leader for 2*$SC$ time interval i.e. for two full switching cycles, they assume that it is gone and resynchronize to the next leader.

Discussion: The above protocol aims at providing randomized synchronization among all the ad hoc nodes, with all the nodes synchronously switching into and out of the ad hoc network with a high probability. Moreover, in the absence of faulty nodes and when no announcement messages are lost, if the MultiNet nodes in the ad hoc network $j$ have the same $ATP_j$ value, then new MultiNet nodes joining network $j$ will converge on a single $ATP_j$ after a period of time no longer than $2*SC$ . This is true since a new node joining the network has to wait at most $2*SC$ time to hear an announcement from another node in the ad hoc network $j$ . This node synchronizes itself with the ad hoc network in the first $SC$ time period, and uses the remaining time to determine the value of $ATP_j$ .

An area of concern is that announcement messages are broadcast and are therefore unreliable. So it is possible for the announcement message to not reach all the ad hoc nodes. There might exist nodes that do not receive any announcement messages in a $SC$ time period. Fortunately, once a node has successfully joined an ad hoc network $j$ and assigned a value to ATP$_j$ , it mainly uses the announcement messages to maintain synchronization to the ad hoc network. So, MultiNet is not drastically affected by the loss of a few announcement messages.

The bigger problem with the above algorithm occurs when MultiNet nodes want to be connected to more than one ad hoc network. It is possible that nodes with largest MAC addresses in the two networks have overlapping times of activity in each network. In such a case, a node cannot be connected to both the networks, and even if it does, it may not synchronize its ATP values. We consider two solutions to solve this problem. The node might try to arbitrate with the leader of each ad hoc network to have non-overlapping periods of activity in each network. This approach has repercussions on other nodes in the network, and we therefore use the second solution in which the node joins both networks, but synchronizes its ATP value to only one network based on its priority. It remains connected to the other network for the remaining duration, but does not send any announcement messages with its ATP in this network. This ensures connectivity to both the networks. However, the node is not permitted to connect to both the networks if their activity periods overlap completely.

A disadvantage of this protocol is that it prohibits adapting switching durations for ad hoc networks based on local decisions at MultiNet nodes. In our current design, we make these decisions at the leader node, and the other ad hoc nodes synchronize themselves based on this value. It should be noted that this is just one solution and we are currently looking at better algorithms for enabling adaptability with synchronization in an ad hoc network. However, the above protocol works for purposes of MultiNet, and a better algorithm will only improve the results presented in Section 7. We note that the above protocol coupled with the Buffering Protocol, described in Section 5.2, only requires loose synchronization among nodes to ensure reliable packet sends and receives. While the switching protocol makes sure that any two nodes in an ad hoc network are connected for some time, the buffering protocol handles the sends and receives when nodes switch between multiple networks.