Subject: Questions about hierarchy

From: Radia Perlman - Boston Center for Networking <[email-masked]>
Date: Fri, 2 Oct 1998 19:36:41 -0400 (EDT)

Two quick questions, with long verbiage afterwards
to explain the 2nd question, in case it's not
clear what I'm talking about:

1) is there a more recent specification of IS-IS than
the infinitely old RFC 1142?

2) does IS-IS officially support arbitrarily levels
of routing hierarchy? Do any implementations
support it?

***********
skip the following if the 2nd question was self-explanatory.

There was once an internet draft about how
"level 2" IS-IS could actually be arbitrarily many
levels of hierarchy. Just draw a circle, configure
the boundary routers with summary prefixes for the
address inside, and have a router attached to two
circles pass prefixes from one to the other.
This required no protocol changes to IS-IS, it
just required implementations capable of running
multiple instances of the routing protocol.

NLSP (which is just IPX-specific IS-IS) specified
this behavior. The IS-IS internet draft describing
how to do it expired many years ago.
If I remember correctly, Cisco's implementation already
did multiple instances, and so it could do arbitrarily
many levels of hierarchy, whereas some other vendors'
implementations (like Novell) couldn't.
But it was only the border routers that needed this
capability.

The question is: what is the current official position of
IS-IS on hierarchy levels?

Thanks,

Radia

---

From: Tony Li <[email-masked]>
Date: Fri, 2 Oct 1998 17:19:41 -0700 (PDT)

|  1) is there a more recent specification of IS-IS than
|  the infinitely old RFC 1142?

Not that I know of.

|  2) does IS-IS officially support arbitrarily levels
|  of routing hierarchy? Do any implementations
|  support it?

No, and no.

|  ***********
|  skip the following if the 2nd question was self-explanatory.
|  
|  There was once an internet draft about how
|  "level 2" IS-IS could actually be arbitrarily many
|  levels of hierarchy. Just draw a circle, configure
|  the boundary routers with summary prefixes for the
|  address inside, and have a router attached to two
|  circles pass prefixes from one to the other.
|  This required no protocol changes to IS-IS, it
|  just required implementations capable of running
|  multiple instances of the routing protocol.
|  
|  NLSP (which is just IPX-specific IS-IS) specified
|  this behavior. The IS-IS internet draft describing
|  how to do it expired many years ago.
|  If I remember correctly, Cisco's implementation already
|  did multiple instances, and so it could do arbitrarily
|  many levels of hierarchy, whereas some other vendors'
|  implementations (like Novell) couldn't.
|  But it was only the border routers that needed this
|  capability.
|  
|  The question is: what is the current official position of
|  IS-IS on hierarchy levels?

I don't believe that there is one.

While one could conceptually do it all with L2, it turns out to be quite
trivial to define L3 (or 4, or 5, ...) and define the necessary LSP
numbers.  The benefits of the additional numbers would be clarity, plus no
need to support multiple instances.

Tony

---

From: Henk Smit <[email-masked]>
Date: Mon, 5 Oct 1998 11:27:13 +0200 (MET DST)

> This required no protocol changes to IS-IS,

  We need some extensions to the spec.
 We need to define more packet-types. Seems like the
 packet-type field is 5 bits, so that would support 8 levels
 of hierachy, with 4 packet types per level. And there are
 3 more reserved bits if we want more packet types.
 The only problem I see is with the "IS type" field in the LSP,
 which has only 2 bits. That field needs a little redefinition.
  We also need more MAC multicast addresses.
  If we follow 10589, some people might also want to limit the
 types of TLVs allowed at a particular level. If it was up to
 me, I would allow all types of TLVs at all levels.

> it

  That view is totally implementation dependent.

> this behavior.

  I wish NLSP was just IPX-specific IS-IS. :-(  It is not.

  And the specs I've seen only talk about level-1. Even the
 wishfull thinking in paragraph 2.8 in the NLSP spec doesn't
 talk about levels higher than 2.

> The IS-IS internet draft describing
> did multiple instances,

  No.

> and so it could do arbitrarily many levels of hierarchy,

  No.

> whereas some other vendors'
> s: what is the current official position of

  Why do you want to define multiple level of hierarchy ?
 Just because it would "cool" to do it ? Or do you know
 of any (big) customers that really need it ?

    Kind regards,

         Henk.

---

From: Antoni Przygienda <[email-masked]>
Date: Mon, 05 Oct 1998 11:14:42 -0400

>  me, I would allow all types of TLVs at all levels.

I believe Radia's proposal  would work well (I saw this kind of solution
deployed with other link-state protocols).  What you write could be made
"compatible" with 10589 although probably more "technically convoluted"
;-). E.g. the problem with L1/L2 we could solve by introducing a novel
TLV in the hellos that would occur when L2 is set and indicate levels of
hierarchy one is willing to participate in [I may get a spanking here
but it would be equivalent somehow to the hierarchy TLV in PNNI hellos
;-)] and so on ...

I am not sure the tradeoff in inherently extending the protocol with the
knowledge of multiple levels of hierarchy is worth the effort vs.
complexity necessary (except, as you say, being a cool thing to work
on). The  advantages I see are (1) given you allow lower layer nodes to
see some condensed view of higher levels and introduce partial source
routing, a better support for some kind of QoS  or (2) globally optimal
routing by forwarding to not just the "closest" gateway in the next
layer but to the "best" one globally.

>  of any (big) customers that really need it ?

THIS IS the most important question, of course. ISPs input welcome and
awaited here. From my little pigeon-hole, I saw that they were unhappy
with the fact that the routing in a 2 layer hierarchy is non-optimal and
that prevents them from runnning multi-level at all so far ... So maybe
the more realistic problem to work on in this area would be to optimize
the L1/L2 routing globally first.

        thanks

        --- tony

---

From: Tony Li <[email-masked]>
Date: Mon, 5 Oct 1998 12:20:53 -0700 (PDT)

|  >   Why do you want to define multiple level of hierarchy ?
|  >  Just because it would "cool" to do it ? Or do you know
|  >  of any (big) customers that really need it ?
|  
|  THIS IS the most important question, of course. ISPs input welcome and
|  awaited here. From my little pigeon-hole, I saw that they were unhappy
|  with the fact that the routing in a 2 layer hierarchy is non-optimal and
|  that prevents them from runnning multi-level at all so far ... So maybe
|  the more realistic problem to work on in this area would be to optimize
|  the L1/L2 routing globally first.

There are several big customers that are thinking of moving to using 2
layer hierarchy.  It would behoove us to stay one step ahead of them.  ;-)

In addition, there are multiple ways of attacking the optimality problem.
One interesting alternative is to do level-skipping when performing prefix
aggregation.  In level-skipping, L1 prefixes and not aggregated when
injected into L2.  Instead, they are only abstracted when injected into
L3.  Thus it helps to have an L3 to inject into.

The result of level-skipping is that you extend the abstraction action
boundary and thus decrease the amount of sub-optimality introduced by the
abstraction mechanisms.  One can see that today's suboptimality occurs
because the abstraction action boundary and the abstraction naming boundary
coincide, with a resultant loss of information being most critical
immediately outside said boundary.  By extending the abstraction action
boundary, we can hope to encompass more of the relevant topology, thereby
decreasing the amount of sub-optimality in the routing.

Of course, there is no true technology that will yield optimal routing
other than a completely flat system, and we've also seen (from traffic
engineering work) that optimal routing is not what's truly desired anyway.

Tony

---

From: Antoni Przygienda <[email-masked]>
Date: Mon, 05 Oct 1998 18:05:59 -0400

> decreasing the amount of sub-optimality in the routing.

ouch, lost some terminology here, what is abstraction action boundary
(that's where you sumamrize & supress components I guess) and what is
abstraction naming boundary then ? Naming is quite a different thing
from addressing normally, isn't it ?And what is said boundary ?  Did I
forget to read some fundamental RFC ?

> engineering work) that optimal routing is not what's truly desired

that's true but we could be better than "go to the closest L2", couldn't
we. The simplest solution that comes to my mind is to inject from every
L2 gateway the learned L2 prefixes with their distance being prefix
distance + distance through L2 domain ... That way L1 systems could
route to the optimal L2 per prefix. That may be equivalent to what you
call "shifting the abstraction action boundary from the abstraction
naming boundary" ;-)

        thanks

        --- tony

---

From: Tony Li <[email-masked]>
Date: Mon, 5 Oct 1998 15:28:38 -0700 (PDT)

|  > The result of level-skipping is that you extend the abstraction action
|  >
|  > boundary and thus decrease the amount of sub-optimality introduced by
|  > the
|  > abstraction mechanisms.  One can see that today's suboptimality occurs
|  >
|  > because the abstraction action boundary and the abstraction naming
|  > boundary
|  > coincide, with a resultant loss of information being most critical
|  > immediately outside said boundary.  By extending the abstraction
|  > action
|  > boundary, we can hope to encompass more of the relevant topology,
|  > thereby
|  > decreasing the amount of sub-optimality in the routing.
|  
|  ouch, lost some terminology here, what is abstraction action boundary
|  (that's where you sumamrize & supress components I guess) and what is
|  abstraction naming boundary then ? Naming is quite a different thing
|  from addressing normally, isn't it ?And what is said boundary ?  Did I
|  forget to read some fundamental RFC ?

No, you must have missed out on some Noel-speak.  Easily remedied:

The abstraction that we're forming is an IPv4 prefix that describes all
address space within a given subset of the topology.  The border of this
subset is the abstraction naming boundary.

The abstraction action boundary is where we actually stop advertising more
specific prefixes and advertise the abstraction.

|  > Of course, there is no true technology that will yield optimal routing
|  >
|  > other than a completely flat system, and we've also seen (from traffic
|  >
|  > engineering work) that optimal routing is not what's truly desired
|  > anyway.
|  
|  that's true but we could be better than "go to the closest L2", couldn't
|  we. The simplest solution that comes to my mind is to inject from every
|  L2 gateway the learned L2 prefixes with their distance being prefix
|  distance + distance through L2 domain ... That way L1 systems could
|  route to the optimal L2 per prefix. That may be equivalent to what you
|  call "shifting the abstraction action boundary from the abstraction
|  naming boundary" ;-)

Yes.  By effectively advertising only default into L1, IS-IS basically
dictates how abstraction happens.  As you can see, this is not necessarily
optimal.  Advertising further prefixes into L1 improves this, at the cost
of more information in L1.  

One might also decide that if one is not aggregating all of L1 when
injecting into L2 that one might want to perform this aggregation when
injecting into a lower level L1.  

For example, suppose that one L1 area has prefix A and another L1 area has
prefix B.  We carry around all longer prefixes of A both within A and
within L2.  But when injecting into B, we would only inject the aggregate
A.

Tony

---

From: Antoni Przygienda <[email-masked]>
Date: Mon, 05 Oct 1998 18:55:07 -0400

> specific prefixes and advertise the abstraction.

thanks for definition of terms, the "naming" still confuses the hell out
of me ;-)

> within L2.  But when injecting into B, we would only inject the

yes, that sounds however not like the most intelligent thing to do
unless you are having overlapping or same aggregates being advertised by
two L2 routers and one is lying ;-) since it cannot cover some more
specific routes supernetted by the aggregate. That would force the
advertised components to be routed through a specific L2 router I guess.

OK, so to bring up the general question back up: why would we need more
than 2 levels again having such a mechanism if we're not concerned about
partial source-route QoS routing ? OSPF is pretty much doing 300*300
routers with the 2 levels and good implementations and I so far didn't
hear of anyone hitting that ... The stuff Radia's proposing is from
previous experience not all that easy (unless you keep strict star
structure) to deploy as it seems to sound.

            thank you

        --- tony

---

From: Tony Li <[email-masked]>
Date: Mon, 5 Oct 1998 16:44:38 -0700 (PDT)

|  yes, that sounds however not like the most intelligent thing to do
|  unless you are having overlapping or same aggregates being advertised by
|  two L2 routers and one is lying ;-) since it cannot cover some more
|  specific routes supernetted by the aggregate. That would force the
|  advertised components to be routed through a specific L2 router I guess.

There's nothing here that architecturally prevents someone from injecting
more specifics from A into B.  That just has obvious scalability concerns
and so is probably not the recommended path.

|  OK, so to bring up the general question back up: why would we need more
|  than 2 levels again having such a mechanism if we're not concerned about
|  partial source-route QoS routing ? OSPF is pretty much doing 300*300
|  routers with the 2 levels and good implementations and I so far didn't
|  hear of anyone hitting that ... The stuff Radia's proposing is from
|  previous experience not all that easy (unless you keep strict star
|  structure) to deploy as it seems to sound.

a) 300*300 routers is not enough routers.  ;-)

b) Optimality gives us pressure to expand the distribution of information.

c) Scalability requires that we continue to constrain the distribution of
information.

d) The result is that we need more granularity in our abstraction
mechanisms and thus need more layers of hierarchy.

Tony

---

From: Mike Truskowski <[email-masked]>
Date: Tue, 6 Oct 1998 07:01:21 -0700 (PDT)

Tony,
Are you saying that you only inject the shorter prefix?...
Looks like this could create longer forwarding paths if
you don't build on a heirarchy.    

Are you assuming IP addressing or OSI & IP?

Mike

---

From: Tony Li <[email-masked]>
Date: Tue, 6 Oct 1998 10:54:06 -0700 (PDT)

|  Are you saying that you only inject the shorter prefix?...

Yes, of course.

|  Looks like this could create longer forwarding paths if
|  you don't build on a heirarchy.    

I don't follow.  Any suboptimality is frequently reflected as a longer
forwarding path.  That's true of whatever protocol performs the aggregation.

|  Are you assuming IP addressing or OSI & IP?

Just IP.  That OSI stuff is only a genetic contributor.  ;-)

Tony