QSPN scalability

The QSPN is an optimised way of "sending a tracer_pkt from each extreme node". A tracer_pkt is just a flood, and the total number of floods is given by:

• total_floods = extreme_nodes + 1

where the extreme_nodes are:

• extreme_nodes = number_of_nodes_with_only_one_link + number_of_cycles*2

A cycle here is meant as a set of nodes, where each node is linked at least at two other nodes of the set.

The total different packets generated by a single flood is equal to:

• total_packets_per_flood = Sum( number_of_links_of_each_node - 1 ) + 1

Since the network is organized in gnodes, the total_floods for all the levels will be the sum of the total_floods of each level. The same applies to the total_packets_per_flood.

Now we'll consider various worst scenarios.

First scenario

The first worst case is a network where all the nodes are an extreme_node, i.e. there's one node X and all the other are linked to it by just one link.

                            O       Y
                             \     / 
                              \   /
                         N ---- X ----L
                                |
                                |
                                M       (A graph describing the first worst
                                         scenario)

In this case all the nodes, including X, will send a tracer_pkt. This means that if all the nodes in the level 0 are linked in that way, and all the gnodes of the higher levels are also linked between them in the same way, then the total floods, in all the levels, we'll be:

• total_floods = MAXGROUPNODE * levels

Where MAXGROUPNODE is the number of (g)node present in a gnode. By the way, this configuration has its advantages because there is only one hop between each node, therefore each flood will end after one hop and the total packets will be:

• total_packets = MAXGROUPNODE^2 * levels

MAXGROUPNODE is equal to 256. In the ipv4 we have 4 levels. This means that in a network composed by 2^32 nodes, in the first worst scenario to run the QSPN at all the levels will have:

• total_floods = 1024; total_packets = 262144;

Note that "levels" is equal to log_2(N)/MAXGROUPNODE_BITS, where N is the maximum number of nodes in the network and MAXGROUPNODE_BITS is equal to 8. MAXGROUPNODE is also equal to 2^MAXGROUPNODE_BITS. The final formulas that describes the growth of the number of floods and packets are:

• total_floods = 2^5 * log_2(N) total_packets = 2^13 * log_2(N)

Second scenario

In this case we consider a network where each (g)node is linked to all the other (g)nodes.

                           C
                          /|\
                         / | \  
                        A-----D
                         \ | /
                          \|/
                           E

That means that we have 1 cycle and 0 nodes_with_only_one_link, so the total_floods are:

• total_floods = 2

Since every (g)node is linked with every other (g)gnodes, the number of links for each of them is MAXGROUPNODE and the number of total different packets generated per flood is:

• total_packets = ( ( MAXGROUPNODE - 1 ) * MAXGROUPNODE + 1)

Supposing that this configuration is the same for the upper levels too, we have:

• total_floods = 2 * levels total_packets = total_floods * ( ( MAXGROUPNODE - 1 ) * MAXGROUPNODE + 1) N = total_number_of_nodes_in_the_network levels = log_2(N)/MAXGROUPNODE_BITS total_packets = (log_2(N)/4) * ( ( MAXGROUPNODE - 1 ) * MAXGROUPNODE + 1)

In ipv4, with 2^32 nodes:

• total_packets = 522248

Third scenario

All the (g)nodes are in just one line: to reach the end node B from the start node A we have traverse N nodes, with N equal to the total number of nodes minus 2.

In this awful case a flood will have to traverse N hops, this means that if the average rtt between two nodes is 70ms, then the flood, if started from an extreme node will take about 9 years to reach the other end.

About the maximum size of a tracer_pkt

Each time a tracer_pkt traverse a node it grows of one byte, since the tracer_pkt is always restricted to a determinate level, which has maximum MAXGROUPNODE nodes, the maximum size of a plain tracer_pkt is 256 Bytes (we are not counting the headers, which are a constant size).

The things change if the tracer_pkt traverses border nodes, in fact, (7 + 10*L) bytes are added in the the tracer_pkt each time it passes trough a bnode. L is the number of gnodes the border node is linked to.

About the maximum size of the maps

The size of levels in the maps is fixed 'cause we already know the maximum number of nodes in the network. We are also considering that we store only the 20 best routes for each node.

So the maximum size of the maps, when we have all the routes stored, and the bnode with all their maximum links filled is: