Principles Digital Communication System & Computer Networks (Charles River Media Computer Engineering)

21.13 ROUTING BETWEEN AUTONOMOUS SYSTEMS

The Internet is a network of a large number of autonomous systems. A host connected to one autonomous system can communicate with another host connected to another autonomous system only when the routing information is shared between the two autonomous systems. The protocols used for sharing the routing information are exterior gateway protocol (EGP) and border gateway protocol (BGP).

On the Internet, routing between two autonomous systems is done through exterior gateway protocol (EGP) or border gateway protocol (BGP).

21.13.1 Exterior Gateway Protocol

As shown in Figure 21.7, two routers each belonging to a different autonomous system share routing information using the exterior gateway protocol (EGP). These routers are called exterior routers. Conceptually, EGP works as seen in Figure 21.7.

• A router acquires a neighbor by sending a hello message. The neighbor responds to the hello.

• The two routers periodically exchange messages to check whether the neighbor is alive. The Internet being very dynamic, there is no guarantee that today's neighbor is there tomorrow. Whenever there is any change in the routing information within the autonomous system, the information is conveyed to the other router through routing update messages.

Figure 21.7: Exterior gateway protocol.

EGP has the following restrictions:

• An exterior router conveys only reachability information. It does not ensure that the path is the shortest.

• An exterior router can announce only the routing information to reach the networks within the autonomous system, not some other autonomous system.

• EGP can advertise only one path to a given network, even if alternate paths are available.

The EGP message consists of a header and parameters fields. The header has the following fields:

Version (8 bits): Specifies the version number of EGP.

Type (8 bits): Specifies the type of message. The message types are:

• Neighbor acquisition messages (type 3)

• Neighbor reachability messages (type 5)

• Poll request messages (type 2)

• Routing update messages (type 1)

• Error

Code (16 bits): Specifies the subtype of the message. For example, type 3 messages have the following codes:

• Acquisition request (code 0) to request for neighborhood

• Acquisition confirm (code 1) to accept neighborhood

• Acquisition refusal (code 2) to refuse neighborhood

• Cease request (code 3), request for termination of neighborhood

• Cease confirm (code 4), confirmation to cease request

Neighbor reachability messages (type 5) messages have the following codes:

• Hello request message (code 0)

• I heard you message (code 1)

Periodically, the neighbors exchange the routing tables using the type 1 message format, with code as 0. The parameters field contains a list of all routers on the network and the distance of the destination for each.

Using this simple protocol, the Internet attained its great flexibility. An autonomous system can enter into an arrangement with a neighbor to share the routing information without the need for a central authority to control the connectivity between various internets. However, because of the limitations mentioned, a new protocol, border gateway protocol, has been developed.

In EGP, two routers establish a neighborhood relationship and keep exchanging the routing information. Hence, there is no need for a centralized system to send routing information to different routers.

21.13.2 Border Gateway Protocol

Routers connected to different autonomous systems can exchange routing information using BGP, the latest version being BGP Version 4. As compared to EGP, BGP is a complex protocol. We will illustrate the functioning of BGP through an example.

Figure 21.8 shows how BGP is used between autonomous systems. Assume that AS#1 and AS#2 are two autonomous systems that need to share routing information. AS#2 is connected to two other autonomous systems: AS#3 and AS#4. AS#1 will have one router designated as a BGP speaker, which has the authority to advertise its routing information with other routers. Similarly, AS#2 will have a BGP speaker.

Figure 21.8: Border gateway protocol.

In BGP, each autonomous system will have a BGP speaker that is authorized to advertise its routing information. This BGP speaker sends information about all the autonomous systems that can be reached via its routers.

The BGP speaker of AS#2 will send the reachability information to the BGP speaker of AS #1. This reachability information includes all the other autonomous systems that can be reached via its routers—in our example, the autonomous systems AS#3 and AS#4. It is this feature that gives complexity to the BGP, but the advantage is that the complete reachability information is obtained by AS#1.

It may happen that because of the failure of a link between AS#2 and AS#3, for example, AS#3 becomes unreachable temporarily. The BGP will also give negative advertisement by sending information about the routes that have been withdrawn.

It is the BGP that is making the Internet a dynamic network. When new networks are added to the Internet, a user can access the new network with the BGP without a centralized administrative authority.