|
|
``Routing protocols'' lists the following about routing protocols:
Routing protocols
| Protocol | Int/ext | daemon | Router or nonrouter | Typical networks | Distinct features |
|---|---|---|---|---|---|
| IRD | other | irdd | both | small/large | backup default router |
| RIP(V1) | int | routed, gated | both | small | |
| RIP(V2) | int | gated | both | small | |
| OSPF | int | gated | router | small/large, 2-tiered | |
| EGP | ext | gated | router | ||
| BGP | ext | gated | router |
The IRD protocol is an extension of the ICMP that is not a true routing protocol. It uses ICMP broadcast or multicast messages to enable hosts attached to multicast or broadcast networks to discover the IP addresses of their neighboring routers. It is best used in a small network within an autonomous system. It provides a low overhead method for routers to advertise themselves as default routers. It also provides a low overhead method for nonrouters to solicit the local network for existence of routers and add to their list of default routers the addresses of any routers that respond.
The following distinguishing features are provided by the IRD protocol:
One of the most widely used interior gateway protocols is the Routing Information Protocol (RIP). RIP is an implementation of a distance-vector, or Bellman-Ford, routing protocol for local networks. It classifies routers as active and passive (silent). Active routers advertise their routes (reachability information) to others; passive routers listen and update their routes based on advertisements but do not advertise. Typically, routers run RIP in active mode, while hosts use passive mode.
A router running RIP in active mode broadcasts updates at set intervals. Each update contains paired values where each pair consists of an IP network address and an integer distance to that network. RIP uses a hop count metric to measure the distance to a destination. In the RIP metric, a router advertises directly connected networks at a metric of 1. Networks that are reachable through one other gateway are two hops. Thus, the number of hops or the hop count along a path from a given source to a given destination refers to the number of gateways that a datagram would encounter along that path. Using hop counts to calculate shortest paths does not always produce optimal results. For example, a path with hop count of 3 that crosses three Ethernets may be substantially faster than a path with a hop count of 2 that crosses two slow-speed serial lines. To compensate for differences in technology, many routers advertise artificially high hop counts for slow links.
The routing daemons that run RIP dynamically build on information received through RIP updates. When started up, the daemon issues a REQUEST for routing information and then listens for responses to the request. If a system configured to supply RIP hears the request, it responds with a RESPONSE packet based on information in its routing database. The RESPONSE packet contains destination network addresses and the routing metric for each destination.
When a RIP RESPONSE packet is received, the routing daemon takes the information and rebuilds the routing database, adding new routes and "better" (lower metric) routes to destinations already listed in the database. RIP also deletes routes from the database if the next router to that destination says the route contains more than 15 hops, or if the route is deleted.
All routes through a gateway are deleted if no updates are received from that gateway for a specified time period. In general, routing updates are issued every 30 seconds. In many implementations, if a gateway is not heard from for 180 seconds, all routes from that gateway are deleted from the routing database.
RIP Version 2 (more commonly known as RIP II) adds additional capabilities to RIP. Some of these capabilities are compatible with RIP I and some are not. To avoid supplying information to RIP I routes that could be misinterpreted, RIP II can only use incompatible features when its packets are multicast. On interfaces that are not capable of IP multicast, RIP-I-compatible packets are used that do not contain potentially confusing information.
Some of the most notable RIP II enhancements are:
Although next hop information is provided
in RIP I-compatible RIP II packets,
RIP I routers ignore next hop information in
RIP II packets. This may result in packets crossing a
network twice, which is the default behavior
with RIP I.
While RIP I routers will ignore the network mask in RIP II packets, their calculation of the network mask will quite possibly be wrong. For this reason, RIP I-compatible RIP II packets must not contain networks that would be misinterpreted. These networks must only be provided in native RIP II packets that are multicast.
The Open Shortest Path First (OSPF) protocol is a shortest path first (SPF) or link-state protocol. OSPF is better suited than RIP for complex networks with many routers.
OSPF is an interior gateway protocol that distributes routing information between routers in a single autonomous system (AS). OSPF chooses the least cost path as the best path. Suitable for complex networks with a large number of routers, OSPF provides equal cost multipath routing where packets to a single destination can be sent via more than one interface simultaneously. In a link-state protocol, each router maintains a database describing the entire AS topology, which it builds out of the collected link-state advertisements of all routers. Each participating router distributes its local state (that is, the router's usable interfaces and reachable neighbors) throughout the AS by flooding. Each multi-access network that has at least two attached routers has a designated router and a backup designated router. The designated router floods a link-state advertisement for the multi-access network and has other special responsibilities. The designated router concept reduces the number of adjacencies required on a multi-access network.
OSPF allows networks to be grouped into areas. Routing information passed between areas is abstracted, potentially allowing a significant reduction in routing traffic. OSPF uses four different types of route, listed here in order of preference: intra-area, inter-area, type 1 external, and type 2 external. Intra-area paths have destinations within the same area, inter-area paths have destinations in other OSPF areas, and Autonomous System External (ASE) routes are routes to destinations external to the AS. Routes imported into OSPF as type 1 routes are supposed to be from internal gateway protocols whose external metrics are directly comparable to OSPF metrics. When a routing decision is being made, OSPF will add the internal cost to the AS border router to the external metric. Type 2 ASEs are used for exterior gateway protocols whose metrics are not comparable to OSPF metrics. In this case, only the internal OSPF cost to the AS border router is used in the routing decision.
From the topology database, each router constructs a tree of the shortest paths with itself as the root. This shortest-path tree gives the route to each destination in the AS. Externally derived routing information appears on the tree as leaves. The link-state advertisement format distinguishes between information acquired from external sources and information acquired from internal routers, so there is no ambiguity about the source or reliability of routes. Externally derived routing information (for example, routes learned from EGP or BGP) is passed transparently through the autonomous system and is kept separate from OSPF's internally derived data. Each external route can also be tagged by the advertising router, enabling a passing of additional information between routers on the borders of the autonomous system.
OSPF optionally includes type of service (TOS) routing and allows administrators to install multiple routes to a given destination for each type of service (for example, low delay or high throughput). A router running OSPF uses the destination address and the type of service to choose the best route to the destination.
OSPF intra- and inter-area routes are always imported into the gated routing database with a preference of 10. (See ``gated preferences and route selection'' for a discussion of preferences.) It would be a violation of the protocol if an OSPF router did not participate fully in the area's OSPF, so it is not possible to override this. Although it is possible to give other routes lower preference values explicitly, it is ill-advised to do so.
OSPF areas are connected by the backbone area, the area with identifier 0.0.0.0. All areas must be logically contiguous and the backbone is no exception. To permit maximum flexibility, OSPF allows the configuration of ``virtual'' links to enable the backbone area to appear contiguous despite the physical reality.
All OSPF protocol exchanges are authenticated. Authentication guarantees that routing information is imported only from trusted routers to protect the Internet and its users. A variety of authentication schemes can be used, but a single scheme must be configured for each area. This enables some areas to use much stricter authentication than others.
All routers in an area must agree on that area's parameters. A separate copy of the link-state algorithm is run for each area. Because of this, most configuration parameters are defined on a per-area basis. All routers belonging to an area must agree on that area's configuration. Misconfiguration will lead to adjacencies not forming between neighbors, and routing information might not flow or even loop.
OSPF is described in RFC 1583. The MIB is defined in RFC 1253. Other related documents are RFC 1245, RFC 1246, and RFC 1370.
The Exterior Gateway Protocol (EGP) is an exterior routing protocol used for exchanging routing information with gateways in other autonomous systems. Unlike interior protocols, EGP propagates only reachability indications, not true metrics. EGP updates contain metrics, called distances, which range from 0 to 255. gated will only compare EGP distances learned from the same AS.
Originally EGP reachability information was passed into ARPANET/MILnet ``core'' gateways where the best routes were chosen and passed back out to all connected autonomous systems. As the Internet moved toward a less hierarchical architecture, EGP, an exterior routing protocol which assumes a hierarchical structure, became less effective.
Before EGP sends routing information to a remote router, it must establish an adjacency with that router. This is accomplished by an exchange of Hello (not to be confused with the HELLO protocol, or OSPF HELLO messages) and I Heard You (I-H-U) messages with that router. Computers communicating via EGP are called EGP neighbors, and the exchange of Hello and I-H-U messages is referred to as acquiring a neighbor. Once the neighbor is acquired, the system polls the neighbor for routing information. The neighbor responds by sending an update containing routing information. If the system receives a poll from its neighbor, it responds with its own update packet. When the system receives an update, it includes routes from the update into its routing database. If the neighbor fails to respond to three consecutive polls, gated assumes that the neighbor is down and removes the neighbor's routes from its database.
The EGP protocol is described in RFC 827 and RFC 904.
The Border Gateway Protocol (BGP) is an exterior routing protocol used for exchanging routing information between autonomous systems. BGP is used for the exchange of routing information between multiple transit autonomous systems as well as between transit and stub autonomous systems. BGP is related to EGP but operates with more capability, greater flexibility, and less required bandwidth. BGP uses path attributes to provide more information about each route, and in particular maintains an AS path, that includes the AS number of each autonomous system the route has transited, providing information sufficient to prevent routing loops in an arbitrary topology. Path attributes also include an origin parameter that indicates whether the source of the routing information is from within the autonomous system of the sending gateway (igp), external from the autonomous system (egp), or from some other source (incomplete). Path attributes may be used to distinguish between groups of routes to determine administrative preferences, allowing greater flexibility in determining route preference to achieve a variety of administrative ends.
BGP supports two basic types of session between neighbors, internal (sometimes referred to as IBGP) and external. Internal sessions are run between routers in the same autonomous system, while external sessions run between routers in different autonomous systems. When sending routes to an external peer, the local AS number is prepended to the AS path. Hence, routes received from an external peer are guaranteed to have the AS number of that peer at the start of the path. A route received from an internal neighbor will not in general have the local AS number prepended to the AS path, and hence, will in general have the same AS path that the route had when the originating internal neighbor received the route from an external peer. Routes with no AS numbers in the path may be legitimately received from internal neighbors; these indicate that the received route should be considered internal to your own AS.
The BGP implementation supports two versions of the BGP protocol: Versions 2, and 3. BGP Versions 2 and 3 are quite similar in capability and function. They will only propagate classed network routes, and the AS path is a simple array of AS numbers.
External BGP sessions may or may not include a single metric, which BGP calls the Multi-Exit Discriminator (MED), in the path attributes. For BGP Versions 2 and 3 this metric is a 16-bit unsigned integer. Smaller values of the metric are to be preferred. Currently, this metric is used only to break ties between routes with equal preference from the same neighbor AS. Internal BGP sessions carry at least one metric in the path attributes, which BGP calls the LocalPref. The size of the metric is identical to the MED. For BGP Versions 2 and 3, this metric is considered better when its value is smaller.
BGP collapses routes with similar path attributes into a single update for advertisement. Routes that are received in a single update will be readvertised in a single update. This minimizes the churn caused by the loss of a neighbor and maximally compresses the initial advertisement sent during peer establishment. BGP does not read information from the kernel message-by-message but fills the input buffer. It processes all complete messages in the buffer before reading again.
All unreachable messages are collected into a single message and sent prior to reachable routes during a flash update. For these unreachable announcements, the next hop is set to the local address on the connection, no metric is sent, and the path origin is set to incomplete. On external connections, the AS path in unreachable announcements is set to the local AS; on internal connections the AS path is set to zero length.
The BGP implementation expects external peers to be directly attached to a shared subnet and expects those peers to advertise next hops that are host addresses on that subnet (though this constraint can be relaxed by configuration for testing). For internal peers, however, there are two alternatives that may be selected from by specifying the ``internal'' or ``igp'' group type. See ``gated BGP protocol statement'' for a discussion of specifying group types.
When group type ``internal'' is specified, BGP expects all peers in the group to be directly attached to a shared subnet so that, like external peers, the next hops received in BGP advertisements may be used directly for forwarding. When group type ``igp'' is specified, BGP expects routes from the peers in the group not to be used for forwarding at all. Instead, they expect that copies of the BGP routes received will also be received via an IGP (interior gateway protocol such as RIP) and that the BGP routes will only be used to determine the path attributes associated with the IGP routes. Such groups also support distant peers and also need to be informed of the IGP they are running with.
For ``internal'' BGP group types (and for ``test'' groups), where possible, a single outgoing message is built for all group peers based on the common policy. A copy of the message is sent to every peer in the group, with possible adjustments to the next hop field as appropriate to each peer. This minimizes the computational load of running large numbers of peers in these types of groups. BGP allows unconfigured peers to connect if an appropriate group has been configured with an allow clause.
BGP Version 1 is described in RFC 1105, Version 2 in RFC 1163, and Version 3 in RFC 1267. The Version 3 MIB is described in RFC 1269. The two documents, RFC 1164 and RFC 1268, describe the application of Versions 2 and 3 in the internet. A protocol analysis of and experience with BGP Version 3 are available in RFC 1265 and RFC 1266. RFC 1397 talks about advertising a default route in BGP Versions 2 and 3. RFC 1403 describes BGP-OSPF interaction.