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]