Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks

R. Gummadi, H. Balakrishnan, P. Maniatis, S. Ratnasamy, "Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks," NSDI'09, (April 2009).

One line summary: This paper presents a system called Not-A-Bot (NAB) that distinguishes human-generated traffic from bot-generated traffic by attesting human-generated traffic at the clients that is then verified at the servers in order to mitigate such problems as spam, DDoS attacks, and click-fraud.

Summary

This paper presents a system called Not-A-Bot (NAB) for identifying human-generated web traffic as distinguished from bot-generated web traffic. The motivation for this is that bots are responsible for a large amount of spam, distributed denial-of-service (DDoS) attacks, and click fraud, so being able to determine if an email or request is human-generated as opposed to bot-generated would help mitigate these problems. NAB consists of an attester and a verifier. When an attestation is requested by an application for a particular request or email, the attester determines if that request or email was indeed generated by a human, and if so, it attaches a signed statement to it that verifies that it was sent by a human. The verifier runs on the server and checks whether the request or email has an attestation and if it is valid. If it does, the application may choose, for example, to prioritize the request, or increase the score of an email so it is more likely to get through a spam filter. Otherwise it may consider the request or email as more likely to have come from a bot.

NAB assumes that applications and the OS are untrusted and so relies on a Trusted Platform Model (TPM) to load the attester code to ensure that it is trusted. As mentioned, the NAB attester decides to grant an attestation if it determines that a human generated the associated request or email. It does this by guessing, using as a heuristic how recently before an attestation request the last keyboard or mouse activity was observed. If the attestation was requested within a certain amount of time since the last keyboard or mouse activity, the attester grants the attestation. An attestation is non-transferrable and is bound to the content of the request it is generated for. An attestation is over the entire content of the application-specific payload and is responder-specific, and where appropriate, challenger-specific. The mechanism for attesting web requests and email in the common case is straightforward. The only complicated case is script-generated email, which requires deferred attestations. The verifier is straightforward and as metioned, implements an application-specific policy. The authors provide several example policies for spam, DDoS, and click-fraud mitigation.

The authors next describe their evaluation of NAB. They evaluate the attester with respect to TCB size, CPU requirements, and application changes. They evaluate the verifier with repect to the extent to which it mitigates attacks and the rate at which it can verify attestations. They find that the attester is 500 SLOC out of 30,000 for the TCB total, that the worst-case latency for generating an attestation is 10 ms on a 2 GHz Core 2 processor, and that modifications to two programs to include attestations required less than 250 SLOC each. For the verifier, they find that the amount of spam can be reduced by 92% with no false positives, that it can reduce the peak processing load seen at mail servers, that it can filter out 89% of bot-generated DDoS activity while not filtering out human-generated requests, and that it can identify click-fraud activity with more than 87% accuracy without filtering out human-generated clicks.

Critique

I didn’t really think that much of this paper. One criticism is that though adding NAB to applications wouldn’t be technically difficult, as the authors explain, you would still have to make sure a lot of applications (i.e. email clients, web browsers, servers, etc.) did include it and then make sure a lot of hosts ran the versions of the applications that included NAB, because it seems it wouldn’t be nearly as useful if not all the clients used it. In their evaluation, all of the client programs ran NAB, but if that weren’t the case it would be less effective. Another criticism or perhaps point of confusion is with regard to their deferred attestations, which are supposed to be used for script-generated emails. I don’t see why attackers couldn’t leverage this to generate attestations for their own spam emails or whatever else they wanted. Another criticism is that with their simple heuristic (guessing that an activity is human-generated if it is within a certain amount of time of keyboard or mouse activity), bots can still generate attestations for its own traffic by, as the authors say, harvesting human activity. This is probably still sufficient for generating large amounts of spam and such. They would probably be better off using the strategy of using specific mouse or keyboard activity to decide whether or not to grant an attestation request, but in the paper they claim that strategy is too complex to implement.

Cutting the Electric Bill for Internet-Scale Systems

A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, B. Maggs, "Cutting the Electric Bill for Internet-Scale Systems," ACM SIGCOMM Conference, (August 2009).

One line summary: In this paper the authors suggest a new method for reducing the energy costs of running large Internet-scale systems by rerouting traffic on an hourly basis to data centers in regions where the price of energy is cheaper.

Summary

This paper examines a new method for reducing energy costs of running large Internet-scale systems. This method is based on the observations (1) that electricity prices vary on an hourly basis and are not well correlated across different geographic locations and (2) that large distributed systems already incorporate request routing and replication. Considering this, the problem the authors want to solve is: given a set of datacenters or server clusters spread out geographically, map client requests to clusters such that the total electricity cost in dollars of the system is minimized, possibly subject to constraints such as staying under a maximum response time.

The authors first do an empirical market analysis. They verify that prices are not well correlated at different locations, and also note that the price differentials between any two locations generally vary hourly and somewhat unpredictably, suggesting that a pre-determined assignment is not optimal. They examine the overall differential distribution and conclude that there does exist the opportunity to exploit these differentials for savings. To evaluate their method, they use traffic data from Akamai to derive a distribution of client activity and cluster sizes and locations. They then use a simple model to map prices and cluster-traffic allocations to energy prices. They handle the issue of bandwidth costs (i.e. changing assignments of clients to clusters could increase bandwidth costs) by estimating the 95th percentile from the data and constrain their reassignments such that this 95th percentile is not increased for any location. To estimate network performance in their model, they use the geographic distance between client and server. They model the energy consumption of a cluster to be roughly proportional to its utilization. The authors assume the system is fully replicated and that the optimization for cost happens every hour. They then use a simple discrete time simulator that steps through the Akamai usage statistics. At each time step a routing module with a global view of the network allocates clusters, and from this they model each cluster’s energy consumption, and use observed hourly market prices to calculate expenditures.

The authors are able to show that existing systems can reduce energy cost by 2% without significant increase in bandwidth or reduction in client performance. They also find that savings rapidly increase with energy elasticity, which is the degree to which energy consumed by a cluster depends on the load placed on it. Lastly, they find that allowing increased distances between the client and server leads to increased savings.

Critique

This paper was somewhat thought-provoking and brought up some interesting issues. However, what I didn’t really enjoy about this paper is that their model is forced to make so many simplifying assumptions about so many things, such as network performance, cluster power usage, and bandwidth costs, to name a few, that I’m not sure how valid their actual findings turn out to be or how much credence to give them. Along this vein, it would be interesting to know to what extent their results depend on the traffic data they used. Another assumption I didn’t really like is that they assume complete replication in the system in question, so that any request can be routed anywhere. I personally can’t guess how true that is in practice but my inclination is that it is not necessarily true for all Internet-scale systems, though it may be true for many. Furthermore, while in theory the basic idea seems like it would work, the authors do hint at a few complicating factors (that are not necessarily purely computer science problems), and it’s hard to know what others might arise in actually trying to implement something like this. For instance, the authors assume that rerouting traffic in this way would not increase bandwidth prices, but that may not be true, and companies are averse to increasing their bandwidth costs. As another example, in reality, renegotiating existing contracts between companies and cluster operators work if the company rents space in a co-located and between companies and the utility companies to take into account this new method may be difficult. Given all the assumptions the authors are forced to make and other complicating details that they may or may not be aware of, it’s hard to judge whether or not something like this would be feasible in reality. And, if everybody did this, it does make you wonder how that would change things, since there is likely feedback between the number of requests routed to an area and the price of energy there. So in summary, although the authors didn’t really have a choice but to try to make good assumptions or estimates of the various unknowns in their model, I couldn’t help but be frustrated by this aspect of the paper. Regardless, I was still impressed by their model and simulation and found it interesting.

DNS Performance and the Effectiveness of Caching

J. Jung, E. Sit, H. Balakrishnan, "DNS Performance and the Effectiveness of Caching," IEEE/ACM Transactions on Networking, V. 10, N. 5, (October 2002).

One line summary: This paper studies the Domain Name System with respect to client-perceived performance and the effectiveness of caching by analyzing several sets of real trace data including DNS and TCP traffic.

Summary

This paper examines DNS performance from the perspective of clients by analyzing DNS and related TCP traffic traces collected at MIT and the Korea Institute of Science and Technology (KAIST). It seeks to answer two questions: (1) what the performance perceived by clients in terms of latency and failures is, and (2) how varying the TTL and cache sharing impacts the effectiveness of caching. The paper first provides an overview of DNS. It then explains the methodology. The study uses three sets of traces that include outgoing DNS queries and responses and outgoing TCP connections. It collects various statistics on these traces for analysis, including, for a given query, the number of referrals involved, the lookup latency, and whether the query was successful. The dominant type of query the authors observed was A, at approximately 60%, followed by PTR at approximately 30% and MX and ANY making up a roughly equal share of the remainder. Only 50% of the queries were associated with TCP connections and 20% of the TCP connections were not preceded by DNS queries.

The rest of the paper is organized with respect to the two main questions it attempts to answer. First, they examine client-perceived performance. They find median lookup latencies of 85 and 97 ms. 80% of lookups are resolved without any referrals, and the number of referrals increases the overall lookup latency. About 20-24% of lookups receive no response. Of the answered lookups, 90% involved no retransmissions. Queries that receive no referrals generate much more wide-area traffic than those that do. These last three facts suggest that many DNS name servers are too persistent in their retry strategies. They also find that most of the negative responses are due to typos and reverse lookups for addresses that don’t have a host name and that negative caching does not work as well as it should, probably because the distribution of names causing negative responses is heavy tailed. They find 15-18% of lookups contact root or gTLD servers and 15-27% of such lookups receive negative responses. Next they examine the effectiveness of caching. Because the distribution of domain name popularity is very long tailed, many names are accessed just once, so having a low TTL doesn’t hurt because caching doesn’t really help. However, not caching NS records would greatly increase loads to root and gTLD servers, so TTL values should not be set too low for these. Also due to the distribution of domain name popularity, sharing caches does does not increase the hit rate very much after a certain point, because while some names are very popular, the rest are likely to be of interest to just one host. They also found that increasing TTL value past a few minutes does not greatly increase the cache hit rate because most cache hits are produced by single clients looking up the same server multiple times in a row. This summarizes most of their main findings.

Critique

I always really like papers that examine systems like DNS in this way because I think it’s interesting that even though we built it, we don’t always understand and aren’t able to predict the kinds of observations that we later make in studies like this. As always, it would be interesting again to go back and do a similar study now that about a decade of time has passed and see what turns up. One thing in this paper that I am confused about is how the authors could have found that such a significant fraction of lookups never receive an answer. I don’t think they provide much in the way of an explanation for this, if I remember correctly. Are these unanswered lookups just due to dropped packets? Because that seems like a lot of dropped packets, and I guess I find that surprising, although I have no real basis for thinking so.

Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications

I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications," ACM SIGCOMM Conference, 2001.

One line summary: This paper presents Chord, a protocol for a distributed lookup service built on a distributed hash table abstraction.

Summary

This paper presents a distributed lookup protocol called Chord that is simple and has provable correctness and performance properties. It is based on the distributed hash table (DHT) abstraction. It addresses the problems of load balancing, decentralization, scalability, availability, and flexible naming. Chord specifies how to map key/value pairs to storage nodes. It does this through the use of consistent hashing. This works as follows: each of the nodes participating in Chord is assigned an identifier based on the hash of its IP address. Each key also has an identifier that is the hash of the key. The identifiers form an identifier circle that has 2m places in it, where m is the length of the identifier. The identifier of a node determines its place in the circle. A key is assigned to the first node that has an identifier equal to or following it on the circle. The node that the key is assigned to is responsible for storing the corresponding key/value pair. Consistent hashing is used for this because it theoretically ensures that key/value pairs are roughly evenly distributed across nodes.

Each node in the circle stores a pointer to its successor so that queries for a key/value pair can be routed to the correct node. Each node also stores a finger table in which entry i contains a pointer to the node that is at least 2i-1 places ahead of it on the circle. As an optimization, each node can also store a pointer to its predecessor. The result of this setup is that a query for a key/value pair takes O(log N) steps to answer, where N is the number of nodes. When a node joins Chord it is logically placed in the spot on the circle to which its identifier maps. The predecessors and fingers of the new node and the other nodes are updated and all key/value pairs with identifiers equal to or following the new node’s identifier are transferred from the node where they were previously stored to the new node. To join the circle, a node only need know the identity of one other node already in Chord. From that node it can learn its place on the circle. Chord periodically runs a stabilization procedure in which each node verifies its successor. To deal with failures, each Chord node keeps a list of its n successors so that it can find a new one when its old one fails.

The paper next provides an evaluation of Chord. The authors first find that due to the non-uniform distribution of node identifiers, keys are not evenly mapped across the nodes, so they suggest a workaround involving virtual nodes. They next show that the average path length traversed by a query is ½ log N, where N is the number of nodes. They find that Chord experiences virtually no lookup failures due to node failures and very few lookup failures (~3%) for lookups that occur during stabilization. Lastly, they find that lookup latency grows slowly with the number of nodes.

Critique

I liked reading this paper because I’ve seen Chord used in a number of other systems. Briefly, I have only two main criticisms of this paper. First, the load balancing or distribution of keys among Chord nodes without using virtual nodes is disappointing but foreseeable. Second, it might be nice if Chord provided some optional automatic or built-in way of replicating keys across nodes. It seems straightforward to do so it would be nice if it were just automatically provided instead of left to the user to do.

Looking Up Data in P2P Systems

H. Balakrishnan, F. Kaashoek, D. Karger, R. Morris, I. Stoica, "Looking Up Data in P2P Systems," Communications of the ACM, V. 46, N. 2, (February 2003).

One line summary: This paper provides an overview of the various DHT-based data lookup mechanisms for peer-to-peer systems.

Summary

This paper begins by introducing the lookup problem in peer-to-peer (P2P) systems, which is that of finding data in a large P2P system containing a dynamic set of nodes in a scalable manner without introducing any centralization or hierarchy. The paper focuses primarily on solutions based on the distributed hash table (DHT) abstraction, after briefly outlining the problems with solutions involving a central database or hierarchical distributed storage structures. The main benefits of a DHT-based solution are that it has few constraints, including that all data items be uniquely identified with a numeric key and that nodes store data for other nodes. A DHT implements only a lookup operation that takes as input the identifying key of a data item and returns the location of the node that is responsible for that data item. A DHT lookup algorithm must address the following: mapping keys to nodes in a load-balanced way, forwarding lookups to the appropriate nodes, providing a distance function that describes the closeness of keys to each other and nodes to each other, and adaptively build routing tables.

The various DHT-based lookup algorithms reviewed in this paper include CAN, Chord, Kademlia, Pastry, Tapestry, and Viceroy. These vary in the data structures they use to provide O(log N) lookups, their routing dimensions, emphasis, distance functions, various operation costs, degree of fault tolerance and concurrency, routing, and security measures. For example, Chord maintains a skiplist-like data structure, while Pastry, Tapestry, and Kademlia use a tree-based structure. In contrast, CAN uses a d-dimensional Cartesian coordinate space as its abstraction. With respect to distance functions, Chord uses distance in the skiplist that is unidirectional and asymmetric, while Pastry uses prefixes and numeric distances and so is symmetric but not unidirectional, and Kademlia uses an XOR-based function that is both unidirectional and symmetric. Topics for future work in this area include analyzing operation costs when the system is large and joins and departures are frequent, improving routing latency, providing security mechanisms, and implementing efficient indexing and keyword search.

Critique

There isn’t much to say in terms of a critique since this paper is just a brief introduction to and description of various algorithms, but I did find it helpful and thought the writing was nicely structured, so I would keep it in the syllabus.

Resilient Overly Networks

D. Andersen. H. Balakrishnan, F. Kaashoek, R. Morris, "Resilient Overly Networks," 18th Symposium on Operating Systems Principles, (December 2001).

One line summary: This paper describes a Resilient Overlay Network architecture which is intended to run at the application layer over the existing Internet infrastructure to provide path failure detection and recovery as well as mechanisms for applications to choose their own routing metrics and implement expressive routing policies.

Summary

This paper describes Resilient Overlay Network (RON), an application-layer overlay that exists on top of the existing Internet. The goal of RON is to allow Internet applications to detect and recover from path failures and performance degradation quickly. That is, a RON seeks to (1) provide failure detection and recovery within 20 seconds, (2) integrate routing more tightly with applications by letting applications choose their own routing metrics, and (3) allow expressive routing policies relating to acceptable use polices and rate controls.

A RON consists of a set of nodes deployed at various locations on the Internet and each path between two RON nodes is represented as a single virtual link. An application that communicates with a RON node is a RON client that interacts with the RON node across an API. Each client instantiates a RON router that implements a routing protocol and a RON membership manager that keeps track of the list of RON members. By default, RON maintains information about three metrics for each virtual link: latency, loss rate, and throughput. It obtains this information via probes and shares it with all RON nodes by storing it in a central performance database. It also uses these probes to detect path outages. RON uses the data collected from these probes and stored in the performance database in a link-state routing protocol to build routing tables according to each metric. When it detects a path outage, RON uses single-hop indirection to route over a new path. RON provides policy routing by allowing administrators to define types of traffic allowed on certain links and it implements this policy routing using packet classification methods. RON manages membership via either a static mechanism that reads the list of members from a file or a dynamic mechanism that uses announcement flooding and stores the discovered members in soft-state at each node. One important note about RONs is that they are intended to consist of only a small number of nodes (approximately less than 50) because the many of the mechanisms used will not scale, but RON can still provide the intended benefits with only a small number of nodes.

The authors evaluated RON by deploying two wide-area RONs, one with 12 nodes (RON1) and one with 16 nodes (RON2). They found that RON1 recovered from path outages 100% of the time and RON2 60% of the time. (The lower figure from RON2 is in part due to a site becoming completely unreachable.) RON is able to detect and share information about a virtual link failure in an average of 26 seconds. It does this with an overhead of 30 Kbps of active probing. RON was also able to route around flooding links and improve performance in a small number of cases. The authors were also able to show that RON routes are relatively stable, with the median length of time for a route to persist being about 70 seconds.

Critique

RONs are a somewhat interesting idea and I do think the problem they address – that of allowing applications to recover from path failures because BGP is very slow at doing so and of allowing applications to choose their own routing metrics – is compelling. However, there are several big issues with RONs, the two most obvious being poor performance and inability to scale. With respect to the first, RON’s IP forwarder that the authors implemented could only forward packets at a maximum rate 90 Mbps. Also, RON was only able to select paths with better performance with respect to the default metrics a very small amount of the time. RON also introduced a fair amount of overhead due to its use of flooding. This also relates to its inability to scale. However, I still think many of the ideas behind RONs are useful.

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

H. Balakrishnan, V. Padmanabhan, S. Seshan, R. H. Katz, "A Comparison of Mechanisms for Improving TCP Performance over Wireless Links," IEEE/ACM Transactions on Networking, (December 1997).

One line summary: This paper compares several end-to-end, link layer, and split connection schemes for improving the performance of TCP over wireless links, and concludes that link layer schemes incorporating TCP awareness and selective acknowledgments, as well as end-to-end schemes using Explicit Loss Notification and selective acknowledgments, were the most promising.

Summary

This paper compares a number of schemes for improving TCP performance in wireless networks using an experimental testbed consisting of a wired and a wireless link. The approaches compared fall under three categories: end-to-end, link layer, and split connection. In the end-to-end category, six specific protocols were tested. These included the de facto TCP implementation, TCP Reno (labeled E2E), TCP New Reno (labeled E2E-NEWRENO), which improves upon the performance of TCP Reno by remaining in fast recovery after a partial acknowledgement to recover from losses at the rate of one packet per RTT, two TCP schemes using selective acknowledgments (SACKs), labeled E2E-SMART and E2E-IETF-SACK, and two schemes using Explicit Loss Notification (ELN), labeled E2E-ELN and E2E-ELN-RXMT. There were four link layer schemes tested. These included a base link layer algorithm, LL, a link layer algorithm that uses SACKs, labeled LL-SMART, and two additional schemes that add to the first two TCP awareness, labeled LL-TCP-AWARE and LL-SMART-TCP-AWARE. Two split connection schemes were tested, one labeled SPLIT modeled after I-TCP, and another that adds SACKs to the first, called SPLIT-SMART.

The authors perform simple initial experiments on the mechanisms in each category. Of the link layer schemes, the authors conclude that the ones that use knowledge of TCP semantics perform the best. Of the end-to-end protocols, the results suggest that TCP New Reno is better than TCP Reno and that a scheme that makes use of both SACKs and ELN would probably perform the best. Of the split-connection schemes, SPLIT-SMART is better, but the performance of these schemes is overall not as good as those in the other categories. Using the most promising schemes from their initial experiments, the authors then test these schemes’ reaction to burst errors and performance at different error rates. Overall, the authors drew four main conclusions: (1) of all the schemes investigated, a link layer protocol with TCP awareness and selective acknowledgements performs the best, (2) splitting the end-to-end is not necessary for good performance and violates the end-to-end semantics, (3) selective acknowledgements are especially useful over lossy links when losses occur in bursts, and (4) end-to-end schemes are not as good as link layer schemes but they are promising because they do not require any support from the link layer or intermediate nodes.

Critique

The comparisons and overviews of the different techniques for improving TCP over wireless were informative. One thing that is a bit questionable is that the authors themselves implemented each of the protocols. The reason I mention this is because in class I remember Prof. Katz telling us about a company that claimed to be able to distinguish between different implementations of TCP because they each had unique signatures of sorts in the way they operated. This suggests that two different implementations of the same protocol aren’t necessarily the same. It may have been more of a fair comparison to use the “standard implementation” of each protocol but if this was not possible in all cases then implementing them all is probably better anyway. On second thought, this method still works for the sake of comparing techniques, if not implementations, and you probably wouldn’t want the results to be implementation dependent anyway. This paper was the first time I had heard about split-connection protocols, and I have to say, they don’t seem like a very good idea at all, but that could have been because of the way it was presented and tested. It confused me that they still used TCP over the wireless link using the split-connection schemes. That didn’t seem very useful. One other thing that confused me is why at one point in a footnote, the paper states that they only measure “receiver throughput”, when at an earlier point in the paper they state they measure “throughput at the receiver”. I think that in this case they intended the same meaning by these two phrases but generally I would think that these two phrases don’t mean the same thing. I also found the charts not so great to read. Lastly, I think an interesting thing to study next would be a comparison of these protocols over more complex wireless topologies, as they mention in the section on future work.

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.