Search

Recent technological advances in commodity server architectures, with multiple multi-core CPUs, integrated memory controllers, high-speed interconnects and enhanced network interface cards, provide substantial computational capacity and thus an attractive platform for packet forwarding. However, to exploit this available capacity, we need a suitable software platform that allows effective parallel packet processing and resource management. In this paper, we at first introduce an improved forwarding architecture for software routers that enhances parallelism by exploiting hardware classification and multi-queue support, already available in recent commodity network interface cards. After evaluating the original scheduling algorithm of the widely-used Click modular router, we propose solutions for extending this scheduler for improved fairness, throughput and more precise resource management. To illustrate the potential benefits of our proposal, we implement and evaluate a few key elements of our overall design.

In this paper, we evaluate the performance of a software IP router forwarding plane inside the Xen virtual machine monitor environment with a view to identifying (some) design issues in Virtual Routers. To this end, we evaluate and compare the forwarding performance of two identical Linux software router configurations, run either above the Xen hypervisor or within vanilla Linux. Even with minimal sized packets, we show that the Xen DomO privileged domain offers near native forwarding performance at the condition that the sollicitation to unpriviledged domains stay minimal, whereas Xen unprivileged domains offer very poor performance in every cases. This shows that an important design principle for virtual router platforms must be to handle all forwarding, for all virtual routers, onto the same forwarding engine, in order to avoid much detrimental per-packet context switching.

The 802.11 encryption standard Wired Equivalent Privacy (WEP) is still widely used today despite the numerous discussions on its insecurity. In this paper, we present a novel vulnerability which allows an attacker to send arbitrary data on a WEP network after having eavesdropped a single data packet. Furthermore, we present techniques for real-time decryption of data packets, which may be used under common circumstances. Vendor produced mitigation techniques which cause frequent WEP re-keying prevent traditional attacks, whereas our attack remains effective even in such scenarios. We implemented a fully automatic version of this attack which demonstrates its practicality and feasibility in real networks. As even rapidly re-keyed networks can be quickly compromised, we believe WEP must now be abandoned rather than patched yet again.

Publish-subscribe is a powerful paradigm for distributed communication based on decoupled producers and consumers of information. Its event-driven nature makes it very appealing for large-scale data dissemination infrastructures. Various architectures were proposed in recent years that provide very diverse features. However, there are few well-defined metrics in the publish-subscribe area that would allow their evaluation and comparison. In this paper, we provide a broad overview of relevant quality-of-service metrics and describe their specific meaning in the context of distributed and decentralized publish-subscribe systems. Our goal is to provide a common base for future evaluations of emerging systems and for the design of qualityof- service aware publish-subscribe infrastructures.

A number of large-scale distributed Internet applications could potentially benefit from some level of knowledge about the relative proximity between its participating host nodes. For example, the performance of large overlay networks could be improved if the application-level connectivity between the nodes in these networks is congruent with the underlying IP-level topology. Similarly, in the case of replicated Web content, client nodes could use topological information in selecting one of multiple available servers. For such applications, one need not find the optimal solution in order to achieve significant practical benefits. Thus, these applications, and presumably others like them, do not require exact topological information and can instead use sufficiently informative hints about the relative positions of Internet hosts. In this paper, we present a binning scheme whereby nodes partition themselves into bins such that nodes that fall within a given bin are relatively close to one another in terms of network latency. Our binning strategy is simple (requiring minimal support from any measurement infrastructure), scalable (requiring no form of global knowledge, each node only needs knowledge of a small number of well-known landmark nodes) and completely distributed (requiring no communication or cooperation between the nodes being binned). We apply this binning strategy to the two applications mentioned above: overlay network construction and server selection. We test our binning strategy and its application using simulation and Internet measurement traces. Our results indicate that the performance of these applications can be significantly improved by even the rather coarse-grained knowledge of topology offered by our binning scheme.

It has been claimed that multicast state cannot be aggregated. In this paper, we will debunk this myth and present a simple technique that can be used to aggregate multicast forwarding state. In particular, we present an interface-centric data structure model which allows aggregation of ranges of multicast addresses in the forwarding table. Understanding the limits of possible aggregation is critical to our knowledge of how IP multicast will scale as it becomes widely deployed. We show through analysis and simulation that some aggregation is possible, even under purely random address allocation and purely random group membership distribution. We further show how other methods of allocation can significantly improve the ability to aggregate, and how non-random distributions of membership can affect aggregation both positively and negatively.

End-to-end congestion control mechanisms have been critical to the robustness and stability of the Internet. Most of today's Internet traffic is TCP, and we expect this to remain so in the future. Thus, having "TCP-friendly" behavior is crucial for new applications. However, the emergence of non-congestion-controlled realtime applications threatens unfairness to competing TCP traffic and possible congestion collapse. We present an end-to-end TCP-friendly rate adaptation protocol (RAP), which employs an additive-increase, multiplicative-decrease (AIMD) algorithm. It is well suited for unicast playback of realtime streams and other semi-reliable rate-based applications. Its primary goal is to be fair and TCP-friendly while separating network congestion control from application-level reliability. We evaluate RAP through extensive simulation, and conclude that bandwidth is usually evenly shared between TCP and RAP traffic. Unfairness to TCP traffic is directly determined by how TCP diverges from the AIMD algorithm. Basic RAP behaves in a TCP-friendly fashion in a wide range of likely conditions, but we also devised a fine-grain rate adaptation mechanism to extend this range further. Finally, we show that deploying RED queue management can result in an ideal fairness between TCP and RAP traffic.

Current multicast routing protocols can be classified into three types according to how the multicast tree is established: broadcast and prune (e.g., DVMRP, PIM-DM), membership advertisement (e.g., MO-SPF), and rendezvous-based (e.g., CBT, PIM-SM). Rendezvous-based protocols associate with each logical multicast group address, a physical unicast address, referred to as the 'core' or 'rendezvous point' (RP). Members first join a multicast tree rooted at this rendezvous point in order to receive data packets sent to the group. Rendezvous mechanisms are well suited to large wide-area networks because they distribute group-specific data and membership information only to those routers that are on the multicast distribution tree. However, rendezvous protocols require a bootstrap mechanism to map each logical multicast address to its current physical rendezvous point address. The bootstrap mechanism must adapt to network and router failures but should minimize unnecessary changes in the group-to-RP mapping. In addition, the bootstrap mechanism should be transparent to the hosts. This paper describes and analyzes the bootstrap mechanism developed for PIM-SM. The mechanism employs an algorithmic mapping of multicast group to rendezvous point address, based on a set of available RPs distributed throughout a multicast domain. The primary evaluation measures are convergence time, message distribution overhead, balanced assignment of groups to RPs, and host impact. The mechanism as a whole, and the design lessons in particular, are applicable to other rendezvous-based multicast routing protocols as well.