Normally IP routing is dynamic with each router making a decision about which next -hop router to send the datagram to. Applications have no control of this, and are normally not concerned with it. It takes tools such as Traceroute to figure out what the route really is.
The idea behind source routing is that the sender specifies the route. Two forms are provided:
Strict source routing. The sender specifies the exact path that the IP datagram must follow. If a router encounters a next hop in the source route that isn't on a directly connected network, an ICMP "source route failed" error is returned.
Loose source routing. The sender specifies a list of IP address that the datagram must traverse, but the datagram can also pass through other routers between any two addresses in the list.
Traceroute provides a way to look at source routing, as we can specify an option allowing us to force a source route, and see what happens.
Some of the publicly available Traceroute source code packages contain patches to specify loose source routing. But the standard versions normally don't include this option. A comment in the patches is that "Van Jacobson's original traceroute (spring 1988) supported this feature, but he removed it due to pressure from people with broken gateways." For the examples shown in this section, the author installed these patches and modified them to allow both loose and strict source routing.
Figure 8.6 shows the format of the source route option.
This format is nearly identical to the format of the record route option that we showed in Figure 7.3. But with source routing we have to fill in the list of IP addresses before sending the IP datagram, while with the record route option we allocate room and zero out the list of IP addresses, letting the routers fill in the next entry in the list. Also, with source routing we only allocate room for and initialize the number of IP addresses required, normally fewer than nine. With the record route option we allocated as much room as we could, for up to nine addresses.
The code is 0x83 for loose source routing, and 0x89 for strict source routing. The len and ptr fields are identical to what we described in Section 7.3.
The source route options are actually called "source and record route" (LSRR and SSRR, for loose and strict) since the list of IP addresses is updated as the datagram passes along the path. What happens is as follows :
The sending host takes the source route list from the application, removes the first entry (it becomes the destination address of the datagram), moves all the remaining entries left by one entry (where left is as in Figure 8.6), and places the original destination address as the final entry in the list. The pointer still points to the first entry in the list (e.g., the value of the pointer is 4).
Each router that handles the datagram checks whether it is the destination address of the datagram. If not, the datagram is forwarded as normal. (In this case loose source routing must have been specified, or we wouldn't have received the datagram.)
If the router is the destination, and the pointer is not greater than the length, then (1) the next address in the list (where ptr points) becomes the destination address of the datagram, (2) the IP address corresponding to the outgoing interface replaces the source address just used, and (3) the pointer is incremented by 4.
This is best explained with an example. In Figure 8.7 we assume that the sending application on host S sends a datagram to D, specifying a source route of R1, R2, and R3.
In this figure the pound sign (#) denotes the pointer field, which assumes the values of 4, 8, 12, and 16. The length field will always be 15 (three IP addresses plus 3 bytes of overhead). Notice how the destination address of the IP datagram changes on every hop.
When an application receives data that was source routed, it should fetch the value of the received route and supply a reversed route for sending replies.
The Host Requirements RFC specifies that a TCP client must be able to specify a source route, and that a TCP server must be able to receive a source route, and use the reverse route for all segments on that TCP connection. If the TCP server later receives a different source route, that newer source route overrides the earlier one.
The -g option to traceroute lets us specify intermediate routers to be used with loose source routing. This option can be specified up to eight times. (The reason this is eight and not nine is that the programming interface being used requires that the final entry be the destination.)
Recall from Figure 8.4 that the route to the NIC, nic.ddn.mil, was through the NASA Science Internet. In Figure 8.8 we force the datagrams to pass through the NSFNET instead by specifying the router enss142.UT.westnet.net (18.104.22.168) as an intermediate router:
This time there appear to be 16 hops with an average RTT of around 350 ms, while the normal route shown in Figure 8.4 had only 13 hops and an average RTT of around 322 ms. The default route appears better. (There are also other decisions made when routes are established. Some are made on the basis of the organizational and political boundaries of the networks involved.)
But we said there appear to be 16 hops, because a comparison of this output with our previous example through the NSFNET (Figure 8.5) shows three missing routers in this example using loose source routing. (These are probably caused by bugs in the router's generation of ICMP time exceeded errors in response to source routed datagrams.) The router gateway.tuc.noao.edu is missing between netb and butch, and the routers Westgate.Telcom.Arizona.edu and uu-ua.AZ.westnet.net are also missing between Gabby and enss142.UT.westnet.net. There is probably a software problem in these missing routers related to incoming datagrams with the loose source routing option. There are really 19 hops between the source and the NIC, when using the NSFNET. Exercise 8.5 continues the discussion of these missing routers.
This example also illustrates another problem. On the command line we have to specify the dotted -decimal IP address of the router enssl42.UT.westnet.net instead of its name. This is because the reverse name lookup (return the name , given the IP address, Section 14.5), associates the name with the IP address, but the forward lookup (given the name, return the IP address) fails. The forward mapping and reverse mapping are two separate files in the DNS (Domain Name System) and not all administrators keep the two synchronized with each other. It's not uncommon to have one direction work and the other direction fail.
Something that we haven't seen before is the asterisk (*) printed for the first RTT for the TTL of 8. This indicates that a timeout occurred and no response was received within 5 seconds for this probe.
Another point that we can infer from a comparison of this figure and Figure 8.4 is that the router nsn-FIX-pe.sura.net is connected to both the NSFNET and the NASA Science Internet.
The -G option in the author's version of traceroute is identical to the -g option described earlier, but the source route is strict instead of loose. We can use this to see what happens when an invalid strict source route is specified. Recall from Figure 8.5 that the normal sequence of routers for datagrams from the author's subnet to the NSFNET is through netb, gateway, butch, and gabby. (We've omitted the domain suffixes, tuc.noao.edu and .telcom.arizona.edu, in all the output below to make it easier to read.) We specify a strict source route that omits butch, trying to go directly from gateway to gabby. We expect this to fail, as shown in Figure 8.9.
The key here is the notation !S following the RTTs for the TTL of 3. This indicates that traceroute received an ICMP "source route failed" error message: a type of 3 and a code of 5 from Figure 6.3. The asterisk for the second RTT for the TTL of 3 indicates no response was received for that probe. This is what we expect, since it's impossible for gateway to send the datagram directly to gabby, because they're not directly connected.
The reason that both TTLs 2 and 3 are from gateway is that the values for the TTL of 2 are from gateway when it receives the datagram with an incoming TTL of 1. It discovers that the TTL has expired before it looks at the (invalid) strict source route, and sends back the ICMP time exceeded. The line with a TTL of 3 is received by gateway with an incoming TTL of 2, so it looks at the strict source route, discovers that it's invalid, and sends back the ICMP source route failed error.
Figure 8.10 shows the tcpdump output corresponding to this example. This output was collected on the SLIP link between sun and netb. We had to specify the -v option for tcpdump to display the source route information. This produces other output that we don't need, such as the datagram ID, which we've deleted. Also, the notation SSRR stands for "strict source and record route."
First note that each UDP datagram sent by sun has a destination of netb, not the destination host ( westgate ). We described this with the example shown in Figure 8.7. Similarly, the other two routers specified with the -G option ( gateway and gabby ) and the final destination ( westgate ) become the SSRR option list on the first hop.
We can also see from this output that the timeout used by traceroute (the time difference between lines 15 and 16) is 5 seconds.
Earlier we said that there is no guarantee that the route from A to B is the same as the route from B to A. Other than having a login on both systems and running traceroute on each end, it's hard to find out if there is a difference in the two paths. Using loose source routing, however, we can determine the route in both directions.
The trick is to specify loose source routing with the destination as the loose route, and the sending host as the final destination. For example, on the host sun we can find the paths to and from the host bruno.cs.Colorado.edu (Figure 8.11).
The outbound path (TTLs 1 “11) differs from the return path (TTLs 11 “21), a good illustration that Internet routing need not be symmetrical.
This output also illustrates the point we discussed with Figure 8.3. Compare the output for TTLs 2 and 19: both are for the router gateway.tuc.noao.edu, but the two IP addresses are different. Since traceroute identifies the incoming interface, and since we're passing through the router in two different directions, once on the outbound path (TTL 2) and then on the return path (TTL 19), we expect this. We see the same effect comparing TTLs 3 and 18, and TTLs 4 and 17.