50 |
ROUTING PROTOCOLS |
Below we will take a quick look at a number of routing protocols widely used in service provider networks and at the mechanisms each uses to improve scalability. Not all protocols neatly fit into these categories, as there are some derivatives and hybrids. However, they provide useful categorizations on which to base this discussion.
5.1 WHY DIFFERENT ROUTING PROTOCOLS?
Many people, particularly those new to the field, ask why we need different routing protocols for our internal routes and our external routes. There are several reasons but the most compelling is that each type of protocol is optimized for its particular purpose. In this respect, there are two main types of routing protocols: Interior Gateway Protocols and Exterior Gateway Protocols.
5.2 INTERIOR GATEWAY PROTOCOLS (IGP)
IGPs are optimized for smaller sets of prefixes within an autonomous system but provide rapid convergence. Generally, it is wise to place fewer, more stable prefixes in your IGP. Ideally, this should be constrained to the links, which actually form part of your own network (i.e. links and loopback2 interfaces attached your core routers, edge routers and, possibly, between edge routers and hosts/servers). IGPs do not usually scale well when comparatively unstable prefixes or large numbers of prefixes are carried. Some feel that it is best not to use an IGP to carry any routes associated with individual customers at all (i.e. point-to-point links and customers’ own networks). However, others feel that the IGP is fundamentally a mechanism for distributing reachability information for BGP next hops. If this is the case, then the point-to-point links could reasonably be considered as a valid IGP route. In the end, this is strictly a policy decision for the network operator. Those holding the former viewpoint feel that the IGP databases should be kept as small as possible and that it is unnecessary, given the ability to set BGP next-hop self,3 to carry any information relating to networks other than those in the core. They point out that if the IGP is unable to stabilize and converge, then it is of no value. Thus, it is essential to make the task of the IGP the bare minimum.
Making a specific statement about how many routes an IGP can hold before it becomes a problem is not easy. The actual number of routes depends upon a huge number of variables, e.g. the design of the protocol, the implementation of that design by the vendor, the way the protocol has been configured by the operator, the stability of the various links, the processing power of the routers, the ability of the routers to transfer routing
2 Loopback interfaces are virtual interfaces that are not associated with any physical interface. Such interfaces are always up and reachable as long as any one of the physical interfaces on the router is up.
3 Next-hop self is explained in more detail later in this chapter.
5.2 INTERIOR GATEWAY PROTOCOLS (IGP) |
51 |
information from the forwarding plane to the control plane, and so on. In an Internet in which the global routing table is around 150 000 prefixes, it is preferable to keep the number of prefixes in your IGP in the hundreds or low thousands. In the tens of thousands, most IGPs (irrespective of how well implemented, configured and sustained by the routers they are) will become unstable. As mentioned above, an unstable IGP is a disaster, because it not only affects your internal routing but also your ability to reach any external destinations.
Today, SPs generally use OSPF or IS-IS, the larger ones tending more towards IS-IS.4 Other IGPs are described here for completeness and because they have a significant role to play in enterprise networks, even moderately large ones.
5.2.1OPEN SHORTEST PATH FIRST (OSPF)
OSPF is a classless, link-state IGP developed in the late 1980s and early 1990s by the IETF. It distributes routing information within a single autonomous system. OSPF floods routing information throughout the entire domain using link state advertisements (LSAs). Each router runs a shortest path first (or Dijkstra) algorithm to derive a complete network topology. All routers in the network have an identical copy of the link state database (LSDB), however, each views the network as a tree with itself as the root of the tree.
OSPF supports a hierarchical model in which ‘areas’ are created. Areas are groups of routers and links. The border between areas falls on routers known as Area Border Routers (ABRs). Each area is identified by a 32-bit identifier (often presented in the form of an ‘IP address’, although it is totally unlinked to any IP address). The core of a network is area zero and all non-zero areas must connect to area zero. All traffic from one non-zero area to another non-zero area must pass through area zero.
ABRs also support the concept of route summarization. Route summarization is yet another compromise. It reduces the amount of routing information stored, which eases the burden on resources such as memory and processing power. However, route summarization can lead to the selection of sub-optimal paths. This is particularly true where more than one ABR provides connectivity between area zero and a single non-zero area.
While OSPF within a single area operates in a link state mode, it operates in a distance vector mode between areas. When routing information is passed between areas, the information regarding the actual source can be lost. Instead, the ABR becomes the advertising router of the summary and it becomes the ‘vector’ towards which the traffic should be sent. This is fundamentally due to the summarization of routing information from one non-zero area upon entry into area zero. This summary information is sourced by the ABR and the topology of the non-zero area is hidden. This information is then flooded throughout the rest of the network.
One side effect of this distance vector behaviour is that some form of loop detection or loop avoidance mechanism is required. The chosen mechanism is to constrain the network to a star-like model. By mandating that all non-zero areas must be connected only to the
4 The reasons for this choice are discussed in more detail later in this chapter.
52 |
ROUTING PROTOCOLS |
backbone area, it is possible to remove the risk of any loops. Figure 5.1 demonstrates a valid network architecture within OSPF, while Figure 5.2 demonstrates an invalid network architecture within OSPF.
In order to bypass the constraint that all areas must be directly connected to area zero, a mechanism called virtual links was devised. This allows a non-zero area to be connected to area zero via another non-zero area (see Figure 5.3).
Area 1.0.0.0
Area 6.0.0.0 |
Area 2.0.0.0 |
Area 0
Area 5.0.0.0 |
Area 3.0.0.0 |
Area 4.0.0.0
ABR
Figure 5.1 Multi-area OSPF hierarchy
Area 1.0.0.0
Area 2.0.0.0
Area 0
Area 5.0.0.0
Area 3.0.0.0
Area 4.0.0.0
Area 6.0.0.0 |
ABR |
|
Figure 5.2 Illegal OSPF hierarchy
5.2 INTERIOR GATEWAY PROTOCOLS (IGP) |
53 |
virtual link |
Area 5.0.0.0 |
Area 1.0.0.0
Area 2.0.0.0
Area 0
Area 3.0.0.0
Area 4.0.0.0
Area 6.0.0.0 |
ABR |
|
Figure 5.3 A virtual link makes this hierarchy legal
5.2.2AUTHENTICATION OF OSPF
OSPF is vulnerable to the insertion of spurious data, either maliciously or inadvertently. Authentication is one mechanism often used to protect against the insertion of invalid data into OSPF. OSPF provides three states of authentication: none, simple authentication and MD5 authentication. It is required, if you configure authentication, that you configure the same authentication method throughout a single area. It is also required in RFC 2328 that authentication be configurable on a per-interface basis. If you cannot configure different authentication mechanisms on a per-interface basis, then it follows that the same authentication type must be configured throughout the entire autonomous system.
•None. As the name suggests in this mode, OSPF exchanges are actually not authenticated at all. This is generally the default configuration of OSPF implementations. It provides no protection whatsoever.
•Simple password authentication. OSPF provides the ability to use a clear text password. Both neighbours must use an identical clear text password in order for the neighbour relationship to be fully established. Since the key is passed in the clear with every authenticated packet, it is a relatively simple matter to snoop the key and inject spurious routing updates. Therefore, this is not a mechanism which would be recommended for a large network.
•MD5 authentication. OSPF is able to use MD5 authentication mechanisms. Each neighbour must have the same MD5 key for any exchange of OSPF packets to occur. A