Mobile mesh - another approach (binary included) (fwd)

Tue Apr 23 00:34:38 EST 2002

wow, folks, check this out.

At this point, he's not released source, only the binary, but
we'll see.  I hope he chooses the path of the OSS side.  :)

I'm a little bit worried about the memory requirements he talks about, but
I don't think we'll have that many 'local' neighbours.

Anyway, I'd like to setup a workshop for anyone who wants to play with
this mobile mesh (and maybe others).   Anyone else interested?

-Eric

---------- Forwarded message ----------
Date: Mon, 22 Apr 2002 13:32:29 +0100
From: Jon Anderson <jon at LOCUST.CO.UK>
To: MOBILEMESH-LIST at lists.mitre.org
Cc: geoff at communitywireless.org
Subject: Mobile mesh - another approach (binary included)

Dear Mobile Mesh fans,

I have been looking at mobile mesh and discussing the various
scalability issues here. I was thinking about this and I wondered if
there was a solution which takes advantage of the data set - (eg how
mobile networks could work)

I think I've found a solution, there may be some reason why this doesn't
work. I thought I would ask for some input.

My method has the following advantages:

1) The entire routing table for the whole network is maintained in
memory, for 1 class A network (eg 16 million addresses) this takes only
32 mb of ram and for say 4 class A networks, this takes 133mb of memory.
2) IP addresses are allocated in a dense fashion (all class C's fully
populated) but individual IP addresses can be routed anywhere on the
network.
3) Routing information is passed in requested class B segments, each of
these address request blocks takes no more than 65536 bytes and so fits
into a single UDP broadcast.
4) Incredibly fast lookup and route merging functions - database is self
indexed using tree structures
5) Statically linked binary weighs in at only 28kb - currently running
on the USR-2450 embedded access point!

My method has the following disadvantages:

1) Routing is only known to the next hop
2) Routing paths can only be a max of 250 hops long - (use of wormhole
fixed broadband points bridge this gap)
3) Router can only have 250 routable *local* neighbours
4) maybe more?

How it works:

1) All nodes advertise using "HELLO" packets to their neighbours
2) Nodes request class B networks they might want to route to, or query
random ones similar to addresses already seen. Units with not much ram
could request on demand. (sending of ASK type hello packets)
3) Advertised route bundles are sent to the broadcast, each neighbour
can hear these
4) Routing bundles are merged with the current routing table (If
new-metric < old-metric then route = new-route)
5) Local routing decisions know which local neighbour is best route for
each address.

Current release:

I currently have a statically linked binary only release designed for
i386 based Linux. This is suitable for any Linux box or the Open
Access-Point. I plan to release the whole thing (source etc) publicly,
but I want to make sure it is all 100% first.

Getting the binary:

http://theophany.co.uk/hj-mm-01.tgz

Testing the binary:

Set up a number of machines with network connections (wireless ad-hoc
etc) - In my setup, I had 3 wireless units and 1 on a fixed ethernet.
Due to a fact of how the access point worked (clients were in managed
mode) some could see 3 neighbours, some only 1. The routes passed
correctly between all the hosts on the network.

This binary is only configured to work with the 10.20.x.x subnet - it
wont handle addresses outside this range yet.

To launch the binary, configure your wlan interface to have an ip
address in this range, then start the system like this:

./hj-mm 10.20.your.local.ip 10028 255.255.255.255 10029

The first param is the address to send from, eventually, this can be
0.0.0.0, but for now, set it to the IP address of the wlan interface.
The second is the sending port number, this just needs to be different
to the receiver. The third param is the address to send broadcasts to.
Leave this at 255.255.255.255, the last param is the destination port.
You can probably change this, but they all need to be set the same. If
you follow my example, then the system will function correctly.

Note that this doesn't actually alter routes or handle any routing yet,
it will just show you everything it is doing, and its idea of what the
routes would be. The system has no "teeth" in place yet.

Example output:

(a host seeing 3 neighbours)

---> Report:  (neighbours: 3) (memused: 7316)

Received packet From: (10.20.1.19) - len: (10)
Known Router at: 1 / 1301140a / 1301140a
Standard Hello packet
Received packet From: (10.20.1.1) - len: (10)
Known Router at: 2 / 101140a / 101140a
Packet valid 601140a/101140a- ASKING:10.20
Segment build scan : pointer depth 0 (10) -  at 809b800
Segment build scan : pointer depth 1 (20) -  at 809d000
Pointer for classb: (10.20.x.x) (809d000)
10.20.1.x known
Writing 2 26 at xmit pos 40
 10.20.1.1 known (route: 254 - metric: 0)
 10.20.1.6 known (route: 1 - metric: 1)
 10.20.1.19 known (route: 254 - metric: 0)
Output pointers now at: 550 - Total/end: 806
Received packet From: (10.20.1.6) - len: (778)

---> Report:  (neighbours: 3) (memused: 7316)

Received packet From: (10.20.1.19) - len: (778)
Known Router at: 1 / 1301140a / 1301140a
RECEIVED ROUTING BUNDLE: from 1301140a (Known as: 1) about 10.20.x.x
Decoded: 10.20.1.x @ pos:512
Decoded: 10.20.1.1 (metric: 1)
Route not trumped: kept: (route: 254 metric: 0) offered (route: 1
metric: 1)
Decoded: 10.20.1.6 (metric: 1)
Route: unchanged (route: 1 metric: 1)
Decoded: 10.20.1.19 (metric: 2)
Route not trumped: kept: (route: 254 metric: 0) offered (route: 1
metric: 2)
Received packet From: (192.100.100.55) - len: (10)
Known Router at: 3 / 376464c0 / 376464c0
Standard Hello packet

Comments welcomed!

Best Regards,

Jon Anderson
http://Locust.net

--------------020509010003060206060708--

To unsubscribe: send mail to majordomo at wireless.org.au
with "unsubscribe melbwireless" in the body of the message