Mills@UDEL.EDU.UUCP (06/05/87)
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
hwb@MCR.UMICH.EDU (Hans-Werner Braun) (06/06/87)
Dave: Why don't you leave the *'s out, as they seem redundant. All you are asking for is to leave host parts out to allow for net and subnet connections. It's obvious without marking explicit *'s. In fact, may be addresses not fully qualified (like 192.5.8) should be followed by a bit mask, to allow for subnets. E.g.: GATEWAY : 35.1.1.4, (35.128 : 255.128.0.0) : MERIT-DIRECT GATEWAY : 35.1.1.4, (35.1.128 : 255.255.224.0) : CITI Another possibility would be to use zeroes instead: GATEWAY : 35.1.1.4, (35.128.0.0 : 255.128.0.0) : MERIT-DIRECT GATEWAY : 35.1.1.4, (35.1.128.0 : 255.255.224.0) : CITI Note that the Merit packet switching nodes allow for the same addressing flexibility Fuzzballs do. However due to some of the limitations you outlined we will soon be able to "let devices know (additionally) what address they should use." This is important for, e.g., ARPs if you have more then one Ethernet interface. -- Hans-Werner
Mills@UDEL.EDU.UUCP (06/06/87)
HW, Well, I like the idea of including bitmasks to indicate address ranges, but I thought that a bit radical to propose at this time. In fact, I have a whole bunch of really radical things to propose, all in good time. Meanwhile, I suggest using zeros instead of * might break something somewhere, like (old) local-net brodcasts. Dave
CERF@A.ISI.EDU (06/09/87)
I'm with Dave on zeroes - the syntax should be explicit about intended "don't cares" as in logic design (0, 1, X). Vint
braden@BRADEN.ISI.EDU.UUCP (06/19/87)
Dave Mills,
This is a delayed reply to your "fuzzy proposal" for a way to represent
in HOSTS.TXT the Fuzzballs and other gateways which follow the
gateway-half model. We too have been grappling with this problem, in the
process of gathering a database specifying the connectivity of NSFnet. We
have arrived at a scheme which differs from yours.
We think that your scheme does not make the topology readily
apparent. Consider your example:
GATEWAY : 35.1.1.1, 192.5.8.* : UMICH1
GATEWAY : 192.5.8.6, 35.*.*.* : SWAMPRAT
Now, it may be possible to infer from this pair of entries that UMICH1 is
connected to SWAMPRAT. One can construct more complex cases where this
is ambiguous. For example, suppose we have two parallel connections:
GATEWAY : 35.1.1.1, 192.5.8.* : UMICH1
GATEWAY : 192,5,8,6, 35.*.*.* : SWAMPRAT1
GATEWAY : 35.1.1.1, 192.5.8.* : UMICH2
GATEWAY : 192.5.8.6, 35.*.*.* : SWAMPRAT2
Which one is connected to which? Another example, with two serial
lines from UMICH1 to two different gateway-halves on 192.5.8, might
be:
GATEWAY : 35.1.1.1, 192.5.8.*, 192.5.8.* : UMICH1
GATEWAY : 192.5.8.6, 35.*.*.* : SWAMPRAT1
GATEWAY : 192.5.8.6, 35.*.*.* : SWAMPRAT2
We suggest that the primary purpose for the databases like the NIC
HOSTS.TXT is to show how things are connected together; derivation
of routing rules would be a secondary activity. Your scheme, which
is based on routing rules rather than actual connectivity, may
hide what we most want to be explicit.
The scheme which we adopted is to use symbolic interface addresses for
the un-numbered serial lines between gateway-halves. Specifically, we
chose names of the form:
<Network name>-<GWhalf 1>-<GWhalf 2>
between two gateway halves with names <GWhalf 1> and <GWhalf 2>. For
consistency, the two GWhalf names are always written in alphabetical
order. We believe, by the way, that for consistency every network ought
to have both a name and a number assigned, even if the number is never
explicitly used because the network is comprised of half gateways
connected with serial lines. In the absence of a network name, you
may think of the first component as an Autonomous System name.
For example, we might list your first example as:
GATEWAY: 35.1.1.1, SWAMP-SWAMPRAT-UMICH1 : UMICH1
GATEWAY: 192.5.8.6, SWAMP-SWAMPRAT-UMICH1 : SWAMPRAT
Suppose one tries to draw a network map based on your entries, without
doing the implied telescoping of entries; one ends up with a
set of two one-way connections between each network pair. For
example:
-------
------- |----------------------------------->( )
( ) -------- -------- ( net )
( net )<----| umich1 | |swamprat|---->(192.5.8)
( 35 ) -------- -------- ( )
( )<----------------------------------| -------
-------
Using our symbolic names, one gets directly the correct topology,
without any telescoping:
-------
( ) --------
( net 35)<---| umich1 |
( ) --------
------- | -------
|----> ( SWAMP ) <----| -------
-------- | ( )
--------- ( net )
| swamprat|---->(192.5.8)
--------- ( )
-------
In short, HOSTS.TXT is one of the main sources of information on network
configuration that is generally available, and we would like to see it
contain clear connectivity information on the fuzzballs and any other
gateway-halves.
By the way, your discussion of the use of the notation for hiding the
internal structure of an autonmous system should not be relevant to
databases such as HOSTS.TXT. We want this to contain as much information
as possible, not to hide information.
Neither scheme, yours or ours, seems quite right. Maybe we are solving
the wrong problem?
Bob Braden
Annette DeSchonMills@UDEL.EDU (06/19/87)
Bob and Annette, Thanks for your thoughtful reply. There are merits in your scheme that would indeed by appropriate in some cases; however, I have reservations. First, your suggestion on using synthetic meta-entities (!?) would be appropriate for the half-gateway model, where the halves are separated by a featureless transmission line or tunnel. I have no problem with that and would support your suggestion over mine when such is the case. My problem is the more general one. In addition to the cases I presented, consider one even more bizarre. In some of the NSFNET swamps there are multi-homed fuzzballs which respond to both local-net and ARPANET (!) addresses. It's all done with logical tunneling, which is possible because the routing algorithm can be configured for arbitrary address ranges. Thus, in point of real fact, udel1.udel.edu appears as directly connected to nets 128.4, 192.5.39 and 10. If I indicate the real truth HOSTS.TXT would be cluttered up with a lot of confusing and strange entries which, even if looking straightforward, would be actual lies. Returning to our example case with linkabit-gw and swamprat, which may be less controversial and move common than the above, I don't see how the connectivity could be accurately recorded with your scheme unless every intervening local-net node were recorded. In my last example I wanted to hide the internals of the swamp, but offered to take responsibility for the delivery of traffic to three nets, some of which are also connected via other gateways. You take exception on the basis that HOSTS.TXT should accurately reflect physical connectivity, not necessarily logical connectivity. I take the strongest objection. If in my autonomous system I refuse to publish every detail that, in my opinion, policy or prescriptive fiat is private and not to be revealed, then thus it verily be so. There is a whole lot of precedent in this policy, not only in the common-carrier community, but in many places in the Internet community as well. If the price to be paid to carry third-party traffic between two POPs is to reveal all the switches in between, then HOSTS.TXT is wholly inadequate and inappropriate. I submit there is room for both your scheme and mine. As you see, it is not possible for me to accurately reflect the connectivity of the cases I submit in either the existing HOSTS.TXT or your scheme. Dave