Subject: [homenet] draft-boutier-homenet-source-specific-routing-00

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 03 Jul 2013 21:24:43 +0200

Dear group, dear chairs,

Matthieu Boutier and myself have just submitted

  http://www.ietf.org/id/draft-boutier-homenet-source-specific-routing-00.txt

which describes our experience with an extension to the Babel routing
protocol with support for source-specific routing.  The code that this
describes is available from

  http://git.wifi.pps.univ-paris-diderot.fr/?p=babels.git;a=shortlog;h=refs/heads/source-specific
  git clone -b source-specific git://git.wifi.pps.univ-paris-diderot.fr/babels.git

We have tried to give proper credit to the people who have done work
on the subject before us; however, due to the tight deadline, we may
have missed some previous work.  If you feel you have not been
properly cited, please shout loudly (by private mail), we will fix
that in the next draft.

Dear chairs, I would very much like to have a slot at the Berlin
meeting to say a few words about this work.  20 minutes should be
enough to give a fair idea and motivate people to read the draft.

Thanks for your attention,

-- Juliusz Chroboczek

---

From: Dave Taht <[email-masked]>
Date: Wed, 3 Jul 2013 12:55:02 -0700

> Thanks for your attention,

another case not quite touched upon in your rfc is the case where
there is an existing deployment of various ipv6 encapsulation
technologies.

6in4
6to4
6rd

can all co-exist with native ipv6, under this scheme, and networks
renumbered at leisure.

It's not clear to me that ula rules are well implemented on hosts at
this point in the host selection mechanisms, and there is some coding
going on in 6relayd that does stuff like prohibit distributing a
default route when there are no ipv6 addresses being distributed via
ra, which is probably covered by some rfc somewhere.

>
> -- Juliusz Chroboczek
> _______________________________________________
> homenet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/homenet

-- 
Dave Täht

Fixing bufferbloat with cerowrt: http://www.teklibre.com/cerowrt/subscribe.html

---

From: Lorenzo Colitti <[email-masked]>
Date: Thu, 4 Jul 2013 21:20:40 +0900

On Thu, Jul 4, 2013 at 4:24 AM, Juliusz Chroboczek <
[email-masked]> wrote:

> protocol with support for source-specific routing.

Er... did you read
http://tools.ietf.org/html/draft-troan-homenet-sadr-00 before
submitting this? With the exception of the text on babel, a lot of
the material you wrote is already covered there.

---

From: Baptiste Jonglez <[email-masked]>
Date: Thu, 4 Jul 2013 16:35:39 +0200

> the material you wrote is already covered there.

This document is listed as a reference: [TROAN].  However, it is not
directly used anywhere in the draft.

---

From: Lorenzo Colitti <[email-masked]>
Date: Thu, 4 Jul 2013 23:56:37 +0900

On Thu, Jul 4, 2013 at 11:35 PM, Baptiste Jonglez <
[email-masked]> wrote:

> This document is listed as a reference: [TROAN].
>

That doesn't answer the "did you read it" question :-)

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 04 Jul 2013 19:41:34 +0200

> Er... did you read
> http://tools.ietf.org/html/draft-troan-homenet-sadr-00
> before submitting this?

I have read it carefully.  I've even had the courtesy of citing it
(it's reference [TROAN]).

> With the exception of the text on babel, a lot of the material you
> wrote is already covered there.

Your draft covers what we describe in Sections 2.1.1 and part of 2.2.2.
That's roughly 15% of our text.

-- Juliusz

---

From: Lorenzo Colitti <[email-masked]>
Date: Fri, 5 Jul 2013 17:10:32 +0900

> That's roughly 15% of our text.

Why does [TROAN] not also cover 2.2.3? Is the conceptual forwarding
algorithm in [TROAN] incomplete?

As for "15% of our text", perhaps that's not the right metric? I mean, it
would certainly be possible to increase the length of [TROAN] by 6x by
adding irrelevant text, but I don't think that would be an improvement. :)

---

From: Tim Chown <[email-masked]>
Date: Fri, 5 Jul 2013 13:00:12 +0100

On 5 Jul 2013, at 09:10, Lorenzo Colitti <[email-masked]> wrote:

> On Fri, Jul 5, 2013 at 2:41 AM, Juliusz Chroboczek <[email-masked]> wrote:
> Why does [TROAN] not also cover 2.2.3? Is the conceptual forwarding algorithm in [TROAN] incomplete?
> 
> As for "15% of our text", perhaps that's not the right metric? I mean, it would certainly be possible to increase the length of [TROAN] by 6x by adding irrelevant text, but I don't think that would be an improvement. :)

I don't think another draft in this space hurts as such. It describes another example of using source routing. It seems pretty likely, and it is already in the arch text, that this capability is highly desirable to solve the exit selection problem.

Can you remind me - what method did Markus' source routing implementation that was successfully demonstrated at IETF85 use?

Tim

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 05 Jul 2013 14:49:29 +0200

> Why does [TROAN] not also cover 2.2.3? Is the conceptual forwarding algorithm

2.2.3 describes the "disambiguation routes" technique that we use in
order to coerce a hostile API (Linux' rule API) into having the right
behaviour.  There is no mention of disambiguation routes in your
draft, there is not even a mention of the fact that the existing
low-level APIs might have a different default behaviour and that a lot
of work needs to be done in order to get the lower layers to behave.

I was under the impression that you make no claim about being able to
implement the "conceptual forwarding algorithm" on existing operating
systems.  If that's not the case, I'd be curious to see your implemen-
tation.

-- Juliusz

---

From: Lorenzo Colitti <[email-masked]>
Date: Mon, 8 Jul 2013 16:58:01 +0900

On Fri, Jul 5, 2013 at 9:49 PM, Juliusz Chroboczek <
[email-masked]> wrote:

> behaviour.

Oh, I see. But then 2.2.3 just describes one possible way to implement the
algorithm proposed in [TROAN] on a system that is constrained by different
lower-level primitives, right?

In that case, might I suggest that you clarify the text so it clearly
separates the desired behaviour from its implementation, presents the
limitations of current OSes in this regard, and then presents your
disambiguation routes as a possible implementation of the desired behaviour
within the capabilities of current OSes.

Also in that case, I would suggest completely getting rid of the concept of
"ambiguity". The draft appears to define "ambiguity" as the case where
multiple entries match a given packet, but this is in no way specific to
source+destination routing, it happens in destination-based routing as well
(that's why we use longest-prefix matches). That said, since ambiguity can
obviously only exist where the rules are not clearly defined, if you
clearly separate the desired behaviour from the implementation, you might
end up finding that there is no need for this concept. In a sense, it seems
that the problem is not ambiguity, it's that current OSes don't implement
the rules that are needed to make source+destination routing work.

There is no mention of disambiguation routes in your
> of work needs to be done in order to get the lower layers to behave.

Well, but that's because they're not needed, right? [TROAN] doesn't mention
disambiguation because the conceptual forwarding algorithm that it presents
is not ambiguous, and so no need to resolve ambiguity.

> systems.  If that's not the case, I'd be curious to see your
> implementation.
>

Does the algorithm you propose implement the conceptual forwarding
algorithm in [TROAN], then? If so, then why not say so? That way we don't
have two drafts describing the same algorithm in different words.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 08 Jul 2013 16:04:22 +0200

Lorenzo,

In [1], you claim that your draft subsumes our work.  In [2], you
rather rudely question whether we've read your draft.  In [3], you
imply that our draft consists of just one page of content and that the
rest is unrelated filler.

Perhaps you could take the time to retract these claims before we
continue this discussion?

-- Juliusz

[1] <[email-masked]>
[2] <[email-masked]>
[3] <[email-masked]>

---

From: Lorenzo Colitti <[email-masked]>
Date: Tue, 9 Jul 2013 00:37:26 +0900

> continue this discussion?

I apologize if that is the way you read the messages. But I did not make
these claims.

I do think that there is substantial overlap between [TROAN] and your work.
I'm still trying to understand if the conceptual algorithm is fundamentally
the same, but it seems to me that it is. If that's true, then as a working
group, it makes more sense to build on [TROAN] rather to introduce a second
draft with a different formalization of what is in effect the same problem
and the same solution (apart from the part of the draft that documents
implementation experience, which is of course useful since it's
implementation experience). I maintain this opinion, and others may of
course disagree.

As for claiming that your draft is one page of content and unrelated
filler, I said nothing of the sort. You said [TROAN] covered roughly 15% of
your text, and I said that longer does not necessarily mean more useful.
The "6x" example was just that - an example. I thought you would agree with
me that if we increased the length of [TROAN] by 6x by adding irrelevant
text then it would not be an improvement. I didn't mean that 85% of your
draft is irrelevant.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 09 Jul 2013 04:40:37 +0200

> algorithm in [TROAN], then?

I've refrained from criticising your draft, since I appreciate people
taking the time to write legible, thought out drafts and thus sharing
their work with others.  However, I do not think that your "conceptual
forwarding algorithm" is a suitable basis for further work on
source-specific routing.  While I am glad to acknowledge that this
draft appears to be technically correct and was published before
I even started seriously thinking about source-specific routing,
I have no intention to base my work on what I believe is a flawed
formalism.

On the one hand, your "conceptual forwarding algorithm" is impossible
to implement directly on any operating system known to me.  On the
other hand, it's expressed in operational terms, with uselessly
complex data structures (two-level routing tables? eek!), which makes
it more difficult to understand than a purely abstract specification.

Look, given the right concepts, your "conceptual forwarding algorithm"
can be defined in one sentence:

  (d, s) pairs are ordered according to the lexicographic product of
  the longer-prefix orderings

This is a proper abstract formulation, and one that doesn't uselessly
introduce data structures where they don't belong.  This is what I've
attempted to do (without using order-theoretic language) at the
beginning of Section 2.2.2.

Not only is your formalism clumsy, but you don't even explain in prose
or justify the particular behaviour that you have chosen for
source-specific routing.  The reason for this particular behaviour was
explained to me by Fred Baker by private mail, and a summary of our
discussion appears in Section 2.2.2 (with proper credit given to
Fred).

Once again: I'm glad to cite your work, and I'm glad to recognise that
you were there first.  Please do not ask me, however, to reformulate
my work to fit a formalism that I happen to find deficient.

-- Juliusz

---

From: Erik Kline <[email-masked]>
Date: Tue, 9 Jul 2013 12:09:59 +0900

>   http://www.ietf.org/id/draft-boutier-homenet-source-specific-routing-00.txt

Juliusz,

A question and a few nits.

[ Section 1, paragraph 2 ]

I'm afraid I'm having a difficult time parsing the sentence, "First,
since a router only controls the next hop, a route can only be
selected by the network if it has a selected route as its suffix,
which makes some forms of global optimisation difficult or
impossible."

I think "suffix" is tripping me up somehow.  Can you clarify what that
means?  (possibly I just lack some essential context)

[ Section 2.2.2, last paragraph ]

"which in turn will send it back to B" --> "back to C", if I'm reading
things correctly.

[ Section 5, paragraph 2 ]

I do not think you mean to say that OSPF/IS-IS are both distance
vector and link state "within" areas.  I think you mean
s/within/(between|among)/ somewhere in there.

---

From: Lorenzo Colitti <[email-masked]>
Date: Tue, 9 Jul 2013 12:38:00 +0900

> I have no intention to base my work on what I believe is a flawed

Ok, so we agree that the forwarding algorithm is conceptually the same,
then. That's a start. The next step is putting that into one document. This
document *must not* be a babel-specific or linux-specific document, because
it needs to apply to more than just babel or linux (Which is why [TROAN]
says "conceptual forwarding algorithm" instead of "forwarding algorithm",
but that's not the point here.)

> it more difficult to understand than a purely abstract specification.

Since Ole wrote that text, I'll let him comment on it (when he comes back
from vacation). This is the IETF, so you're certainly free (within reason)
to trash him for writing something that you assert cannot be implemented,
but please do note that he does work for a company known to implement
things like this, and that he has, I believe, written implementations
himself, so I would advise you not to write him off without good reason,
because doing so might have the effect of lessening your credibility in the
eyes of the working group.

> beginning of Section 2.2.2.

Since we have now agreed that the two solutions are in fact the same, then
any formulation that achieves the consensus of the working group is
acceptable, as long as there is only one and not two.

While I'm sure "lexicographic product of the longer-prefix orderings" is an
elegant way of stating this, I doubt that the IETF would publish an RFC
that says so, because its intended audience might not understand that
language (I know I don't, and I would guess much of the working group does
not either, and who knows about implementers).

However, leaving things and unspecified - for example, introducing
"disambiguation routes" without saying how they are calculated, is also
unlikely to gain consensus because it is not implementable.

I'm afraid that in order for people to understand what you are proposing
(which is sort of required for them to agree with it), you will need to
explain to them why "OSes" (by which I assume you mostly mean "Linux",
though you don't say what they are) require these disambiguation routes -
for example, by stating that the primitives available make a decision first
on the source address and only then on the destination address, and thus
you need to create extra routing table entries to make things work. You and
I know this already, but I suspect there is very little chance of anyone
understanding this based on your current text alone.

> you don't even explain in prose or justify the particular behaviour that
> you have chosen for source-specific routing.  The reason for this
> particular behaviour was explained to me by Fred Baker by private mail, and
> a summary of our discussion appears in Section 2.2.2 (with proper credit
> given to Fred).
>

Perhaps, but on the other hand, "this is the right thing to do because Fred
Baker says so in private email" is not appropriate justification either. At
least we get to say "we took it to the working group and consensus on the
floor was that this is what we want to do".

> my work to fit a formalism that I happen to find deficient.

Oh no, I'm not asking you to reformulate your work. I will, however, make
the suggestion that if you would like the working group to adopt your work,
then you should write it in a way that the working group can understand and
agree with, and that you avoid duplication of effort. If you do not do so,
then it is likely that your work will not find adoption, with possibly
little sympathy for that outcome.

---

From: Simon Perreault <[email-masked]>
Date: Tue, 09 Jul 2013 09:53:10 +0200

>   the longer-prefix orderings

I, for one, enjoy mathematical succinctness (in small doses). A merged
draft having both that sentence and a longer explanation for
implementers would make me happy.

I agree that the merged document must not be protocol- or OS-specific,
but short implementation notes in appendix are very often useful.

Simon

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 09 Jul 2013 16:49:56 +0200

> While I'm sure "lexicographic product of the longer-prefix
> orderings" is an elegant way of stating this, I doubt that the IETF
> would publish an RFC that says so, because its intended audience
> might not understand that language

Yes.  I've tried to avoid mathematical jargon in our draft, but I was
in a rush, and the formulation is somewhat clumsy (beginning of 2.2.2).
I think I've done a better job in RFC 6126 paragraph 3.5.1, where
I use a similar construction, we'll try to do something similar in the
next version of draft-boutier-homenet-source-specific-routing.

> This is the IETF, so you're certainly free (within reason) to trash
> him for writing something that you assert cannot be implemented,

This is not my objection.

Either you are describing the visible behaviour of routers, in which
case you should use a description sufficiently abstract to be useful
to reason about forwarding behaviours.  Or you're describing an
existing implementation, in which case you should describe the actual
algorithm.  It appears to me that your draft does neither -- it uses
fairly complex data structures while not claiming to describe an
actual implementation.

> Since we have now agreed that the two solutions are in fact the
> same, then any formulation that achieves the consensus of the
> working group is acceptable, as long as there is only one and not
> two.

We certainly don't want homenet routers to be too strongly constrained
(e.g. by a concrete algorithm).  There are three questions to ask:

1. Do different forwarding behaviours interoperate?

The general answer is no -- incompatible forwarding behaviours cause
persistent routing loops (Section 2.2.2).  However, there are
particular cases where everything works out, most importantly mixing
source-specific and ordinary next-hop routing (Section 4.1).  (Please
do not underestimate the importance of this property -- what it says
is that you can mix "legacy" routers with source-specific ones.)

2. Can we characterise a class of interoperable forwarding behaviours?

The hard property -- which we're currently working on reformulating in
a manner that avoids mathematical jargon -- is that a set of routers
will interoperate without persistent routing loops as long as their
forwarding behaviours have a common linearisation.  (This is actually
an equivalence -- you can construct topologies that yield a persistent
routing loop unless there exists a linearisation.  Which is a rather
cool property.)

The softer, engineering answer is given in Section 4.2.  The
formulation there is admittedly clumsy, we're working on it.

3. What class of forwarding behaviours do we want to allow in Homenet?

Clearly, we want to allow both source-specific, destination first
routing, and classical next-hop routing to live in the same routing
domain.  Do we want to allow TOS-specific and flow-id-specific?  Do we
want to allow doubly-specific strategies (e.g. both source- and
TOS-specific)?  (I call these "three-dimensional forwarding
behaviours", you'll understand why when you see the pretty pictures
I'm preparing for Berlin.)

I hope we can define a class of interoperable forwarding behaviours
that is both large enough to cover all of the above, and simple enough
that it can be expressed in comprehensible RFC-ese.

> Baker says so in private email" is not appropriate justification either.

This is a somewhat disingenious way of describing Section 2.2.2.

> Oh no, I'm not asking you to reformulate your work. I will, however, make the
> suggestion that if you would like the working group to adopt your work,

I think there's a misunderstanding here.
draft-boutier-homenet-source-specific-routing-00 is a description of
a working implementation of source-specific routing, that has the
"obviously right" behaviour, and that has been implemented over an
off-the-shelf operating system.  This draft was published in order to
request a slot at the Berlin meeting where I want to present this
work, describe a few of the remaining open problems, prompt further
discussion, and hopefully convince people to attempt their own
implementation.

I am very much surprised at spending so much time justifying the
existence of a draft outlining a working implementation of
a technology that is badly needed for the Homenet effort.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 09 Jul 2013 16:53:33 +0200

> A merged draft having both that sentence and a longer explanation
> for implementers would make me happy.

Matthieu now has a formulation that is both declarative (it describes
where a packet must go without mandating a particular algorithm) and
expressed in fairly elementary terms (it uses the notion of more or
less specific patterns).  It's a little longer than the compact block
of jargon above, but will hopefully remain abstract enough to allow
reasoning.

I'll run it through this list when we've frozen the terminology.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 09 Jul 2013 17:03:38 +0200

> which makes some forms of global optimisation difficult or

Consider the following topology:

           C
          / \
         /   \
   A -- B     S
         \   /
          \ /
           D

Suppose that B routes packets to S through C; then there is no way
that A can possibly route its own packets to S through D.

What happens here is that the route ABDS cannot be selected because
nobody has selected its suffix BDS.  This limitation doesn't occur
with e.g. source routing or circuit switching.

> s/within/(between|among)/ somewhere in there.

Noted, thanks.

-- Juliusz

---

From: Henning Rogge <[email-masked]>
Date: Tue, 9 Jul 2013 17:11:29 +0200

> is that you can mix "legacy" routers with source-specific ones.)

Having multiple source-specific default routes (0.0.0.0/0 or ::/0) are
a good recipe for routing loops if some routers don't support
source-specific routing.

Henning Rogge

--
We began as wanderers, and we are wanderers still. We have lingered
long enough on the shores of the cosmic ocean. We are ready at last to
set sail for the stars - Carl Sagan

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 09 Jul 2013 17:14:12 +0200

> a good recipe for routing loops if some routers don't support

See Section 4.1, notably the second paragraph.

(And yes -- you get it wrong, you die.)

-- Juliusz

---

From: Lorenzo Colitti <[email-masked]>
Date: Wed, 10 Jul 2013 00:21:18 +0900

> fairly complex data structures while not claiming to describe an

The intent was to document something that did not unnecessarily constrain
implementations but was detailed enough to be clear unambiguous. I agree
it's not universe-harmonizingly elegant, but on the other hand, the
documents have to be understood by implementers who aren't always experts
in graph theory.

I do think there's a decent balance there, but of course it could always be
improved. We welcome suggestions.

> formulation there is admittedly clumsy, we're working on it.

Personally, I think you're being a bit too optimistic on what is possible
in the real world. I do think it's good to document the circumstances under
which things are likely to work, but I fear that we won't actually be able
to take advantage of them because we won't be able to know if we're in one
of the working cases. So if we end up in a broken topology, most of the
time routing is dead in the water anyway.

> domain.

If we can achieve this in a sufficiently large set of topologies.
Otherwise, it's possible that it's better to explicitly not support this
mode rather than attempt to support it only if the topology works.

> Do we want to allow TOS-specific and flow-id-specific?

Personally, I don't think so. I think source+destination routing is about
as much as we can reasonably pull off in the real world. Others may
disagree (and I know many people believe that even just src+dst is
impossible to deploy in the real world).

> This is a somewhat disingenious way of describing Section 2.2.2.

I'm just repeating what you wrote.

> discussion, and hopefully convince people to attempt their own

Then perhaps the problem is that instead of an implementation report, it
reads a bit like a scientific paper, with its own introduction and
characterization of the problem (which overlap with the existing work in
this working group), and partly like a specification (but an underspecified
one - for example, it doesn't say what the disambiguation looks like). And
the implementation report itself is unofrtunately lacking crucial details
like what the limitations of current OSes are and what "disambiguation
routes" need to look like, how often they appear in practice, etc.)

I have no problem with the implementation report - in fact, I look forward
to more details when you write them up. But I do think that the part of
your draft that is the implementation report should its own document,
separate from anything else, and I do think that the characterization part
should be in a separate document, either [TROAN], to which the authors do
welcome constructive criticism, or, if the working group thinks otherwise,
something else.

But putting everything in one document is not a good idea. It's true that
this is not how most documents, including as scientific papers, are
written, but on the other hand, IETF RFCs are a more collaborative
environment than your average scientific journal.

---

From: Henning Rogge <[email-masked]>
Date: Tue, 9 Jul 2013 19:34:43 +0200

I think the last paragraph of Section 4.1 is not necessarily true for
all protocols. You might end up with "non-source route" aware routers
that forward the source-route specific information.

Still, as long as the different destinations for the source-routed
default-routes are in a source-route aware subnet it should work. The
"non source-routed" default route will push the traffic into the
"source-route aware" subnet... and from there to the destination.

It should work both with distance-vector and linkstate routing as long
as there is also a "non-sourcerouted" default route.

Henning Rogge

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 10 Jul 2013 14:59:58 +0200

> that forward the source-route specific information.

We're assuming here that "legacy" routers silently discard
source-specific routes.  This is the reason for the encoding we use
for source-specific routes.

> default-routes are in a source-route aware subnet it should work.

Could you please clarify.  Have you identified another case where
everything works out?

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 10 Jul 2013 15:14:13 +0200

> If we can achieve this in a sufficiently large set of topologies. Otherwise,
> it's possible that it's better to explicitly not support this mode rather than
> attempt to support it only if the topology works.

I think we're speaking of two different things here.

The condition on a consistent linearisation that I've given above does
not depend on the topology: Bellman-Ford will converge to a loop-free
configuration as long as there exists a consistent linearisation,
whatever the topology.

Now of course, a loop-free configuration is of little help if the
network is partitioned.  So the question you appear to be asking is
how many specific routers do you need in order to converge to
a configuration that actually gets your packets to the right place.

That's a good question, and one to which we don't have a general
answer yet.  A partial answer is the one given in 4.1.

-- Juliusz

---

From: Henning Rogge <[email-masked]>
Date: Wed, 10 Jul 2013 16:55:36 +0200

> Could you please clarify.  Have you identified another case where

I am looking at the problem from the link-state point of view.

Lets assume there is a random mixture of source-routing aware and
non-aware routers. The only restriction is that there is a
source-aware path of routers between all gateways (gateways to the are
of course source-aware too).

There are two topologies in the network, the default topology all
routers participate in and a "source-aware" topology.

I see three cases when forwarding an IP packet with a "specific source
address" along the default route.

a) the router is not source-routing aware, which means it forwards the
packet along the normal default route
b) the router is source-routing aware, but has no source-aware path
towards the gateway. In this case it will still forward the packet
along the normal default route because it has no connected path to the
gateway selected by the source address (shortest path first result
should be empty).
c) the router is source-routing aware and has at least one path
towards the selected destination. In this case it will forward the
packet towards the selected gateway. The next hop will also be
source-aware, otherwise the link would not have been selected for the
"source-aware" topology.

Every non-source-aware default route will bring the traffic into the
source-aware region around the gateways, which mean they should reach
the desired gateway (even if it hit a different gateway first).

This should work with or without dropping data on the source-aware
topology on the non-source-aware routers.

Henning Rogge

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 10 Jul 2013 17:44:04 +0200

> I am looking at the problem from the link-state point of view.

You're assuming that non-source-specific routers drop source-specific
routes, right?

> of course source-aware too).

Yeah, that's exactly what we describe in 4.1.

> the desired gateway (even if it hit a different gateway first).

Yes.  Hence the language at the end of 4.1.

A related question is whether it is okay to reannounce a source-
specific route as a non-specific one, for the sake of legacy routers.
(This is analogous to aggregation -- reannouncing a more specific
route as a less specific one.)  The general answer is no, so I was
wondering if you'd identified a class of topologies where it is okay
to do so.  Does anyone know any good papers describing when aggregation
is safe?

-- Juliusz

---

From: Henning Rogge <[email-masked]>
Date: Wed, 10 Jul 2013 17:51:52 +0200

> You're assuming that non-source-specific routers drop source-specific

Doesn't really matter, at least for the routes to the gateways.

> Yeah, that's exactly what we describe in 4.1.

Okay... wasn't sure about it.

> to do so.  Does anyone know any good papers describing when aggregation

In my example I assumed that every gateway announces a
non-source-specific route too, so there should be no special code
necessary for the "normal" routers.

In terms of OLSRv2 an IPv6 gateway could announce its ::/0 route and
add a "src prefix xyz::/64" attribute (TLV) to it. Routers that do not
understand this attribute just ignore it.

Henning Rogge

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 10 Jul 2013 18:19:53 +0200

> necessary for the "normal" routers.

Unless I'm missing something, that's not as simple as you make it.
Consider this:

  -- A -- B --

Suppose that A announces (::/0, alpha), and B announces (::/0, beta)
(two source-specific default routes).  Suppose further that, as you
suggest, both A and B announce default routes (::/0, ::/0).

What happens when A receives a packet that's not sourced in either
alpha or beta?  It will route it towards B (which, you will recall, is
announcing a non-specific default route).  Now B will send the packet
back to A, and you're in trouble.

So you cannot just announce a default route, you must redistribute
a blackhole route.  But then, you might end up overriding a bona fide
default route with your blackhole.  Grr.

I'm pretty sure various workarounds can be devised (such as using
a very high metric for the blackhole route, or adding a flag "this
route must be ignored by source-specific routers"), but I'd obviously
prefer avoiding such hacks.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 10 Jul 2013 18:26:00 +0200

> Doesn't really matter, at least for the routes to the gateways.

Hmm...

  -- A -- X -- B --
       \     /
        - Y -

A is announcing (::/0, alpha), B is announcing (::/0, beta).  X is
source-specific.  Y is a legacy router.

Suppose now that rather than dropping the source-specific routes, Y is
casting them into non-specific default routes, and that it has
selected A as its next hop for the default route.

Now X crashes:

  -- A         B --
       \     /
        - Y -

A's routing table is now just (::/0, alpha) and (::/0, ::/0), with the
latter pointing at Y.  But Y is still pointing its default route at A,
so you're in trouble.

If legacy routers just drop specific routes -- you get a blackhole
instead of a routing loop.

-- Juliusz

---

From: Teco Boot <[email-masked]>
Date: Wed, 10 Jul 2013 21:44:09 +0200

> back to A, and you're in trouble.
No. A knows B sends out a specific default route. A shall not send packets to B where B doesn't know what to do with it. This is delegated ingress filtering.
In a homenet, "normal" routers know how to handle multi-homing. 

Teco

---

From: Ray Hunter <[email-masked]>
Date: Thu, 11 Jul 2013 08:34:58 +0200

> instead of a routing loop.
Hardly surprising. Whenever you have multiple routing technologies
active in one network, you're going to get pathological cases.

What would a current standard OSPF implementation do today?
I presume ignore the LSA's for source-specific routing, and cause a
black hole.
That's not so bad IMHO.

What's the fix?

Detect routing loops automatically so Y disables injecting the
synthesised default route when it sees packets bouncing?
If you're going to do that then you've had to update Y's code anyway, so
you may as well implement source-specific routing.

Mandate all Homenet routers MUST support source-specific routing, and
update the version number of the routing protocol?

Advise users to move any legacy routers to the leaves of their network,
or remove them completely?
That's pretty much what's going to happen anyway with legacy non IPv6
speaking routers.

regards,
RayH

---

From: Lorenzo Colitti <[email-masked]>
Date: Thu, 11 Jul 2013 16:25:26 +0900

On Wed, Jul 10, 2013 at 11:55 PM, Henning Rogge <[email-masked]>wrote:

> The only restriction is that there is a source-aware path of routers
> between all gateways (gateways to the are of course source-aware too).
>

But isn't this an impossible requirement to meet in reality? What if users
plug things in in such a way that there is no such path between two given
gateways?

---

From: Henning Rogge <[email-masked]>
Date: Thu, 11 Jul 2013 12:44:44 +0200

> back to A, and you're in trouble.

I would assume that a packet that is not source-ip tagged for a
specific gateway would just go out of any gateway. In this case
gateway A.

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Thu, 11 Jul 2013 12:48:44 +0200

> source-specific.  Y is a legacy router.

Okay.

> selected A as its next hop for the default route.

Y is just announcing that it only does forward normal traffic, its not
part of the "source-specific" topology.

> latter pointing at Y.  But Y is still pointing its default route at A,

I think its the same issue/misunderstanding we had in the last post.
The question if traffic for an unspecific source-address can go out of
any gateway or not. If it can go out of any gateway, A will just take
the traffic and forward it to the external gateway without asking Y.

What do you think?

Henning Rogge

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 11 Jul 2013 14:46:33 +0200

> part of the "source-specific" topology.

How do you identify "normal traffic"?

Recall that we're not "tagging" source-specific packets -- these are
perfectly ordinary IP packets that happen to have a source address
that matches a source-specific route.

(If you start tagging packets with the gateway's address, then you're
doing weak source routing -- which is a rather cool technology in
itself, see reference [CLARK] in draft-boutier-tralala, but it is out
of scope for this particular work.)

> the traffic and forward it to the external gateway without asking Y.

Yeah, that's essentially equivalent to redistributing a non-specific
default route from each gateway, perhaps a blackhole route, and
perhaps with a high metric.  I guess that's what we need to do, since
it breaks routing loops in many cases.  It makes me vaguely uncomfortable,
but I'm not quite sure why.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 11 Jul 2013 15:11:50 +0200

> But isn't this an impossible requirement to meet in reality?

I have no idea.  We're just exploring the space of possible solutions
right now -- hey, it's not like we've had a lot of operational
experience with source-specific routing yet.  We're playing with
things, and looking what breaks.

> What if users plug things in in such a way that there is no such
> path between two given gateways?

Things break.  We make sure things break as gracefully as possible.
Then we'll need to ask ourselves whether we want to support such
hybrid topologies in the first place.

(My gut instinct is to agree with you -- we'll probably want to forbid
hybrid networks --, but I'm keeping an open mind until we learn more.)

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 11 Jul 2013 16:06:56 +0200

> I presume ignore the LSA's for source-specific routing, and cause a

Agreed.  (Hence the use of a new TLV for source-specific routes in
Matthieu's code, rather than a sub-TLV of the existing Update TLV --
the new TLV is silently ignored by RFC 6126 routers.)

> you may as well implement source-specific routing.

Fully agreed.  If we change the code in the first place, we might as
well avoid the dodgy hack and go for the clean solution.

> update the version number of the routing protocol?

Please no.  Even if we forbid non-specific routers in Homenet, there's
no reason to prevent enlightened amateurs from experimenting with
hybrid networks.  (And what else is a university researcher than an
enlightened amateur?)

Note that if we go with my suggestion of mobile nodes participating in
the routing protocol (but not actually routing third-party packets),
then we might hypothetically want to allow such nodes to use
non-specific routing only -- or even to accept the default route only.
Even if we don't want to go with this suggestion, we certainly don't
want to prevent people from experimenting with such solutions.

> or remove them completely?

Right now I'd say the latter, but I'm still working on my opinion.

Please keep in mind, however, that if Homenet is successful, we'll be
stuck with it for the next 20 years or so.  There's no saying what
kind of networks will emerge over that timeframe, and we will curse
our former selves for any impediments to compatible extensions we
might put in the protocol.

-- Juliusz

---

From: Teco Boot <[email-masked]>
Date: Thu, 11 Jul 2013 17:09:59 +0200

With BRDP, I suggest to use whatever untouched routing protocol. I suggest to add another protocol, in my proposal something on top of RA. I do not understand your arguments against RA.

With whatever CHiRP we come up with, I don't think we face an installed base at homenets. Why bother backwards compatibility?

If we reuse an existing routing protocol and enforce routing to external networks using the source address, we must make sure homenet routers only have adjacency with compatible CHiRP routers. Many ways to enforce, update version is just one of them.

Support for university researchers would be my lowest priority :-) Don't take this wrong, I highly appreciate efforts on plug and play networks from everyone. But as often, options can be our enemy.

Teco

PS: From earlier mail, CHiRP: Common Homenet (interior) Routing Protocol

---

From: Henning Rogge <[email-masked]>
Date: Fri, 12 Jul 2013 12:54:53 +0200

The problem with "forbidding" such topologies will be that things will
break and users will not know why.

Henning Rogge

---

From: Ray Hunter <[email-masked]>
Date: Fri, 12 Jul 2013 21:09:32 +0200

> break and users will not know why.

Sure, but users are also probably going to plug IPv4 only routers into
the middle of Homenet.

As long as it all breaks reasonably gracefully, that's the best you can do.