Differences between revisions 1 and 2
Revision 1 as of 2005-10-16 22:14:45
Size: 2807
Editor: alpt
Comment:
Revision 2 as of 2005-10-16 22:21:25
Size: 2861
Editor: alpt
Comment:
Deletions are marked like this. Additions are marked like this.
Line 55: Line 55:
Note that levels is equal to log_2(N)/MAXGROUPNODE_BITS, where N is the Note that "levels" is equal to log_2(N)/MAXGROUPNODE_BITS, where N is the
Line 79: Line 79:
Maximum size of a tracer_pkt

/* TODO */

--

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

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

  • total_packets_per_flood = Sum( number_of_links_of_each_node - 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.

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-1)

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-1)

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 = 768; total_packets = 196608;

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)

--

All the nodes are bnode...

--

All the nodes are in one line...

--

Maximum size of a tracer_pkt

--

Simple and not accurate reasons for the scalability of Netsukuku (until there is the math/technical documentation that is being written): 1) the size of the maps is fixed: about 4Kb for the int_map and 16Kb for the ext_map. 2) Not all the nodes sends a broadcast discovery. 3) There are few floods for each discovery 4) When a node receives a flood it already has the routes without calculating anything. 5) A flood is syncronized: the same flood starts at the same time for all the nodes.

Netsukuku_scalability (last edited 2009-09-18 11:18:26 by alpt)