Routing algorithm research

Unanswered Question
Dec 27th, 2007

Sir, I am a PhD student at the University of Oklahoma and am working on solving the Snake-in-the-Box problem for multidimensional hypercubes. Several papers I have read report that good solutions to this problem can be used in the development of network routing algorithms. However, I can find no further information on this topic. I would like to know if anyone at Cisco can enlighten me on this, or perhaps point me to a paper that explains the connection between these two. Thank you for your help.

I have this problem too.
0 votes
  • 1
  • 2
  • 3
  • 4
  • 5
Overall Rating: 5 (2 ratings)
marikakis Fri, 12/28/2007 - 02:32


What do "network routing algorithms" mean to you and to the authors of the several papers you have read?

The answer might be obvious to most networking professionals in this forum, and people here by this phrase usually mean a protocol like OSPF, BGP and the like (I will not attempt to supply a definition).

However, some hardware research people have the (annoying I must say :-) habit of naming other kinds of methods as network routing algorithms. Those hardware people usually name like this methods that decide how to establish a hardware/wire path along two endpoints by turning transistors on and off in a Network On a Chip or something like that, which, in this forum's terminology, would be considered methods that involve more the "switching" rather than the "routing" part (this could be a pretty religious discussion).

The magic phrase "multidimensional hypercube" rings a hardware bell to me (plus my opinion that one would not expect with hypercubes and stuff like that to have some luck against OSPF, BGP, and friends in the near future).

Anyway, I return to my first question. Before proceeding with your work, I believe you should clarify what "network routing algorithms" mean in the context of the papers that you have read. In many cases understanding what someone says is just a matter of definitions.

Kind Regards,


carlsonbenjaminp Fri, 12/28/2007 - 08:45

You are quite correct. Upon further reading I find that most of the papers I have read seem to be referring to finding the best path/route in a hardware sense. As a matter of fact, most (but not all) seem to involve conntecting nodes in a parallel processing network, not a traditional multiuser/multicomputer IP type network. However, if anyone has any information about how hypercubes are used in designing traditional IP routing algorithms, I would be very interested in hearing about this. I suspect that they are not used in this manner.


marikakis Fri, 12/28/2007 - 14:40


Yes, this is my impression as well, that parallel processing networks is the primary target market for hypercubes and stuff like that. It is a matter of scaling the number of nodes in what is considered the "network" and the physical distance between between the nodes participating in the "network". The Internet is huge. It has many nodes geographically dispersed and belonging to different administative domains. The interconection in parallel processing systems serves in many cases a lot of nodes that are in close proximity and can make use of fancy networks inside a single chip, while chips continue to grow in capacity and can have inside them lots of transistors.

It is also a matter of trust. You cannot expect the whole Internet to cooperate in order to setup an end-to-end path, let it be setup via hardware or software. In the Internet every router does its best according to its administator's desires and policies. In a parallel multiprocessor network nodes in many cases trust each other, are best friends and party together.

So, in my opinion, you do not have many chances of beating down BGP. Same thing I believe for OSPF or IS-IS, not only because those interior gateway protocols serve well a variety of close and long distances between nodes, but also because the network arena has some inertia in this kind of stuff. It takes some time to get the ball rolling, but once you get it, it is hard to stop it. Which routing protocol dominates depends on many factors besides how smart, correct and scalable it is. It also depends on the how many stable implementations you have, how many internets already use it, how good related documentation is and how familiar are networking professionals with it. The networking community seems to prefer at this point to continue using traditional routing protocols even in the transition towards IPv6. So, in years to come it is quite difficult to convince people of anything else. "If it works, do not touch it!" many networkers say :-)

I do not mean to stand in your way of developing something really innovative and useful. I am only telling you what I would tell even to myself. I would put my money on your work in the context of multiprocessor networks, since it is a developing market with some space for researchers, and I have a few suggestions for reading during the holidays :-)

1. Network Algorithmics by George Varghese from Elsevier/Morgan Kaufmann publishers

2. Interconnections (2nd edition) by Radia Perlman from Addison-Wesley

3. Interconnection Networks by Duato, Yalamanchili, Ni from Morgan Kaufmann publishers

All those authors do know what they are talking about, some of them are quite amusing (especially Radia Perlman) and I believe you will gain an understanding in a variety of fields, what people in different disciplines think, and perhaps ideas will come to you on what you can do more, once you understand the current status of things. Varghese will also give you an idea about the balance between what is innovative and what is practical in today's internet, which is probably the essence of engineering.

If there is anything else you would like to discuss, I would be more than glad to hear it (since my master's work is at a dead end, I hope I can do something useful somewhere else :-)

Kind Regards,


Paolo Bevilacqua Fri, 12/28/2007 - 16:17

I liked marikakis posts that for once, go beyond the strict practicality of these forums.

He reminds us that behind any kind of efficient network (hardware, software, or a combination), there is a lot of study, common sense, and human factors as well.

My rating, a '5', and Season Greetings!

carlsonbenjaminp Mon, 12/31/2007 - 07:05

Thanks for your extensive feedback. Your information and insight have helped a lot. While I already have too much holiday reading, I will look into these books (I may already have at least one in my library). Merry Christmas!


This Discussion