Problems with BGP Essay
Problems with BGP
The fact that BGP is the protocol that has been chosen as the standard for controlling data transmission across the Internet suggests that it is considered the best solution that is currently available. That does not mean that there are no problems with the operation of BGP. Among these problems are routing instability, slow convergence, scalability routing inefficiency and security. The purpose of this section is to examine the cause of these problems and some possible solutions.
As previously discussed, routers must communicate path attributes with one another in order for the BGP algorithm to choose the ’best path’. Routing instabilities are time dependent fluctuations in the amount of routing information data traffic between routers .. For optimum performance, it is desirable that this traffic load remain at a constant and low level. Spikes in routing information load can lead to increases in latency, convergence time and even packet loss .
A possible scenario leading to routing instability has been described by Li  as “A typical scenario that results in routing instability is as follows: A failure occurs on part of the network, such as a single link failure or a set of network prefixes unreachable or with duplicate routes. The router directly related to the failure would detect it and withdraw the corresponding route(s). Subsequently, the neighbour routers peering with the router will receive the new routing updates and take corresponding action, for example, withdraw the failed network prefixes and announce the recalculated routes.
Thus, the propagation would continue with the updated information. Most probably, the ripple effect will go on to a large portion of or even the whole Internet. At the same time, since each router receives the updates and makes its own decision based on its local information and policies, it may advertise different update results to its peers. This may lead to different views on different routers about the topology change. Finally, there may be more and more or even divergent routing updates going on which cause a larger scale of routing instability. ” The study by Labovitz et.
al . showed that even though the internet routing tables contained routing information from an estimate of only 45,000 active routers at any given time, there were three to six million routing updates per day. The authors suggest that this is at least an order of magnitude greater than expected. Moreover, most of these updates were not needed because they did not reflect a change in network topology or local routing policy. The traffic load associated with these redundant updates was quasi-periodic with a periodicity of between 30 seconds and sixty seconds. Labovitz et al .organized the update traffic into three categories, forwarding instability, routing policy change and pathological updates.
Forwarding instability provides information on local network topology, such as router or transmission line failure, that may be required to optimize path selection by BGP. Routing policy change updates announce changes in local policy without changing the AS path. Pathological updates are described as incorrect updates, such as a route incorrectly being reported as withdrawn because of temporary latency problems, or unnecessary updates, such as repeated announcements of the same transmission line failure.
Labovitz et al . found that that the majority of updates observed on the Internet were pathological. The root causes of pathological updates and routing instability have been investigated in a few studies, but no conclusion has achieved general acceptance. One problem that has been identified has to do with the shared responsibility of routers to minimize unnecessary router communication. When a router receives an update, it should examine the update to see if the update is redundant. If so, the router should not pass on this update.
However, to save on the routers’ random access memory resources, the BGP may be implemented so that any update is automatically passed on without checking to see if it is redundant. This can make the router perform better as it reserves resources to calculate best path. However, if this practice is too common, then unnecessary updates flood the Internet, resulting in routing instability. Any programming error in the configuration of BGP for AS interaction or BGP/IGP interaction can also result in pathological behaviour. An extreme case of this occurrence is considered in .
Another possible cause of router instability is related to implementation of BGP using cache architecture. When such routers are injected with large routing tables, a ‘malloc error’ associated with insufficient random access memory allocation was observed . This resulted in a change in network topology, requiring updates across the Internet, which resulted in an increase in data traffic load. If this increased load resulted in other router shutdowns, then the a cascade of router updates would give rise to a spike in router communication traffic.
This type of router communication cascade is a more damaging incident if the BGP router communication occurs without randomizing the time interval between network topology update messages. Thus, a network of routers may become synchronized such that every router in the network sends an update message at the same time. This would again result in a spike in the update traffic load and possible router failures . When slow convergence of BGP occurs, the time required for routers to decide the best path for data transmission is increased because path choice can not occur until convergence has occurred.
This can become an issue when a router failure causes a significant change in internet topology and results in a convergence time of up to 10 minutes for the Internet . Recent research has again blamed configurable timers leading to unfavourable synchronization and incompatible implementation criteria at different nodes leading to a condition that never converges locally (divergence) . A simple example of the divergence problem has been given by K. Varadhan, R. Govindan, and D.
Estrin , “Persistent Route Oscillations in Inter-Domain Routing,” Computer Networks, March 2000. Consider that three nodes, D0, D1 and D2, are connected as shown in figure 2. 1 and that the BGP running in each node has been programmed to have a preferred route to destination, z, as route r0 for node D0, route r1 for node D1 and route r2 for node D2. Moreover, the routers are also programmed with the policy that D0 will never choose route r1, D1 will never choose route r2 and D2 will never choose route r0. This routing policy is described in table 2. I.
Figure 2. 1  Table 2. I  The top row in table 2. I gives the route that has been advertised to each node. The route at the intersection of the top row and the node column gives the node that would be chosen based on the advertisement in the top row. The dashed line means that the advertisement is consistent with the protocol programmed at that node. The results of a sequential node communication process are shown in Table 2. II, where the initial state (step 0) is the preferred route to destination z for each of the three nodes. Table 2. II 
Step 1 is the chosen path exhibited by each node after the advertisement by D0 consistent with the policy implementation at each node. Notice that D2 cannot accept r0 as the best path (based on local policy) and thus the three node network cannot agree on the best path (no convergence). Thus D2 advertises the best path, r2, according to its local policy. Again, there is no network convergence because D1 cannot accept. The process continues until the state at step 1 is recreated in step 4 and the process then repeats. The network is said to oscillate and to diverge.
University/College: University of California
Type of paper: Thesis/Dissertation Chapter
Date: 17 May 2017