Section 7.5. Interdomain Routing Protocols

7.5. Interdomain Routing Protocols

Unlike intradomain routing protocols, interdomain routing protocols create a network of networks, or an internetwork . Interdomain routing protocols route packets outside of a defined domain. Each domain consists of several networks and routers that can be accessed publicly . Figure 7.8 shows an example of internetworking, in which a packet at router R ₁ faces two defined larger service provider domains, A and B. Each service domain is shown by a number of interconnected circles, each representing a network or a router. Obviously, at router R ₁ , finding the best path for a packet to go to which domain is a challenge. The Border Gateway Protocol helps meet this challenge.

Figure 7.8. Internetworking, in which router packet faces two defined service domains

7.5.1. Border Gateway Protocol (BGP)

The Border gateway protocol (BGP) is a preferred routing protocol for interdomain communications and TCP/IP connections. BGP allows routers to carry specific policies or constraints that they must meet. With BGP, routers exchange more comprehensive information about routes to a certain destination instead of simply costs and the best link. In BGP, two contributing routers can exchange routing information even if they are located in two different autonomous systems. When an external destination is chosen , a router sends the information to all internal neighbors. Then, all routers decide whether the new route is possible, and if so, the new route is added to the router's database. Thus, the new update message is propagated. One of the most important techniques in BGP is path-vector routing.

Path-Vector Routing

RIP and OSPF are not suitable for interdomain routing protocols. As discussed earlier, distance vector routing is used to send information to each of a router's neighbors, and then each router builds up a routing database. However, a router is not aware of the identity of routers on any particular path. Two problems arise. First, if different routers give different information to an assigned cost, it is impossible to have stable and loop-free routes. Second, an autonomous system can have limitations about which specific autonomous system should be used. This is true while the distance vector algorithm has no information about the autonomous systems.

Each router sends its link cost to all other routers and then starts routing calculations. Two issues can arise in link-state routing. First, different independent systems can use different costs and have different limitations. The link-state protocol allows a router to make the topology, and its metrics may be different for each independent system. In this case, it is impossible to create a reliable routing algorithm. Second, when flood routing occurs, the use of an interdomain routing protocol across the independent system can be unstable.

To resolve these issues, consider an alternative solution: the path vector routing protocol , which provides information about how to reach a network given a certain router and identifies which autonomous system (or domain) should be visited, as in the case for router R ₁ in Figure 7.8. The path vector routing protocol is different from the distance vector algorithm, in which each path has information about cost and distance. In the path vector routing protocol, these packages of information are not included, and all visited autonomous systems and all components of domain A in Figure 7.8 reaching the destination network are listed in each routing information package. Thus, a router can be programmed to refuse the acceptance of a particular path if the information about the path is not included in the package it receives.

Details of BGP

BGP was created to find a solution to interdomain routing among autonomous (in-dependent) systems. BGP works well for making a connection when a long-haul TCP session must be established. BGP has three functional components:

Neighbor relationship
Neighbor maintenance
Network maintenance

The neighbor relationship refers to an agreement between two routers in two different autonomous systems to exchange routing information on a regular basis. A router may reject its participation in establishing a neighbor relationship for several reasons, such as the rule of the domain, overload, or a temporary malfunctioning of external links. Neighbor maintenance is a process of maintaining the neighbor relationship already established. Normally, each corresponding router needs to find out whether the relationship with the other router is still available. For this reason, two routers send keep- alive messages to each other. The last BGP process is network maintenance. Each router keeps the database of the subnetworks that it can reach and tries to get the best route for that subnetwork.

BGP Packets

There are four different BGP packets as shown in Figure 7.9, as follows :

Open packet. This packet requests establishment of a relationship between two routers.
Update packet. This packet conveys update information about routes.
Keep-alive packet. Once a relationship between two routers is established, this packet confirms its neighbor relationship frequently.
Notification packet. This packet is used when an error occurs.

Figure 7.9. Four types of BGP packets and their fields: (a) open packet, (b) update packet, (c) keep-alive packet, and (d) notification packet

Figure 7.10 shows a BGP connection. Assume that router R ₂ in one Internet service provider, network 2 opens a TCP connection to its desired router, R ₃ , in another ISP domain of network 3. Router R ₂ sends an open packet to R ₃ . This packet is identified by R ₃ , telling it which domain the sender belongs to. A router sends a keep-alive packet to its neighbors to prevent an agreed hold time from expiring.

Figure 7.10. Use of BGP in an interdomain routing protocol

The first type of update packet can include the information of a single route that passes through a network. This information can be divided into three fields: the network-layer readability field, the path attributes field, and the total path attributes length field. The network-layer readability field has a list of subnetwork identifiers that can be found by the router. The path attributes field has a list of attributes that can be referred to a specific route. The second type of update information is used to remove one or more routes identified by the IP address of the destination subnetwork. In this case, the notification packet is sent in case of an error, which may be authentication errors, validity errors in the update packet, or an expired hold-time error.