
We study the following oneway asymmetric transmission problem, also a
variant of modelbased compressed sensing: a resourcelimited encoder has to
report a small set $S$ from a universe of $N$ items to a more powerful decoder
(server). The distinguishing feature is asymmetric information: the subset $S$
is comprised of i.i.d. samples from a prior distribution $\mu$, and $\mu$ is
only known to the decoder. The goal for the encoder is to encode $S$
obliviously, while achieving the informationtheoretic bound of $S \cdot
H(\mu)$, i.e., the Shannon entropy bound.
We first show that any such compression scheme must be {\em randomized}, if
it gains nontrivially from the prior $\mu$. This stands in contrast to the
symmetric case (when both the encoder and decoder know $\mu$), where the
Huffman code provides a nearoptimal deterministic solution. On the other hand,
a rather simple argument shows that, when $S=k$, a random linear code
achieves nearoptimal communication rate of about $k\cdot H(\mu)$ bits. Alas,
the resulting scheme has prohibitive decoding time: about ${N\choose k} \approx
(N/k)^k$.
Our main result is a computationally efficient and linear coding scheme,
which achieves an $O(\lg\lg N)$competitive communication ratio compared to the
optimal benchmark, and runs in $\text{poly}(N,k)$ time. Our "multilevel"
coding scheme uses a combination of hashing and syndromedecoding of
ReedSolomon codes, and relies on viewing the (unknown) prior $\mu$ as a rather
small convex combination of uniform ("flat") distributions.

Fullduplex (FD) wireless is an attractive communication paradigm with high
potential for improving network capacity and reducing delay in wireless
networks. Despite significant progress on the physical layer development, the
challenges associated with developing medium access control (MAC) protocols for
heterogeneous networks composed of both legacy halfduplex (HD) and emerging FD
devices have not been fully addressed. Therefore, we focus on the design and
performance evaluation of scheduling algorithms for infrastructurebased
heterogeneous networks (composed of HD and FD users). We develop the hybrid
Greedy Maximal Scheduling (HGMS) algorithm, which is tailored to the special
characteristics of such heterogeneous networks and combines both centralized
GMS and decentralized QCSMA mechanisms. Moreover, we prove that HGMS is
throughputoptimal. We then demonstrate by simple examples the benefits of
adding FD nodes to a network. Finally, we evaluate the performance of HGMS and
its variants in terms of throughput, delay, and fairness between FD and HD
users via extensive simulations. We show that in heterogeneous HDFD networks,
HGMS achieves 510x better delay performance and improves fairness between HD
and FD users by up to 50% compared with the fully decentralized QCSMA
algorithm.

In dataparallel computing frameworks, intermediate parallel data is often
produced at various stages which needs to be transferred among servers in the
datacenter network (e.g. the shuffle phase in MapReduce). A stage often cannot
start or be completed unless all the required data pieces from the preceding
stage are received. \emph{Coflow} is a recently proposed networking abstraction
to capture such communication patterns. We consider the problem of efficiently
scheduling coflows with release dates in a shared datacenter network so as to
minimize the total weighted completion time of coflows.
Several heuristics have been proposed recently to address this problem, as
well as a few polynomialtime approximation algorithms with provable
performance guarantees. Our main result in this paper is a polynomialtime
deterministic algorithm that improves the prior known results. Specifically, we
propose a deterministic algorithm with approximation ratio of $5$, which
improves the prior best known ratio of $12$. For the special case when all
coflows are released at time zero, our deterministic algorithm obtains
approximation ratio of $4$ which improves the prior best known ratio of $8$.
The key ingredient of our approach is an improved linear program formulation
for sorting the coflows followed by a simple list scheduling policy. Extensive
simulation results, using both synthetic and real traffic traces, are presented
that verify the performance of our algorithm and show improvement over the
prior approaches.

Wireless object tracking applications are gaining popularity and will soon
utilize emerging ultralowpower devicetodevice communication. However,
severe energy constraints require much more careful accounting of energy usage
than what prior art provides. In particular, the available energy, the
differing power consumption levels for listening, receiving, and transmitting,
as well as the limited control bandwidth must all be considered. Therefore, we
formulate the problem of maximizing the throughput among a set of heterogeneous
broadcasting nodes with differing power consumption levels, each subject to a
strict ultralowpower budget. We obtain the oracle throughput (i.e., maximum
throughput achieved by an oracle) and use Lagrangian methods to design EconCast
 a simple asynchronous distributed protocol in which nodes transition between
sleep, listen, and transmit states, and dynamically change the transition
rates. EconCast can operate in groupput or anyput modes to respectively
maximize two alternative throughput measures. We show that EconCast approaches
the oracle throughput. The performance is also evaluated numerically and via
extensive simulations and it is shown that EconCast outperforms prior art by 6x
 17x under realistic assumptions. Moreover, we evaluate EconCast's latency
performance and consider design tradeoffs when operating in groupput and anyput
modes. Finally, we implement EconCast using the TI eZ430RF2500SEH energy
harvesting nodes and experimentally show that in realistic environments it
obtains 57%  77% of the achievable throughput.

Content Delivery Networks (CDNs) deliver a majority of the userrequested
content on the Internet, including web pages, videos, and software downloads. A
CDN server caches and serves the content requested by users. Designing caching
algorithms that automatically adapt to the heterogeneity, burstiness, and
nonstationary nature of realworld content requests is a major challenge and
is the focus of our work. While there is much work on caching algorithms for
stationary request traffic, the work on nonstationary request traffic is very
limited. Consequently, most prior models are inaccurate for production CDN
traffic that is nonstationary.
We propose two TTLbased caching algorithms and provide provable guarantees
for content request traffic that is bursty and nonstationary. The first
algorithm called dTTL dynamically adapts a TTL parameter using a stochastic
approximation approach. Given a feasible target hit rate, we show that the hit
rate of dTTL converges to its target value for a general class of bursty
traffic that allows Markov dependence over time and nonstationary arrivals.
The second algorithm called fTTL uses two caches, each with its own TTL. The
firstlevel cache adaptively filters out nonstationary traffic, while the
secondlevel cache stores frequentlyaccessed stationary traffic. Given
feasible targets for both the hit rate and the expected cache size, fTTL
asymptotically achieves both targets. We implement dTTL and fTTL and evaluate
both algorithms using an extensive nineday trace consisting of 500 million
requests from a production CDN server. We show that both dTTL and fTTL
converge to their hit rate targets with an error of about 1.3%. But, fTTL
requires a significantly smaller cache size than dTTL to achieve the same hit
rate, since it effectively filters out the nonstationary traffic for
rarelyaccessed objects.

Motivated by emerging big streaming data processing paradigms (e.g., Twitter
Storm, Streaming MapReduce), we investigate the problem of scheduling graphs
over a large cluster of servers. Each graph is a job, where nodes represent
compute tasks and edges indicate dataflows between these compute tasks. Jobs
(graphs) arrive randomly over time, and upon completion, leave the system. When
a job arrives, the scheduler needs to partition the graph and distribute it
over the servers to satisfy load balancing and cost considerations.
Specifically, neighboring compute tasks in the graph that are mapped to
different servers incur load on the network; thus a mapping of the jobs among
the servers incurs a cost that is proportional to the number of "broken edges".
We propose a low complexity randomized scheduling algorithm that, without
service preemptions, stabilizes the system with graph arrivals/departures; more
importantly, it allows a smooth tradeoff between minimizing average
partitioning cost and average queue lengths. Interestingly, to avoid service
preemptions, our approach does not rely on a Gibbs sampler; instead, we show
that the corresponding limiting invariant measure has an interpretation
stemming from a loss system.

In this paper we look at content placement in the highdimensional regime:
there are n servers, and O(n) distinct types of content. Each server can store
and serve O(1) types at any given time. Demands for these content types arrive,
and have to be served in an online fashion; over time, there are a total of
O(n) of these demands. We consider the algorithmic task of content placement:
determining which types of content should be on which server at any given time,
in the setting where the demand statistics (i.e. the relative popularity of
each type of content) are not known apriori, but have to be inferred from the
very demands we are trying to satisfy. This is the high dimensional regime
because this scaling (everything being O(n)) prevents consistent estimation of
demand statistics; it models many modern settings where large numbers of users,
servers and videos/webpages interact in this way. We characterize the
performance of any scheme that separates learning and placement (i.e. which use
a portion of the demands to gain some estimate of the demand statistics, and
then uses the same for the remaining demands), showing it is orderwise
strictly suboptimal. We then study a simple adaptive scheme  which myopically
attempts to store the most recently requested content on idle servers  and
show it outperforms schemes that separate learning and placement. Our results
also generalize to the setting where the demand statistics change with time.
Overall, our results demonstrate that separating the estimation of demand, and
the subsequent use of the same, is strictly suboptimal.

We use fluid limits to explore the (in)stability properties of wireless
networks with queuebased randomaccess algorithms. Queuebased randomaccess
schemes are simple and inherently distributed in nature, yet provide the
capability to match the optimal throughput performance of centralized
scheduling mechanisms in a wide range of scenarios. Unfortunately, the type of
activation rules for which throughput optimality has been established, may
result in excessive queue lengths and delays. The use of more
aggressive/persistent access schemes can improve the delay performance, but
does not offer any universal maximumstability guarantees. In order to gain
qualitative insight and investigate the (in)stability properties of more
aggressive/persistent activation rules, we examine fluid limits where the
dynamics are scaled in space and time. In some situations, the fluid limits
have smooth deterministic features and maximum stability is maintained, while
in other scenarios they exhibit random oscillatory characteristics, giving rise
to major technical challenges. In the latter regime, more aggressive access
schemes continue to provide maximum stability in some networks, but may cause
instability in others. Simulation experiments are conducted to illustrate and
validate the analytical results.

It is by now wellknown that wireless networks with file arrivals and
departures are stable if one uses alphafair congestion control and
backpressure based scheduling and routing. In this paper, we examine whether
?alphafair congestion control is necessary for flowlevel stability. We show
that stability can be ensured even with very simple congestion control
mechanisms, such as a fixed window size scheme which limits the maximum number
of packets that are allowed into the ingress queue of a flow. A key ingredient
of our result is the use of the difference between the logarithms of queue
lengths as the link weights. This result is reminiscent of results in the
context of CSMA algorithms, but for entirely different reasons.

The process by which new ideas, innovations, and behaviors spread through a
large social network can be thought of as a networked interaction game: Each
agent obtains information from certain number of agents in his friendship
neighborhood, and adapts his idea or behavior to increase his benefit. In this
paper, we are interested in how opinions, about a certain topic, form in social
networks. We model opinions as continuous scalars ranging from 0 to 1 with 1(0)
representing extremely positive(negative) opinion. Each agent has an initial
opinion and incurs some cost depending on the opinions of his neighbors, his
initial opinion, and his stubbornness about his initial opinion. Agents
iteratively update their opinions based on their own initial opinions and
observing the opinions of their neighbors. The iterative update of an agent can
be viewed as a myopic costminimization response (i.e., the socalled best
response) to the others' actions. We study whether an equilibrium can emerge as
a result of such local interactions and how such equilibrium possibly depends
on the network structure, initial opinions of the agents, and the location of
stubborn agents and the extent of their stubbornness. We also study the
convergence speed to such equilibrium and characterize the convergence time as
a function of aforementioned factors. We also discuss the implications of such
results in a few wellknown graphs such as ErdosRenyi random graphs and
smallworld graphs.

Recently, it has been shown that CSMA algorithms which use queue lengthbased
link weights can achieve throughput optimality in wireless networks. In
particular, a key result by Rajagopalan, Shah, and Shin (2009) shows that, if
the link weights are chosen to be of the form log(log(q)) (where q is the
queuelength), then throughput optimality is achieved. In this paper, we
tighten their result by showing that throughput optimality is preserved even
with weight functions of the form log(q)/g(q), where g(q) can be a function
that increases arbitrarily slowly. The significance of the result is due to the
fact that weight functions of the form log(q)/g(q) seem to achieve the best
delay performance in practice.