Initiation, Formation and Usage of Spontaneous PN-F

Since in the spontaneous PN-F, the federation is formed in the absence of a fixed infrastructure; therefore we extend our proposal for PN cluster formation i.e. PNRP, for the initiation, formation and usage of spontaneous PN-Fs. The Personal Network Routing Protocol (PNRP) extension for PN-F is a variant of on-demand multi-hop routing protocol such as AODV and DSR, which adapts to the personal networking environments for communication among PNs. The PN-F creator decides the PN-F members and sends them, the PN-F profile. On the reception of PN-F profile, if the initially proposed members decide to be the part of PN-F, they exchange their PN-F participation profile with the PN-F creator.

Therefore, PN-F initiation becomes an intrinsic capability of PN-F formation owed by PNRP. Moreover, PN-F routing mechanisms assist to determine the routes towards the desired PN-F members and provide means to form and to use PN Federations.

PN-F Topology Discovery, Initiation and Formation

PN-F routing builds routes using a join request/reply query cycle. When a PN desires to create a PN-F with certain defined PN-F members, it creates a PN-F profile and sends to its FMs, piggybacked with a Join-Request (JR) message, leveraging the inter-cluster routes; thanks to PNRP's PN-cluster formation capability. As show in Figure 1, in order to create a PN-F with PN2, PN3 and PN4, the PN1 (i.e. PN-F creator) sends the JR message to its FMs. The Join-Request (JR) message contains two lists of PN-IDs such as "destination-list", which stores the potential PN-F participants and "destination-attained-list", which represents the PNs already attained by the JR message. As FMs receive the JR, they investigate whether the PN-ID of their neighbouring PN is mentioned in JR message destination-list. In case of positive response, the JR is forwarded to the FM of the neighbouring PN. In contrast, if the FM does not find the adjacent PN in the destination-list and the potential participant PNs are not accessible through other FMs of the same PN, a "Connectivity PN-F" can be formed with the adjacent PN in order to relay the PN-F information towards the potential PN-F members.

 
Figure 1: PN-F topology discovery in PNRP

On the reception of JR message, the neighbouring PN's FM first removes its PN-ID from JR's destination-list and then put it in the destination-attained-list. Moreover it also sets up backward pointers in PN-F routing table, towards the PN which sent the JR, as a next-hop to reach all the PNs mentioned in the destination-attained-list. PN1's FM (i.e. A) forwards the JR to PN2's FM (i.e. B), which sets the entries in its PN-F routing table that PN1 is reachable through its FM B.

The above presented mechanisms are repeated at each next PN until all the PNs mentioned in the JR destination-list are reached. Finally, on the reception of JR if the PN finds the JR's destination-list is empty, it will send a Joint-Request-Ack (JRA) message (by replacing the entries of destination-attained-list with destination-list) backwards to the PN which forwarded the JR message. As shown in Figure 1, the JRA is initiated by PN4, which receives the empty destination-list. The mechanisms of setting backward pointers to the PNs declared in destination-attained-list and moving the PN-IDs from destination-list to destination-attained-list at every next PN is also repeated for JRA message until it reaches the PN-F creator, who triggered the PN-F formation. The exchange of JR and JRA messages facilitate the establishment of PN-F routing tables at the Federation Managers of PNs, which are participating in the PN-F.

Data Forwarding and PN-F Use

During the integrated PN-F topology discovery process, the entire participant PNs learns the routes not only towards the PN-F creator but also towards each other. These routes are stored in the PN-F routing table and are leveraged to exchange, initially the PN-F profiles and then the PN-F participation profiles in order to form the PN-F. To this end, the data packets destined to any other PN are first forwarded to the FMs, which further routes the data with the help of PN-F routing table. The profiles are stored at the FMs (the entry points of PNs), which are used to enforce PN-F policies on the PN-F routing in order to ensure secure PN-F overlay concept.

PN Cluster Formation and Personal Network Routing Protocol (PNRP)

The initial step towards the PN formation is the formation of PN clusters i.e. all the personal nodes that are in the close vicinity of each other discover the routes towards each other. Subsequently, the different geographically separated clusters of a PN are glued together to form a PN with the help of PN Agent. To this end, we propose the Personal Network Routing Protocol (PNRP) which helps in determining the routes among all the personal nodes in a PN cluster.

PNRP is a variant of link-state multi-hop routing protocol that adapts to the personal networking environments. It maintains the proactive topology of nodes which lie within the PN cluster boundary, at every personal node of the PN cluster. Moreover, the information on functionalities of the personal nodes such as Gateway Node and/or Federation Manager is also exchanged within the PN topology in order to facilitate PN's access to the outside world. In the following subsections, we discuss different steps that PNRP performs towards the formation of a PN cluster.

Integrated Topology Discovery

The role of Integrated Topology Discovery mechanism is to determine how the personal nodes are connected (using which interfaces in single/multi hop) in order to provide routes for any source/destination pair in the PN cluster. It first determines the direct connectivity among nodes and further exchanges this information to form a unified cluster topology.

Neighbor discovery is incorporated into PNRP by allowing every personal node to periodically transmit "Hello" packets on all of its interfaces. "Hello" packet contains the PN-ID and the Node-ID of the source node which is processed at the destination node to identify the source of the "Hello" packet. It is possible that the personal nodes may discover the non-personal nodes; therefore PN level authentication is indispensable. Every node maintains a 1-hop neighbour table and associated costs to each link with its direct neighbours and their PN identification. For the current implementation of PNRP, we have considered number-of-hops as a cost metric.

Once the 1-hop topology is formed, it is exchanged with other personal nodes in order to form a complete snapshot (table) of the PN cluster on its every single node. The topology information is only exchanged with the personal nodes i.e. among the nodes which belong to the same PN. To this end, every personal node periodically transmits the "Cluster topology (Ctopo)" message towards all its personal nodes (neighbours). On the reception of "Ctopo", the PN cluster routing tables are formed/updated and further exchanged with the other neighbouring nodes. Figure 1 shows the PN routing table at a personal node constructed after the exchange of "Hello" and "Ctopo" messages.

 
Figure 1: PNRP for PN routing

Gateway and Neighboring PN's Discovery

In PNRP, each Gateway Node (GN) advertises in the "Hello" message, whether it has connectivity with the infrastructure network or not. As can be seen in Figure 1, the exchange of integrated PN cluster topology with the help of "Ctopo" message permits each node to maintain routes to all the existing GNs and the cost to reach them, in the PN routing table.

Discovery of the neighbouring PNs is also intrinsic to Integrated Topology Discovery mechanism. During the exchange of "Hello" messages, if the destination node finds out that it's not the part of the source node's PN (with the help of PN-ID), the destination node sets itself as a Federation Manager (FM) to the source node's PN. The connectivity among the PNs is realised with the help of FMs. Once the integrated topology information is exchanged among all the nodes of the PN, every node knows the exit points (FMs) to communicate with other neighbouring PNs, which further helps in PN to PN (PN-F) routing. In case of multiple GNs or FMs, the minimum cost option is selected.

Route Discovery

PNRP differentiates the route discovery procedure when the destination is the part of same PN as the source and/or from the case when the destination is the part of different PN. In latter case, "PNRP for PN-F" mechanisms are triggered. In former case, since a proactive PN cluster-level topology is maintained at each PN node, the route to all the destinations in the PN will be known before time.