Real-time Communications (RTC) services, including multiparty conferencing, live streaming, and cloud-gaming, rely on a large-scale media plane infrastructure that provides real-time audio/video processing to clients. Unfortunately, offthe- shelf RTC services are not elastically scalable. As a result, operators must provision media servers to meet peak demand, resulting in resource under-utilization and high cost. Given that today microservice orchestrators like Kubernetes allow web-services to scale transparently and econimically, this paper looks at applying the same approach to scale large-scale RTC services. We find that this is challenging for two reasons: (a) the default network dataplane underlying Kubernetes does not meet the compelling traffic management, performance and real-time requirements of RTC; and (b) current autoscaling policies are ill-suited to RTC. We address these challenges by designing a RTC-specific service mesh that pushes media traffic processing into the OS kernel and designing new RTC-specific Kubernetes autoscaling policies. Our evaluation on a functional VoIP test-bed shows that this combination allows to deploy elatically scalable RTC services with 100× lower-jitter and 700× lower RTT than the current state-of-the art.

Novel telecommunication systems build on a cloudified architecture running softwarized network services as disaggregated virtual network functions (VNFs) on commercial off-the-shelf (COTS) hardware to improve costs and flexibility. Given the stringent processing deadlines of modern applications, these systems are critically dependent on a closed-loop control algorithm to orchestrate the execution of the disaggregated components. At the moment, however, the formal model for implementing such real-time control loops is mostly missing. In this paper, we introduce a new real-time VNF execution environment that runs entirely on COTS hardware. First, we define a comprehensive formal model that enables us to reason about packet processing delays across disaggregated VNF processing chains analytically. Then we integrate the model into a gradient-optimization control algorithm to provide optimal scheduling for real-time infocommunication services in a programmable way. We present experimental evidence that our model gives a proper delay estimation on a real software switch. We evaluate our control algorithm on multiple representative use cases using a software switch simulator. Our results show the algorithm drives the system to a real-time capable state in just a few control periods even in case of complex services.

State-of-the-art approaches to design, develop and optimize software packet-processing programs are based on static compilation: the compiler’s input is a description of the forwarding plane semantics and the output is a binary that can accommodate any control plane configuration or input traffic. In this paper, we demonstrate that tracking control plane actions and packet-level traffic dynamics at run time opens up new opportunities for code specialization. We present Morpheus, a system working alongside static compilers that continuously optimizes the targeted networking code. We introduce a number of new techniques, from static code analysis to adaptive code instrumentation, and we implement a toolbox of domain specific optimizations that are not restricted to a specific data plane framework or programming language. We apply Morpheus to several systems, from eBPF and DPDK programs including Katran, Meta’s production-grade load balancer to container orchestration solutions such a Kubernets. We compare Morpheus to state-of-the-art optimization frameworks and show that it can bring up to 2x throughput improvement, while halving the 99th percentile latency.

P4 is a widely used Domain-specific Language for Programmable Data Planes. A critical step in P4 compilation is finding a feasible and efficient mapping of the high-level P4 source code constructs to the physical resources exposed by the underlying hardware, while meeting data and control flow dependencies in the program. In this paper, we take a new look at the algorithmic aspects of this problem, with the motivation to understand the fundamental theoretical limits and obtain better P4 pipeline embeddings, and to speed up practical P4 compilation times for RMT and dRMT target architectures. We report mixed results: we find that P4 compilation is computationally hard even in a severely relaxed formulation, and there is no polynomial-time approximation of arbitrary precision (unless$\mathcal {P}$=$\mathcal {N}$$\mathcal {P}$), while the good news is that, despite its inherent complexity, P4 compilation is approximable in linear time with a small constant bound even for the most complex, nearly real-life models.

We introduce self-adjusting partially ordered lists, a generalization of self-adjusting lists where additionally there may be constraints for the relative order of some nodes in the list. The lists self-adjust to improve performance while serving input sequences exhibiting favorable properties, such as locality of reference, but the constraints must be respected.We design a deterministic adjusting algorithm that operates without any assumptions about the input distribution and without maintaining frequency statistics or timestamps. Despite the more general model, we show that our deterministic algorithm performs closely to optimum (it is 4-competitive). In addition, we design a family of randomized algorithms with improved competitive ratios, handling also a more general rearrangement cost model, scaled by an arbitrary constant d ≥1. Moreover, we observe that different constraints influence the competitiveness of online algorithms, and we shed light on this aspect with a lower bound.We investigate the applicability of our self-adjusting lists in the context of network packet classification. Our evaluations show that our classifier performs similarly to a static list for low-locality traffic, but significantly outperforms Efficuts (by factor 7x), CutSplit (3.6x) and the static list (14x) for high locality and small rulesets.

State-of-the-art approaches to design, develop and optimize software packet-processing programs are based on static compilation: the compiler's input is a description of the forwarding plane semantics and the output is a binary that can accommodate any control plane configuration or input traffic.

Caching is at the core of most modern communication systems, where caches are used to store content and traffic classification rules. While network components can leverage caching in a cooperative manner, one important aspect of such systems concerns possible dependencies among stored items. A major use case of such dependencies appears in rule placement across software-defined networks (SDNs). Despite the tremendous success of SDNs in datacenters, their wide adoption still poses a key challenge: the packet-forwarding rules in switches require fast and power-hungry memories. Rule tables, which serve as caches, are of limited size in cheap and energy-constrained devices, motivating novel solutions to achieve high hit rates. We leverage device connectivity in the fast data plane, where delays are in the order of few milliseconds, and propose multiple switches to work together to avoid accessing the control plane, where delays are orders of magnitude greater. As a low priority rule in a cache entails caching higher priority rules, we pose the problem of cooperative caching with dependencies. We provide models and algorithms accounting for dependencies among rules implied by existing switch memory types, andlay the foundations of cooperative caching with dependencies.

Software-Defined Networking (SDN) offers a new way to operate, manage, and deploy communication networks and to overcome many long-standing problems of legacy networking. However, widespread SDN adoption has not occurred yet due to the lack of a viable incremental deployment path and the relatively immature present state of SDN-capable devices on the market. While continuously evolving software switches may alleviate the operational issues of commercial hardware-based SDN offerings, namely lagging standards-compliance, performance regressions, and poor scaling, they fail to match the cost-efficiency and port density. In this paper, we propose HARMLESS, a new SDN switch design that seamlessly adds SDN capability to legacy network gear, by emulating the OpenFlow switch OS in a separate software switch component. This way, HARMLESS enables a quick and easy leap into SDN, combining the rapid innovation and upgrade cycles of software switches with the port density and cost-efficiency of hardware-based appliances into a fully dataplane-transparent and vendor-neutral solution. HARMLESS incurs an order of magnitude smaller initial expenditure for an SDN deployment than existing turnkey vendor SDN solutions while, at the same time, yields matching, or even better, data plane performance for smaller enterprises.

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.

While the industry is still struggling to embrace the network function virtualization paradigm, recently a novel approach has appeared with the promise of improving the state-of-the-art: stateless virtualized network functions. Rooted in cloud-native computing, this design outsources the state embedded in virtual network functions to a dedicated "state storage" layer, facilitating elastic scaling and resiliency. While related work mostly focuses on performance, we in this paper pinpoint all other factors that weigh in when it comes to deploying the stateless design in a carrier-grade operator network. Among those we argue that reliability and flexibility are key, and we propose a system design that can be adapted to any telco use case without the need for complex coordination among the network control, the stateless network functions, and the state storage backend. Then, in extensive evaluations on synthetic use cases we show that the additional flexibility provided by our design does not come at a performance penalty; in fact, in certain cases our design outperforms the state-of-the-art significantly. Finally, we present what to our knowledge is the first product-phase realization of the stateless paradigm, an operational virtualized IP Multimedia Subsystem that can restore the live call records of thousands of mobile subscribers under a couple of seconds with half the resources required by a traditional "stateful" design.

Efficient and highly available packet classification is fundamental for various security primitives. In this paper, we evaluate whether the de facto Tuple Space Search (TSS) packet classification algorithm used in popular software networking stacks such as the Open vSwitch is robust against low-rate denial-of-service attacks. We present the Tuple Space Explosion (TSE) attack that exploits the fundamental space/time complexity of the TSS algorithm.

Packet processing programs may have multiple semantically equivalent representations in terms of the match-action abstraction exposed by the underlying data plane. Some representations may encode the entire packet processing program into one large table allowing packets to be matched in a single lookup, while others may encode the same functionality decomposed into a pipeline of smaller match-action tables, maximizing modularity at the cost of increased lookup latency. In this paper, we provide the first systematic study of match-action program representations in order to assist network programmers in navigating this vast design space. Borrowing from relational database and formal language theory, we define a framework for the equivalent transformation of match-action programs to obtain certain irredundant representations that we call "normal forms". We find that normalization generally improves the capacity of the control plane to program the data-plane and to observe its state, at the same time having negligible, or positive, performance impact.

Nowadays, a majority of the Internet service providers are either piloting or migrating to software-defined networking (SDN) in their networks. In an SDN architecture a central network controller has a top-down view of the network and can directly configure each of their physical switches. It opens up several fundamental unsolved challenges, such as deploying efficient multipath routing that can provide disjoint end-to-end paths, each one satisfying specific operational goals (e.g., shortest possible), without overwhelming the data plane with a prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest (node- or edge-) disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the complexity of the underlying mathematical problem is NP-complete and we present fast heuristic algorithms. By extensive simulations, we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1%-5%), eventually opening the door for wide-scale multipath routing deployments. Finally, we show that even if a primary tree is already given it remains NP-complete to find a minimum length secondary tree concerning this primary tree.

The ongoing network softwarization trend holds the promise to revolutionize network infrastructures by making them more flexible, reconfigurable, portable, and more adaptive than ever. Still, the migration from hard-coded/hard-wired network functions toward their software-programmable counterparts comes along with the need for tailored optimizations and acceleration techniques so as to avoid or at least mitigate the throughput/latency performance degradation with respect to fixed function network elements. The contribution of this paper is twofold. First, we provide a comprehensive overview of the host-based network function virtualization (NFV) ecosystem, covering a broad range of techniques, from low-level hardware acceleration and bump-in-the-wire offloading approaches to high-level software acceleration solutions, including the virtualization technique itself. Second, we derive guidelines regarding the design, development, and operation of NFV-based deployments that meet the flexibility and scalability requirements of modern communication networks.

Programmable switches allow the packet processing behavior to be applied to transmitted packets, including the type, sequence, and semantics of processing operations, to be reconfigured on the fly in a systematic fashion. As such, programmable switches are the key to realize the next-generation of network services and applications, including software-defined networking, 5G, IoT, and massive-scale cloud computing. This paper presents a survey on the recent trends and issues in the design and implementation of programmable network devices, focusing on the prominent abstractions and architectures proposed, debated, realized, and deployed during the last 10 years. First we describe the anatomy of a programmable switch, then we highlight the most important pointers from the literature and cast different taxonomies for the field, and finally we sketch open issues and possible future research directions.

The killer features of the next-generation 5G mobile standard, including mobile edge computing and network slicing, will be very difficult to support with traditional fixed-function network appliances. Rather, the 5G core will depend on programmable switches, which allow packet processing functionality to be reconfigured on the fly in order to deploy virtualized network functions and service chains instantaneously. With 5G on the close horizon, it has become crucial to identify the price for programmability in the software data plane, considering the expected complexity and scale of the next-generation mobile core. In this paper, we report on a multi-year data-plane scalability study we have conducted for a large mobile vendor. Our results paint a rather pessimistic picture on the current landscape of the programmable software data plane. We find that the prominent programmable switches either do not provide all the features necessary to implement 5G telco pipelines efficiently or struggle to meet the scale, and the performance operators have come to expect from conventional fixed-function appliances. The only exception, ESwitch, remains proprietary. We call for further work on data-plane scalability and sketch some directions for future research.

To optimize the flow of traffic in IP networks, operators do traffic engineering (TE), i.e., tune routing-protocol parameters in response to traffic demands. TE in IP networks typically involves configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal-Cost-MultiPath (ECMP) mechanism. Unfortunately, ECMP is a notoriously cumbersome and indirect means for optimizing traffic flow, often leading to poor network performance. Also, obtaining accurate knowledge of traffic demands as the input to TE is elusive, and traffic conditions can be highly variable, further complicating TE. We leverage recently proposed schemes for increasing ECMP's expressiveness via carefully disseminated bogus information ("lies") to design COYOTE, a readily deployable TE scheme for robust and efficient network utilization. COYOTE leverages new algorithmic ideas to configure (static) traffic splitting ratios that are optimized with respect to all (even adversarially chosen) traffic scenarios within the operator's "uncertainty bounds". Our experimental analyses show that COYOTE significantly outperforms today's prevalent TE schemes in a manner that is robust to traffic uncertainty and variation. We discuss experiments with a prototype implementation of COYOTE.

OpenFlow is an amazingly expressive dataplane programming language, but this expressiveness comes at a severe performance price as switches must do excessive packet classification in the fast path. The prevalent OpenFlow software switch architecture is therefore built on flow caching, but this imposes intricate limitations on the workloads that can be supported efficiently and may even open the door to malicious cache overflow attacks. In this paper we argue that instead of enforcing the same universal flow cache semantics to all OpenFlow applications and optimize for the common case, a switch should rather automatically specialize its dataplane piecemeal with respect to the configured workload. We introduce ESwitch, a novel switch architecture that uses on-the-fly template-based code generation to compile any OpenFlow pipeline into efficient machine code, which can then be readily used as fast path. We present a proof-of-concept prototype and we demonstrate on illustrative use cases that ESwitch yields a simpler architecture, superior packet processing speed, improved latency and CPU scalability, and predictable performance. Our prototype can easily scale beyond 100 Gbps on a single Intel blade even with complex OpenFlow pipelines.

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state of the art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we redesign the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode an FIB comprising more than 440 K prefixes to just about 100-400 kB of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

A fundamental unsolved challenge in multipath routing is to provide disjoint end-to-end paths, each one satisfying certain operational goals (e.g., shortest possible), without overwhelming the data plane with prohibitive amount of forwarding state. In this paper, we study the problem of finding a pair of shortest disjoint paths that can be represented by only two forwarding table entries per destination. Building on prior work on minimum length redundant trees, we show that the underlying mathematical problem is NP-complete and we present heuristic algorithms that improve the known complexity bounds from cubic to the order of a single shortest path search. Finally, by extensive simulations we find that it is possible to very closely attain the absolute optimal path length with our algorithms (the gap is just 1 -- 5%), eventually opening the door for wide-scale multipath routing deployments.

With the increasing volume and volatility of Internet traffic, the need for adaptive routing algorithms has become compelling lately. An adaptive routing algorithm controls the rate at which traffic is placed on forwarding paths in concert with the actual user demands, making it possible to avoid congestion even when no information on expected traffic is available. In this article, we present a new model for rate-adaptive multipath routing, which allows one to analyze distributed, centralized, and hybrid routing architectures within a single framework, and to develop quantitative as well as qualitative arguments regarding their optimality, stability, and realizability. By a novel generalization of oblivious routing, we present a centralized algorithm with provable optimality, and we arrive at the conclusion that congestion can be completely eliminated even if routing decisions are completely precomputed. We find, although, that the complexity of the centralized scheme can become exponential. Therefore, we develop a hybrid distributed-centralized algorithm that combines the simplicity of distributed algorithms with the efficiency of centralized ones, and we provide numerical studies demonstrating that the hybrid scheme performs well in a broad selection of realistic scenarios. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 118–135 2015

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.

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.

The Internet routing ecosystem is facing compelling scalability challenges, manifested primarily in the rapid growth of IP packet forwarding tables. The forwarding table, implemented at the data plane fast path of Internet routers to drive the packet forwarding process, currently contains about half a million entries and counting. Meanwhile, it needs to support millions of complex queries and updates per second. In this paper, we make the curious observation that the entropy of IP forwarding tables is very small and, what is more, seems to increase at a lower pace than the size of the network. This suggests that a sophisticated compression scheme may effectively and persistently reduce the memory footprint of IP forwarding tables, shielding operators from scalability matters at least temporarily. Our main contribution is such a compression scheme which, for the first time, admits both the required information-theoretical size bounds and attains fast lookups, thanks to aggressive level compression. Although we find the underlying optimization problem NP-complete, we can still give a lightweight heuristic algorithm with firm approximation guarantees. This allows us to squeeze real IP forwarding tables, comprising almost 500, 000 prefixes, to just about 140-200 KBytes of memory within a factor of 2-3 of the entropy bound, so that forwarding decisions take only 8-10 memory accesses on average and updates are supported efficiently. Our compression scheme may be of more general interest, as it is applicable to essentially any prefix tree.

IP-level failure protection based on the IP Fast ReRoute/Loop-Free Alternates (LFA) specification has become industrial requirement recently. The success of LFA lies in its inherent simplicity, but this comes at the expense of letting certain failure scenarios go unprotected. Realizing full failure coverage with LFA so far has only been possible through completely reengineering the network around LFA-compliant design patterns. In this paper, we show that attaining high LFA coverage is possible without any alteration to the installed IP infrastructure, by introducing a carefully designed virtual overlay on top of the physical network that provides LFAs to otherwise unprotected routers. We study the problem of how to provision the overlay to maximize LFA coverage, we find that this problem is NPcomplete, and we give Integer Linear Programs to solve it. We also propose novel methods to work-around the limitations of current LFA implementations concerning Shared Risk Link Groups (SRLGs), which might be of independent interest. Our numerical evaluations suggest that router virtualization is an efficient tool for improving LFA-based resilience in real topologies.

Lately, there has been an upsurge of interest in compressed data structures, aiming to pack ever larger quantities of information into constrained memory without sacrificing the efficiency of standard operations, like random access, search, or update. The main goal of this paper is to demonstrate how data compression can benefit the networking community, by showing how to squeeze the IP Forwarding Information Base (FIB), the giant table consulted by IP routers to make forwarding decisions, into information-theoretical entropy bounds, with essentially zero cost on longest prefix match and FIB update. First, we adopt the state-of-the-art in compressed data structures, yielding a static entropy-compressed FIB representation with asymptotically optimal lookup. Then, we re-design the venerable prefix tree, used commonly for IP lookup for at least 20 years in IP routers, to also admit entropy bounds and support lookup in optimal time and update in nearly optimal time. Evaluations on a Linux kernel prototype indicate that our compressors encode a FIB comprising more than 440K prefixes to just about 100--400 KBytes of memory, with a threefold increase in lookup throughput and no penalty on FIB updates.

About what is the smallest size we can compress an IP Forwarding Information Base (FIB) down to, while still guaranteeing fast lookup? Is there some notion of FIB entropy that could serve as a compressibility metric? As an initial step in answering these questions, we present a FIB data structure, called Multibit Burrows-Wheeler transform (MBW), that is fundamentally pointerless, can be built in linear time, guarantees theoretically optimal longest prefix match, and compresses to higher-order entropy. Measurements on a Linux prototype provide a first glimpse of the applicability of MBW.

No abstract available.

Oblivious routing asks for a static routing that serves arbitrary user demands with minimal performance penalty. Performance is measured in terms of the competitive ratio, the proportion of the maximum congestion to the best possible congestion. In this paper, we take the first steps towards extending this worst-case characterization to a more revealing statistical one. We define new performance metrics and we present numerical evaluations showing that, in statistical terms, oblivious routing is not as competitive as the worst-case performance characterizations would suggest.

IP Fast ReRoute (IPFRR) is the IETF standard for providing fast failure protection in IP and MPLS/LDP networks and Loop Free Alternates (LFA) is a basic specification for implementing it. Even though LFA is simple and unobtrusive, it has a significant drawback: it does not guarantee protection for all possible failure cases. Consequently, many IPFRR proposals have appeared lately, promising full failure coverage at the price of added complexity and non-trivial modifications to IP hardware and software. Meanwhile, LFA remains the only commercially available, and therefore, the only deployable IPFRR solution. Deployment, however, crucially depends on the extent to which LFA can protect failures in operational networks. In this paper, therefore, we revisit LFA in order to give theoretical insights and practical hints to LFA failure coverage analysis. First, we identify the topological properties a network must possess to profit from good failure coverage. Then, we study how coverage varies as new links are added to a network, we show how to do this optimally and, through extensive simulations, we arrive to the conclusion that cleverly adding just a couple of new links can improve the quality of LFA protection drastically.

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.

Until recent years, it was more or less undisputed common-sense that an accurate view on traffic demands is indispensable for optimizing the flow of traffic through a network. Lately, this premise has been questioned sharply: it was shown that setting just a single routing, the so called demand-oblivious routing, is sufficient to accommodate any admissible traffic matrix in the network with moderate link overload, so no prior information on demands is absolutely necessary for efficient traffic engineering. Demand-oblivious routing lends itself to distributed implementations, so it scales well. In this paper, we generalize demand-oblivious routing in a new way: we show that, in contrast to the distributed case, centralized demand-oblivious routing can eliminate link overload completely. What is more, our centralized scheme allows for optimizing the routes with respect to arbitrary linear or quadratic objective function. We realize, however, that a centralized scheme can become prohibitively complex, therefore, we propose a hybrid distributed-centralized algorithm, which, according to our simulations, strikes a good balance between efficiency, scalability and complexity.

A centralized rate-adaptive routing algorithm is presented that, in contrast to the distributed ones available in the literature, achieves provable stability, optimalilty with respect to optional linear or quadratic objective functions, and feasibility in that it can accommodate any admissible traffic matrix in the network without violating link capacities. We recast the routing problem in the framework of constrained optimal control theory to obtain optimal state feedback routing controllers, and we present simulations confirming that our routing controllers are viable in small- and middle-sized networks.

In order for IP to become a full-fledged carrier- grade transport technology, a native IP failure-recovery scheme is necessary that can correct failures in the order of milliseconds. IP fast reroute (IPFRR) intends to fill this gap, providing fast, local and proactive handling of failures right in the IP layer. Building on experiences and extensive measurement results collected with a prototype implementation of the prevailing IPFRR technique, Not-via, in this paper we identify high address management burden and computational complexity as the major causes of why commercial IPFRR deployment still lags behind, and we present a lightweight not-via scheme, which, according to our measurements, improves these issues.

Redundant trees are commonly used for protection and restoration in communications networks. Zhang et al. presented a linear time algorithm to compute node-redundant trees in 2-node-connected networks, which has become widely cited in the literature. In this paper, we show that it is difficult to implement this algorithm providing both correctness and linear complexity at the same time. Therefore, we present a revised algorithm with strict linear time complexity. Moreover, we generalize the concept of node-redundant trees from 2-node-connected networks to arbitrary topologies, a crucial development since real networks can not always satisfy 2-connectedness, especially after a failure.

The problem of fair and feasible allocation of user throughputs in capacitated networks is investigated. The main contribution of the paper is an extension of network fairness, and in particular, max-min fairness from the traditional "fixed- path" model to a more versatile, routing-independent model. We show that the set of throughput configurations realizable in a capacitated network makes up a polyhedron, which gives rise to a max-min fair allocation completely analogous to the conventional case.

The problem of fair and feasible allocation of user throughputs in capacitated networks is investigated. The main contribution of the paper is a novel geometric approach, which facilitates to generalize several throughput allocation strategies, most importantly max-min fairness, from the traditional "fixed-path" model to a more versatile, routing-independent model. We show that the set of throughput configurations realizable in a capacitated network makes up a polyhedron, which gives rise to a max-min fair allocation completely analogous to the conventional one. An algorithm to compute this polyhedron is also presented, whose viability is demonstrated by comprehensive evaluation studies.

This paper focuses on the selection of bandwidth-guaranteed channels for communication sessions that require it. The basic idea comes from minimum interference routing: select a feasible path that puts the least possible restriction on the available transmission capacity of other communicating parties. This is achieved by circumventing some critical bottleneck links. The main contribution of the paper is a novel characterization of link criticality, the criticality threshold, which can be readily precompiled for routing dozens of subsequent calls. Based on this finding we define a generic precomputation framework for minimum interference routing, the least-critical-path-first routing algorithm. We show by means of extensive simulations that efficient route precomputation is possible even in the case, when accurate resource availability information is not immediately available.

The minimum cost multicommodity flow problem plays a central role in today's operations research theory with applications ranging from transportation and logistics to telecommunications network routing. In this paper, we introduce a novel Lagrangian-relaxation technique, which, given an initial feasible solution, can solve the minimum cost multicommodity flow problem as a sequence of single-commodity flow problems. Our methodology is best suited for OSPF traffic engineering, because it can rapidly improve a given path set towards approximate optimality while simultaneously provides the link weights, which implement the paths as shortest paths.