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

Main Points:

1. This paper is another important step in the emergence of software-based routers. The authors describe  their experiences using network processors like Intel IXP1200 to build a router.
2. They propose a processor hierarchy in the routers, by having the data plane (data packets) handled by a microengine at line speeds, whereas the control plane traffic (control packets like LDP, route calculation etc) handled by sophisticated Pentium at the top of the hierarchy. This ensures separation of functionalities and responsibilities across layers.
3. The paper provides immense insight to a network designer into the general approach to design a network router. They describe the hardware used, the data structures involved at the classifier, forwarder and scheduler, and the queuing discipline they employed.

Problems:

While they dwell on the possibility of having multiple forwarders between classifier and scheduler, they do not adequately consider such scenarios in their implementation. They mention that to simplify their analysis, they have considered only the straight-forward input-port/output-port forwarding.

Future Work:

I see scope for future work in the aspect of using different hardware. They use 700 Mhz processor at the lowest level. If today’s technology permits them to use a much more sophisticated processor there, would there be a possibility of shifting some of the control traffic handling to the lower layer — thereby, avoiding some of the performance loss due to layering.

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

One contribution of the paper is that the authors describe a design to achieve fixed routing functionality using the 3 level processor hierarchy and the parallelism offered by the microengines. The authors describe how the IXP micro engines can be used to get the fastest data path forwarding while allowing exception packets to be sent to the StrongARM processor or the even higher layer Pentium  processor. At each higher layer, more memory and processor cycles can be spent on each packet, but the latency to forward the packet as well as the throughput in terms of number of packets that can be processed per second decreases.

Another contribution of the paper lay in the fact that the authors were able to get have easily programmable/extensible protocols or functionality inserted into the three levels of the processor hierarchy with specific constaints on the processing at each level such that a particular functionality inserted into one level does not adversely affect the forwarding in the other layer.

An important concept that the paper brings out is the separation of policy from mechanism (although the authors do not exactly describe it). Each lower layer in the hierarchy provides mechanisms to implement the policies that the higher layer would like to achieve. Certain mechanisms supported by the lower layers allow some functionality to be achieved entirely in the lower layer in which case the lower layer can then handle that functionality for all remaining packets of the flow. This analogous to the fast path / slow path differentiation seen in modern switches. The policy or routing decision is typically taken by the slow path, but the fast path eventually achieves that policy by forwarding at line rate.

One of the weaknesses of their approaches however is that they only experimented with a very restricted model of routing. The forwarders that they implemented or were able to achieve at the lower layers were very simple and most routers require more functionality than that. For example they mention in the paper that IP prefix lookups had to be done only in the Pentium (or the slow path). So this raises questions over whether their approach can scale to higher speed routers. The other challenge is that writing more complex forwarders entirely in assembly is going to be hard and with different network processors having different instruction sets etc, this can be a huge hurdle.

One possible direction of research is to explore what is the right set of primitives that the lowest layer (implementing the fast path) must provide to the higher layers, while still being able to achieve acceptable levels of extensibility. If the switch

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

Paper proposes to build a software router using a network processor (Intel’s IXP1200) and PC.

Paper uses a hierarchical approach to provide the flexibility of extra processing while supporting the high speed switching.  Software based router performance has been increased with the nelp of network processors. IXP1200 has 6 micro engines each supporting four contexts. Context provides the execution while other are waiting for the memory operations. Paper defines the implementation by segregating the task into data plane and control plane. Data plane does the forwarding of packets while control plane runs protocol like RSVP, OSPF.  This requires processing at line speed while control planes are expected to receive fewer packets. Network processor is used for running the data plane and PC processor for control plane.  Data plane requires less computation while control plane requires more computation. Many of the applications lies in between where packets have both the characteristics. Paper treats the router as processor hierarchy, where packet flow different levels of hierarchy. These hierarchies are microengines, strogARM, Pentium. One important aspect of this hierarchy is the fact that going higher layers uses the resources of all the layers.

Paper addresses the resource allocation and scheduling problems for an extensible souter on this three level hierarchy. Three goals of the paper are performance, extensibility, and robustness. Software architecture of the router consists of three main components:

1. Classifier: this reads fields in the packet and based on the attribute it decides to sent to a forwarder
2. Forwarder: Forwarder takes a packet applies appropriate function to it and forwards it to the output queue.
3. Output scheduler: selects a packet from non-empty queue and transmits the associates packet to the output port.

This architecture provides additional flexibility to add any number of forwarder, forwarders are not linked to any specific processor (microengine, strongARM, Pentium). Architecture does not distinguish between forwarders based on the data plane or control plane.

Paper discusses the design issues involved while treating all the processors in a hierarchy.  More complicated forwarders require more-cycles-per-packet which might reduce the maximum forwarding rate.

Paper suggests that based on their experience that static allocation of resource (task to context and context to port assignment), coupled with scheduling through token passing mechanism, and yields the most effective router. Register allocation should be done properly to achieve good performance. Paper further suggests that key innovation is to statically partition the processing capacity of the microengines into a fixed routing infrastructure and virtual processors.

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

This paper describes the implementation of a software router using Intel IXP1 1200 network processor and an Intel P3 PC. The authors emphasize the significance of the software-based routers because of the increasing array of services like firewalls, intrusion detection, proxies etc. demanded from the routers. The emergence of network processors has come as a boon to this thinking since it’s a specific processor developed for network applications. The router described in the paper implements both the data plane that forwards packets and the control plane where signaling protocols run. The requirements of speed are demanding on data plane at it must support line speed therefore it must perform minimal processing on the packets and the compute intensive tasks be handed over to control plane which receives fewer packets (new connections come up, routes to be decided etc.).

The approach taken is to treat the router as a processor hierarchy where packets follow switching paths that traverse different levels of the hierarchy. This hierarchy consists of the microengines of the IXP1 1200 at the lowest level, StrongARM processor at the middle and the Pentium at the highest level. The number of cycles available decreases from higher level to lower level since lowest levels must work at line speeds. The authors implement their extensible router on a three-level processor hierarchy with the goals of performance, extensibility and robustness.

The software architecture of the router consists of a classifier, a forwarder and an output scheduler. The role of classifier is to read packets from input port and select a forwarder to assign a packet to based on the packet header. The forwarder performs transformations on the packets and sends the modified packets to the output queue which are retrieved by the output scheduler to transmit to the output ports. Their architecture has two main attributes mainly, the explicit support for adding new services to the router and no fix mapping of the forwarders to the levels in the processor hierarchy. The paper discusses the performance bound on each of the levels in the hierarchy and how the context scheduling of each of the microengines and the mutual exclusion is achieved between the operations. The authors also discuss some insights into their packet switching, managing queue contention and the various optimizations performed. They perform experiments to measure the maximum forwarding rates and the excess per packet processor cycles. They find that an aggregate of 3.47 million packets can be forwarded per second and the upper limit is posed by the serial input of the DMA. The StrongArm processes at a maximum speed of 526Kpps and the limit enforced by Pentium is 534Kpps. The authors also talk about a virtual router processor that runs additional code on behalf of each packet. Essentially, the virtual router processor runs the protocol-processing step and supports a fixed number of cycles for each Mac packet.  The authors also performed robustness experiments in tune with their goals and ran synthetic suite of forwarders on configured Microengines.

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

The authors describe a 3 tiered processor structure for a software based router using a Pentium computer and a network processor (also from Intel). The aim is to show that using the tiered approach data and control packets can be routed at Gbs line rates while allowing for software based protocol extensibility.

The Intel network processor board comes with DRAM and SRAM caches as well as several MicroEngines and a StrongARM processor.  The MicroEngines are programed using microcode and can perform very fast rudimentary instructions (dequeue, enqueue, copy, etc.). The MicroEngines can operate in parallel servicing input and output ports. The StrongARM processor is used to service exceptional packets, those that incur a route lookup miss or are control packets. The StrongARM process runs as a single process and is capable of forwarding even more “exceptional” packets across a PCI bus to the Pentium processor. The Pentium processor is used to perform compute intensive operations such as calculating shortest paths.

The main contributions are in the design of the 3 tiered architecture and the design of the protocol extensions interface.

The architecture defines a fast path and a mechanism for routing through a longer path (more compute intensive). Packets arrive at an input port where they are queued in a FIFO. The packets are then processed in parallel by the MicroEngines that perform classification on the type of packet. If the packet can be forwarded on by the MicroEngines, they perform whatever transformation is necessary and enqueue the packet in an output FIFO. If the packet requires further processing, it is put into RAM where the StrongARM processor will check for packets to process. The StrongARM processor may copy some or all of the packets onto the PCI bus for the Pentium processor to service. The Pentium can copy back transformed packets via the PCI bus. When the StrongARM has completed the processing (or received the completion from the Pentium processor), it is responsible for forwarding the packet to the appropriate output queue. MicroEngines also work in parallel to service copying from output FIFOs to the output ports. Contention for output ports is solved by using mutual exclusion (implemented using a passing token).

The second contribution involves the interface for which extensions can be installed. The Pentium processor can functions on the StrongARM processor that register/unregister custom fiilters. These filters are used by the StrongARM to identify and forward specialized packets (conforming to some new/extended protocol) up to the Pentium for processing.

The paper provides a very detailed description for building a network processor + general purpose processor based software router. The authors’ results are impressive as they report a processing line rate of 3.47 Mpps.  What seems a bit unaddressed is what would actually happen if a new/extension protocol were implemented using this architecture. If that protocol required Pentium level processing for each packet, it seems as though the line rate would drop considerably. So from a practical perspective, one would not actually want to run their new protocol using this hardware (despite the fact that it could be run).

I’d very much like to see performance results of line rates for traffic using one of the extensions proposed in the paper. This paper does a great job of explaining how traditional traffic can be supported at high line rates but does not provide results from more complex protocols implemented using their design.

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

(i) The three most important things the paper says:

1. It is possible to build a cheap but effective routers. The authors combine a IXP1200 network board and a PC to build a router capable of forwarding an order of magnitude faster than the pure PC based routers. This gives them  three processors which are exploited to gain much higher throughput than average PC based routers of the day.

2. Specifically the author demonstrates how to obtain performance extensibility and robustness with a three level processor hierarchy. It explains in detail how to manage scheduling and resource allocation to gain great performance. On there board they dedicate the MicroEngines to reading and transferring packets from input to 0utput ports while exceptional conditions trap up to the StrongARM processor.

3. The author also points out another major gain of using this nerwork board rather than a pure PC. The board has extra resources it can devote to extensions to the router. Examples of the services that can be added are: performance monitoring, intrusion detection, denial of service detection, etc. These things were being put off since the PC would have to sacrifice performance since its processor would have to perform these tasks on top of the routing tasks.

(ii) The most glaring problem with the paper:

The author does not address how this architecture avoids the normal problems of separation and hiding when in a hierarchy. Meaning what performance hits do you take from this separation. Certain pieces may longer no about information which means extra transfers of data etc. Especially when later going for more complex performance boosts.

(iii) The future research directions of the work:

Something mentioned by the author that could have substantial gain are coming up with background work the processors could attend to during down time. Finding useful activities would make for better cpu utilization. Another necessary research topic is even if we do have a well defined hierarchy of processors, what about when we want multiple processors sharing one portion of the hierarchy.

Building a Robust Software-based Router using Network Processors April 30, 2009

Most important contributions

While a number of related approaches tried to implement software routers using a single general purpose processor, this paper introduced a new hierarchical processor architecture to be used in the forwarding engine of routers. The architecture consists of three different processor levels with different functional and performance requirements. The authors assume that the majority of packets processed by routers can be processed by very simple, dedicated and parallel engines. The main rationale behind the architecture was robustness, performance and extensibility. The goal was to preserve the performance and robustness of dedicated hardware-based routers while opening new extension points for a smaller number of packets.

For every packet, depending on the processing needed and the complexity of the forwarding engine involved, it is moved to a different processing layer. For each processing layer as the packets have to be transported up, the performance penalty increases and therefore the forwarding rate goes down. But since higher level programming languages are available on the higher processing levels, they are broader in application to extensions to routers.

The authors treat even the normal IP-Forwarding engine as an extension to their architecture, therefore proving their point about extensibility.

Most glaring problem

It is unclear whether the authors address the scalability issues of these software based routers enough. Whether the same design (with it’s memory access rates and processor speeds) still works for routers at Gigabit or 10-Gigabit speeds is not obvious.

Possible future work

Since this work might have triggered a standard architecture, but at the very least a standard operation set for forwarding engines when accessing/manipulating the routing packets, the most urgent work would be to standardize and harmonize these APIs and architectures in the routing industry

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

Important Things:
1) Demonstrates how network processors can be used to design a flexible and extensible router. The system is reporgrammable due to it being software-based. Simple extensibility is acheived by separating high-level functionality (implemented as extensions) from low-level mechanisms which are used by all extensions.
2) Demonstrates how the performance capabilities of the network processor can be harnessed. Presents a hierachical design which leverages the throughput of MicroEngines for high-volume traffic with simple processing requirements while allowing for more complex control protocols on a general-purpose CPU higher in the hierarchy.
3) Evaluates the performance and limitations of the design. Discusses implementation challenges and their solutions, particularly in regards to resource allocation and scheduling.

Problem:
Full IP, prefix matching, and other forwarders could not be done on the MicroEngines, so if this functionality is desired, performance is severely limited.

Future Work:
Given today’s performance demands, what are network processors capable of, how much flexibility do they allow, and how do they compare to other flexible alternatives?

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

This paper describes the architecture and implementation of a packet router which takes advantage of both a dedicated network processor (an Intel IXP1200) and a commodity Pentium III in order to provide a combination of high forwarding speed for small packets and rich services for control packets. They start by describing their basic line-speed packet forwarding mechanism, where a two-stage pipeline running on the MicroEngines moves packets from the input ports to queues, and from the queues to the output ports. This architecture is helpful because it allows easy extensibility when they want to add more functionality, provided by the StrongARM and Pentium processors.

Based on some performance numbers they obtained, it was decided to avoid implementing much of the robust functions on the StrongARM processor because they required most of its bandwidth and processing time to move packets between the MicroEngines and the Pentium.

Their final design used the concept of “virtual routing processor” (VRP) to provide rich services for control packets while allowing line-speed routing of simple packets. To do this, they gave their VRP a fixed number of cycles to perform its task in order to avoid penalizing simple packets. This requires validating VRP routines before installing them to ensure that they do not consume too many resources. Once this is done, the processing stage of the MicroEngine can either run one of the simpler VRP routines directly or hand the packet off to the higher levels of the processor hierarchy (StrongARM or Pentium) to perform more complex computations.

A weakness of their approach is that most of the code must be hand-crafted in assembly, since there is no compiler for the MicroEngines. This restricts the flexibility of the architecture, since the queue layout and therefore the implementation of the VRP is dependent on the architecture of that particular network processor. However, the lack of flexibility is balanced by the high performance attained by hand-coding the assembly. Since forwarding millions of packets a second is a very real requirement of commercial products, perhaps the greater amount of work required to implement the architecture on different platforms is worth it.

Future research in this area could focus on ways to find the optimum performance/flexibility point (as mentioned in the previous paragraph). Perhaps by adding a level of abstraction in a key location, performance can be maintained while allowing the code to run on more variegated platforms.

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

1. This paper describes the implementation of a software router built from a 733MHz Pentium III connected to an IXP1200 development board running on a 200MHz StrongARM CPU. The cost was roughly $1500USD and performs an order of magnitude faster compared to pure PC software routers.

2. The paper contributed a packet processing architecture with three switching hierarchical paths. The lowest level of the hierarchy, packets gets processed by the hardware microengines. At the intermediate layer, packet has access to StrongARM cycles. At the top layer, packet processing have access to cycles of the Pentium processor. Packets are switched to the layers based on a classifier, forwarding, and scheduling architecture.

3. The paper then contributes the experience of designing a fixed routing structure that fully and robustly exploits the IXP1200’s parallel hardware microengines.The paper talks about the bugs, optimizations, and synchronization issues encountered.

Further research can be done in this area by using newer hardware than was available in 2001. Different levels of hierarchy and different architectures can be explored with the variety of faster hardware available today.

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

The paper proposes the idea of a scalable software router that can handle and forward packets at rate comparable to conventional routers. They describe their experience of using emerging network processor, in particular the Intel IXP1200, to implement a router. They have shown that to is possible to combine an IXP1200 development board and a PC to build an inexpensive router that forwards minimum sized packets at a rate of 3.47 Mpps which is nearly an order faster than PC based routers and sufficient to support 1.77 Gbps of aggregate link bandwidth. The router implements both the data plane and the control plane where the former has the responsibility of forwarding packets at line speed while the latter does complex jobs like finding shortest paths to nodes and building routing tables. They have taken advantage of the underlying architecture which supports multiple cores each with many hardware contexts. Hence the software for processing packets has to be managed in parallel hardware contexts in a way that fully utilizes the available memory bandwidth. The architecture of the router has been divided into input queues and output queues and several forwarding units between them that parallely read packets from input, process them and finally write to the output queue. The architecture has the flexibility of adding new functionalities to the router. It also gives the freedom of where in the processor hierarchy each forwarder is implemented .

The conventional memory based processing can become a bottle neck in such architecture. Specially since the input and the output queues are shared between the multiple hardware contexts, they have to be protected by mutexes. This can add extra overhead for lock contention when all the threads are simultaneously trying to acquire the lock. Finally programming a network processor platform is complex since all code is written in assembly language due to lack of a compiler for such specialized application. This can lead to difficulties in upgrading different policies and adding services to the router. Also being written in assembly, critical portions of the code can become really error prone.

Future works can be done in a evaluating the flexibility of the network processor based router and its programmability. Research may also include the study of how efficiently emerging general purpose chip multiprocessors and state of the art I/O can be used to match data forwarding rates of conventional hardware based routers. Finally for specialized application like network packet processing and forwarding emerging GPUs can play a huge role in providing high bandwidth and scalability. Thus the distinction between hardware and software based router will hopefully become less meaningful.

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

(i) The three most important things the paper says:

1. The paper describes the authors’ experience with building a software router using the Intel IXP1200 network processor with a commodity PC. They identify three switching paths through the processor hierarchy — on the Pentium, StrongARM, and/or MicroEngines (from the highest to lowest level) in order to achieve the amount of required processing. The paths are not completely independent; for example, the path which sends packets to be processed by the Pentium requires the packets to pass through the MicroEngines and StrongARM. The MicroEngines work in parallel and use a fixed routing infrastructure.
   
2. One of the key benefits to using a software router is the ability to build extensions to perform such tasks as performance monitoring, firewalling, and packet dropping and tagging, among others. The described architecture allows these functionalities to be implemented by allowing programming in the data plane. This is done with a data forwarder on the network processor and a control forwarder on the Pentium to control the actions of the data forwarder. The forwarders are “budgeted” within a virtual router processor.
   
3. By using protected public queues with no contention for input processing, and a single queue with batching for output processing, the system is able to foward minimum-sized packets at 3.47 Mpps. Furthermore, even in the the face of many exceptional (control) packets which exceeding the processing capacity of the StrongARM, the forwarding rate was sustained at 3.47 Mpps.
   

(ii) The most glaring problem with the paper:

The experiments were performed with only minimum-size packets. I would be curious as to what kind of bandwidth is achieved with larger packet sizes (such as 1024 byte packets, as used in the “Can Software Routers Scale?” paper. Furthermore, the paper does not really address the scalability of their solution except a passing mention in the conclusions. I think it would have been worthwhile discussing the advantages and potential problems in scalability inherent to their architecture.

(iii) The future research directions of the work:

One potential research direction is to add the admission control mechanism described in section 4.6 to decide which forwarders to install. In addition to the functionality described in that section, it may also be worthwhile to add functionality to the admission control mechanism which detects and handles misbehaving forwarders (either unintentional or malicious). The authors also mention the lack of a compiler for MicroEngines and voice their doubts that such a compiler is feasible. Although this may be the case, it might be interesting to see if there was some set of abstractions that could be obtained and accessed through an interface such that managing parallel resources could be simplified a bit, and not need to be completely done in assembly language.

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).

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

This paper presents a software based router that exploits a three-layer processor hierarchy architecture.

The main features of the proposed solution are the following:

1. Separation of data plane and control plane. The former plane forwards packets from the input port to the appropriate output port. The latter plane instead defines the policies for such forwarding.  The main differences between the two layers are that the data plane must process packets at line speed, hence it has only few cycles available per packet processing. Instead, the control plane has a theoretical much smaller workload but it can run computer-intensive programs, such as shrotest-path algorithm. This separation between data plane and control plane allows the system to be much more flexible and axtensible than other already existing solutions where the two planes are combined.
2. Flexibility and extensibility. As already mentioned at the previous point, the fact that the proposed system implements the control plane in a different place than the data plane allows the system to be flexible and extensible. In particular, it is possible to inject new routing policies or new features at run time, such as firewalls, TCP proxiex, virtual LANs etc. , without having to tear down the router nor having to rewrite the code from scratch. In this system, a new functionality injection results in basically adding a new forwarder F to the router.
3. Full exploitation of the hardware parallelism. With their ad hoc programming, the authors achieved great performance out of the three level processor hierarchy by exploiting the parallelism of the IXP1200 MicroEngine. The authors also presented interesting guidelines on how such programming should be implemented.

I can see two main critiques to this paper.

1. The tests showed in the paper and the implementation presented are very basic and trivial. In particular, they have not stressed the system with the heaviest forwarding policy types workloads. Most of the authors’ benchmarking is based on trivial IP forwarding. As they explained, the system must be able to handle packet forwarding at line speed. They claimed their system does it. However, it is also clear from their analysis that their architecture present a big bottleneck with the StrongARM. Even if the system is handling only basic IP forwarding, the StrongARM is already at full capacity and not able to provide any more cycle/packet. This would be required though when a more complex functionality was inserted into the system.
2. The paper is 8 years old and at the time line speed was considerably slower. The system is structure to handle 8 100Mb/s Ethernet connections. As said at the previous point, the system is already at full capacity. Nowadays, we have 10 Gigabit connections, hence 2 orders of magnitude faster. The processors have not had such a speed up in the same time. They are only few times faster than 8 years ago. This is as the same time a potential bottleneck and also an interesting avenue for further research. Indeed it would be interesting to see how the proposed architecture scales up with the increased connection speed.

Building a Robust SoftwareBased Router Using Network Processors April 30, 2009

The paper discusses the design of a software based router using Intel IXP1200 network processor platform and an Intel Pentium III PC. The claim is that a cheap extensible router configuration can be built without having to use the ASIC technology and still get similar gigabit throughput performance. The authors implement the data plane/forwarding plane of the router which requires line speed processing without priority inversion on the IXP platform and they use the Pentium to implement the control plane of the router which needs intensive processing capabilities. The IXP internally contains 6 micro-engines and a strong ARM processor, thus making a three tiered processor hierarchy along with the Pentium and the paper presents a detailed description of which functionality is/could be implemented at each level of this hierarchy. The paper highlights the three main topics, viz. the system architecture, the fixed infrastructure required for minimal forwarding and the extensibility argument.

The system software as described in the paper primarily consists of a classifier which receives and reads packets on the input queue and redirects them to appropriate forwarder which then processes the packets and forwards the modified packets to the output scheduler. The scheduler ultimately schedules the packets on the output queue connected to the output ports of the router. This architecture allows for software extensibility and processor independent forwarder implementation. The hardware mainly consists of the processor hierarchy and associated DRAMs and SRAMs that implemented the queues mentioned in the software architecture and are capable of supporting several gigabits of aggregate forwarding bandwidth.

The paper then establishes a performance bound that can be achieved by each level in the processor hierarchy. The authors specifically highlight the mutual exclusions and parallelism considerations when programming the micro-engines of the IXP since they present multiple contexts. Micro-engine contexts forward 64-byte MAC packets in a two stage pipelined fashion with DRAM acting as the pipeline register. A pipelined approach is used to avoid contention on the output ports and to efficiently utilize all the processing contexts. An incoming packet is DAMed onto the on-chip memory and subjected to software protocol processing. To enable multiple micro-engines to process the input packet’s MPs in parallel, they are statically scheduled on to process contexts and mutex synchronization is used to mutually exclude them. Although processing happens on multiple contexts simultaneously, output contexts need to be serialized to obey packet ordering and this is done by passing token between contexts. Just like at the input, packets when processed are removed from contexts to output queues by static scheduling. The authors do a performance evaluation on the processing capabilities of the micro-engines and demonstrate that an aggregate through of 3.47 million packets per second are processed without losses and the upper limit is posed only because the input DMA engine is serial. When the micro-engines detect a routing cache miss or further protocol processing, they signal the strong arm to accept the packets from the DRAM for processing. The strong arm is shown to successfully process 526kpps and the only overhead is because of the handshaking between micro-engine contexts and strong arm. All control plane processing is handled inside the Pentium which is supports close to 534kpps of aggregate throughput.

The third major discussion in the paper is on the extensibility of the proposed architecture. Addition of complex forwarders and integrating the control plane into the overall architecture are seen as the possible extensions. The authors expose the limitations of the system in the form of strong arm having to share signaling with Pentium and sharing DRAM with the processor contexts. To circumvent this, the authors propose to add additional code in the form of a virtual router processor (VRP) over the micro-engine contexts to augment the packet processing capabilities. VRP budget and line speed rate processing are shown as conflicting goals and the authors propose to make extensions by fixing either. The authors propose performance monitoring, packet splicing and smart packet dropping as examples to demonstrate the possible extensions that can be made to their architecture by executing data plane on the IXP processors and control plane on the Pentium. They further propose an interface and a set of operations required to seamlessly integrate IXP and Pentium. The authors finally test different workloads on the system to validate its robustness in the event a transfer of processing capability is required up the hierarchy.

One major problem with this paper was that it lacked substantial performance evaluation data and the main focus was centered on the design implementation. The feasibility and deployment of the system is questionable since a crude PC-PCI-IXP interface is used to demonstrate it at a high level. Even with these limitations the paper opens up an arena of possibilities in the software router space and establishes a base for developing routers entirely on network processor platforms and PC hardware.

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

1. The paper presents a router design incorporating in itself both hardware and software features. The hardware components provide the speed and computation power required of a network processor, while the part of it implemented in software provides it with the flexibility to handle any protocol and to extend the current model to support new additions and changes.

2. The hardware portion of the router is implemented as a hierarchical structure. Though a hierarchical implementation has its shortcomings, it provides a simple structure which allows packets with different requirements to be processed at a different level. This way, only those packets that require more complex computations to be performed are forwarded to the upper layers. In addition, the hardware implementation also provides for “efficient” parallel processing. Efficiency here refers to, realizing parallel processing while keeping the overhead of parallel processing with shared resources to a minimum. The paper achieves this by implementing token passing. Only the unit in possession of the token can use the shared resource.

3. The paper makes some interesting trade-offs. By allocating fixed buffers and queues to each context (unit of hardware), it chooses speed over amount of resources to be provided. It also fixes the lifetime of a buffer so as to eliminate booking overhead. It chooses to make the structure as general as possible at the cost of efficiency achived from making a design protocol specific.

Shortcomings:

The hierarchical structure, while having its benefits, has its shortcomings. A three tier hierarchy means that every packet the needs to get to the highest tier needs to pass through all the lower ones before it can get there. This results in unnecessary consumption of time and resources. There are a few other choices they make that come at a price. Their use of token to co-ordinate amongst multiple contexts sharing a resource, while reducing the overhead of implementing mutual exclusion, means time is spent in giving contexts that donot require a resource a chance to use the resource. It also means priority is neglected while servicing ports. This is a conscious choice made on their part.

Future Work:

The design proposed by them has several avenues for additions and extensions. The model they propose is generic with maximal flexibility. A similar hardware/software system could be designed for real time networks. Features such as priority would be an important consideration is such a system. If flexibility isn’t a major criterion, a non-hierarchical structure could also be explored.

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

(i) The three most important things the paper says:

1) Advances in network processors warrants a revival in the discussion of software based routers on conventional PCs. These network processors are relatively inexpensive and have features such as parallel processing capabilities to improve pps (packets per sec).

2) Consideration of the three processor hierarchy as an integrated whole. This was a key point because if they were to introduce the network processor as a viable solution, there must be a plan to make it all work together. So in their paper they outlined all the potential issues along with their design solutions (e.g. running a minimal OS on the StrongArm).

3) They demonstrated how they can inject new features into all three levels of the processor hierarchy without jeopardizing robustness for different workloads. This is an important point, because this is a feature that sets them apart from standalone HW solutions. If this feature wasn’t robust enough, there wouldn’t be a compelling reason to switch to this solution.

(ii) The most glaring problem with the paper:

The biggest problem with the paper is that it focuses too much on the technical details and not enough on the impact of this work in a commercial setting. For example, how does this solution compare with standalone hw based routers in terms of power consumption. Also, how does this setup compare in terms of time to failure (aka stability of system)?

(iii) The future research directions of the work:

The future research of the work would be to take the lessons learned and system in this paper and extend it to a clustered solution of conventional PCs. This is because to make this solution viable in a commercial setting, there must be support for growing a network infrastructure.

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

i)

1. Seperating the data plane from the control plane and having a processor heirarchy allows normal packets to be forwarded at line speed while having a more powerful processor deal with exceptional packets. This allows for a software based router that can operate at line speed for normal traffic.

2. By statically allocating memory and processors, the issues of guaranteeing line speed forwarding is made easier, but it is at the expense of making portability to platforms with differing number of ports & port speeds more difficult.

3. Allowing the network processors to run any code as long as it fits into the resource budget allows the router to be extensible, while also ensuring guarantees on line speed routing for non-exceptional packets.

ii) I was unsure why the StrongARM was necessary and why it was necessary to have it on the path between the MicroEngines and the Pentium. The flaw in this paper is not adequatley explaining the reasoning for having the StrongARM between the MicroEngines and the Pentium and/or why the Pentium can’t be eliminated all together by simply getting a faster ARM processor.

iii) I think the future research areas include researching what capabilities can be implemented at line speed forwarding and what requires higher level processing.

Can Software Routers Scale? April 30, 2009

The primary contribution of the paper is a design of an entirely PC based architecture for software based routing at line rates. The authors have made an attempt to quantify the maximum possible theoritical performance that is possible using a particular PC architecture and also provide experimental results that describe the actual performance achieved.

An important aspect of the paper is that it focusses on achieving extensibility or easy of upgradation in routers. This has been a very crucial bottleneck to upgrading the internet router infrastructure.

The authors propose a mesh based topology with valiant load balancing to scale without being limited by a single PC’s processing power. Also they propose that L2 switches can be used in the valiant mesh to avoid the bottleneck of fan out at a single node

One missing aspect in their discussion is their discussion focusses on very simple routing / forwarding (raw speed) which could very well be the case for core routers – however other routers do perform more tasks than that. Extending the analysis for more complicated routing aspects would have given the paper more credibility.

Future research can explore if different topologies can offer better performance (such as fat trees). Also exploring price points of the PC based architectures vs. traditional architectures is another aspect.

Can Software Routers Scale? April 30, 2009

In this paper, written by several people from Intel and academics, an introductory analysis of the feasibilty of software routers is presented.

The first impression I got reading this paper is that it is only an early introductory paper. It basically presents only conjectures on whether a software router can keep up with the high volume workload that hardware router can handle.

Still, I can see the following a couple of interesting points in the paper:

1. Analysis of software router bottlenecks. The authors did a quite extensive work in understanding where the bottlenecks of a software based router implementation are. In particular they identified the FSB and the memory system as the most problematic points. As solution they suggest a multicore architecture with point-to-point interconnections between c0res and memory in order to avoid the shared bus.
2. Scaling switching analysis. The authors identified that another issue related with software routers is a scaling problem of switching packets from input to output ports. The workload that a standard pc, where usually a software based router is implemented, can handle is far lower than a specialized router. The authors present a interesting analysis of the reasons why a pc based architecture can’t scale too much and suggest a solution based on the Valiant load-balanced routing algorithm.

The main flaw of this paper is that it does not present much content. All the details of the hardware analysis are related to a previous work of the authors and only the results are presented here. The analysis they present of both the single core and multicore architecture is very approximated and weak. They claim a 4 times increase in performance for the latter implementation, but in the paper a complete evaluation section of a real full implementation is completely missing. It is hence hard to fully buy the authors’ conclusions. Moreover, all the techical problems are left open for further work and research.

As research direction, I would start with implementing at least a complete prototype of their idea and evaluate more seriously whether this approach is good to further research. Indeed, from the paper is not clear at all whether a software based router has any chance to be at least as performing as a hardware based one. Even after all the simplifications that the authors took, their proposed solution can barely get to the same performance level of the hardware one. Moreover, to achieve that performance would require big changes in both the hardware and the operating system. That sounds a lot of work. The main question is still the same and is still open: are software routers worth it?

Can Software Routers Scale? April 30, 2009

Paper proposes the idea of software routers made from general purpose server platforms using cluster-based architectures for scalable and programmability. This approach has two main advantages: i. Software router’s upgrade is relatively cheap than the hardware routers. Ii. Use of commodity software further reduces the cost. One problem with the current routers is the fact that today’s software router are in the range of 1-3Gbps but carrier-grade routers are in the range of 40-90Gbps. Paper tries to revisit the question of increasing switching speed of software router by changing the “single server as router” approach to clustered software-router architecture that uses interconnect of servers to achieve greater scalability. Paper describes two type of cost: per packet processing cost and switching cost. Per packet cost directly depends upon the line rate while switching cost depends upon line rate as well as number of ports. Current carrier grade uses network processor and switch fabric for these tasks.

Paper proposes to build a N port router using N servers each supporting a line with rate R. These servers are connected to each other to switch packets from input to output. In this setup,

Each server is supporting a line rate of R hence per packet processing capability of each server should scale with R. Aggregate switching capability of the server must scale with NR.

Paper proposes a high level model to access the per-packet processing capability for a traditional shared bus architecture and point-to-point architecture. Paper shows that the bottleneck was memory chip and packet layout which was remedied by modifying the linux memory allocator. Paper further suggests the changes in the packet descriptor handling, Direct I/O, multi-processor mesh architecture.  Paper extrapolates based on other work and these validations that rates up to 10Gbps for shared bus servers and 40Gbps for mesh based servers can be achieved.

Another aspect of the problem is switching scaling, which occurs when input ports receive packets for the some output port at a rate that exceeds its capacity. High speed routers handle these situations using switch fabric configuration using a centralized scheduler. PC cannot scale up to the speed of schedulers paper proposes a interconnected switching network either scheduling is implicit in the routing through the network. Because OSes are general purpose they will not work in unison and per node connectivity is also limited to number of ports available. Link speed is also limited. Paper proposes to use load-based routing algorithm to achieve the switching scalability.

This paper does not adres the power usage, form factor and reliability aspects which is important in real deployment.

Can Software Routers Scale? April 30, 2009

The paper talks about the challenges involved in building scalable software routers and propose a solution of cluster-based router architecture that uses an interconnect of commodity server platforms to build software routers that are both incrementally scalable and programmable. The authors support the cause of software routers because of their flexibility in deploying new changes, the low cost of commodity PCs because of large-volume manufacturing, familiar programming environment and operating systems and widespread supply and support chains. The basic limitation of the current software routers is their ’single server as router’ approach which can never scale to hardware routers with high carrier speeds and thus, the need of clustered software-router architecture. The authors aim to build an N-port router using a cluster of service-class PCs where the challenges faced are per-packet processing capability of each server and the aggregate switching capability of the server cluster.

The authors predict the packet processing rates using a highly simplified model over a high-level view of PC architectures and then, experimentally measure the packet-processing rate achievable on a current PC platform. These analyses provided the upper and lower bounds respectively on the line-rate scaling and on whether their proposal is feasible. They chose shared-bus architecture and a multi-processor architecture as two architectures for their making predictions and performing experiments. They also computer lower bounds on the bandwidths of server scale processors and argue that small 64 byte packets limit bandwidth to 3.4Gbps. They suggest few ways to improve performance like improved packet descriptor handling, meshed processor technology and direct I/O. They also propose valiant load balanced architecture by using intermediate nodes for traffic rerouting.

Can Software Routers Scale? April 30, 2009

This is an interesting paper that focusses on a topic that few others have ventured into. Moin points are:

1. Primary reason for relatively little prior work in this area is the underlying demotivating assumption that it is impossible for software to ever match the line speeds that current routers and traffic patterns demand. While this premise is true, the paper proposes interesting ways to get around it by trying to place best- and worst-case performance bounds when a PC is deployed as a router.
2. The authors make a fine case that the specialized network processors of today have in fact turned out to be more of a stumbling block for new innovation in this space. The reason is that even adding a new module to a router requires changes in the hardware, which proves expensive. Unlike this scenario, a network world with software routers would enable deployment of new protocols and modules, just as today’s desktop and servers do.
3. Shedding light into the problem of scalability of switching. The paper systematically characterizes the bounds in terms of what a software based router is expected to achieve: 1) the per-packet processing capability of each server must scale with O(line rate) 2) the aggregate switching capability of the server cluster must scale with O(#(ports) * line rate)

Problems:

This paper marks the first step in considering the feasibility of using software-based routers as a subsitiute to the network processors of today. As an obvious consequence, there are many if’s and but’s at every step of reading through the paper. We know that Cisco and Juniper use specialized hardware for their routers, different from the regular PC. The first one that comes to mind is: if software-based routers were indeed possible, why is it that not one networking company in the industry has been pushing for it. Most likely reason for it concerns the scalability issue.

Future:

The paper makes a mention of the wide array of issues that need to be confronted in the future work, before this is deemed viable. For example, critical functionalities like multicast, quality of service and buffer management need to be researched upon extensively. Power usage, reliability, tolerance to software failures etc, accumulate enhanced importance in the context of a software-based router.

Can Software Routers Scale? April 30, 2009

Most important contributions

This paper is an overview paper on the scalability problem of software-based routers using commodity hardware. The authors point out that modern PC architectures are ready to act as general-purpose, software-based routers even at current and future line of 10 Gbits and 40 Gbits.

This scalability problem is explained to be twofold, one: the per-packet processing speed and second: the switching speed. The first problem is presented as needing changes in the core architecture of shared-bus architectures, the FSB seems to be limiting forwarding speed per packet. For the second problem, the paper only creates a space of possible solutions without going into details.

Most glaring problem

Most of the numbers presented in this papers are estimates and back-of-an-envelope calculations. I’d have liked to see a more general overview over different hardware architectures to consider for building future routing – the prevalence of the PC architecture seems a really narrow focus. Furthermore, this paper lacks any proof-of-concept for the switching solution.

Future work

Keeping all of the Green-IT initiatives and the fact that the most expensive part of using a data center is power consumption, I’d like to see how power consumption on dedicated switches fares against these general-purpose machines.

Can Software Routers Scale? April 30, 2009

Yes (with caveats).

This paper provides two models of differing accuracy in order to explore the possibility of implementing a carrier-grade router using only commodity computers and software routing. First, they use a back-of-the-envelope calculation based on theoretical bandwidths of processor front-side busses (FSBs), PCI-Express, and memory. This highly-optimistic model shows that using processors which should be available in the near future (mesh-network instead of FSB), a 40Gb/s line-speed router should be possible, which is at the low end of carrier-grade.

They then proceed to refine this model by performing calculations using an actual software router running Click on a commodity server. After correcting for a memory bug which hurt performance, they found that performance was only limited by FSB, which should be mitigated by future processor architectures.

After addressing a couple of possible enhancements to their naive software router approach (amortizing packet descriptors and allowing the processor to snoop DMA data directly into cache), they go on to discuss the switching problem. One area in which a commodity server will never be able to compete with purpose-built products is in the speed of the switching fabric. However, to solve this, they propose using a cluster of machines, which will increase aggregate bandwidth while providing load balancing.

A weakness of this paper is that it tends to rely a bit too heavily on future technology without providing much in the way of convincing benchmarks. Their Click benchmark seemed to jibe with their theoretical result, but that does not mean that it will scale with the advancement of commodity server technology. They mention in their closing remarks that they are working on creating a complete cluster using a switching mesh, and it would be nice to see the results from that study before drawing conclusions from this paper.

Future research needs to examine whether the mesh-based processors can really provide the bandwidth promised by their model or whether there will be another bottleneck which they did not account for. Also, if the packet descriptors cannot be modified at the NIC level, they need to find a way to account for that in order for their claims of 40+Gb/s to hold. Further, they need to decide whether the power consumption, reliability, and packaging constraints involved in a clustered system are worth the price gap between a cluster and a purpose-built part.

Can Software Routers Scale? April 30, 2009

(i) The three most important things the paper says:

1. This paper used simplifications of routing to be able to characterize and analyze it from a new perspective. In particular, they found that the first bottleneck they hit was indeed the memory system but not because of access times as everyone one assumes, but instead it was caused by a combination of packet layout and memory chip organization. After patching this, they discovered the next bottleneck was due to FSB saturation.

2. When analyzing whether real systems could reach those promised by their analysis using simplifications. They uncovered that the main difference between real results and their theoretical analysis was the added overhead of packet descriptors. The author gives a number suggestions of ways to fight this overhead. First by combining desciptors or getting hardware support for dealing with them.

3. The author then advocates for a cluster based mesh architecture. These meshes are no longer limited by the FSB since they use direct CPU links. The author claims, backed up in his other paper, that by simply switching networking to these architectures will offer 4x performance improvements without much trouble.

(ii) The most glaring problem with the paper:

This paper is very broad without focus or emphasis on the key discoveries of this paper are. The author tries to address and theorize on all aspects and limitations of router performance in an already short paper. The one saving factor is the author states that a more in depth analysis is done in a more in depth paper and this then only viewed as a summary is much more viable. In short the author must use words like we believe a lot indicating that which means you must decide to trust the author instead of being forced to by fact. The author doesn’t address the case when expansion makes a mesh of CPUs no longer a viable option.

(iii) The future research directions of the work:

This paper screams for more research to be done. The author repeatedly states that people need to test the theories put forth in this paper.  In particular, tests using the mesh based architecture and other design improvements brought forth are a must. The paper ends with the authors stating his current goal of building a 40 gbps router with the method he prescribed but the results therefore could not be put in this paper. Lastly future research should be done on ways to interconnect the computers using neither a FSB or mesh since a mesh has limited scalability. and what effects those architectures will have on performance.

Can Software Routers Scale? April 30, 2009

Three Important Things:

• Software routing was not taken seriously as an enterprise solution at the time when this paper was written. This was mainly due to the accepted notion that they do not scale well and that commodity hardware could not compete with specialized hardware routing solutions. A high level sanity check calculation challenges this notion, showing that a shared-bus architecture can scale up to 10Gbps with the bottleneck in the memory bus. A multi-processor mesh architecture could scale up to 40Gbps. The reason for this improvement is that the mesh approach replaces the FSB with multiple point-to-point links.
• In order to ground these calculations the authors implemented a shared bus architecture proof-of-concept system and ran several experiments. These experiments quantified the FSB bottleneck by showing that the address bus was 70% utilized, close to a known saturation point. Based on the results, the authors suggest several ideas for improvement that would allow scaling up to and beyond 10Gbps: batch handling of packet descriptors, Direct Cache Access implementation, mesh architectures.
• Another concern in software routing solutions is making sure that the internal switching scales appropriately as the load and number of ports increases. Deterministic internal switching is ruled out because it would require that the interconnect run at a higher speed than the incoming line. Instead a dynamic load balanced approach is proposed, referencing work done by Valiant et al. Randomly choosing packet routes introduces potential problems of packet reordering however the authors claim that these can be mitigated by enforcing deterministic ordering on short bursts of packets as these are at the highest risk for reordering.

Glaring Problem:
By the author’s own admission, the paper is intended as a light overview of software routing solutions. As such, it ignores many issues related to large scale deployment. Routing companies and their customer have a vested interest in hardware solutions that by their natures cannot be upgraded. Despite its numerous benefits, software routing would need to blow existing solutions out of the water in order to be adopted, and it is not clear that this is the case.

Future Work:
The suggestion of applying software solutions to routing architecture is largely unexplored, and the authors mention several avenues for future research. These would entail a rigorous analysis of  cluster configurations, power, cooling, as well as large scale prototyping.  In addition to these, I would add that a cost/throughput analysis is very important in order to justify the use of commodity machines. Also, software routing raises a bigger issue regarding the overall routing architecture of the internet. Another avenue for exploration could be how to scale our routers with hybrid hardware/software solutions.

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

Important Things:
1) Uses a simple model of commodity PC architecture to place an upper bound on its packet processing performance according to its specs, and uses experimentation to place a lower bound on packet processing performance for current server-class PC’s.
2) Begins exploring options for interconnecting a cluster of PC’s in a way that provides high routing throughput and is also scalable.
3) Introduces the idea of a mini-flow (a flow within some time window), suggesting that it may be a good balance between maintaining packet order and load balancing.

Problem:
As they point out in the beginning of the paper, power usage, form factor, and reliability not addressed. Additionally, they focus on acheiving high bandwidth, and there is no talk of latency. The cluster topologies they discuss involve routing packets through multiple PC’s, and the packet goes up and down the software stack at each node. If this approach is to be used in the core Internet routing infrastructure, then the additional latency will affect most Internet traffic, and will multiplied by the number of such cluster-based routers that are traversed. A flexible platorm for implementing routing protocols need not be purely software-based.

Future Work:
Certainly the PC architecture analysis will be important even in the context of end hosts with high-rate NICs, as rates scale to 40Gbps and 100Gbps. The topology question was not conclusively answered in this paper and should be investigated further. Also, I think the mini-flow idea for multi-path load balancing deserves further investigation.

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.

Can Software Routers Scale? April 30, 2009

1. Routers implemented in software running on servers, in spite of providing the flexibility, low cost and ease of programibility, weren’t popular since they didn’t scale and weren’t able to support line speeds. The paper proposes a method for implementing such a router, realized in software running on commodity servers. It achieves this by using multiple interconnected servers to form a cluster, each server handling one incoming line. It goes on to show that this cluster has the capability to support current line speeds and scale.

2. The paper also make a quantitative analysis of such a server, both in theory and by practical implementation. It does this for a server using a shared bus and one supported by a mesh of multi-processors. It identifies the major time consuming components and estimates the theoretically achievable, best case forwarding time for data packets. It then goes on to implement the proposed server and measures and compares the estimated times with the observed times. It identifies the communication buses to be the bottlenecks.

3. It looks into various topologies for inter-connecting the servers in the cluster. It identifies the issues, which include line-speed communication between the servers and in-order delivery of packets. It proposes a solution for in-order delivery of packets. It takes a look at the scalability of this cluster.

Oversight

The paper talks of providing as many servers as number of line. Though it talks of how this structure would scale as a function of O(sqrt(N)), it still might end up being quite formidable. Also, the paper does not consider packets requiring greater computation such control packets and the impact such packets would have on the processing times for data packets.

Future Work

The paper presents a new approach to implementing software based routers. It also proves theoretically that it is capable of supporting line speeds. The idea can be extended to incorporate servers more suited for the application. Attempt can be made to validate that the system works and supports all types of traffic, including data-control packets and is robust to external network changes. It internal scalability can also be verified.

Can Software Routers Scale? April 30, 2009

With the internet constantly evolving, it would be nice if old routers could keep in touch with the evolution. Using software routers can make changes easier to deploy. The problem with software routers is that it supposedly does not scale. This paper addresses whether or not the performance cap is fundamental or an architecture fault.
Major Points of Paper:
1.) Clustered software-router architecture
A big reason why today’s software routers cannot scale is because they adopt a “single server as router” architecture. This paper however sees the limitation in this architecture and has decided on using a clustered software-router architecture instead. Where a N port router can be built using a cluster of server-class PC’s. Each server handles one incoming line of the router and the N server are connected so that they can switch packets from input to output lines. To scale they need to show that for N ports with R bps line rates; lookups and classification must scale with O(R) and switching must be done in O(N*R). This clustered software-router architecture can take advantage of the newer hardware technologies like meshes.
2.) Back-of-the-envelope Analysis
The authors of this paper evaluate whether a architecture can scale as a software router by using back-of-the-envelope analysis and actually running experiments. The analysis looks at the architecture at a higher level view to see whether or not it can scale. This is more of a upper bound limit of whether or not line-rate scaling is possible. They check things like how many transactions on the memory bus , FSB and PCIe buses occur to see if it takes too long. From their work it seems as if a shared-bus architecture won’t be able to scale but with emerging server arhitectures the multi-process mesh architecture should be able to get 40Gps.
3.) Experimentations
Back-of-the-evelope analysis is nice to know whether or not something should work theoritically but a common problem is whether or not the implementations back up the theory. In their case, with large packets (1024 bytes) their server scales to 14.9 Gbps but for 64 bytes packets they get capped off at 3.4 Gbps. The bottleneck to the performance was found to be related to the memory system. To partially fix this they edited the linux memory allocator. Their experimentations lead them to discover many improvements that they can make to help scale.

Glaring Problem with Paper:
Using a cluster software-router architecture might help software routers scale better but is it enough? As advances in hardware allow for meshes that make a cluster architecture faster, can it keep up with the advances in network speeds? I think it is going to be very hard for it to if it is even possible. If it is possible, it seem like a lot of changes have to be made to acheive them.

Future Direction of the Work:
Using a clustered software-router architecture brings light into the software-router scaling problems. The authors are now building a 40Gbps prototype that should shed more light into whether or not software-routers can scale. There are bigger questions that have to do with configurations, footprint, power and cooling that the authors did not address but will be important if these software routers do ever scale.

Can Software Routers Scale? April 30, 2009

The authors provide theoretical and observational evidence that PC based software routing can achieve multi-Gbs routing speeds. The focus is on whether such routers can scale in terms of line and switching rates. They address the processing and bandwidth limitations in PC based architectures and where bottlenecks arise when forwarding packets at Gbs speeds.

The primary contributions are in identifying where the bottlenecks arise within a PC while doing packet forwarding and how a switching fabric can be constructed that preserves line rate.

For the first, the authors perform analysis of two internal PC topology models: traditional shared bus and point-to-point. They perform some coarse high level calculations to determine if the bandwidths on the PCIe bus, memory channels, and front side buses (FSBs) can support Gbs line rates. They consider this an upper bound. This bound is then tested using a real PC and multi Gbs network traffic generators. The result is that memory layout and access patterns are a bottleneck. If adjusted to suit the packet sizes, then the address bus on the FSB becomes the bottleneck. In these experiments they achieve roughly a 4.4 Gbs forwarding rate. They identify further packet descriptor handling adjustments to improve the bottleneck but do not implement them.

The second contribution comes in the area of switching. Because the line rate must be maintained throughout the entire process, the switching fabric has to support much higher processing rates. The solution they propose is to use a Valiant load balanced mesh architecture. In this architecture nodes are connected in a mesh and input on a node is forwarded to a random intermediate node before it is forwarded on to the destination. This helps alleviate the overload on any output node but introduces the prospect of packet reordering. They investigate several different switching networks based on this model (and variations of). The results show the maximum link and node capacities of each.

The paper does a good job of providing both theoretical analysis and emperical results. Unfortunately, I found their experiment setup to be too simplified. Their routing process uses static routes which considerably limits the amount of work needed to forward packets. This really makes the forwarding rates incomparable with real dedicated routers and works to undermine the applicability of their results.

I’d expect future research to focus on testing PCs using the customized memory and descriptor changes. Additionally, I’d like to see more reasonable “commodity” PC architectures considered. Multi-core point-to-point PC architectures are still not cheap commodity computers. Replacing low cost dedicated routers with a higher priced PC that can perform a the same level, may not be that surprising of a result.

Can Software Routers Scale? April 30, 2009

The paper examines whether software routers can scale to speeds achieved by network processors and what architecture optimizations may be required.

1. First, a high level model was used to predict an upper bound and bottleneck for current general purpose architectures. It is estimated that a shared FSB architecture can achieve speeds up to 10Gbps and point-to-point architecture can achieve speeds up to 40Gbps using current hardware.

2. Experiements were performed to validate the high level model and provide a more realistic lower bound using unoptimized off the shelf platforms. A server with 16 GigE cards was tested. With packet sizes of 1KB, the server forwarded at 14.9Gbps with a 16Gbps load. With packet sizes of 64 bytes the server can only forward at 3.4Gbps with a 16Gbps load.

3. The initial bottleneck was identified to be the way Linux allocated memory. After the Linux memory allocator was modified, the next bottleneck was discovered to be from the high FSB address bus utilization when sending small packets. This can be partly remedied by modifying the NIC firmware to integrate packets and their descriptors. Other improvements can come from Direct I/O from the NIC to CPU cache and using multi-processor mesh architectures.

The paper then explores switching architectures and topology. This can be a topic of future research to implement routers connected in a Valiant mesh. Additional research can also include optimizations to current hardware and software to achieve network processor speeds. There were no technical flaws in the paper.

Can Software Routers Scale? April 30, 2009

Implementing routing algorithms in software on commodity hardware is a very inexpensive and attractive proposition. The paper explores the upper and lower bounds on the throughput achieved by software routers when implemented on processor hardware available today through theory and experimentation. Commodity hardware has the advantages of low cost, widespread availability and understood programmability but implementing router framework on single server is limited by peak performance the server can deliver to compare with the raw line speed. So, the authors propose a server cluster based distributed router architecture to build a software router that compare in scalability to an N-port R bps ASIC router.

The authors compute the theoretical and practical limits to which today’s processors can scale when servicing a router traffic-like workload. They expect the memory system, the FSB and the I/O buses to limit the performance of the processors. They illustrate a theoretical upper bound on the processor throughput when using shared bus and mesh architectures. Forwarding a single packet in shared bus architecture would require 4 memory accesses for DMA-ing packet data into and out of the processor and to 2 FSB and PCIe accesses, this, the authors show would approximately result in an overall bandwidth of 10Gbps. As opposed to a shared bus architecture, a multi-processor mesh architecture would give a higher bandwidth (approx 40Gbps) since it does not incur the cost of an FSB and since each processor would have its dedicated memory subsystem.

Using experimentation the authors compute a lower bound on the bandwidth delivered by server scale processors. They observer that while substantial bandwidth is delivered for large packets, small 64-byte packets highly limit the bandwidth since these transactions incur an additional read/write of per packet descriptors thus leaving a practical bandwidth of only 3.4Gbps. To overcome such limitations the paper proposes using improved packet descriptor handling (more packets per descriptor), meshed processor topologies and direct cache access. Having established that servers can indeed be scaled to give router like performances, the paper proposes valiant load-balanced architecture where in intermediate nodes are used to load balance incoming traffic and subsequently route them onto output ports and an 8-port mesh topologies to substitute valiant algorithm because valiant ends up reordering the packets to achieve balanced loads. Both these approaches are seen a potentially competitive replacements to conventional hardware routers used today. Thus the authors push for server cluster based distributed software routers for extensibility, programmability and ease of use.

The paper creates the scope of an interesting niche in the router architecture space. It can lead to future research on the possibility of server nodes replacing ASIC routers and the required driver and network stack software to support such configurations. Also since the paper only serves in making a proposal, extensive research needs to be carried out on power usage, form factor, server node reliability and other deployment related considerations when using servers to replace routers.

Can Software Routers Scale? April 30, 2009

The paper proposes the idea of revisiting the feasibility of high-speed software routers that are also scalable with the rate of incoming traffic and the number of ports they support. The fact that costly hardware routers have already been deployed in the market has resulted in the inflexibility of considering the alternative of a software router. This paper shows that the general perception of software routers being unscalable and low bandwidth is not actually true. A basic limitation of today’s software routers comes from the fact that they adopt a “single server as router” architecture. Given the evolution of general purpose platforms, a single server architecture is unlikely to ever reach such high carrier speeds as conventional routers. But a clustered software-router architecture that uses an interconnect of multiple servers can achieve much greater scalability. Also with the emergence of mutlicores packets can be processed in parallel. Infact current processor architectures available in PCs can indeed support raw bandwidths of processing single data stream at 10Gbps. In such multiprocessor architectures, the memory bandwith of a bus based system really becomes the bottleneck. This can be further alleviated by using mesh interconnect model in which every processor has faster access to its portion of the shared memory.

The problem that further needed to be addressed is that of fast switching of packets between the different ports which are essentially individual servers in the cluster. Since the per-node connectivity in terms of number of interfaces on a typical server board is low, the interconnect complexity between the server nodes in a cluster has to sublinear for it to scale. Thus maintaining fast communication with low degree of connectivity is a major challenge. Finally the load between the nodes and their internal data links has to balanced dynamically for optimal performance.

The work mentioned in the paper has really opened the possibility of high speed software routers which are also much more flexible in terms of programmability and configurability. Future directions may include more comprehensive study and comparison between conventional and software routers both in terms of power and performance. The result of such study will shed light on the necessity of special purpose architectures for network centric workloads or alternatively on the architectural modifications needed to improve the packet processing capabilities of general purpose PCs.

Can Software Routers Scale? April 30, 2009

(i) The three most important things the paper says:

1. Software routers are becoming an increasingly attractive alternative to special-purpose hardware routers for a number of reasons: they are cheaper, more flexible, and are a more familiar programming environment for developers. However, a key obstacle for software routers is their (potential) inability to scale up to the speed required of a router in today’s Internet environment.
2. Experimental results seemed to indicate that the setup tested in the paper with front side buses could not scale beyond 10 Gbps. This was due to the overhead in reading and writing packet descriptors. The paper made a number of suggested improvements, but the likely most promising is switching the architecture from using front-side buses to a multi-processor mesh architecture.
3. Load-balanced routing is generally preferred over deterministic routing since it can more efficiently make use of the overall capacity of the interconnect. However, this choice leads to a few problems: packet reordering and constraints on fan-out for a large number of software router servers. Potential solutions including mini-flows (a burst of packets from the same flow are sent along the same path) and using different topologies.
   

(ii) The most glaring problem with the paper:

This paper proposes discusses two potential architectures (shared bus and multi-processor shared architecture), but indicates that the shared bus architecture will likely be bottlenecked by the memory bus at around 10 Gbps. They then show this with experimental results, leading them to say that a multi-processor shared architecture would have done much better. Unfortunately they have not yet verified these claims with a prototype of their architecture. So, it seems that in the absence of more than just theoretical (and optimistic) estimates (especially since their estimates for the shared bus architecture overlooked a limiting overhead), it is rather premature from the evidence the authors present to claim that they have found a solution for scalable software routers.

(iii) The future research directions of the work:

It seems the paper presents a novel direction in which research on software routers may head. A lot more work should probably be done to verify not only the scalability of the architecture, but other necessary properties such as reliability, security etc. I am also curious about the price scaling of software versus hardware routers (for example, a 10-port hardware router may be more expensive than a 10-server setup of a software router, but would that be the case still with more ports — say 100,000? In other words, is incremental cost of adding a port in a hardware router more than that of adding a server (and the additional links necessary to connect it to the existing topology). If not, then one of the advantages of having a software router might be lost).

Can Software Routers Scale? April 30, 2009

(i) The three most important things the paper says:

1) The current school of research that assumes that software routers adopt a “single server as a router” will never be feasible. Instead the idea of a “clustered software router” solution shows more promise. The rest of the paper then discuss how this can be achieved with specific algorithms and conventional PC architecture.

2) Pin pointing the bottleneck of current conventional PCs that limit the performance at the FSB. Since they are arguing for the use of conventional PCs, this point immediately allows follow up research into how to solve this problem and make an improvement in the performance. Furthermore, they even propose non-radical software and hardware already in this paper.

3) Observation that a conventional PC cannot hope to scale a PC to the speed of a centralized scheduler. Although this may be seemingly trivial, it is actual very thought provoking, since it incites research to look for alternatives instead of doing the same thing as a centralized scheduler. Later in the paper, they even mention specific possibilities, such as interconnecting PCs to form a switching or sorting network.

(ii) The most glaring problem with the paper:

Although a lot of analysis was put into comparing different switching solutions, the paper would have benefited with some actual experimentation. Without experimentation, there may be unforeseen issues that they missed when comparing with pure calculations.

(iii) The future research directions of the work:

A good area for future research is to consider how conventional PCs can be used to beat dedicated hw routers. Since, even if the ideas proposed in this paper are successful and they manage to match speeds of dedicated HW, it may not be enough incentive for users to change. Because changes cost money, and users would only change if there was a compelling reason such as speed improvement or cost reduction.

Can Software Routers Scale? April 30, 2009

i)

1. In order to achieve the high performance required of a software router, there must be a very high attention to detail to eek out the most out of the hardware. For instance the authors initially thought memory was their bottleneck, but upon futher investiagtion they discovered that by cleverly laying out the packets in memory they were able to improve performance by 30%

2. In order to scale to speeds like 40 Gbps advances in hardware design such as direct cache access (DCA) or multi-processor mesh architectures will have to make their way into commercially available hardware.

3. In order to achieve a high throughput packet switching network it is important to be able to balance load. They propose using a load balancing algorithm such as the Valiant routing algorithm

ii) I think one flaw of the paper is not addressing the feasibility of removing RAM from the picture and simply using the on-chip L1, L2 and in some cases L3 caches. The caches are getting so large now it might be feasible to assess the possibility of simply having the processors pull the data directly into their caches and bypass main memory.

iii) This paper examined the feasibility of building a 10 Gbps or 40 Gbps software router based on comodity hardware. The next step would obviously be to go try and actually build one.

Can Software Routers Scale April 30, 2009

The purpose of this article was to look into whether or not it would be possible for software routers to scale to performance levels equal to and even beyond what todays specialized routers are capable of through the use of routing clusters. A fully programmable router network would solve many of todays issues regarding upgradability, security, etc. and could fundamentally impact the way the internet works. The key points in this article were:

1.It appears that through increased cache size and highly accurate lookup table algorithms, it may be possible for PC hardware to scale to the needed speeds of packet processing. The authors are not conclusive on this issue as they did not place it through a full battery of tests. However, the tests that they conducted suggested that the packet processing would not be a bottleneck.

2.Several hardware improvements such as Direct I/O and multi-processor mesh server architectures, some of which are already available, should significantly improve performance by removing the current bottlenecks in a software router. The removal of these bottlenecks is very difficult for a general purpose PC but very likely can be implemented for one specifically configured to be a router.

3.It is becoming increasingly common to place several computers into a cluster in order to improve performance without improving hardware. It could be very possible to do this with software routers in order to cheaply improve the performance to acceptable levels

The biggest issue that I was with this paper was the lack of specifics involving improvements that could be made and the relatively few number of measurements made to test their theory. While this paper was obviously designed to inspire new research without being too long. I think that a page or two more of analysis would have benefited future research greatly in providing some more direction.

The future research of this paper is going on right now. Research into clustering routers, adding more functionality and extensibility, and virtualization of routers are all topics being actively researched in order to improve the capabilities of the internet. What is most interesting to me is the use of inexpensive clusters as a way to improve performance as I would like to see some programmability introduced to the routing structure as a way to improve the internet at large.

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

This paper is primarily concerned with detailing advancements to software-based routers, as it was written at a time in which there were cheap routers that were relatively dumb compared to todays standards, and expensive PC based routers that handles resource intensive tasks such as firewall, port forwarding and the like. The primary points of this paper were:

1. The development of a hierarchical scheme in which some operations were performed at the lowest level in order to maximize throughput, some were passed up to the specialized network board that could handle moderate sized operations with good speed, and finally, the most intensive tasks were passed up to the general purpose CPU in order to perform those operations as quickly as possible. This took advantage of the strengths of each stage and ensured that the router was operating as quickly as possible.

2. The authors of this paper made extensibility one of their primary design considerations, a view that was a wise choice in retrospect. They recognized that the proliferations of services that inspired them to build this router would likely continue increase and that their design would need to be able to implement them cheaply and easily in order to stay competitive. Their design is somewhat modular in that the forwarding and scheduling mechanism of the different layers is somewhat removed from the modular services that they can incorporate. This would make it easier to add a service and then change the forwarding algorithm slightly so that it would recognize where to send the packets.

3. The forwarding mechanism mentioned above is also static, allowing for an extremely robust system, even under an extremely heavy load. By decoupling the services and the forwarding mechanisms, the authors were able to optimize each component to its specific strength. The three design considerations: performance, extensibility, and robustness were well thought out and addressed for each component.

The primary weakness of this paper that I saw was that they did not try to implement any of the services that were much less common at the time, but rather stuck with the basic ones common to many routers. While they did show that they could do it better, being able to demonstrate increased functionality would have improved this already excellent paper and added something that was missing. The other thing that I thought would have improved the paper would have been a simple graph detailing performance compared to other common router configurations.

Future research in this area has been ongoing as routers have been forced to do more and more over the years. The authors mentioned moving a lot of this functionality to FPGA’s which I see as something that might merit a considerable amount of research. Also, improving upon th system and even adding more layers or duplicates of each layer might significantly improve performance. These were all mentioned by the authors but I also believe that these are the most likely paths for future research.

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

With the internet quickly evolving into a vast global network owned by several administrative authorities, the implementation and maintenance of various routing policies have become increasingly complex. The paper describes the various goals that the operators of ISPs have and their resulting routing policies. Most of the modifications to BGP protocols have been made using decision process to chose routes. The result is a protocol where most of the complexity is in the decision process and the policies used to influence decision is fairly simple. The policies can be broadly categorized into business relationship, traffic engineering and scalability. In the 1^st category, ISPs may want to prefer customer learned routes over routes learned from peers because sending traffic through customers generates revenue while sending traffic through providers costs money. The ISP can achieve this by assigning a non overlapping range of LocalPref values to each type of peering relationship. ISPs can also control route export to neighboring ISPs by tagging advertisements with a community attribute signifying the business relationship of the session, and filtering routes with certain community attributes when exporting to peers. In the case of traffic engineering, Operators can influence outbound traffic flow either by configuring import policies that affect which routes get in the set of equally-good border routers or by modifying the IGP link costs. One common goal is early-exit routing where ISPs forward traffic to the closest possible exit point hence avoiding congestion in its internal network. Load balancing can also be done by LocalPref to the outgoing links. Finally a properly configured set of BGP policies can improve the scalability of a network and its resilience to instability. For example one of the goals of an ISP is to protect itself from invalid route advertisements from an adversarial ISP which may lead to memory overflow and crashing of routers. This can be done by ignoring advertisements from peers with address spaces they don’t own and also by performing some sanity checks on the paths.

With the increasing complexity of policies, routers nowadays are much more weighted down with such policy enforcements which can make it subject to a variety of problems including misconfiguration, oscillations, and protocol divergence. The complexity of Internet routing makes it difficult to predict the way policies interact thus increasing the prevalence of configuration mistakes. Interdependencies of policy across ISPs can also trigger problems like persistent route oscillations.

The future directions of the work can include configuration checking tools that can avoid misconfigurations by verifying certain consistency criteria hold while modeling tools can predict side effects of configuration changes on routers within an ISP. Works can also attempt to coordinate route policies across ISPs without revealing private details of policies. Another important direction is to come up with some Routing Policy Specification Language (RPSL) which is vendor-neutral language for describing ISP policies. This will enable router configurations with higher level constructs that allow diverse policies while precluding certain misconfigurations. Finally new architectures like HLP can be explored which propose to expose the common policies that can be typically inferred in BGP today and optimize the routing protocol based on the resulting structure, with the aim to improve scalability and convergence of interdomain routes.

BGP Routing policies in ISP networks April 28, 2009

1. The paper provides a comprehensive overview of the BGP protocol used to achieve routing between ASs. It makes note of the major factors that influence inter-AS routing that aren’t an issue in intra-AS routing such as conflicting policies between different ASs, commercial aspects that define traffic between ASs, routing through intermediate ASs, etc. It talks of how BGP functions within an AS to allow its nodes to communicate with nodes in other ASs and also how packets that need to travel through multiple ASs before the reach their destination AS need to be handled. It makes note of the policies and the priorities of the policies that are used to determine routes in inter-AS communication.

2. It looks into the problem of a given AS wishing to influence the routing decisions of adjacent ASs when it has no direct control over the policies of its adjacent ASs. It talks of how an AS can make one route more preferable that another by suitably setting the MED attribute of the routers in the respective routes. It also talks of scenarios when it might be possible for an AS to remotely control the routing policies of a router in an adjacent AS.

3. It talks of how the overhead traffic generated due to the book-keeping involved in inter-AS routing can be reduced. Route-aggregation as a method to reduce the amount of information that needs to be communicated with a neighbouring AS when new nodes are added within an AS. An AS can configure its routers to advertise a single, less specific prefix to it’s neighbouring AS instead of advertizing two adjacent prefixes. Ignoring routes that change too frequently is another method of reducing the excessive traffic generated due to unstable routes.

Oversights:

The paper provides a concise overview of various aspects of BGP, ranging from the policies used in deciding routes to factors influencing these policies and how these policies can be used to control traffic between ASs. The topic is vast and there is no end to additional insights that can be given. It paper could have gone on and given a more in depth analysis of the BGP protocol and how it functions when the communicating ASs are not adjacent to each other or it could have looked into the short comings of BGP which include oscillations when routes change and how these shortcomings can be handled etc. However, there is no end to the detail that can be provided.

Future Work:

Some of the solutions provided by BGP are not the most efficient. For example the methods used by BGP to handel routes that go down or need to be taken down for maintence take up a lot of time and traffic before they reach a steady states. The various short commings of BGP can be looked into and methods can be suggested that circumvent the problem or provide more efficient solutions.

BGP Routing Policies in ISP Networks April 28, 2009

(i) The three most important things the paper says:

 

1) Routing policies is not a simple “shortest path” problem as the Internet grew.  It is now based on a myriad of factors, including but not exclusively economic, political, security and operational.  The paper effectively expands on the reasoning behind each one of these points.

 

2) It is difficult, if not impossible to ask every ISP to support a new routing design.  Therefore, the community of ISPs have opted to modify the “decision process” of routers instead.  That is why it is important to understand the “decision process” and not just simply change the protocol to support the limitations of the current system.

 

3) There is a delicate balance that each ISP has to play with neighboring AS. On one hand they need to depend on its neighbors routing information to make the best choice, but they also need to doubt everything that is provided.  This issue of trusting your neighbor really is root of BGP’s security, economic, and political concerns.

 

(ii) The most glaring problem with the paper:

 

This paper provides a lot of details of what settings to change and how it effects the decision process by the router.  However it never provides an overall perspective of how changing these settings work together.  For example, LocalPrefs is changed to support “business relationships”  and also changed to manage traffic.  The paper never addresses how this one setting can be configured in a way to satisfy the requirements from two directions.

 

(iii) The future research directions of the work:

 

It is obvious that with all the limitations of the current BGP framework, a new system is needed.  Perhaps instead of just simply working on a new protocol like HLP, some research should be done into how to propagated this new protocol.  And to go even further, how would an upgrade potentially disturb the QOS of the Internet as a whole.

 

BGP Routing Policies in ISP Networks April 28, 2009

i)

1. How packets are routed today on the internet is primarily a factor of different ISPs routing policies based on business concerns. I didn’t know business concerns effected packet routing to such an extent.

2.ISPs must balance the flow of traffic to/from their peers, customers, and bigger ISPs in order to maximize their profit. For instance an ISP might balance outgoing load across multiple exit points even if they are not the most ideal in order to not use a particular peer too much.

3. BGP can be used as a security mechanism to “blockhole” routes from spammers or Denial of Service attacks.

ii) I think the most glaring error of this paper was not giving an idea of how prevelent the different policies are and how the effect latency in the internet

iii) A future research direction would be to determine how these routing policies effect latency in the internet. It would be interesting to see if an overlay network could be build that dynamically monitored latency to other nodes in the network to build a routing network based on minimizing latency.

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.

BGP Routing Policies in ISP Networks April 28, 2009

(i) The three most important things the paper says:

1. BGP was introduced to allow ISPs to have greater control over route selection and propagation. It is an incremental, path-vector protocol. ISPs send updates for each prefix and updates to several fields may be advertised at once. Route selection is based on path length by default (when no policy exists), and via the BGP decision process in the presence of policy attributes. Using these advertised attributes (or purposely ignoring some of them), ISPs have the ability to choose particular routes, filter out certain routes, or add additional state to routes by tagging them with a community attribute.
2. The paper presents four distinct design patterns that are commonly used by ISPs to direct policy:
   • Business Relationships: ISPs generally have three types of business relationships — customer-provider, peer-peer and backup. The customer-provider relationship is the most desirable since this is how an ISP generates revenue. Furthermore, the ISP wants to suppress routes where traffic is forwarded from one provider/peer to another. These properties are achieved with attributes and tagging.
   • Traffic engineering: ISPs often want to be able to guide traffic to ensure optimal performance or guarantee some class of traffic quality/availability. ISPs use a number of techniques, such as hot-potato routing (so packets stay in the network for as short a time as possible) and load balancing.
   • Scalability: ISPs want to ensure that excessive updates are suppressed so that service quality and availability are not affected. This is achieved by capping the size of the routing table or suppressing unstable routes. ISPs try to send and receive a limited number of advertisements by using longer prefxes, imposing prefix caps and aggregating adjacent prefixes as needed.
   • Secuity: false information, either generated erroneously or injected maliciously, can be detrimental to performance. Some techniques used include sanity checks to eliminate invalid routes, overwriting unexpected attributes, filtering undesirable advertisements and putting limits on number of prefixes and session timeout.
3. There is a dense field of many policies which require support in BGP. This complexity leads to a variety of problems (such as misconfiguration, oscillations and protocol divergence) which could lead to degraded performance. Open research topics in the field include configuration checking (verifying that policies are consistent with each other), language design (creating a language that can be used to easily describe policy) and new architecture (which aims to simplify and extend BGP).

(ii) The most glaring problem with the paper:

A type of AS relationship not mentioned in the paper and which may have interesting implications for BGP policy is the sibling-to-sibling relationship. Siblings may be willing to share routes, which would not be done for providers or peers. Furthermore, there is no money gained or lost through routing traffic to a sibling, which may influence the decision process (we may choose a sibling over a provider but choose a customer over a sibling for instance).

(iii) The future research directions of the work:

The paper names some of the research directions that are currently being investigated (configuration checking, language design and new architectures). One thing about the BGP policies that concerns me is the fact that the policies of two or more ISPs may end up “butting heads”, perhaps unwittingly, and the ISPs’ performance might suffer as a consequence. It may be interesting to look into whether it was possible for a global or regional (i.e. on some subset of ISPs) tool could be devised to inform ISPs of the tradeoffs of their policies and to suggest possible modifications that would increase performance.

BGP Routing Policies in ISP Networks April 28, 2009

This paper just explains how BGP works on the internet. The point of the paper is the explain how BGP came to be and to describe patterns that ISPs use for policies to help understand what would be required to fix BGP or improve it.
Major Points of Paper:
1.) Scalability
Since bad information can be easily passed around ASs, BGP needs to be able to stop bad information from generating excessive updates that can trigger route instability. BGP uses filtering of long prefixes and community attributes to limit the routing table sizes. It also uses route aggregation to limit its advertisments to other ISPs. Lastly BGP uses flap damping to assign penalties that are incremented for any route that an update is received.
2.) Security
There are many different security goals ISP may have. The first is to stop their customers from learning bad routes. To do this the ISP checks  to make sure that updates are valid before sending them out. Other security problems include, stopping neighboring AS’s from influencing their routing decisions, stopping external routers from accessing certain information in the AS and DOS attacks. To deal with these an ISP can use import policies to delete or overwrite attributes,  filter bad AS advertisements and only accept a maximum number of prefixes before tearing down the session.
3.) Configuration
ISP’s have to deal with many different policies that can handle their business relationships and traffic. By using LocalPrefs and community attributes, ISP’s are able to control which routes their border router uses. They can make so that they send their packets to a neighboring AS A, but A cannot send its packets to this AS. This situation usually occurs when this AS pays A to send its packets it way. Traffic can be control by load balancing the traffic through many AS’s even if it is not the shortest route.

Glaring Problem:
BGP is a very complex protocol because of its general ability to apply policies. The problem with this is if bad information is given it require the AS’s  to be very smart to prevent bad information from messing up the routes the AS uses. It can be done but like earlier stated it is very complex and always changing.

Future Work:
With the patterns of BGP exposed, there will be more work on automating tools that support the BGP patterns that are mention in the paper. This paper also address more work on automated configuration checking, a policy language and new architectures.

The Case for Separating Routing from Routers April 27, 2009

The paper proposes the idea of introducing a Routing Control Protocol (RCP) that is intended to separate the routing information computation overhead from the actual routers, thus leaving them with only the responsibility of forwarding packets by lookups that can be done in efficient way. The complexity of the internet is inherent due to the limitations of today’s distributed infrastructure to scalably cope with the new requirements. Thus the RCP should select the routes on behalf of the routers by gathering the route information from them. The information across various routers is infact not replicated but decomposed. Thus each node does not have a complete consistent view of the entire network. Also distributed path selection causes routing decisions at one router to depend on the configuration of another. Computing routes on a networkwide basis using a consistent view of routing state can reduce interdomain routing’s dependencies on these subtle details. Also dividing functionality into distinct modules with clear interfaces helps control complexity. For example inconsistencies between iBGP and IGP routers can cause forwarding loops and routing oscillations. Hence instead of being ignorant about the IGP forwarding paths the routing can use the available knowledge to explicitly enforce consistency in the router level forwarding paths. Finally small changes in the IGP topology can trigger unnecessary shifts in the BGP routes. By controlling the path selection for each router, RCP can force routers to continue using an egress point (border gateway of AS) even when link failure or small IGP costs change make one egress point slightly closer than another. Thus the routing decisions can be implemented by RCP as a single logically centralized entity in each domain. This centralized logic must be actually implemented in a physically distributed fashion to avoid a single point of failure.

Such separation of route states from routers can potentially introduce robustness, scalability, speed and consistency problems: the challenges that RCP must be able to handle. RCP can become a single point of failure since it serves as a single repository for route information. For these RCP should be distributes across several RCP servers (RCS) which must maintain a consistent view of the available routes to ensure that all routers receive consistent and loop-free paths. Hence the types of inconsistencies that can result from various combinations of partitioning of the ASs has to be studied and taken care of. Also RCP must be able to handle thousands of BGB sessions each with thousands of routes. Such huge memory and computation intensive jobs must be distributed across many physical machines which is difficult and complex. RCPs must also compute the route information and propagate the results in a timely fashion as BGP and IGP topologies change. Hence the convergence speed of such routes should not be worse than in today’s routing architecture. Finally transient inconsistencies may occur if the routers donot receive updates from RCP in a certain order. Such inconsistencies can cause loop formation which are as worse as those occurring in current BGP convergence and hence needs serious attention.

Future directions of the work may include simplification of the underlying routing mechanisms which can in turn simplify configuration languages. For example configuring routing policy using RCP will obviate the need for implementing high level tasks with communities and complex import and export policies on individual routers. Locating configuration state at RCP should make it easier for the operators to specify high level tasks leaving the implementation details to the RCP. The RCP should also impose various invariant conditions on the network configuration to guarantee correctness. Defining those invariants should be an area for future work. Also being a repository of routing states it can help the operators debug routing and performance problems. Finally RCP can improve routing efficiency by aggregating prefixes for a particular routers forwarding table if it can determine that the router will make the same forwarding decision for all of the specific routes. Efficient aggregation of such contiguous prefixes is also left as an open question.

Towards an Evolvable Internet Architecture April 27, 2009

The paper describes the framework of changes that need to be done to contribute towards the evolution of the Internet. The most basic change as described by the authors is to make suitable changes in the IP layer. One naïve solution could be to augment the existing Internet with multiple overlay networks implementing newer architectures. But this as the authors caution would lead to revolution as against evolution since every individual ISP would come up its own augmented IP architecture. The idea behind any evolving change in the Internet should still be to provide Universal access and the authors provide the mechanisms for the universal deployment of an IPvN network given an existing starting point IPv(N-1) network.

Universal access could be implemented by IP multicast wherein each content provider would interface with an IPvN ISP and enable users to access IPvN networks through multicast. But this proposal has a problem of partial deployment of services by the content providers as it requires migration of their applications to support IP multicast. Another strategy for deploying IPvN could be redirection either at the application-level or at the network-level. Application level redirection would involve looking up a service to identify the ISP domains/routers supporting IPvN and the clients could then tunnel their packets through. Lookup service implementation could either by done by the ISPs or third party brokers, but the authors suggest that either form of lookup is infeasible. The first form would require manual lookup/hash-table configuration at the ISP and the second the form would require change in the market structure (i.e. introducing thridy party brokers). Given these limitations of lookup/application-level redirection based IPvN deployment, the authors then put forth the idea of network-level redirection and build a framework around it. They give three mechanisms, namely, anycast, vN-bone construction and packet forwarding in the IP layer to support IPvN.

Network-level redirection means a mechanism in which a network router automatically redirects packets to an IPvN router, but clients should be able to initially connect to non-IPvN offering ISPs and still access IPvN capabilities. This enablement is achieved by the three mechanisms described above. In anycast, a packet is routed to nearest best possible server providing IPvN and thence the IPvN packet is encapsulated in IPv(N-1). This simple anycast strategy allows seamless spread of deployment and reuses existing unicast IP routing infrastructure. But a potential problem of IP anycast is that it is limited to certain individual domains and hence requires the development of a concrete routing scheme. Anycast could be categorized as intra-domain (within the network of IPvN supports) and inter-domain (within a hybrid network of IPv(N-1) and IPvN routers). For instance, in a link-state anycast strategy, intra-domain routing can be accomplished by associating a high-cost ‘advertisement’ with the anycast router. While intra-domain anycast is accomplished relatively simply, inter domain anycast would require global routes with non-aggregatable addresses or aggregatable addresses default routes. The first case would require the designation of a portion of unicast address to anycast and make requires policy changes (not mechanism changes) in BGP support these addresses and has a problem of all ISPs having to support anycast propagation. The second case of aggregatable addres with default routes would require anycast addresses to be allocated from the unicast address space of the first ISP to initiate deployment of IPvN and IPvN routers to be configured to advertise the anycast address in their IGP. Additional ISPs that adopt IPvN also then need to configure their IPvN routers to advertise the same anycast address internally. The paper then describes the formation of a virtual network bone or vN-bone for cooperation between the ‘existing’ IPvN routers built by various ISPs to cooperate and forward the packet. This would require vN-bone spanning multiple ISPs to be built as an overlay over IPv(N-1). Similar to anycast, routing with vn-bone is divided by the authors into intra-domain and inter-domain. Intra-domain vN-bone would simply involve each IPvN router to pick out the k closest routers running IPvN. Whereas, intern-domain vN-bone routing requires the ISPs to setup intern-domain tunnels based on peering policies with other ISPs. Once a vN-bone is successfully established, routing between endhosts then boils down to the problem of routing between ingress and egress vn-bone routers.

Lastly the papers discusses packet forwarding which can be accomplished by leveraging the anycast and vN-bone infrastructure described above. To start with the source encapsulates the IPvN packet in an IPv(N-1) header with destination A(n-1). Then using anycast, the packet is forwarded over legacy IPv(N-1) routers to the closest IPvN router. The IPvN router then strips off the IPv(N-1) header, processes the packet as needed, looks up the next hop to the destination using the vN-Bone forwarding tables, and forwards the packet to the next IPvN router and so on. This is repeated until the packet reaches the egress IPvN router which tunnels the packet through to the destination.

The paper concludes by providing another broad alternative to the above strategies in the form of SSM or source specific multicast which again can function even with partial cooperation among ISPs. The authors reiterate the need for the evolution of internet to support exponentially multiplying endhosts by the day. They propose the strategies above to which can they claim can be seamlessly integrated in the IP framework of today and claim that these changes will encourage the ISPs for immediate adoption and benefit end-users. Although the claims of the authors are relevant and thought provoking, a possible problem is the non-explanation of economics that would encourage the ISPs of today to adopt these IP augmentation policies. The commercial viability of creating anycast and vN-bones need to be practically explored, probably by experimentation, to attract the ISPs to supporting such IP architectures. Finally security concerns and attack vulnerability of such hybrid IPvN/IPv(N-1) architectures need to be thoroughly considered and dealt with and they are made no stab at in the paper.

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.

BGP Routing Policies in ISP Networks April 27, 2009

This paper was primarily concerned with detailing BGP, or border gateway protocol, used by ISPs to influence the paths on which packets of different types are routed. It does not propose the actual idea, as it was well-established by the time that this paper was written but attempts to clearly describe BGP, the methods by which it influences routes, and the motivations for the different procedures implemented by the ISPs. The three major points that I took away from this paper were:
1. BGP policies can generally be broken down as being implemented for 1 of 4 general reasons: business relationships, traffic engineering, scalability, and security. These 4 considerations greatly impact how the policies are implemented as they require very different approaches and have very different goals in their design.
2. BGP can be extremely complex and the issue is further complicated because each implementer can do basically whatever they want without any kind of internet wide standard to worry about. This lack of standardization among the ISPs can lead to problems and degradation of customer service, scalability, and security if one of the ISPs decides to not play well with others.
3. BGP is something that has become necessary as the size of the number of nodes on the internet increased beyond what anyone had ever predicted. Intelligent control of packets within a group of nodes like an ISP provides valuable functionality and improved performance when implemented correctly. There are a number of things that can be done to improve the performance of the internet as a while using BGP or a similar protocol.
This biggest issue that I saw with this paper was the lack of discussion regarding the possible improvements to the system. However, this was an informational paper so that is to be expected. Slightly more discussion of what extensions could be useful or what standards have become commonplace (so as to be required implementation) would have added to the overall value of the paper.
Future research in this field is fairly obvious as it concerns making BGP more efficient, standardized and even extend it to provide more functionality. I feel that this final piece will become a fact due to increased security awareness and concerns. Improved security over the router system will add another layer of protection to every user and greatly complicate attackers jobs.

Realistic and Responsive Network Traffic Generation April 25, 2009

(i) The three most important things the paper says:

1. The authors present a new traffic generator named Swing. The generator uses a trace measured at a single point in the network and automatically finds distributions for user, application, and network behavior. It also captures burstiness in ackets and individual bytes as they are flung across it.

2. Swing then has the capabilities to randomly recreate these conditions. This means you can take a sample of the network you will be deploying an application on, then you simulate network performance of your application or network hardware. It is important for the generated trace to be random and not just recreate the trace exactly so unexpected behavior is encountered and you can gain confidence in you system under various conditions.

3. Swing then goes one step further to let you change parameters to extrapolate network conditions. You are able to increase traffic, the prevalence of a certain protocol, or burstiness of your desired conditions.  This allows the user to test his machine in conditions that aren’t readily available even if he were to deploy his system.

(ii) The most glaring problem with the paper:

This paper did not have as glaring problems as the others I have read this far. That being said, something that bothered me is the authors mentions that having a session generator offered better response towards matching network conditions but a lot of randomness was lost. I would think they would have said that this could be something worth pursuing or looking for ways to get around this problem in the future.

(iii) The future research directions of the work:

A feature desired by the authors but not yet deployed is the ability to instead of taking averages and deviation of network data, it would be nice to be able to capture that something, say bandwidth is steadily increasing throughout the trace. A possibility that I find intriguing, not mentioned by the author, would be using multiple traces taken at the same spot that represent different conditions that occur at the location as the seed to the generator. The author lists many other of his own future directions in the future work section.

TCP Congestion Control with a Misbehaving Receiver April 25, 2009

(i) Three most important things

1. TCP was designed for a cooperative environment which as a result contains several vulnerabilities that the receiver can exploit to obtain improved service at the expense of others on the network or to implement a denial-of-service attack. End-to-end congestion control mechanisms were implemented for sharing scarce bandwidth between users on the Internet but require both endpoints to cooperate in determining a proper rate at which to send data. However, a misbehaving receiver may send more data quickly than the cooperating host, possibly forcing competing traffic to be delayed or discarded.

2. There are three different approaches the receiver can take to exploit the vulnerabilities of TCP that allow the receiver to enhance performance. Because of the incongruence between byte granularity error control and segment granularity congestion control, the receiver can divide the ACK for a segment received into multiple ACKs so that the TCP sender will grow the congestion window at a faster rate than usual. The receiver can also send duplicate ACKs which tells the sender that segments are leaving the network so the congestion window inflates in order to reflect the additional segments that have left the network. Lastly, the receiver can send ACKs before the data has actually reached the receiver so that the sender will think the round trip time was short and send segments faster.

3. The design of TCP can be modified so that the receiver cannot exploit the vulnerabilities of TCP that allow the receiver to improve service at the expense of other clients on the network, without requiring that the receiver be trusted in any manner. One of the solutions described was the Cumulative Nonce, which requires that the sender sends a unique random number with each segment and the receiver either echoes the current nonce sum (the cumulative sum of all in-sequence acknowledged nonces) or the nonce value sent by the sender, for each ACK in response to a data segment.

(ii) Most glaring problem

The most glaring problem would be that the nonce solution to the majority of the possible misbehaving receiver attacks requires the modification of clients and servers and an addition of a TCP field. This would not be solution that would likely get implemented because the solution requires a whole makeover to TCP that would take a lot of time and effort.

(iii) Future Research Directions

Future research directions for this work would be to see how this research could be extended to other protocols. The Cumulative Nonce could be adapted to any sender-based congestion control scheme which could prove to be more conducive for unreliable transports because it effectively defines a sequencing mechanism between untrusted parties.

Timing Analysis of Keystrokes and Timing Attacks on SSH April 25, 2009

This paper investigates using timing analysis of packets sent during an SSH session to try and recover users passwords. The paper notes there are two main weaknesses in SSH that can be used as a vector for an attack

1) Packets are padded only to an eight-byte boundary if a block cipher is used

2) In interactive mode, every individual keystroke a user types is sent in a packet right when it is pressed.

The authors proposed using the time between keystrokes to help determine what the password might be. They note that users tend to type their password very quickly without much thought since they type them so often and also that users tend to type out their passwords in groups of 3-4 characters with a small pause before typing the next group of characters.

The approach they used is break down a password into a series of keystroke pairs, so for instance a password of length n would have n-1 keystroke pairs. Next, they conducted studies where they brought in people and had them practice typing the same randomly selected keystroke pair like (e,v) 40 times and then recorded the time between keystrokes. They did this for 142 keystroke pairs and then identified 5 major classes of keystroke combination that had similar time spacings for pairs that fell within that class.

1) Two letters typed with different hands

2) A number and a letter typed with different hands

3) Two letters typed with the same hand, but different fingers

4) Two letters typed with the same finger

5) A letter and a number typed with the same hand

They then used this information to develop hidden Markov model. When given a sequence of timings between keystrokes based on observing the spacing between packets sent from one host to another they then used the n-Viterbi algorithm to select the top n most likely sequence of keystrokes for the password based on the hidden Markov model and the observed timings between keystrokes. They could then attempt to break the password by trying each password that the model indicated was a likely candidate for the password. Overall the results indicated that using this method, only 1/50th login attempts had to be made in comparison with a brute force approach.

The most glaring problem is the authors only conducted the study for users using randomly generated passwords instead of passwords they people might actually use. Some arguments were made about why the approach would likely work for normal passwords, but it wouldn’t have been much trouble for them to actually try it out on a couple human selected passwords. The future research direction would be to see how this attack translates to normal user selected passwords.

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

1. The transition from distance vector to path vector routing algorithms increases the number of routing path oscillations, which can last up to fifteen minutes.
2. Much of the path restoration delay is a result of non-standardized implementation decisions on the part of BGP router vendors, including timer parameters. The lower bound on convergence could be reduced from linear time to constant time with minor changes to said implementations.

Using a full mesh may greatly increase the number of paths (up to an exponential

Possible future work includes adding some form of synchronization

Delayed Internet Routing Convergence April 23, 2009

Salient points:

1. This paper represents a significant milestone among the networking research community with respect to understanding the Border Gateway Protocol (BGP). The authors use a theoretical approach to predict the lower and upper bounds for the view convergence among BGP routers. That also serves as a model for systematic theoretical approaches to evaluating other network protocols.
2. The main revelation of the paper is that the delay in convergence is generally much higher than previously thought. The paper formally shows that Internet lags behind public telephony networks in terms of availability, reliability and quality of service.
3. One of the contributions of this paper is their model for injecting faults into the BGP routers to effect changes in routes. Faults are injected from a Fault Injection Server at the Upstream ISPs and RouteViews are collected the other ISP. They try to mimic the real-world occurrence of faults by spacing them randomly. The period of testing has been very extensive (2 years) which gives credibility to their claims.

Concerns with the paper:

While the analysis of the BGP convergence model is extensive, I am not convinced whether the assumptions they have made to simplify the analysis hold in the real world. They consider “a complete graph of autonomous systems as model for Internet,” which favors shortest path. This is not true today, as ISPs route to other ISPs based on business alliance and not based soleley on shortest routes.

Also, they admit that the routing at ASes pass through many other protocols like IBGP, route reflectors etc. but they exculde the dealys caused by these based on their experimentation

Future Work:

More light needs to be shed on the impact or latencies caused by the the above protocols other than BGP which occur during transmission between ISPs. This apart, most ISPs have ingress and egress filters to route certain packets differently than others. The effect of such customer route filtering on BGP needs to be investigated.

Delayed Internet Routing Convergence April 23, 2009

Three Major contributions:

1. BGP convergence in the Internet is an order of magnitude slower than previously thought. Showing that the Internet does not support effective inter-domain failover.
2. Most of these convergence problems are from configuration problems with routers, and differences in implementations. They provide some changes to BGP implementations to help improve this problem.
3. They provide a theoretical upper bound on the latency of BGP convergence.

The most glaring problem with the paper:

For the most part, the study was done using simulation. A simplified model of the internet topology and the BGP algorithm were used. I think a longer  study using a large part of the actual Internet would be extremely useful. This, however, might be infeasible at the moment.

Future research implications:

Application and Protocol architects might have to rethink their designs of current algorithms that depend on effective inter-domain failover. These include QoS dependent things like VoIP, or other content delivery networks.

Delayed Internet Routing Convergence April 23, 2009

The paper describes an elaborate study (spanning two years) of the convergence behavior of the inter-domain routing protocol BGP upon changes to routing paths. The paper describes in detail about the methodology that they used to measure the convergence times averaged over a long period to evaluate the parameter and validate if it was indeed as short as it was previously believed.

One of the primary contributions of the paper is the actual quantitative measurement of the convergence time for BGP over the wide area on the Internet rather than through simulations. As claimed by the authors, although several attempts had been made earlier to measure the convergence time of distance vector protocols, this paper is the first attempt to investigate the convergence of BGP which is a path vector based protocol. Their findings showed that the convergence time for BGP could be as high as O(n!) in the worst case and O(n) in the best case where n is the number of ASes in the Internet.

A second important aspect of the paper is that they measure the convergence time both for the BGP routing information in the network as well as for end-to-end convergence which provides a better measure of actual application level impact of the routing convergence process.

Another contribution is their recommendation for changes to routers which could improve the convergence times based on their understanding of the causes of the long delays in convergence.

One flaw or missing aspect from the paper is that they do not mention the actual location or sizes of the 5 ISPs chosen for the measurements in the study. While the BGP routing information is only decided by the edge routers of the ISPs, the actual end-to-end performance would also be affected by the internal policies used by the ISPs for configuring routes. This could vary between different ISPs and can have an impact on the end-to-end measurements.

From a research perspective, it would be interesting to see if any other changes other than the ones suggested by the authors can actually improve the convergence times of BGP. One of the important aspects is that the existing installed router infrastructure cannot be replaced easily, so what improvements can be effected while using the existing hardware to improve the convergence times.

Delayed Internet Routing Convergence April 23, 2009

Paper addresses the effects of the convergence delay on packet loss and latency in end-to-end Internet paths. Convergence delay is defined as a time elapsed between the router change and by the time a consistent view of the new network established. Authors discuss the distance vector routing algorithms and issues associated with them such as slow convergence, loop formation due to insufficient information transmitted between nodes.

Border Gateway Protocol is discussed which a type of distance vector algorithms used for inter-domain is routing in present day Internet. Though it solves some of the problems associated with the DV algorithms (e.g. count-to-infinity) it is not as fast as believed.

Paper suggests that it is wrong to assume that path vector approach used in BGP can provide much better convergence properties. Internet does not support effective inter-domain failure conditions. It has been suggested that most of the delay in path restoral are due to unexpected interaction of configurable routing  protocol timers and specific router vendor protocol implementation decisions during the process of delayed BGP convergence.  Path vector approach increases the number of possible routing table oscillations though providing the count-to-infinity problem. Internet path failover adversely affect the end-to-end performance. It has been shown that packet loss grows by a factor of 30 and latency by a factor of four during path restoral.

Author analyzes the BGP convergence model and establishes the theoretical bounds on the convergence. It is assumed that message delays are unbounded. Author shows that states explored for the convergence grows exponentially with the number of nodes. Lower bound is Ω ((n-3)*30). It has been shown that by slight modification in present implementation it can be reduced.

Paper suggests specific changes to BGP implementation to improve Internet convergence latencies. It discusses that impact of these inefficiencies on the emerging standards (e.g. VoIP) will be significant.

Delayed Internet Routing Convergence April 23, 2009

The Internet infrastructure had grown in very few years from some dozen to billions of end-users and machines constantly connected. This is putting a big stress on the infrastructure that must be able to deal with failures in order to provide a certain level  of availability, scalability and reliability. Indeed, even transient disruptions in backbone networks can now cause massive finantial loss and disrupt hundreds of thousands of users.

The Internet infrastructure has always been considered to be able to support rapid failure recovery of some node or link through restoration and rerouting on other routes. Unfortunately, this paper proves the opposite.

These are the three main results of the study presented in the paper:

1. The average recovery time from a inter-domain failover is in the order of three minutes with some peaks up to fifteen minutes, hence much higher than originally thought. Moreover, this delay will increase linearly with the addition of  new autonomous systems to the Internet, in the best case. The worst case scenario could take to an exponential growth of the complexity.
2. The BGP convergence is strictly inflenced by vendors’ implementations of the BGP protocol. The authors suggest possibile changes that BGP implementation vendors could use to reduce the Internet convergency latencies. However, this would come at the cost of a higher complexity of the protocol.
3. During their study, the authors observed the behavior and the performance of 5 different major ISPs. The interesting observation that came out of that study is that there were significant variations between the convergence latencies of the five ISPs, completely unrelated to geographical or network distance. This is in contrast with the assumption that the Internet is a complete mesh. If it had been so, we would have observed similar results among the ISPs. Instead, the key factor of these variations relates to topological factors, such as the length and number of the possible paths between an AS and a given destination.

I think that the paper presents a really interesting study of  a real test bed, the Internet itself. The authors indeed injected over a 2 year time period, over 250,000 routing faults into geographically and topologically diverse peering sessions with five different ISPs. Hence, the results presented in the paper are not arficial ones, but they do reflect the real behavior of the Internet. I think that this is a very important aspect of the work presented.

Since the authors claims that the recovery delay from inter-domain failover can increase from linearl to exponential with the number of new autonomous systems, I think it would be good to narrow down this range, also to understand whether major structural changes to the BGP implementation are really needed. In fact, it is not so clear if this is the case because they observed that the average failure ratio is in the order of one failure/month.

Another avenue for further research that I can see is to understand how robust the rerouting protocol really is. In the last few months we have observed at least two major failures of the backbone network, one in the Mediterrean see between Sicily and the North Africa and one in the Bay Area. Both of them created huge problems to many countries for several days. In the case of the Mediterrean failure (the optic wires were cut) part of the Middle East, Noth Africa and even India got completely disconnected from the rest of the world. In theory, this should not have happened if the rerouting algorithm had worked as expected.

Delayed Internet Routing Convergence April 23, 2009

(i) The three most important things the paper says:

1. A major oversight in the internet today is the recovery time of path selection for main BGP routers used by ISPs after a fault. The faults  caused by oscillations in the BGP convergence algorithm. The average and upper bound for time until convergence is much slower than originally predicted and what is commonly assumed.

2. With a small augmentation to the minimum route advertisement interval timer of the BGP convergence algorithm, it you can significantly reduce the convergence time to a constant 30 seconds and reduce the number of states needed as the number of autonomous nodes increase in the network with unbounded delay.

3. If loop detection is done by both the sender and the receiver mutual dependencies can be detected and eliminated within a single advertisement round. This is the lynchpin that allows the modified version of BGP to converge so much quicker than its predecessor.

(ii) The most glaring problem with the paper:

The author spends the first part of the paper arguing that the old theoretical results of convergence were never realized in practice but then spends much effort promoting an augmentation to improve the current theory. The theory is only able to be supported by simulation results but the problems with the other algorithm were only caught long after deployment. It feels like he undercuts the trust in his theoretical results.

(iii) The future research directions of the work:

Further discussion of the overhead of making the adjustments suggested by the author must be viewed. It also will of course be interesting to verify the theory in practice as more service providers adopt changes advocated by the author. An on going analysis should be done as well as exploring other tweaks to the algorithm.

Delayed Internet Routing Convergence April 23, 2009

This paper looks into the latency in internet path failure, failover and repair due to the convergence properties on interdomain routing. The failure recovery times after are substantial as compared to the circuit-switched paths. This burden is created due to the growing size and complexity of the internet. Border Gateway Protocol (BGP) is used as the interdomain routing protocol which uses the path vector approach in including the entire path to the destination. The BGP protocol is widely and incorrectly believed to provide significantly improved convergence performance over other traditional Distance Vector (DV) routing algorithms. The paper provides a theoretical upper bound on the number of computational states explored during BGP convergence which is factorial of the number of autonomous systems in the internet. The paper investigates the rate at which the inter-domain repair and failure information propagates through the Internet. Furthermore, they measure the impact of path changes on end-to-end network performance. The methodology adopted is the analysis of the data collected from the experimental instrumentation of key portions of the internet infrastructure. The authors accomplished this by injecting routing faults into geographically and topologically diverse peering sessions with five major commercial ISPs. They also built a model of the delayed BGP convergence process to provide an upper and lower theoretical computational bound. The theoretical
upper bound is said to be unlikely to occur in practice as it is based on a set of specific assumptions and worst-case scenarios. Finally they related their experimental findings to their theoretical model. They report the delay in internet interdomain path failovers averaged at three minutes. They also argue that the delay of interdomain route convergence is due almost entirely to the unforeseen interaction of the protocol timers with specific router vendor implementation decision. One observation was that the convergence time varied across autonomous systems and therefore the time is directly related to topological factors. One question that arises is if normally occurring Internet failures occur on the average of once a month, do the delays caused by these rare failures have a noticeable effect? Since their solution is relatively straightforward and simple, it is worth making modifications to reduce delays even if the failures are rare. The effect of these failures on end-systems and applications is unclear. Is the situation as dire as they make it out to be? Furthermore, the delay is proportional to the number of autonomous systems.

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

(i) the three most important things the paper says

First off, the paper makes the observation that, due to how the BGP protocol operates, route conversion between BGP routers could take much longer than anticipated when presented with a route withdrawal (via results from other, similar, studies).  The study showed that due to router oscillations (shown through different step-by-step examples) that the worst-case for convergence on any given route withdrawal could be factorial on the number of interconnected BGP hosts.

Secondly, related to the first point, the authors pointed out that inconsistencies in BGP implementations from different vendors proved detrimental to their presented read world results.  I feel that this is an important point, because it may show ambiguities in the BGP protocol that should possibly be more rigidly defined (so as to limit these oscillatory delays present after a BGP withdrawal).

Lastly, the paper creates a great correlation between Tdown timing measurements and theoretical observations made in the paper.  The authors point out that Tdown creates a longer convergence time between BGP routers because of the different cases that are created by the BGP protocol itself (iterating through the numerous routes that a certain router may have stored that are probably not valid routes at all).  The authors bring up the point that using MinRouteAdver significantly decreases the lower bound on this convergence time (another important observation).

(ii) the most glaring problem with the paper

I feel that the paper may make too many simplifying assumptions in their BGP convergence model.  It seems that some of the assumptions might not exist within the context of the Internet today (although this probably an artifact of my lack of knowledge of the architecture of the Internet).  For instance, I found it hard to believe that ASes on the Internet today were somehow peered with all other ASes on the internet [which is the point that I picked up from the authors' statement that all nodes had (n-1) different direct connections].  I feel that some more supporting information was needed for these simplifying assumptions.

(iii) the future research directions of the work

I think that a good future direction for this work would be to perhaps investigate replacement protocols to BGP or perhaps some sort of significant optimization that would reduce the amount of oscillatory behavior in BGP route advertising.  I agree with the authors when they say that improvement needs to be made in convergence time (after a route withdrawal) because of the amount of real-time traffic that continues to be added to the Internet each day.

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.

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

(i) The three most important things the paper says:

1. Routing table oscillations that occur during failure, fail-over and repair of Internet paths can cause routing convergence to take up to tens of minutes (with a theoretical upper bound of O(n!) time), contrary to conventional wisdom that this convergence takes only milliseconds.
2. The authors injected four types of events into the Internet for the purpose of their study. The routing events Tup (a route repair, representing a newly available route) and Tshort (a route repair and fail-over) formed one equivalence class while the events Tdown (a route failure) and Tlong (a route failure and fail-over) represented another equivalence class in both convergence latencies and triggered number of update messages. This is because the former is strictly increasing (similar to DV algorithms) while the latter is monotonically increasing (similar to BGP).
3. Improvements can be made to current convergence latencies by adding sender-side loop detection by modifying MinRouteAdver (significantly reducing state complexity and allowing much faster convergence). However, oscillations triggered by BGP path changes appear to be inevitable. Though we can expedite convergence, this would lead to increased protocol complexity and overhead.

(ii) The most glaring problem with the paper:

This paper discusses the discusses the latency of the system to reach a consistent view after failover, which is on the order of many minutes. However, they first mention that at least one study of user experience places the fail-over latency at 30 seconds or less. This indicates to me that while the “true” fail-over latency may be much longer than people would have expected, the user experience study shows that most people don’t think their experience is all that bad. Though the worst case can in theory be quite bad, perhaps this happens only in rare cases.

(iii) The future research directions of the work:

Possible research directions could maybe explore fail-over latency for the average case in order to reconcile the results obtained in the paper with the user experience study. Further work could also be done to look for better ways to minimize routing table oscillations, as well as to explore average-case trends as the Internet is scaled up.

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

The three most important things the paper says:
1) Extensive experimental data indicates that the Internet does not support effective inter-domain failover.
2) Simulation indicates that convergence time can be improved by employing both sender and receiver side loop detection.
3) If reliable, real time services are to be deployed over the Internet (the paper mentions QoS and VoIP), then the quality of the underlying inter-domain failover must be addressed.

The most glaring problem with the paper:
The proofs for theoretical upper and lower bounds on BGP convergence both assume a complete graph topology. A complete graph topology is stated as a necessary condition for worst case convergence, but they don’t relate their theoretical lower bound for a complete graph to an incomplete graph. The Internet is far from being a complete graph, so I don’t know how useful these bounds are.

The future research directions of the work:
The paper suggested some tweaks to BGP to improve convergence performance, and hinted at some ideas for a better solution, which all involved more complexity and overhead. It is not clear to me that the tradeoff mentioned in the paper between scalability and fault-tolerance is fundamental. Future research should try to find a better solution to inter-domain routing issues which are both more fault-tolerant and more scalable.

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

The paper describes the latencies of various kinds of faults to converge in the internet routing domain. They have experimented over 2 years by injecting several faults and measuring their latency to reach steady states and found that the average latency is orders of magnitude greater than previously reported. The paper also gives theoretical upper and lower bound on the delay of convergence assuming a topology of connected nodes and showed that the worst case time to converge is in the order of factorial of the number of nodes in the internet. Specially the adoption of path vector routing to avoid count to infinity problem has pushed the theoretical upper bound of the convergence delay to be exponentially worse. They have characterized the convergence delay based on four kinds of faults, viz. Tup, Tdown, Tlong, Tshort which are the cases when a new link comes up, an existing link goes down, a longer link is available and a shorter link is available respectively. According to their experimental observation both Tlong and Tdown converge more slowly than Tshort and Tup. This was also in accordance to the number of messages sent in the respective cases. Also the delay of end to end packet delivery and percentage loss of packets agreed with the fast and slow convergence of Tshort and Tlong respectively.

The paper addresses the delay of convergence of various faults in the internet and has tried to provide theoretical basis for such observations. According to them the actual observed delays are orders of magnitude worse than previously reported numbers which is also supported by the theoretical upper bound. But the theoretical analysis assumes complete mesh topology of the internet which is rarely the case in practice. Hence the worse case theoretical upper bounds may not hold and depends on the actual topological factors of the networks. Nevertheless, they have proposed a theoretical base on which the even the average case can be analysed for convergence delay in the real case.

The future directions of the research can be of designing better routing algorithms than path vectoring that does not have such exponential worst case complexity for convergence delay. As the paper stated, with the growth and increasing complexity of the internet, routing convergence delay will become significant and possibly a bottleneck in future. Hence the application layer protocols also needs to be re-evaluated which relies on stable underlying interdomain forwarding infrastructure and fast IP path restoral. Also specific changes to future vendor BGP implementation should be employed that can significantly improve the internet convergence latencies.

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

1) This paper’s main objective is to dispel the conventional wisdom about internet failover. Specifically regarding the fact that the Internet actually does not support an effective nor efficient inter domain failover because of delayed BGP convergence.

2) Another main point are the reasons why routing events Tup and Tshort converge faster than Tdown and Tlong. Understanding the reasons why one is strictly increasing vs monotonically increasing is a key point in understanding the delay and what measures could be taken to mitigate it.

3) They also show, by means of actual experimentation, that even a moderate level of routing table oscillation will lead to increase packet loss. This drives their point home, that delay BGP convergence has an effect that is exponentially worse than originally perceived.

(ii) The most glaring problem with the paper:

This paper is actually pretty well written with experimentation and analysis of real network data. So there aren’t any *truly* glaring problems; however if I had to critique it, I would have to say that it does not offer any true solutions. The “tweak” that was suggested for MinRouteAdver is only a band-aid and cannot be relied upon to fully address the issue. If they actually propose a real working solution, then this paper would become more complete.

(iii) The future research directions of the work:

After reading the paper, it seems the most critical area for research would be one of two areas. Either to work on new internet protocols that is robust enough to handle the worse case scenarios of delayed BGP convergence. The other direction could be to solve the problem of delayed BGP convergence or at least further mitigate this issue. I feel that solving either problems is important, because as the internet grows, this problem will get worse considering that the complexity is based on the number of nodes.

Delayed Internet Routing Convergence April 23, 2009

The paper “Delayed Internet Routing Convergence” makes three important contributions to the problem of convergence of interdomain routing:

First, the authors present an experimental study on route repair, failure and failover events injected into the routing infrastructure. They observe key exchange points too see how long BGP routers exchange messages after injecting events before all observed ISPs agree on the routing configuration for their experimental stub AS. Metrics included the number of BGP update messages sent and the time until convergence, i.e. when no more messages where generated for this particular event. Also analyzed are end-to-end connectivity by looking at packet loss rates and latency.

Second, the paper contributes a theoretical model for the convergence of the BGP protocol based on the BGP specification, simulation and the previously described experiments. The analysis of the upper bound on the convergence given by this model emerges interesting properties  of BGP.

Third, a proposal to improve the slow convergence of BGP by introducing a loop detection on AS paths exchanged via BGP messages for both partners of the message exchange, sender and receiver.

As the authors acknowledge, implementing the solution does only mitigate some part of the problem, but doesn’t face the problem of slow convergence itself. So further research on these matters and on follow-on protocols to BGP is needed.

Delayed Internet Routing Convergence April 23, 2009

i)

1. Contrary to popular belief the BGP protocol takes longer to failover than previously thought. This delay was primarily due to protocol timers and implementation decisions in the routers.

2. Tdown (a route failure) and Tlong (route failure & failover) both take significantly longer to propogate throughout the internet than Tup (new route/route repair) and Tshort (route repair & failover).  This is because information about a longer path takes more time to spread than information about a shorter path. This is because there tends to be multiple routes between some router A out in the internet and the destination B and the information that the route to the destination is now longer must spread to at least 1 router along every previous path of length less than the new real path length from A to B.

3. BGP routers are usually implemented to only send updates to a particular peer at a rate of at most once every 30 seconds. This however creates in effect 30 second rounds. A solution that would improve convergence time would be to have a timer for every (destination prefix, peer) tuple, or some sort of solution that emulated such a system. This would improve convergence time at the cost of possibly increased # of packets sent and requiring more memory on the router.

ii) I think the most glaring problem is the authors only considered faults at the end host and did not evaluate how effective BGP was when there are faults in the middle.

iii) Future research directions include exploring what other tweaks / impelementation details can be changed to impove convergence times since with the increase of streaming video and VoIP, the quicker to failover the better.

Delayed Internet Routing Convergence April 23, 2009

The growth in size and complexity of the Internet calls for stronger routing infrastructure. The authors of the paper conducted a series of experiments to the latency in Internet path failure, failover and repair due to the convergence properties of inter-domain routing over a two-year period. They attribute this delay to the slow convergence of routing algorithms. The BGP protocol uses a path vector with the entire path to the destination as opposed to the DV approach and BGP is believed to have lower latencies. The paper shows that the upper bound on complexity for BGP convergence is factorial with respect to the number of autonomous systems. The authors investigate the rate at which the inter-domain repair and failure information propagates through the Internet and finally measure the impact of path changes on end-to-end network performance.

In their experiment, the authors collected data over the course of two years while injecting over 250000 routing faults in 5 major ISPs. They also built a fault model of the delayed BGP convergence process to provide an upper and lower theoretical computational bound. The theoretical upper bound is shown to be unlikely to occur in practice as it is based on a set of specific assumptions and worst-case scenarios. The theoretical lower bound is closer to practice since timers are used to handle synchronization issues not accounted for in the upper bound. The authors finally link their experimental results to the theoretical fault model proposed.

Some important experimental results discussed in the papers are, the average delay in inter-domain path failovers was three minutes, the theoretical upper bound on BGP convergence is O(n!) with n autonomous systems, the lower bound on BGP convergence is Ω((n-3)*30) with n autonomous systems, the delay of inter-domain route convergence is almost entirely attributable to unforeseen interaction of protocol timers, the path failover results in packet loss growth factor of 30 and latency increase factor of 4 on end-to-end performance and lastly changes to vendor BGP implementations would reduce lower bound on inter-domain convergence to Ω(30). An important observation was that the convergence time varied across autonomous systems and therefore the time is directly related to topological factors.

Although the experimental analysis is made thoroughly and is convincing of the fact that the routing delay in the internet stems from the convergence of algorithms, the oversimplified theoretical treatment in the later half of the paper slackens the stronghold established by experimentation. The future that stems from the observations made in the paper are that although the average internet failures rates are rare, if the effect of these failures is noticeable then a cheap feasible solution should be explored and deployed. Further since the delay is proportional to the number of autonomous systems, it is imperative to know the rate at which their numbers are increasing. If these observations are validated and investigated then there will be a better indication on whether BGP needs improvement and the algorithmic and protocol changes that need to be done to make it more fault-tolerant with lower latency.

Delayed Internet Routing Convergence April 23, 2009

This paper shows that the common belief that BGP has good convergence properties is inaccurate. To show this Labovits et al. uses passive data collection for a 2 year period and also used a fault-injected machine at major Internet exchange points.

Three most important things:
1.) Measurements
When they looked at their results from the measurements, Labovits et al. notice that the routing convergence was an order magnitude longer than expected. They used a four categrories for describing the route injection: Tup(unavailable route is now available), Tdown(available route is withdrawn), Tshort(long route is replaced with short) and Tlong(short route is replaced with long). Their results showed that Tdown and Tlong converged slower than Tup and Tshort which in idle situation you would want Tdown and Tlong to converge quickly and Tup and Tshort to converge slowly. Tdown also generated a lot more announcements than Tup.
2.) Impact of slow routing convergence
It turns out that the slow routing convergence has an impact on end-to-end internet paths. This is because the routers will drop the packets if they do not have a valid next hop so we will have more dropped packets or they will queue packets while awaiting for their forwarding table cache to update. Their results show the increase packets drops, which occur more on TLong than Tshort because TLong takes longer to converge.
3.) Analysis
The analysis on why Tlong converges longer than Tshort is because, Tshort is accepted quicker than Tlong. When we get a Tlong in BGP, we first try to find all alternatives for the shortest path which can be O(n) long if n is the number of autonomous systems. The rest of the slowness in convergence can be credited to the vendor’s BGP policies.

Glaring Problem:
The most glaring problem is mention by the author himself. In his proposals to fix this problem, he suggests fixes that make the BGP protocol very complex and create more router overhead. Having a complex protocol goes into the debate of scalability versus fault-tolerance.

Future Work:
Labovits et al. showed that something that was commonly believed to be true was infact very inaccurate with just measurements and analysis. It comes to show the difference between theory and implementations as many things can come into play during the implementations. This paper will help evaluate other protocols to reassure that the protocols are acting as they should be.

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

Major Contributions

1. This paper presents the results of a two year study on the convergence of the BGP routing protocol and provides recommendations to reduce convergence time and overhead mainly caused by BGP routers with different implementations due to the ambiguity of BGP specs. RouteView data collection probe was used to log and timestamp all BGP updates from BGP routers of vaious ISPs. Results show that failover delay is independent of network load, congestion, locality and more dependent on topology.

2. A fault injection server was used to inject BGP faults to upstream ISPs and measure the latency to random websites. The failure injection measurement results were taken for BGP events Tup, Tdown, Tshort, and Tlong and measured how long it takes for all the route tables to converge following an event. Tup is a previously unavailable route is now available. Tdown is the opposite of Tup. Tshort is a long ASPath is now replaced by a shorter ASPath. Tlong is the opposite of Tshort. From the distribution of convergence latencies following Tlong, Tdown, Tshort, and Tup faults,  the authors find that Tlong and Tdown form one equivalence class, and Tshort and Tup formed another equivalence class. Tlong and Tdown took almost three times the amount of time to converge compared to Tshort and Tup events. Analysis showed that Tlong and Tdown took longer because it is monotonically incrasing compared to strictly increasing for Tshort and Tup events. The results also show that RTT latency to random websites increased by a factor of four following a failover event and packet loss increased by a factor of 30.

3. The paper provides vendor specific recommendations to reduce convergence lower bound to 30 seconds by analyzing changes to MinRouteAdver using simulation data. The recommendation is to implement both sender and receive side ASPath loop detection, and do not apply MinRouteAdver to Tdown withdrawals.

The most glaring problem is not answering the question of how often these rare long convergence delays occur and whether BGP can still scale without much modification given some constraints on topology.

With routers getting faster, further research considerations with implementing additions or modifications to BGP to improve convergence times using synchronization, diffusing updates, and having additional state information may be feasible. Further research can also consider a complete overhaul or replacement of BGP.

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

The paper takes a critical and look at BGP route convergence in the face of failover/updates. It provides empirical measurements of real Internet latencies and packet losses for a period of over 2 years as well as theoretical analysis for worst and best case complexity of the route convergence process.

The paper brings to light the fact that most of the failovers measured during the 2 year period took an average of 3 minutes to converge. This observation provides hard statistical evidence that there are considerable BGP inefficiencies. Moreover, this duration length is considerably higher as compared to telephone network failovers. The underlying point here being that the network infrastructure supporting the Internet should be as efficient at resolving failures as the telephone network, especially given the increasing reliance on the Internet for business purposes.

The paper also analyzes the BGP protocol from a theoretical perspective. Given a completely connected graph model for the Internet and certain message ordering and processing constraints, the authors show that unbounded delay BGP messages can result in Ο((n-1)!) states. This is of course the upper bound, but it provides insight into how the network topology and BGP router processing details can affect route convergence. Additionally, the authors point out that a lower bound also exists for router states (or rounds as termed in the paper). If the BGP routers adhere to the minimum route advertisement delay and process messages of route length in increasing order (among other constraints), the lower bound is Ω(n).

Lastly, as a result of the analysis on the lower bound for rounds/states, the authors provide implementation suggestions and optimizations to reduce the lower bound to Ω(1). The minor changes to BGP implementations include performing sender and receiver loop detection and using peerwise MinRouteAdvert times. These suggestions allow routers to converge in one round. The paper provides simulation results that explore the unbounded, MinRouteAdvert, and modified (as per suggestions) MinRouyteAdvert implementations of BGP. These results validate the theoretical implications made by the authors.

The paper is a solid presentation of simulation, theoretical analysis, and real world observation/experimentation results. The only criticism is that the authors make the comparison between the public switched telephone network and the Internet. This isn’t necessarily a fair comparison as the telephone networks were designed with a dedicated single purpose, presumably using the same underlying technology throughout. The Internet serves considerably larger topologies, provides numerous varying uses, and runs on a myriad of technologies. Providing faster failure convergence is a great endeavor, but comparing against the telephone network may be too ambitious.

I think the path for further research would be to implement some of the suggestions and perform a long term test of the efficacy of the modified MinRouteAdvert protocol.

Suggestions for Web Server Evaluation April 21, 2009

You might find it helpful to check out the web server evaluations performed in the following two papers:

• Flash: An Efficient and Portable Web Server
• SEDA: An Architecture for Well-Conditioned, Scalable Internet Services

We don’t require that you evaluate your web server using the approaches from these papers; feel free to copy those tests that seem relevant, but be sure to justify why you picked them.

Untraceable Electronic Mail, Return Addresses and Digital Pseudonyms April 21, 2009

(i) The three most important things the paper says:

1. A problem with using traditional public key cryptography in electronic mail systems (that is, using a cryptographic system such as RSA to encrypt/decrypt messages) is that although the contents of the sealed messages are safe from prying eyes, other information such as the origin and destination of the messages may be easily determined, and messages may be tampered with (added, deleted or changed). In other words, cryptography is employed to guarantee message secrecy, but authentication is not ensured. The paper attempts to obtain some additional security for messages in a mail system even when one or more authorities may be malicious. The idea is to send messages through a number of “mix” computers and to obfuscate the sender’s identity through a layered series of encryptions, so that the sender’s identity is hidden even if all but one of the authorities is malicious.
2. To send a message, the participant prepares a message K_n(R_n, K_n-1(R_n-1, …, K₁(R₁, K_a(R₀, M), A) …)) (where K_i is the public key of mix i, R_i is a random string, K_a is the addressee’s public key, M is the original message and A is the destination address) which passes through a cascade of n mixes. Each mix peels away a layer of the encryption to determine the “next hop” until the message is delivered to the recipient. A similar idea is used to allow the receiver to respond to the sender while unable to detect the sender’s identity by using an untraceable return address embedded in the prepared response.
3. The idea of being able to send anonymous messages is also useful in the context of a general election. Applicants send an anonymous letter to the voting authority with their digital pseudonym, a public key that may be used to verify their future actions, as well as other information that would allow the authority to decide whether to accept the application or not. The authority can then prepare a roster from the accepted pseudonyms. Ballots received from applicants are similar to the prepared inputs for n mixes described above. Once the input reaches the authority (the recipient), it is of the form K, K^-1(C, V), where K is the pseudonym, K^-1 is the corresponding private key of the applicant, C is some constant and V is the vote, the authority verifies that the pseudonym matches an entry in the roster and then decrypts and counts the vote.

(ii) The most glaring problem with the paper:

At the time this paper was written, it may have seemed like a good idea to have a technique for allowing anonymous mail to be send through an e-mail system. However, with the advent of spam and phishing via e-mail, allowing anonymous e-mail on the Internet may no longer be such a good idea.

Furthermore, the government would likely want to be able to obtain certain information pertaining to mail messages without having to subpoena every single mail provider.

(iii) The future research directions of the work:

Although I don’t believe that mix nets are feasible in e-mail systems today given the current climate, there are certainly other applications for a method which allows for anonymous feedback. Perhaps a mix network can be used on a more limited scope to provide anonymous feedback for a variety of situations. Governments may also want to be able to have this capability for sending out anonymous e-mails that cannot be traced back to them (though perhaps this can be done with the use of proxies?). One of the most prominent uses for mix nets in current research is in voting (and many proposals for online voting in particular) to provide ballot secrecy. The idea of leveraging untraceable return addresses may also be used to permit voters to audit an election by checking their own votes.

Inferring Internet Denial-of-Service Activity April 21, 2009

In this paper the authors attempt to gauge the amount of denial-of-service attacks are happening on the internet. Most denial of service attacks attempt to either flood the victim with a large number of small packets (since routers and NICs are limited by packets/second no bytes/second) and/or send a large number of requests that need to be processed by the operating system or an application by sending a large number of TCP SYN packets. The attackers also lie about their ip on the packets they send to the victim so the victim cannot identify attackers or easily filter to the malicious packets (this is known as ip spoofing).

The authors use a technique known as backscatter analysis to try and detect denial-of-service attacks. Backscatter analysis involves listening to a chunk of the ip address space that is not actively in use and logging any unsolicited packets that are recieved. The idea is that attackers spoof their ips in a uniformly random distribution so when the victim sends out a response to the malicious packet the responses are uniformly distributed across the entire ip address space. It should be noted that this paper’s analysis relies on the assumptions that addresses are spoofed in a uniformly random manner, there is reliable delivery of response packets, and unsolicited packets are backscatter from a denial-of-service attack.  The authors verify for attacks that they detect, the responses for that attack are uniformly distribute throughout the chunk of addresses they are listening on. As for reliable delivery or responses,  response packets that get dropped will only cause the intensity of the attack to be underestimated.

The authors logged all packets recieved in a chunk of ip addresses that made up 1/256th of the ip address space over the span of 3 seperate 1 week periods. In order to estimate the intensity of the attacks they simply multiply the number of packets they recieved by 256 since they are theoretically recieving 1/256th of the responses. During the sampling time they detected 12,805 attacks directed at over 5,000 unique ips. TCP SYN floods made up over 50% of the attacks they observed. Of these SYN flood attacks about 46% of them could generate packet rates high enough to overwhelm a typical server and 2.4% of them could overwhelm servers with specialized firewalls to protect against SYN floods.

Other Interesting Observations:

• 50% of attacks last less than 10 minutes and 90% of attacks lasted less than an hour
• A significant portion of attacks are directed against home computers indicating they are being used to settle grudges.
• 2-3% of attacks are directed against network infrastructure such as name servers.
• Attacks are directed at a wide range of comercial targets ranging from Amazon or AOL to small and medium size businesses.
• After attacks against URLs in the .com and .net domains, .ro (Romania) and .br (Brazil) were the next most frequently attacked.
• 65% of victims were only attacked once.

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

Convergence time of routing information and packet loss and delay due to inter-domain route changes, longer than expected.

Paper carries out experiments and analyses data collected to determine the average time taken before inter-domain routing information reaches steady state after there has been a change in the topology of an Autonomous System (AS). Data was collected by injecting routing faults into five major ISPs over a period of two years. In one of its experiments the paper observes that  20% of nodes require more than 3 minutes to converge for a Tdown or Tlong update.

Factors convergence time depends on.

The paper makes mention of some interesting factors convergence time depends (and does not depend) on. It provides experimental proofs and reasoning to support its claims. Some of them are:

i) Order in which route-change announcements are processed at a node

ii) Number of interconnections between AS (number of BGP peers). A complete graph would have larger number of computational states to be explored during convergence.

iii) Upstream provider transit property.

iv) If loop detection is done at only the receiver or both the sender and the receiver.

v) Largely independent of network load and congestion.

vi) Independent of geographical location of the node.

T-long and T-down have longer convergence times and why.

In the experimental data gathered by the paper it can be noted that convergence time and latencies are larger when the topology change involved a route going down. This might have resulted in a node becoming inaccessible or a longer route having to be taken. The paper analyses the sequence of events that occur when a route disappears and the how this results in T-down and T-long requiring longer convergence times as compared to T-short and T-up. In the case of T-down, a node keeps failing over to a longer secondary path before it exhausts all of them and realizes that the destination node is no longer available.

Problems/Oversights.

A couple of assumptions the paper makes in its experimental methods might not accurately model internet. Some of them are:

- It monitors the routing tables of only 25 ISPs. This might or might not correctly reflect packet forwarding and updating times over internet. More ISPs would mean more locations from which updates might reach a node.

- It models BGP messages to be processed in a single linear queue. This only models the case where there exist high congestion and long delays over the internet.

Future Work

The new system can be modeled which imbibes in itself factors claimed by the paper to reduce convergence times. These could involve, among others, sender and receiver end loop detection, re-ordering of announcements received to reduce convergence times, etc. This new system could be analyzed to obtain a quantitative measure of the enhancement that can be achieved at adding some amount of complexity to the internet protocol.

How to 0wn the Internet in your spare time April 18, 2009

This paper is primarily a discussion of several internet “worms” that had a major impact on the way people viewed Internet security, the different methods by which they might spread and several proposals that could greatly help with such threats in the future. The three key ideas that I got from this paper were:

1. Worms such as Code Red and Nimbda show the plausibility of gaining control of thousands or more computers in a completely automated fashion in a relatively short period of time. The power that could be wielded by such a botnet is startling and could even approach the sort of power only entrusted to governments. This is a serious threat that must be taken into consideration when designing any kind of software or hardware system.

2. Worms use a variety of methods to spread, some discrete and some not, and Nimbda showed that it does not even have to spread to every computer by the same means. A multi-vector attack can be extremely successful if the creator is talented enough. When designing system security, it is very important to look at all possible angles and implement defense in depth in order to guard against those possibilities that may not have been thought of.

3. A centralized agency with appropriate resources could be of great use in identifying outbreaks, analyzing the virus’s, developing protection mechanisms, and helping to slow or even stop the spread of a large scale worm. The example used in the paper was the CDC and I do believe that this metaphor is fairly appropriate. This problem could be big enough for the government to devote significant funding as it is hard to believe that there are not outside agencies that would not hesitate to release a new large-scale virus attack if it was available to them.

The most glaring weakness of this paper that I saw was that while it did a good job of analyzing the (at the time) recent attacks and discussing large scale controls that could be implemented. I think that it could have focused more attention on the user habits and security lapses that were most common to the spread of these virus’s and the standard controls that could have prevented them. While a large agency would be instrumental after the attack has happened, it is really at a lower level that security controls must be implemented in order to truly prevent a worm from spreading.

Future research in this area has been ongoing, both in their suggestion of a centralized agency and with lower level security. People are much more security conscious now than at the time that Code Red and Nimbda were deployed and attackers have a much more difficult job on their hands. There have also been efforts to centralize computer security analysis and tracking through organizations such as NIST, CERT, and private parties like E-Security, among others. This has let to a much greater understanding of such attacks and a large increase in communication between all of the white hats that are working for the good guys. While we have made improvements, I feel that there is a long way to go and in all likelihood, security research will remain an ongoing project as long as the internet is in existence.

On Packet Switches with Infinite Storage April 18, 2009

(i) The three most important things the paper says:

1. By considering a packet switch network with infinite storage we can ignore the problem that is often focused on, buffer management, and instead concentrate on solving congestion. It is found that with congestion a datagram network may drop all packets.

2. It is possible and not even difficult with today’s technology to make a network switch with “infinite buffer space”. The author states that for an ARPANET-like network with 15s time to live only 420K bytes are needed to guarantee that no packets will be lost due to buffer exhaustion.

3. Not all protocol implementation are done in well behaved manor. That is they do not adhere to the protocol in a way such that maximum throughput can be seen for all users. The author says the best possible solution is one where you make the network perform best when the user is well behaved. This encouragement makes no room for temptation that you can offer better performance for your clients by making adjustments that hurt the network as a whole. To do this the author suggests that each first order network switch (the on closest to the user) the switch should have multiple queues that it services in a round robin fashion rather than one queue which is first come first serve. Since this guarantees every user a chance to go high congestion will not make all packets lost. And if the big congestion is created by just one user only his packets will be dropped and others will not be affected. This means that optimal throughput will be to only send packets at the rate the network can handle them.

(ii) The most glaring problem with the paper:

The author of this paper differentiates between badly behaved and malicious protocol implementations in the following way. He states that badly behaved implementations are those that do not follow the exact specs of the protocol usually for some gain in performance for themselves.  Malicious programs however are just trying to damage the network by creating unneeded congestion with no gain for itself.  The author gives the example of giving packets with many different host fields to clutter the network and slow it down.  The author says that this is a discussion that shall be left to network security and not addressed in this paper. The problem is that a badly behaved implementation could use this as well, since by acting as two hosts he would be able to get two turns for each round and be able to send packets almost twice as fast as other users making the network no longer fair.

(iii) The future research directions of the work:

The author leaves it wide open on what should be done about malicious implementations of the protocol and does not address the case of a badly behaved protocol pretending to be more than one user. The author has not began testing his theory of having a fair network delivery service of round robin, rather than first come first serve.  As such, someone needs to implement such a network and begin getting performance results for such a system to back the authors claim that this is an effective way to only reward well behaved protocol implementations.

Jigsaw: Solving the Puzzle of Enterprise 802.11 Analysis April 18, 2009

Jigsaw is a paper that tries to answer the question of “What is going on in my wireless network?” It seems now that more and more enterprises are deploying access points(AP) in their sites for wireless internet. The problem with wireless versus wired networks is that wireless networks are not well described as either a single broadcast channel nor as a graph of links. There can be many reasons why a receiver in a wireless network did not receive a frame, including the distance between the receiver and AP, sender’s transmit power, microwaves, etc… With the problems set, Jigsaw differs from other research because it is more broad. Other research has measured wireless networks problems individually while Jigsaw measures a wireless network(aiming at enterprises) as a whole using 150 monitors at the UCSD CSE building to capture all the data and send it to Jigsaw, their centralized measurement application.
The three most important features of this approach are:
1.) Trace Merging
Trace merging allows Jigsaw to make sense of all the traces/data from the monitors. In order for trace merging to be successful, Jigsaw needs three things: unification, synchronization and efficiency. Jigsaw needs unification because multiple monitors might receive a particular frame that so happens to be a duplicate frame. Since the hardware might have different clocks it is important that the timestamps used from the monitors be the same so Jigsaw estimates a global time for each monitor. Lastly trace merging must execute efficiently because to allow online applications. Trace merging is good approach to tackling such a large scale problem.
2.) Reconstruction of Link and Transport Layer
After Jigsaw receives all the frames from the monitors it must reconstruct the link and transport layer. For the link layer, Jigsaw groups frames by MAC address to make sure that transmission request are delivered properly. Sequence numbers are also used on the group of frames. For the transport layer, Jigsaw takes frame exchanges and reconstructs TCP flows using the packet headers. Jigsaw also captures TCP acks to find omitted frames from the packet.
3.) Results
The results that Jigsaw found showed that Jigsaw works. They found out that the 802.11g protection mode for networks that have both b and g were creating a lot of traffic because of the conservative policy timeout. They also found out that the 802.11 management software were creating a lot of ARP request. Multiple copies of the same ARP request will also interfere with each other. These problems are hard to find without Jigsaw.

Potential problems:
The potential problems with Jigsaw is does it really scale? Since monitors are capturing all packets in the wireless network and sending them through the wire network, this can become a problem. Although in this case UCSD’s Gigabyte ethernet could easily handle it, maybe the monitors could be more complex in shorting their frames. An example of this is say a monitor hears a frame and the corresponding ack. Instead of sending both the frame and ack, the monitor can send some message that just states that a frame and corresponding ack came.

Possible future research:
From the results it is clear that Jigsaw is going towards the right direction. It was capable of finding some reasons why wireless networks are slow, via protection mode of 802.11g, ARP, etc… The authors plan to build on top of Jigsaw to further answer why networks are slow and how they can be fixed. It would be interesting if the authors can find a natural flaw in wireless technologies in large enterprises. The gap between measuring wireless and wired networks is shrinking.

Internet Indirection Infrastructure April 16, 2009

This seems to do the same as SSH reverse tunneling in terms of its mobility.

Indirection — this allows for portability in that the end user does not need to know the exact location of the other end and the system can more easily do “creative” rerouting (e.g. multicast).

Distributed routing “tables” — instead of having one central domain name server as a single point of failure, this allows for some reliability through multiplexing and redundancy.

I see an issue with the routing efficiency. The paper gives the example of having the sender and receiver in Berkeley, but the i3 node storing the triggers in London. The claim is that the data can avoid the trip from Berkeley to London and back by way of a private trigger on a closer server, but does not account for the case where there is no closer server.

Internet Indirection Infrastructure April 16, 2009

Three Important Things:

• The motivating observation by the authors is that the demand for additional internet abstractions is out there, and the current IP layer cannot provide things such as multicast, anycast, and mobility in a scalable way. Taking the overlay network approach to this problem is a crucial decision, and it has the advantage of working with the infrastructure in place instead of trying to replace it. Such a network could be easily deployed in today’s internet, and based on the evaluation of its merit could someday become the dominant protocol.
• By decoupling the sender from the receiver i3 is able to implement a variety of services. Using indirection is a key design point that enables flexible communication between hosts. This transition to rendezvous-based communication  is a marked improvement over the point to point model.
• As the way that we use the internet has evolved, security has become a primary concern because of the services that are delivered over the internet. The problem is that the protocols in use today were not designed with security in mind. Any new idea for internet architecture should make sure to address security concerns. The paper comments on issues that are particularly relevant such as eavesdropping and DoS attacks.  The ability to have private triggers, enforcing that only a host can insert triggers on its own behalf, and fair queuing are all important extensions.

Glaring Problem:
A major concern with i3 is that the end hosts are responsible for inserting triggers, which means that it would be hard to enforce order and structure in the resulting overlay network. I would have liked to see the paper address this more fully, and maybe elaborate on how a large scale network could evolve out of an ad hoc, approach. This is discussed in the context of preventing attacks, but not in terms of how the network should be structured.

Future Work:
The i3 overlay is presented to us as a general mechanism for implementing communication abstractions. It would be interesting to see what other abstractions could be implemented with i3 in its current form or with extensions.

Internet Indirection Infrastructure April 16, 2009

(i) The three most important things the paper says:

1. The author suggests adding more robustness and flexibility to the IP protocol with the introduction of i3 as an overlay on top of IP. The defining feature of this new protocol is that it is designed to be support more than peer to peer communication as the original IP protocol first envisioned. i3 is aimed at easily adapting multicast, anycast and host mobility while still efficiently handling unicast.

2. The protocol uses packet ids and triggers to route packets instead of source and destination adresses. This means that the sender does not need to know exactly who he is sending his data to, and multicast is attained by having multiple hosts subscribe (by creating triggers) for that packet id. This means that no extra protocol or overhead is needed to attain other types of communication which is needed with IP alone.

3. This protocol has gone to great lengths to take design ideas from what has shown it was adaptable by users in the past. The author emphasizes that the protocol can be incrementally distributed and will work even when a low percentage of the machines support i3. This will greatly help a transitional phase to adapt this protocol. The protocol also limits itself in adapting IP’s best effort delivery model and not adding overhead by adding checks when not all applications would find then useful. This has been proven to be a key when designing a flexible enough system to enable widespread support.

(ii) The most glaring problem with the paper:

A contradiction that this paper suggests but does not offer a solution or recommendation for is that for many of the security and large scale multicast problems they recommend adding a trigger hierarchy to decouple the sender from the receiver, but for performance they recommend caching the receiver so the messages can be sent directly.

(iii) The future research directions of the work:

The paper offers many suggestions for possible future research on i3.  The state that parameters, algorithms and protocol should be experimented with for optimal performance, so the benefits for i3 can be fully assessed. The many security risks pointed out by the paper should also be considered and a balance of security versus performance should also be found before this technology could be deployed. After limited or full deployment there would be many measurements to compile and evaluate to gain further insight on the uses of i3.

Internet Indirection Infrastructure April 16, 2009

The paper proposes an overlay network introducing a level of indirection which allows an easy implementation of the multicast, anycast and host mobility. The i3 overlay provides a rendezvous-based communication abstraction which decouples senders from receivers.

In i3 packets are represented by pairs of message identifier (id) and data. Receivers wanting to an id class attach their addresses with that id to form triggers. The packet identifiers are distributed among the available i3-nodes that are connected in a loop. The packet id is matched until it researches the node whose id matches and from that node, the packet is sent to the destination basing the receiver-address. Further the authors propose that packets and triggers may contain a stack of identifiers to allow service composition, eliminating the clients’ need to know the identity of service provider. The authors point the key differences between the existing rendezvous based overlays like the distributed-event system and i3 and describe their event-dispatching architectures. In a conventional event-based systems, a set of hosts subscribe to a set of events and notify them to a distributed dispatcher routes them as per the subscription. Similar to this model triggers distributed in i3. Also, the traditional system use overlay for routing even notifications whereas i3 uses the IP address of the receiver (a part from some inter-i3-nodes transmissions).

The paper mentions that since i3 end-hosts are responsible for maintaining the routing information through triggers, this poses security threats since users can eavesdrop, isolate a host by removing its trigger and also adversely affect a server of another host. To overcome the authors propose the use of public and private triggers, so as to make i3 at least as secure as IP. The authors then propose ways to make the system robust to i3-node failures: one based on backup triggers, and the other on trigger replication. A possible problem in the i3 could stem from the fact that the final i3-node can be far apart from the sender and the receiver although the two are physically close and this may introduce unnecessary latency. The authors alleviate this problem by proposing that the server selection should be made on the basis of the last m-k bits, which should contain the location information and for private triggers, they make an assumption which states that receivers will check identifier space to find ranges located on nearby i3-nodes. Further the latency arising from sender-to-server network distance is addressed by caching the server IP-address on the sender. They present a performance evaluation by providing simulations of the end-to-end latency and the improvement in this latency by using proximity routing.

The authors also provide simulations for the trigger insertion, data packet forwarding, and throughput. They find that as packet size increases, memory copy operations and pushing bits through the network dominate processing time, and that user throughput increases as packet payload increases since the overhead for headers and processing is small relative to the payload. Since i3 is incrementally deployed as an overlay at the same time giving the security of ip, it can be evaluated and deployed to augment the existing point-to-point links in networks which may benefit from multicast and anycast. And like the authors mention in the paper, third party providers can seamlessly provide i3 service and dependence on major ISPs can be decreased.

Internet Indirection Infrastructure April 16, 2009

(i) the three most important things the paper says:

1. The Internet Indirection Infrastructure (i3) is an overlay-based network infrastructure which provides a level of indirection that is convenient for implementing such services as mobility, multicast and anycast. i3 provides this indirection by decoupling the act of sending from that of receiving via the use of packets and triggers. Senders and receivers use an address, id, to send and receive messages. In particular, senders send a message addressed to id (by sending a packet consisting of id and their message), while receivers express their interest in receiving a packet destined to id by registering a trigger consisting of id and their own IP address/port.
2. i3 addresses various security issues by using techniques such as private and public triggers (with private triggers encrypted and shared via a public trigger), an additional level of indirection in the trigger to protect against trigger hijacking, and use of random nonces and resource capping to avoid denial of service attacks.
3. An implementation of i3 was built using the Chord overlay protocol, which was chosen due to its robustness, scalability, efficiency and stability. Caching is used to avoid hot-spots (i.e. if a flood of clients all try to contact a particular trigger) — specifically, the S which keeps the trigger will send a copy to another server (and more if necessary) to offload some of the traffic. Backup triggers and replication of triggers in the servers is used to protect against failure.

(ii) the most glaring problem with the paper:

Adding extra indirection and particularly pushing storage and translation of rendezvous identifiers into the network seems to be a violation of the end-to-end principle.

(iii) the future research directions of the work:

A more fleshed-out implementation of the overlay network as well as stronger benchmarking results (perhaps helped by re-implementing the finger table with a more efficient data structure) would help bolster the author’s arguments. Further applications that could capitalize on the properties provided by the infrastructure (mobility, multicast, anycast) could be built and compared to current implementations that do not use the infrastructure. Additional experiments to verify some of the properties that the authors describe in their system (such as incremental deployment and protection against failure) would be interesting.

Internet Indirection Infrastructure April 16, 2009

The main contributions of this paper are:

1. Indirection: the authors discuss how decoupling of the sender and receivers helps to generalize point-to-point communication. i3 provides better mobility, multicast, and anycast through this indirection. i3 identifiers and triggers serve to achieve this level of indirection.
2. The paper proves the flexibility of overlay networks. It further provides valuable techniques to build security, scalability, availability, fault tolerance, and improved performance on top of the overlay. Overlay also allows for incremental deployment of i3 in a network.
3. The authors provide many novel ideas such as using a stack of i3 identifiers to achieve service composition on top of i3, heterogeneous multicast (where receivers choose to receive different flavors of the multicast data), and fault tolerance (if one identifier fails, try the next identifier).

Glaring problems: The paper is well written and many scenarios are well thought of, however, the authors provide no experimental results for the applications of i3 most discussed in the paper: multicast, anycast, mobility. The paper goes at length to describe how i3 eases multicast, but does not provide evidence about i3’s efficiency when dealing with these. Additionally, it is my understanding that i3 would make unicast quite slow, so it would not be a suitable replacement for existing network infrastructue.

Future research: it would be interesting to implement a hybrid approach where packets are not required to go through an i3 node. Also implement i3 servers as modified switches. That is, modify a network switch to work with i3 triggers and identifiers instead of IP packets. If a switch can be made like this, a lot of the overhead from processing the triggers in software is taken away.

Internet Indirection Infrastructure April 16, 2009

Single overlay capable of achieving multiple communication services over a P2P network
The paper comes up with a single infrastructure capable of supporting several services such as multicast, broadcast, anycast, mobility etc over the Internet architecture with was built to be P2P. It achieves this by introducing a level of indirection in the form of nodes that act as i3 servers. Senders direct outgoing messages to identifiers instead of a particular destination node address. Receiving nodes can then subscribe to these identifiers if they wish to the message. Hence, more than one receiver can subscribe to an identifier, thereby allowing for the above mentioned services to be achieved over a P2P network. This method suggested by them provides for a lot of flexibility in the terms of the types of services that can be provided, nodes that can add or drop themselves to a service, etc. Other than providing for these services, their structure achieves security (in some aspects, while giving rise to different set of security concerns that they consider in detail and provide methods to counteract) which couldn’t have been achieved in a P2P system.

Methods to add new nodes, handle failure of old ones and provide efficient routing
In addition to suggesting the basic infrastructure, the paper also talks of efficient methods implementation of the idea. The first question that comes to mind when the i3 structure is suggested is, the overhead it would add. The paper provides for a method of packet forwarding that seems to add minimal overhead. In the method suggested, the senders cache the address of the server that is responsible for routing packets to the identifier the sender wishes to send packets to. This reduces the time to find the server for subsequent sends. The receivers reduce the time to receive packets from the servers by choosing servers close to themselves. Similarly, the paper also suggests efficient methods to deal with node failures, node additions and packet forwarding.

Methods to handle security threats
The nature of how the i3 system works exposes it to several security threads. The paper makes a detailed analysis of all possible threats and suggests methods to counteract them.

PROBLEMS

The paper claims that it handles the triangle problem by getting the receiving nodes to choose a server close to themselves to store the trigger containing their id. However, this solution only works if the system has a large number of i3 servers. If there exist only a few servers for a large number of nodes, it is likely that two nodes, adjacent to one another, might have to communicate with a far away server node to be able to reach one another.

Several of the methods they suggest to handle the issue of security work by inhibiting free and flexible use of i3 by the servers. For eg, one of the methods limit the number of triggers a node can have. Also, the innate structure of i3 introduces far too many means of intrusion to be able to detect and counter every one of them.

In spite of several methods to reduce overhead, the structure still introduces them at various stages and steps. There is the overhead introduced by in the security methods suggested, enabling caching by the appropriate server sending out the, “it is me you want to send future messages to” message, etc.

FUTURE WORK

It seems like i3 would provide a workable and efficient platform for a network of rapidly moving nodes. it seems to have the mechanisms in place to provide support for such a system. Work could be done to explore possibilities in the area.

Internet Indirection Infrastructure April 16, 2009

i)

1. There are many applications that implement their own versions of multicast, anycast, or address mobility since trying to deploy a level 3 protocol to solve these is infeasible. Building up a generic infrastructure that can service any of these types of services would be a much better solution. The author propose a generic, incrementally deployable solution to this problem by adding servers that use their own specialized level 7 protocol.

2. Decoupling the act of sending and receiving allows for a very generic design than can support any type of packet routing that is currently used. The authors introduce the idea of using a publish/subscribe type framework where senders can send a packet with and id# and anyone interested in receiving that packet can do so by adding a trigger to indicate they want to receive the packet.

3. The ability to quickly route a packet to the server that has a longest matching trigger is important since it greatly impacts the efficiency of the system. The authors use the  chord lookup protocol to allow them to route packets to the correct server in O(log # of servers) hops.

ii) While the authors did address security of the end users, I felt they failed to adequetly address the security of the actual infrastructure. For instance an attacker could mount a denial of service attack on i3 (i.e. disrupt i3 so anyone trying to use i3 can’t) by creating a large number of i3 servers on perhaps a small number of physical machines by using virtualization. The attacker will then be responsible for a large portion of the id space and they can correctly reply to requests to register triggers or send a packet to an id, but refuse to actually send the packet to end users who have registered a trigger for that id.

iii) A clear area of future research would be into the feasibility of deploying such a system. This would require gauging peoples interest of having such a system and determining the best economic model for deployment (i.e. single provider, multi-provider, for profit, not for profit).

Internet Indirection Infrastructure April 16, 2009

In this paper the authors present a single new overlay network that serves as a general purpose Internet Indirection Infrastructure (i3) based on rendezvous. This network would expand functionalities offered by the IP network without requiring a widespread consensus and commitment from the network community. The two main entities are the sender and the receiver that locate each other through i3 nodes. The senders sends into the i3 network a packet (id, data), where id is an identifier of the communication/service/flow that the sender is providing. At every point in time, in the i3 network there is only one i3 node that is responsible to manage that particular id. On the other side, the receiver registers itself at the i3 node responsible for the specific id the receiver is interested in receiving. From that moment on, the i3 node forwards all the incoming packets with that specific id to all the registered receivers.
The three most important features of this approach are:
1. Modularity & scalability. The new layer can be created in an incremental way, starting with even only one i3 node. It does not require any particular modification to the existing Internet protocol nor infrastructure. The i3 nodes can be pc-based and they communicate through IP. The required number of i3 nodes depends only on the traffic that this new network has to manage and on the locality of the users. The fact that it is so modular can potentially be a key success factor for this approach since it does not require a huge investment to start.
2. Adds functionalities to already existing services. The i3 network allows multicast, anycast etc, combining them with also mobility. A receiver can move from a network to another one and in order to remain connected it has only to send another trigger packet to register itself with the new location. This can be easily be implemented in a seamless way for the application and hence for the user. I3 network can also add security to the communication with the use of public and private triggers that allow the i3 node and the end-host to exchange their private ids.
3. Dynamic service composition & Heterogeneous multicast. A receiver can specify that the data that it wants to receive must be first processed by another server (in the paper there is the example of the H.263 transcoder). This chain of execution/elaboration can be built dynamically by the receiver by sending different triggers to the i3 node. In the same way, a intermediate processing node can exploit the capabilities of another server by forwarding the data to it in a completely transparent way for the receiver. Heterogeneous multicast instead allows the same flow of data to the elaborated in different ways by adding different triggers for a particular id.

Potential problems:
Security. Even if the authors try to address this part in section 4.10, their solution does not sound very strong to me. In particular they address all the security related problems with the use of private triggers. While they can potentially work, they could also add a lot of overhead and complexity to the system, as well as modifying the real nature of the multicast idea.

Possible future research:
The authors do not compare the performance of their implementation with already existing technologies. That would definitely be an interesting avenue of research, also to prove the quality of the i3 infrastructure. Another branch of research could be to try to quantify their proposed solutions to the security related problems.

Internet Indirection Infrastructure April 16, 2009

The authors introduce a design for separating network senders from receivers by introducing a layer of indirection. The system is called i3. The basic structure involves receivers registering a trigger containing an id and the receiver’s address which signals willingness to receive data labeled with the id. Correspondingly, senders send data with an id. The i3 system ensures that data sent with an id is routed to receivers interested in data with that id. The decoupling is intended to improve connectivity in the face of end host mobility as well as provide scalable multicast and anycast solutions.

The greatest contribution is the idea of decoupling the sender from the receiver. This is also the source of the greatest hit to performance, as will be discussed later. Because the sender does not know who will be receiving its transmissions, it is free to simply publish the data however is easiest. The infrastructure can handle routing the data to the appropriate hosts, whether there exists just one or multiple hosts.

Another feature of the i3 design is that it allows ids to be composite ordered stacks. This means that an end host can express a route that the data should take before being delivered. This feature can be used to compose services, such as transforming data into a specific format before being received by the end host. By allowing this kind of id based routing, end hosts can push processing into the network instead of orchestrating such compositions directly (as might be done in a traditional IP network). Of course this freedom is not without consequences. Being able to direct a route is a powerful feature and can cause problems with efficiency and loops if not used carefully.

The authors take steps to avoid the obvious misuses of this type of design. Security and robustness are directly addressed with seemingly adequate solutions. Although they also implement numerous optimizations to achieve low overhead and low latency, they are ultimately tied to the extra processing and hops necessitated by the level of indirection. The simulations in the paper show that at best, packet latency is twice as long as direct IP delivery — and this is after caching addresses and sampling servers to find the closest intermediary. Interestingly, one of the example applications proposed in the paper is transmission of MPEG data that is distributed to multiple end hosts. One of the hosts makes use of i3 composition to transcode the MPEG data into H.264 data en route. Clearly, this was not meant to be an example of a realtime video stream.

Despite the glaringly high latency issues, I find the approach to be interesting and possibly useful in specialized environments. It’s not clear how i3 can be used on the Internet, in practice, however. Further exploration into specific applications where mobility is an extremely common and problematic issue might yield enough demand to consider using i3.

Internet Indirection Infrastructure April 16, 2009

This paper was about I3, a proposed rendezvous-based packet delivery system that would overlay the current Internet. The authors hope that this method will provide greater flexibility than the IP based system in current use can provide. The three main points of this paper were:

1. I3 decouples the sender from the receiver by creating a two part packet, an ID and a Payload, that is transmitted by the sender without any knowledge of the recipients. The nodes wishing to receive the packets, express interest in that particular ID and receive it without speaking to the sender node directly. This provides for greater flexibility in the way that packets are handled by the network.

2. The decoupled nature of such a network provides robustness, scalability, efficiency, stability and incremental deployability. The designers of this system are familiar with the modern Internet and have planned for challenges in a way that the original creators could not have imagined. This gives them a considerable advantage in that not only do they know the challenges associated with designing such a protocol, they are also familiar with the growth trends that we likely must plan for in order for the protocol to be acceptable for a long time into the future.

3. This type of network mitigates some security concerns common in todays Internet but introduces several new ones. This solution is not necessarily designed to be a more secure network, but one that provides for greater flexibility in packet delivery and an alternative to the IP based system that we now use. The authors do a good job of pointing out the security concerns and make no claims to be completely secure.

The most glaring weakness that I saw with this paper was that while the authors did show a solid proof of concept for a different method of packet delivery, I do not know that I am convinced that this kind of network would be able to withstand the amount of traffic present on todays Internet with the performance that people are used to receiving. While they do do a solid performance evaluation, I was still left with some questions about its potential due to the small size of the implemented network and the controlled nature of the experiments.

The research in this paper is in the same vein as the active network, a new way of dealing with packets. This is an ongoing research project and one that is likely to continue for some time as few people believe that our current Internet structure is perfect and strive to find a more effective alternative. Also, further research into performance optimization and security should greatly improve the chances of a protocol such as this being adopted by the mainstream public.

Assignment 1 Submission Instructions April 14, 2009

Assignment 1 is due by 5 pm on Thursday, April 16th.  Place your code and makefile and README in a directory labeled A-B where A and B are the last names of the two people in your group.  Use tar to create a file A-B.tar.gz and email it to barath@cs.ucsd.edu.  Your makefile should generate a binary named “server” and upon execution the server should take the listening port number as an option.  Your README should contain a brief description of what you implemented, how you implemented it, and what problems there were (or still are).  Your assignment will be evaluated under Linux (2.6.21-rc6 i686 Intel(R) Pentium(R) 4 CPU 2.80GHz with GCC/G++ version 3.4.6).

The grading checklist that will be used to evaluate your submission is here.  Take a look and feel free to share test cases, questions, and answers in the comments section of this post.

Active network vision and reality: lessons from a capsule-based system April 14, 2009

Salient points:

This paper packages the idea of Active Networks in a way that’s different from the then existing line of thought. The following are the salient points:

1. Active networks are not impractical, and can be built incrementally: This perhaps best describes the author’s message. His ideology has been to introduce processing along the route of a packet. He goes on to demonstrate that the capsule-based active network performs reasonably well, when compared to static routing in software. A real system ANTS has been built to reassure the critics of active network of its feasibility. Also, the active network can co-exist with the regular IP-network.
2. Concept of capsules: These special packets introduce the element of processing in the active nodes along the network path. Capsule processing helps to ease the burden of point-wise updates from the network administrators, by dynamically changing the forwarding entries at active nodes based on the factors such as the current load on that route.
3. Security aspects: Security of network carrying mobile code has often been cited as one of the challenges for active networks to gain acceptability in the Internet of today. The ANTS system allows any untrusted user to customize the network based on his requirements, but without compromising on security. This is achieved by the sandbox model of execution provided by the Java Virtual Machine. The system also relies on certification of capsule code by a trusted authority.

Potential problems:

One problem I see is that the overhead incurred because of the additional security mechanisms (be it certification of the capsule code by an authority, or the use of sandbox approach provided by JVM) could potentially increase when this is to be deployed on a large scale. The author does mention this, but claims that proof carrying code could solve the problem. He does not substantiate wih results. Also, we need to keep in mind the extra traffic introduced by capsules.

Future:

The asymmetry introduced among the network nodes due to the presence of active nodes requires us to design a different routing algorithm. More research can be on optimizing the routes so that each flow has to pass through a minimum number of active nodes in its lifetime. Also, we need to validate whether passing code by reference will hold advantage over passing by value.

Active network vision and reality: lessons from a capsule-based system April 14, 2009

Important:

Current router technology requires that router vendors implement new networking protocols before they can be deployed in a production environment. Routers must be taken out of service while their software is upgraded. Active networks provides a facility for the deployment of after-market routing technology. Deployed active network routers can distribute and interpret new router software dynamically.

Capsule-based active network technology allows deployment of new software over an operating network in an incremental fashion. The new software can be the result of local devlopment or purchased from a software vendor. Incremental deployment allows new router software to be tested in a limited deployment before it is installed globally. Deployment of new software does not require taking routers offline for a software upgrade, as is required by current routers.

Problem:

Software based routers are quickly being replaced with hardware routers. Software based routers are too slow to keep up with the latest broadband networks. Operational high speed networks are based on hardware router technology.

Future:

Active network technology can be used in network testbeds for the evaluation of new network technologies.

Wireless networks tend to lag behind wired networks in speed and active networking technology may be appropriate in a wireless environment where speed is not a limitation. Low speed networks have to most to gain from improved routing capabilities and the ability to easily deploy the latest technology to remote routers has promise.

Active Network Vision and Reality: Lessons from a Capsule-based System April 14, 2009

The paper offers interesting insight into a technique for experimenting with new networking services/protocols using active networks. An active network is one where custom user code can be executed on each router or node through which the packet passes in order to make forwarding decisions etc. The authors describe their experiences and learning from designing and implementing the ANTS toolkit which is their model for programming/introducing new services on the active networks.

One of the primary contributions of their work is the formalization of how user code should be distributed to the routers/active nodes. The authors describe the value in passing around references to the code in each packet rather than the code itself and then distributing the code to the active node on demand and caching it locally. This reduces the overhead of distributing the custom user code to the active nodes. The notion of capsules encapsulated in IP packets is an interesting technique.

The second important contribution is the notion of protection that they achieve. The vision for active networks is to allow all users to customize processing of their traffic in the network. The authors describe how they try to achieve this goal but targeting robustness rather than fairness and by having a restrictive API with several clear constraints on the programming model itself. This has a lot of similarities to an operating system that wishes to offer time-shared services to a set of applications. The applications must be protected and isolated from each other while at the same time, the operating system needs to protect itself from the applications.

Another important contribution of their work is their recognition of the fact that active networks offer a suitable model for the internet to evolve incrementally. Some nodes in the network might be active nodes while other nodes might just be simple IP routers, so the services that can be implemented by this ‘hybrid’ network should not require each node to be an active node. Both active nodes and regular IP routers would coexist while active nodes might be incrementally deployed.

One of the points against the paper is that the techniques seem useful for experimentation, but the lower performance of software based routing would still be challenge to widespread deployment and use in the internet. If the purpose of the idea is experimentation with new services and techniques, it would not offer sufficient incentive for everyone to deploy active nodes considering the relative small fraction of researchers who would use the active networks relative to the large number of internet users.

From a research perspective, it would be useful to explore what are the kind of experimental services that can be built over active networks. Also, the notion of capsules in the active network model allows the source of traffic to indicate the processing that it wishes to have in the network. However it does not offer control to the receiver of the traffic. Extending the idea to provide control to the receiver or having a complementary protocol that can offer control to receivers would widely expand the sort of services and network protocols that can be experiemented with.