1. Online Aggregation of
the Forwarding Information Base: Accounting for Locality and Churn
Abstract: 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.
2. Adaptive Caching Networks With Optimality
Guarantees
Abstract: We study the optimal
placement of content over a network of caches, a problem naturally arising in
several networking applications. Given a demand of content request rates and
paths followed, we wish to determine the content placement that maximizes the
expected caching gain, i.e., the reduction of routing costs due to intermediate
caching. The offline version of this problem is NP-hard and, in general, the
demand and topology may be a priori unknown. Hence, a distributed,
adaptive approximation algorithm for placing contents into caches is desired.
We show that path replication, a simple algorithm frequently encountered in
literature, can be arbitrarily suboptimal when combined with traditional
eviction policies. We propose a distributed, adaptive algorithm that performs
stochastic gradient ascent on a concave relaxation of the expected caching
gain, and constructs a probabilistic content placement within a
1 − 1/e factor from the optimal, in expectation. Motivated by
our analysis, we also propose a novel greedy eviction policy to be used with
path replication, and show through numerical evaluations that both algorithms
significantly outperform path replication with traditional eviction policies
over a broad array of network topologies.
3. A Probabilistic
Framework for Structural Analysis and Community Detection in Directed Networks
Abstract: There is growing interest
in structural analysis of directed networks. Two major points that
need to be addressed are: 1) a formal and precise definition of the graph
clustering and community detection problem in directed networks and 2)
algorithm design and evaluation of community detection algorithms in directed
networks.Motivated by these, we develop a probabilistic framework for
structural analysis and community detection in directed networks
based on our previous work in undirected networks. By relaxing the
assumption from symmetric bivariate distributions in our previous
work to bivariate distributions that have the same marginal distributions in
this paper, we can still formally define various notions for structural
analysis in directed networks, including centrality, relative centrality,
community, and modularity. We also extend three commonly used community
detection algorithms in undirected networks to directed networks:
the hierarchical agglomerative algorithm, the partitional algorithm, and the
fast unfolding algorithm. These are made possible by two modularity preserving
and sparsity preserving transformations. In conjunction with the probabilistic
framework, we show these three algorithms converge in a finite number of steps.
In particular, we show that the partitional algorithm is a linear time
algorithm for large sparse graphs. Moreover, the outputs of the hierarchical
agglomerative algorithm and the fast unfolding algorithm are guaranteed to
be communities. These three algorithms can also be extended to general
bivariate distributions with some minor modifications. We also conduct various
experiments by using two sampling methods in directed networks: 1) PageRank and
2) random walks with self-loops and backward jumps.
4. Datum: Managing Data
Purchasing and Data Placement in a Geo-Distributed Data Market
Abstract: This paper studies two
design tasks faced by a geodistributed cloud data market: which data to
purchase (data purchasing) and where to place/replicate the data for delivery
(data placement). We show that the joint problem of data purchasing and data
placement within a cloud data market can be viewed as a facility location
problem and is thus NP-hard. However, we give a provably optimal algorithm for
the case of a data market made up of a single data center and then generalize
the structure from the single data center setting in order to develop a
near-optimal, polynomial-time algorithm for a geo-distributed data market. The
resulting design, Datum, decomposes the joint purchasing and placement
problem into two subproblems, one for data purchasing and one for data
placement, using a transformation of the underlying bandwidth costs. We show,
via a case study, that Datum is near optimal (within 1.6%) in
practical settings.
5. Efficient and Flexible
Crowdsourcing of Specialized Tasks with Precedence Constraints
Abstract: Many companies now use
crowdsourcing to leverage external (as well as internal) crowds to perform
specialized work, and so methods of improving efficiency are critical. Tasks in
crowdsourcing systems with specialized work have multiple steps and each step
requires multiple skills. Steps may have different flexibilities in terms of
obtaining service from one or multiple agents, due to varying levels of
dependency among parts of steps. Steps of a task may have precedence
constraints among them. Moreover, there are variations in loads of different
types of tasks requiring different skill-sets and availabilities of different
types of agents with different skill-sets. Considering these constraints
together necessitates the design of novel schemes to allocate steps to agents.
In addition, large crowdsourcing systems require allocation schemes that are
simple, fast, decentralized and offer customers (task requesters) the freedom
to choose agents. In this work we study the performance limits of such
crowdsourcing systems and propose efficient allocation schemes that provably
meet the performance limits under these additional requirements. We demonstrate
our algorithms on data from a crowdsourcing platform run by a non-profit
company and show significant improvements over current practice.
6. A Non-Monetary
Mechanism for Optimal Rate Control Through Efficient Cost Allocation
Abstract: This paper proposes a
practical non-monetary mechanism that induces the efficient solution to the
optimal rate control problem, where each client optimizes its request arrival
rate to maximize its own net utility individually, and at the Nash Equilibrium
the total net utility of the system is also maximized. Existing mechanisms
typically rely on monetary exchange which requires additional infrastructure
that is not always available. Instead, the proposed mechanism is based on
efficient cost allocation, where the cost is in terms of nonmonetary metric,
such as average delay or request loss rate. Specifically, we present an
efficient cost allocation rule for the server to determine the target cost of
each client.We then propose an intelligent policy for the server to control the
costs of the clients to achieve the efficient allocation. Furthermore, we
design a distributed rate control protocol with provable convergence to the
Nash Equilibrium of the system. The effectiveness of our mechanism is
extensively evaluated via simulations of both delay allocation and loss rate
allocation against baseline mechanisms with classic control policies.
7. Efficient Embedding of
Scale-Free Graphs In the Hyperbolic Plane
Abstract: Hyperbolic geometry
appears to be intrinsic in many large real networks. We construct and implement
a new maximum likelihood estimation algorithm that embeds scale-free graphs in
the hyperbolic space. All previous approaches of similar embedding algorithms
require at least a quadratic runtime. Our algorithm achieves quasi-linear
runtime, which makes it the first algorithm that can embed networks with
hundreds of thousands of nodes in less than one hour. We demonstrate the
performance of our algorithm on artificial and real networks. In all typical
metrics, such as log-likelihood and greedy routing, our algorithm discovers
embeddings that are very close to the ground truth.
8. Enhancing Fault
Tolerance and Resource Utilization In Unidirectional Quorum-Based Cycle Routing
Abstract: Cycle-based optical
network routing, whether using synchronous optical networking rings or
p-cycles, provides sufficient reliability in the network. Light trails forming
a cycle allow broadcasts within a cycle to be used for efficient multicasts.
Optimal communication quorum sets forming optical cycles based on light trails
have been shown to flexibly and efficiently route both point-to-point and
multipoint-to-multipoint traffic requests. Commonly, cycle routing techniques
use pairs of cycles to achieve both routing and fault tolerance, which use
substantial resources and create the potential for underutilization. Instead,
we intentionally utilize R redundancy within the quorum cycles for
fault tolerance such that every point-to-point communication pairs occur in at
least R cycles. We develop a generalized R redundancy cycle
technique that provides optical networks high fault-tolerant communications
capability. When applied using only the single unidirectional cycles rather
than the standard paired cycles, the generalized R redundancy
technique has been shown to almost halve the necessary light-trail resources in
the network. However, due to unidirectional nature, a small percentage of node
pairs for one-to-one communication may not have exactly two paths. For this
reason, we further develop a greedy cycle direction heuristic and show a
reduction of missing pairs. More importantly, we show that the resource
requirement is reduced while maintaining the fault tolerance and dependability
expected from cycle-based routing. The result is a set of cycles with
96.6%–99.37% fault coverage, while using 42.9%–47.18% fewer resources.
Abstract: User-facing services
deployed in data centers must respond quickly to user actions. The measurement
of network latencies is of paramount importance. Recently, a new family of
compact data structures has been proposed to estimate one-way latencies. In order
to achieve scalability, these new methods rely on timestamp aggregation.
Unfortunately, this approach suffers from serious accuracy problems in the
presence of packet loss and reordering, given that a single lost or
out-of-order packet may invalidate a huge number of aggregated samples. In this
paper, we unify the problem to detect lost and reordered packets within the set
reconciliation framework. Although the set reconciliation approach and the data
structures for aggregating packet timestamps are previously known, the
combination of these two principles is novel. We present a space-efficient
synopsis called reconcilable difference aggregator (RDA). RDA maximizes the
percentage of useful packets for latency measurement by mapping packets to
multiple banks and repairing aggregated samples that have been damaged by lost
and reordered packets. RDA simultaneously obtains the average and the standard
deviation of the latency. We provide a formal guarantee of the performance and
derive optimized parameters. We further design and implement a user-space
passive latency measurement system that addresses practical issues of
integrating RDA into the network stack. Our extensive evaluation shows that
compared with existing methods, our approach improves the relative error of the
average latency estimation in 10–15 orders of magnitude, and the relative error
of the standard deviation in 0.5–6 orders of magnitude.
10. Optimal Control for
Generalized Network-Flow Problems
Abstract: We consider the problem
of throughput-optimal packet dissemination, in the presence of an arbitrary mix
of unicast, broadcast, multicast and anycast traffic, in a general wireless
network. We propose an online dynamic policy, called Universal Max-Weight
(UMW), which solves the above problem efficiently. To the best of our
knowledge, UMW is the first throughput-optimal algorithm of such versatility in
the context of generalized network flow problems. Conceptually, the UMW policy
is derived by relaxing the precedence constraints associated with multi-hop
routing, and then solving a min-cost routing and max-weight scheduling problem
on a virtual network of queues. When specialized to the unicast setting, the
UMW policy yields a throughput-optimal cycle-free routing and link scheduling
policy. This is in contrast to the well-known throughput-optimal Back- Pressure
(BP) policy which allows for packet cycling, resulting in excessive delay.
Extensive simulation results show that the proposed policy incurs a
substantially lower delay as compared to the BP policy. The proof of
throughput-optimality of the UMW policy combines techniques from stochastic
Lyapunov theory with a sample path argument from adversarial queueing theory
and may be of independent theoretical interest.
11. Online Scaling of NFV
Service Chains Across Geo-Distributed Datacenters
Abstract: Network Function
Virtualization (NFV) is an emerging paradigm that turns hardware-dependent
implementation of network functions (i.e., middleboxes) into software modules
running on virtualized platforms, for significant cost reduction and ease of
management. Such virtual network functions (VNFs) commonly constitute service
chains, to provide network services that traffic flows need to go through.
Efficient deployment of VNFs for network service provisioning is a key to
realize the NFV goals. Existing efforts on VNF placement mostly deal with
offline or one-time placement, ignoring the fundamental, dynamic deployment and
scaling need of VNFs to handle practical time-varying traffic volumes. This
work investigates dynamic placement of VNF service chains across geodistributed
datacenters to serve flows between dispersed source and destination pairs, for
operational cost minimization of the service chain provider over the entire
system span. An efficient online algorithm is proposed, which consists of two
main components: 1) A regularization-based approach from online learning
literature to convert the offline optimal deployment problem into a sequence of
one-shot regularized problems, each to be efficiently solved in one time slot
and 2) An online dependent rounding scheme to derive feasible integer solutions
from the optimal fractional solutions of the one-shot problems, and to
guarantee a good competitive ratio of the online algorithm over the entire time
span. We verify our online algorithm with solid theoretical analysis and
trace-driven simulations under realistic settings.
12. A Ternary Unification
Framework for Optimizing Tcam-Based Packet Classification Systems
Abstract: Packet classification is
the key mechanism for enabling many networking and security services. Ternary
Content Addressable Memory (TCAM) has been the industrial standard for
implementing high-speed packet classification because of its constant
classification time. However, TCAM chips have small capacity, high power
consumption, high heat generation, and large area size. This paper focuses on
the TCAMbased Classifier Compression problem: given a classifier C, we
want to construct the smallest possible list of TCAM entries T that
implement C. In this paper, we propose the Ternary Unification Framework
(TUF) for this compression problem and three concrete compression algorithms
within this framework. The framework allows us to find more optimization
opportunities and design new TCAM-based classifier compression algorithms. Our
experimental results show that the TUF can speed up the prior algorithm TCAM
Razor by twenty times or more and leads to new algorithms that improve
compression performance over prior algorithms by an average of 13.7% on our
largest real life classifiers.
13. Accurate Recovery of Internet Traffic Data
Under Variable Rate Measurements
Abstract: The inference of the
network traffic matrix from partial measurement data becomes increasingly
critical for various network engineering tasks, such as capacity planning, load
balancing, path setup, network provisioning, anomaly detection, and failure
recovery. The recent study shows it is promising to more accurately interpolate
the missing data with a 3-D tensor as compared with the interpolation methods
based on a 2-D matrix. Despite the potential, it is difficult to form a tensor
with measurements taken at varying rate in a practical network. To address the
issues, we propose a Reshape-Align scheme to form the regular tensor with data
from variable rate measurements, and introduce user-domain and temporal-domain
factor matrices which take full advantage of features from both domains to
translate the matrix completion problem to the tensor completion problem based
on CANDECOMP/PARAFAC decomposition for more accurate missing data recovery. Our
performance results demonstrate that our Reshape-Align scheme can achieve
significantly better performance in terms of several metrics: error ratio, mean
absolute error, and root mean square error.
No comments:
Post a Comment