NTK_RFC 0010

Subject: Viphilama - Virtual to Physical Layer Mapper

This text describes a change to the Npv7. It will be included in the final documentation, so feel free to correct it. But if you want to change the system here described, please contact us first.

Viphilama

Viphilama will permit to Netsukuku to expand itself over the Internet and then switch automatically to the physical layer without interfering with the stability of the Net.

Applications

Viphilama transforms Netsukuku into a hybrid overlay network which expands the original structure of the Internet. Its main advantages are:

Basic idea

The basic idea of Viphilama is to connect, with Internet tunnels, nodes which aren't physically linked. Then whenever, Viphilama finds that a virtual link can be replaced by a physical one, it removes the virtual link.

Assume this scenario: 

        Tokyo      Moscow          Rome      London
          |          |               |         |
          |          |               |         |
          |__________|Internet tunnel|_________|

All the cities are linked with Internet tunnels.

When Tokyo and Moscow will be linked by a series of physical nodes, Viphilama will change the net in this way: 

        Tokyo<--ntk nodes-->Moscow     Rome          London
                             |          |               |
                             |______ Internet tunnel ___|

When even Moscow and Rome will be linked by physical nodes: 

        Tokyo<--ntk nodes-->Moscow<--ntk nodes-->Rome          London
                                                  |                |
                                                  |__ Inet tunnel _|

And finally: 

        Tokyo<--ntk nodes-->Moscow<--ntk nodes-->Rome<--ntk nodes-->London

This is only the general description of the Viphilama idea, actually, the implementation is a bit more complex ;)

Layer

Netsukuku will be split in two layer: the virtual layer and the physical one.

The physical layer

The physical layer is the original Netsukuku layer: every node is linked to other nodes by physical links (wifi, cables, ...). The physical layer is prioritised over the virtual one.

The virtual layer

The virtual layer is built upon the Internet or any other existing network. The Netsukuku nodes, in this layer, are linked each other by tunnels.

Coordinates

A node, in order to join in the virtual layer, has to know its physical coordinates. The use of geographical coordinates is required for Viphilama, because it has to map the virtual layer to the physical one and it needs a way to measure the effective distance between two virtual nodes.

The coordinates can be retrieved using an online map service like http://maps.google.com or with a GPS.

The coordinates are stored in the internal, external and bnode maps. In the internal map there are the coordinates of each single node. In the external maps, the coordinates which locate a gnode are set to its barycenter: it is the average of the coordinates of all its internal nodes.

The coordinates don't affect the anonymity of the user worse than the Internet does, in fact, it is possible to make a guess about the geo location of an IP (see xtraceroute). If the user doesn't specify its accurate location, then the xtraceroute method will be used to retrieve an approximated location.

Two nodes may share the same coordinates. This happen when they use inaccurate coordinates, i.e. xtraceroute associates the same location to two IPs of the same city. In this case, the difference of their IPs will be used as an (inaccurate) measure of the distance. Or in other words:

Terminology

The virtual layer is composed by the same elements of the physical layer, for this reason they have the same names but the are prefixed with 'v'.

Gate node

The two layers are joined by the gate nodes. They are nodes which belong to both layers. This means that the two layer form a unique network.

The short name of a gate node is simply "gate", in this way it isn't confused with gnode (group node).

Virtual to Physical mapper

Viphilama is the supervisor of the topology of the entire net, it shapes the virtual layer and merges it with the physical one trying to achieve the best balance.

It follows simple rules:

Let's go into the details.

Virtual hooking

A node, which hasn't any physical neighbours, resides in a black zone and, for this reason, it can't hook to the physical layer. If it has access to another network, i.e. the Internet, it will hook directly to a vnode, joining the virtual layer. Let this hooking node be H.

Searching for the nearest vrnode

The first part of the Virtual Hooking is the creation of virtual links (ip tunnels) to the first vrnode it founds.

H chooses, at first, a random vnode which can be located anywhere in the globe. If it is its first hook to the virtual layer, it will get the IP of the vnode from a small public list available on the Internet, otherwise it will consult its saved virtual maps. Each IP on the public list and in the virtual maps is associated to its own geographic coordinates. H will choose the nearest vnode to itself. Let the chosen vnode be V.

H sends to V a packet containing its coordinates and a random ID. V consults its external map and forwards the received packet to the gnode G, which is the nearest to H. The packet will be forwarded until it gets to I, the nearest node to H, which belongs to the gnode G. At this point, I sends an ACK packet to H and includes in it the ID. In this way it certifies that it has truly received the original packet, sent by H.

I is the first vrnode of H.

Linking to other vrnodes

Since only one vrnode per vnode is not sufficient to balance the network, H will link to other `vlinks_max' vnodes. These vnodes are the nearest to H. `vlinks_max' is a value proportional to the bandwidth of H.

The node I appends its Internet IP to the received packet and forwards it again to a node T, so that d(H,T) ~= d(H,I). The node T will do the same (adds its IP and forwards the pkt). When the packet will be forwarded for the `vlinks_max'-th time or when it can't be forwarded anymore, it is sent back to the node H.

The node H collects this last packet and creates a virtual link (tunnel) to each Internet IP which has been stored in the packet itself. These linked nodes are the new vrnodes of the node H.

Reordering the virtual layer

At this point the node H will hook to each linked node. This procedure is called vlinking:

Let L be the generic vrnode of H.

It is possible that some vrnodes of L are nearer to H, in this case they should be linked to H instead of L. For example: 

1. Initial configuration

        Tokyo                      London
          |                          |
          |______ Internet tunnel ___|

2. Rome vhooks to London.

        Tokyo -------- London ----- Rome

3. Since Rome is nearer to Tokyo than London, the links are reordered in their
   final configuration:
        
        Tokyo -------- Rome -------- London

The reordering of the links works in this way:

H sends the I_AM_VHOOKING request to L.

L analyses its virtual rnodes and compares d(L,vR) to d(H,vR), where vR is a vrnode. If d(H,vR) < d(L,vR), L adds the Internet IP of vR in the reply packet.

H receives the reply packet of L and tries to create a virtual link to each vR listed in the same packet. H writes the list of all the vR nodes which has been successfully linked to H itself. This list is sent back to L.

L reads this latter list and deletes all its links to the vR nodes, which has been successfully linked to H.

This same procedure is repeated for each vrnode of H.

In the end, H chooses one of its vrnodes and hooks with the classical method to it.

Gate hooking

When a gate node is linked physically to another gate node, they use the v-linking procedure to reorder their links.

Virtual topology

The node H will remain virtually linked to a generic node L if and only if there isn't a physical route which connects H to L.

When H notices (analysing the QSPN pkts) that L can be reached through a physical route, it deletes the virtual link.

Load balancing

All the nodes, which have an Internet connection, should be gate nodes. In this way, the traffic passing on the virtual layer will be well balanced. For example, two separated physical gnodes will be linked with the maximum number of virtual links. 

                   virtual links
                   ___ ... ____
                  /___ ... ____\
                 /____ ... _____\
                /                \
        Gnode A ------ ... ------- Gnode B
                \_____ ... ______/
                 \____ ... _____/
                  \___ ... ____/
                   virtual links

`vlinks_max' is the maximum number of vrnodes which H can have and it is a value proportional to the bandwidth of H itself.

`vlinks_min' is the minimum number of vrnodes and is always proportional to the bandwidth.

When the number of vrnodes becomes greater than `vlinks_max', H drops its farest vrnodes, keeping all the others.

Instead, if the number becomes smaller than `vlinks_min', H vhooks again in the virtual layer using the same procedure described before.

The end of Viphilama

When all the nodes will be linked with physical links, Viphilama will automatically cease to operate. In fact, there will be always a physical route which connects any other node and therefore all the virtual links will be deleted.

Feel free to help the development of Viphilama.

Related: ["Netsukuku_RFC"]