Subject: Re: Working Group Last Call on "Multi-Topology (MT) Routing in OSPF" (draft-ietf-ospf-mt-03.txt)

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 18 Apr 2005 14:25:04 -0700

Tony, replies inline below. 

> -----Original Message-----
> From: Tony Przygienda [mailto:[email-masked]] 
> Sent: Monday, April 18, 2005 1:06 PM
> To: [email-masked]
> Subject: Re: Working Group Last Call on "Multi-Topology (MT) 
> Routing in OSPF" (draft-ietf-ospf-mt-03.txt)
> 
> >
> >"The above specification of MT routing does not allow for forwarding 
> >paths to be constructed with a mix of MT links and default links, in 
> >such cases for which a fully MT path does not exist.  For 
> the purpose 
> >of transition, it is possible to implement an option that 
> relaxes the 
> >constraint that all links in an MT path only use MT links.  Such an 
> >option, if used, MUST be applied consistently for a given MT in a 
> >routing domain (so that consistent forwarding decisions are 
> made), and 
> >SHOULD be used with caution by operators because of its potential to 
> >enable routing loops if configured incorrectly."
> >  
> >
> There is a _lot_ of looping potential here from experience. I 
> am not clear first which scenario you are pursuing. Either
> 
> 1) all routers are MT aware in the deployment, then why don't 
> you just add the necessary links to the
>     desired MT topology and you don't need any such hacks.
> 2) If you desire to have some routers being non-MT capable, 
> unless you give
>     an exact algebra (or worded more simply, rules) that the 
> operators must follow to avoid the
>     loops you allure to, how is he supposed to know how to 
> deploy your hack ?

I had in mind #2-- a specific scenario customer for which
i) it is operationally difficult to upgrade all routers to MT in same
timeframe
ii) one or two routers at key points (e.g. network border) are blocking
the effective use of MT
iii) by inspection of the topology, loops are avoided

I agree that the above is a hack and is dangerous in general.  Because
of that, I will concede that it may be best to leave out of the spec,
and treat it as a hack.

> >
> >Section 3.8 (Forwarding in MT):
> >The specification is ambiguous as to how to treat packets 
> that a) map 
> >to a defined MT in the area, but b) do not have a path to 
> the desired 
> >prefix in the MT topology, yet do have a default path there.  In the
> >1583 TOS routing, such packets would fall back to the 
> default topology.
> >  
> >
> >I would recommend that such behavior be preserved here, 
> because it is 
> >more robust, especially in light of the new capability to 
> exclude links 
> >from the default topology if so desired.  In fact, it should be 
> >possible to define the behavior as an option; i.e., one 
> could configure 
> >a particular MT-ID to either fallback to default or not.
> >  
> >
> MT is _not_ TOS routing (any claim as to that is made purely 
> to generate confusion IMO).
> MT is a solution to generate multiple, _independent_ 
> topologies in the same routing protocol and not a 
> 'special-capability link' vs. 'general-link' 
> solution.
> Simply forwarding along the default path if a link lacks a MT 
> metric will lead to routing loops very easily. Example:
> 
>     +------ #0/1 ----------------------->C
>     |                                    ^
>     v                                    |
>     A <-- #1/10 ---> B <---#0/10---------+
>     ^                ^                
>     |                |
>     +-----#0/1-------+  
> 
> 
> (where #1/X denotes link in topology 1 with metric X, assume 
> all links bidirectional with same metric, A, B and C all 
> understand MT). If A forwards to B in topology #1 but B 
> forwards along the shortest 'default' 
> path you'll have a
> persistent loop. 

I am not saying (here) to mix and match default and MT links-- clearly,
that can lead to loops.  Instead, in your example, if A forwards to B in
topology #1, it can only do so if the remainder of the path from B to
the destination exists in topology #1-- the packet does not (must not)
jump out of this topology downstream.  If A doesn't have the end-to-end
MT path, A will choose the default topology, and B will likewise do
so... until (if the case arises) the MT topology does exist to the last
hop, in which case the packet can be sucked into the MT topology.

To be clear, the two use cases that I have in mind are that i) every
router does not necessarily need to enumerate MT-ID for every link in
the topology, or ii) not every router is MT capable.

> Now start to imagine what will happen if you 
> start to deal with subset of routers that do not understand 
> MT on the way.

Consider packets that have been traversing a set of non-MT routers, and
then suddenly hit an intermediate patch of MT routers (not contiguously
connecting to the last hop) for which the packet matches an MT.  What
should be done with such packets?  They cannot be routed to the
destination on an MT topology exclusively.  Should they be dropped?
Maybe, but I would argue that an operator may instead want them to fall
back to the default topology in this case.

That is, while MTR is not TOS routing, 1583 TOS forwarding behavior
should not be precluded (or mandated either-- it should be configurable
option).

> 
> I would strongly suggest to leave anything out as to general 
> fallback-default-topology forwarding from the spec (you're 
> free of course attempting any little private hack you can get 
> people to pick up) unless the implications and algorithms are 
> very tightly written down (as footnote: there exists an 
> algebra [and algorithm] that deals with this problem 
> precisely [i.e. default topology being a subset of the MT 
> topology] but it delivers non-obvious results, especially the 
> Bellman-suboptimality doesn't hold [i.e. the resulting set of 
> shortest-paths is not a tree] which is enough to make most 
> people heads spin and decide they don't care about this 
> problem all THAT much)
> 

This I would argue is not a hack, but affects how gradual deployment can
behave.

Returning to a point that Peter made:

> - one can define various forwarding behaviors with different 
> results. As 
> you said implementation can provide a configurable forwarding 
> behavior.
> - what we specified in the draft was how OSPF should compute 
> paths and 
> populate topology specific RIB. I'm not sure the specification of how 
> the forwarding entries in various RIBs/FIBs are used during the 
> forwarding belongs to this draft.

If you want to take the stance that forwarding is out of scope of the
draft (that it only deals with how to build MT RIB-- not how to convert
that RIB into a FIB), then I would suggest that the wording in 3.8 be
tweaked, because it is making statements about how forwarding works that
preclude the forwarding behavior described above.  

New suggestion:

"This document describes how multiple topologies can be built in OSPF's
routing information base.  It is outside of the scope of this document
to describe how these routes are mapped to forwarding rules.  It is also
outside of the scope of this document to consider different methods of
associating an incoming packet to a corresponding topology.  User
configuration MUST be consistently applied in a network to avoid
incorrect forwarding behavior."

Tom

---

From: Peter Psenak <[email-masked]>
Date: Tue, 19 Apr 2005 10:02:39 +0200

Thomas,

 > incorrect forwarding behavior."

I'll reword 3.8

Peter

---

From: Yakov Rekhter <[email-masked]>
Date: Tue, 19 Apr 2005 06:27:56 -0700

Peter,

>  > incorrect forwarding behavior."

Actually what needs to be consistenly applied in a network are the
rules for how routes are mapped into forwarding rules and methods
of associating an incoming packet to a corresponding topology.

Yakov.

---

From: Tony Przygienda <[email-masked]>
Date: Tue, 19 Apr 2005 16:55:20 +0000

>ii) one or two routers at key points (e.g. network border) are blocking
ok, I would gladly yield to your pressure to do so ;-)

>iii) by inspection of the topology, loops are avoided
huh, that concept I cannot become friend with. Kind of takes the 
reason-d'etre
of dynamic routing away.

>of that, I will concede that it may be best to leave out of the spec,
agreed.

>>....
ok, yes, that is actually one possible solution for the algebra of this 
kind of nested
topologies (this solution proven to be loop-free) but then you MUST 
specify the according behavior
in the spec (i.e., every MT router, if a topology X !=0 path end-2-end 
does not exist,
MUST forward along the default topology, EVEN if a topology X next-hop 
exists!
That's what I ment by such an SPF not being a tree anymore since what 
you have in
terms of forwarding paths to all destinations on the network is all of a 
sudden only a DAG.
I assume as well that you want
to drop the packet if there is not path in #X and in #0. That's also OK.

Footnote if you're interested: it is possible to 'jump up' a topology, i.e.
you can start routing along default path and then if a router knows a 
feasible
path in #X to destination, it can forward the packet along that path. 
That however
just complicates the behavior for minimal gain.

>back to the default topology in this case.
yes, as above, as long as ALL the routers (from the first on) forward along
default topology you will be ok.

>should not be precluded (or mandated either-- it should be configurable
It is just _confusing_ insisting on calling this thing TOS forwarding.  
TOS is just
one topology with all the same prefixes and an undeployed forwarding 
'hack'. Here,
when you implement what you are talking about correctly, you will 
realize that
you are running into a completely different beast, you must run kind of 
a nested SPF
(and for the spec, you better write the algorithm cleanly down, it's not 
trivial)
for _each_ topology #0 you want to be able to 'downgrade' to 
default-topology
forwarding since otherwise you will be very confused as to which prefixes
belong to which topology (and don't forget, they can overlap if you 
'flatten' the
topologies). As well, your hack will force you for each incoming packet 
on each link to
be able to classify it as belonging to any topology #0, rather than just 
the
ones you configured on the link, maybe an expensive operation.

>preclude the forwarding behavior described above.  
Read section 12. of the MT ISIS draft, I would suggest. Forwarding behavior
(and FIB segregation) can be 'classified' into a framework but it cannot be
'prescribed' IMO and that's why I wouldn't put your 'addition' into the 
draft either.
In pretty general terms, what Yakov wrote is correct, albeit you can
generalize it even further to say that a chain (in mathematical sense) 
of forwarding
classifications and forwarding behaviors in the network must exist that 
is loop-free
[that's where the 'algebra' I mention all the time comes in, the algebra 
actually
seems to suggest that the whole thing is a 'ring' and the forwarding 
behaviors
'must' be a chain, here however my math background is too weak, I used 
to work
places where I had a 'crutch' of an ingenious russian mathematician who 
was far more smart
than I was but I tended to understand the practical problems to take his 
tools to better ;-)
I know a couple of 'fancy'
ways people do forwarding on MT these days, e.g. one deployment feeds 
couple of
topologies into a single one. I think your 'addition' will become more 
and more
complicated in all those scenarios (albeit, as I said, an algebra exists 
to prove/disprove
the correctness and completeness of an according forwarding behavior 
[i.e. behavior
that uses the 'default' topology as 'backup'])

Final remark: One of the things with the MT draft was that ISP people 
(at least some I talked to)
are fairly paranoid when selling any kind of 'partitioned' network for 
packet not to end up in
the 'wrong' topology for security reasons. Your 'addition' would cause 
packets to show up in
funny places that overlap with other people topologies . Maybe an issue, 
maybe not since
OSPF/ISIS are IGPs and therefore pretty much all one control AD for the 
ISP.

    --- tony

---

From: Naiming Shen <[email-masked]>
Date: Tue, 19 Apr 2005 10:56:12 -0700

I agree that the default topology "jumping" should not be in this
spec. Routers want to do that need to consider, why just jumping
to the "default topology" not some other topologies; how the
reply packets come back to the source if they do that; and
security considerations.

I think a better way to achieve the goal is to do "redistribution".
We can think of them as a provider running both ISIS and OSPF
in two different topologies, and some of the routes need to be
announced into other side. This is a clean design and can be
easily controlled. It's an implementation and configuration
issue. Just be careful to tag those "redistributed" routes
so they will not be "redistributed" back into the original
topology on another router thus causing packets looping.

thanks.
- Naiming

Tony Przygienda said the following on 04/19/2005 09:55 AM:
>>> There is a _lot_ of looping potential here from experience. I am not 
>>> clear first which scenario you are pursuing. Either
>>>
>>> 1) all routers are MT aware in the deployment, then why don't you 
>>> just add the necessary links to the
>>> 2) If you desire to have some routers being non-MT capable, unless 
>>> you give
>>>    an exact algebra (or worded more simply, rules) that the operators 
>>> must follow to avoid the
>>>    loops you allure to, how is he supposed to know how to deploy your 
>>> hack ?
>>>   
>>
>>
>>> (where #1/X denotes link in topology 1 with metric X, assume all 
>>> links bidirectional with same metric, A, B and C all understand MT). 
>>> If A forwards to B in topology #1 but B forwards along the shortest 
>>> 'default' path you'll have a
>>> persistent loop.   
>>
>>
>>> Now start to imagine what will happen if you start to deal with 
>>> subset of routers that do not understand MT on the way.
>>>   
>>
>>
>>> fallback-default-topology forwarding from the spec (you're free of 
>>> course attempting any little private hack you can get people to pick 
>>> up) unless the implications and algorithms are very tightly written 
>>> down (as footnote: there exists an algebra [and algorithm] that deals 
>>> with this problem precisely [i.e. default topology being a subset of 
>>> the MT topology] but it delivers non-obvious results, especially the 
>>> shortest-paths is not a tree] which is enough to make most people 
>>> heads spin and decide they don't care about this problem all THAT much)
>>>
>>>   
>>
>>
>>> - one can define various forwarding behaviors with different results. 
>>> As you said implementation can provide a configurable forwarding 
>>> behavior.
>>> - what we specified in the draft was how OSPF should compute paths 
>>> and populate topology specific RIB. I'm not sure the specification of 
>>> how the forwarding entries in various RIBs/FIBs are used during the