Salim El Rouayheb – Research

Research Summary

My research interests lie in the broad area of communications with a focus on the reliability and security of data. in distributed storage systems, networks and wireless systems. My research focuses on exploring the fundamental performance limits and developing efficient algorithms for data reliability and security in today's large-scale distributed systems. These systems are now undergoing an explosive growth under the umbrella name of ‘‘the cloud", which includes data centers, peer-to-peer (p2p) architectures and content delivery networks. In this exploration, I draw on tools from information theory, coding theory, network coding, combinatorics and probabilistic methods to find solutions. My goal is to contribute to the vision of making data seamlessly available to users anywhere and anytime over wired and wireless networks. Below, I describe research projects that I have been interested in and that are aimed toward that goal.

reliable and secure distributed information systems and on the algorithmic and information-theoretic aspects of networking.

My research focuses on exploring the fundamental performance limits and developing efficient algorithms for data reliability and security in today's large-scale distributed systems. These systems are now undergoing an explosive growth under the umbrella name of ‘‘the cloud", which includes data centers, peer-to-peer (p2p) architectures and content delivery networks. In this exploration, I draw on tools from information theory, coding theory, network coding, combinatorics and probabilistic methods, and place a special emphasis on solutions that can be implemented in real systems. For this reason, I enjoy talking to and collaborating with people in the industry to formulate new relevant problems and test new solutions. The general goal of my research is to contribute to the vision of making data seamlessly available to users anywhere and anytime over wired and wireless networks. Below, I describe three main tracks of my research work aimed toward that goal.vspace{-.2cm}

My research interests lie in the broad area of communications with a focus on reliable and secure distributed information systems and on the algorithmic and information-theoretic aspects of networking.

In my research, I seek to establish the theoretical foundations of next-generation communications systems, such as data centers, cloud and peer-to-peer (p2p) systems, with a multidisciplinary approach based on coding and information theory, combinatorics, graph theory and matroid theory.

Distributed Storage Systems

Data, in the order of petabytes, is now hailed as the ‘‘Intel Inside" of the cloud. However, the cloud is not reliable due to the use of large number of cheap commodity hardware devices. Cloud storage relies on large distributed networks of cheap storage nodes to reliably store petabytes of data. The quote from the Google File System paper puts it best: ‘‘Component failures are the norm rather than the exception." While 3-way replication is currently the industry standard for providing data reliability, it is not a scalable solution due to the huge incurred storage cost. Practitioners are now realizing the need to move to more sophisticated code-based redundancy schemes to protect the data. Classical erasure codes such as Reed-Solomon have optimal storage cost, but incur additional bandwidth, disk access and computation overheads since reproducing a coded chunk of a file requires reading, downloading and decoding the whole file. In my current research, I investigate the fundamental tradeoffs that exist among the different system resources for achieving a desired level of reliability. These resources include storage capacity, bandwidth, disk access and energy. %The majority of current cloud storage systems are hard disk based, and due to its mechanical nature disk access and reads is still a major bottleneck. I showed that it is possible to simultaneously minimize disk reads - a major system bottleneck - and repair bandwidth, at a slight storage overhead. Moreover, I proposed new codes, dubbed Distributed Replication-based Simple Storage (DRESS) codes, that can achieve these optimal tradeoffs. DRESS codes were implemented in a new cache-based distributed video-on-demand system that was built at UC Berkeley.vspace{.2cm}

{it Future directions:} A theory of cloud systems is still in a nascent state and numerous fundamental problems are still to be explored, in terms of data availability, load-balancing, caching and energy cost, to state a few. For instance, a cloud system should be able to scale and grow with little overhead and no service disruption. This requires investigating emph{‘‘elastic"} codes that are storage efficient and can distributively grow to serve increasingly popular files or move data closer to mobile users. Codes also enable a fluid abstraction of the data where any coded chunk can be helpful to a user requesting the file. Codes can therefore play an instrumental role in load-balancing techniques to minimize the emph{delay} %footnote{delay costs dollars.} in the user response time. This important role of codes is yet to be studied and analyzed. Moreover, in emph{cloud computing} applications, and particularly in the MapReduce framework, placing the data closer to compute nodes is essential in reducing the delay. Efficient algorithms with guarantees for data placement, within and across data centers, are needed to go beyond the heuristics used in practice. Another related big challenge is designing scalable solutions for video-on-demand applications over the internet. I am interested in analyzing and implementing distributed caching techniques and p2p cloud architectures which I believe are key ingredients for meeting this challenge. Answering these open questions will be essential in building the next-generation cloud systems.

Security of Distributed Storage Systems

Collaboration in Wireless Networks

The rapid growth in the popularity of data-hungry smart phones and tablets are choking the cellular networks. The main bottleneck is the last-mile wireless link between the base station and the mobile devices. In my research, I investigate new collaborative algorithms and codes that help support high data rates in next-generation wireless systems:

1. Index coding: that leverages data cached at the mobile users to reduce the bandwidth at the base station (Figure 4-a). We showed that finding optimal index codes is NP-hard and provided approximation algorithms. Moreover, we showed that linear codes can be sub-optimal by establishing a formal connection to network coding and matroid representation.

2. Data exchange: in which mobile phones “talk” to each other directly, without going through the base station, in order to obtain a file that they collectively have but individually have parts of. We devised efficient algorithms that can achieve this goal with minimum exchanged bits among the phones using network coding and combinatorial optimization techniques. Sustaining our ever-increasing appetite for high data rates is a major challenge for future wireless systems. As these systems keep approaching their theoretical physical-layer limits, collaboration methods at the network layer will play a crucial role in meeting these demands. Many questions remain open and require more investigation such as collaboration in multi-hop wireless networks (vehicular networks), caching for video-on-demand, personalized content placement and mobile support for real-time data.

Selected Publications:

1. S. El Rouayheb, M. A. R. Chaudhry and A. Sprintson, On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks, In the proceeding of IEEE Information Theory Workshop, Lake Tahoe, California, September 2007.

2. S. El Rouayheb, A. Sprintson and C. N. Georghiades, On the Index Coding Problem and its Relation to Network Coding and Matroid Theory, IEEE Transactions on Information Theory, Vol. 56, No. 7, July 2010.

3. S. El Rouayheb, A. Sprintson and P. Sadeghi, On Coding for Cooperative Data Exchange, Proceedings of IEEE Information Theory Workshop (ITW), Cairo, Egypt, January 2010.

4. N. Milosavljevic, S. Pawar, S. El Rouayheb, M. Gastpar and K. Ramchandran, An Optimal Divide-and-Conquer Solution to the Linear Data Exchange Problem, Proceedings of 2011 IEEE International Symposium on Information Theory (ISIT), St Petersburg, Russia, August 2011.

Network Coding for Security and Robustness

The recent theory of network coding has demonstrated the advantages of “mixing” (coding) information packets at intermediate nodes in the network over traditional routing algorithms. Network codes can achieve higher data throughputs and better security and fault-tolerance in networks. In my research, I have investigated the information-theoretical limits on network security against wiretapping and malicious attacks and constructed efficient network codes that can achieve these limits. In particular, I have focused on the following two problems:

1. Secrecy against eavesdropping: We investigated data secrecy in multicast (one-to-many) networks in the presence of a wiretapper. We devised polynomial-time algorithms for constructing secure network codes that achieve perfect secrecy. Our main idea was to use a coset code at the source with a “matched” multicast network code (see Figure 4-a).

2. Robustness against link attacks: Links in networks may fail or or may be the target of an adversarial attack that destroys them. Many critical applications require fast recovery in the case of such adversities. We studied constructions for robust network code over the binary field that can achieve instantaneous recovery from link attacks in networks (see Figure 4-b).
   

Selected Publications:

1. S. El Rouayheb, E. Soljanin and A. Sprintson, Secure Network Coding for Wiretap Networks of Type II, IEEE Transactions on Information Theory, Vol. 56, No. 9, March 2012.

2. S. El Rouayheb, A. Sprintson and C. N. Georghiades, Robust Network Codes for Unicast Connections: A Case Study, IEEE/ACM Transactions on Networking, Vol. 19, No. 3, June 2011.

3. S. El Rouayheb and E. Soljanin, On Wiretap Networks II, In proceedings of 2007 IEEE International Symposium on Information Theory (ISIT), Nice, France, June 2007.