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.