Friday, October 21, 2016

URSP Student Anatoliy Zinovyev Develops a New Routing Protocol for Mesh Networks

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.