Subject: [Isis-wg] draft-ietf-zinin-flood-opt-01.txt

From: Alex Zinin <[email-masked]>
Date: Mon, 9 Oct 2000 18:21:25 -0700

Folks,

  The new version of the flooding optimization draft
  has been submitted to the IETF directories today.

  So far, it is available at the following URL:

  http://www.employees.org/~azinin/draft-ietf-zinin-flood-opt-01.txt

  Regards,
-- 
Alex Zinin

_______________________________________________
Isis-wg mailing list  -  [email-masked]
http://external.juniper.net/mailman/listinfo/isis-wg

---

From: Alex Zinin <[email-masked]>
Date: Tue, 10 Oct 2000 11:19:23 -0700

Thanks, Jim.

Regarding the fully meshed topo's.

To begin with, I'm not a big fan (gently put) of "optimizing"
dynamic algorithms with some manually configured stuff...
So, for me personally, the mesh group in ISIS and LSA blocking
in OSPF (yes, we have it implemented) is not an option (again,
it's just my opinion).

As far as automated algorithms are concerned, pure spanning
flooding tree over the topo graph is a non-starter, I think.
Redundant spanning tree may not be worth spending time since
a) regions with highly redundant topology (like fully meshed groups)
may be addressed more optimally, I guess, and b) not so redundant
regions may not be interesting...

We could discuss this, actually, with the first question being
"do we really need this" ? ;)

Cheers,

-- 
Alex Zinin

Tuesday, October 10, 2000, 2:48 AM, Jim Boyle wrote:

> this is very good for addressing how to optimize flooding w/ multiple
> links between two nodes.                                    

> How can a fully meshed topology w/ on the order of 1 link between each    
> node be addressed (I'm not sure how mesh groups work).

> I've heard of a hack that limits flooding from N^2 to more like 6N   
> so there is an adjacency/forwarding topology and a flooding topology 
> This could be useful with either manual configuration like "no    
> ospf flood" or via automated pruning to a certain level of adjacency (even
> with SRLGs taken into account, perhaps).

> regards,

> Jim

> p.s. - pruned mpls wg

> On Mon, 9 Oct 2000, Alex Zinin wrote:

---

From: Tony Li <[email-masked]>
Date: Tue, 10 Oct 2000 11:42:27 -0700 (PDT)

| We could discuss this, actually, with the first question being
 | "do we really need this" ? ;)

IM(ns)HO, we are in dire need of a replacement flooding algorithm that
scales much more nicely.

It needs to adapt to the topology as end-users cannot be expected to
provide us with additional configuration information about their topology.

It needs to be robust in the case of failure, not causing massive
pertubations of the flooding path on a single link failure.

It needs to restrict the amount of flooding that any single node needs to
do.

Currently, my best guess is that a redundant spanning tree is the best
known direction.

Tony

---

From: Dave Katz <[email-masked]>
Date: Tue, 10 Oct 2000 11:51:08 -0700 (PDT)

I concur.  The mesh group hack is just that, a hack.  It saved our bacon
in a pinch.  The fact that it's been documented is a little embarassing.
I tried to hide the awful truth, but I was exposed.  Oh, well.  ;-)

---

From: Jim Boyle <[email-masked]>
Date: Tue, 10 Oct 2000 15:36:39 -0600 (MDT)

I don't know.  Imagine a 1000xOC192 router, and a service provider using
it in say, 100 markets.  You are going to get some meshing here.  As for
parallel links between two nodes, bundle the links if possible, if not
(e.g. some go N some go S) - you're draft sounds good for that portion of
the flooding.

However, you are still left w/ a full mesh (or close) topology - perhaps
one that isn't as bad as some of the ATM meshes of yesteryear, and
processors are much faster today, so... maybe it's not worth it.

Then again..... maybe that big old router doesn't want to deal w/ making
100 copies of the LSA, or checking the 100 or so he gets echo'd back.  I
just hope there aren't cases where that mesh loses, for instance, 25% of
it's links, affecting 75% of the routers.  Hmmm...  75 routers, 75 LSAs,
75-100 to flood (to non-affected adjacencies), that's 75^2 before we even
get to the echo.

Then again.... with link bundling, infinitely huge routers, dirt cheap
router ports (and OEO), maybe we can pull all IP traffic through most
routers, even if it's transit.  Then with a simple topology, we have no
worries.

Jim

---

From: Jim Boyle <[email-masked]>
Date: Tue, 10 Oct 2000 03:48:16 -0600 (MDT)

regards,

Jim

p.s. - pruned mpls wg

---

From: Alex Zinin <[email-masked]>
Date: Wed, 11 Oct 2000 17:43:56 -0700

> IM(ns)HO, we are in dire need of a replacement flooding algorithm that

I don't really like that "replacement" word ;), but I agree we
may need to modify the algo in some places...

> provide us with additional configuration information about their topology.

Agree.

> pertubations of the flooding path on a single link failure.

Agree.

> It needs to restrict the amount of flooding that any single node needs to

Not sure what you mean here...

> Currently, my best guess is that a redundant spanning tree is the best

If there are enough interested parties, we could create
a design group made of ISIS and OSPF guys and consider
possible options.

Alex.

---

From: Tony Li <[email-masked]>
Date: Wed, 11 Oct 2000 18:07:52 -0700 (PDT)

| > It needs to restrict the amount of flooding that any single node needs to
 | > do.
 | 
 | Not sure what you mean here...

Think about the amount of replication that a single node needs to perform.
Imagine that you have a network of tens of thousands of routers that are
fully meshed on a L2 fabric.  All of the other requirements as specified
might result in a single node being selected as the replication engine and
it having to transmit each LSP/LSA tens of thousands of times.

This does not scale.

However, hierarchy would scale.  If the result is a flooding tree where
each node performs a limited number of replications, then no processor is
unduly burdened.  The only question now is how much replication we would
like a processor to do.  More formally, what is the degree of the node in
the flooding graph?  Higher degree requires more processor but results in a
shallower tree with lower flooding latency.  Lower degree results in less
work and longer latency.

 | > IM(ns)HO, we are in dire need of a replacement flooding algorithm that
 | > scales much more nicely.
 | 
 | I don't really like that "replacement" word ;), but I agree we
 | may need to modify the algo in some places...

If you can meet all of the requirements and still interoperate or even
function without a flag day, that would be a genuine coup.  ;-)

 | > Currently, my best guess is that a redundant spanning tree is the best
 | > known direction.
 | 
 | If there are enough interested parties, we could create
 | a design group made of ISIS and OSPF guys and consider
 | possible options.

I'm game.  However, interest to date on this has been.... low.

Tony

---

From: Alex Zinin <[email-masked]>
Date: Wed, 11 Oct 2000 19:16:00 -0700

> Think about the amount of replication that a single node needs to perform.

Agree.
This could be *partially* be addressed with:

 a) good pointer-work in the code :)

 b) notion of "replication groups" when flooding newly installed LS{A|P}s
    over a bunch of interfaces. This can be "a bit" of mess, though
    (the keyword is "peer-groups" ;).

> fully meshed on a L2 fabric.

Sounds familiar :)

>   All of the other requirements as specified

Yeah... Multicast/broadcast capabilities of the L2 part would
definitely help, but I agree, if we have a large number of interfaces
in a box and the guy with sysadmin rights has configured them to be
in one area...

> unduly burdened.

There's always the other part in this equation --- the number of
LSAs... If we continue going the same direction (flat IGP domains,
flat TE domains, etc.), we may hit the same problem later...

>   The only question now is how much replication we would

Not only this is the question.
We would need to assure the same level of determinism in flooding as
we have today. It's definitely going to be more than just pruning
the flooding topo to the tree.

> function without a flag day, that would be a genuine coup.  ;-)

I do not think we should consider other options...

> I'm game.  However, interest to date on this has been.... low.

Yeah... And this time, I'm not going to ask on the NANOG list :)
Those who are interested or have something to say, please, speak up.

So far we have Jim, Tony, Dave [if I understood him correctly ;)]
and me...

Alex.

---

From: Tony Li <[email-masked]>
Date: Wed, 11 Oct 2000 23:04:04 -0700 (PDT)

Alex,

 | Agree.
 | This could be *partially* be addressed with:
 | 
 |  a) good pointer-work in the code :)
 | 
 |  b) notion of "replication groups" when flooding newly installed LS{A|P}s
 |     over a bunch of interfaces. This can be "a bit" of mess, though
 |     (the keyword is "peer-groups" ;).

With all due respect, I don't believe that these are sufficient.  Even with
optimal pointer work, you're maintaining a list of transmissions and
retransmissions per adjacency, or a scanner and one bit per adjacency.
This implies that your overhead scales linearly with the number of
adjacencies, which is exactly the situation that we'd like to avoid.

The "peer groups" (ala BGP) are really only of use when you have to compute
the updates and can amortize the computation across the numbers of the
group.

 | > However, hierarchy would scale. If the result is a flooding tree where
 | > each node performs a limited number of replications, then no processor is
 | > unduly burdened.
 | 
 | There's always the other part in this equation --- the number of
 | LSAs... If we continue going the same direction (flat IGP domains,
 | flat TE domains, etc.), we may hit the same problem later...

Correct, this would decrease the other multiplier.  However, when a network
operator is given the choice of restricting the growth of his network,
restricting its feature set and therefore optimality or inspiring his
network equipment vendor to work harder, which do you think they will
prefer?

Yes, that's a rhetorical question.  ;-)

 | We would need to assure the same level of determinism in flooding as
 | we have today. It's definitely going to be more than just pruning
 | the flooding topo to the tree.

I'm not sure that I understand this requirement.  Are you suggesting that
we need a deterministic flooding algorithm?  Or that there needs to be user
control over the resulting active flooding topology?

Tony

---

From: Alex Zinin <[email-masked]>
Date: Thu, 12 Oct 2000 11:18:22 -0700

Tony:

> With all due respect, I don't believe that these are sufficient.
[...]

That's why I said "*partially* addressed".

> Yes, that's a rhetorical question.  ;-)

I think I meant a bit different thing, but I won't start another
discussion... ;)

> control over the resulting active flooding topology?

I mean we need to make sure the flooding algorithm (if modified)
guarantees the same results in PDU delivery in the presence of arbitrary
topology changes (including those killing both branches of the
redundant tree), as the current one.

Alex.

---

From: Tony Przygienda <[email-masked]>
Date: Fri, 13 Oct 2000 08:47:16 +0200 (MEST)

Here's my jest on the flooding-optimization problem:

First, I think it's a good idea to get a small group
of people in a room and after some high-flying 
discussions get some rough-cut proposal out that 
preferrably a Ph.D. candidate or an agressive
company goes off to tinker with 
and comes back with implemenation results as either
 papers or competitive advantage. To get anything 
 done, my opinion is that group has to be restricted
 to people with at least one deployed commercial
 link-state under their belt or serious researchers
 that dealt with link-state and a group of more 
 than 15 people won't get anything done anyway ;-)
BTW,  I tried to encourage
2-3 candidates in last years to pick up the topic
but without success. Either the topic is not sexy
enough or I'm a really bad sales-guy ;-) Withough
someone willing to go and do the work on gated or 
a commercial piece of software the topic will end 
up as it always ended up so far, an interesting 
discussion without practical implications. 

There was a flurry of activity on the research side 
about 2-3 years ago and to my knowledge 2 streams of 
thinking
are around: one is the spanning tree on top of 
topology (Bala's paper is an example, convergence
has been proven) algorithms are variations of 802.1
mostly or distributed Bellman-Ford, 
the other one, much less known is a variation
of a token-passing algorithm building hierarchical
trees (kind like multi-cast in PNNI, not algorithm-
wise but in the sense of trees built). Some thinking
was spend on building 2 redundant trees that can fall-over
when first one is cut or alternatively the two
sides of the tree operate independently until merged
again. Not sure that has been published and if, it's 
a while and not in IP context. 

Both approaches have an obvious common underlying problem:
When converging the tree, the very underlying mechanism
(flooding) is being fiddled with, possibly affecting
flooding-speed and therefore the convergence of
the tree. So the so-formed control-loop needs to
be broken or dampened somehow obviously.

	so who's game & when ? 

	-- tony

---

From: Alex Zinin <[email-masked]>
Date: Fri, 13 Oct 2000 22:47:27 -0700

Tony:

I think I'll establish an alias for this discussion
and will drop it to the lists.

>         so who's game & when ? 

Hawaii, next month ;)

What about an informal BOF at the next IETF?

BTW, I think we should welcome presentations from
academia as well. Maybe with preliminary abstract
review.

Alex.

---

From: Vijay Gill <[email-masked]>
Date: Sat, 14 Oct 2000 14:40:35 -0400

> academia as well. Maybe with preliminary abstract

Folks, this might be of interest.

http://www.nanog.org/mtg-0010/igp.html

Abstract: Towards Millisecond IGP Convergence 
Cengiz Alaettinoglu, Van Jacobson, & Haobo Yu, Packet Design 
--------------------------------------------------------------------------------

On currently deployed IP networks, "convergence" times, or the ability to
reroute, is often cited as one of the key issues in providing new services
and larger scale. It is, however, possible for link-state routing
protocols to converge in link propagation time scales, that is, in tens of
milliseconds. Why then are deployments of IS-IS, a link-state routing
protocol, not anywhere near this point? 

In this talk, we present some analyses of IS-IS convergence by showing its
behavior upon link/router failures and repairs, and its scaling properties
to large networks, both in terms of number of nodes and links. We then
explore changes needed in the IS-IS specification and implementations to
reach IGP convergence in milliseconds. Our results are based on
experimentation done with IS-IS, but some of the findings may apply to
OSPF as well. 

/vijay