MIRO: Multi-path Interdomain ROuting May 29, 2009

(i) the three most important things the paper says

1. One of the most important topics that this paper addresses is that BGP, in its current form, does not allow for any given AS to (in any reasonably automated way) request a certain route for its packets to traverse, regardless of the motive.  In fact, beyond sending that packet to its next AS-hop, the originating AS has no control whatsoever within the BGP implementation on the Internet today.  Some great examples mentioned in the paper about why this level of control (over which individual AS hops a stream of packets will travel) could be useful are security, performance/bandwidth, or price (among other things, I’m sure).  For example, a government agency may not want to route a certain set of transmissions through a country that is considered hostile and thus would like to request that a certain AS not be used, regardless of the fact that it may be on the shortest and most economical path.  This lack of control is the problem that the authors of this paper have set out to solve with their new scheme: MIRO.
2. The authors also address the standing issues with the current (most popular) solutions for this problem: source routing and overlay networks, demonstrating why these solutions lack the proper scalability, lack the proper backwards compatibility (which would require a batch change of all Internet hardware), and require far too much overhead to be used as Internet-wide protocols.  Quite notably, on this same note, the authors made it a point to demonstrate why MIRO satisfied these two requirements (at the protocol level).  The authors brought up the point that MIRO continues to keep relatively the same amount of BGP-control messages between ASes as vanilla BGP (because of its pull-based alternate route advertisements), helping scalability.
3. The authors also describe a method in which it would be possible for MIRO to operate on existing hardware on the intermediate routers of a given AS (to reiterate, not including edge BGP routers).  This is a great advantage of the MIRO solution, as most/all changes to the Internet backbone that require increasingly larger change rarely are implemented.  The solution involves treating an alternate route as if it were another IP address in the given AS’s inner network (essentially adding a level of indirection).  This would essentially require changes solely to the routing tables of each router instead of to the underlying software of hardware.

(ii) the most glaring problem with the paper

One of the largest problems with this paper (and it was quite difficult to find a topic that wasn’t addressed well by the authors) was that it did not address any performance metrics below the level of the protocol level.  Specifically, the authors did not investigate the impact of these new changes on the performance of edge BGP routers.  Since these routers are meant to move packets from their ingress ports to their egress ports (or vice-a-versa) as quickly and accurately as possible, adding to the latency of moving a packet from one end to the other is very undesirable.  If it is the case that this scheme adds significant overhead to these routers, this scheme may find greater resistance in its adoption (as it would also require a hardware or significant software change to each of the edge BGP routers–another big hurdle to overcome).

(iii) the future research directions of the work

Although mentioned briefly in the conclusion, security would be on the mind of the average grad-student reader of this paper from the very beginning.  The level of control can is given (insecurely) to any router that can send a packet is practically limitless, as long as the negotiating AS approves of its requests.  Some sort of secure handshaking protocol or digital signature technique would greatly help to strengthen this scheme.  Another great future direction of this work would be to investigate the true overhead created by this scheme versus the BGP baseline, along with he overheads of other popular replacements for or augmentations to BGP.  It would be useful to quantify the different overheads created by each scheme.

Ten Things Lawyers Should Know About the Internet May 25, 2009

Although this paper has ten points which concern laws and the Internet, they can be boiled down to three:

1. The laws relating to copyright, privacy, wiretapping, and common carriage are not relevant to the Internet today. Furthermore, trying to apply them to the Internet has many deleterious effects with no real gains, since the usage model of the Internet differs so much from the services provided at the time when the laws were written.
2. Furthermore, we actually know very little about the Internet from an empirical perspective. This is due to two factors. First, much of the current legislation (see point 1) makes it impossible (or rather, illegal) to gather the very information that would illuminate the usage patterns on the Internet. This hamstrings researchers, who are able to come up with many wonderful theories about current or future traffic patterns, algorithms, etc., but are unable to test or validate them on the Internet at large. Secondly, even when legal, these same efforts are frustrated by the fact that the Internet is composed of many private companies only motivated by relatively short-term financial concerns and unconcerned with the viability of their practices in the mid- to far future.
3. With both the legal and financial restrictions on what can and cannot be implemented, the Internet as it stands today is in a fair amount of risk. The underlying routing and naming services are insecure because they were designed for an Internet that is very different from the one present today. Not only are they insecure, but they are not designed to scale to the size of the modern Internet. Even though these problems are evident from even the limited amount of data available under current laws and from the companies operating the core routers in a secretive manner, the educated people who have exposed these problems are helpless to enact any change at a global level.

The main problem with this paper (and likely this summary) is that it views the current state of the Internet from a very pessimistic perspective. While it may be true that there are many unresolved problems on the Internet, it is risky for the researchers to look down from an ivory tower and proclaim that the Internet is doomed unless we do X, Y, and Z. What does need to happen is that government regulation needs to be designed in such a way as to not stifle the approaches that the market takes to optimizing the Internet for its current and future needs.

Future research needs to look at ways to incentivize the change that researchers think needs to be implemented. Unless they can provide economic incentives for the companies that control the Internet, then the changes will fall on deaf ears.

Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises May 12, 2009

Three Important Things:

• The motivating question for this work is that Ethernet networks provide several benefits such as “zero configuration” and a flat address space but do not scale well. The proposed solution operates at the network level and leverages a scalable DHT that does not require level 2 switches to maintain state for every host. Instead, host information (MAC, IP address) is mapped to a switch as the result of a distributed hash query. This removes the need for flooding in order to dissminate information, and protocols like ARP and DHCP can be replaced with on-demand queries and updates to a directory service abstraction.
• SEATTLE was designed to provide the appearance of regular ethernet to regular hosts, while maintaining a new internal network structure. This is a key selling point and paves the way for realistic, practical deployment. This feature is achieved by making the switches “link aware.” A switch is able to detect which links are connected to hosts as opposed to other switches by sending a control messge not recognized by end host level 2 NICs. Such links are treated in a special way in order to perform discovery and configuration. DHCP and ARP packets are snooped for this purpose.
• Experimental results were important in order to justify the claims of scalability and Ethernet class performance. Using simulation traces, the authors determined that forwarding table size is reduced by a factor of 41 in a 50K host network when compared to Ethernet. Table size and control overhead scale linearly with the number of hosts. In an Emulab implementation, SEATTLE switches significantly outperformed Ethernet in the middle of the network, however border switches required more processing time in order to deal with learning host addresses.

Glaring Problem:

Although a SEATTLE deployment would be transparent from the perspective of the end hosts, it would require a complete overhaul of the underlying network. This represents a significant cost barrier for an organization with a large existing infrastructure, the likes of which such a solution would be directed at. The authors dedicated little or no discussion to incremental deployment and coexistence with regular Ethernet switches and level 3 routers. Such a scenario has significant implications for the adoption of SEATTLE.

Future Work:

The DHT abstraction provided by the network is currently hidden from  the end hosts. Assuming the hosts can be made “SEATTLE aware,” they could make great use of the DHT for applications such as peer-to-peer content sharing. In order for this to happen future work would need to explore the necessary modifications to the host and possibly to the network.

ROFL: Routing on Flat Labels May 4, 2009

Three Important Things:

• The motivation behind flat routing is the desire to separate location from identity. Having labels be flat implies that no location information is stored in a host identifier. This fundamental change brings numerous advantages for individual hosts such as mobility, multihoming, and stable identity. These are the benefits of location/identity separation. Removing location altogether brings further benefits; The paper proposes to reuse DNS infrastructure to provide naming, which would leverage existing resources. Allocation must only satisfy uniqueness and does not need to confirm to the physical characterisitics of the network.
• Intradomain routing is a basic building block for the flat label scheme. A new arriving host is assigned to a first-hop router which is responsible for determining its “successor” and “predecessor,” effectively inserting it into a ring topolgy. In addition, the host is assigned an “external successor” for forwarding packets outside of the local domain. Packets are forwarded along the ring in a greedy fashion towards the destination host. The first-hop router can cache the path . Interdomain routing follows in similar syle, with the additional border router complexity for enforcing ISP policies. One can imagine each internal domain as a small ring, with the border routers for each domain forming their own large interdomain ring.
• In order to ground their claims of viability, the authors gathered traces from 4 moderate sized (200-600 internal routers) ISPs and performed several simulations. Standout results were 1MB of path caching on a typical router, 40ms host setup latency, and 45 control messages generated per host per join request. These numbers were for intradomain routing, and were used to extrapolate information about Internet scale networks. The authors felt they could do this because of the similarities between interdomain and intradomain routing.

Glaring Problem:

Though several interesting and exciting potential benefits of ROFL were presented, not all of them were explored in depth in the discussion that followed. Possible security applications were only briefly mentioned, and the adaptation of DNS to work with ROFL was not discussed. Host mobility was implied (through a rejoining operation) but not explicitly described.

Future Work:

Given that the performance simulation results for flat routing were largely unspectacular, it would be interesting to explore a hybrid flat approach. In such a scheme a small (possible fixed) number of hierarchical naming levels would exist. The requirement that location be separate from identity would thus be relaxed a little, and so perhaps desirable properties like mobility would be possible not everywhere but within a large geographic area. This would perhaps allow better scalability and performance, making ROFL a viable candidate for deployment.

Building a Robust Software-Based Router Using Network Processors April 30, 2009

(i) the three most important things the paper says

This paper addresses the feasibility of a software-based router while taking into consideration the specific interactions within the hardware design.  The paper demonstrates an architecture which the authors believe will provide sufficient worst-case performance while still allowing a significant amount of reprogrammability.  The first most important idea that the paper articulates is that this system is still not necessarily easy to program for because of the low-level programming required to do so.  I feel that the authors show, in this idea, that this system isn’t quite ready for any sort of implementation, but is more of a work-in-progress.  The second most important idea from the paper is the hierarchy that is used within its operation.  The authors dictate that packets that require the lowest level of external processing shouldn’t have to realize the latency of using the “higher-level” processors, but can instead be forwarded along at the maximum speed.  I believe that this bodes well for this design, so that the possibility of adding additional functionality later won’t greatly interfere with someone who may want to extract solely speed from this router design.  The third most important idea demonstrated is that this system can function well in the “worst case” conditions (minimum-sized packets).  This means that, ignoring any task that requires heavy processing, the design should function well for larger-sized packets.

(ii) the most glaring problem with the paper

The largest problem that I found with this paper was that they authors did not really address the operation of the system (performance-wise) in the event of a more complex algorithm for processing packets.  They spent most of the paper speaking about the worst-case operation.  It would have been much more enlightening to learn more about the typical-case operation and how that operation will scale with added functionality and algorithmic complexity.

(iii) the future research directions of the work

I feel that the next immediate direction of this work needs to profile a more typical usage case for this hardware, so that the research can show how this type of device will scale with added complexity.  The next direction for this work could be adding on to the programmability of the system, since many of the important aspects of the system must currently be programmed in assembly.

Building a Robust Software-Based Router Using Network Processors April 30, 2009

The authors note the flexibility of the software based routing systems and their increasing importance in the networks due to their flexibility. Their approach is to use specilized network processors on top of commodity PCs to achieve performance that is orders of magnitude better than the typical software based routers.

1) The authors show that software based routing on PC can be improved by orders of magnitude by utilizing a network processor. By doing so the network processor can take over the job of packet forwarding (data plane), allowing the packets to be processed quickly at line speed, and the PC processor can handle the signaling protocols. The network processor has multiple contexts that can work in parallel, and an efficient MicroEngine that can be programmed to examin the incoming data quickly. This approach combines the less flexible-quick network processor with the more flexible-slow PC processor and takes advantage of both flexibility and speed offered by both.
2) The paper provides a process hierarchy approach at splitting the router’s tasks into three separate areas: The data is either processed by the PC processor, by the network MicroEngine or by its StrongARM processor. By doing so, the bottleneck processing which is packet forwarding, can be handed to the more efficient network processor, and the PC processor can handle the rest of the data. A set of static Micro Engine contexts examines incoming MAC packets, and if necessary hand them to the StrongARM processor.
3) The authors show that both resource allocation and scheduling problems are approachable in a PC-based router solution. Resouce allocation is alleviated by the network processor: the MiroEngine decides whether the tasks are to be allocated to a router infrastructure for forwading at line speed, or if they are to be allocated to a virtual router processor for additional processing.

Glaring problems: The solution is based largely on the assumption that the majority of the traffic is forwarding packets. While this is true under realistic conditions, the software router would suffer performance under other conditions where ‘control plane’ traffic is high, since these are processed by the PC’s processor.

Future work: it would be interesting to see the combination of their single PC approach with the other assigned paper that describes using a cluster of PCs. This would provide the highest level of parallelism while still offerring the advantages of using a network processor. It would also seem beneficial if more user-friendly MicroEngines become available (they mention that there is no compiler and the code has to be written in assembly).

Can Software Routers Scale? April 30, 2009

(i) the three most important things the paper says

One of the most important things that this paper says, although the observation is not conclusive, is that it is feasible to generate multi-Gb routing speeds by using solely commodity PC parts.  This leads to the possibility of having software routing for higher speed links in the future.  I should note that the calculations and benchmarks used were not conclusive and were solely for “basic feasibility” (as the authors mentioned in the paper).  The next most important thing that the paper articulates is the need for non-typical switching topologies, which would be a whole new field of research within itself.  The authors noted that the number of interface ports on a typical server motherboard is not likely to scale (without producing specialized hardware, which was against the ideas set forth in the paper), so they must adapt their ideas to fit the hardware available.  A third important observation of the paper includes the conclusion that simplified high-level models of router operation on commodity PC hardware may actually reflect, to some accuracy, the actual operation of those routing ideas on the hardware.

(ii) the most glaring problem with the paper

The most glaring problem with this paper is the fact that there is little to no actual data presented and much of the observations presented had to be taken at face value.  Also, even though the models presented matched with the basic tests that were performed for this paper, it might not be the case that this carries over to the actual implementation of the routing system itself.  I feel that actual simulation might not reflect the results presented in this simple model as well as the authors would lead us to believe.

(iii) the future research directions of the work

A good future research direction of this work would be to establish a community around the topic by building tools that would help simulate the ideas presented here (and would thus allow others to more easily innovate upon those ideas).  I’m referring specifically to simulators, workloads, and the like.  This way, if the ideas presented here ended up yielding successful results in benchmarking, others could help to investigate other processor architectures or memory types easily.

Can Software Routers Scale? April 30, 2009

This paper examines the use of software routers. The authors observe that the current software routers, while flexible, do not scale well beyond 3Gbps, thus they examine the problem of making a general purpose software routing solution that is scalable. They key idea is to use a cluster of servers rather than a single server to do the software routing. They try to predict the performance of a server with known hardware specifications.

1. Past software routing solutions typically relied on a single server acting as the router. In this paper authors show that given clusters of general purpose servers it is possible (with optimism) to build a framework that supports rates close to 40Gbps using mesh architecture multi processors servers.
2. The authors observe that traditional shared bus architectures impose a high penalty due to the FSB speeds, but multi processor mesh architectures remove this FSB barrier and thus have a much better packet processing rate.
3. Several other techniques such as the use of Direct IOs by the NIC (NIC directly uses the processor cache), and integration of packets and descriptors are used.

Glaring problems: The authors seem too optimistic in their calculations (ie assuming a CPI of 1 may not be the case for many processors out there). Also, their solution is highly reliable on CPU and memory speeds, as well as a good system architecture. It seems that it would be rather difficult to provide performance guarantees for specific bandwidth rates.

Future work: The paper mentions that switching could be a problem but does not provide enough analysis on various software switching/routing algorithms. More work could be done to determine what switching solutions best suite interconnected-servers.

BGP Routing Policies in ISP Networks April 28, 2009

The paper describes common techniques used to implement BGP decision policy in boarder gateway routers. Because the BGP does not specify the decision process, a complex preference and filtering scheme as sprung up in the relatively simple path vector protocol. The use of route attributes allows ISP to implement custom routing policies as they see fit.

Routing decisions are therefore not always simply shortest path. The main contributions from this paper are descriptions of the ways in which ISPs (and enterprises) make use of these attributes, filtering, and tagging to achieve preferred decisions.

The authors describe that it is common for ISP to affect routing policy for business relationship purposes. A common technique is to set non-overlapping LocalPref values for each business entity. This allows specific routing to say customers over peers. Additionally, tagging is used to disseminate preferences internally while filtering the tags prevents external entities from receiving such information.

It is also common and perhaps necessary to adjust routing for inbound and outbound traffic according to quality of service and load balancing purposes. The routing attributes can be used here to affect import policy so that LocalPref values can be updated according to capacity.

Filtering community attributes is also used to limit amount of routing updates received and thus the routing table size. This is an important concern as it has direct consequences in terms of scalability.

Lastly, the authors describe how filtering on import can prevent invalid (malicious) routes from changing the routing table. Similarly, filtering on export avoids spreading infrastructure information to the rest of the network.

The main problem with this paper is that it assumes that any change to the BGP protocol is out of the question. While it may not be the focus of this paper, it seems that some discussion of how the protocol could be improved to better accommodate custom routing would be in order. Instead the authors focus on how the existing policy can be manipulated to provide routing policy flexibility.

I’d expect to see further work on the use of RPSL or other routing policy languages in Internet level experiments. It would be nice to see how much better a routing policy language can be as compared to the current methods of policy implementation.

BGP Routing Policies in ISP Networks April 28, 2009

This paper starts with an introduction to BGP and AS routing and then focus on the decision process BGP uses to choose routes. There are several factors that influence ISPs to implement certain BGP routing decisions.

1. Business Relationships influence the decision process which cause ISPs to assign LocalPrefs to determine which peering relationship is more desired to be used to route traffic. Customers may be most preferred, while backup links may be least preferred. ISPs may also want to control route exports to other ASs by prepending a community attribute to advertisements from a peer, and filter for that attribute when advertising routes to other peers.

2. Traffic Engineering is also a factor in an ISP’s BGP policy when there may be several routes that are equally preferred. For outbound traffic control, one common goal is hot-potato or early-exit routing where the ISP forwards traffic to the closest border router to avoid internal congestion at the cost of inflating end-to-end path lengths on the internet. Another common goal is to reduce congestion on outbound links via load balancing by changing LocalPref for a set of prefixes that matches a regular expression with the help of tools. ISPs may also have inbound traffic control to limit internal congestion or control how much traffic it will receive from peers. One way of controlling inbound traffic is by AS pre-pending to artificially inflate the AS-path length. Another way ois to use the MED attribute. Traffic can also be remotely controlled by having an agreement between two AS’s to have community values map routes to a LocalPerf on a remote router. This is done because MED applies next AS hop  and LocalPref applies to routes across all neighbours.

3. Scalability is of concern to ISPs as well. There is a common goal of limiting the routing table size by utilising the community attribute and filters. Another goal is to limit the number of routing changes by flap damping to limit propagation of unstable routes.

4. Security is a big issue since an AS is highly vulnerable to false BGP updates. ISPs can defend themselves by filtering invalid routes, protect routing policies by overwriting attributes to expected values, securing the internal network infrastructure by export filtering, and blocking DoS attacks via damping and filters to direct spammer address blocks to blackhole routes.

I didn’t find any problems with the paper as it is just describing common design patterns of ISPs deploying BGP policies. The paper cites research topics done to improve BGP and further research can by done in serveral areas:

- Configuration checking and simulators to predict how policies will interact.

- Language design for a vendor neutral language to express routing policies.

- Research in an overhaul of BGP. BGP is not a clean protocol since there are many ambiguities associated with decision making.

Multicast Routing in Datagram Internetworks and Extended LANs April 27, 2009

This paper talks about extending multicast beyond a single LAN. At the time of writing (1990) multicast was feasible in LANs, but not across LANs. In order to support multicast across multiple LANs, the paper offers extensions to three common routing algorithms for unicast:

1. Single-Spanning Tree Multicast Routing: Existing bridges of the day would forward broadcast and multicast packets to every segment of the extended LAN. To save bandwidth and processing time, the authors suggest one multicast member from each LAN to periodically send a membership-report to all bridges. When a bridge receives a membership-report from a multicast group G, it remembers which direction the packet arrived from. Any subsequent packets destined to group G would then be only forwarded along the direction of that group. For example if bridge B receives a membership packet from LAN C destined to LAN D, with multicast group G, then the bridge learns to forward packets of G from LAN C to LAN D, but not vice versa nor to any other LAN. This saves bandwidth that would otherwise be wasted by forwarding multicast packets along all segments connected to the bridge
2. Distance Vector Multicast Routing: by sending routing packets, routers maintain distance vectors to all other routers, thus enabling them to compute shortest-path routes to all other nodes in the network. The authors build on top of several existing unicast algorithms. Using Reverse Path Flooding (RPF), a router forwards a broadcast message from source S to all other links, iff the packet arrived from the shortest path from the router to S. Reverse Path Broadcasting (RPB) modified RPF so that packets are not forwarded to the parent router — router with minimum distance to S. This provides shortest-path broadcasting while avoiding duplicate messages. Truncated RPB (TRPB) builds on top of this but deletes child links that no router uses to reach the multicast sender. Finally, Reverse Path Multicasting (RPM) narrows the broadcast tree further by receiving non-membership messages from routers that are not connected to the multicast-group, and by removing these non-members from the multicast spanning tree.
3. Link-state Multicast Routing: Using this approach, each router monitors its attached links. Upon detecting a change in a link state, all routers attached to that link broadcast the change to every other router. By doing so, each router learns the complete topology of the internetwork, and can find shortest paths to any node in the network using Dijkstra’s algorithm. To extend this algorithm to support shortest-path multicast, the routers would consider creation of new groups or deletion of old groups as a state change, and broadcast this multicast-group-change to all other routers. Like the algorithms above, the hosts periodically send membership-reports to the routers in order to maintain multicast membership information.

Most glaring problem: The paper proposes many algorithms and ideas, but there is no implementation. The authors speculate the efficiency of their algorithm without providing any experimental results or simulations. Also the algorithms presented are non-trivial, and would require extra router memory, as well as increased processing. It is my impression that there might be too much overhead using the distance-vector algorithms. The link-state algorithm seems very simple and efficient but might not be practical across LANs because the state change is broadcast to the entire network.

Future research: it would be interesting to extend the distance-vector algorithms to use source-routing (I am not aware whether they do this or not). By doing so, a router who finds a shortest path for the multicast packet could specify this path and relieve the other routers from the burden of calculating shortest paths again.

Delayed Internet Routing Convergence April 23, 2009

Three Important Things:

• There is common acceptance that the internet in its current form is robust and efficient in adjusting routes in the face of link failures. Such occurrences are fairly common in such a huge infrastructure, and the authors recognized that it would be valuable to evaluate this accepted belief. By evaluating BGP convergence they came to the conclusion that inter-domain failover has significant delay, and that the path vector approach is incorrectly believed to provide improved convergence properties over distance vector routing. The claim is that the delay stems from ambiguity in the BGP protocol, and varying implementations across different router vendors.
• The paper was focused on experimental trails conducted over a long period of time, lending strength to the obtained results. The authors emphasize several points about designing and executing their experiments in order to produce quality, meaningful, relevant results.  Faults were injected into the actual internet backbone as opposed to a simulation environment. Latency effects were measured at the router level by routing ISP routing tables, this allowed the examination of several events: route repair, route failure, repair and failover, failurea and failover. End-to-end measurements were performed to determine the application level impact, the results proved that even moderate routing table flux caused packet loss, increased packet latency, and out-order-delivery.
• In addition to the hard data, the authors provide theoretical lower and upper bounds. The exploration of these bounds resulted in several insights about delayed convergence. For example, a lack of minimum route advertisement interval timer in some implementations influences the order in which link updates are processed, which impacts the rate of convergence. There are numerous implementation variations across vendors that contribute to the performance bounds.

Glaring Problem:
A major concern that I had with this work is that it only focues on BGP, and that it didn’t really discuss the parallels between inter-domain and intra-domain results. It would have been useful to see how the obtained results pertained to other routing protocols, if at all.

Future Work:
Following this thorough treatment of BGP convergence analysis, it would be useful to follow up on the root causes of delayed convergence and try to design new protocols, or at least new features in future routers that could help alieviate the strain on the internet backbone.  These topics were mentioned in the paper, but not at length. Such research would be crucial to the continued viability of the internet from a QoS perspective.

An Experimental Study of Delayed Internet Routing Convergence April 23, 2009

This paper presents the results of a very comprehensive study of routing convergence behavior on the internet. By monitoring the internet in many different places while injecting routing faults at various points in the network, they were able to measure in great detail the effects of such faults on both the routing tables themselves and their effect on end users.

They present a few important conclusions. The first is that the amount of time it takes for new routes to stabilize after a fault is actually much longer than previously thought. In addition to this insight, they have discovered that this delay will increase linearly in the best case and exponentially in the worst case with the number of additional autonomous systems on the internet. This presents a significant challenge to the designers of internet routers, especially if the growth rate increases more exponentially than linearly.

Their second conclusion is that much of this large failover time is due to differences in how vendors implement the BGP specification. If more loop detection was done by the sender instead of just at the receiver, the number of total updates could be reduced dramatically. However, this adds complexity to routers which are likely already quite expensive and complicated to design.

A third conclusion they arrive at is that different classes of update traffic have different behavior with regards to the amount of time and number of messages necessary to reach routing convergence. The loss of a route causes messages which are monotonically increasing while the addition of a route causes messages which are strictly increasing. While this may not seem like a significant difference, it actually has a profound effect on the convergence time, since it can take a long time for a faulted route to disappear from the system as routers bounce messages back and forth slowly increasing their distance to the faulted route until eventually they all realize that it is no longer present. This is in contrast to an added route, which either creates a shorter path which is propagated, or doesn’t, and doesn’t generate any new routes.

A weakness of this paper is that their bounds on the convergence rate of routes are fairly loose. While it is valuable to know that it is at least linear, the upper bound is quite high and does not necessarily describe the behavior accurately. However, since the growth rate is at least linear, future research needs to focus on ways to either improve BGP or supplant it with something more intelligent, which is less susceptible to implementation dependencies and superfluous messages during routing convergence.

IP Switching: ATM Under IP April 9, 2009

The main contribution is that ATM switches can be modified to provide level-3 IP routing using hardware. This results in utilizing less expensive hardware to provide higher performance IP routing. The authors identify that while IP is connectionless, many protocols and applications that run on IP do behave as though a virtual connection exists for some period of time. Thus, the existence of a switched connection under IP will benefit many applications. It seems that previous attempts to run IP over ATM did not exploit the connection-based nature of ATM.

Some key details of this approach include flow classification, the use of soft state, and a timeout mechanism. Flow classification allows the IP switch to identify which packets represent a flow between two hosts. An identified flow suggests that packets will be exchanged between the same two hosts because they are engaged in some type of application based conversion/exchange. The authors admit that many flow classification schemes are possible. They chose to identify flows in two ways: between hosts with the same TTL and between hosts with the same port (service-type) and TTL. In the former case, flows were established only after a number of packets were exchanged. In the latter case, flows were setup immediately (as the service types are known). Once a flow is established, the routing no longer involved store-and-forward processing via IP software. The routing was accomplished by switching packets based on setup virtual ATM circuits.

Soft state is employed to provide a cache-like mechanism for each IP switch. When flows are being established, some cached packet history is needed. Similarly, when the flows are established, they need to be tracked so that they can maintain the virtual ATM circuits. However, because each IP switch is autonomous and may fail at any time, this soft state is not absolutely required. It can be rebuilt if lost. Moreover, it is designed to be updated dynamically as the topology and traffic changes.

This leads to the last key detail, the use of timeouts. Each flow is established for a limited amount of time. This prevents virtual ATM circuits from being permanently allocated. If however a flow is continually used, the IP switches will periodically refresh the flow lifetime to keep it alive. This approach allows flows to not consume too many ATM resources and still provide switching for those flows that need it.

Although performance simulations are provided (based on Internet and corporate traces), there is no performance comparison between other IP routing approaches. Several different approaches are described. Based on the descriptions it seems rather glaring that no performance evaluation was done to identify how viable an alternative this IP over ATM approach really is.

Although it appears that crossbar switch based IP routing as won out, I’d expect further research in this area to involve exploring the multicasting benefits that ATM switches may be able to confer. It seems that given the inherent point to many architecture of these devices that they may be able to out perform traditional crossbar switching.