A fuzzy proposal


Mills@UDEL.EDU
Fri, 5 Jun 87 13:58:14 EDT


Folks,

This is a proposal for a modification to the data base used by the NIC and
other organizations which identifies hosts and gateways. The modification is
suggested by certain routing configurations that commonly occur in the NSFNET
community and also elsewhere. These configurations involve cases where the
internal structure of an autonomous system is to be hidden from outside the
system for various good reasons.

The issues involved are best raised by an example involving a gateway/host
called the fuzzball and used in the NSFNET Backbone system, as well in other
systems. First a few words on fuzzballs and routing. In order to minimize
consumption of network numbers and local-net addresses, a peculiar addressing
model is enjoyed by the fuzzies. Each one is assigned a "home address,"
usually on the local Ether, which represents its entity title in ISOspeak.
This address is unique, so that unambiguous routes can always be computed.

When two fuzzies are spliced together by a serial line, each sends the other a
hello message with its home address in the IP source-address field. The other
one saves this address and uses it to update its local-entity routing tables
and network-entity routing tables (if both are on different networks). Thus,
fuzzies automatically build routing tables for not only the local routes, but
routes to adjacent networks. Additional data in the hello message is used to
construct routes to other than adjacent networks.

In order to reduce consumption of net numbers and local-net addresses, two
fuzzies connected as above do not need to know their address (if any) on the
adjacent network. This avoids the "null net" problem sometimes encountered
when two gateways belonging to different autonomous systems are connected by a
point-to-point line. Nevertheless, if necessary for other reasons, fuzzy
addresses can be assigned with appropriate handcrafted entries in the routing
data base (this is in fact done sometimes to create a "tunnel" where a host
physically connected to one network is assigned an address on some other
network). However, this defeats a very desirable self-configuration
characteristic and considerably complicates configuration control and
management.

Following is an example scenario involving UMICHNET (35) and MACOMNET
(192.5.8). The 35.1.1.1 fuzzy is connected to the 192.5.8.6 fuzzy by a serial
line. To the 35.1.1.1 fuzzy its end of the line appears an extension of net
192.5.8 while, to the 192.5.8.6 fuzzy its end of the line appears an extension
of net 35; however, neither fuzzy knows or cares about its specific address on
the other network (in fact no such address is used). However, each fuzzy
determines from the source address of received hello messages the specific net
number and updates its tables accordingly.

                     +---------------+ ARPANET
                     |192.5.8.x |35.x.x.x |
+---------+ +----+----+ +----+----+ +----+----+
| net 35 | |35.1.1.1 | |192.5.8.6| |192.5.8.1|
| host | | umich1 | |swamprat | | macom1 |
+----+----+ +----+----+ +----+----+ +----+----+
     | | | |
=====O===============O==== =====O===============O=====
       net 35 Ether net 192.5.8 Ether

Although attractive in these aspects, the fuzzball scheme does create some
problems. For instance, it is not possible to determine an unambiguous return
route, since a fuzzy may not know its address on the previous network. Also,
it is not possible to produce an unambiguous interface list suitable for
recording in the NIC or similar data bases. In fact, it is not possible to
contact either the 35.1.1.1 or 192.5.8.6 fuzzies using addresses on their
respective adjacent nets, since such addresses do not exist.

Comes now a proposal to deal with this problem. Henceforth, gateways in this
embarrasing situation shall be assigned synthetic addresses in the form
<net>*, where * indicates unknown or unassigned. For example, the
fuzzies above would be recorded as

        GATEWAY : 35.1.1.1, 192.5.8.* : UMICH1
        GATEWAY : 192,5,8,6 35.*.*.* : SWAMPRAT .

It is possible in the case of subnets to indicate finer granularity by
replacing * fields with assigned numbers; however, the subnet mask can only be
inferred and then only if it corresponds to octet fields.

The above notation can also be used when two or more gateways are operated as
a single autonomous system and where the internal structure of that system is
to be hidden. For instance, assume the ARPANET gateway 192.5.8.1 above wishes
to hide the other two gateays. This could be done by

        GATEWAY : 10.0.0.111, 192.5.8.*, 35.*.*.* : MACOM1 .

The implication is that routing computations are to be done under the
assumption that MACOM1 has in fact direct interfaces to the nets listed and
that it will take responsibility for all traffic to those nets received at
10.0.0.111.

How might this proposal affect global routing schemes such as proposed for
the Dissimilar Gateway Protocol (DGP)? The DGP routing algorithm synthesizes
routes directly from interface lists in the form

                        <gate> <net1> <net2> ... ,

where <gate> is a unique gateway identifier and <net1>, etc., are the
interface addresses assigned to it. The algorithm constructs a path between
desginated endpoint addresses <source> and <destination> in the form

   <source> <gate1> <net1> <gate2> <net2> ... <gaten> <destination> .

The particular algorithm used is a variant of the Dijkstra (SPF) algorithm
modified for a hierarchical data base, but this is not important for the
present discussion. However, note that the Dijkstra algorithm (and many other
ones similar to it) operate by extending paths from a given node to each of
several possible successor nodes. Say the algorithm is currently extending
paths from <gate1>, for example. It then adds to the path ending in <gate1>
new edges for each interface address, which according to the proposal above
could involve an incompletely specified address.

In some following step the incompletely specified node will be found. When
extending the path from that node the set of interface lists will be searched
for interface addresses on the same network and for each one found the
associated gateway will be added to the path. There are two cases:

1. The interface address on the next hop is completely specified. In this case
   a complete source route can be constructed in the usual way.

3. The interface address on the next hop is not completely specified. A source
   route must then be constructed to the previous-hop gateway, which then
   has the responsibility to determine the remainder of the route.

Your advice and comment on this proposal will be appreciated.

Dave



This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:38:19 GMT