[Goat] routing

[Benoit Grégoire]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sunday 25 April 2004 07:23 pm, William Waites wrote:
> 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.

Agreed, I previously meant "serving as a gateway to a wired subnet".  Now if, 
like you illustrated, we want mesh traffic to travel through the wired 
network, and since in you diagram B cannot reach D directly, we have a few 
solutions:

1- Run the same routing protocol on nodes B, C and D as the rest of the mesh.  
Note that that does not imply that it's the only routing protocol that is run 
on those three nodes, only that the protocols do not talk to each other.  
"Node" C  only hears two other nodes (B and D), but with very high speed and 
reliability.
2- We don't want to bother with the problem, and simply add a VPN (or PPPoE, 
or whatever) between B and D, making the two of them broadcast reachable.  
3- We make the wired and wireless protocols talk to each other.

> 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.

Indeed, I don't see much benefit in cross connecting the protocols.

> 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.

Say we are in case 1 or 2 above and the routing protocol for the wireless part 
is RoofNet (and for node C as well in case 1).  Roofnet's metric can be 
summarised as the mant time for sucessfully transmiting a packet.   
If indeed there is radio loss on the A-F-E, it will take longer, on average, 
to successfully tranmit a packet than on A-B-C-D-E.  In fact even in the 
ideal case (no loss anywhere) A-B-C-D-E, will always be twice as fast, since 
node F is half duplex, and the B-C-D group is effectively full duplex, since 
D can transmit while B receives.

> 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.

Off course.

> 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.

Well, the case I was discussing is if someone were to connect an existing LAN 
to the MESH.  The wireless protocol would be wastefull inside the LAN, as 
there is no compeling reason to measure link bandwith and packet delivery 
rate, as that's usually a constant.  If there is only one gateway to the 
MESH, there is no reason why the protocol on the wired lan has to be the same 
one as the mesh.  Furthermore you may want to do trafic engineering or 
manipulate static metrics on the wired lan, something you cannot do with 
wireless routing protocols.

Now for small lan, it will be much simpler to simply run the wireless routing 
protocol everywhere and be done with it.

> > >    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.

In theory I would agree with you.  In practice, many of these nodes may be run 
by individuals or OSBLs that have no technocal knowledge of the way the 
network works. 

> > - -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.

In the trivial case, I'll grant you that.
 
> > - -Automatic routing around dead nodes.
>
> all routing protocols do this.

Ok, perhaps I worded that badly.  Radio links can have a whole range of 
intermitent falures and packet loss.  It was my understanding that OSPF and 
similar routing protocols can take up to several minutes to detect link state 
change.  Long enough for a TCP connection to be broken if it has to be 
re-routed.  Perhaps I am wrong.  I am sadly not an expert in routing 
protocols, especially traditional ones.   

> > - -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.

I disagree, they simply assume that neighbour routers can be discovered by 
broadcasting on every interface that they have to manage, which isn't the 
same thing.  

Some protocols have explicit support for wired links (which always get chosen 
over wireless ones), but that is only relevent if you are unable to 
dynamically measure the performance of your links, or if the main purpose of 
your mesh is to get out of the mesh at the nearest wired router to the 
internet.

> > - -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.

One of the premise for my analysis of each protocol is that manual 
configuration at each nodes and contacting each neighbour nodes to get on the 
network are not reasonnable requirements for the sociological and economic 
model of the mesh to work.

If that premise is no longuer valid, most of my complaints about OSPF are no 
longer valid. 

> > 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

True, but I don't see how changing this assumption would change their 
conclusions.

> 	- assumes an ad-hoc network such that maximum
> 	  possible throughput varies inversely with
> 	  hopcount (!!)

Sadly ad-hoc network is unavoidable.  I supose we could write a custom daemon 
to use WDS, but if memory serves you are limited to six links and the 
transmission is still half duplex.

As for bandwidth loss with hopcount, fortunately you stops decreasing after a 
large number of nodes, so you always have at least 25% available.
 
> 	- 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.

In theory it is (in fact this is what the routing protocol used bu HAM packet 
radio does).  Unfortunately, to allow communication with a station that 
cannot acknowledge successfull transmission on the same radio link would 
requires low level access to the cards, which we usually don't have.  Even 
with HostAP I'm not sure if we have sufficient control over the hardware.

- -- 
Benoit Grégoire, http://step.polymtl.ca/~bock/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFAjG+AmZ6zzPlLuwMRAmjVAKCY9pOv0xPciWnmdvPnErkGH6ogqACfWHFc
NYv6IPqoj5os7FvUA1tR2uU=
=9kuA
-----END PGP SIGNATURE-----

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