Subject: Re: Questions about hierarchy

From: Radia Perlman - Boston Center for Networking <[email-masked]>
Date: Mon, 5 Oct 1998 13:10:09 -0400 (EDT)

>>1) Why am I suggesting this?

Well, it is cool, but mostly I'm worried about being
correct for 2nd edition Interconnections. So I just
want to understand what's out there. My primary involvement
in IS-IS in the last 5 years was through NLSP.

>>2) Putting in fields to specify "this is level 6"

(Apologies in advance for giving a long technical description
for something that people may not be interested in, but in
case they are, read on...)

Let me explain. The reason the concept of "level 1" and
"level 2" wound up in IS-IS was because it was originally
designed for CLNP, where the address really has two types
of routing. The first deals with exact match on the ID field.
The 2nd deals with longest matching prefix on the rest of the
field. But "level 2 routing" is really a misnomer, because there
is no reason why it can't be multilevel.

For things like IP where all routing is based on longest prefix,
there's no reason to have level 1 routing at all.

Now, let's just look at longest prefix routing. There's no reason
to be aware of how many levels are beneath you. As a matter of
fact, that would be bad, because if someone below you made
an extra level of routing, you wouldn't want to have to change
your LSPs from level 6 into level 7. Plus you might have
one thing below you that was 4 levels, and another thing that
was 6 levels. Does that make you level 5 or level 7?

There's a way for it to work without making any protocol changes,
and it was documented in NLSP. Perhaps whoever was saying there
was only 1 level defined had the early version of the spec, where
that was the case.

The basic idea is that you partition the network into globs, where
a "glob" is the region through which an LSP is flooded. In order
to connect two globs, there has to be a router connected to both
globs. It is configured to know that is connected to "glob A" and
"glob B" (and possibly more globs), and which ports are associated
with which glob. If it gets an LSP from a port in glob A, it only
forwards it to other ports in glob A.

Now it has several disjoint link state databases. To pass information
from one glob to another, the router is configured to know what to
pass. The default might be "pass everything" or "pass nothing", but
it's better to configure summary addresses, as in "summarize glob B
with the summary 879*".

So if we imagine a top down kind of thing for a simple example, imagine
the top level that owns all the addresses. It has some next level guys.
To each of the "next level guys" it hands out addresses 4*, 792*, and
2* (the one with the longer prefix might be something expected to
have fewer members).
The guy with 4* has next level guys and hands out blocks of addresses
413*, 414*, 42*, etc.

Back to the top level. There's a router R connected to the top level, and
to the thing that owns 4*. It is configured to know which ports are in
"glob foo", and which are in "glob bar", and that "foo" can be summarized
with "*" and "bar" can be summarized with "4*". So R generates an LSP
into bar summarize foo, saying it can reach "*", and R generates an LSP
into foo summarizing bar, saying it can reach "4*".

This can keep going down as many levels as anyone might want. Whoever
had prefix 792381* can create new levels 7923811*, 7923812*, etc.,
without disrupting upper levels.

********
Now for further flexibility, there's no reason why you can't interconnect
things that aren't strict child/parent. You could interconnect glob 798*
and glob 239*, perhaps because two groups way down in two companies decide
they need a high bandwidth link to facilitate a joint project. But they
don't want the link used for anyone else. The way to
accomplish that is to have the router connecting 798* and 239* configured,
not just with the address summaries for the two globs, but with an
extra parameter "glob-hops", which indicates how many times it is legal
to learn about that summary and pass it on. The "glob-hops" would be
sent in the LSP along with the summary. So R would advertise into 798* that
it could read 239* with "glob-hops=0" meaning "don't pass this information
along to other globs.

**********
The result is that you can have as many levels of hierarchy as you want,
and you don't need to know how many there are. You can interconnect
things however you want. You don't need to force "level 3" to connect
to "level 3" or to have to go way up in the hierarchy and down again to
connect two low-level globs.

I think this is very simple implementation-wise, assuming that your
router can implement different instances of the routing protocol (which
I'd think it ought to be able to do). The down-side is that when
summaries go away, there is distance-vector-like counting-to-infinity
behavior (which can be ameliorated with "glob-hops") and in most
cases wouldn't be an issue because the topology would mostly be
a tree.

Radia