Missing an Eulerian trail problem on my first-grade math olympiads was a shock. Ever since, I had a great deal of personal interest in this mystical path finding algorithm. The obsession grew out of hand, and I was once led to think that there was some linkage between the number of possible eulerian trail with n nodes and the nth prime number. Well, I never found any linkage, but maybe…someone else could.
Today, I am here to talk about potential use of Eulerian trail to reduce flooding in a network. The notion is very simple.
Please look at the triangle above. By the way, I got this picture from www.shmoop.com ( Let me know if I am violating any copyrights)
This of this triangle as a computer network where each node becomes a router. This network is running a sort of SPF, which would typically require flooding in the network. Each node will flood to make an update to the topology and the network suffers from the massive flooding. So the problem is evident. Flooding degrades the network performance.
Now, what if one packet from an arbitrary router travels the entire network collecting link states? The link state of a node will be added in a form of header and passed on to the next node. If this packet travels in an Eulerian trail over this network, it would not only cover the whole network, but travel in the most efficient way by travelling each link only once.
For example, a packet starting from Router B will pass through the network in the following order;
Instead of having every node flooding to each other, one packet from an arbitrary router will be able to collect all necessary information by travelling the network in an Eulerian trail.
If we are develop this algorithm further, there are some areas that must be addressed;
1.Not all network can have an Eulerian trail.
2.An algorithm is required to make a packet travel in an Eulerian trail.
Flooding becomes a problem as a data center gets massive. In order to build a massivly scalable data center, problems such as flooding must be controlled.
I am not here to give a rigorous mathematical proof on Eulerian trail, but would like to explore the possibility of applying this notion in reducing flooding in a network.
I will be working on this, but I would also like to have some more people on board to research on this together.
Please leave some comments or write me an email at firstname.lastname@example.org.