This paper studies the problem of compressing the forwarding information base (FIB), but taking a wider perspective. Indeed, FIB compression goes beyond sheer compression, as the gain in memory use obtained from the compression has consequences on the updates that will have to be applied to the compressed FIB. We are interested in the situation where forwarding rules can change over time, e.g., due to border gateway protocol (BGP) route updates. Accordingly, we frame FIB compression as an online problem and design competitive online algorithms to solve it. In contrast to prior work which mostly focused on static optimizations, we study an online variant of the problem where routes can change over time and where the number of updates to the FIB is taken into account explicitly. The reason to consider this version of the problem is that leveraging temporal locality while accounting for the number of FIB updates helps to keep routers CPU load low and reduces the number of FIB updates to be transferred, e.g., from the network-attached software-defined network controller to a remote switch. This paper introduces a formal model which is an interesting generalization of several classic online aggregation problems. Our main contribution is an O(w)-competitive algorithm, where w is the length of an IP address. We also derive a lower bound which shows that our result is asymptotically optimal within a natural class of algorithms, based on so-called sticks.

Snapshots of the Forwarding Information Base (FIB) in Internet routers can be compressed (or aggregated) to at least half of their original size, as shown by previous studies. However, the permanent stream of updates to the FIB due to routing updates complicates FIB aggregation in practice: keeping a (near-)optimally aggregated FIB in face of these routing updates is algorithmically challenging. A sensible trade-off has to be found between the aggregation gain and the complexity of handling routing updates. This paper investigates whether the spatial and temporal locality properties of routing updates conceal opportunities for improving this trade-off in online FIB aggregation. Our contributions include an empirical study of the locality of updates in public Internet routing data. To facilitate this study, we design the Locality-aware FIB Aggregation (LFA) algorithm. We show, that an algorithm as simple as LFA can effectively leverage the locality of FIB churn to keep low the number of updates to the aggregated FIB, as within time periods of a few seconds or minutes, routing updates affect only a limited number of regions in the FIB.

This paper attends to the well-known problem of compressing the Forwarding Information Base of a router or switch, while preserving a correct forwarding. In contrast to related work, we study an online variant of the problem where BGP routes can change over time, and where the number of updates to the FIB are taken into account explicitly. Minimizing the number of FIB updates is important, especially when they are sent across the network (e.g., from the network-attached SDN controller). This paper pursues a competitive analysis approach and introduces a formal model which is an interesting generalization of several classic online aggregation problems. The main contribution is a O (w)-competitive algorithm, where w is the length of an IP address. We also derive a lower bound which shows that our result is asymptotically optimal within a natural class of algorithms.

Recent Internet studies have reported on continued traffic growth and popularity of web-based applications. Any adverse impact that these observed trends may have on Internet traffic flows can result in sub par performance, which in turn results in unsatisfactory user experience. Leveraging data collected at a major content distribution network (CDN), we investigate flow-level performance in the wild. We observe that packet losses differ widely across flows of different sizes, and even for flows of similar size. To shed light on these observations, we rely on a controlled testbed setup with advanced instrumentation via NetFPGA cards. We highlight the key factors which can degrade flow-performance across different network loads and flow-size distributions. We find that packet losses do not affect all flows similarly. Depending on the network load, some flows either suffer from significantly more drops (unhappy flows) or significantly less drops than the average loss rate (happy flows). Very few flows actually observe a loss rate similar to the average loss rate. Therefore, any single flow is very unlikely to observe the global packet loss process. Furthermore, we find that some flows are burstier than others as indicated by their average congestion window.

The largest IXPs carry on a daily basis traffic volumes in the petabyte range, similar to what some of the largest global ISPs reportedly handle. This little-known fact is due to a few hundreds of member ASes exchanging traffic with one another over the IXP's infrastructure. This paper reports on a first-of-its-kind and in-depth analysis of one of the largest IXPs worldwide based on nine months' worth of sFlow records collected at that IXP in 2011.

The evolution of wireless network standards, e.g., GSM/GPRS, UMTS, WiFi, WiMAX, and end-user devices has paved the way towards Next Generation Mobile Networks (NGMN), where users are always connected through multiple radio access networks. NGMN technologies target to improve the user experience especially for mobile data and multimedia services, which are in line with user expectations evident from, for instance, the increasingly popular mobile HTTP video streaming. To understand the quality that can be offered to the user in NGMNs, we compare the Quality of Experience (QoE) for HTTP streaming in a prototype NGMN testbed with WiFi and 3G UMTS/HSDPA support. We use CUBIC TCP as the transport layer protocol as it is typically the default TCP variant, e.g., in Android phones. We complement the QoE estimations with network QoS parameters such as throughput and delay, and transport layer statistics. The results of our evaluation show that (i) video QoE remains stable in WiFi even for high packet losses compared to UMTS, (ii) QoE in UMTS is sensitive to packet loss even for low loss rates due to high variations in the network QoS, namely, throughput and delay, (iii) the decrease in QoE and QoS in HSDPA is due to its negative interactions with the aggressive congestion control of CUBIC TCP, and (iv) handover from WiFi to HSDPA degrades QoE.