Random Early Detection Gateways for Congestion Avoidance

S. Floyd, V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM Transactions on Networking, (August 1993).

One line summary: This paper presents an algorithm for congestion avoidance called Random Early Detection (RED) that drops packets probabilistically when the computed average queue length is between a minimum and maximum threshold in order to avoid congestion.

Summary

This paper presents an algorithm for congestion avoidance called Random Early Detection (RED). The authors argue that the most effective congestion detection can occur at gateways as opposed to the endpoints. In the current Internet, TCP only detects congestion when a packet has been dropped, meaning the queue at the gateway is full. Large queues at gateways are especially undesirable in networks with large delay-bandwidth product connections as it can significantly increase the average delay in the network. The authors also assume that it is useful to have queues at gateways in which traffic is multiplexed together with FIFO scheduling, and that per-connection gateway mechanisms such as those used in Fair Queueing should only be used when not having per-flow mechanisms is clearly inadequate. As RED does not use per-connection mechanisms, it is intended for networks where transport protocols are cooperative and respond to congestion indications, although it can be used to control congestion even when sources are not cooperative. In addition to the goals of keeping average queue size low and detecting congestion, RED places emphasis on avoiding global synchronization of TCP connections and avoiding bias against bursty traffic.

The RED algorithm works by first calculating the average queue size using a low-pass filter with an exponential weighted moving average. RED defines two thresholds, minimum and maximum. When the average queue size is below the minimum threshold, no packets are dropped. When it is above the maximum threshold, all packets are dropped. When it is between the two thresholds, each packet from the connections in the queue may be dropped with a probability that is a function of the average queue size, and this probability uniformly distributed and is proportional to that connection’s share of the bandwidth at the gateway. Later in the paper, the authors discuss setting the parameters for the algorithm. The weight in calculating the average should be selected to be not so low that it responds too slowly to changes in the actual queue size but not so high that the average fluctuates too wildly in response to bursty traffic. The minimum threshold shouldn’t be too low if traffic is fairly bursty. The maximum threshold depends on how high of an average queue length is tolerable. A rule of thumb is that the difference in the threshold values should be larger than the typical queue length increase in one RTT, in order to avoid global synchronization.

The authors state that RED meets the following goals: congestion avoidance, congestion detection at the same time scale as connections can respond to congestion, no global synchronization, simplicity, maximizing the throughput-to-delay ratio, no bias against bursty traffic (which the authors somewhat misleadingly term “fairness”), and appropriateness for a wide range of network environments. To show this they conduct a number of simulation experiments that compare RED with Drop Tail and Random Drop gateways. They also show how RED gateways can be used to identify connections using more than their fair share of bandwidth by noting which connections are having more of their packets dropped, as the probability of a connection having its packets dropped is assumed to be equal to that connection’s fraction of the link bandwidth through the gateway. Lastly, they provide an efficient implementation of the RED algorithm.

Critique

I didn’t really like this paper. I found it interesting that they argued for FIFO queueing, and I’m not sure I found their arguments as compelling after reading the other congestion avoidance papers we read. I also found their talk about their algorithm being “fair” rather misleading, since they don’t mean fair in the accepted sense. I think they gloss over the issue of true fairness as it was talked about in the Fair Queueing paper a little bit too much. Also, proper setting of the parameters of their algorithm seems to be important, but despite their rough guidelines it may not always be clear what the proper setting is. This seems like an undesirable property of their algorithm. It does seem like a step up from Drop Tail and a smaller step up from Random Drop, I will give them that. However, as I think we mentioned in class, I don’t think that this has led it to be widely implemented anyway. On more of a nit-picky note, I thought that a lot of their phrasing was awkward and their graphs were absolute crap (difficult to read, didn’t even have legends). I didn’t think the paper needed to be 20 pages long.

Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks

I. Stoica, S. Shenker, H. Zhang, "Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks," ACM SIGCOMM, (August 1998).

One line summary: This paper describes Core-Stateless Fair Queueing, a mechanism for implementing fair allocation in networks in such a way that minimizes the amount of state stored and the complexity of algorithms implemented in core network routers by relying on edge routers to perform flow rate estimation and labeling.

Summary

This paper presents a mechanism for fair allocation called Core-Stateless Fair Queueing (CSFQ). CSFQ identifies contiguous portions of the network as islands consisting of edge routers and core routers performing different functions to provide fair allocation in a simple and effective way. Edge routers compute per-flow estimates and label packets passing through them for use by core routers. Core routers keep no per-flow state and execute FIFO queueing and probabilistic dropping using the information in the packet labels put in place by the edge routers. The authors’ motivation for designing CSFQ begins with the assumptions that fair allocation is important to congestion control and that the complexity of existing mechanism hinders their adoption. The goal of CSFQ then is to achieve fair allocation while avoiding the need for core routers to maintain per-flow state or use complicated algorithms.

The authors use a fluid model to design and analyze CSFQ. Their fairness model is min-max fairness. Their algorithm uses the concept of max-min fairness to calculate the fair share of each flow. When the total arrival rate of all flows is less than the link capacity, no packets will be dropped. When arrival rate exceeds link capacity, those flows that are using more than their fair share will have packets dropped with a probability based on the amount they are using over their fair share. Two challenges in this algorithm are estimating flow rates and estimating the fair share. To estimate flow arrival rates, the algorithm uses an exponential averaging formula. Estimating fair share is more complicated. It is based on the prior estimate of fair share, the estimated total arrival rate, the estimated rate at which the algorithm accepts packets, and whether or not the link is congested. Edge routers estimate flow rates and use this to label packets. Note that these labels must be rewritten at a link that is congested because the estimated rate will no longer be accurate; the minimum of the estimated rate and the fair share rate instead. When experiencing congestion, core routers use the estimate of the flow rate and the estimate of the fair share to perform probabilistic dropping of flows’ packets based on how much beyond their fair share these flows are using. The authors briefly mention an extension that could be implemented to CSFQ that uses weights. They provide performance bounds for CSFQ and show that flows cannot use more than their fair share over the long run, so their algorithm does ensure fairness. They also demonstrate how their algorithm could be efficiently implemented in contemporary routers.

The authors compare CSFQ with four other algorithms. Two are baseline cases that do not ensure fairness: FIFO and RED. The other two represent alternative approaches to ensuring fairness: FRED and DRR. The authors note that CSFQ edge routers have complexity comparable to FRED while core routers have complexity comparable to RED. This is important because one of the main arguments of the authors is that CSFQ is simpler and thus more feasible to deploy. Their findings include that CSFQ provides reasonable fairness even in the face of ill-behaving source, works with different underlying flow control schemes, performs well over multiple congested links, reacts well to bursty traffic, performs reasonably when there is large link delay, and works well even when packets must be relabeled. In general, CSFQ provides fairness comparable to FRED but in a much more scalable manner. The authors also show how CSFQ can be extended to punish unfriendly or unresponsive sources.

Critique

In general, I liked this paper. I especially thought their experiments were nice and clean and revealed interesting aspects of the systems tested. However, as the authors admit, their experiments do not fully reveal how CSFQ would operate over more complex topologies, especially one containing large latencies. Large latency links seem to be a hazardous area for many a network protocol.

One concern is whether CSFQ would in fact be easier to adopt and administer than other fair queueing algorithms. That was one of their main motivations for proposing the architecture, but the fact that it has to be adopted on an “island-by-island” basis as opposed to a router-by-router basis seems potentially awkward. As the authors freely admit in the beginning of their paper, their underlying assumptions are open to debate. In particular, it was (and still is?) arguable whether other fair allocation mechanisms are too complex to implement and deploy in contemporary routers. While this may indeed turn out to be false, I think I recall discussing in class the fact that fair allocation mechanisms weren’t really implemented in most routers today. I may be misremembering this, but if not, then we can’t really say if the authors’ goal of providing a simple and feasibly deployable fair allocation mechanism has been met, since it hasn’t really been tested in practice.

Analysis and Simulation of a Fair Queueing Algorithm

A. Demers, S. Keshav, S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," Internetworking: Research and Experience, 1 (1990), pp. 3-26.

One line summary: This paper proposes a fair queueing algorithm for congestion control at gateways and provides analysis and simulation results for this algorithm.

Summary

This paper proposes a fair queueing algorithm for congestion control at gateways. As the authors point out, there are two points at which congestion control can be implemented. The first is at the source and the second is at the gateways. At the source, flow control algorithms, while not directly designed to control congestion, do affect overall network traffic. At the gateways, congestion control can be implemented through routing algorithms, such as adaptive routing, and through queueing algorithms, which affect congestion indirectly. This paper focuses on the latter.

The authors note that queueing algorithms can be thought of as allocating bandwidth, promptness, and buffer space. The most commonly used queueing algorithm, first-come-first-served (FCFS) does not address each of these things separately. The authors argue that it is important to consider how flow control algorithms interact with queueing algorithms to affect network congestion. With this in mind, a major shortcoming of FCFS is that it does not provide good congestion control in the presence of ill-behaved sources in the network i.e. sources that do not provide good flow control and thus flood the network with packets. Such ill-behaving sources can unfairly capture high portions of the outgoing bandwidth of gateways implementing FCFS. In response to this, the authors propose a fair queueing (FQ) algorithm.

The authors’ requirements of their algorithm are: it must be able to allocate bandwidth and buffer space fairly; it must be able to control promptness/delay somewhat independently of bandwidth and buffer space; and it should provide service that does not depend discontinuously on a packet’s time of arrival. To define fair, the authors use the max-min fairness criteria, which state that an allocation is fair if (1) no user receives more than it requests, (2) no other allocation satisfying the first condition has a higher minimum allocation, and (3) the second condition remains recursively true as the minimal user is removed and the total resource amount reduced accordingly. The authors define a user as a source-destination pair, or a conversation. They then define their algorithm, which is based on a packetized version of a bit-by-bit round-robin scheme. Essentially, they first allocate a queue to each conversation. Then they consider the packets at the head of the queue, and estimate what they call the ‘finish time’ for these packets, which is the time at which the packet would finish being serviced. Finally, the algorithm selects the packet with the lowest finish time for transmission. The authors build upon this algorithm by introducing an additional factor that they call the bid. In this improved version of the algorithm, the packets are selected for transmission based on their bid, which is calculated in such a way as to provide less delay to users using less than their fair share of bandwidth. When the gateway’s buffers begin to fill, it must choose packets to drop. The way the authors’ algorithm selects a packet to drop is by choosing the last packet from the user currently using the most buffer space.

The authors then analyze their algorithm with respect to two types of sources: FTP-like sources and telnet-like sources. They do a bunch of annoying math and conclude that their algorithm is indeed able to provide lower delay to lower throughput sources. They then consider their algorithm with respect to flow control algorithms. They consider three types, (1) generic flow control algorithms using a timeout mechanism and a sliding window of set size, (2) second generation flow control algorithms using dynamic window sizes, fast retransmits, improved timeout calculation, and congestion signals, and (3) third generation flow control algorithms, which are similar to the second except that congestion signals are sent selectively. They select one flow control algorithm from each category and use them each with their FQ algorithm and with the FCFS algorithm to compare the two via simulation. They provide a lot of results but the main lesson from these is that FQ gateways cannot control congestion by themselves but can help protect from ill-behaved sources. Their FQ algorithm isn’t perfect and its performance depends a lot on the flow control algorithm used and the specific network dynamics, but it still provides much better fairness than FCFS.

Critique

There are a few things I didn’t like about this paper. I found all their mathematical analysis a bit much. It was annoying to read, especially the preemptive versus nonpreemtive bit, which didn’t factor in much anywhere else in the paper. I think it would have been better if the authors included all the mathematical details in an appendix and used the space instead to state their main point and conclusion of all that analysis, which as far as I can tell, they did in just one sentence out of 3-5 pages. The unused space then could have been used to provide some psuedocode or examples of their algorithm in action. These things would have made their paper much more appealing.

The authors also point out that there are objections to their algorithm, which might be interesting to discuss. The first objection is that some source-destination pairs, such as mail servers, need more than their fair share of bandwidth. The second is that their algorithm is too complicated to implement on routers in a such a way that it could run fast enough to match the speed of the links. It wouldn’t be very useful or compelling if their algorithm slowed the routers down.

Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

D-M Chiu, R. Jain, "Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks," Computer Networks and ISDN Systems, 17 (1989), pp 1-14.

One line summary: In this paper the authors algebraically analyze a subset of algorithms for congestion avoidance with respect to a number of criteria, including efficiency, fairness, distributedness, and convergence; they are able to conclude that the optimal algorithm uses additive increase and multiplicative decrease.

Summary

In this paper, the authors analyze decentralized algorithms for congestion avoidance based on binary feedback signals, focusing on what they call increase/decrease algorithms. They focus on an abstract system in which there is one bottleneck resource used by n users. They assume that the binary feedback signal indicates whether this resource is overloaded or underloaded, and that the signal is sent by setting a bit in the packet header. They also assume that the feedback and control loop is synchronous across all users. The authors focus on linear control functions. In this context then, increase/decrease algorithms are merely those in which one signal indicates that the resource is underloaded and the load should be increased, and the other signal means the opposite. Examples of such algorithms include multiplicative increase/additive decrease and additive increase/multiplicative decrease.

The criteria by which the authors select controls are efficiency, fairness, distributedness, and convergence. Efficiency is measure by how close the total load on a resource is to the point where any further load would cause a decrease in response time and throughput, i.e. the point of maximum utilization and throughput and lowest response time. Fairness is measured by a function that the authors define which attempts to measure how equal the allocation of the resource is across all users. Distributedness means that the users only have limited knowledge of the system, in particular, whether the resource is overloaded or underloaded. Lastly, convergence is a measure of both responsiveness, or how fast the system takes to reach equilibrium, and of smoothness, or how large the oscillations around the equilibrium are. They choose to examine distributed linear control functions that converge to efficient and fair states.

In order to analyze the set of possible control functions, the authors represent system state transitions in an n-dimensional vector space (representing the load for each of n users) across discrete time slots. The ith user’s load at time t is x_i(t) and the load at the next time interval, x_i(t+1), is a function of the control scheme used with the load at time t and the system feedback. For example, it could be that x_i(t+1) = a + b*x_i(t) if the binary signal is indicates the resource is underloaded. In this function, a is additive and b is multiplicative. With this representation, they are able to deduce algebraically a number of propositions. The first is essentially that the decrease policy should be multiplicative and the increase policy should have an additive component and can optionally have a multiplicative component with coefficient no less than one. The second proposition is that both the increase and the decrease can have both additive and multiplicative components provide that a special step is taken in the case when certain convergence restrictions would be violated. The third and most conclusive proposition is that for feasibility and optimal convergence, the increase should be additive and the decrease should be multiplicative.

At the end of the paper, the authors describe what nonlinear control functions in congestion avoidance algorithms might look like, but reason that because such control is too sensitive to various system parameters, the robustness of the control is decreased. On this note, they go on to enumerate a few practical considerations in choosing an algorithm for congestion avoidance. The first is that it should be independent of hardware and software parameters as much as possible in order to reduce the complexity of the configuration task and make configuration errors less possible. The second consideration is that the resources and allocations must be measured in integers, so this should be taken into account when choosing an algorithm. The last practical consideration they mention is ease of implementation. Given all these considerations in addition to the result of their earlier analysis, they conclude that an algorithm that uses a linear control function with additive increase and multiplicative decrease is optimal.

Critique

I didn’t like everything about this paper. I thought that it was a bit too abstract, and I think in general it is no trivial matter to translate abstract results into real working solutions. However, given that there appear to be so many different algorithms for congestion avoidance, of which they only examine a subset, their analysis does provide some solid guidance in choosing among these, especially if you accept that the conclusions they draw from their analysis of their simplified system still completely hold in the much more complex environment of real systems. Since real TCP uses additive increase/multiplicative decrease, it seems that this could be a safe bet.

I’d be curious to see if algorithms with control functions other than additive increase/multiplicative decrease have been tested in practice. The authors mention that this paper is just one in a series of papers in which they examine a range of mechanisms for congestion avoidance, so an interesting exercise might be to take some of the algorithms they look at in their other papers and actually test them against additive increase/multiplicative decrease, and also maybe examine some algorithms that use nonlinear control functions.

One thing I did really like about this paper is their use of graphs. Whereas some of the algebra was at times a bit tedious or difficult to follow, I thought the graphs helped them provide a nice, clear, and more intuitive explanation for how the control functions worked and how they converged to fairness and efficiency. Although these graphs were further simplified on top of their simplifying assumptions, in that they represented the case with only two users, they were still pretty much key in helping me to understand some of their conclusions.

Congestion Avoidance and Control

V. Jacobson, M. Karels, "Congestion Avoidance and Control," ACM SIGCOMM Conference, (August 1988).

One line summary: This paper describes several important algorithms for congestion control in TCP, including slow-start, exponential backoff, multiplicative decrease additive increase, and RTT variance estimation; the paper also provides results that demonstrate that implementations of TCP using the algorithms described in the paper are better than older implementations.

Summary

The authors note that due to an explosive increase in size, computer networks have increasingly experienced congestion problems. Seven algorithms added to TCP are meant to help deal with this: round-trip time (RTT) variance estimation, exponential backoff, slow start, aggressive receiver ACK policy, dynamic window sizing, Karn’s algorithm, and fast retransmit. The authors describe the first five of these algorithms. According to the authors, these algorithms stem from the observation that a TCP connection should obey a “conservation of packets” principle, which basically states that for a connection in equilibrium, the sender should not place a new packet into the connection until an old packet leaves. There are three instances in which this principle will not be upheld: when the connection doesn’t initially reach equilibrium, when after equilibrium is reached, a new packet is sent before an old packet leaves, and when resource limitations along the connection path make equilibrium unattainable. The authors address each of these in turn.

The first failure occurs when a connection is being started or restarted. The authors note that a TCP connection is a self-clocking system, which help makes it stable, however, this also means that in order to get packets flowing there must be ACKS to clock them out, but to get ACKS there must be packets flowing. The authors thus describe the slow-start algorithm as a method for “starting the clock” and gradually increasing the number of packets flowing. The slow-start algorithm is as follows: For each connection, store a variable called the congestion window that will be used to determine the number of packets to send. When starting or restarting, set the congestion window to 1 packet. Every time a packet is acknowledged, increase the congestion window by 1. To select how many packets to send at a time, choose the minimum of the congestion window and the receiver’s advertised window. The result of this algorithm is that if no packets are lost or delayed, the congestion window doubles every RTT, and never will the sender send packets at a rate faster than twice the maximum send rate on the connection path. The authors find that this algorithm greatly decreases the number of retransmits and increases effective bandwidth.

The authors next explain that the second failure must be due to a sender’s faulty retransmit timer. This timer should estimate the RTT, which increases when load increases, in order to determine when a packet should be retransmitted, but one mistake in doing this is not estimating the variance in the RTT. The authors present an easy-to-calculate method for estimating the variance in their appendix. Another mistake is not choosing the correct backoff after a packet is retransmitted. The authors argue that only exponential backoff schemes have any hope of working in the general case. The authors demonstrate that a timer that estimates RTT using their method more accurately approximates RTT than the method previously used in TCP.

Lastly, the authors point out that if the timers are doing a good job of estimating RTT, then a timeout probably indicates a lost packet instead of a broken timer. Lost packets are typically a sign that the network is congested, causing connections to encounter resource limits, which is the third failure case. Connection endpoints must have a way of responding to congestion such that they decrease the amount they send when the network is congested and increase the amount they send when it is possible to do so, in order to achieve the proper utilization of network resources while avoiding congestion. To this end, the authors introduce a multiplicative decrease additive increase algorithm. The reason the decrease happens much faster than the increase is because it is easy for the network to become congested and much harder for it to become uncongested. The algorithm works as follows: On a timeout, the congestion window is set to half of the current congestion window size (multiplicative decrease). For each packet acknowledgement received thereafter, increase the congestion window (cwnd) by 1/cwnd (additive increase). Then when choosing the number of packets to send, choose the minimum of the congestion window and the receiver’s advertised window. The authors note that this does not include slow-start because they are two entirely different algorithms, but they should be implemented together, which is done usually by having separate slow-start and congestion avoidance phases. The authors show that their congestion avoidance approach results in fewer retransmits and higher bandwidth utilization.

Critique

The algorithms the authors propose in this paper later made it into newer implementations of TCP, so in that sense, they were very successful. Their results demonstrate that their algorithms were generally an improvement over previous implementations. However, as the authors point out, there are still improvements to be made. For instance, none of their solutions ensure fair sharing of network bandwidth, so they propose this as an area of future work. (Then again, according to Kurose and Ross, the multiplicative decrease additive increase algorithm was later shown to converge to provide equal sharing of bandwidth by Chui in 1989, a year after this paper was published, so perhaps it was the case that this work did not need to be done after all.)

Also, in certain situations, TCP’s exponential backoff and congestion avoidance can cause serious performance problems. Regular TCP can be improved for high-performance networks and there are apparently some extensions to TCP for this. Investigation reveals that some of the later changes to TCP’s congestion avoidance algorithms were suggested in order to allow it to more appropriately handle networks with LFNs and high-latency links. Lastly, some of the assumptions that the authors make about the network aren’t necessarily always valid. For instance, the authors state that packets are lost due to either network congestion or packet damage, but that the latter occurs so infrequently that it is safe to assume that a timeout is almost always a sign of network congestion. However, in wireless networks, this assumption does not generally hold, so TCP’s congestion avoidance can in this case result in link underutilization. Thus, a modified mechanism that takes this into account would be appropriate for TCP in wireless networks.

I thought this paper was good, and obviously the algorithms described in the paper are important, as they are now an integral part of TCP. Congestion control is a very important service, without which the Internet could not function well, if at all. I was somewhat confused as to how much of the algorithms suggested were original contributions, since some of the footnotes seem to indicate very similar algorithms had first been suggested elsewhere. I found that the authors’ tendency to reference a handful of papers I hadn’t read without really explaining briefly what was in those papers inhibited my understanding. And just as a matter of personal taste, I did not like it that so much information was crammed into the footnotes and appendices; to me this made the paper less readable, although aside from this it was well-written.

[EDIT: From my comment about fairness as examined by Chui it's probably clear that I read this paper before I read the other one. ;-) ]

Understanding BGP Misconfiguration

R. Mahajan, D. Wetherall, T. Anderson, "Understanding BGP Misconfiguration," ACM SIGCOMM Conference, (August 2002).

One line summary: In this paper the authors identify and analyze BGP misconfiguration errors, measure their frequency, classify them into a number of types, examine their causes, and suggest a number of mechanisms for reducing these misconfigurations.

Summary

This paper provides a quantitative and systematic study of BGP misconfiguration. They classify misconfigurations into two main types: origin misconfiguration and export misconfiguration. Origin misconfiguration occurs when an AS inadvertently advertises an IP prefix and it becomes globally visible. Export configuration occurs when an AS fails to filter a route that should have been filtered, thereby violating policies of one or more of the ASs in the AS path. They identify a number of negative effects of such misconfigurations, including increased routing load, connectivity disruption, and policy violation. In order to measure and analyze misconfigurations, the authors collected data from 23 peers in 19 ASs over a period of three weeks. They examine new routes and assume that those that don’t last for very long are likely due to misconfiguration and failures, and so select these to investigate. As part of their investigation they used an email survey of the operators of the ASs involved, as well as a connectivity verifier to determine the extent of disruptions. They note that their method underestimates the number and effect of misconfigurations for various reasons.

The authors first describe their results for origin misconfiguration analysis. They classify the new routes that are potential results of origin misconfiguration into three categories, self-deaggregation of prefixes, announcement of a new route with an origin related to the origin of the old route via their AS paths, and announcement of a new route with a foreign origin (unrelated to that of the old route). They observe that the number of incidents from each of these three categories is roughly the same, with self-deaggregation being slightly higher. They note, however, that the success rates for identifying these different types of origin misconfigurations are different for each, as some incidents that were classified as origin misconfigurations were actually the result of failures. Some interesting conclusions they draw from their analysis are that at least 72% of new routes seen by a router in a day are the result of misconfiguration, that 13% of incidents cause connectivity disruptions, mainly caused by new routes of foreign origin, that compared to failures connectivity disruptions due to misconfigurations play a small role, and that 80% of misconfigurations are corrected within an hour, often less if the misconfiguration disrupts connectivity. The authors next examine export misconfigurations. They note that such misconfigurations do not tend to cause connectivity problems directly, and that most incidents involved providers rather than peers. The authors also examine the effect of misconfigurations on routing load, and conclude that in the extreme case, load can spike to 60%.

In the paper, the authors identify and classify a number of causes of misconfiguration, which they classify into slips and mistakes. Slips and mistakes turn out to be roughly equally responsible for misconfiguration. Mistakes in origin misconfiguration that they identified include initialization bugs, reliance on upstream filtering, and use of old configurations. Slips in origin misconfiguration include accidents (such as typos) in specifying redistribution, attachment of the wrong community attribute to prefixes, hijacks, forgotten filters, incorrect summaries, unknown errors, and miscellaneous problems. They also identify three additional mistakes causing export misconfiguration, including prefix-based configuration, bad ACL or route map, and initialization bugs. Lastly, they identify a number of causes for short-lived new routes that are not misconfigurations, including failures, testing, migration, and load balancing.

Lastly, the authors suggest a number of ways to reduce misconfigurations. These include enacting improvement to the router CLIs, implementing transactional semantics for configuration changes, developing and supporting high-level configuration tools, developing configuration checkers, and building database consistency mechanisms. They also describe a protocol extension to BGP called S-BGP which would prevent about half of the misconfigurations they observed.

Critique

In general, I thought this was an entertaining read, especially as I could relate to how difficult router CLIs are to use and how easy it is to make mistakes in configuring BGP, having had to do this in a previous networks class. It is unfortunate that because misconfigurations are hard to identify, the authors’ methodology was necessarily limited. I’d be interested to see if other newer techniques have been or could be developed to do this and similar sorts of analysis. Due to the weaknesses in their methodology, I’m not sure how meaningful some of the figures and percentages they derive actually are, but they do still provide some interesting insights, especially if they are correct in arguing that their study provides a lower bound. That said, I still think their approach was clever, given the difficulties.

I particularly like their suggestions for reducing some of the causes of misconfigurations. User interface design improvements seemed to me to be the most obvious thing to do. In general, I wonder why many of their suggested solutions, which have been used in many other contexts and computer systems, have not been used in router configuration. Although the authors do briefly discuss some of the barriers to implementing such solutions, it still surprises me that harried system administrators haven’t risen up and demanded that at least some of the more obvious steps be taken sooner, but maybe the potential for missteps makes things more interesting for them, it’s hard to say. I think investigation of some of the improvements they suggest would be an interesting area for research, although they did seem to imply at one point that industry can be a barrier to the adoption of some of these improvements, which might be too frustrating to deal with.

Interdomain Internet Routing

H. Balakrishnan, "Interdomain Internet Routing," MIT Lecture Notes.

One line summary: In this lecture the author describes the Border Gateway Protocol (BGP), used used to exchange reachability information for interdomain routing in the Internet, describing its operation as well as pointing out several flaws in the protocol.

Summary

This lecture starts by explaining that the Internet service is provided by a large number of commercial entities called Internet Service Providers (ISPs) which own an administer portions of the wide-area routing infrastructure called autonomous systems (ASs). ASs are classified into tiers based on their size and routing scope, e.g. the ISPs that have global scope are Tier-1 ISPs, whereas local providers tend to be Tier-3 ISPs. Within each AS, routing is done via Interior Gateway Protocols (IGPs) such as RIP and OSPF. Routing between ASs is accomplished through BGP. BGP is used to exchange routing information between ASs. ASs interconnections are generally either transit or peering type connections. In transit connections, one ASs acts as the customer and the other as the provider, where the provider gives the customer access to some or all of the destinations in its routing tables. In peering connections, ASs share some subset of their routing tables with each other, and these connections tend to be between business competitors. The first kind of interconnection tends to generate revenue for the provider, while the second does not.

BGP consists of two parts: eBGP between ASs and iBGP within an AS. In BGP, one router opens a BGP connection with another router using an OPEN message. The routers then exchange some of their routing information subject to filtering rules which ASs use to determine which routes to share. This exchange is done by UPDATE messages, which consist of an IP prefix followed by a number of attributes. These attributes are what ASs use to apply their filtering rules. Some of these attributes include Next Hop, AS Path, Local Preference, and Multiple-Exit Discriminator (MED). As mentioned, eBGP is used to disseminate routes between ASs, and eBGP connections are usually point-to-point. Two main goals eBGP must meet are loop-free forwarding and complete visibility. Within an AS, routers use iBGP to learn information about routes external to the AS, although the routing protocol used within the AS itself will be one of the IGPs. Ideally, iBGP routers within an AS would be organized into a full mesh, but as some ASs have large numbers of internal routers, this solution is not scalable. Within an AS, there are two methods for organizing iBGP routers into some sort of hierarchy to improve scalability. The first is to use route reflectors, and the second is to set up confederations.

Critique

There are many issues with BGP that cause it to not function as desired. One issue is that because peering interconnections between ASs usually occur between business competitors, financial motivations cause ASs to attempt to force other ASs to use up their resources (i.e. bandwidth) carrying packets in the wide-area network, leading to a large amount of asymmetrical routing. In addition, as mentioned before, there is an issue with scalability. Even bigger issues are caused by the lack of origin authentication. Because of this, misconfigurations or malicious users can cause a route to any IP prefix to be incorrectly advertised from an AS, causing traffic to be routed to that AS when that AS does not actually own that set of IPs. The propagation of incorrect routing information via BGP can affect huge portions of the Internet and result in users being unable to connect to the mis-advertised addresses. Also, by advertising false routing information via BGP, malicious users can engage in such activities as transmitting hard to trace email spam. An additional issue with BGP is convergence. BGP initially can take several minutes to converge, and in addition, to prevent propagation of transient faulty routing information, many routers use the policy of ignoring frequently changing advertisements, increasing convergence time. Another issue is that the increase of multi-homed customer networks is causing additional stress by increasing routing complexity, churn, and convergence time.

There are several things I found interesting about this lecture. One is the vulnerability of BGP to misconfigurations and malicious activity. I wonder if it is possible to “fix” BGP to address this issue or if it would be more advisable to attempt to replace BGP with a better protocol, if one even exists. Given the capacity for massive routing failures caused by BGP, I wonder what measures are taken to prevent them from occurring more often. I also found the discussion of the effect of financial interests of ISPs on routing interesting. It seems that ISPs engage in a fair amount of subterfuge, subverting routing goals. It might be interesting to examine this activity in more detail, and possibly determine if it would be possible to design a protocol to prevent this sort of behavior or create incentives to improve routing in the Internet, or if this sort of behavior is unavoidable given the nature of the participants.