[Goat] routing

[William Waites]

On Sun, Apr 25, 2004 at 02:59:06PM -0400, Benoit Grégoire wrote:

> >       ii. support for what would be called "areas" with
> >          ospf is very limited.
> 
> I don't see that as a problem, none of the protocols we 
> are considering need  to build a complete map of the network.   
> And you still need only one node capable of mesh routing to
> serve a wired subnet.

what about the scenario where you have


      \|/  ...  \|/             \|/  ...  \|/
       |         |               |         |
     +---+     +---+   +---+   +---+     +---+
     | A |     | B |---| C |---| D |     | E |
     +---+     +---+   +---+   +---+     +---+

the "serving a wired subnet" is ambiguous in this case.

for A to reach E, each of the routers has to participate
in some sort of routing protocol. if the protocol on the
wireless network is different from that on the wired network
(C), then B and D have to be able to do cross-redistribution,
which is tricky and likely to be unstable. if it is the
same then we don't want LSAs to flood through the whole
thing.

as well, suppose there is another node, F that makes
a wireless-only path A-F-E. in this case we still would
probably want to prefer the above path with the wired
part since it is likely to have less loss. of course
a DV or dijkstra (OSPF) algorithm wouldn't be appropriate
in this scenario either.


> >       iii. support for interaction in a predictable way
> >          with other protocols (i.e. rip, ospf, bgp) is
> >          limited -- i.e. there is no support for these
> >          in zebra/quagga or gated.
> 
> Well, that would be an interestion projet to get them
> to work together.  But  in any case the interaction 
> isn't very complicated.  Whatever protocol is 
> chosen would need to answer queries to adresses
> advertised (or implied by) the RIP, OSPF or BGP, for
> which it is a gateway.  All the other protocol need 
> to know is the existence of the gateway, capable of
> reaching the entire  adress space chosen for the mesh. 

see above. The interaction is subtler than that, but
perhaps we have different hypothetical architectures
in mind. i don't see the problem with inserting wired
(or tunneled) nodes between wireless nodes. indeed
this will be desireable in many cases. 

there would be no explicit boundary on which to do
the type of aggregation that you describe, and
redistribution of routes then has to be done sanely.

> >    b. what do these specialized routing protocols
> >       give us that say, ospf with equal-cost or
> >       weighted-cost multipath routing does not?
> 
> - -No need to contact anyone to get on the network 
>   (except for reserving IP space)

it does not seem unreasonable to require contacting
adjacent nodes in order to connect to the network.

> - -No centralised network management.

this is not required with ospf or bgp either -- all
that is required is for you to get your neighbours
to talk to you.

> - -Automatic routing around dead nodes.

all routing protocols do this.

> - -Does not assume that connection is bidirectionnal.

this one's trickier. i have to learn more about how
AODV and OLSR and RoofNet deal with this. the paper
you reference below talks about it a bit, but there
are a couple of problems that i see with their model.

the main drawback that i see with ospf as well as
distance vector algorithms is the "shortest path is
not always best" problem. but on the other hand the
other protocols assume a homogeneous wireless network
which is not a reasonable assumption.

> - -Does not need to maintain a routing table covering
>   the whole network.

this seems to be a more specific issue relating to
actual deployment rather than an argument against,
say, ospf. holding complete routes for the network
is not likely to be too big of a problem -- especially
if separated into areas and doing aggregation on
the boundaries. this would also circumscribe link
state which is potentially the bigger problem.

while requiring a bit of manual configuration, it
is not at all unreasonable even to use BGP... it
has a few advantages:

	- works over a tcp transport so links with
	  bad asymmetric paket loss are not likely
	  to be used (since the peering sessions 
	  won't work).
	- it is not a distance vector algorighm so
	  hop-count can be overridden easily.
	- it is not hard to modify to use extended
	  route attributes to carry things like the
	  ETX, for example.

this would be feasible for a fixed network where 
putting up a node means explicitly creating links
to adjacent nodes.

> This paper explain a lot of the isues and possible 
> solutions, I very much  encourage everyone to read it:  
>
> http://www.pdos.lcs.mit.edu/papers/grid:mobicom03/paper.pdf

interesting paper. three objections to their model:

	- assumes a homogeneously wireless network
	- assumes an ad-hoc network such that maximum
	  possible throughput varies inversely with
	  hopcount (!!)
	- the ETX as proposed assumes symmetric
	  routing even though it takes into account
	  forward and reverse loss. it is quite possible
	  to use one path for sending packets, and have
	  the received packets come back via a different
	  path with no adverse effects.
	  
> I'm happy finally someone else stepped up to challenge my
> vision of the  MESH ;)

:)

So let's start building and see where it goes!

-w
-- 
At Group L, Stoffel oversees six first-rate programmers, a managerial
challenge roughly comparable to herding cats.
		-- The Washington Post Magazine, June 9, 1985

_______________________________________________
Goat mailing list
Goat at isf.waglo.com
http://isf.waglo.com/mailman/listinfo/goat_isf.waglo.com