Representation, Configuration, and Route Information
			    Distribution in Nimrod

				Ram Ramanathan
				December, 1993



In this write-up, I have put down my thoughts on representation, configuration
and route information distribution. Much of this, especially representation,
is what I believe to be status quo (from our discussions), expressed perhaps in
a different manner and in slightly more detail. The sections on configuration
and route information distribution may be fait accompli to you. 

Please quip if you don't understand something (it is probably because
of sloppy writing) or if you have differences of opinions. Hopefully,
using the latter, we can converge to a common viewpoint on things before we
start writing the Architectural document. 

Representation is discussed in section 1, mainly as a basis for discussing
section 2 on configuration and route information distribution. Each section
has a "theme" that summarizes ideas of the section for those of you that
don't have time to go through the entire rant.

1. Representational Entities

1.1. Theme 

There are four entities that are used for representing  topology in
Nimrod. These are : cluster, boundary point, intercluster link, 
intracluster link.

A "cluster" is a Nimrod addressable entity. Data flows into and out of
a cluster by means of "intercluster links" incident to that cluster at
"boundary points". An intercluster link connects two boundary points
in distinct clusters. Characteristics of a cluster are expressed by 
"intracluster links" between a pair of boundary points belonging to
the same cluster.

All of these entities have "locators" associated with them. An entity's
locator is composed using labels and/or locators of other entities.

1.2. Elaboration 

A set of clusters and the links between them may be aggregated to
form a cluster. The former clusters are then said to be "contained"
within the latter cluster. Recursive aggregation of clusters in this
manner results in a (cluster) "hierarchy". 

[Remarks : Note that no mention has been made of any "basic" entities.
There is no basic entity other than a cluster. Within a cluster, a 
"local mechanism" determines transfer of data entering the cluster to
physical entities within the cluster. These entities may be whatever
you want - interfaces, routers, networks, processes and so on. From
Nimrod's viewpoint, its job is to get it to the destination cluster
indicated, it does not need to worry about the basic entities within the
cluster.

Note also that there is no representational entity "node". In a sense,
the boundary points will behave as "nodes" and the links as "edges/arcs"
for a route calculation. However, I see no reason to impose strict graph 
theoretical notions or structures and have to define notions such as
"what is a node" if unnecessary. Maps will be represented in terms of
the abovementioned basic representational entities and routes calculated
by doing a search on them (you don't need "traditional" graphs for a route).]

Very informally, clusters represent network elements that are to be treated
somewhat uniformly. Intercluster links represent connectivity between 
clusters and intracluster links represent the transit characteristics
of that cluster. Thus, they are quite different things and have different
locator construction schemes (explained later). Note that if there is
an intercluster link L between clusters A and B and both A and B are contained
within cluster C, then L is *not* an intracluster link for C. Intracluster
links always run between boundary points of the same cluster. [Remark : In
a sense, the names "intra" and "inter" are misleading and should probably
be changed, although I cannot think of anything better at the moment].

Boundary points effect an association between intercluster and intracluster
links. The entire transit characteristics of the cluster are expressed in
the individual characteristics of the intracluster links between each pair
of boundary points.

[Remarks : Here we have the famous N^2 problem, ie, the possibility of
the number of intracluster links growing as square of the boundary points.
Curtailing this is of course necessary, but that is the problem of 
"abstraction". Abstraction takes a representation and converts it into
another, less space consuming one. Any abstraction scheme desired may be
used; however, the abstraction must be expressed in a "language" that 
everybody understands. One such "language", a simple one similar to the
one used in IDPR, is given in section 2.2.1]

All of the entities discussed above, namely, clusters, boundary points,
intercluster links and intracluster links are associated with a unique
"locator" that identifies the location of the entity within a particular
cluster hierarchy.

The basic constituent of a locator is a "label". The locator for an
entity, typically, combines in some manner, labels or other locators.
The rules for forming the locators could be as follows :

Cluster ::- l1.l2.l3...lk, such that
            l1 is U the universal cluster.
            lk is the label assigned to the concerned cluster and
            for all n from 1 to k, ln is contained in l(n-1).

Boundary point :- <cluster locator>,[<label>]
            The <label> is unique for that cluster. If there is no <label>
            then the boundary point is a synonym for the cluster. That is,
            all intracluster links have the same attributes and all 
            intercluster links are incident to this single boundary point
            for the cluster (see remarks end of this section).

Intercluster link :- (<locator of BP 1> -> <locator of BP 2>),<label>
            The label is unique for that pair of BPs

Intracluster 
        link :- <cluster locator>*(<label of BP 1> -> <label of BP 2>),<label>
            The <cluster locator> is the locator of the cluster in which
            the intracluster link resides. <label> is unique for that pair
            of BPs and may be omitted if there is only one link between BP1 and
            BP2.

All of the above entities have "attributes" associated with them, describing
their capabilities (offered services), access restrictions etc. These are
addressed in the next section.

[Remarks : While the attributes for inter and intra cluster links need no
justification, you may wonder what the attributes mean for a cluster and
a boundary point. Actually, there are no explicit attributes for a cluster-
its attributes are implicit in the attributes of the intracluster links.
However, it does make sense to talk about the cluster attributes, say, as
a "minimum" service provided from any point to any point over the cluster.
As far as the boundary point is concerned, it is not *always* associated
with an attribute, only when the cluster has only one boundary point. 
This represents the situation when the cluster offers uniform services and
access restrictions over all of its entry and exit points - in such a case
we attach the attributes to the single boundary point to which all of the
intercluster links are incident. As mentioned earlier, the boundary point is
just a different name for a cluster in this case].


2. Personality of a Nimrod "process"

2.1. Theme

Nimrod is a distributed system that transfers data from one entity to
another. The system is implemented by a Nimrod "process" running at
a Nimrod "site". How does everything look from the point of view of the
process? What are its input and output parameters and what is the distri-
-buted algorithm?

Describing the above would be to nearly give the protocol specification.
I am only going to describe here my thoughts on two issues in this context,
and that too, very briefly : configuration and routing information 
dissemination. 

The configuration for a Nimrod process consists of an entry for each 
cluster that the process represents. For each cluster, it contains, amongst
other things, the cluster locator, locators of the boundary points,
abstracted intracluster links, abstracted intercluster links. When the
process represents and is configured for several (typically nested) clusters,
the process has a "split personality".

On the receipt of routing information, the process determines which
"personality" it should use by looking at the contents of the information.
Without explicitly using "level numbers", but by comparing relevant
locator strings, the process assures that the dissemination of routing 
info is confined to the appropriate level. This is not complicated, but I was
not convinced before working it out that you can do this without using
level numbers. It seems you can - details are in section 2.2.2.

[Remarks : Every work on hierarchical networks that I have seen uses 
level numbers - we don't. I am still a bit worried that there may be
other places (route generation?) where level numbers are a must. On the
other hand if we can pull this off without using level numbers, it would
almost certainly be new and glorious].

2.2. Elaboration

2.2.1. Configuration

To begin, the configuration of a process tells it which clusters it
"represents". A process is said to represent a cluster if if is capable
of processing information intended for that cluster. A process may 
represent many clusters; many processes may represent a cluster, say,
at different sites.

For each cluster that the process represents, the cluster locator would
look something like below :

Configuration entry for cluster X represented by this process :
      Locator of X;
      for each boundary point(BP) in X
         Locator of the BP;
         Locators of the intercluster links incident to that BP;
         (Abstracted) attributes of each intercluster link;
         Largest common denominator of attributes of intracluster links
         incident to this BP;
      Abstracted attributes of intracluster links;

The largest common denominator is the set of attributes and attribute values
that are true for all of the intracluster links. For instance if there are
3 intracluster links A, B, C with bandwidths 100, 200 and 300 and delays
10, 20 and 30, the LCD of A, B, C is (bw=100, delay=30). This helps
quickly calculate not-so-picky route requests.

Any abstraction scheme may be applied to get the abstracted attributes of
intracluster links. One simple scheme is to group links of same/nearly the
same characteristics and access restrictions. If most of the links have
the same characteristics and there are a few exceptions, only the exceptions
need be specified (as in group1-attr1, group2-attr2, rest-attr3).

Abstracted attributes of intracluster links :
      1st group of links
        link characteristics (delay, bandwidth etc)., access restrictions..
      2nd group of links
        link characteristics (delay, bandwidth etc)., access restrictions..
      and so on.......
      [rest of the links]
        link characteristics (delay, bandwidth etc)., access restrictions..

The configuration of a cluster may be given to the process representing
the cluster completely manually (for instance, the network administrator
presents it with a configuration file), or may be deduced automatically
by the cluster using the intracluster link information of the clusters
contained within it and the intercluster information between those 
clusters, which, once again could themselves have been gotten automatically
or manually. It is envisioned that (the process for) a cluster A, after
gettting the requisite information from its children clusters would
run that information through some abstraction algorithm to arrive at
the intracluster link states for itself.

2.2.2. Routing Information Dissemination

Routing information, specifically, link state information must be
disseminated throughout the network so that Nimrod processes can 
construct the maps that are then used to calculate routes. We assume
that routing information is propagated in Nimrod in pretty much the
same way that it is done in other link state based protocols (IDPR,
OSPF etc.). In particular, a process sends information to its
"neighboring" processes, which in turn send it to *their* neighboring
processes and so on. 

In general then, a process receives information about link L1 and is faced
with the decision of whether or not to propagate that information over
a link L2. The question we address is : how does the process make that 
decision? Note that, in a sense, this depends upon the relative levels of
L1 and L2 - however, we have refrained from attaching level numbers to
the links and therefore, the decision must be based on other information.

Some definitions. A "prefix" of a cluster locator X is any non-null
substring of X, starting from the beginning. For instance if X = A.B.C.D,
then, A.B.C.D, A.B.C, A.B and A are all prefixes (but not, for instance,
B.C). The "scope" of a link L = (Z->Y) is the longest prefix common to
both Z and Y. Informally, the scope is the lowermost cluster that contains
the link in its entirety.

First we consider only cases when L1 and L2 are both intercluster links.

To decide whether or not to forward received information about L1 over L2, 
the process evaluates the scope of L1 and L2. Four cases are possible :

1) scope(L1) = scope(L2). In this case the information is sent over L2.
2) scope(L2) is a prefix of scope(L1). This means that L1 is too "low-level"
   for L2 to bother about. The information is not sent.
3) scope(L1) is a prefix of scope(L2). This is a sensitive case. L1 is too
   high a level for L2 to know, however, L2 may be on the path to another
   link L3 such that scope(L1) = scope(L3) and if so, we may have to
   propagate L1's information over L2.  
4) None of the above. Actually, this should never happen if all of the above
   are handled in the manner indicated. Nevertheless, the action is to
   *not* propagate.

Additional rules to handle cases when L1 or L2 can be intracluster links
are as follows :

- Information about intercluster link L = (Z->Y) is propagated over all 
  of the intracluster links of Z and Y.
- Information about intracluster link L = (bx->by) is propagated over all
  of the intercluster links incident on bx and by.

In the present of abstracted link information, such as a link group, the
above is only affected if the scopes of the links within the group differ.
This should not be the case in the kind of abstractions I am envisioning.

Example :

     A
      --------------------
      | B        C       |
      |  ---     ---     |
      |  | |____ | |     |
      |  | |     | |     |
      |  ---     ---     |
      --------*-----------
              |
    D --------*-----------
      |                  |
      |                  |
      |                  |
      |                  |
      |                  |
      -------------------

Consider L1= U.A.B -> U.A.C, L2= U.A -> U.D

scope(L1) = U.A, scope(L2) = U.

Since scope(L2) is a prefix of scope L1, rule #2 above applies and the
info about L1 is not transferred to D.