Routing in large-scale computer networks today is built on hop-by-hop routing: packet headers specify the destination address and routers use internal forwarding tables to map addresses to next-hop ports. In this paper we take a new look at the scalability of this paradigm. We define a new model that reduces forwarding tables to sequential strings, which then lend themselves readily to an information-theoretical analysis. Contrary to previous work, our analysis is not of worst-case nature, but gives verifiable and realizable memory requirement characterizations even when subjected to concrete topologies and routing policies. We formulate the optimal address space design problem as the task to set node addresses in order to minimize certain network-wide entropy-related measures. We derive tight space bounds for many well-known graph families and we propose a simple heuristic to find optimal address spaces for general graphs. Our evaluations suggest that in structured graphs, including most practically important network topologies, significant memory savings can be attained by forwarding table compression over our optimized address spaces. According to our knowledge, our work is the first to bridge the gap between computer network scalability and information-theory.

Amongst data center structures, flattened butterfly (FBFly) networks have been shown to outperform their common counterparts such as fat-trees in terms of energy proportionality and cost efficiency. This efficiency is achieved by using less networking equipment (switches, ports, cables) at the expense of increased control plane complexity. In this paper we show that cabling complexity can be further reduced by an order of magnitude, by reconfiguring the optical fully meshed components into optical “pseudo”-fully meshed components. Following established methods, optical star networks are obtained by exchanging the FBFly's regular (grey) optical transceivers for dense wavelength division multiplexing (DWDM or colored) optical transceivers and placing an arrayed waveguide grating router (AWGR) in the center. Depending on the data center configuration and equipment prices, our colored FBFly (C-FBFly) proposal yields lower capital expenditure than the original FBFly. The key advantage of our structural modification of FBFly, however, is that in large FBFly networks (e.g., > 50K nodes) it reduces the number of inter-rack cables by a factor as large as 48.

SDN opens a new chapter in network troubleshooting as besides misconfigurations and firmware/hardware errors, software bugs can occur all over the SDN stack. As an answer to this challenge the networking community developed a wealth of piecemeal SDN troubleshooting tools aiming to track down misconfigurations or bugs of a specific nature (e.g. in a given SDN layer). In this demonstration we present EPOXIDE, an Emacs based modular framework, which can effectively combine existing network and software troubleshooting tools in a single platform and defines a possible way of integrated SDN troubleshooting.

Many networking visioners agree that 5G will be much more than the incremental improvement, in terms of data rate, of 4G. Besides the mobile networks, 5G will fundamentally influence the core infrastructure as well. In our vision the realization of the challenging promises of 5G (e.g. extremely fast, low-overhead, low-delay access of mostly cloudified services and content) will require the massive use of multipathing equipped with low overhead transport solutions tailored to fast, reliable and secure data retrieval from cloud architectures. In this demo we present a prototype architecture supporting such services by making use of automatically configured multipath service chains implementing network coding based transport solutions over off-the-shelf software defined networking (SDN) components.

Today’s ever-growing networks call for routing schemes with sound theoretical scalability guarantees. In this context, a routing scheme is scalable if the amount of memory needed to implement it grows significantly slower than the network size. Unfortunately, theoretical scalability characterizations only exist for shortest path routing, but for general policy routing that current and future networks increasingly rely on, very little understanding is available. In this paper, we attempt to fill this gap. We define a general framework for policy routing, and we study the theoretical scaling properties of three fundamental policy models within this framework. Our most important contributions are the finding that, contrary to shortest path routing, there exist policies that inherently scale well, and a separation between the class of policies that admit compact routing tables and those that do not. Finally, we ask to what extent memory size can be decreased by allowing paths to contain a certain bounded number of policy violations and, surprisingly, we conclude that most unscalable policies remain unscalable under the relaxed model as well.

Large-scale information dissemination in multicast communications has been increasingly attracting attention, be it through uptake in new services or through recent research efforts. In these, the core issues are supporting increased forwarding speed, avoiding state in the forwarding elements, and scaling in terms of the multicast tree size. This paper addresses all these challenges-which are crucial for any scalable multicast scheme to be successful-by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept, we build our Bloom filter by enclosing limited information about the structure of the tree. Analytical investigation is conducted and approximation formulas are provided for optimal-length Bloom filters, in which we got rid of typical Bloom filter illnesses such as false-positive forwarding. These filters can be used in several multicast implementations, which are demonstrated through a prototype. Thorough simulations are conducted to demonstrate the scalability of the proposed Bloom filters compared to its counterparts.

Many of our computer networks, not the least of which the Internet, are built upon hop-by-hop routing. At the moment, it is not clear whether we will be able to scale these networks into the future economically. In this paper, we propose a new information-theoretic model to study routing scalability, we present preliminary analysis suggesting that hop-by-hop routing tolerates network growth surprisingly efficiently, and we sketch the scalability map of the Internet which we then use to make some bold predictions.

Multipath TCP is an experimental transport protocol with remarkable recent past and non-negligible future potential. It has been standardized recently, however the evaluation studies focus only on a limited set of isolated use-cases and a comprehensive analysis or a feasible path of Internet-wide adoption is still missing. This is mostly because in the current networking practice it is unusual to configure multiple paths between the endpoints of a connection. Therefore, conducting and precisely controlling multipath experiments over the real “internet” is a challenging task for some experimenters and impossible for others. In this paper, we invoke SDN technology to make this control possible and exploit large-scale internet testbeds to conduct end-to-end MPTCP experiments. More specifically, we establish a special purpose control and measurement framework on top of two distinct internet testbeds. First, using the OpenFlow support of GÉANT, we build a testbed enabling measurements with real traffic. Second, we design and establish a publicly available large-scale multipath capable measurement framework on top of PlanetLab Europe and show the challenges of such a system. Furthermore, we present measurements results with MPTCP in both testbeds to get insight into its behavior in such not well explored environment.

Mininet is a great prototyping tool which combines existing SDN-related software components (e.g., Open vSwitch, OpenFlow controllers, network namespaces, cgroups) into a framework, which can automatically set up and configure customized OpenFlow testbeds scaling up to hundreds of nodes. Standing on the shoulders of Mininet, we implement a similar prototyping system called ESCAPE, which can be used to develop and test various components of the service chaining architecture. Our framework incorporates Click for implementing Virtual Network Functions (VNF), NETCONF for managing Click-based VNFs and POX for taking care of traffic steering. We also add our extensible Orchestrator module, which can accommodate mapping algorithms from abstract service descriptions to deployed and running service chains.

Multipath TCP is an experimental transport protocol with remarkable recent past and non-negligible future potential. However the lack of available large-scale testbeds and publicly accessible multiple paths grossly prohibits the adoption of the technology. Here, we demonstrate a large-scale multipath playground deployed on PlanetLab Europe, which can be used either by experimenters and researchers to test and verify their multipath-related ideas (e.g. enhancing congestion control, fairness or even the arrangement of multiple paths) and also by early adopters to enhance their Internet connection even if single-homed.

Large-scale information distribution has been increasingly attracting attention, be it through uptake in new services or through recent research efforts in fields like information-centric networking. The core issue to be addressed is the more efficient distribution of information to a large set of receivers. Avoiding state in the forwarding elements is crucial for any scheme to be successful. This paper addresses this challenge by revisiting the idea of in-packet Bloom filters and source routing. As opposed to the traditional in-packet Bloom filter concept which represent the trees flatly as sets, we build our filter by enclosing limited information about the structure of the tree, namely its stage decomposition, which helps to get rid of typical Bloom filter illnesses as infinite loops and false positive forwarding. Our analytical and simulation results show that by using this information we obtain more succinct tree representation while still maintaining forwarding efficiency.

No abstract available.

The limited capabilities of the switches renders the implementation of unorthodox routing and forwarding mechanisms as a hard task in OpenFlow. Our high level goal is therefore to inspect the possibilities of slightly smartening up the OpenFlow switches. As a first step in this direction we demonstrate (with Bloom filters, greedy routing and network coding) that a very limited computational capability enables us to natively support experimental technologies while preserving performance. We distribute the demos in source files and as a ready-to-experiment VM image to promote further improvements and evaluations.

Power management is a critical issue for mobile devices, where a significant portion of the total system energy can be often consumed by heavy wireless network activity. In this paper we present a framework that reduces the energy consumption of wireless mobile devices during streaming video content over Wireless LAN networks by utilizing the power saving mechanisms defined in the IEEE 802.11e standard. The framework allows video applications to directly optimize the overall energy efficiency by controlling the sleep cycles of wireless network adapters based on video QoE. The framework employs a simple QoE estimation algorithm that estimates the user level video quality, and adjusts the sleep intervals of the wireless adapter to maintain video quality while maximizing power efficiency. As an important part of our paper the building and configuration steps of a working testbed system is carefully described, which demonstrates the availability and efficiency of the U-APSD power saving technology at hand. A preliminary evaluation of the proposed framework supports that by enabling the WMM Power Saving feature 20-30% of total system energy can be saved even in case of asynchronous video traffic.

This paper takes a first step towards generalizing compact routing to arbitrary routing policies that favor a broader set of path attributes beyond path length. Using the formalism of routing algebras we identify the algebraic requirements for a routing policy to be realizable with sublinear size routing tables and we show that a wealth of practical policies can be classified by our results. By generalizing the notion of stretch, we also discover the algebraic validity of compact routing schemes considered so far and we show that there are routing policies for which one cannot expect sublinear scaling even if permitting arbitrary constant stretch.

Research works concerning AS (Autonomous Systems) level Internet topology measurements typically aim at obtaining near-complete maps of the AS structure. In this paper, we take a fundamentally different approach by inspecting several concurrently visible local views of the AS graph stored at individual BGP route servers. We find that each of these views exhibits the characteristic properties of complex graphs having power-law degree distribution, large clustering coefficient and the small world property. As a main contribution, the intersection of these views is investigated to identify the skeleton of the Internet consisting of edges seen by most of the ASes. Our measurements support the surprising claim that this skeleton is a scale-free complex network, having a giant connected component with a dense part in its heart forming the critical AS level core. We identify the edges in the skeleton as critical infrastructure, any changes of which induces an Internet-wide effect with BGP updates propagating to all ASes. Finally, we reinterpret the path inflation metric using the local view approach and show that local path inflation can be very diverse in different ASes.

Network calculus is the result of recent developments in the area of network analysis, providing considerable insight into the behavior of (packet-based) communication networks. The classical approach uses deterministic bounds to describe systems having stochastic properties in nature, offering simple formulation to a set of-otherwise analytically hardly tractable-problems. Eliminating probabilistic nature, however, often leads to-practically hardly usable-loose bounds after quantification. In this paper, we address the problem of extending the network calculus theory to regain the advantage coming from the statistical multiplexing effect, preserving at the same time easy discussion that the original approach provides us. During the main part of the paper we introduce and discuss some important theorems about the novel effective w-arrival and w-service curves. As an example we show how to apply the results to the efficient computation of the workload loss ratio, as an important and widely used quality of service parameter while remaining in the framework and concept of the network calculus.

The estimation of resource usage in network nodes is a basic issue from the point of QoS (quality of service) provisioning. The estimation of the buffer overflow is considered in network elements represented by a service curve property. Existing results (Vojnovic, M. and Le Boudec, J.-Y., IEEE Trans. Commun., 2002; Gulya/spl acute/s, A. et al., IEEE GLOBECOM, 2004), define bounds on buffer overflow for such elements, multiplexing homogeneous and heterogeneous independent regulated inputs. The requirement of independence for the inputs can be reduced by setting up new bounds for the homogeneous case, using a bounding technique which relies only on the limited independence among the inputs (Siegel, A. et al., ACM-SIAM Symp. Discrete Algms, 1993). Beside the presentation of the new bounds, it is shown that they improve existing ones in all cases, and an investigation is given about the independence properties which are required from the input flows.

The estimation of resource usage in network nodes is a basic issue from the point of QoS (quality of service) provisioning. This paper is about estimating the buffer overflow within network elements, which are represented by a service curve property. There are some previous investigations which define bounds on buffer overflow for such elements, multiplexing homogeneous and heterogeneous independent regulated inputs. The main topic of this paper is setting up new bounds for the heterogeneous case, by using a new PGF (probability generating function) approximation presented in (J. Biro et al, Proc. of 1st Int. Work. Conf. on Performance Modelling and Eval. of Heterogeneous Networks, 2003). We show, that the new bounds are also valid for the homogeneous case, so the results for the homogeneous and the heterogeneous case can be integrated into a single formula. It is also shown, that the new bounds improve the existing ones in most cases.

In this paper we set up a family of conservative upper bounds for QoS measures applicable in QoS guaranteed packet-based communication networks. The bounds are distribution free that is they depend only on the number of traffic sources, the peak rates of the flows and the mean arrival intensity of the aggregated traffic stream. No other information on the traffic distribution is required. The bounds have been developed under the well known bufferless fluid flow multiplexing (bffm) modeling framework, nevertheless, an important property is also discussed in the paper, namely they can also be applicable to the buffered statistical multiplexer case when the input flows are regulated. The performances of the bounds are analyzed and comparative numerical investigations are also presented in both multiplexing models.