Chapter 10

Some additional net references for routing can be found at http://www.itprc.com/routing.htm and http://www.ietf.org/html.charters/idr-charter.html. There is an excellent graphical tool for showing routes (from Warsaw!) at http://visualroute.ipartners.pl:81, and a different one at http://visualroute.visualware.co.uk.

p. 127

The widespread use of ATM as the link-layer protocol in WANs has meant, oddly enough, that IP routing within a WAN is less important than it used to be. Consider, for example, the SuperJanet IV core network (see http://www.superjanet4.net/rollout/outline.pdf for a diagram). The underlying link-layer protocol between the eight Core PoP routers is ATM, so that, as seen from IP's point of view, all eight are directly connected on the same network, and no IP-layer routing is necessary between them. If one of the fibres goes down, so that two sites are no longer directly connected at the fibre level, then it is up to ATM's routing to redirect the ATM cells, so that the IP layer still sees direct connectivity between all the sites.

p. 128

OSPF is now definitely more popular than RIP for new networks, for the reasons outlined later. RFC 1812 (updating the small print statement on the page) says that if a router supports any IGP, then it MUST support OSPF³⁴. BGP has also replaced EGP in most situations, and again is mandated by RFC 1812 if any Exterior Gateway Protocol (EGP per se, RIP etc.) is supported.

p. 132

Although the RIP RFC (1058³⁵) was written three years after the definition of sub-netting (RFC 950), the RIP RFC was a piece of retrospective documentation, and the RIP code was generally written before sub-netting.

p. 132

The second problem mentioned here is slow convergence. This is often due to a phenomenon known as ``counting to infinity'' which we illustrate in the context of the diagram on page 131. The initial stable state is as follows (where the entries show ``first-hop'' routes and metrics).

R1$\rightarrow$N2

R1$\rightarrow$N3

R2$\rightarrow$N1

R2$\rightarrow$N2

R2$\rightarrow$N3 (direct) 1

R2 is sending RIP messages to R1 indicating that N3 is one hop from it, and therefore R1 deduces that N3 is two hops from it. It therefore broadcasts this fact, but R2 ignores this, since that route would make N3 three hops from it, whereas it is only one.

Now suppose that the interface from R2 to N3 fails. The situation is then as follows.

R1$\rightarrow$N2

R1$\rightarrow$N3

R2$\rightarrow$N1

R2$\rightarrow$N2

R2$\rightarrow$N3 (direct) 1

R2 now does not know how to reach N3 directly, so the next broadcast from R1 causes it to accept that message (after all, R1 might have another route to N3, say via a router connecting N1 and N3). This makes the situation the following.

R1$\rightarrow$N2

R1$\rightarrow$N3

R2$\rightarrow$N1

R2$\rightarrow$N2

R2$\rightarrow$N3 (direct) 1

R2's next broadcast will advertise a distance of three to N3, which will cause R1 to believe that it is now four from it. This makes the situation the following.

R1$\rightarrow$N2

R1$\rightarrow$N3

R2$\rightarrow$N1

R2$\rightarrow$N2

R2$\rightarrow$N3 (direct) 1

The next broadcast from R1 will make R2 now believe that it is five hops from N3. R1 will later believe that it is six hops, and so on.

The problem is that R2 does not know that the route R1 is advertising is in fact through R2 (since it could be via some other router). Since ``infinity''=16 in RIP, this means that the process takes, on average, four minutes to converge (eight RIP updates from R1 to R2), assuming that no packet is lost. Since packets are bouncing around between R1 and R2, N2 is likely to be overloaded, so packet loss is indeed possible, slowing down the convergence.

p. 137

The current version of OSPF is described in RFC 2328.

p. 138

All OSPF packets begin with a standard header, as defined below.

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version # (2) |     Type      |         Packet length         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Router ID                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                           Area ID                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           Checksum            |             AuType            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Authentication                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Authentication                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The various types are as follows.

1. Hello -- these packets are sent to immediate neighbour routers, to ``establish and maintain neighbor relationships''³⁶.
2. Database Description.
3. Link State Request.
4. Link State Update.
5. Link State Acknowledgment.

Unusually, the checksum, though computed the usual IP way, does not include the 64 bits of authentication: this is because authentication is done after checksumming. Various kinds of authentication³⁷ are possible with OSPF, and the AuType field says which is being used for this packet.

The `Hello' packet has the following format (after the standard OSPF header).

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Network Mask                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         HelloInterval         |    Options    |    Rtr Pri    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     RouterDeadInterval                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      Designated Router                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Backup Designated Router                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Neighbour                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                              ...                              |

For the format of the other packets, see RFC2328.

p. 139

BGP version 4 is now described in RFC 1771, with a good rationale in the companion RFC 1772. The introduction of CIDR has meant that the definition of an AS has changed: RFC 1771 says the following.

Since this classic definition was developed, it has become common for a single AS to use several interior gateway protocols and sometimes several metrics within an AS. The use of the term Autonomous System here stresses the fact that, even when multiple IGPs and metrics are used, the administration of an AS appears to other ASs to have a single coherent interior routing plan and presents a consistent picture of what destinations are reachable through it.

A further complication is that there are many autonomous systems that ought not to be visible much beyond their boundary. Consider the University of Bath, which is an AS hung off BWEMAN. This is its only point of access, so it is a stub AS. From the point of view of everyone outside BWEMAN, it might as well be part of BWEMAN's AS, since the only route to it is via BWEMAN. RFC 3065 introduces the concept of an `AS confederation', defined as ``A collection of autonomous systems advertised as a single AS number to BGP speakers that are not members of the confederation''. In this sense, there is an AS confederation including the BWEMAN core, Bath, Bristol, UWE etc., which can be regarded as a single AS by everyone outside it. Indeed the whole of SuperJanet IV and all connected MANs could be regarded as a (multi-homed: there are several external links - see http://www.ja.net/topology/external.html) AS confederation.

p. 139

The Bath campus is a typical example of a stub AS. It does support more than one network: as well as 138.38, there are networks for UKOLN, ingenta and EduServ. There is also a private network 172.28 for the IP interfaces on the campus ATM network and for ResNet.

p. 141

It was reported at the end of 1999 that some routers were close to having 100,000 entries in their route table. This, while large (and requiring better algorithms than sequential search in the routing mechanism!), is still less than the 2,000,000+ that classic IP without CIDR would imply.