Building applications that can harness this tremendous power requires a drastic change in our design philosophy from the conventional client/server paradigms to network computing, one that is based on the cooperation of a large number of network users. Network computing applications range from pooling of digital media and computation resources in P2P networks to parallel computing, sensor networking, wireless ad-hoc networking and network multimedia communication.

 

Network computing has to overcome many challenges. Firstly, all protocols and algorithms developed should be local. This is essential if the network members should work autonomously as is the case for most modern distributed applications. Yet, these local protocols and algorithms should be able to provide a global desired service. This becomes a lot more challenging when one considers the extreme size of some of these networks (tens of millions of nodes in some application), heterogeneity of most networks and the ad-hoc and perhaps unreliable behavior of network members.

 

My current and future research interests lie broadly in the realm of networked, distributed and collaborative systems. Throughout my graduate work, I have been specifically working on the issues arising in networked heterogeneous systems. This includes various distributed search algorithms as well as collaborative source communication. To deal with very large scale networks, I had to bring together many tools and ideas from computer science, communication engineering and statistical physics. With this unique combination, I had been able to turn diverse ideas, such as percolation theory and thermodynamics, into realizable, analytically tractable, robust network computing algorithms.

 

 In addition, I have collaborated with a number of researchers on topics ranging from Queuing Theory to Bio-Informatics. The following sections summarize the projects I have been working on, my contributions, and their future directions. My long-term research plans and potential research directions in related fields are also discussed briefly.

 

• Large Scale Distributed Systems and P2P Networks

The "Peer-to-Peer (P2P) revolution", has essentially redefined the Internet into an infrastructure for overlay distributed computing. Large scale P2P networks have recently been deployed, in which some 20 million users are expected to be online at any given time. While file sharing remains the dominant area in P2P computing, the promise of P2P computing extends well beyond pooling digital media. P2P computing is the paradigm with the promise to push a number of interesting distributed computing technologies from the shadows into the spotlight. P2P distributed computing is no more confined to a few interconnected processors on one chip; rather it extends to millions of users widely distributed all over the planet. P2P resource pooling is already employed for efficient use of corporate resources. The P2P philosophy, that of providing robust services through redundant employment of cheap, fault prone agents is gaining large industrial attention. Google, for instance, is known to have incorporated a web of thousands of interconnected commodity PC's, instead of a few expensive servers. This has allowed Google to extremely increase its robustness while significantly reducing its costs.

 

A successful large scale P2P network has to bring together a large number of participants with hugely different computational and communication resources, with various services and demands and varying interaction behaviors and dynamics. Yet, this heterogeneous set of participants, equipped with proper P2P computation protocols, has to seamlessly provide some service, e.g., P2P search. Network management in such ad-hoc environment requires new tools, both analytically and practically, previously unknown to more centralized design paradigms. This problem can be divided into two parts. (1) New protocols should be devised that run locally on nodes, but can guarantee the emergence of some desired global network structure. Designing such protocols that can lead to stable, robust and scalable networks even in heterogeneous and ad-hoc environments is a challenging problem. (2) Once formed, the P2P network should provide a primitive function (e.g., search) using only decentralized algorithms. The scalability of these algorithms directly determines the extent to which the P2P network can grow.

 

Accomplishments and Contributions:

I have invented a new scalable P2P search algorithm, called “percolation search algorithm”. Percolation search is a totally decentralized algorithm that is able to locate any item in a P2P network with minimal search traffic. Using percolation search, any item in a network of N nodes can almost surely be located using only  communications within steps. This state of the art search algorithm has received widespread academic and media attention. It won the best paper award at the 4^th IEEE International Conference on P2P Computing in 2003.

Percolation search works on networks with certain statistical properties. We have devised decentralized algorithms, based on ideas in statistical physics, that provably ensure the emergence of networks with such properties, even in the face of extreme dynamical uncertainties.

UCLA’s complex networks group, led by Prof. Roychowdhury, in conjunction with Dr. Boykin’s group in University of Florida are currently implementing ideas of percolation search into a real P2P system called the BruNet.

Future Directions:

      Percolation search algorithm has the ability to answer complex queries using scalable resources. Its use therefore, goes far beyond file sharing. My long term vision is a full featured distributed database with percolation search as its search engine. With the BruNet project nearing its end, a professional, open source and free implementation of the percolation search algorithm will be soon available.  As for the first assignment of BruNet, Dr. Müller’s group at the University of Bamberg in Germany will be using BruNet for searching shared images in Flickr.com in a P2P fashion.

 

• Source Communication over Large Networks

How can members of a large scale network cooperate in communicating information across the network? Dose cooperation increase the communication capability of a network? A positive answer to this question has given birth to an exciting new filed called network coding. Network coding has received an immense attention from the research community in the past five years.

For many applications, on the other hand, such as networked multimedia and sensor networks, the relevant question is, how well can a source be communicated over a network? Surprisingly, this problem (which we call network source communication) is virtually left unconsidered. This is despite the fact that, arguably, the majority of applications, both in the Internet and in various wireless setups (in particular for multimedia applications), involve network source communication.

 

As an example, consider the problem of broadcasting a movie to a heterogeneous set of clients over the Internet. The clients can range from low connectivity wireless phones to broadband connections. Network source coding is the strategy that ensures that each client is able to enjoy the clip with a quality proportional to its connection bandwidth. Superior performance is accomplished by using the help of all the clients; each client can receive, process and forward information to its neighboring nodes in the network.

Understanding the network source coding problem and designing proper network source coding algorithms and techniques can have far reaching consequences in some of the most practically interesting network applications, such as real-time multimedia streaming.

 

Accomplishments and Contributions:

I, along with my advisor Prof. Wu, have formally posed the network source coding problem for the first time and have proved the only known nontrivial achievability result. On the practical side, we have devised a systematic approach to optimized source network coding. The approach breaks the problem into two parts: (1) optimizing the flow of source descriptions in the network, (2) designing an optimal source code corresponding to this optimal flow.

To that end, we had to introduce a new set of routing problems we call Rainbow Network Flow (RNF) problems. RNF is concerned with optimal routing of multiple description codes (MDC) over arbitrary networks. RNF is different from classic commodity routing in that it takes into account the information content of the descriptions. A node is not going to benefit from duplicate copies of a single description. The goal is, therefore, not to maximize the total volume of the flow to clients, rather, to maximize the total volume of distinct descriptions. On the other hand, unlike commodity flow, a description can be duplicated at intermediate nodes.

 The RNF concept leads to a set of new and exciting problems that are important both in their engineering as well as computer scientific rights.  We show that RNF problem is NP-Hard in its full generality. We have identified various practically interesting special cases for which the problem is polynomially solvable. Once a solution to RNF problem is found, we use information theoretic methods to optimize multiple description code to maximize the overall fidelity of the source reconstruction at end users.

Future Directions:

      Optimized source network coding can have far reaching implications on the real time network multimedia applications. My goal is to combine my knowledge of P2P networking with our new results in network source coding into a single, highly optimized P2P multimedia application. In such an application, members of a P2P network are able to broadcast multimedia contents in real time without the requirement for any central streaming server or multicast backbone. This can be made possible only with cooperation of all the members. The source coding strategy as well as the routes are optimized using our new results on network source coding.

• Long-term Research Plans and Conclusion

 

In the future, I believe collaborative and network computation will essentially replace the traditional client/server computation model. Computation Clients will be able to pool their computation power and to use computation power by logging into a computation web, just as one uses electric power by plugging into a power outlet on the wall. Network computation, is the science that makes this possible.

 

The interdisciplinary nature of my graduate work has given me the opportunity to collaborate with several professors and graduate students from different research areas and universities. Also, I have been a collaborator with fellow graduate students in my group, each working on different projects. My research experience has shown me that collaboration and constructive discussions are keys to producing high-quality results. I believe network computation will potentially be utilized in applications for different disciplines. Fortunately, different application domains tend to create new sets of problems as a result of each domain’s particular constraints and requirements. Therefore, a research effort is needed to address the issues arising in this new application domain. I am eagerly looking forward to collaborating with other researchers in order to extend my current results to new application domains or to develop novel techniques for them.