14. September 2003

[ English ]

Routing in Mesh Networks

The people at the freifunk.net summer convention had a very beautiful idea to explain how routing works in a Mesh Network: They had handed out cards which could be used for sending messages to another person. The design was very simple:

To (required)
From (optional)
Date (optional)
Message (optional, but it makes sense to write one)
The instructions, also printed on the cards, were as follows:
1) If the message is for you, read it. Stop.
2) If you know the person that the message is for, give this person the card.
3) If you don't know the person, pass the card to someone else.

Thank you, [Ja, Namen... wenn er mir Montag die versprochene Email schreibt, trage ich den nach. Tut mir leid.], for explaining this to me.

I wonder how a messaging system like this would work in real life, in a larger environment than a conference. There must be a formula that explains how the average routing time grows with the number of participants in the mesh... can somebody work that out or find it somewhere on the Internet?

[30.11.2003] A more detailed explanation of how this works can be found in informal.org's Wiki.

 

Hi Martin,
Yes, there is mathematical stuff that supports this. In fact came across it just a week or so ago. But where? I'll have to think.......

I found it where it related to how much meshing is needed in a network for it to be highly invulnerable to nodes/people failing/withdrawing. Meshness increases stability as compared e.g. a ring-formed net or starformed one, but is far less costly than a situation where all nodes are connected to all others. There is an optimum there somewhere, and it can be caculated. Should be more or less the same calculation for figuring out your question (i.e. how to create an ad-hoc network in a sea of independent or minimally clustered nodes.)

Ton Zijlstra am 16.09.03 19:29 #
 

hi martin,

actually the To field was optional, though the From and Date were required.

We wanted to make the messgae part RFC 2822 compliant (like an email) and in that protocol only the return address is required. It seemed counter intuitive at the time, but as a sender it is true that you are never sure if the destination address is correct only that your origination one is.

Does work better with a to field though ;-)

julian priest am 18.09.03 00:51 #
 

Hi Julian! Thanks fo the correction! Makes it even more fascinating for me... :-)

Martin Röll am 18.09.03 00:57 #
 

The kind of networks you are talking about are so-called scale-free networks. Barabasi did some important work on this topic.

As far as I know, relations between people on this planet can also be descibed as such a network. A quite surprising fact is that any two people on this planet are "connected" via 5 or 6 other people at most!

So if everyone would have a device that could keep him connected to all the people he knows, any message would receive its destination within 5 or 6 transfers. THAT would be quite fast routing, wouldn't it?

Markus Tiersch am 10.06.04 14:08 #
 

Yes, there is a 'formula' for the routing mechanism in a real world experiment. It's called the Small World Phenomenon and I think Wikipedia has a nice article about it.

http://en.wikipedia.org/wiki/Small-world_phenomenon

Lota am 05.08.05 23:50 #