This is the second semester I am participating in URSP. You
can find my previous blog post (https://studentsasscholarsgmu.blogspot.nl/2016/05/ursp-student-highlights-anatoliy.html)
where I described what my project is about. Here I would like to briefly
describe some basic ideas behind the networking algorithm.
We can start by asserting that a mesh network might consist
of thousands of nodes. In many routing protocols every node learns about all
the other nodes; this way one immediately knows how to send packets to a given
node. In many other approaches, a node learns a path to a given node on demand,
when it needs to, by often flooding the network in a search of the node. When
scalability is required, neither option works well.
One idea that occurred to me is to deal with smaller
networks. How can one do it without reducing the number of nodes, you might
ask. Let’s assign each node one of two colors, white and black, randomly and
fairly. Now, let’s create one network out of all the white nodes and one
network out of all the black nodes. Each graph will approximately have twice as
fewer nodes. Pretty good, huh? Any two white (or black) nodes can communicate
by operating on a twice smaller graph. And if a white node wants to send data
to a black node, it sends data to a nearby black node which in turn forwards it
to the destination. Actually, this idea can extended by subdividing the two
graphs each onto two smaller ones. Let’s say, each white node becomes either
white or light-gray, randomly; and each black node becomes black or dark-gray.
Each of these 4 graphs can be divided and so on. We do this until each has a
reasonably small number of nodes, so each node can learn about all the others.
Now routing is just a matter of sending packets to the nodes of right color.
For instance, white → light gray → light light gray → destination, or in terms
of binary numbers, 0??? → 01?? → 010? → 0100.
0100 in this example is an address of a node, generated randomly at the
set up time, and 01?? is any node that starts with 01.
It turns out, this is exactly how routing in Kademlia DHT
works, although for a purpose of working over the Internet where a method of
addressing (IP) is given. You can say I reinvented Kademlia DHT. :) In the world of mesh network, you do not have
IP addressing, so that problem is a bit trickier. For example, we need to
ensure that the white graph is actually a connected graph, given that the
initial graph is connected. I have described one way how this can be achieved
in a draft paper here: https://github.com/aszinovyev/bmlrp/releases/download/2016-04-18/bmlrp.pdf
. Right now I am thinking about using a
different way for doing this and eventually finishing the simulation code with
moving nodes. Again, all the code will be released under FOSS licenses.
