home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / ien / ien-95 < prev    next >
Text File  |  1988-12-02  |  10KB  |  339 lines
  1.  
  2.                                                                         
  3.  
  4.  
  5. IEN 95
  6.                                     
  7.                                     
  8.                              Source Routing
  9.  
  10.  
  11.  
  12.  
  13.  
  14.                               Danny Cohen
  15.                                     
  16.                                Jon Postel
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.                                2 May 1979
  34.  
  35.  
  36.  
  37.  
  38.  
  39.                      Information Sciences Institute
  40.                    University of Southern California
  41.                            4676 Admiralty Way
  42.                    Marina del Rey, California  90291
  43.                                     
  44.                              (213) 822-1511
  45.                                     
  46.                                     
  47.  
  48.  
  49.  
  50.  
  51. IEN-95                                                          D. Cohen
  52.                                                                J. Postel
  53.                                                                      ISI
  54.                                                               2 May 1979
  55.  
  56.  
  57.  
  58.                              SOURCE ROUTING
  59.                              --------------
  60.  
  61. Introduction
  62. ------------
  63.  
  64. This memo discusses source routing.  Source routing allows (or requires)
  65. the source of a message to supply information with the message that will
  66. influence   the  route  of  that  message   as  it  passes  through  the
  67. communication system.
  68.  
  69. Discussion
  70. ----------
  71.  
  72. The Internet  Protocol  (IN)  [1] header  may contain  both  destination
  73. address field and a source route string.
  74.  
  75. There are 3 possible relations between them:
  76.  
  77.   (1)  The  terminal  destination  address  (TDA)  is always  in the  IN
  78.        destination address field (DAF),
  79.  
  80.     (1A) The  source route is included in an advisory capacity only.  It
  81.          is used  if there  is no known  route  to the  TDA.   Once  the
  82.          message  arrives to where route to the TDA is known, the source
  83.          route may be ignored.
  84.  
  85.     (1B) The  source route is mandatory and has to be followed until the
  86.          TDA is reached.
  87.  
  88.   (2)  The  DAF contains  the address  of the next  leg  of  the  source
  89.        routing.   Only when it is reached,  the  source  routing  option
  90.        field has to be checked  again.   Hence,  a source routed message
  91.        can pass through   intermediate  gateways and nodes which are not
  92.        capable  of handling   source routing, and only those nodes which
  93.        are  specifically  mentioned   in  the  source  route  (with  the
  94.        possible  exception  of the terminal destination) have to be able
  95.        to handle the source routing option.
  96.  
  97. The most reasonable  of these three possibilities  is (2).   It has  the
  98. same  flavor  as (1B),  by forcing the message to traverse the specified
  99. source  route, which is important for (i) reaching obscure destinations,
  100. (ii) security, and (iii) measurements.
  101.  
  102.  
  103.  
  104.  
  105. Cohen & Postel                                                  [page 1]
  106.  
  107.  
  108.                                                                         
  109.                                                               2 May 1979
  110. Source Routing                                                    IEN 95
  111.  
  112.  
  113.  
  114. The (2) possibility, unlike either (1A) and (1B), has the advantage that
  115. it does not require  that all the involved  gateways  should  be able to
  116. process the source routing options.
  117.  
  118. This is also a more efficient  way to handle the source routing, because
  119. even in the case that all gateways  can handle  the source routing, only
  120. the ones specifically included in it, has to examine this option.
  121.  
  122. It is likely  that  if A has to source  route to B, then B would need to
  123. source route to A.  Since the source route from B to A may not be known,
  124. it is desired to figure it by "tracking" the messages from A to B.
  125.  
  126. This can be done by using the Construct-Return-Route (CRR) option.  When
  127. this option  is included, each participating gateway adds to this option
  128. field  its own name,  as known in the environment to which to message is
  129. forwarded.
  130.  
  131. For example:
  132.  
  133.                     S----1A----2B----3C----4D----R 
  134.                       N1    N2    N3    N4    N5   
  135.  
  136. The first  gateway  is known as "1" in the N1 network, and as "A" in the
  137. N2 net.  Similarly, the second gateway is "2" for the N2 network and "B"
  138. for the next  one.   And so on.   S may source-route  a message  to R as
  139. [N2:2,  N4:4,  N5:R]  provided  that its interface can route messages to
  140. N2,  (but probably  not to N3 and beyond), that the gateway 2B can route
  141. messages to N4, and so on.
  142.  
  143. For the return route, [N5:D, N3:B, N1:S] should be used.
  144.  
  145. In order to construct  the return  route,  each process participating in
  146. the    source   route   (by  being   included  in  the  list)  adds  its
  147. "return-address"  IN-FRONT of the return-route which is found in the CRR
  148. option field.
  149.  
  150. It  is  recommended   to  use  this  option   only  for   initiating   a
  151. communication,   and to save time by not repeating  the CRR  request  in
  152. every message thereafter.
  153.  
  154. Note,  the source  route cannot  be used  to  constructing  hierarchical
  155. addressing where not expected.
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163. [page 2]                                                  Cohen & Postel
  164.  
  165.  
  166.  
  167. 2 May 1979
  168. IEN 95                                                    Source Routing
  169.  
  170.  
  171.  
  172. Here are 3 possible  formats  for the SR (S1,  S2,  S3),  and 2 possible
  173. formats for the CRR (C1, C2).
  174.  
  175.                        S   ----->  mM  ----->  nN  ----->  R
  176.             -----------+-----------+-----------+-----------+
  177.                    DAF |     R     |     R     |     R     |
  178.             S1     SR  | 3,1,m,n,R | 3,2,m,n,R | 3,3,m,n,R |
  179.             -----------+-----------+-----------+-----------+
  180.                    DAF |     m     |     n     |     R     |
  181.             S2     SR  | 3,1,m,n,R | 3,2,m,n,R | 3,3,m,n,R |
  182.             -----------+-----------+-----------+-----------+
  183.                    DAF |     m     |     n     |     R     |
  184.             S3     SR  |   2,n,R   |    1,R    |     0     |
  185.             -----------+-----------+-----------+-----------+
  186.                    SAF |     S     |     S     |     S     |
  187.             C1     RR  |     0     |    1,M    |   2,M,N   |
  188.             -----------+-----------+-----------+-----------+
  189.                    SAF |     S     |     S     |           |
  190.             C2     RR  |    1,S    |   2,S,M   |  3,S,M,N  |
  191.             -----------+-----------+-----------+-----------+
  192.  
  193.  
  194.                                  Legend
  195.                                  ------
  196.         for S1, S2 the SR format is "count,pointer,a1,a2,..."  
  197.         for S3, C1, C2 the SR or RR format is "count,a1,a2,..."
  198.  
  199. S3/C1 is the method selected.
  200.  
  201. Source Route Option
  202. -------------------
  203.  
  204. +--------+--------+--------+---------//--------+
  205. |00000011| length |        source route        |
  206. +--------+--------+--------+---------//--------+
  207. Option=3
  208.  
  209. The source  route  option provides a means for the source of an internet
  210. datagram  to supply  routing  information  to be used by the gateways in
  211. forwarding the datagram to the destination.
  212.  
  213. The option  begins  with the option  type code.  The second octet is the
  214. option  length which includes the option type code and the length octet,
  215. as well as length-2 octets of source route data.
  216.  
  217. A source  route is composed  of a series  of internet  addresses.   Each
  218.  
  219.  
  220.  
  221. Cohen & Postel                                                  [page 3]
  222.  
  223.  
  224.                                                                         
  225.                                                               2 May 1979
  226. Source Routing                                                    IEN 95
  227.  
  228.  
  229.  
  230. internet  address  is 32 bits or 4 octets.   The length defaults to two,
  231. which indicates  the source  route is empty and the remaining routing is
  232. to be based on the destination address field.
  233.  
  234. If the address  in destination  address  field has been reached  and the
  235. length  is not two,  the next address  in the source  route replaces the
  236. address  in the destination  address  field, and that address is deleted
  237. from the source route and the length is reduced by four.
  238.  
  239. Return Route Option
  240. -------------------
  241.  
  242. +--------+--------+--------+---------//--------+
  243. |00000111| length |        return route        |
  244. +--------+--------+--------+---------//--------+
  245. Option=7
  246.  
  247. The return  route  option  provides  a means  to record  the route of an
  248. internet datagram.
  249.  
  250. The option  begins  with the option  type code.  The second octet is the
  251. option  length which includes the option type code and the length octet,
  252. as well as length-2 octets of return route data.
  253.  
  254. A return  route  is composed  of a series  of internet  addresses.   The
  255. length defaults to two, which indicates the return route is empty.
  256.  
  257. When an internet module routes a datagram it checks to see if the return
  258. route  option is present.  If it is, it inserts its own internet address
  259. as known in the environment  into which this datagram is being forwarded
  260. into the return  route at the front of the address string and increments
  261. the length by four.
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279. [page 4]                                                  Cohen & Postel
  280.  
  281.  
  282.  
  283. 2 May 1979
  284. IEN 95                                                    Source Routing
  285.                                                               References
  286.  
  287.  
  288.  
  289. References
  290. ----------
  291.  
  292. [1]     Postel,  J.,  "Internet Datagram Protocol -- Version 4," IEN 80,
  293.         USC-Information Sciences Institute, February 1979.
  294.  
  295. [2]     Postel,  J.,  "Transmission  Control  Protocol  --  Version  4,"
  296.         IEN 81, USC-Information Sciences Institute, February 1979.
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337. Cohen & Postel                                                  [page 5]
  338.  
  339.