Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
A PROPOSAL FOR ADDRESSING AND ROUTING IN THE INTERNET
David D. Clark
Laboratory for Computer Science
Massachusetts Institute of Technology
Danny Cohen
USC/Information Sciences Institute
1. Introduction
Within the internet, there is a need for both addressing and routing
information as part of every packet. Using the distinction articulated by
John Shoch (1), we take the address of a packet to be where the packet is
destined, and the route, the specification of how the packet will get there.
Currently, an internet header contains only an address, and the route is
derived implicitly from that address. That addressing/routing strategy is
quite suitable given the current internet topology, but two problems may arise
as the internet continues to grow. First, unless the internet experiment is
truncated artificially, it can be expected to continue, as has the ARPANET,
for some period of time, in which case the number of networks involved may
grow to exceed the size of the field allocated to number them. Second, as the
topology grows more complex, it may not always be possible to deduce the
desired or effective route from the address. This proposal attempts to
address those two problems.
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
2. Addressing of Networks
The current internet header has space to name 256 networks. The
assumption, at least for the time being, is that any network entering the
internet will be assigned one of these numbers. While it is not likely that a
great number of large nets, such as the ARPANET, will join the internet, the
trend toward local area networking suggests that a very large number of small
networks can be expected in the internet in the not too distant future. We
should thus begin to prepare for the day when there are more than 256 networks
participating in the internet.
To cope with this problem, we propose that the top level entity named in
an internet address not be a single network, but, optionally, an aggregate of
networks which we will refer to as a region. Thus, an address now begins with
a region number, perhaps followed by a network number, in turn followed by
network dependent fields. Large networks, such as the ARPANET, will
presumably continue to be a region unto themselves. In fact, all of the
currently existing networks in the internet can be viewed as regions, which
means that no reimplementation is required if the concept of regions is
accepted. However, in the future, as more and more nets enter the internet,
we can, at our discression, lump various networks together into regions. Put
another way, a network can only join the internet by first joining a region.
In fact, the concept of a region was always available to the internet,
although in an informal manner. The structure of a network address was
unspecified except that it began with a fixed size field naming the network.
It was always permissible to use the component of the internet address next
after the network field to identify a subnet of the named network. Making
more explicit this hierarchy of regions and networks is important because, as
2
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
we discussed above, the address is used not only as an address but as a basis
for deriving a default route. We must thus consider how, using the addressing
structure of regions and nets within regions, the address can be used to
generate an effective and unambiguous route.
3. Default Routing
Currently, every gateway in the internet knows how to generate a route to
every network. If the number of networks grows substantially above 100 or
200, the gateways can no longer be expected to understand this much
information. One of the major purposes of the region concept is to control
the amount of information which every gateway must know. This scheme would
imply that an arbitrary gateway now only need to know how to reach every
region, but need not be concerned with routing to the individual network
within a distant region. Only for gateways connected to or completely inside
a particular region would be necessary to understand how to route packets to
all of the networks within the region.
Let us consider an example of how these regions might be used. There are
already two local networks at M.I.T., with more on the way. These might quite
properly be considered as one region. That would imply that a gateway located
in England need not be concerned with the internal structure of the local
networks at M.I.T. If M.I.T. were one region, such a gateway would merely
need to know how to reach M.I.T. Only when the packet has reached a gateway
connecting to one of the nets at M.I.T., would it be necessary to begin to
worry about how to reach the correct local network. It is possible that
deriving the route in this manner will not produce the optimum route; the
packet may arrive at a gateway to M.I.T. which leads to the wrong local
3
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
network, but presumably this is an acceptable inefficiency. (We will return
later to consider what might be done if it is not an acceptable inefficiency.)
More generally, this example suggests that the success of deriving routes from
addresses depends critically on the way networks are grouped together to form
regions. A region containing two networks, one in California and the other in
England, is not structured in such a way that effective routes can be derived
from the network address alone. A naive gateway, routing its packet only to
the region without regard to the particular network for which the packet is
destined, may discover that the packet has been routed to the wrong side of
the world. In fact, it is probable, in most cases, that regions should be
connected. If not, it may be impossible to get a packet from one part of the
region to the other, since the packet will have to leave the region in order
to do so and may encounter a gateway which, not understanding anything about
the network structure of the region, blindly sends the packet back to the part
of the region from which it came. If, however, the appropriate gateways can
be specially trained, there is nothing to prevent a disjoint region, and in
particular circumstances it may be quite appropriate.
4. Source Routing
In the previous section, it was shown that an internet address of the
form <region, network,...> could be used to derive a default route for a
packet, much as a route is now derived by the gateways from the current
internetwork address. Can we presume that this route will always be
sufficient, even if it is not optimal? Unfortunately, in a few cases we
cannot. First, it is easy to imagine circumstances in which the default route
is hopelessly inefficient. A network may be connected by gateways to several
4
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
regions, even though for addressing purposes it is identified as belonging to
one particular region. To send a packet to that region in order to reach the
network may grossly lengthen the path of the packet. As we said before, this
problem can be minimized by proper use of the region mechanism, but we cannot
expect the region mechanism to be perfect. Second, it may be necessary to
route a packet in such a way that it explicitly does not go through certain
networks. For example, speech packets may be hopelessly delayed if they
inadvertantly travel by a network involving a satellite. It may be necessary
to ensure that speech packets travel by some network with lower bandwidth but
better response characteristics.
How can the internet come up with better routing information in those
cases where it is required? In many cases, additional intelligence can be
built into the gateways. What is required is that gateways not immediately
adjacent to a region be prepared to understand the network field as well as
the region field of packets destined to that region. This is analogous to
something which happened in the telephone system, where a central office
originating a phone call will usually examine only the area code in order to
generate a route, but may, if it detects a particular area code, then further
examine the destinations central office to discover if use of a particular
optomized route is applicable. Building this additional routing knowledge
into the gateways is very desirable in general, since it means that it will
apply to all packets. However, we cannot expect all routing information to be
embedded in the gateways. First, in order to solve the problem offered above
of properly routing the speech packet, it would be necessary for the gateways
to base their routing decisions on type of service information. This sounds
like a rather complex decision for the gateways, especially since type of
5
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
service is not well understood. Second, network topology will change with
time, and it is not reasonable to expect that all gateways will be constantly
updated. Thus, we can expect the situation where only the originator of the
packet has sufficient information to specify the proper route.
The solution which has been proposed in the past to cope with this is to
replace the address in the packet whith a route, called a source route since
it is provided by the source of the packet. The disadvantage of having a
route in a packet instead of an address is that the concept of an address is
very useful one. For example, for accounting purposes it may be necessary to
note the source and destination of a packet as it passes through a transit
net. Clearly, it is desirable that the source and destination be uniquely
identified for this purpose, something not easily done if the source and
destination are specified only by a route. Thus, we propose that the address
continue to be the primary piece of information in the packet, but that it be
possible to include, in addition, an optional source route. This new internet
option field will, if present, be used by the gateways instead of the default
route which would normally be derived from the address.
We do not propose, in this report, a specific syntax for the option
field. However, we make the following general observations. The source route
should be structured in such a way that it need not contain more information
than that required to augment the defficiencies in the default route. Thus,
for example, it should be possible to source route a packet into a particular
region, then specify that the default route should be used to get from there
to some other region, and then specify additional explicit source information.
In a later section we propose a particular semantics for source routes.
6
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
5. Migration
What is the relationship between the scheme proposed here and the current
internet header with a fixed size address field? Happily, adoption of the
addressing strategy involving regions together with the optional internet
source route implies no immediate upheaval to packet formats or gateway code.
Currently, every network is a region, and every gateway thus contains code for
doing inter-region routing. Eventually, gateways will want to be modified as
follows. When a region finally is defined which contains more than one
network, then gateways inside that region will need to understand an
additional component of the internet address. Presumably, since different
regions may have a different number of networks, we can expect the size of the
network field to differ between regions. Thus, unless gateway code is
rewritten for different regions, it will be necessary to write code which can
deal, eventually, with a variable size component of the address. The address
itself, however, can reasonably be a fixed size, since it is merely an address
and not a route. In fact, it seems that the field as specified for the
current internet header is sufficient in size, although perhaps marginally so.
Given that certain implementations of this header already exist, I would
suggest that the correct field size in 3.1 be accepted unless strong
complaints are heard from someone in the near future.
The next step in adopting this scheme, after the gateways have learned
that for certain regions they must also look at some additional address bits,
is to arrange that gateways selectively use this additional information, even
when it is for a region for which they are not immediately adjacent. This
facility, discussed above, can be used to provide more efficient routing than
the default which would otherwise result from simplistic use of the address
7
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
information. The technical problem here is not implementation of additional
gateway code for address manipulation, but rather the development of proper
policies for dissemination of routing information so that the appropriate
gateways are correctly informed of the routing decisions to make.
The third and final step in adoption of this scheme is the implementation
in the gateways and hosts of the new internet option which specifies explicit
source routes. Presumably, the general mechanism for dealing with internet
option fields will already exist, so this is not a major upheaval of the code
which parses an internet header. The only issue related to parsing is that,
as the packet flows from gateway to gateway the source route will need to be
modified to indicate which portion has already been used. This can either be
done by physically rewriting the route into the option field, or by providing
a pointer into the field as part of the option. The pointer field has the
advantage that it does not destroy the route, so that it can be used to
backtrack to the source, which is an important feature.
There are two reasons why it is desirable to be able to use a source route
in reverse. First, the recipient of the packet may have no idea how to get
back to the source. Second, and more relevant, if the route has been formed
incorrectly, a gateway may receive a packet and have no idea how to forward
it, because the next component of the route is nonsense. If that intermediate
gateway cannot figure out how to get an error message back to the originating
host, packets sent with malformed routes will appear to fall into black holes.
It is very difficult to debug systems with black holes. Thus, reversability
of routes is very important.
The need for modification implies the option should not be checksummed as
part of an end-to-end checksum. The packet will also contain an address which
8
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
can be used by the eventual recipient to confirm that the packet is indeed
destined for him. The address field can be checksummed, and under certain
circumstances even encrypted.
6. Semantics of Source Routes
We view the internet as being composed of three physical entities:
networks, gateways, and hosts, and one logical entity, a region, which is an
aggregate of networks. The default route algorithm examines the region and,
optionally, the network within this region, and selects from a table the
appropriate network and gateway on that network to which to send the packet.
Thus, if the route followed by a packet were written out in advance, it would
be an alternating concatination of network names and gateway names, finally
terminating with a network name followed by a host name. For symmetry, one
should also precede the source route with the name of the originating host, to
allow the route to be used in reverse. Thus, an initial structure for
internet source routes might look as follows:
H,N,G,N,G,N,G,N,...,G,N,H
where H is a host identifier,
N is a network identifier,
G is a gateway identifier.
Each gateway, on receiving this route, finds his position in the route using
the pointer into the route, updates the pointer to indicate the next gateway
which is to receive the packet, and then routes the packet through the
specified network to the next gateway.
The source route as shown above always specifies the complete route. For
many cases this degree of specificity is not necessary. For example, once a
9
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
packet has been routed part of its way, the default route may then be
effective. This generalization means that instead of specifying the
particular network which is used as we pass from one gateway to the next, a
default route can be used between two particular points in the route. Thus,
we propose a more general form of a source route, as follows:
<source route>:=<source><step>...<destination>
The source route takes the packet from the source to a sequence of
gateways to the destination. The progress from each of these specified points
to the next is a step.
<step>:=<explicit route step>|<default route step>
<explicit route step>:= RNG
If we are concerned with the exact route between one gateway and the
next, we specify the step in this form, naming the particular network that is
to be used. A sequence of explicit route steps can thus connect two gateways
not immediately adjacent.
<default route step>:=<starting net><ending net>G
<starting net>,<ending net>:= RN
If the particular route to the next specified point is not critical, then
the default route step is used. The originating gateway will generate a route
to the network addressed by <ending net>. That net may be any distance away
in the internet; intermediate gateways in this step will again generate the
default route from <ending net> until the specified gateway G is reached,
which will end the step. <starting net> is required so that the route can be
10
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
used in reverse. It must specify the network address of the gateway,
originating this step.
<destination>:= RNH|RNRNH
The destination is in fact the final step and as such can be either
explicit or default. Thus it has two forms, with the interpretation of the
step with the equivalent form.
Note that while the string representing the source route is generated as
a sequence of "forward" steps, there is another grammar that generates the
same strings as a sequence of "reverse" steps. Also, in the <explicit route
step>, the intervening network is identified using a full network address,
including the region. In fact, any shorthand network identifier can be used,
so long as it is unambiguously interpretable by the gateway at each end of the
step.
7. Uniqueness of Names
Hosts will often be attached to more than one network. Thus, hosts may
have more than one internet address. As long as the only routing algorithm is
default routes based on addresses, there will be a strong desire to use these
additional names to generate better routes. While this is fine in the short
run, functions such as accounting will be easier to implement if hosts have a
single unique address. To this end, when the route option is implemented we
expect that it will be appropriate to address a host in only one way, and
specify a route additionally.
11
Internet Notebook Section 2.3.3.15 Clark, Cohen
IEN No. 46 June, 1978
REFERENCES:
(1) Shoch, J.F., "A Note on Inter-Networking Naming, Addressing, and
Routing," Xerox Palo Alto Research Center, Palo Alto, California,
INTERNET Notebook, Note No. 19, Section 2.3.3.5, January 1978.
12
mirror server hosted at Truenetwork, Russian Federation.