IEN 95


                             Source Routing





                              Danny Cohen

                               Jon Postel
















                               2 May 1979





                     Information Sciences Institute
                   University of Southern California
                           4676 Admiralty Way
                   Marina del Rey, California  90291

                             (213) 822-1511





IEN-95                                                          D. Cohen
                                                               J. Postel
                                                                     ISI
                                                              2 May 1979



                             SOURCE ROUTING
                             --------------

Introduction
------------

This memo discusses source routing.  Source routing allows (or requires)
the source of a message to supply information with the message that will
influence   the  route  of  that  message   as  it  passes  through  the
communication system.

Discussion
----------

The Internet  Protocol  (IN)  [1] header  may contain  both  destination
address field and a source route string.

There are 3 possible relations between them:

  (1)  The  terminal  destination  address  (TDA)  is always  in the  IN
       destination address field (DAF),

    (1A) The  source route is included in an advisory capacity only.  It
         is used  if there  is no known  route  to the  TDA.   Once  the
         message  arrives to where route to the TDA is known, the source
         route may be ignored.

    (1B) The  source route is mandatory and has to be followed until the
         TDA is reached.

  (2)  The  DAF contains  the address  of the next  leg  of  the  source
       routing.   Only when it is reached,  the  source  routing  option
       field has to be checked  again.   Hence,  a source routed message
       can pass through   intermediate  gateways and nodes which are not
       capable  of handling   source routing, and only those nodes which
       are  specifically  mentioned   in  the  source  route  (with  the
       possible  exception  of the terminal destination) have to be able
       to handle the source routing option.

The most reasonable  of these three possibilities  is (2).   It has  the
same  flavor  as (1B),  by forcing the message to traverse the specified
source  route, which is important for (i) reaching obscure destinations,
(ii) security, and (iii) measurements.




Cohen & Postel                                                  [page 1]


                                                              2 May 1979
Source Routing                                                    IEN 95



The (2) possibility, unlike either (1A) and (1B), has the advantage that
it does not require  that all the involved  gateways  should  be able to
process the source routing options.

This is also a more efficient  way to handle the source routing, because
even in the case that all gateways  can handle  the source routing, only
the ones specifically included in it, has to examine this option.

It is likely  that  if A has to source  route to B, then B would need to
source route to A.  Since the source route from B to A may not be known,
it is desired to figure it by "tracking" the messages from A to B.

This can be done by using the Construct-Return-Route (CRR) option.  When
this option  is included, each participating gateway adds to this option
field  its own name,  as known in the environment to which to message is
forwarded.

For example:

                    S----1A----2B----3C----4D----R
                      N1    N2    N3    N4    N5

The first  gateway  is known as "1" in the N1 network, and as "A" in the
N2 net.  Similarly, the second gateway is "2" for the N2 network and "B"
for the next  one.   And so on.   S may source-route  a message  to R as
[N2:2,  N4:4,  N5:R]  provided  that its interface can route messages to
N2,  (but probably  not to N3 and beyond), that the gateway 2B can route
messages to N4, and so on.

For the return route, [N5:D, N3:B, N1:S] should be used.

In order to construct  the return  route,  each process participating in
the    source   route   (by  being   included  in  the  list)  adds  its
"return-address"  IN-FRONT of the return-route which is found in the CRR
option field.

It  is  recommended   to  use  this  option   only  for   initiating   a
communication,   and to save time by not repeating  the CRR  request  in
every message thereafter.

Note,  the source  route cannot  be used  to  constructing  hierarchical
addressing where not expected.







[page 2]                                                  Cohen & Postel


2 May 1979
IEN 95                                                    Source Routing



Here are 3 possible  formats  for the SR (S1,  S2,  S3),  and 2 possible
formats for the CRR (C1, C2).

                       S   ----->  mM  ----->  nN  ----->  R
            -----------+-----------+-----------+-----------+
                   DAF |     R     |     R     |     R     |
            S1     SR  | 3,1,m,n,R | 3,2,m,n,R | 3,3,m,n,R |
            -----------+-----------+-----------+-----------+
                   DAF |     m     |     n     |     R     |
            S2     SR  | 3,1,m,n,R | 3,2,m,n,R | 3,3,m,n,R |
            -----------+-----------+-----------+-----------+
                   DAF |     m     |     n     |     R     |
            S3     SR  |   2,n,R   |    1,R    |     0     |
            -----------+-----------+-----------+-----------+
                   SAF |     S     |     S     |     S     |
            C1     RR  |     0     |    1,M    |   2,M,N   |
            -----------+-----------+-----------+-----------+
                   SAF |     S     |     S     |           |
            C2     RR  |    1,S    |   2,S,M   |  3,S,M,N  |
            -----------+-----------+-----------+-----------+


                                 Legend
                                 ------
        for S1, S2 the SR format is "count,pointer,a1,a2,..."
        for S3, C1, C2 the SR or RR format is "count,a1,a2,..."

S3/C1 is the method selected.

Source Route Option
-------------------

+--------+--------+--------+---------//--------+
|00000011| length |        source route        |
+--------+--------+--------+---------//--------+
Option=3

The source  route  option provides a means for the source of an internet
datagram  to supply  routing  information  to be used by the gateways in
forwarding the datagram to the destination.

The option  begins  with the option  type code.  The second octet is the
option  length which includes the option type code and the length octet,
as well as length-2 octets of source route data.

A source  route is composed  of a series  of internet  addresses.   Each



Cohen & Postel                                                  [page 3]


                                                              2 May 1979
Source Routing                                                    IEN 95



internet  address  is 32 bits or 4 octets.   The length defaults to two,
which indicates  the source  route is empty and the remaining routing is
to be based on the destination address field.

If the address  in destination  address  field has been reached  and the
length  is not two,  the next address  in the source  route replaces the
address  in the destination  address  field, and that address is deleted
from the source route and the length is reduced by four.

Return Route Option
-------------------

+--------+--------+--------+---------//--------+
|00000111| length |        return route        |
+--------+--------+--------+---------//--------+
Option=7

The return  route  option  provides  a means  to record  the route of an
internet datagram.

The option  begins  with the option  type code.  The second octet is the
option  length which includes the option type code and the length octet,
as well as length-2 octets of return route data.

A return  route  is composed  of a series  of internet  addresses.   The
length defaults to two, which indicates the return route is empty.

When an internet module routes a datagram it checks to see if the return
route  option is present.  If it is, it inserts its own internet address
as known in the environment  into which this datagram is being forwarded
into the return  route at the front of the address string and increments
the length by four.

















[page 4]                                                  Cohen & Postel


2 May 1979
IEN 95                                                    Source Routing
                                                              References



References
----------

[1]     Postel,  J.,  "Internet Datagram Protocol -- Version 4," IEN 80,
        USC-Information Sciences Institute, February 1979.

[2]     Postel,  J.,  "Transmission  Control  Protocol  --  Version  4,"
        IEN 81, USC-Information Sciences Institute, February 1979.








































Cohen & Postel                                                  [page 5]