from the tuba list

Tom Kessler <Tom.Kessler@eng.sun.com> Fri, 21 May 1993 21:03 UTC

Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa14203; 21 May 93 17:03 EDT
Received: from CNRI.RESTON.VA.US by IETF.CNRI.Reston.VA.US id aa14195; 21 May 93 17:03 EDT
Received: from Sun.COM by CNRI.Reston.VA.US id aa18364; 21 May 93 17:03 EDT
Received: from Eng.Sun.COM (zigzag-bb.Corp.Sun.COM) by Sun.COM (4.1/SMI-4.1) id AA04357; Fri, 21 May 93 13:55:36 PDT
Received: from sunroof2.Eng.Sun.COM by Eng.Sun.COM (4.1/SMI-4.1) id AA21566; Fri, 21 May 93 13:55:37 PDT
Received: from bigriver.Eng.Sun.COM by sunroof2.Eng.Sun.COM (4.1/SMI-4.1) id AA07860; Fri, 21 May 93 13:58:54 PDT
Received: from hacketorium.Eng.Sun.COM by bigriver.Eng.Sun.COM (4.1/SMI-4.1) id AA28217; Fri, 21 May 93 13:55:18 PDT
Date: Fri, 21 May 93 13:55:18 PDT
Sender: ietf-archive-request@IETF.CNRI.Reston.VA.US
From: Tom Kessler <Tom.Kessler@eng.sun.com>
Message-Id: <9305212055.AA28217@bigriver.Eng.Sun.COM>
Received: by hacketorium.Eng.Sun.COM (5.0/SMI-SVR4) id AA17754; Fri, 21 May 93 13:55:23 PDT
To: ip-encaps@sunroof.eng.sun.com
Subject: from the tuba list
Content-Length: 11574

From: perlman@radia.enet.dec.com
To: tuba@lanl.gov
Apparently-To: tuba@lanl.gov
Subject: Thing I promised to write up about TUBA advantages.  Should this go anywhere other than the TUBA mailing list?  Or do people have suggestions to improve this memo? -- Radia
Date: Fri, 21 May 93 15:56:31 EDT

This is an attempt to write up the technical characteristics
of TUBA (CLNP).

A CLNP address looks like:

.literal
           < 14 bytes         6 bytes      1
    +---------------------+------------+-----+
    |    area address     |     ID     | SEL |
    +---------------------+------------+-----+

.end literal

A quick summary of the advantages:

1) autoconfiguration and autoacquisition of address, because of
inclusion of the 6 byte ID field.
2) very flexible addressing hierarchy with virtually unlimited
number of levels, because of the fact that level 2 routing
is based on routing to longest matching address prefix
3) the ability to embed a point of attachment address into the area
address, allowing routing for free (no protocol messages, no configuration)
across a backbone WAN such as a public network provider.

************************************************************************

Now I'll explain these features in detail.

1) 6 byte ID field:

The IEEE 6 byte address space is large enough so that every machine
manufactured can include a ROM with a globally unique ID.  It is not
necessary to be attached to an IEEE LAN in order to have an IEEE 6 byte ID. 
It is not difficult or expensive to acquire a block of IEEE addresses. 

Although 6 bytes is probably sufficient for giving every node a unique
address, it is not practical as a Network Layer address because there is no
hierarchy, i.e., no routing hints.  If the IEEE address were used as the
Network Layer address, then the routers would have to keep track of every
individual node in the entire world, and they could not afford the memory,
the CPU, or the bandwidth necessary to keep and exchange information
about every attached system.

The CLNP address includes a 6 byte ID field.  An end system which has a ROM
with a guaranteed globally unique IEEE address can find out all the rest of
its CLNP address from a neighbor router: "welcome to USA, Massachusetts,
Littleton". 

Furthermore, the fact that routers have an ID field makes it easier to
configure them, even though they cannot completely autoconfigure, since only
the area address portion of the CLNP address need be configured. 

Aside from the convenience of not having to configure addresses, either into
the end system or into some sort of boot server, in order for an end system
to participate in a network, there are additional features of having a
unique ID included as part of the address.  For instance, it guarantees that
an address will not be reused for a different node, which avoids confusion
with misdelivery when name to address caches become stale. 

2) Address prefix routing:  Address prefixes are equivalent to the IP notion
of masks with varying numbers of 1's, but since CLNP addresses are so much
longer than IP addresses, the number of levels of hierarchy that can be
obtained is much larger.  The idea behind address prefix routing is that,
with judicious use of the address space, large numbers of addresses can be
summarized with a prefix. For example, assume that CLNP addresses were ascii
strings and looked like postal addresses of the form
country|state|county|city|street|ID. The routers on the boundary of the US
might advertise that they can reach anything starting with "US", so they'd
advertise the address prefix "US*".  But in addition, to optimize routing
somewhat, the ones on the West coast might advertise "USCAL*", and the ones
on the east coast might advertise "USMA*". 

With address prefix routing it is not necessary to know how many octets of
the address are used for country, or state, or even have the same breakdowns
- -- some states might not bother with county as part of the address.  Some
countries might not be subdivided into states.  Routing does not have to
understand the structure of an address.  Routers just see addresses as a
pile of bits, and they route towards the longest pile of bits that match the
pile of bits which is the destination address of a packet.  They do not need
to know about AFIs, IDIs, and whether something is GOSIP format or something
else. 

All routing requires is for someone configuring routers on the boundary of
some region to make a decision about a sensible prefix to configure into the
routers for advertising reachable addresses within that region, or for
advertising as reachable addresses reachable outside that region. 

So routers on the boundary of a region are configured with a set of address
prefixes to advertise outside the region that will summarize the addresses
in the region.  A router will advertise a configured prefix provided that at
least one of the addresses reachable in the region matches the prefix.  In
addition it will advertise any addresses that are reachable that are not
included in any of the configured summaries.  In addition, for filtering
reasons, there might be configured prefixes for addresses that should not be
advertised outside the region. 

Similarly the boundary routers are configured with address prefixes
to summarize into the region, with similar rules.

Routing is to the longest matching address prefix.  There are efficient
algorithms (TRIE, binary search) for routing to the longest matching address
prefix (I know of one routing implementation that can route CLNP at 50,000
packets per second, for instance). 

3) embedded point of attachment addresses:  Consider the following, very
common topology.  There is some sort of backbone network, say an SMDS
network or an X.25 network.  Let's say some business, like a bank, has
thousands of branch offices, all interconnected via the backbone network. 
Each branch office has a little private Ethernet with perhaps 50 nodes on
it, or it might be simply a single node, say an ATM machine. 

A very convenient use of the CLNP address is to embed the SMDS address of
the router attached to the backbone network into the area address. In this
way it is not necessary to do any "address resolution" type protocol to find
the data link address on SMDS, since it is embedded in the CLNP address. 
Furthermore, it is not necessary to do any routing protocol to find the set
of CLNP addresses reachable from a particular router, since all the
addresses reachable from a particular router will be summarized with that
router's SMDS address. 

Think of the CLNP address as:

.literal

+----------------+--------------------+---------+----+-----+
| which provider | "telephone number" | loc-area| ID | SEL |
+----------------+--------------------+---------+----+-----+

.end literal

The router attached to SMDS is configured with the magic prefix for "which
provider" that defines the address as an SMDS address. Part of the driver
for SMDS knows how to extract an SMDS telephone number from the "telephone
number" part of the CLNP address. That router advertises into the other
routers in its branch office the "which provider" prefix it has been
configured with for the SMDS link.  So all addresses reachable on SMDS are
sent to that router, which merely extracts the SMDS number and sends the
packets.  In this way an unlimited number of branch offices are
interconnected with very minimal configuration and no protocol overhead. 

               +-------------------------+        +-----------+
               |                         |---R1---|private net|--A
               |    public network       |        +-----------+
               |                         |
               +-------------------------+
                         |           |
                         R2--B       C

For instance, assume that R1's "phone number" on the public net is
x.  R2's is y, and C's is z.  Let's assume that the "which provider"
part of the address is "57".  Then A's address would be 57.x.A, B's
address would be 57.y.B, and C's address would be 57.z.C.
Let's say A wants to talk to B.  At some point in the past, B would
have figured out its address, and registered itself in some naming
service.  A looks up B's name and gets the address 57.y.B. R1 will have
advertised to the level 2 routers in that private net that anything that
starts with 57 can be routed to it, since it's been configured with
the knowledge that anything starting with 57 can be routed over its
link to the public net.  So the packet is sent to R1.  When it gets to
R1, R1's driver for the public net knows how to extract a phone number
from the CLNP address.  It extracts "y", dials it, and by magic, the
packet is delivered, even though R1 and R2 did not explicitly know
about each other and never exchanged routing information with each other.

Now not all networks have such a simple topology.  A branch office might be
attached to SMDS with two routers, or it might be attached to SMDS and X.25.
Most of such cases can be provided for with a little additional
configuration, or the use of alias addresses. However, in some rare cases
things will be so complex that the CLNP feature of embedded subnet addresses
will not be helpful.  In those rare cases, you are no worse off than an
addressing scheme that did not provide this at all -- if 90% of your data
can be routed "for free", then the complex cases can be handled with the
appropriate combination of manual configuration and explicit exchange of
routing information via a routing protocol. 

Just to show there are reasonable solutions for complicated cases, we'll
discuss some complicated (and hopefully reasonably rare) cases.  Suppose
there is a private net hooked up to two backbone nets, say N1 and N2 via two
routers. One possibility is for all the nodes in that private net to have
two addresses.  When someone looks up an address in the name server they
will get back multiple addresses.  Then they can choose which address to
try. Presumably they'll try the address most similar to their own, or they
could simply try them in the order given. 

Another possibility is for the nodes to all take their address from the
point of attachment to one of the nets, say N1.  For example, let's assume
that R2's phone number on N2 is x.  Let's say that R1's address on N1 is y. 
So A's CLNP address will be N1.x.A. R3 can be configured to know that the
address prefix N1 is reachable on its link to N2 by dialing y. 
Alternatively, R3 can be configured with R2's address on N2 and they can
communicate via a routing protocol. 


                N1          N2--R3---private net---B
                  \        /
                   R1     R2 
                   |      |
                   privatenet
                     |
                     A

Yet another possibility is for N2 to route to CLNP addresses.  For instance,
N2 might be ATM.  It might have its own addressing structure, for instance
E.164.  You'd get routing for free if you use your E.164 address on ATM as
your CLNP address.  However, if the owner of R2 was willing to pay extra to
N2, R2 could advertise the prefix N1 into ATM.  Then ATM would be smart
enough to route packets for anything in N1 towards R2. 

How could R2 let N2 know which address prefixes R2 can reach?  It could
either be determined at subscription time, or there could be some sort of
ES-IS type protocol in which R2 could dynamically, as it discovered address
prefixes reachable in its private net, advertise them into N2. 


------- End of forwarded message -------