Subject: RE: Comments on draft-ip-optical-framework-00.txt

From: "J. Noel Chiappa" <[email-masked]>
Date: Fri, 31 Mar 2000 14:27:21 -0500

>> From: "Krishna Bala" <[email-masked]>

    >> the difference between the open model and the overlay is just that
    >> the overlay model typically suggests that there would be N^2
    >> connectivity (i.e., every router, for instance, is statically
    >> connected to every other).

I've been turning this remark over in my mind for several days, and I have
what I think is a mildly important recognition about the limits of *any*
interaction model.

I should start by saying I've been thinking about this whole problem of
"what topological model of the underlying network do we present to the
higher layer" in the context of a more advanced routing architecture.
(In my case, I chose something which looks vaguely like Nimrod
[http://ana-3.lcs.mit.edu/~jnc/nimrod/docs.html], of course! :-).

I know this may sound sort of useless, thinking about the problem using
tools we don't currently have, but I would argue to the contrary. My
reasoning is that I now think this problem has some *fundamental*
limitations, and it's easier to see those limitations if you take away the
artificial constraints imposed by our current less-than-ideal routing tools.

Anyway, my thoughts were prompted in part by a later comment of Curtis':

    > [Note: networks built using the overlay model need not provide a
    > full mesh contrary to misinformation provided on this mailing
    > list.  Today ATM PVC based IP backbones are often not built as
    > full mesh networks to reduce the nuber of routing adjacencies.]

This comment reminded me that there's a general problem whenever you try and
"abstract" a piece of the network topology. What I mean by "astract" is the
following process:

- take a graph of the the physical network;
- replace any part of that graph (i.e. a section of the graph bounded by
  a closed line, such that the line only cuts arcs - don't argue with
  this constraint for now, just assume it, OK? :-) with an alternative
  (simpler?) graph, one which has the same set of outgoing arcs crossing
  the boundary, going to the same set of nodes outside the boundary
- repeat the process (i.e. recurse)

If you aren't comfortable with this, try drawing some pictures. (Sorry, I'm
to lazy to do so for you!)

There's a reason I defined my second step the way I did, instead of simply
saying "replace any group of nodes bounded by closed line with a single
node" (which I'll call "non-virtual abstraction"). The process I defined
allows one to create arbitrary "virtual" representations of a piece of
topology one is trying to abstract.

Here are some examples of this 'vitualization' process. Let's assume I'm
trying to tackle the situation Curtis alluded to: I have an ATM network, and
I'm trying to model the connectivity of the routers attached to that network
(represented in the graph by nodes which have arcs crossing the circle drawn
around the set of nodes which represent the ATM network elements). I have a
vast number of options for doing so.

For one, I could model the routers as all being connected to a single giant
node in the center, a node which replaces the entire ATM mesh. The problem
with this is that if you're trying to put some reasonably correct metrics
(or, more generally, attributes) on the arcs that connect each router node
to the center node, there's no way to get completely accurate results; the
topology is too simplified.

For another, you could do a full N^2 model; in this you can accurately model
the attributes of each indidivual router-router "connection" (it's actually a
"current path"). However, this has two drawbacks, one obvious, one subtle. The
obvious one is that it's N^2. The subtle one has to do with using alternate
paths - you get an even bigger combinatorial explosion if you try and start
representing alternative paths. (Note also that there's no way to produce this
representation using non-virtual abstraction.)

Then you could do what Curtis alluded to - something less than full N^2.
This has the limitation that paths through the fabric between routers X and
Y may actually exist - but such a path is not represented in our
"virtualization" of the ATM network, and the only way to get from X to Y is
to find some router Q which *does* show a pair of virtual links, one to X,
and one to Y, and take an "extra hop" through it.

You can go on for a while, trying different things, and you soon discover a
simple truth: in basically all real networks, there's *no* virtual
representation of a part of the topology graph which is both i) simpler
than the full representation, and ii) accurately and fully describes the
connectivity through that part of the graph.

In other words, the real graph is generally the most compact representation of
the connectivity, for path selection purposes.

Now, here's where the going gets tough, and the tough get going. Obviously, in
a real network, everyone can't have a full graph of the network. So you *have*
to produce simplified representations - and accept that some paths are going
to be non-optimal. In other words, you have to trade-off two kinds of
overhead: routing overhead (i.e. the cost handing around routing data), and
non-optimal paths.

In the optical case, we have an *additional* constraint, which is that even
if people *outside* the optical part *did* have a full map, they wouldn't
necessarily be able to use it - because finding optical paths is a process
that has unusual constraints.

So, again, you're forced to produce a model of the connectivity across that
part of the connectivity graph; i.e. select a set of paths, and advertise
that set of paths as the connectivity graph which is a virtual
representation of the connectivity of that part of the network. And, as
we've seen, there are fundamental limitations on how well any such virtual
representation can work.

So, where does this leave us, here in the real world, with the real tools at
our disposal - tools which unfortunately don't allow us to create any virtual
representation, but just a few selected ones?

Well, the main conclusion is that if you're producing non-optimal results,
it's not necessarily because your tools are bad - it's an impossible problem
even with the best possible tools.

I will also stick to my earlier conclusion: the problem will be easier to
tackle in a system which uses a uniform routing system at both the local
and higher layers. Whatever information flow you *do* decide to do (i.e.
whatever virtual representation of the local topology you do decide to
propogate out to the higher layer), you will have more flexibility in doing
so if the two are using the same routing system.

	Noel

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 31 Mar 2000 16:31:59 -0500

Noel,

Your lengthy message was trimmed before replying.

In message <[email-masked]>, "J. Noel Chiappa" writes
> and one to Y, and take an "extra hop" through it.

In optical networks there is a good reason to do this.  You may have
very little traffic from A to C and not that much from A to B and B to
C either.  If you only set up a path from A to B and B to C, you can
still get from A to C without congestion, and you use one less lambda.

In IP over ATM if each POP i has two routers for redundancy, called
R_{i1} and R_{i2}, then you need to connect R_{in} and R_{jn} for all
i!=j and for n={1,2} and you will also want to connect R_{i1} to
R_{i2}.  This provides redundancy for a network with N POPs without
creating 2N(2N-1) adjacencies.

> connectivity through that part of the graph.

This is not a problem.

> even with the best possible tools.

Depends on your view of optimal.  If you are optimizing your use of
the available lambdas, then not creating a path from A to C in the
above example is optimal because the extra hop cost didn't cost
anything (you needed to have those router interfaces at A-B and B-C)
and saved a lambda that did cost something (you didn't burn another
lambda and didn't neeed an extra pair of router interfaces at A and
C).  Whether this optimization is best done offline is still an open
issue.

> so if the two are using the same routing system.

Another way of thinking of this is that bypassing LSRs with optical
paths and not doing the electrical routing will always be making
slightly less efficient use of the lambdas that it is using than if
the lambdas were terminated and routed.  OTOH if lambdas are available
and cheaper to use than additional routing capacity, then from a
dollar cost standpoint, the network would be better off bypassing some
of the routers with PSC tunnels that are optically switched.

> 	Noel

The point of my earlier message was that we need a signaling mechanism
that does not constrain us down the road and some of the internet
drafts seem to allow that.  For example:

  An offline NMS can configure explicit paths on the edge LSR and the
  edge LSR can set up an LSP and use it as a PSC through the optical
  core signaling the explicit path.  This gives us a static overlay
  that is signaled from the edge.  This can also be accomplished by
  configuring each network element separately (as was done in the old
  days with PVCs) but constrains us to this approach only.

  The edge LSR can signal an explicit path for an LSP with one strict
  hop to the immediate optical device and a loose hop to the far end.
  The LSP can be used as a PSC.  This provides the signaled overlay
  (same functionality as the open model).

  If we get to the point where the peer model is feasible, the loose
  hop becomes a set of strict hops.

There is still plenty of work to be done to make the peer model work
given the optical network's characteristics but the signaling won't be
a restriction if it is designed to accomodate all three methods.
Additional information will have to be flooded later for the peer
method to work but the setup is not likely to need change.

Curtis