[consume-routing] New mobile mesh approach

[Jon Anderson]

>Firstly, I am familiar with your Locust service, my colleagues at work
have dealt with you very recently, I am happy to 
>see it is still going strong.

That's great! I do my best. :)


1) BSD 4.3 Reno has used a radix tree based routing table for over 10
years.
   How is this any different?

I've searched for radix tress on the net, is there a simple introduction
anywhere?


2) Tying the routing to IPv4 doesn't make much sense. We might well
   wish to run IPv6 soon. How will you address this?

I've heard a lot of great things about IPv6, but I don't understand it
yet. I looked at this and I couldn't find out how IPv6 can self
configure and handle routes throughout the network without some central
organisation. I looked for some stuff with IPv6, I couldn't find much
which I immediately understood.

I believe the original "mobile mesh" was created to fill this gap, where
hosts can pass round routing information. My method differs, in that all
routes to each IP are known to each IP. Eg, if you have 1,000,000 Ips,
you have a million routes, but these only take (approx) 2 bytes each to
store in ram and 1 byte during inter node transfer...

Nodes don't store routes to gateways etc, the network is peer-to-peer,
each node is a router to its local broadcast range.



3) How do you propose we integrate this with routing backbones built on
   existing routing protocols (e.g. IS-IS, OSPF) ?

At the moment, I'm not proposing anything like that. I'm not trying to
build an IP network which can bridge directly on to the existing
"internet" or to a LAN etc. I'm sure some people will want to reject the
idea based on this, but I don't think this will present a problem and
I'd prefer to deal with that once I have the "Anderson Mesh" actually up
and running and fully working.


4) How will you handle CIDR (Classless Inter-Domain Routing) and VLSM
   (Variable Length Subnet Masks) ?

Well, I don't know much about these protocols except what I've skimmed
from various references. The network topology I'm presenting has no
subnets or classes. Each IP is uniquely routed. It doesn't need to be an
IPv4 address, that is just a 32 bit address. I've presented this with
IPv4 examples because I already understand that and I'm utilising the
IPv4 networking protocols to get nodes to talk to each other.


5) Doesn't this memory hungry approach limit or rule out its use with
   embedded devices?

I'm thinking the opposite. On a "regular" network, you avoid complexity
at each node by having a centralised structure and known routes. If you
have no centralised structure, the only method I can think of is to hold
the entire routing table in memory. But, this routing table only needs
to know the next hop and routing information. I'm coding these as single
bytes.

Other than the table structure (which tends to zero as the network
scales up) only two bytes of ram are needed for each IP in the network.
My calculations show that it would take 32mb to hold an address range of
16 million fully populated, individually routed IP addresses. 

I know that current "embedded" devices might not have 32 mb of ram (the
USR2450 has about 4mb) but we'd only need 32mb of ram to handle every
household in the UK, which is a few years off I'm sure.


6) How long will it take for link state to propagate when nodes go down
   (considering each node maintains a *complete* routing table) ?

This depends on whether or not you're routing traffic to/from this node
and the refresh policies at each node, the number of neighbours to each
node in the chain to the new route etc. Its complex and I don't imagine
that it will become obvious until fully implemented.

>One agrees people always like to hear about new and exciting
developments, but these can often turn out merely to be old 
>ideas rediscovered. Many sharp minds around the globe have been
thinking about these very issues.

I'm very much aware of this, I don't expect to have magically come up
with a perfect solution. I am looking for a way to achieve peer to peer
routing without centralised configuration over an adhoc wireless
network. I haven't found any solutions which can scale easily. I'm
proposing another, it may not work, may not be scalable etc, but until I
can find out why *not* I'll continue to pursue it. So far, I have high
hopes. No-one has suggested to me where this will all fall over yet. But
then I'm not sure I've yet made it entirely clear what I'm proposing.

>If you can concretely define the routing protocol used, and provide a
precise and unambiguous specification of the routing >algorithm and
routing table data structures, then we can pin down whether or not this
is a novel and viable idea, or if
>it's been thought of before.

I will see what I can do on this. Diagrams required.

Best Regards,

Jon Anderson