|
Broadly speaking, the bulk of my research deals with
computation and communication
problems in large-scale networks. I have been working on furthering
our theoretical
understandings of network information processing, as well as
devising efficient practical
algorithms and protocols for processing, discovering, and delivering
information in largescale networks of all kinds. With a unique background
in communication theory,
computer science and statistical physics, I have been able to make
significant
contributions to this wide filed, as summarized below.
(I) Joint Optimization of Multimedia Coding and Network
Delivery
Current network multimedia communication systems divide their
task into two,
essentially separate, layers: (i) a multimedia compression
layer and (ii) a network
delivery layer. This separation makes it possible to stream multimedia
contents using
protocols that were initially devised for communicating
generic information contents
(e.g., downloading a piece of software).
Our recent works have proved that unless in
very
special circumstances, this separation approach is grossly
suboptimal, i.e., the quality of
service to clients can be significantly improved if one views,
and solves, the problem of
multimedia compression and network delivery as one joint problem.
We have pioneered a new line of inquiry dubbed “joint
network-source coding”, as the
information theoretical framework for this joint design problem. On the
practical side,
we have devised a systematic solution to the problem based on
diversity routing and
coding, which employs multiple description coding (MDC) as its core coding
element
and
where the design of the MDC and the choice packet routes are jointly optimized.
For decades, MDC was believed to be useful
only to combat packet losses in packetswitched networks. As Goyal, a
pioneer in the field of MDC suggests, “... to gain
robustness to the loss of descriptions, MDC must sacrifice some
compression efficiency.
Thus, MDC should be applied only if this disadvantage in compression is
offset by the
advantage of mitigating transport failures”. Interestingly, I have been
able to show that
MDC is in fact quite
useful for communicating multimedia contents in networks, even in
the
absence of any transport failures. Our initial paper was warmly received at
major
conferences. It won the HP Best Paper
Award at the Visual Communications and Image
Processing,San Jose, CA, Jan 2008.
The work on joint multimedia coding and network delivery
algorithms, funded by two
NSERC strategic and discovery grants, is a major direction of
my future work. With
multimedia contents claiming the lion share of the Internet
traffic, I would expect more
researchers to get involved in understanding the fundamental
of the interplay between
lossy
signal compression and network communication. My upcoming book, titled
“Network-Aware Source Coding and Communication”, by the Cambridge University
Press, is almost entirely devoted to defining and developing
this new filed. With these
pioneering works, I hope to establish our group as a leader in this
emerging field.
(II) Efficient P2P Network Management and Search
We have made significant contributions to the field of
unstructured P2P networking.
P2P networks are broadly categorizes as either structured or
unstructured. Unlike their
structured counterparts, unstructured networks, (e.g.,
Gnutella) do not impose strict
restrictions on the network topology and placement of the contents on
network nodes.
The search on unstructured P2P networks was believed to be
inherently unscalable, as it
often
required exhaustive search of network nodes. However, our pioneering work
on
search in
unstructured networks proved otherwise.
We devised a scalable Peer-to-Peer (P2P) search algorithm,
called the “Percolation
Search Algorithm” (PAS), that provably
generates sub-linear traffic per query, while
guaranteeing that any content can be found with probability one. To date,
and to the best
of my knowledge, PSA remains the only
provably scalable unstructured P2P search
algorithm with guarantees search quality. The related paper received
the best paper
award at the Fourth IEEE International Conference on P2P
Networks (2004), held in
Zurich,
where an anonymous reviewer described it as a “beautiful piece of art”. The
work was also featured in a number of articles, including one
in the Technology
Research News Magazine and was cited more than 90 times by Nov 2009.
While based on complex theoretical foundations, the PSA itself is surprisingly
easy to
implement. The Brunet project, which we initiated at the UCLA in 2004
and is now
maintained by the University of Florida, is an open source, general purpose P2P
networking library that implements PSA as one of its
publication and search mechanisms.
(III) Understanding and “Engineering” Complex Networks
Complex networks comprises a challenging interdisciplinary
field that integrates
concepts and tools from statistical mechanics (e.g., the
mean-field theory, self-organized
criticality, and critical phenomena, such as phase transitions),
and combinatorics and
computer science (e.g., random graphs, networks, and graph theory). We
have, however,
brought in a
completely new perspective into the field.
While most researchers have been trying to model the
properties and dynamics of reallife
networks (e.g., social networks, email networks or the
Internet), we posed the
following two major questions: (a) can one use some of the
underlying dynamical
principles in real-life networks to actively design or “engineer” new networks with
predictable, desired properties, such as global connectivity
and searchability?, and (b)
whether understanding statistical properties of existing
networks allows us to design
algorithms and applications that exploit these inherent
properties for efficient information
processing and disvovery?
A large portion of my work for the past six years has focused
on different aspects of
these
questions. In particular, we have been able to model the time evolution of
the
WWW graph and to devise
algorithms that go beyond PageRank type algorithms to
detect “up and comming” web pages that are potentially of
higher quality than others, a
work that was featured on the
cover of the prestigious Proceedings of the National
Academy of Sciences (PNAS). Other works include
exploiting the topological structure of
email networks to create efficient, distributed spam control
algorithms, or devising P2P
network
management protocols that guarantee network connectivity and searchability.
Complex networks theory and application will remain an active
area of our research in
the
future. We have recently embarked on a new ambitious joint project with the
University
of California, Los Angles, to further our initial works on the evolution of
the WWW
graph, by using cloud computing to track the evolutions of
tens of billions of nodes in the
WWW graph over an extended
period of time.
(V) Distributed Communication Algorithms for Large-Scale
Ad-Hoc Networks
We have had a number of important contributions to designing
routing and network
management protocols for large-scale wireless sensor and ad-hoc
networks. I have been
particularly interested in network structures and routing algorithms that
can support lowlatency ad-hoc networking, where the network latency is
required to scale logarithmically with the network size. There are two
major problems in doing so. Firstly, low-latency networking is demanding in
terms of power and bandwidth. Secondly, even when power and bandwidth are
not issues, designing routing protocols to provide a low-latency networking
infrastructure is not trivial. In a series of papers including two in the
IEEE Trans. on Networks, we have investigated fundamental power and
bandwidth bounds in low-latency ad-hoc networks, as well as efficient,
distributed routing algorithms that achieve these bounds.
|
