7.1.1 Hosts vs Gateways

The present day router, which was earlier commonly known as the gateway, has multiple interfaces and can forward packets across interfaces. A host is differentiated from a router by its inability to send packets across its interfaces. The present‐day hosts can be configured to act as routers as well by simultaneously taking up the processing work of the host and the packet‐forwarding activity of the router. Even though a host may have multiple interfaces, it should not be configured by default to act as a router in parallel. A network should preferably separate the functionality of host and router for the following reasons:

• The host computers have application software running on them with an interface for the user and provide various services to the user. The router has networking services running in it with the aim of interconnecting networks.
• The number of hosts in a network is too huge as compared with the number of routers. The routers are involved in exchange of routing information among themselves. If all the hosts simultaneously act as routers, the amount of routing information exchanged will be too huge and will lead to bandwidth, memory, and processing constraints.
• The host computers generally have application software running on them, while the routers have a networking operating system and the routing protocols installed in it. Upgrade of the routing protocol would be easier if the version upgrade or patches had to be applied only on the routers and not on all the hosts.
• Routers are meant for 24 × 7 operations, while the hosts are used on demand. Participation of the hosts in routing and their frequent switching on and off will lead to regular change in the topology, making the network initiate the route update process. It will be very difficult for the network to converge.
• There are certain protocols and processes that have a separate policy for communication between host, communication between the routers, and communication between a router and a host. An example of router‐to‐host communication is the ‘redirect mechanism’, which is explained in the following section to indicate the need to separate host from router.

7.1.2 Gateway‐to‐Gateway Protocol

The Gateway‐to‐Gateway Protocol was developed in 1982 by BBN Inc. for DARPA and set out in RFC 823 [4, 6]. Although the protocol is not in use any more, it was a stepping stone in the development of the present‐day distance vector protocols. GGP was used for communication of reachability and routing information only between the gateways, i.e. the core routers, and hence was given the name Gateway‐to‐Gateway Protocol.

In the early Internet architecture there were core routers connected with each other, which acted as the backbone, and non‐core routers were connected to the core routers to provide Internet connectivity to the local network [7]. The routing protocol that was used among the core routers was GGP. The system of core routers for the Internet backbone as well as the GGP, which was the routing protocol used in it, is now obsolete. But the working of GGP gives an idea of the evolution of routing. GGP can be taken as an example of a distance vector protocol with hop count as the metric.

When a GGP router boots up, it tries to discover its neighbors by sending a GGP echo message to all its neighbors at a regular predefined frequency, which is generally 15 s. The GGP neighbors receiving the GGP echo respond by sending a GGP echo reply message. When the GGP router that has sent the GGP echo message receives K‐out‐of‐N GGP echo [8] replies from a neighbor, where K is the number of GGP echo replies sent by the destination neighbor router and N is the number of GGP echo messages sent by the originating router (generally, K = ½ N or K = ¾ N), the neighbor is considered to be connected and the link is treated as ready for communication.

The routing update message that is shared by the GGP routers contains the following two pieces of information – N and D, i.e. the IP address of the networks that are connected through the router (N) and the distance (D) to that network in terms of number of hops required to reach that router. This information is sent to the neighbors, sorted in groups based on hop counts, i.e. the group of neighbors at a hop distance of 1 from the GGP router, then the group of neighbors at a hop distance of 2 from the router, and so on. The GGP router that receives this update information compares this information individually for each of the network entries already available in it and updates the routing table if a low hop count path has been received through the neighbor or information about any new connected network has been received. The update message received from a neighbor carries a sequence number to avoid processing of outdated or duplicate information. On receiving an update message that has a new and higher sequence number than the one already processed by the receiving GGP router from the originating BGP neighbor, the GGP router sends a positive acknowledgement message. This acknowledgement message sent back to the originating neighbor GGP router also carries the sequence number of the received update message. If an update with a lower sequence number is received, the message is ignored and a negative acknowledgement is sent back to the originating neighbor. The negative acknowledgement message also carries with it the sequence number of the last correctly received message and not the sequence number of the last received update message.

Thus, GGP was a simple routing protocol with only four types of message – echo request, echo reply, acknowledgement, and routing update. Whenever there was a change in topology, the network had to exchange update messages and allow time for the propagation of topology change information across the entire network, and thereafter the network would converge. GGP being a protocol used over slow‐speed links with lesser reliability, a slow convergence process was a major drawback of the protocol.

7.1.3 Autonomous System

An autonomous system (AS) [9] is formed by a collection of networks that are under the administrative control of a single organization. As it comprises a collection of routers forming the network, the AS is also referred to as the routing domain. The routers within an AS generally follow the same routing policy, and they may implement the same or different routing protocols for internal routing.

The Interior Gateway Protocol (IGP) is used for routing within an AS, while the Exterior Gateway Protocol (EGP) is used for routing between ASs [10] on the Internet backbone.

EGP is used for routing in a wide area network supported by a number of Internet service providers (ISPs). EGP supports routing among different service provider networks. EGP supports redundancies in the network paths by implementing routing policies supporting transfer of data through different ISPs simultaneously. It can also implement load balancing of traffic by distributing data over two or more different paths. The EGP can scale to extremely huge networks such as the Internet.

EGP connects two gateway hosts each having its own border router by enabling exchange of information in a network of autonomous systems. The neighboring EGP routers, each belonging to a separate AS, exchange routing tables for inter‐AS routing. Inter‐AS routing is also referred to as interdomain routing. The routing tables exchanged between the routers have entries giving the list of reachable routers, their addresses, and the path cost associated with reaching a router.

AS identifier. The EGP should be able to identify and distinguish between ASs, and so there should be unique AS identifiers. Each AS that is connected to the public domain through the Internet is assigned a 16 bit identifier by the Internet Assigned Numbers Authority (IANA). The AS identifier allocated by IANA has a value ranging between 1 and 65 535. RFC 4893 and RFC 5398 propose an increase in the AS identifier pool range by converting it from 16 bit to 32 bit size. The AS connecting to a single ISP may use an AS identifier from a private pool as the identification has to be mutually agreed only between the ISP and the organization. But an organization connecting to multiple ISPs over the Internet requires the AS identifier from the IANA‐assigned pool. IANA does not allocate an AS identifier directly to the organization’s AS, but through the five Regional Internet Registries (RIRs) [11], each of which is responsible for the assignment of the AS number in its geographical region. Each RIR has a huge geographic region under its coverage so as to cover the entire world. Presently the five RIRs are:

• African Network Information Center (AFRINIC)

  [Africa, portions of the Indian Ocean]

• Asia‐Pacific Network Information Center (APNIC)

  [portions of Asia and Oceania]

• American Registry for Internet Numbers (ARIN)

  [United States, Canada, and many Caribbean and North Atlantic islands]

• Latin America and Caribbean Network Information Center (LACNIC)

  [Latin America, portions of the Caribbean]

• Réseaux IP Européens Network Coordination Center (RIPE NCC)

  [Europe, Middle East and Central Asia]

Unlike Interior Routing Protocol, the path selection in EGP is not based on minimizing the path cost between two ASs. The routing policy between ASs is based on a number of other parameters [12‐16]. As each AS is under the administrative control of a separate ISP or organization, there may be varying relationships between the organizations. Moreover, there might also be an assured level of service agreement between the organizations. A certain level of secrecy regarding the internal network of the organization has also to be kept, and the internal topology of the network should not be shared with another organization. Taking all this into consideration, the path metrics are based on a set of policies that differ for each AS. The administrator of the AS defines the path metrics between the AS and its neighbors so that they satisfy the assured level of parameters. The policy may even impose restrictions on disclosing certain routes to its neighboring ASs. An AS may have a different routing policy for each of the neighboring ASs connected to it. Thus, the routing policy may not necessarily have a technical foundation but be based on political, organizational, security, maintenance, or management reasons. To enable EGP to detect the organization, it carries the customer prefixes or the Internet prefixes during routing. The router sends this routing table to its neighbors in response to a request received from them. Generally, a router requests its neighbors every 2–8 min to send the routing table entries.

The router participating in EGP routing is also known as the Internet facing router and requires the following information [11] to perform the routing:

• A list of neighbor routers for exchange of routing information. These neighbor routers will belong to different ASs.
• A list of networks to advertise as directly connected. This may be different from the list of ASs to which it is actually connected owing to organizational policy and security.
• The identifier of the AS to which it belongs.

EGP can be described as a policy‐based routing, as the AS administrator defines the policies on whose basis a packet received from a particular source may be forwarded to the required destination. In the policy‐based routing used in EGP, multiple packets received at an AS for the same destination may be forwarded through different routes or even multiple routes with a varying number of replicas for each packet, based on the predefined routing policy. The policy may be based on the address of the source from which the packet has been received or any intermediate AS through which the packet has travelled. The intermediate ASs play an important role in policy‐based routing, which is very particular about the security aspect as the packet may have passed through a non‐friendly AS and might be bugged or prepared for an attack or sniffing. The policies are also based on the size of the payload, the status of flags in the packet header, the protocol of the packet, hops, and timers.

7.1.4 Characteristics of EGP

The three significant characteristics [2] of the EGP are as follows:

• Independence of operation. The EGP provides independence of operation not only to all autonomous systems with the routers running in it but also to the gateway routers. An autonomous system is provided freedom from the other autonomous systems on the Internet or the routers therein. The routers within an AS are not dependent on EGP or on the routers located in other ASs for data transmission within the AS or even beyond that. The gateway router takes care of data transmission beyond the AS. The EGP also provides freedom of operation to the gateway router as the frequency of receiving updates is not dictated by the protocol or any other AS or gateway router. The gateway router itself negotiates the parameter specifying the frequency of receiving updates from neighboring ASs. The gateway router cannot be interrupted with updates from other gateway routers other than those already agreed to at the predefined frequency.
• Association of metrics with each independent path. EGP is based on distance as well as vector, i.e. direction from the source towards the destination. The metric is associated with each independent route. In a normal distance–vector routing, the cost of the destination from the source is maintained without entry of any intermediate routers, whereas in EGP the reachability from source to destination is associated with the sequence of intermediate gateway routers in the path and the associated metric. EGP maintains the information about various paths from source to destination, and hence it should know the cost associated with each path. EGP can send different packets through different paths or even the same packet from different routes, and hence the protocol should be able to select the route. Therefore the protocol maintains a metric specifying that the destination can be reached from the source via an intermediate gateway ‘X’ with a certain metric and can reach the same destination from the same source through another gateway ‘Y’ with another metric, and so on, to enable information about all available route metrics.
• Domination of reachability over routing. In an exterior gateway, all destinations with a metric of non‐infinity are termed reachable. EGP does not specify a common technique to compare one route with another based on metrics. Although an update received by a gateway has a metric in it, this is rarely used to compare one route with another. Moreover, the path for forwarding a packet from source to destination is not distinctively selected on the basis of the metric. Neither is the path changed, even when a burst of packets are being sent from source to destination and during the transmission an update is received indicating an alternative path with much better metrics. The routing architecture of the Internet does not have common criteria for metrics interpretation.

Border Gateway Protocol (BGP) is the most common EGP protocol in use across the Internet by all ISPs. A protocol also exists by the name of EGP, which was specified in RFC 827 and RFC 904 and was used to connect the autonomous systems over the Internet in the 1980s, much earlier than BGP. Thus, EGP in general refers to the class of protocols for interdomain routing, and BGP and EGP are the two most familiar routing protocols of this class. BGP version 4 is the common protocol being run by the Internet facing routers forming the backbone for the Internet, and this has replaced EGP version 3, which was used to interconnect ASs in the initial years of the Internet.

7.2.1 Evolution of EGP Standards

The EGP was first documented in RFC 827, published in October 1982, with the aim of creating specifications for communication between gateways. Some of these gateways may not even have been trusted or known by the other communicating gateways. The RFC had introduced the requirements and limitations of EGP, and it was known as EGP version 1. The RFC described the process for neighbor acquisition, a technique for detecting neighbor connectivity using ‘hello’ and ‘I heard you’ messages, and called this process neighbor reachability. Specifications for exchange of neighbor reachability messages (polling) and the process to send neighbor reachability messages were also mentioned. The RFC also defined the term ‘indirect neighbor’ and indicated its difference from a direct neighbor. Although RFC 827 defined the ‘stub gateway’ and its communication with core gateways, RFC 888 was released in January 1984 exclusively to explain in detail the neighbor acquisition, neighbor reachability, message formats, and polling for EGP‐based connectivity of a stub gateway to a core router. RFC 888 marked the beginning of version 2 of EGP. RFC 904 published in April 1984 was an improvement of RFC 827 and RFC 888, and this was the final and formal set of specifications of Exterior Gateway Protocol (version 2) that was in use before the BGP replaced it.

When the Internet was initially designed, it was planned that the connectivity would form a tree structure. The core routers were designated to form the root of the tree, and the non‐core routers would be connected in a hierarchical architecture with the root of the tree. However, the present inter‐AS linking with mesh structure disrupted the planned tree structure, and hence deviated from the basic topology over which the EGP was designed. EGP, being designed for a tree structure, had no provision for loop avoidance in any arbitrary topology, which was one of the major reasons for BGP taking over from EGP.

7.2.2 EGP Terminology and Topology

EGP routers that are neighbors of a particular EGP router are known at its peers. The peers can be internal or external, i.e. peers within the same AS or in different ASs. The EGP does not have a defined mechanism for neighbor discovery by itself. The IP address of each router has to be manually configured and the connectivity established between the neighbors to make the network ready for routing of packets between them. However, in EGP, two neighboring EGP routers may not necessarily share a common link, i.e. two EGP routers may not be directly connected with each other, but through one or more in‐between non‐EGP routers. Based on the number of external peers in different ASs to which a gateway is connected, it is classified as a stub gateway or a core gateway [19, 20]. A stub gateway is connected to only one AS other than the AS to which it belongs. There may be only one link to the other AS or multiple links from the stub gateway to the same or different gateways in that external AS. The core gateways connect to more than one external AS. In EGP, the stub gateway can forward updates related only to its network, while the core gateway can forward updates related to its network as well as the information learnt from other gateways. However, both core gateways and stub gateways can receive updates from external gateways.

7.2.3 EGP Operation Model

An EGP router will always be in one of the following states – idle, acquisition, down, up, or cease. There are ten different messages that are exchanged between the routers in various states, and, based on the message received or sent, the router changes its state or continues to remain in its present state. These messages are:

• request,
• confirm,
• refuse,
• cease,
• cease‐ack,
• hello,
• I‐H‐U,
• poll,
• update,
• error.

The various messages that a state can receive and the messages or responses that an EGP router sends out when it is in a particular state are depicted in Table 7.1.

A gateway is initially in the idle state when it does not receive any message except the cease message, which it may optionally receive and respond with a cease‐ack. The router is brought from the idle state to the acquisition state by a trigger, which can either be system generated or manual in the form of a request command or start event. When moving to the acquisition state from the idle state, the router sends a request command to its neighbors and thereafter periodically keeps sending the request command to its neighbors until it receives a confirm response. On receiving a confirm response, it moves to the down state, and on receiving a refuse response from the neighbor it moves back to the idle state. The router can also move directly from the idle state to the down state on receiving a request command.

When the router is in the down state, it accepts request messages, cease messages, and hello messages and responds to them. It also receives confirm messages, which it receives in response to the request messages sent by it. The router may also periodically send hello messages in this state, as well as receive unsolicited updates.

A neighbor reachability protocol working in EGP declares the router to be in the up state. The router in the up state can receive and respond to all types of EGP message.

The router can come to the cease state from the acquisition state, the up state, or the down state by sending a cease command to the router in that state. If the router in the cease state receives a cease‐ack message or another cease message, it moves to the idle state.

When two gateways enter into a neighbor relationship, one of them becomes the active neighbor and the other becomes the passive neighbor. The active neighbor can only send various request messages such as an acquisition request and hello message, while the passive neighbor can only respond to these messages, and it cannot send these messages to the active neighbor. However, both neighbors can send a cease message or respond to it by sending a cease‐ack message.

EGP does not describe the process of neighbor discovery and hence it is generally configured manually. Once an EGP router establishes connection with its neighbor, it has to keep checking regularly whether the neighbor is still connected and reachable. This is done by sending a hello message to the neighbor and receiving back an I‐H‐U reply message from the neighbor. If a poll message or update message is received in‐between, it can also be treated as a reachability confirmation message between the neighbors and used in lieu of hello and I‐H‐U for that reachability confirmation cycle.

To update its routing table, the router sends a poll message to its reachable neighbor. The neighbor responds by sending an update message, which contains the details of the networks reachable from it. This is used by the router that sent the poll message to update its routing table entries.

The router sends an error message in response to any message received by it that is not as per the defined format for the header or data field. An error message is also sent if it receives ‘poll’ or ‘hello’ messages above a maximum rate. Any of the neighbors can decide to cease the connection with or without giving a reason for disconnection.

7.3.1 Router Connectivity and Terminology

To participate in BGP routing, each AS should have at least one router running BGP. An AS may also have more than one router running BGP, and these routers may even communicate within the AS using BGP. A router running BGP is also referred to as a BGP speaker. However, the BGP speaker may not necessarily be a router, but it can be a host terminal running some other protocol, e.g. a static routing protocol to pass on BGP information received by it to some other BGP router. A boundary router in an AS is a router that connects an AS to another AS. Not all routers running BGP in an AS may be boundary routers, as only a selected few of the BGP running routers in an AS may be connected to some other AS. There may also be a few BGP running routers in the AS that are connected only to other BGP routers in the same AS but not in any other AS. In contrast to the boundary routers, the routers in an AS that connect only to routers within the same AS but not to any router in other ASs are known as internal routers. The other BGP routers to which a BGP router is directly connected are known as its neighbors. The neighbors of a BGP router can thus be in the same AS or in different ASs. The neighbors that are in the same AS are known as internal peers, and BGP communication between these internal peers is referred to as internal BGP. Thus, the routers participating in internal BGP will have the same AS number. Analogous to this, the neighbors of a BGP running router in another AS are referred to as external peers, and BGP communication between the external peers is referred to as external BGP. An AS that is connected to only one other AS through a single BGP link is known as a stub AS, while an AS that is connected to two or more other ASs is known as a dual‐homed or multihomed AS respectively. Most of these BGP terminologies are depicted in Figure 7.1 and Figure 7.2.

Topology. A BGP router may be an internal router or it may be a stub or multihomed external router. This conveys that a BGP router may be connected to any number of other BGP routers. Generally, the designers of the network ensure that a router is connected to at least two other routers to ensure path availability even in the case of link failure. The support by BGP to this open‐ended connectivity leads to variation in connectivity architecture between the ASs. As shown in Table 7.2, the boundary routers may be connected in complete mesh, partial mesh, tree, ring, bus/chain, or any other random architecture to enable them to communicate with each other. Adaptability to variation in topology leads to high scalability of the BGP network. Furthermore, BGP also supports dynamic change in topology, i.e. if the link between any two ASs goes down and two other ASs are connected, BGP will discover these changes and rediscover efficient paths. The protocol also ensures that the routing is free from loops.

Bus topology
Ring topology
Star topology
Mesh topology
Partial Mesh Topology

Traffic type and policy. A data packet that originates within an AS or is meant for delivery in the AS is called local traffic, while packets that enter the AS just to pass through it are known as transit traffic. Transit traffic is generated in some other AS and reaches this particular AS as this intermediate AS falls in the path from source AS to destination AS. BGP allows an AS to have variation in routing policy for different types of traffic. An AS may have a policy of not allowing any transit traffic or it may allow transit traffic only from selected ASs while restricting transit traffic from any other AS. The traffic policy may not necessarily be based only on the AS, but may be criteria based. These criteria may be single parameters or a weighted combination of a number of parameters such as the amount of data transferred, the number of hops traversed, the internal load on the routers, the time of the day, the number of available internal paths, and the number of external connections with boundary routers. An AS can also specify how the packets originating in this AS should be handled by the intermediate ASs. It is necessary to allow every AS to have its own policy on transit traffic, because if it is not allowed, there will be certain dual‐homed or multihomed ASs as depicted in Figure 7.3 where the internal network might become choked by transit traffic. But as this policy allows the AS to have a different policy for different transit packets, to save on resources, no AS will like to allow any transit traffic to pass through it. At the same time it will want all other ASs to permit traffic generated by this AS or meant for delivery to this AS to pass through them, and that too on priority. This selfish behavior might lead to deadlocks and blocking of inter‐AS routing. To avoid such situations, necessary arrangements have been made. An AS has mutual agreements with other ASs for transit traffic. In addition to this, there are certain backbone ASs that have the capability to carry a huge volume of traffic at a greater speed, and the ASs connect to these backbone ASs for transit traffic.

Routing. The BGP router maintains routing information to reach other ASs along with the information about the routers in the path. This information is stored in the form of a routing information base (RIB). Routing information is exchanged by each router throughout the network by forwarding it through its neighboring routers. All the BGP routers use this information to find single or multiple paths to other ASs, and also regularly to update this path information. As the packet has to pass through a number of different ASs, similar to path vector routing, BGP has to take into account the information about the intermediate ASs owing to policy and security issues of the originating AS, the forwarding AS, and other ASs in the upcoming path. Thus, the protocol is aware of the entire path and the intermediate ASs before forwarding a packet, and it is not concerned only with the next hop as in the case of distance vector routing. The selection of path by BGP is not simply based on the cost metrics, but is a mix of efficient path selection along with compliance with routing policies across ASs. These policies are based on a number of parameters, each of which may be affected by one or more of the intermediate ASs. Still, BGP cannot guarantee efficient delivery of packets through any particular route as the routing within an AS is not known to the BGP. Every AS has its policy to allow or disallow traffic received from other designated ASs. The internal route traveled by any packet inside an AS may also depend on the originating AS or any particular intermediate AS where the packet might have landed during its traversal.

There are BGP routers connected within an AS as well as BGP routers connected to BGP routers of other ASs. Hence, BGP routing can be categorized [21, 22] into three different scenarios:

1. Intra‐autonomous routing. In an intra‐autonomous routing, the BGP routing is confined within the same AS. The peer routers in intra‐autonomous routing use BGP to have a view of the topology within the AS for effective packet delivery or forwarding the packet inside the AS. The intra‐autonomous routing decides the routers that will act as boundary routers connecting with external peers. This routing can also be used for effective routing within an organization controlling an AS.
2. Interautonomous routing. The interautonomous routing deals with routing between different routers located in separate ASs. The peer routers in this type of routing use BGP to have a view of the Internetwork without having any details about the internal network of any AS. The Internet is the most common and the biggest example of interautonomous routing.
3. Pass‐through routing. When a packet neither has originated in the AS nor is to be delivered within the AS, but rather is just passing through the AS en route from source to destination, it is known as pass‐through routing. In pass‐through routing the intermediate routers generally ensure that the packet is forwarded in such a way that it reaches nearer to its destination. The AS participating in pass‐through routing may not necessarily have BGP running in its routers, including its boundary routers.

Confederation of AS. AS confederation is a collection of ASs that are represented by the same AS number. Although there may be two or more ASs in an AS confederation, the ASs outside the confederation visualize this collection of ASs as a single AS. An AS confederation helps in the splitting or merging of ASs. An AS may be split into several ASs for a number of reasons. A huge AS under the administrative control of a single organization may want to split into a number of separate ASs each under the administrative control of the organization’s local region for effective management of the ASs as well as for maintenance of a separate region‐based policy for each AS. An AS may also become too huge to be managed by Interior Gateway Protocol owing to scalability‐related issues leading to memory, processing power, and processing time constraints. Splitting an AS into smaller ASs would resolve the problems arising out of these situations. On the other hand, it might be required to merge two ASs for administrative or technical reasons. An organization might take over a number of other smaller organizations, or a few Internet service providers might merge. In such a scenario, the organization might want the external BGP routers to view all the ASs under the administrative control of this organization as a single AS. The requirement of AS confederation was also felt to be an alternative to the initial defined structure of BGP where it mandates complete mesh connection between BGP routers within the same AS. If an AS is split into a number of smaller ASs, this reduces the number of interconnections inside the ASs and the associated overhead of intra‐AS routing. Also, if an AS is split into a few ASs and the associated AS confederation is not formed, this would increase the AS path information.

AS confederation [23] was first documented in RFC 1965 in June 1996, and it was revised in February 2001 as RFC 3065. Finally, RFC 5065 was introduced in August 2007 and made RFC 3065 obsolete. Figure 7.4 depicts an example of AS confederation where the confederation of two ASs appears to be a single AS to ASs that are not members of the AS confederation. A router within an AS confederation possesses the AS confederation identifier of the AS confederation of which it is a member, as well as its member AS number within the confederation. The AS confederation identifier is the identifier of the AS confederation that is known to non‐member ASs and is used by them in the path information. The member AS number is unique to each member AS within the AS confederation and is used only within the AS confederation.

Route aggregation. The process and requirement of route aggregation [24] in BGP is explained by the example shown in Figure 7.5. Let there be a scenario where three external BGP routers R_EBGP_AS01, R_EBGP_AS02, and R_EBGP_AS03, each belonging to a separate AS, are connected to an external BGP router R_EBGP_AS04 in another AS. R_EBGP_AS04 is further connected to R_EBGP_AS05, which is another external BGP router in another AS. R_EBGP_AS04 aggregates the routes received from R_EBGP_AS01, R_EBGP_AS02, and R_EBGP_AS03 and forwards them to R_EBGP_AS05. Now, when R_EBGP_AS04 forwards the route to R_EBGP_AS05, it cannot be mentioned as (AS4, AS3, AS2, AS1) as this will indicate that the path has passed through all three ASs i.e. AS1, AS2, and AS3. Neither can it be indicated as (AS4, AS3) or (AS4, AS2) or (AS4, AS1), as this will give incomplete path information and may also lead to routing loops. Such a network is indicated and advertised using a set representation of ASs as (AS4, {AS1, AS2, AS3}), without any preference for order within the set.

Classification of path attributes. In BGP, the path to destination is not decided upon solely on the basis of the cost metrics of bandwidth, hop, and selection of the next‐hop router. The BGP router is aware of the entire path and the characteristics of the ASs in the path. In order to maintain the path information along with the characteristics of the intermediate ASs, the routers should also share this additional set of attributes with each other during advertisements and path updates. Based on these attributes, each router decides on the path selection as well as on sending update information to peers [24–27]. As BGP is an inter‐AS routing protocol, there may be a selected group of ASs that use a proprietary attribute to share some private information, but there will be certain attributes that must be recognized globally by all BGP routers to enable exchange of mandatory information. Furthermore, a BGP router itself decides whether to process an update received from its peer. In a similar manner, it also decides which attributes to share with its peers. Hence, it should be indicated to the router which attributes are essential and which are not. Similarly, the BGP router should also be informed of those attributes that must not be dropped but rather passed on to its peers during updates. Based on these background factors, as shown in Figure 7.6, the path attributes are divided into two major categories – well‐known attributes and optional attributes. The well‐known attributes must be recognized by all BGP implementations, while the optional attributes may be recognized only by selected BGP implementations and not all, as these may be proprietary.

The well‐known attributes are further divided into two subcategories – mandatory and discretionary. The well‐known mandatory attributes, as shown in Figure 7.7, should be processed by the BGP implementation as well as advertised to the peers in the update message. If an update message is received without a well‐known mandatory attribute, an error message is generated. The well‐known mandatory attributes are the origin of path information (ORIGIN), the list of the AS sequence that describes the path taken (AS_PATH), and the IP address of the next‐hop router (NEXT_HOP). The ORIGIN attribute can have three values – internal, external, or incomplete, and indicates how the BGP router learnt about the route, i.e. from an interior routing protocol or from an external BGP or by some other known or unknown means other than EGP. The value of ORIGIN is introduced by the BGP router initiating the routing and should not be changed in the route by any BGP routers. As AS_PATH contains information about the BGP routers traversed in the route, it helps to prevent routing loops. An update received by a peer with its AS number in the AS_PATH indicates that the information has already been received and it is dropped. Before forwarding a packet to its external peer, a BGP boundary router adds in the beginning its AS number to the AS_PATH. NEXT_HOP is an attribute that is treated differently by external BGP and internal BGP. In the case of an external BGP, the boundary router puts the IP address of its egress interface to reach the external peer. In the case of internal BGP, the internal BGP routers generally do not change the NEXT_HOP and carry it without any change within the AS unless specifically configured to remove the previous entry and add its local IP address [27].

The well‐known discretionary attributes, though recognized by the BGP implementation, may or may not be included in the update message to the peers, at the discretion of the implementation. The well‐known discretionary attributes are local preference (LOCAL_PREF) and atomic aggregate (ATOMIC_AGGREGATE). The LOCAL_PREF is used within an AS and hence forwarded only in internal BGP to identify the most preferred internal path if there exist multiple paths to the destination. The LOCAL_PREF value is not sent to the external BGP peers. The values that LOCAL_PREF can take range from 0 to 4 294 967 295, indicating the degree of preference. A higher value indicates greater preference. The default value of LOCAL_PREF is 100. The ATOMIC_AGGREGATE is used to intimate that specific route information has been lost during route aggregation. When the ATOMIC_AGGREGATE flag is set, it indicates that routers receiving this update should not remove this attribute.

The optional attributes are divided into two subcategories – transitive and non‐transitive. The optional transitive attributes, as shown in Figure 7.8, have to be passed on to the peers, whether they are recognized or not recognized by the BGP implementation. The only advantage of them being recognized is that the implementation can understand the meaning of an attribute that it is passing on to the peer, failing which the attribute is marked as partial by the BGP implementation. The optional transitive attributes are AGGREGATOR and COMMUNITY (No‐Export, No‐Advertise, Internet, NO_EXPORT‐SUBCONFED). The AGGREGATOR attribute records the AS number and the BGP router within the AS that performed route aggregation. The information provided by this attribute indicates the source of origination of the less specific route. COMMUNITY is a 32 bit attribute accommodating two values – the local AS number and the community value in the first 16 bits and in the last 16 bits respectively. COMMUNITY defines a group of routes with similar policies. The default community in a BGP route is the Internet. If the community of the route has to be changed to any other value, it has to be done locally. There are a few other well‐defined communities such as NO_EXPORT, NO_ADVERTISE, and NO_EXPORT‐SUBCONFED, which restrict advertising the attribute outside the AS or confederation advertisements to peer routers and advertisements to any external ASs, even including ASs that are within the same confederation.

The optional non‐transitive attributes [7], explained in Figure 7.9, are passed on to the peers if they are recognized by the implementation. They are dropped and not forwarded to the peers if the BGP implementation does not recognize them. The optional non‐transitive attributes are Multi‐Exit Discriminator (MED), Originator ID, Cluster List, Multiprotocol Reachable NLRI (network layer reachability information), and Multiprotocol Unreachable NLRI. The MED attribute helps adjoining ASs with multiple links between them to mark the most preferred link. The value of MED can range between 0 and 4 294 967 295, with higher preference to lower values. The default MED value is 0. The MED value is applicable only between two external BGP neighbors.

7.3.2 Routing Information Base

The prime objective of BGP is to determine routes across ASs. Searching for routes as well as the exchange and updating of routing information between the BGP routers is assisted by the routing information base (RIB). The routing information base has three sections – Adj‐RIB‐In, Loc‐RIB, and Adj‐RIB‐out, the role of each of which is set out below.

Adj‐RIB‐In. This holds the RIBs received (inwards) from the peers (adjoining routers), and hence the name Adj‐RIB‐In. The RIB received from each peer is stored separately. Adj‐RIB‐In is used to update the routing information stored within the BGP router in Loc‐RIB.

Adj‐RIB‐Out. This holds the routing information that the BGP router plans to share (outwards) with its peers (adjoining routers). The Adj‐RIB‐Out sent by the BGP router to its peers helps in ‘route advertisement’ and ‘route updating’ in the peers.

Loc‐RIB. This is the main database, which is used locally by the BGP router in ‘Route Selection’. The Loc‐RIB is regularly updated from the selected information received through Adj‐RIB‐In.

The structure and the operations performed by the RIB are complex and may be stored in a single database or in separate, but related databases, depending on the internal implementation of the protocol.

7.3.3 BGP Operation

Before two BGP routers can establish connectivity between themselves and start operating, they should be linked to each other through a BGP‐enabled network. Even though two BGP routers may be linked with each other, these BGP peers may or may not be connected or may be in the process of establishing connectivity or closing a connection. Hence, as indicated in Figure 7.10, the BGP session is in one of the following states [28] based on the status of connectivity:

• idle state,
• active state,
• connect state,
• open sent state,
• open confirm state,
• established state.

The process of session establishment, session retention, and session closure explains all these states very clearly and is shown in Figure 7.11. When a BGP peer boots up, it is in the idle state. The BGP router in the idle state cannot accept any BGP connections. When a start event is triggered manually or automatically, the BGP router initiates a TCP connection on port 179 with its peer and enters into the connect state. This TCP connection remains intact throughout the time messages are exchanged between the peers.

While in the connect state, i.e. when an attempt has been initiated to make a TCP connection to a peer, if the connection fails, the BGP router tries again to establish the connection and enters into the active state, i.e. although the connection has not been established, it is actively trying to establish the connection.

When a BGP connection is established with a peer, the router exchanges BGP open messages and enters into the open sent state, i.e. the router has sent a BGP open message and is awaiting a response. The contents of the BGP open message includes the identifier of the router, its AS number, and the parameters that the BGP router desires to use for the session connectivity.

When a router receives an open message, it checks the contents of the message, and if it disagrees with the contents of the open message, it sends a notification to its peer, closes the connection, and goes back to the idle state.

If both peers agree on the contents of the open message, each of them sends a keep alive message back to its peer and enters into the open confirm state, i.e. the router has replied to the open message in confirmation and is awaiting further action.

When the first keep alive message is received from the peer, it enters into an established state, i.e. the connection has been established between the peers and the BGP session is said to be open between the peers. Once a router has entered into an established state, it cannot continue to remain in the state for ever without regular confirmation of its being alive. The frequency of update messages is much lower. Update messages may be exchanged between two routers once in a few seconds. Augmentation of regular communication between the peers is done by sending keep alive messages at a predefined frequency. The frequency varies between 1 and 21 845 s, but the most commonly used frequency of keep alive message transmission is 30 or 60 s.

If a BGP router does not receive any message, i.e. an update message or a keep alive message, for a specified amount of time known as the ‘hold time’, it closes the connection to that peer and deletes the routes through that peer in its RIB.

When a router establishes TCP connection with its peer for the first time, it exchanges its complete routing information with the peer, and thereafter only updates are exchanged between them to save bandwidth requirement and processing.

7.3.4 Decision Process

In BGP, the decision process is responsible for deciding which among the routes received by the BGP router in its Adj‐RIB‐In should be selected for storing in Local‐RIB. It also decides on the data that should be put in the Adj‐RIB‐Out to share with its peers. An UPDATE message is exchanged between the BGP routers to share routes among themselves. The UPDATE message is also used to initiate entry for a new route, as well as to advertise routes that can no longer be reached and hence the paths through them should be withdrawn. The decision process helps to update and store the route table, select the preferred route, and advertise routes to peers.

Among the routes available in the Adj‐RIB‐In of the router, the various routes to each of the networks received from different external peers are analyzed and a preference level assigned to each route. Thereafter, the most preferred route to each of the networks is selected and forwarded to the internal peers. The best route to each network as available from the incoming route information available from Adj‐RIB‐In and compliant with its input routing policy is used to update the Local‐RIB. Routes are selected from Local‐RIB based on output policies of the AS for advertising to other BGP routers in adjoining ASs. The set of rules used to define the preferred path for forwarding to the internal peers may be different from the set of rules used to define the preferred route for external peers. This leads to differences in the preferred path to any particular network being sent to the internal peers and that to external peers.

The preference of routes may be based on a set of criteria such as number of in‐between ASs, policies of the AS, source AS initiating the path, and reliability of intermediate ASs traversed by the packet. Even though BGP selects the most suitable path to each of the distant networks connected to it through multiple in‐between ASs, the protocol cannot guarantee it to be the best path in terms of time, cost, or congestion because BGP is an inter‐AS routing protocol and is not aware of the internal routers, links, and policies within any of the ASs. Selecting the best path based only on the minimum number of in‐between ASs may lead to scenarios of doing away with paths with a much larger number of in‐between ASs but with a better overall performance. For example, in Figure 7.12, the preferred path between AS1 and AS2 will be through AS3 and not through (AS4, AS5, AS6), but the latter path would have better performance than the former one assuming a similar link connectivity between the routers. Another example is shown in Figure 7.13, where the path from AS1 to AS2 will be selected through AS3 and not (AS4, AS5, AS6). However, the links between AS1–AS4–AS5–AS6–AS2 are much faster, and hence this path would have better performance.

7.3.5 Route Selection Process

The route selection process helps BGP to decide which path should be preferred over other paths when multiple paths exist for the same destination. The BGP router will receive multiple paths from its peers through update messages sent by them and store them in the Adj‐RIB‐In. The router cannot store all routes towards any network in its Local_RIB, so the most preferred path has to be selected for storing. The stages for screening of paths and selecting the preferred path are depicted in Figure 7.14 and also listed below. Some of the stages might be optional or specific to certain settings, configurations, or protocols:

1. The reachable next‐hop IP address of the path.
2. The local AS number is not in the AS_Path (loop prevention).
3. Links with higher weight.
4. Route with highest local preference.
5. Locally originated route preferred over externally generated route.
6. Shortest AS path.
7. Routers generated through BGP preferred over routes generated through EGP and the last preference for origin from other protocols.
8. Route with lowest MED value.
9. External BGP preferred over internal BGP.
10. Minimum cost to the next hop.
11. Oldest route.
12. For routes learned through EBGP – select route with lowest router ID.
13. For routes learned through IBGP – select route with lowest router ID.
14. Lowest interface IP address.
15. Shortest cluster list.
16. Lowest BGP neighbor IP address.

The major features and advantages of BGP can be summarized as follows:

• The protocol runs over TCP/IP.
• It is highly scalable.
• It avoids routing loops.
• It avoids count‐to‐infinity problem
• It supports multihomed networks.
• The protocol can detect a node or link failure and redirect paths by withdrawing from failed routes.
• It gives the shortest path in terms of hop count.
• A number of attributes can be associated with the route to help in the process of path selection.
• BGP is not entirely a shortest path routing algorithm but also has policy‐based routing.
• It allows multiple options for route selection, optimization, avoidance, or manipulation using routing policies.
• BGP can work between ASs (external BGP) as well as within the AS (internal BGP).
• The neighboring routers are manually configured to ensure security.
• The present day Internet works on BGP.