Publications

Monographs

  1. C. Fragouli and E. Soljanin, Network Coding Fundamentals, Foundations and Trends in Networking, Now Publishers, June 2007.
  2. C. Fragouli and E. Soljanin, Network Coding Applications, Foundations and Trends in Networking, Now Publishers, January 2008.

Book chapters

  1. K. Argyraki, C. Fragouli and L. Keller, Multipath diversity and robustness for sensor networks, chapter in Sensor Networks - Where Theory Meets Practice, Springer-Verlag, 2009.
  2. C. Fragouli, Network coding for Sensor Network Applications, chapter in Handbook on Array Processing and Sensor Networks, IEEE-Wiley, 2009.

Journal and conference papers

A PHP Error was encountered

Severity: Warning

Message: Creating default object from empty value

Filename: gettext/gettext.inc

Line Number: 195

Preprints

  1. L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network Coding for Reliable Sensor Networks, ACM Transactions on Sensor Networks, 9:2, 2013
    Download:  
    Citation: BibTeX RIS
    Designing a communication protocol for sensor networks often involves obtaining the “right” trade-off be- tween energy efficiency and end-to-end packet error rate. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks—and, to the best of our knowledge, the first such implemented pro- tocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing end-to-end packet error rate in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it reduces end-to-end packet error rate in highly dynamic environments, while consuming a comparable amount of network resources. We have implemented SenseCode as a TinyOS module and evaluate it through extensive TOSSIM simulations.
  2. J. Ebrahimi and C. Fragouli, Combinatorial algorithms for wireless information flow, ACM Transactions on Algorithms, 2011
    Download:  
    Citation: BibTeX RIS
    A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this paper, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
  3. H. Seferoglu, L. Keller, A. Markopoulou and C. Fragouli, SmartCast: Cooperative video streaming on smartphones, in IEEE Allerton Conference on Communications, Control and Computing, 2011
    Download:  
    Citation: BibTeX RIS
    Video applications are increasingly popular over smartphones. However, in current cellular systems, the downlink data rate fluctuates and the loss rate can be quite high. We are interested in the scenario where a group of smartphone users, within proximity of each other, are interested in viewing the same video at the same time and are also willing to cooperate with each other. We propose a system that maximizes the video quality by appropriately using all available resources, namely the cellular connections to the phones as well as the device-to-device links that can be established via Bluetooth or WiFi. Key ingredients of our design are: (i) the cooperation among users, (ii) network coding, and (iii) exploiting broadcast in the mobile-to-mobile links. Our approach is grounded on a network utility maximization formulation of the problem. We present numerical results that demonstrate the benefit of our approach, and we implement a prototype on android phones.
  4. P. Sattari, A. Markopoulou and C. Fragouli, Inferring Logical Topologies using Network Coding, N/A, 2010
     
    Citation: BibTeX RIS
    The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity, etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. Our main idea behind using network coding is to introduce topologydependent correlation, which can be exploited at the receivers to infer the topology. We explored this idea in [33] for trees. We also combined network coding and tomographic techniques to infer the topology of a Directed Acyclic Graph (DAG), under specific routing assumptions, in [34]. The supporting idea in [34] was to decompose a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem into multiple two source, two receiver subproblems, as shown in [12]. In this paper, we unify and extend our two previous pieces of work. Our main contribution is that when intermediate nodes perform network coding, topological information contained in network coded packets allows to uniquely identify a tree topology, or to accurately distinguish among all different 2-by-2 subnetwork components in a general DAG; this knowledge can then be used to merge the subnetworks and reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
  5. C. Fragouli, A. Markopoulou and M. Gjoka, A network coding approach to network tomography, IEEE Transactions on Information Theory, 2009
     
    Citation: BibTeX RIS
  6. S. Mohajer, S. N. Diggavi, C. Fragouli and D. Tse, Approximate capacity of a class of gaussian interference-relay networks, IEEE Transactions on Information Theory, 2009
     
    Citation: BibTeX RIS
  7. M. Jafari Siavoshani, C. Fragouli and S. N. Diggavi, Subspace properties of network coding and their applications, IEEE Transactions on Information Theory, 2008
     
    Citation: BibTeX RIS

2013

  1. E. Onaran, M. Gatzianas and C. Fragouli, Broadcast erasure channel with feedback: the two multicast case - algorithms and bounds, in IEEE Symposium on Network Coding (NetCod), 2013
    Download:  
    Citation: BibTeX RIS
  2. K. Argyraki, S. Diggavi, M. Duarte Gelvez, C. Fragouli, M. A. Gkatzianas and P. Kostopoulos, Creating Secrets out of Erasures, in Proceedings of the ACM Conference on Mobile Computing and Networking (MobiCom), Miami, Florida, USA, 2013
    Download:  
    Citation: BibTeX RIS
    Current security systems often rely on the adversary's computational limitations. Wireless networks offer the opportunity for a different, complementary kind of security, which relies on the adversary's limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We present a system that leverages this opportunity to enable N wireless nodes to create a shared secret S, in a way that an eavesdropper, Eve, obtains very little information on S. Our system consists of two steps: (1) The nodes transmit packets following a special pattern, such that Eve learns very little about a given fraction of the transmitted packets. This is achieved through a combination of beam forming (from many different sources) and wiretap codes. (2) The nodes participate in a protocol that reshuffles the information known to each node, such that the nodes end up sharing a secret that Eve knows very little about. Our protocol is easily implementable in existing wireless devices and scales well with the number of nodes; these properties are achieved through a combination of public feedback, broadcasting, and network coding. We evaluate our system through a 5-node testbed. We demonstrate that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.
  3. I. Safaka, C. Fragouli, K. Argyraki and S. Diggavi, Exchanging Pairwise Secrets Efficiently, in Proceedings of the 32nd Annual IEEE International Conference on Computer Communications (INFOCOM), Turin, Italy, 2013
    Download:  
    Citation: BibTeX RIS
    We consider the problem where a group of wireless nodes, connected to the same broadcast domain, want to create pairwise secrets, in the presence of an adversary Eve, who tries to listen in and steal these secrets. Existing solutions assume that Eve cannot perform certain computations (e.g., large-integer factorization) in useful time. We ask the question: can we solve this problem without assuming anything about Eve's computational capabilities? We propose a simple secret-agreement protocol, where the wireless nodes keep exchanging bits until they have agreed on pairwise secrets that Eve cannot reconstruct with very high probability. Our protocol relies on Eve's limited network presence (the fact that she cannot be located at an arbitrary number of points in the network at the same time), but assumes nothing about her computational capabilities. We formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure (it leaks zero information to Eve about the secrets). Using a small wireless testbed of smartphones, we provide experimental evidence that it is feasible for 5 nodes to create thousands of secret bits per second, with their secrecy being independent from the adversary's capabilities.
  4. L. Czap, V. M. Prabhakaran, S. Diggavi and C. Fragouli, Exploiting Common Randomness: a Resource for Network Secrecy, in IEEE Information Theory Workshop (ITW), 2013
     
    Citation: BibTeX RIS
  5. E. Atsan, I. Safaka, L. Keller and C. Fragouli, Low cost security for sensor networks, in Proceedings of the 2013 IEEE International Symposium on Network Coding (NetCod), Calgary, Canada, 2013
    Download:  
    Citation: BibTeX RIS
    We design and evaluate a lightweight encryption protocol suitable for sensor networks, that enables weak security in the presence of passive eavesdroppers. At every communication round, our protocol creates a key between each sensor node and the sink, by appropriately mixing and coding information packets that the nodes passively overhear. Evaluation using the TOSSIM simulator indicates that with our protocol we can gain significant security benefits at low overhead cost.
  6. S. Brahma, C. Fragouli and A. Ozgur, On the structure of approximately optimal schedules for half-duplex diamond networks, in Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 2013
     
    Citation: BibTeX RIS
  7. S. Brahma and C. Fragouli, Pliable Index Coding - The Multiple Requests Case, in Proceedings of the IEEE International Symposium on Infromation Theory (ISIT), 2013
     
    Citation: BibTeX RIS
  8. M. Duarte Gelvez, A. Sengupta, S. Brahma, C. Fragouli and S. Diggavi, Quantize-Map-Forward (QMF) Relaying - An Experimental Study, 2013
     
    Citation: BibTeX RIS
  9. L. Czap, C. Fragouli, V. Prabhakaran and S. Diggavi, Secure Network Coding with Erasures and Feedback, in Annual Allerton Conference on Communication, Control, and Computing, 2013
    Download:  
    Citation: BibTeX RIS
  10. L. Czap, V. M. Prabhakaran, S. Diggavi and C. Fragouli, Securing Broadcast Against Dishonest Receivers, in IEEE Symposium on Network Coding (NetCod), 2013
    Download:  
    Citation: BibTeX RIS
  11. S. Athanasiadou, M. Gatzianas, L. Georgiadis and L. Tassiulas, Stable and capacity achieving XOR-based policies for the broadcast erasure channel with feedback, 2013
     
    Citation: BibTeX RIS

2012

  1. P. Sattari, C. Fragouli and A. Markopoulou, Active topology inference using network coding, Physical Communication, 2012
     
    Citation: BibTeX RIS
  2. L. Czap, V. Prabhakaran, S. N. Diggavi and C. Fragouli, Broadcasting Private Messages Securely, in IEEE International Symposium on Information Theory (ISIT), IEEE, 2012
    Download:  
    Citation: BibTeX RIS
  3. I. Safaka, C. Fragouli, K. Argyraki and S. Diggavi, Creating shared secrets out of thin air, in Proceedings of the 11th ACM Workshop on Hot Topics in Networks, Redmond, Washington, ACM, 2012
     
    Citation: BibTeX RIS
  4. M. Gatzianas, S. Saeedi and C. Fragouli, Feedback-based coding algorithms for broadcast erasure channels with degraded message sets, in Proceedings NETCOD, 2012
    Download:  
    Citation: BibTeX RIS
  5. N. Karamchandani, L. Keller, C. Fragouli and M. Franceschetti, Function computation via subspace coding, Physical Communication, 2012
    Download:  
    Citation: BibTeX RIS
    This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.
  6. S. S. Bidokhti, V. M. Prabhakaran, S. Diggavi and others, Is non-unique decoding necessary?, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012
     
    Citation: BibTeX RIS
  7. L. Keller, A. Le, B. Cici, H. Seferoglu, C. Fragouli and A. Markopoulou, Microcast: Cooperative video streaming on smartphones, in Proceedings of the 10th international conference on Mobile systems, applications, and services, ACM, 2012
    Download:  
    Citation: BibTeX RIS
    Video streaming is one of the increasingly popular, as well as demanding, applications on smartphones today. In this paper, we consider a group of smartphone users, within proximity of each other, who are interested in watching the same video from the Internet at the same time. The common practice today is that each user downloads the video independently using her own cellular connection, which often leads to poor quality. We design, implement, and evaluate a novel system, MicroCast, that uses the resources on all smartphones of the group in a cooperative way so as to improve the streaming experience. Each 4 phone uses simultaneously two network interfaces: the cellular to connect to the video server and the WiFi to connect to the rest of the group. Key ingredients of our design include the following. First, we propose a scheduling algorithm, MicroDownload, that decides which parts of the video each phone should download from the server, based on the phones’ download rate. Second, we propose a novel all-to-all local dissemination scheme, MicroNC-P2, for sharing content among group members, which outperforms state-of-the-art peer-to-peer schemes in our setting. MicroNC-P2 is designed to exploit WiFi overhearing and network coding, based on a local packet broadcast framework, MicroBroadcast, which we developed specifically for Android phones. We evaluate MicroCast on a testbed consisting of seven Android phones, and we show that it brings significant performance benefits without battery penalty.
  8. A. Le, L. Keller, C. Fragouli and A. Markopoulou, MicroPlay: a networking framework for local multiplayer games, in Proceedings of the first ACM international workshop on Mobile gaming, ACM, 2012
    Download:  
    Citation: BibTeX RIS
    Smartphones are an ideal platform for local multiplayer games, thanks to their computational and networking capabilities as well as their popularity and portability. However, existing game engines do not exploit the locality of players to improve game latency. In this paper, we propose MicroPlay, a complete networking framework for local multiplayer mobile games. To the best of our knowledge, this is the first framework that exploits local connections between smartphones, and in particular, the broadcast nature of the wireless medium, to provide smooth, accurate rendering of all players with two desired properties. First, it performs direct-input rendering (i.e., without any inter- or extrapo- lation of game state) for all players; second, it provides very low game latency. We implement a MicroPlay prototype on Android phones, as well as an example multiplayer car racing game, called Racer, in order to demonstrate MicroPlay’s capabilities. Our experiments show that cars can be rendered smoothly, without any prediction of state, and with only 20–30 ms game latency.
  9. M. J. Siavoshani and C. Fragouli, Multi-terminal secrecy in a linear non-coherent packetized networks, in Network Coding (NetCod), 2012 International Symposium on, IEEE, 2012
     
    Citation: BibTeX RIS
  10. S. S. Bidokhti, V. M. Prabhakaran and S. N. Diggavi, On Multicasting Nested Message Sets over Combination Networks, in IEEE Information Theory Workshop (ITW), 2012
     
    Citation: BibTeX RIS
  11. A. Sengupta, I. -. Wang and C. Fragouli, Optimizing Quantize-Map-and-Forward in Slow Fading Relay Networks, in 2012 50Th Annual Allerton Conference On Communication, Control, And Computing (Allerton), Ieee, 2012
     
    Citation: BibTeX RIS
    Quantize-Map-and-Forward (QMF) relaying has been shown to achieve the optimal diversity-multiplexing trade-off (DMT) for the slow fading single-antenna relay channel, regardless of whether the relay is full-duplex or half-duplex. A key reason for the DMT optimality is that quantizing at the noise level suffices to achieve the cut-set bound approximately and hence the relay does not need any instantaneous channel state information (CSI). However, DMT only captures the high SNR performance and potentially, limited CSI at the relay can help improve the performance in moderate SNR regimes. In this work we propose an optimization framework for QMF relaying in slow fading relay channels. Focusing on vector Gaussian quantizers, for the full-duplex relay we optimize the outage probability by finding the best quantization level according to the available CSI at the relay and the channel statistics. For the half-duplex relay we find good relay schedules using the same framework. Numerical evaluations show the improvement of taking the CSI into account over noise-level quantization and static schedules in moderate SNR regimes.
  12. S. Brahma and C. Fragouli, Pliable index coding, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012
     
    Citation: BibTeX RIS
  13. J. B. Ebrahimi and C. Fragouli, Properties of network polynomials, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012
     
    Citation: BibTeX RIS
  14. E. Drinea, L. Keller and C. Fragouli, Real-time delay with network coding and feedback, Physical Communication, 2012
    Download:  
    Citation: BibTeX RIS
    We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of μ messages to several receivers. The sender can broadcast a single message or a combination of messages at each timestep, through separate erasure channels. Receivers provide feedback as to whether the transmission was received. If, at some time step, a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel in that it combines coding techniques with feedback information to the end of minimizing delay. We show that it allows Θ(μ) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay compared to online algorithms without feedback. Our main complexity result is that the offline minimization problem is NP-hard both under scheduling and coding algorithms. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.
  15. S. Brahma, A. Ozgur and C. Fragouli, Simple schedules for half-duplex networks, in Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, IEEE, 2012
     
    Citation: BibTeX RIS
  16. M. J. Siavoshani, C. Fragouli and S. N. Diggavi, Subspace properties of network coding and their applications, Information Theory, IEEE Transactions on, 58:5, 2012
     
    Citation: BibTeX RIS
  17. E. Atsan, R. Knopp, S. N. Diggavi and C. Fragouli, Towards integrating Quantize-Map-Forward relaying into LTE, in Information Theory Workshop (ITW), IEEE, 2012
     
    Citation: BibTeX RIS
    We present a method to integrate the Quantize-Map-Forward (QMF) relaying scheme into the standard LTE operation, for a two-relay diamond network configuration. Our approach implements QMF using mainly existing LTE modules and functionalities, and results in minimal changes in the standard link-layer LTE operation. In particular, the destination operation is only affected in that we adapt the log-likelihood ratio (LLR) calculations at the decoder input to take into account the existence of relays; thus, the decoding complexity and operations (apart the LLR calculations) are not modified. We report extensive performance evaluations of our scheme using the OpenAirInterface (OAI) link-level simulation tools.
  18. Y. Buyukalp, G. Maatouk, V. M. Prabhakaran and C. Fragouli, Untrusting network coding, in Network Coding (NetCod), 2012 International Symposium on, IEEE, 2012
     
    Citation: BibTeX RIS

2011

  1. C. Neuberg, P. Papadimitratos, C. Fragouli and R. Urbanke, A mobile world of security, in CISS, 2011
     
    Citation: BibTeX RIS
  2. L. Keller, A. Karaagac, C. Fragouli and K. Argyraki, A network coding approach to the sniper detection problem, in IEEE Wireless Measurements Workshop (WinMee), 2011
    Download:  
    Citation: BibTeX RIS
    This paper experimentally studies the reliability and delay of flooding based multicast protocols for a sniper detection application. In particular using an emulator it studies under which conditions protocols based on network coding deliver performance improvements compared to classic flooding. It then presents an implementation of such protocols on mobile phones.
  3. J. Ebrahimi and C. Fragouli, Algorithms for vector network coding, IEEE Transactions on Information Theory (Special Issue on Facets of Coding Theory: from Algorithms to Networks), 2011
    Download:  
    Citation: BibTeX RIS
    We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L x L coding matrices that play a similar role as coding coefficients in scalar coding. We start our work by extending the algebraic framework developed for multicasting over graphs in [1] to include operations over matrices; we build on this generalized framework, to provide a new approach for both scalar and vector code design which attempts to minimize the employed field size and employed vector length, while selecting the coding operations. Our algorithms also lead as a special case to network code designs that employ structured matrices.
  4. S. Mohajer, S. N. Diggavi, C. Fragouli and D. Tse, Approximate capacity of a class of relay-interference networks, IEEE Transactions on Information Theory, 57:5, 2011
     
    Citation: BibTeX RIS
  5. S. Georghiu, S. Saeedi, C. Fragouli and A. Toledo, Degraded multicasting with network coding over the combination network, in IEEE International Symposium on Network Coding (NetCod), 2011
     
    Citation: BibTeX RIS
  6. S. Saeedi and C. Fragouli, Degraded two-message multicast over graphs, in IEEE International Symposium on Information Theory (ISIT), 2011
     
    Citation: BibTeX RIS
  7. A. Sengupta, S. Brahma, A. Ozgur, C. Fragouli and S. Diggavi, Graph-based codes for Quantize-Map-and-Forward relaying, in Information Theory Workshop (ITW), 2011 IEEE, IEEE, 2011
     
    Citation: BibTeX RIS
  8. M. Jafari Siavoshani, S. Mishra, S. N. Diggavi and C. Fragouli, Group secret key agreement over state-dependent wireless broadcast channels, in IEEE International Symposium on Information Theory (ISIT), 2011
     
    Citation: BibTeX RIS
  9. P. Sattari, A. Markopoulou and C. Fragouli, Maximum likelihood estimation for multiple-source loss tomography with network coding, in IEEE International Symposium on Network Coding (NetCod), 2011
     
    Citation: BibTeX RIS
  10. C. Fragouli, Network coding: beyond throughput benefits, Special Issue on Network Coding at the Proceedings of the IEEE, 2011
    Download:  
    Citation: BibTeX RIS
  11. C. Nazaroglu, A. Ozgur, J. Ebrahimi and C. Fragouli, Network simplification: the Gaussian diamond network with Multiple Antennas, in IEEE International Symposium on Information Theory (ISIT), 2011
     
    Citation: BibTeX RIS
  12. L. Czap and C. Fragouli, On secure key exchange in wireless networks, in IEEE International Symposium on Network Coding (NetCod), 2011
     
    Citation: BibTeX RIS
  13. M. Jafari Siavoshani, S. Mohajer, C. Fragouli and S. N. Diggavi, On the capacity of non-coherent network coding, IEEE Transactions on Information Theory (Special Issue on Facets of Coding Theory: from Algorithms to Networks), 57:2, 2011
     
    Citation: BibTeX RIS
    We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized network coding operations on the source packets. We propose a channel model for the non-coherent network coding introduced by Koetter and Kschischang in [6], that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.
  14. V. Venkatesan, I. Iliadis, C. Fragouli and R. Urbanke, Reliability of clustered vs. declustered replica placement in data storage systems, in IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), 2011
     
    Citation: BibTeX RIS
  15. L. Czap, V. Prabhakaran, C. Fragouli and S. N. Diggavi, Secret message capacity of erasure broadcast channels with feedback, in IEEE Information Theory Workshop (ITW), 2011
     
    Citation: BibTeX RIS

2010

  1. J. Ebrahimi and C. Fragouli, Algebraic techniques for deterministic networks, in International conference on Signal Processing and Communications (SPCOM), 2010
     
    Citation: BibTeX RIS
  2. V. Venkatesan, I. Iliadis, X. Hu, R. Haas and C. Fragouli, Effect of Replica Placement on the Reliability of Large-Scale Data Storage Systems, Modeling, Analysis, and Simulation of Computer Systems, International Symposium on, 2010
    Download:  
    Citation: BibTeX RIS
    Replication is a widely used method to protect largescale data storage systems from data loss when storage nodes fail. It is well known that the placement of replicas of the different data blocks across the nodes affects the time to rebuild. Several systems described in the literature are designed based on the premise that minimizing the rebuild times maximizes the system reliability. Our results however indicate that the reliability is essentially unaffected by the replica placement scheme. We show that, for a replication factor of two, all possible placement schemes have mean times to data loss (MTTDLs) within a factor of two for practical values of the failure rate, storage capacity, and rebuild bandwidth of a storage node. The theoretical results are confirmed by means of event-driven simulation. For higher replication factors, an analytical derivation of MTTDL becomes intractable for a general placement scheme. We therefore use one of the alternate measures of reliability that have been proposed in the literature, namely, the probability of data loss during rebuild in the critical mode of the system. Whereas for a replication factor of two this measure can be directly translated into MTTDL, it is only speculative of the MTTDL behavior for higher replication factors. This measure of reliability is shown to lie within a factor of two for all possible placement schemes and any replication factor. We also show that for any replication factor, the clustered placement scheme has the lowest probability of data loss during rebuild in critical mode among all possible placement schemes, whereas the declustered placement scheme has the highest probability. Simulation results reveal however that these properties do not hold for the corresponding MTTDLs for a replication factor greater than two. This indicates that some alternate measures of reliability may not be appropriate for comparing the MTTDL of different placement schemes.
  3. L. Keller, N. Karamchandani and C. Fragouli, Function computation over linear channels, in IEEE International Symposium on Network Coding (NetCod), 2010
    Download:  
    Citation: BibTeX RIS
    This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.
  4. N. Karamchandani, L. Keller, C. Fragouli and M. Franceschetti, Function computation via subspace coding, in IEEE International Symposium on Information Theory (ISIT), 2010
    Download:  
    Citation: BibTeX RIS
    This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for computing functions, that requires intermediate nodes to be aware of the function to be computed, our designs are transparent to the intermediate node operations.
  5. L. Keller, M. Jafari Siavoshani, K. Argyraki, C. Fragouli and S. N. Diggavi, Joint identity-message coding for sensor networks, IEEE JSAC on Wireless Sensor Networks, 2010
    Download:  
    Citation: BibTeX RIS
    In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit---for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occurred, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how communication should happen in such identity-aware sensor networks. We calculate theoretical performance bounds for this type of communication, where ``performance'' refers to the number of transmitted bits. We propose a communication protocol, where the identity and message of each source are specified jointly using subspace coding. We show through analysis and simulation that our protocol's performance is close to optimal and compare it to the performance of a traditional protocol, where identity and message are specified separately.
  6. J. Ebrahimi and C. Fragouli, Multicasting algorithms for deterministic networks, in IEEE Information Theory Workshop (ITW), 2010
    Download:  
    Citation: BibTeX RIS
    We present a polynomial time algorithm for multicasting rate h to N receivers over deterministic networks. Our algorithm requires intermediate network nodes to perform coding operations over vectors of a finite length L, through multiplication with L #x00D7; L binary coding matrices that play the same role as coding coefficients over graphs. Our code design consists in selecting these matrices so that each receiver is able to recover the source information. As a special case, we provide an alternative construction for a unicast algorithm over deterministic networks.
  7. R. Appuswamy, E. Atsan, C. Fragouli and M. Franceschetti, On relay placement for deterministic line networks, in IEEE Wireless Network Coding Workshop (WiNC), 2010
    Download:  
    Citation: BibTeX RIS
    We consider a unicast communication problem where a source transmits information to a destination through a wireless network with the help of k relays positioned on a line. We adopt the linear deterministic model to capture the wireless signal interactions and study the optimal placement of the relays so that the capacity from the source to the destination in the deterministic network is maximized. Analytical results are provided for a number of special cases, and the insights gained are used to provide a heuristic framework for designing large relay networks.
  8. J. Ebrahimi and C. Fragouli, On the benefits of vector network coding, in 48th Annual Allerton Conference on Communication, Control, and Computing, 2010
    Download:  
    Citation: BibTeX RIS
    In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L x L coding matrices that play a similar role as coding coefficients in scalar coding. Vector network coding generalizes scalar coding, and thus offers a wider range of solutions over which to optimize. This paper starts exploring the new possibilities vector network coding can offer along two directions. First, we propose a new randomized algorithm for vector network coding. We compare the performance of our proposed algorithm with the existing randomized algorithms in the literature over a specific class of networks. Second, we explore the use of structured coding matrices for vector network coding. We present deterministic designs that allow to operate using rotation coding matrices and thus result in reduced encoding complexity.
  9. A. Dhulipala, C. Fragouli and A. Orlitsky, Silence based communication, IEEE Transactions on Information Theory, 56, 2010
    Download:  
    Citation: BibTeX RIS
    Communication complexity---the minimum amount of communication required---of computing a function of data held by several parties is studied. A communication model where silence is used to convey information is introduced. For this model the worst-case and average-case complexities of symmetric functions are studied. For binary-input functions the average- and worst-case complexities are determined and the protocols achieving them are described. For functions of non-binary inputs one-round communication, where each party is restricted to communicate in consecutive stages, is considered and the extra amount of communication required by one- over multi-round communication is analyzed. For the special case of ternary-input functions close lower and upper bounds on the worst-case one-round complexity are provided and protocols achieving them are described. Protocols achieving the average-case one-round complexity for ternary-input functions are also described. These protocols can be generalized to inputs of arbitrary size.
  10. J. Ebrahimi and C. Fragouli, Vector network coding, in IEEE International Symposium on Information Theory (ISIT), 2010
    Download:  
    Citation: BibTeX RIS
    We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L x L coding matrices that play a similar role as coding coefficients in scalar coding. Our algorithms for scalar network jointly optimize the employed field size while selecting the coding coefficients. Similarly, for vector coding, our algorithms optimize the length L while designing the coding matrices. These algorithms apply both for regular network graphs as well as linear deterministic networks.

2009

  1. C. Fragouli, An overview of network coding for dynamically changing networks, Int. J. Auton. Adapt. Commun. Syst., 2:1, 2009
     
    Citation: BibTeX RIS
  2. S. Mohajer, S. N. Diggavi, C. Fragouli and D. Tse, Capacity of deterministic Z-chain relay-interference network, in IEEE Information Theory Workshop (ITW), 2009
    Download:  
    Citation: BibTeX RIS
    The wireless multiple-unicast problem is considered over a layered network, where the rates of transmission are limited by the relaying and interference effect. The deterministic model introduced is used to capture the broadcasting and multiple access effects. The capacity region of the Z-chain relay-interference network is fully characterized. In order to solve the problem, we introduce a new achievability scheme based on ldquointerference neutralizationrdquo and a new analysis technique to bound the number of non-interfering (pure) signals
  3. A. Amaudruz and C. Fragouli, Combinatorial algorithms for wireless information flow, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
     
    Citation: BibTeX RIS
    A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes infeasible. In this work, we develop a polynomial time algorithm that discovers the relay encoding strategy to achieve the min-cut value in binary linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between edges to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes, thereby constructively yielding finite length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.
  4. M. Jafari Siavoshani, L. Keller, K. Argyraki and C. Fragouli, Compressed network coding vectors, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009
    Download:  
    Citation: BibTeX RIS
    In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.
  5. E. Drinea, C. Fragouli and L. Keller, Delay with network coding and feedback, in IEEE International Symposium on Information Theory (ISIT), 2009
    Download:  
    Citation: BibTeX RIS
    We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of mu messages to several receivers over separate erasure channels. The sender can broadcast a single message or a combination (encoding) of messages at each timestep. Receivers provide feedback as to whether the transmission was received. If at some time step a receiver cannot identify a new message, delay is incurred. Our notion of delay is motivated by real-time applications that request progressively refined input, such as the successive refinement of an image encoded using multiple description coding. Our setup is novel because it combines coding techniques with feedback information to the end of minimizing delay. It allows Theta(mu) benefits as compared to previous approaches for offline algorithms, while feedback allows online algorithms to achieve smaller delay than online algorithms without feedback. Our main complexity results are that the offline minimization problem is NP-hard when the sender only schedules single messages and that the general problem remains NP-hard even when coding is allowed. However we show that coding does offer delay and complexity gains over scheduling. We also discuss online heuristics and evaluate their performance through simulations.
  6. A. Jafarian, S. H. Lee, S. Vishwanath and C. Fragouli, Distributed Rate Allocation for Network-coded Systems, in Sensor, Mesh and Ad Hoc Communications and Networks Workshops, 2009. SECON Workshops '09. 6th Annual IEEE Communications Society Conference on, 2009
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of distributed rate allocation for a class of multicast networks employing linear network coding. The goal is to minimize the cost (for example, the sum rates allocated to each link in the network) while satisfying a multicast rate requirement for each destination in the network. In essence, this paper aims to achieve network capacity while ensuring that the cost of operation (equivalently, the rate allocated per link in the network) is minimal. This paper uses a belief propagation framework to obtain a distributed algorithm for the rate allocation problem. Simulation results are presented to demonstrate the convergence of this algorithm to the optimal rate allocation solution.
  7. L. Keller, M. Jafari Siavoshani, C. Fragouli, K. Argyraki and S. N. Diggavi, Identity aware sensor networks, in INFOCOM 2009, IEEE, 2009
    Download:  
    Citation: BibTeX RIS
    In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.
  8. C. Fragouli, K. Argyraki and L. Keller, Multipath Diversity and Robustness for Sensor Networks, in: Sensor Networks, Springer, 2009
    Download:  
    Citation: BibTeX RIS
    Balancing energy efficiency and reliability is a common underlying goal for most information collection protocols in sensor networks. Multipath diversity has emerged as one of the promising techniques to achieve such a balance. In this chapter, we provide a unified framework for the multipath techniques in the literature and discuss their basic benefits and drawbacks. We also discuss emerging techniques from the area of network coding.
  9. P. Sattari, A. Markopoulou and C. Fragouli, Multiple source multiple destination topology inference using network coding, in Network Coding, Theory, and Applications, 2009. NetCod '09. Workshop on, 2009
    Download:  
    Citation: BibTeX RIS
    In this paper, we combine network coding and tomographic techniques for topology inference. Our goal is to infer the topology of a network by sending probes between a given set of multiple sources and multiple receivers and by having intermediate nodes perform network coding operations. We combine and extend two ideas that have been developed independently. On one hand, network coding introduces topology-dependent correlation, which can then be exploited at the receivers to infer the topology. On the other hand, it has been shown that a traditional (i.e., without network coding) multiple source, multiple receiver tomography problem can be decomposed into multiple two source, two receiver subproblems. Our first contribution is to show that, when intermediate nodes perform network coding, topological information contained in network coded packets allows to accurately distinguish among all different 2-by-2 subnetwork components, which was not possible with traditional tomographic techniques. Our second contribution is to use this knowledge to merge the subnetworks and accurately reconstruct the general topology. Our approach is applicable to any general Internet-like topology, and is robust to the presence of delay variability and packet loss.
  10. J. Goseling, C. Fragouli and S. N. Diggavi, Network coding for undirected information exchange, Communications Letters, IEEE, 13:1, 2009
    Download:  
    Citation: BibTeX RIS
    We consider the information exchange problem where each in a set of terminals transmits information to all other terminals in the set, over an undirected network. We show that the design of only a single network code for multicasting is sufficient to achieve an arbitrary point in the achievable rate region. We also provide an alternative proof for the set of achievable rate tuples.
  11. S. Saeedi, S. N. Diggavi, C. Fragouli and V. Prabhakaran, On Degraded Two Message Set Broadcast, in IEEE Information Theory Workshop (ITW), 2009
    Download:  
    Citation: BibTeX RIS
    We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P x U. Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
  12. S. Mohajer, M. Jafari Siavoshani, S. N. Diggavi and C. Fragouli, On the capacity of multisource non-coherent network coding, in Networking and Information Theory, 2009. ITW 2009. IEEE Information Theory Workshop on, 2009
    Download:  
    Citation: BibTeX RIS
    We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1 - delta2), where deltai is what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.
  13. M. Jafari Siavoshani, S. Mohajer, C. Fragouli and S. N. Diggavi, On the capacity of non-coherent network coding, in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, 2009
    Download:  
    Citation: BibTeX RIS
    The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N ges 1 receivers can also be achieved using packets of length logN bits, if the operations the intermediate nodes perform are deterministically known at the receivers. We here calculate the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.
  14. L. Keller, E. Atsan, K. Argyraki and C. Fragouli, SenseCode: Network coding for reliable sensor networks, EPFL Technical Report, in submission, 2009
     
    Citation: BibTeX RIS
    Designing a communication protocol for sensor networks often involves obtaining the ``right'' trade-off between energy efficiency and reliability. In this paper, we show that network coding provides a means to elegantly balance these two goals. We present the design and implementation of SenseCode, a collection protocol for sensor networks---and, to the best of our knowledge, the first such protocol to employ network coding. SenseCode provides a way to gracefully introduce a configurable amount of redundant information in the network, thereby increasing reliability in the face of packet loss. We compare SenseCode to the best (to our knowledge) existing alternative and show that it achieves higher reliability (typically 20%, in certain cases up to 30%), while consuming the same amount of network resources. We have implemented SenseCode as a TinyOs module, and evaluate it through TOSSIM simulations, as well as a testbed of 30 TinyNode sensors deployed in our department building

2008

  1. C. Fragouli, J. Widmer and J.-Y. Le Boudec, Efficient broadcasting using network coding, IEEE/ACM Transactions on Networking, 16, 2008
    Download:  
    Citation: BibTeX RIS
    We consider the problem of broadcasting in an ad hoc wireless network, where all nodes of the network are sources that want to transmit information to all other nodes. Our figure of merit is energy efficiency, a critical design parameter for wireless networks since it directly affects battery life and thus network lifetime. We prove that applying ideas from network coding allows to realize significant benefits in terms of energy efficiency for the problem of broadcasting, and propose very simple algorithms that allow to realize these benefits in practice. In particular, our theoretical analysis shows that network coding improves performance by a constant factor in fixed networks. We calculate this factor exactly for some canonical configurations. We then show that in networks where the topology dynamically changes, for example due to mobility, and where operations are restricted to simple distributed algorithms, network coding can offer improvements of a factor of , where is the number of nodes in the network. We use the insights gained from the theoretical analysis to propose low-complexity distributed algorithms for realistic wireless ad hoc scenarios, discuss a number of practical considerations, and evaluate our algorithms through packet level simulation.
  2. C. Fragouli, Network coding for dynamically changing networks, IEEE International Wireless Communications and Mobile Computing Conference, 2008
    Download:  
    Citation: BibTeX RIS
    We here advocate the case for network coding as a guiding paradigm for the operation of networks that vary in a small time frame, due to node mobility, channel variations, and varying traffic conditions. Three ideas that appeared succesively in time brought in place an elegant operation for network coding in such environments. These are, use of randomized network coding for intermediate node operation, use of generations to avoid synchronization, and use of subspace coding to allow for small packet sizes. Information theoretical performance limits support these results.
  3. L. Loyola, T. D. Souza, J. Widmer and C. Fragouli, Network-coded broadcast: from canonical networks to random topologies, Network Coding Workshop: Theory and Applications, 2008
    Download:  
    Citation: BibTeX RIS
    We consider the problem of finding the minimum number of transmissions in an ad-hoc network for all-to-all broadcasting using network coding. This work generalizes previous results for canonical topologies such as the circle and the wrap around grid to the finite-sized line, and non-wrap-around grid. The latter topologies better reflect network coding in random topologies, since the dissemination of information is "directional", in a sense that information usually arrives via the neighbors on the path to its originator instead of from all possible directions. We find that while the line topology requires a higher number of transmissions compared to the circle, this is interestingly not the case for the grid. We further present simulation results on a heuristic that estimates the required minimum number of transmissions in random wireless topologies and compare it to the optimum solution, as well as previously proposed heuristics.
  4. M. Jafari Siavoshani, C. Fragouli and S. N. Diggavi, Noncoherent multi-source network coding, IEEE International Symposium on Information Theory (ISIT), 2008
    Download:  
    Citation: BibTeX RIS
    We examine the problem of multiple sources transmitting information to one or more receivers that require the information from all the sources, over a network where the network nodes perform randomized network coding. We consider the noncoherent case, where neither the sources nor the receivers have any knowledge of the intermediate nodes operations. We formulate a model for this problem, inspired from block- fading noncoherent MIMO communications. We prove, using information theoretic tools, that coding over subspaces is sufficient to achieve the capacity, and give bounds for the capacity. We then examine the associated combinatorial problem of code design. We extend the work by Koetter and Kschischang [3] to code constructions for the multisource case. Our constructions can also be viewed as coding for the noncoherent multiple-access finite-field channel.
  5. M. Jafari Siavoshani, C. Fragouli and S. N. Diggavi, On Locating Byzantine Attackers, Network Coding Workshop: Theory and Applications, 2008
    Download:  
    Citation: BibTeX RIS
    We examine networks that employ network coding, and are subject to Byzantine attacks. We consider systems where an appropriate network error correcting scheme is employed that is able to correct (up to a certain number of) Byzantine errors. Given this setup, we formulate the problem of locating these malicious nodes that insert errors. We utilize the subspace properties of (randomized) network coding to develop algorithms to locate the Byzantine attackers.
  6. L. Keller, E. Drinea and C. Fragouli, Online Broadcasting with Network Coding, in Network Coding, Theory and Applications, 2008. NetCod 2008. Fourth Workshop on, 2008
    Download:  
    Citation: BibTeX RIS
    Consider a source broadcasting M packets to N receivers over independent erasure channels, where perfect feedback is available from the receivers to the source, and the source is allowed to use coding. We investigate offline and online algorithms that optimize delay, both through theoretical analysis as well as simulation results.
  7. S. Mohajer, S. N. Diggavi, C. Fragouli and D. Tse, Transmission techniques for relay-interference networks, IEEE Allerton, 2008
     
    Citation: BibTeX RIS
    In this paper we study the relay-interference wireless network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We examine this in the context of a deterministic wireless interaction model, which eliminates the channel noise and focuses on the signal interactions. Using this model, we show that almost all the known schemes such as interference suppression, interference alignment and interference separation are necessary for relay-interference networks. In addition, we discover a new interference management technique, which we call interference neutralization, which allows for over-the-air interference removal, without the transmitters having complete access the interfering signals. We show that interference separation, suppression, and neutralization arise in a fundamental manner, since we show complete characterizations for special configurations of the relay-interference network.

2007

  1. M. Jafari Siavoshani, C. Fragouli, S. N. Diggavi and C. Gkantsidis, Bottleneck discovery and overlay management in network coded Peer-to-Peer systems, SIGCOMM INM, 2007
    Download:  
    Citation: BibTeX RIS
    The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. In this paper we study P2P networks for content distribution (such as Avalanche) that use randomized network coding techniques. The basic idea of such systems is that peers randomly combine and exchange linear combinations of the source packets. A header appended to each packet specifies the linear combination that the packet carries. In this paper we show that the linear combinations a node receives from its neighbors reveal structural information about the network. We propose algorithms to utilize this observation for topology management to avoid bottlenecks and clustering in network-coded P2P systems. Our approach is decentralized, inherently adapts to the network topology, and reduces substantially the number of topology rewirings that are necessary to maintain a well connected overlay. Moreover, this is done passively during the normal content distribution. This work demonstrates another value of using network coding and complements previous work that showed network coding achieves high utilization of the network resources.
  2. M. Gjoka, C. Fragouli, P. Sattari and A. Markopoulou, Loss Tomography in General Topologies with Network Coding, IEEE GLOBECOM, 2007
    Download:  
    Citation: BibTeX RIS
    Network tomography infers internal network characteristics by sending and collecting probe packets from the network edge. Traditional tomographic techniques for general topologies typically use a mesh of multicast trees and/or unicast paths to cover the entire graph, which is suboptimal from the point of view of bandwidth efficiency and estimation accuracy. In this paper, we investigate an active probing method for link loss inference in a general topology, where multiple sources and receivers are used and intermediate nodes are equipped with network coding, in addition to unicast and multicast, capabilities. With our approach, each link is traversed by exactly one packet, which is in general a linear combination of the original probes. The receivers infer the loss rate on all links by observing not only the number but also the contents of the received probes. In this paper: (i) we propose an orientation algorithm that creates an acyclic graph with the maximum number of identifiable edges (ii) we define probe combining coding schemes and discuss some of their properties and (iii) we present simulation results over realistic topologies using Belief-Propagation (BP) algorithms.
  3. C. Fragouli, A. Markopoulou, R. Srinivasan and S. N. Diggavi, Network monitoring: it depends on your points of view, ITA, 2007
    Download:  
    Citation: BibTeX RIS
    End-to-end active network monitoring infers network characteristics by sending and collecting probe packets from the network edge, while probes traverse the network through multicast trees or a mesh of unicast paths. Most reported methods consider given source and receiver locations and study the path selection and the associated estimation algorithms. In this paper, we show that appropriately choosing the number of sources and receivers, as well as their location, may have a significant effect on the accuracy of the estimation; we also give guidelines on how to choose the best ``points of view'' of a network for link loss monitoring purposes. Though this observation applies across all monitoring methods, we consider, in particular, networks where nodes are equipped with network coding capabilities; our framework includes as special cases the scenarios of pure multicast and network coding. We show that, in network-coding enabled networks, multiple source active monitoring can exploit these capabilities to estimate link loss rates more efficiently than purely tomographic methods. To address the complexity of the estimation problem for large networks, we also propose efficient algorithms, including the decomposition into smaller multicast inference problems, belief-propagation, and a MINC-like algorithm.
  4. C. Fragouli, D. Lun, M. Médard and P. Pakzad, On feedback for network coding, in in Proc. of 2007 Conference on Information Sciences and Systems (CISS), 2007
    Download:  
    Citation: BibTeX RIS
  5. U. Niesen, C. Fragouli and D. Tuninetti, On the capacity of line networks, IEEE Transactions on Information Theory, 53, 2007
    Download:  
    Citation: BibTeX RIS
    We consider communication through a cascade of discrete memoryless channels (DMCs). The source and destination node of this cascade are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of a fixed length. We investigate how the processing at the relays must be chosen in order to maximize the capacity of the cascade, that is, the maximum achievable end-to-end rate between the source and the destination. For infinite cascades with fixed intermediate processing length at the relays, we prove that this intermediate processing can be chosen to be identical without loss of optimality, and that the capacity of the cascade coincides with the rate of the best zero-error code of length equal to the block length of the intermediate processing. We further show that for fixed and identical intermediate processing at all relays, convergence of capacity as the length of the cascade goes to infinity is exponentially fast. Finally, we characterize how the block length of the intermediate processing must scale with the length of the cascade to guarantee a constant end-to-end rate. We prove that it is sufficient that the block length scales logarithmically with the network length in order to achieve any rate above the zero-error capacity. We show that in many cases of interest logarithmic growth is also necessary
  6. A. K. Dhulipala, C. Fragouli and A. Orlitsky, Single versus multiple rounds for distributed function computation, in Information Theory, 2007. ISIT 2007. IEEE International Symposium on, 2007
    Download:  
    Citation: BibTeX RIS
    Communication complexity of computing functions using unrestricted communication and one-round communication are compared. In the standard unrestricted communication each party could potentially communicate several times while in one-round communication each party is restricted to communicate at most once. Results on the ratio of these two complexities are provided for symmetric and asymmetric functions under different scenarios. These results are suitably illustrated with examples.
  7. M. Jafari Siavoshani, C. Fragouli and S. N. Diggavi, Subspace properties of randomized network coding, in IEEE Information Theory Workshop (ITW), 2007
    Download:  
    Citation: BibTeX RIS
    Randomized network coding has network nodes randomly combine and exchange linear combinations of the source packets. A header appended to the packet, called coding vector, specifies the exact linear combination that each packet carries. The main contribution of this work is to investigate properties of the subspacesspanned by the collected coding vectors in each network node. We use these properties to exhibit the relationship between the network topology and the subspaces collected at the nodes. This allows us to passively infer the network topology for a general class of graphs.
  8. M. Durvy, C. Fragouli and P. Thiran, Towards reliable broadcasting using ACKs, ISIT, 2007
    Download:  
    Citation: BibTeX RIS
    We propose a mechanism for reliable broadcasting in wireless networks, that consists of two components: a method for bandwidth efficient acknowledgment collection, and a coding scheme that uses acknowledgments. Our approach combines ideas from network coding and distributed space time coding.
  9. C. Fragouli, D. Katabi, A. Markopoulou, M. Medard and H. Rahul, Wireless network coding: opportunities and challenges, IEEE MILCOM, 2007
    Download:  
    Citation: BibTeX RIS
    Wireless networks suffer from a variety of unique problems such as low throughput, dead spots, and inadequate support for mobility. However, their characteristics such as the broadcast nature of the medium, spatial diversity, and significant data redundancy, provide opportunities for new design principles to address these problems. There has been recent interest in employing network coding in wireless networks. This paper explores the case for network coding as a unifying design paradigm for wireless networks, by describing how it addresses issues of throughput, reliability, mobility, and management. We also discuss the practical challenges facing the integration of such a design into the network stack.

2006

  1. C. Fragouli, J. Widmer and J.-Y. Le Boudec, A Network Coding Approach to Energy Efficient Broadcasting: from Theory to Practice, Infocom, 2006
    Download:  
    Citation: BibTeX RIS
    We show that network coding allows to realize significant energy savings in a wireless ad-hoc network, when each node of the network is a source that wants to transmit information to all other nodes. Energy efficiency directly affects battery life and thus is a critical design parameter for wireless ad-hoc networks. We propose an implementable method for performing network coding in such a setting. We analyze theoretical cases in detail, and use the insights gained to propose a practical, fully distributed method for realistic wireless ad-hoc scenarios. We address practical issues such as setting the forwarding factor, managing generations, and impact of transmission range. We use theoretical analysis and packet level simulation.
  2. D. Lun, P. Pakzad, C. Fragouli, M. Medard and R. Koetter, An Analysis of Finite-Memory Random Linear Coding on Packet Streams, 2nd Network Coding Workshop, 2006
    Download:  
    Citation: BibTeX RIS
    We consider the following packet coding scheme: The coding node has a fixed, finite memory in which it stores packets formed from an incoming packet stream, and it sends packets formed from random linear combinations of its memory contents. We analyze the scheme in two settings: as a self-contained component in a network providing reliability on a single link, and as a component employed at intermediate nodes in a block-coded end-to-end connection. We believe that the scheme is a good alternative to automatic repeat request when feedback is too slow, too unreliable, or too difficult to implement.
  3. C. Fragouli and E. Soljanin, Information Flow Decomposition for Network Coding, IEEE Trans. Inform. Theory, 2006
    Download:  
    Citation: BibTeX RIS
    The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.
  4. C. Fragouli, J. Widmer and J.-Y. Le Boudec, Network coding: an instant primer, ACM SIGCOM Computer Communication Review, 2006
    Download:  
    Citation: BibTeX RIS
    Network coding is a new research area that may have interesting applications in practical networking systems. With network coding, intermediate nodes may send out packets that are linear combinations of previously received information. There are two main benefits of this approach: potential throughput improvements and a high degree of robustness. Robustness translates into loss resilience and facilitates the design of simple distributed algorithms that perform well, even if decisions are based only on partial information. This paper is an instant primer on network coding: we explain what network coding does and how it does it. We also discuss the implications of theoretical results on network coding for realistic settings and show how network coding can be used in practice.
  5. C. Chekuri, C. Fragouli and E. Soljanin, On achievable information rates in single-source non-uniform demand networks, ISIT, 2006
     
    Citation: BibTeX RIS
    A non-uniform demand network consists of a source and a set of receivers that have different min-cut values from the source. We look at the case where the receivers would like to receive from the source a rate that is (approximately) equal to their min-cut value. We formulate this problem and its relaxations and present preliminary results.
  6. C. Chekuri, C. Fragouli and E. Soljanin, On Average Throughput Benefits and Alphabet Size in Network Coding, IEEE Trans. Inform. Theory, 2006
    Download:  
    Citation: BibTeX RIS
    We examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. We relate these benefits to the integrality gap of a standard LP formulation for the directed Steiner tree problem. We describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with $N$ receivers where network coding offers benefits proportional to $\sqrt{N}$. We also discuss other throughput measures in networks, and show how in certain classes of networks, the average throughput can be achieved uniformly by all receivers by employing vector routing and channel coding. Finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.
  7. C. Fragouli, J. Widmer and J.-Y. Le Boudec, On the benefits of network coding for wireless applications, 2nd Network Coding Workshop, 2006
    Download:  
    Citation: BibTeX RIS
    We argue that the main benefits of network coding in a wireless environment might manifest in situations where the topology dynamically changes, and operation is restricted to distributed algorithms that do not employ knowledge about the network environment. We consider several problem instances in this set-up, that include broadcasting information to all nodes of the network and collecting sensor measurements. We show that in many such cases, under some simplifying assumptions, the problem is theoretically equivalent to simple variations of the coupon collector problem. Thus network coding can offer benefits of a factor of $\log n$, where $n$ is the number of nodes and the benefits are in terms of energy efficiency, as was proven in the literature. We present simulation results under more realistic conditions that support this claim.
  8. U. Niesen, C. Fragouli and D. Tuninetti, Scaling laws for line networks: from zero-error to min-cut capacity, ISIT, 2006
    Download:  
    Citation: BibTeX RIS
    We consider communication through a cascade of $L$ identical Discrete Memory less Channels (DMCs).The source and destination node are allowed to use coding schemes of arbitrary complexity, but the intermediate relay nodes are restricted to process only blocks of $N$ symbols.It is well known that for any $L$ and $N\to\infty$ the relays can use a capacity achieving code and communicate reliably as long as the rate of this code is below the capacity of the underlying DMC. The capacity of the cascade is hence equal to the network {\em min-cut capacity}.For finite $N$ and $L\to\infty$, we showed in previous work that the optimal intermediate processing is the highest rate zero-error code of length $N$ for the underlying DMC.The capacity of the cascade coincides with the rate of this zero-error code, and is always below the {\em zero-error capacity}.In this work, we characterize how $N$ must scale with $L$ in order to achieve rates in between the zero-error and the min-cut capacity.In particular, we have observed that $N = \Theta(\log L)$ is {\em sufficient} to achieve any rate below the min-cut capacity. Here, we develop a novel upper bound on the capacity of cascades with optimal intermediate processing that applies for any $(N,L)$ pairs and use it to show that $N = \Theta(\log L)$ is {\em necessary} to achieve certain rates above the zero-error capacity. Furthermore, we propose a method to evaluate our upper bound by establishing a connection with the Set-Cover Problem in algorithms.
  9. A. Dhulipala, C. Fragouli and A. Orlitsky, Silence based communication for sensor networks, ISIT, 2006
    Download:  
    Citation: BibTeX RIS
    We consider a power-efficient communication model for wireless sensor networks where silence is used to convey information. We study the average-case and worst-case complexities of symmetric functions under this model and describe protocols that achieve them. For binary-input functions, we determine the average complexity. For ternary-input functions, we consider a special type of protocols and provide close lower and upper bounds for their worst-case complexity. We also describe the protocol that achieves the average complexity.
  10. C. Fragouli, A. Markopoulou and S. N. Diggavi, Topology inference using network coding, Allerton, 2006
    Download:  
    Citation: BibTeX RIS
    The network coding paradigm is based on the idea that independent information flows can be linearly combined throughout the network to give benefits in terms of throughput, complexity etc. In this paper, we explore the application of the network coding paradigm to topology inference. Our goal is to infer the topology of a network using multiple sources and observations at the edges of the network. In particular, we consider networks where multiple sources send probes and intermediate nodes locally combine probe packets (perform XOR-operations in incoming links). In previous works (e.g., Ratnasamy \& McCanne '99; Duffield et al '02), the correlation between the observed packet loss patterns is used to infer the underlying topology. In contrast, our main idea behind using network coding is to introduce correlations among multiple probe packets in a topology dependent manner and also develop algorithms that take advantage of these correlations to infer the network topology from end-host observations. Preliminary numerical results illustrate the performance benefits of this approach. In particular, in the absence of packet loss, we can deterministically infer the topology, with very few probes; in the presence of packet loss, we can rapidly infer topology, even at very small loss rates (which was not the case in previous tomography techniques).

2005

  1. C. Fragouli and A. Markopoulou, A Network Coding Approach to Network Monitoring, Allerton, 2005
     
    Citation: BibTeX RIS
    Network Monitoring is a challenging problem that has received a lot of attention in the Internet community, particularly in the context of overlay networks. Independently, recent advances in Network Coding have shown that it is possible to increase network capacity and better share the available resources by allowing intermediate nodes to perform processing operations, in addition to just forwarding packets. In this work, we propose the use of Network Coding techniques to improve Network Monitoring. As a specific application, we use our approach for the well-known problem of network tomography, and in particular for inferring link loss rates from end-to-end measurements. We demonstrate that our approach can decrease the bandwidth used by probes, improve the accuracy of estimation, and decrease the complexity of selecting paths or trees to send probes. Overall, we argue that the use of Network Coding techniques shows great promise for improving several aspects of monitoring in overlay networks.
  2. P. Pakzad, C. Fragouli and A. Shokrollahi, Coding schemes for line networks, ISIT, 2005
    Download:  
    Citation: BibTeX RIS
    We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks.
  3. C. Fragouli and T. Tabet, Conditions for constant throughput in wireless networks, ACM Transactions on Sensor Networks, 2, 2005
     
    Citation: BibTeX RIS
    In this paper we propose a set of necessary and sufficient conditions under which the throughput in an ad-hoc network can remain constant as the number of nodes $n$ increases. Throughput refers to the minimum achievable rate between a source-destination pair for a given routing mechanism and physical model, when the network is shared by $\Theta(n)$ randomly chosen source-destination pairs. The main idea is to use a {\em connectivity graph}, that does not represent the actual physical network, but rather the available communication resources. This graph also allows to translate the problem of maximizing t he throughput in ad-hoc networks to the multicommodity flow problem and directly apply related results.
  4. J. Widmer, C. Fragouli and J.-Y. Le Boudec, Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding, 1st Network Coding Workshop, 2005
    Download:  
    Citation: BibTeX RIS
    Energy efficiency, i.e., the amount of battery energy consumed to transmit bits across a wireless link, is a critical design parameter for wireless ad-hoc networks. This paper examines the problem of broadcasting information to all nodes in an ad-hoc network, when a large percentage of the nodes act as sources. For this application, we theoretically quantify the energy savings that network coding can offer in the cases of a line network and a rectangular grid network. We then propose low-complexity distributed algorithms, and demonstrate through simulation that in practice, for random networks, network coding can in fact offer significant benefits in terms of energy consumption.
  5. C. Chekuri, C. Fragouli and E. Soljanin, On average throughput benefits and alphabet size in network Coding, ISIT, 2005
    Download:  
    Citation: BibTeX RIS
    We analyze a special class of configurations with $h$ sources and $N$ receivers to demonstrate the throughput benefits of network coding and deterministic code design. We show that the throughput benefits network coding offers can increase proportionally to $\sqrt{N}$, with respect to the average as well as the minimum throughput. We also show that while for this class of configurations there exists a deterministic coding scheme that realizes these benefits using a binary alphabet, randomized coding may require an exponentially large alphabet size.
  6. U. Niesen, C. Fragouli and D. Tuninetti, On cascaded channels with finite complexity processing at intermediate nodes, Allerton, 2005
    Download:  
    Citation: BibTeX RIS
    We consider communication through an infinite cascade of identical discrete memoryless channels. We allow the source and destination nodes to use coding schemes of arbitrary complexity, but restrict the intermediate (relay) nodes to process blocks of a fixed blocklength. We calculate the optimal end-to-end rate, maximized over all possible processings at the relays, and show that it coincides with the end-to-end zero-error capacity. The optimal processing is shown to be identical at each relay and to correspond to a zero-error code. We also show that the rate of convergence to the asymptotic value is exponential in the length of the cascade.
  7.  
    Citation: BibTeX RIS
    We consider a source that transmits information to a receiver by routing it over a communication network represented by a graph and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that there exist configurations where the optimal rate is achieved only when coding across independent information streams (channel coding and routing cannot be separated); that optimal processing is a function of the particular set of channel parameters and not only of the network topology; and that there exists a connection between linear codes and routing for a special class of graphs.
  8. C. Fragouli and A. Orlitsky, Silence is golden and time is money: power-aware communication for sensor networks, in 43rd Annual Allerton Conference on Communication, Control, and Computing, University of Illinois, Urbana-Champaign, USA, 2005
    Download:  
    Citation: BibTeX RIS

2004

  1. C. Fragouli and E. Soljanin, A Connection between Network Coding and Convolutional Codes, ICC, 2004
    Download:  
    Citation: BibTeX RIS
    The min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by liner re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. In this paper we discuss connections between such coding schemes and convolutional codes. We propose a method to simplify the convolutionalencoder design that is based on a subtree decompositionof the network line graph, describe the structure of the associated matrices, investigate methods to reduce decoding complexity and discuss possible binary implementation.
  2. C. Fragouli and E. Soljanin, Decentralized Network Coding, Information Theory Workshop, 2004
    Download:  
    Citation: BibTeX RIS
    This paper proposes deterministic algorithms for decentralized network coding. Decentralized coding allows to locally specify the coding operations at network nodes without knowledge of the overall network topology, and to accommodate future changes in the network such as addition of receivers. To the best of our knowledge, these are the first deterministic decentralized algorithms proposed for network coding.
  3. C. Fragouli, E. Soljanin and A. Shokrollahi, Network Coding as a Coloring Problem, CISS, 2004
    Download:  
    Citation: BibTeX RIS
    We consider a multicast configuration with two sources, and translate the network code design problem to vertex coloring of an appropriately defined graph. This observation enables to derive code design algorithms and alphabet size bounds, as well as establish a connection with a number of well-known results from discrete mathematics that increase our insight in the different trade-offs possible for network coding.
  4. C. Fragouli and E. Soljanin, On Average Throughput Benefits for Network Coding, Allerton, 2004
    Download:  
    Citation: BibTeX RIS
    We calculate the average throughput benefit that network coding can offer as compared to routing for different classes of multicast configurations over directed graphs. The averaging is over the throughput each individual receiver experiences. For the cases we examine, network coding at most doubles the average throughput.
  5. C. Fragouli, T. Tabet and C. Derdiyok, On the Throughput of Ad-Hoc Networks using Connectivity Graphs, in 42nd Annual Allerton Conference on Communication, Control, and Computing, University of Illinois, Urbana-Champaign, USA, 2004
    Download:  
    Citation: BibTeX RIS
    In this paper we propose a set of necessary and sufficient conditions under which the throughput in an ad-hoc network can remain constant as the number of nodes n increases. Throughput refers to the minimum achievable rate between a source-destination pair for a given routing mechanism and physical model, when the network is shared by \Theta(n) randomly chosen source-destination pairs. The main idea is to use a connectivity graph, that does not represent the actual physical network, but rather the available communication resources.
  6. D. Tuninetti and C. Fragouli, Processing along the way: forwarding vs. coding, ISITA, Parma, 2004
    Download:  
    Citation: BibTeX RIS
    We consider a source that transmits to a receiver by routing the information packets over a communication network and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that the processing capabilities of the intermediate nodes affect not only the end-to-end achievable rate, but also the optimal routing strategy. For example, there exist network configurations where the maximal throughput is achieved only by coding across independent information streams.
  7. C. Fragouli and E. Soljanin, Subtree Decomposition for Network Coding, ISIT, 2004
    Download:  
    Citation: BibTeX RIS
    We propose a subtree decomposition method for network coding. This approach enables derivation of tight bounds on the network code alpha- bet size, makes connections with convolutional codes transparent, allows specification of coding operations at network nodes without the knowledge of the overall network topology, and facilitates design of codes which can easily accommodate future changes in the network, such as addition of receivers and loss of links.

2003

  1. C. Fragouli, N. Al-Dhahir and W. Turin, Training-based channel estimation for multiple-antenna broadband transmissions, IEEE Transactions on Wireless Communications, vol. 2, no. 2, 2003
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. To achieve the channel estimation minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto correlation and zero cross correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto correlation. To this end, we propose to encode the training symbols with a space-time code, that may be the same or different from the space-time code that encodes the information symbols.

2002

  1. C. Fragouli, N. Al-Dhahir and W. Turin, Effect of Spatio-Temporal Channel Correlation on the Performance of Space-Time Codes, ICC 2002, NY, vol. 2, 2002
    Download:  
    Citation: BibTeX RIS
    The determinant and rank criteria used for space-time code design apply at high SNR. Code design metrics developed for low SNR assume a channel autocorrelation matrix with equal eigenvalues, which does not hold in many practical scenarios. This paper shows that a space-time code designed to ensure full diversity at high SNR can suffer significant degradation when implemented at low-to-medium SNR because of the channel autocorrelation profile. We examine the effect of the channel autocorrelation matrix on a space-time code's performance and discuss how knowledge of this matrix can be used for code design, particularly from the aspect of space-time trellis code minimum memory requirements. Our discussion applies to both flat-fading and frequency-selective channels that are treated in a unified manner.
  2. C. Fragouli, N. Al-Dhahir and W. Turin, Finite-Alphabet Constant-Amplitude Training Sequences for Multiple-Antennas, ICC 2002, NY, vol. 25, no. 1, 2002
    Download:  
    Citation: BibTeX RIS
    We propose a method to identify training sequences for multiple-antenna transmissions over quasi-static frequency-selective channels. These sequences are constructed to belong to a standard constant-amplitude 2m-PSK constellation (such as BPSK, QPSK etc) to simplify the transmitter/receiver implementation. Many practical systems use training of predetermined length. Optimal sequences do not exist for all training sequence lengths and constellation alphabets. The proposed method allows us to identify training sequences that belong to a standard constellation for an arbitrary training sequence length and an arbitrary number of unknown channel taps. Performance bounds derived indicate that these sequences achieve near-optimum performance.
  3. N. Al-Dhahir and C. Fragouli, How to choose the number of taps in a DFE?, CISS 2002, 2002
    Download:  
    Citation: BibTeX RIS
    In this paper, we address the following problem. Given a fixed total number of feedforward and feedback filter taps in a decision feedback equalizer, what is the optimum number of taps of each filter and what is the optimum delay setting? We propose a simple algorithm that resudes the solution search space from being two-dimensional to one-dimensional at a small performance loss. We demosntrate the application of our algorithm for indoor wireless channels.
  4. C. Komninakis, C. Fragouli, A. H. Sayed and R. D. Wesel, Multi-Input Multi-Output Fading Channel Tracking and Equalization using Kalman Estimation, IEEE Transactions on Signal Processing, vol. 50, 2002
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of channel tracking and equalization for multi-input multi-output (MIMO) time-varying frequency-selective channels. These channels model the effects of inter-symbol interference (ISI), co-channel interference (CCI), and noise. A low-order autoregressive model approximates the MIMO channel variation and facilitates tracking via a Kalman filter. Hard decisions to aid Kalman tracking come from a MIMO finite-length minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE), which performs the equalization task. Since the optimum DFE for a wide range of channels produces decisions with a delay ~ > 0, the Kalman filter tracks the channel with a delay. A channel prediction module bridges the time gap between the channel estimates produced by the Kalman filter and those needed for the DFE adaptation. The proposed algorithm offers good tracking behavior for multiuser fading ISI channels at the expense of higher complexity than conventional adaptive algorithms. Applications include synchronous multiuser detection of independent transmitters, as well as coordinated transmission through many transmitter/receiver antennas, for increased data rate.
  5. C. Fragouli, N. Al-Dhahir, S. N. Diggavi and W. Turin, Prefiltered M-BCJR Equalizer for MIMO Frequency-Selective Channels, IEEE Transactions on Communications, vol. 50, no. 5, 2002
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of soft equalization for space-time-coded transmissions over frequency-selective fading channels. The structure of the space-time code is embedded in the channel impulse response for efficient joint equalization and decoding. The proposed equalization/decoding approach uses a prefilter to concentrate the effective channel power in a small number of taps followed by a reduced-complexity maximum a posteriori probability (MAP) equalizer/decoder to produce soft decisions. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements such as using different prefilters for the forward and backward recursions, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the EDGE typical urban channel.
  6. C. Fragouli, N. Al-Dhahir and W. Turin, Reduced-Complexity Training Schemes for Multiple-Antenna Broadband Transmissions, WCNC 2002, vol. 3, 2002
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. As performance metric for channel estimation, mean square error is adopted. To achieve the minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto-correlation and zero cross-correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto-correlation. To this end, we propose to encode the training sequences with a space-time code, that may be the same or different from the space-time code that encodes the information symbols. Designing one instead of multiple training sequences reduces the search space significantly and simplifies the construction of optimal or suboptimal training sequences.
  7. C. Fragouli and A. Polydoros, Serially concatenated coding for broadcasting S-UMTS applications, IEEE Seventh International Symposium on Spread Spectrum Techniques and Applications, vol. 3, 2002
    Download:  
    Citation: BibTeX RIS
    Satellite-UMTS supports broadcast applications that involve transmission of the same encoded data over channels that may vary significantly. The same code must allow a user with a good channel to recover the information with low complexity, while a user with a bad channel should still be able to achieve an acceptable BER at the cost of increased complexity and/or decoding delay. To this end, we propose serially concatenated multilevel code structures that employ PSK modulation. The receiver has the flexibility to achieve turbo-code, trellis-code or uncoded performance, depending on the decoding effort. Design considerations include the constituent encoder design and the use of a non-uniform constellation. Simulation results investigate the system's performance and highlight different parameters trade-offs.
  8. N. Al-Dhahir, C. Fragouli, A. Stamoulis, W. Younis and A. R. Calderbank, Space-Time Coding for Broadband Wireless Transmission, IEEE Communications Magazine issue ``Technologies for 3G and Beyond'', vol. 40, no. 9, 2002
    Download:  
    Citation: BibTeX RIS
    We present an overview of research activities on space-time coding for broadband wireless transmission performed at AT&T Shannon Laboratory over the past two years. The emphasis is on physical layer modem algorithms such as channel estimation, equalization, and interference cancellation. However, we also discuss the impact of space-time coding gains at the physical layer on throughput at or above the networking layer. Furthermore, we describe a flexible graphical user interface attached to our physical layer simulation engine in order to explore the performance of space-time codes under a variety of practical transmission scenarios. Simulation results for the EDGE cellular system and the 802.11 wireless LAN environment are presented.
  9. C. Fragouli and A. Polydoros, Symbol-Interleaved Serially Concatenated Turbo Codes, CISS 2002, 2002
     
    Citation: BibTeX RIS

2001

  1. C. Fragouli and R. D. Wesel, Bit vs. Symbol Interleaving for Parallel Concatenated Trellis Coded Modulation, GlobeCom, vol. 2, 2001
    Download:  
    Citation: BibTeX RIS
    This paper compares bit versus symbol interleaving for parallel-concatenated trellis-coded turbo codes, employing the turbo encoder structure proposed in Benedetto et al., (1996). To compare systems optimized with the same techniques, the paper extends the turbo-encoder design procedure proposed in Fragouli et al. (2001), to bit-interleaved systems. We discuss a method to jointly design the multiple required interleavers for the bit-interleaved system, and a procedure to select constituent encoders that can take advantage of the interleaver structure to achieve a low error floor. Simulation results for the designed bit-interleaved system show better performance than bit-interleaved performance reported in the literature. The symbol-interleaved system though achieves an earlier convergence, especially with an increased number of decoder iterations, but at the cost of a slightly higher error floor.
  2. C. Fragouli, C. Komninakis and R. D. Wesel, Minimality for puncturing convolutional codes, ICC 2001, Helsinki, Finland, June, vol. 1, 2001
    Download:  
    Citation: BibTeX RIS
    This paper investigates encoders optimization for the Hamming weight after periodic puncturing, and discusses minimality issues that may affect the performance of the punctured encoders. Periodically puncturing a minimal encoder produces a higher rate encoder that may or may not be minimal. If it is not minimal, it may have a zero-output loop and it may be catastrophic. A code search can use a fast algorithm to determine whether an encoder's state diagram has a zero-output loop under periodic symbol puncturing, and a proposed method to assess the performance of codes with a zero-output loop that are not catastrophic. As an example, the paper optimizes rate-1/4 unpunctured codes for Hamming weight under both bit-wise and symbol-wise periodic puncturing. Code tables and simulation results are included.
  3. C. Fragouli, N. Al-Dhahir, S. N. Diggavi and W. Turin, Prefiltered space-Time M-BCJR Equalizer for MIMO Frequency-Selective Channels, CISS, 2001
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of soft equalization for time-variant frequency-selective channels. Such a channel arises in EDGE (Enhanced Data for GSM Evolution), third generation TDMA proposal, which employs 8-PSK modulation with a linearized GMSK pulse shaping filter that introduces strong intersymbol interference. The proposed equalization approach uses a prefilter to concetrate the effective channel power in a small number of taps, followed by a reduced complexity MAP equalizer to produce soft decision outputs. The MAP equalizer is based on the implementation of the M-algorithm in the log domain. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements, such as using a different prefilter for the forward and backward recursion, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the typical urban (TU) EDGE channel.
  4. C. Fragouli, N. Seshadri and W. Turin, Reduced-trellis equalization using a variation of the M-BCJR algorithm, Journal on Wireless Communications and Mobile Computing, vol. 1, 2001
     
    Citation: BibTeX RIS
  5. C. Fragouli, R. D. Wesel, D. Sommer and G. P. Fettweis, Turbo Codes with Non-Uniform Constellation, ICC 2001, Helsinki, Finland, vol. 1, 2001
    Download:  
    Citation: BibTeX RIS
    This paper presents parallel concatenated turbo codes that employ a non-uniform constellation to achieve shaping gain. The output signal approximates the Gaussian distribution by using equally likely signals with unequal spacing (a non-uniform constellation). The small distance of points near the center of the constellation may lead to a small overall free distance and thus a high error floor for turbo codes. We avoid this situation by a two-step design procedure, that first creates an interleaver, and then identifies the constituent encoders that maximize the turbo code free distance. Simulation results for 4 bits/sec/Hz show that this use of shaping can offer an improvement of approximately 0.2 dB for turbo codes.
  6. C. Fragouli and R. D. Wesel, Turbo encoder design for symbol interleaved parallel concatenated trellis coded modulation, IEEE Transactions on Communications, no. 3, vol. 49, 2001
    Download:  
    Citation: BibTeX RIS
    This paper addresses turbo-encoder design for coding with high spectral efficiency using parallel concatenated trellis-coded modulation and symbol interleaving. The turbo-encoder design involves the constituent encoder design and the interleaver design. The constituent encoders are optimized for symbol-wise effective free distance, and each has an infinite symbol-wise impulse response. We identify the canonical structures for the constituent encoder search space. In many cases of practical interest, the optimal structure for these constituent encoders connects the memory elements in a single row. This single row generally applies to turbo code constituent encoders for parallel concatenation and is not restricted to symbol interleaving. To lower the error floor, a new semi-random interleaver design criteria and a construction method extends the spread-interleaver concept introduced by Divsalar and Pollara (1995). Simulation results show that the proposed system employing symbol interleaving can converge at a lower signal-to-noise ratio than previously reported systems. We report simulation results between 0.5 and 0.6 db from constrained capacity for rates of 2 and 4 bits/s/Hz.

2000

  1. C. Komninakis, C. Fragouli, A. H. Sayed and R. D. Wesel, Adaptive Multi-Input Multi-Output Fading Channel Equalization using Kalman Estimation, ICC 2000, New Orleans, Louisiana, June 18-22, vol. 3, 2000
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of adaptive channel tracking and equalization for multi-input multi-output (MIMO) time-variant frequency-selective channels. A finite-length minimum-mean-squared-error decision-feedback equalizer (MMSE-DFE) performs the equalization task, while a Kalman filter tracks the MIMO channel, which models the corrupting effects of inter-symbol interference (ISI), inter-user interference (IUI), and noise. The Kalman tracking is aided by previous hard decisions produced by the DFE, with a decision delay ~>0, which causes the Kalman filter to track the channel with a delay. A channel prediction module bridges the time gap between the channel estimates produced by the Kalman filter and those needed for the DFE adaptation. The proposed algorithm offers good tracking behavior for multi-user fading ISI channels at the expense of higher complexity.
  2. C. Fragouli, N. Seshadri and W. Turin, On reduced trellis equalization using the M-BCJR Algorithm, in CISS, Boston, 2000
    Download:  
    Citation: BibTeX RIS
    The complexity of channel equalization using the BCJR algorithn [1] grows exponentially with the channel memory. The M-BCJR algorithm [2], provides a method for reduced-trellis channel equalization. This paper examines the algorithm performance for different finite impulse response channels, identifies pathological cases, and introduces designer choices such as the decision delay, maximum and minimum phase transformation, and selection of states used by the algorithm. Simulation results demonstrate the effect of the different parameters in the algorithm's performance.

1999

  1. C. Komninakis, C. Fragouli, R. D. Wesel and A. H. Sayed, Channel estimation and equalization in fading, 33rd Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, October 24-27, 1999
    Download:  
    Citation: BibTeX RIS
    This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. To achieve the channel estimation minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto correlation and zero cross correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto correlation. To this end, we propose to encode the training symbols with a space-time code, that may be the same or different from the space-time code that encodes the information symbols. Optimal sequences do not exist for all training sequence lengths and constellation alphabets. We also propose a method to easily identify training sequences that belong to a standard 2m-PSK constellation for an arbitrary training sequence length and an arbitrary number of unknown channel taps. Performance bounds derived indicate that these sequences achieve near-optimum performance.
  2. C. Fragouli and R. D. Wesel, Convolutional codes and matrix control theory, Proceedings of the 7th International Conference on Advances in Communications and Control, June 28-July 2, Athens, Greece., 1999
     
    Citation: BibTeX RIS
  3. C. Fragouli and R. D. Wesel, Semi-random interleaver design criteria, Communication Theory Symposium at Globecom 99, Rio de Janeiro, Brazil, December 5-9, 5, 1999
    Download:  
    Citation: BibTeX RIS
    A spread interleaver of length N is a semi-random interleaver based on the random selection without replacement of N integers from 1 to N under a design constraint. This paper extends the spread-interleaver design method to multiple error events, based on the interleaver's role in overall turbo code error event distances. The extension helps to explain why the spread interleaver is specifically designed to be semi-random. Simulation results show the performance achieved for a symbol-interleaved parallel concatenated trellis coded modulation (PCTCM) scheme.
  4. C. Fragouli and R. D. Wesel, Symbol interleaved parallel concatenated trellis coded modulation, Communication Theory Miniconference in conjunction with ICC '99, June 6-10 1999, 1999
    Download:  
    Citation: BibTeX RIS
    This paper presents a method for efficient coding at high spectral efficiency using parallel concatenated trellis coded modulation (PCTCM) with symbol interleaving. The constituent encoders are optimized for symbol-wise free distance, and each has an infinite symbol-wise impulse response. In many cases of practical interest, the optimal structure for these constituent encoders connects the memory elements in a single row. Simulation results show that the performance is as close as 0.5 dB to the constrained capacity.

1998

  1. Download:  
    Citation: BibTeX RIS
    A key problem in transporting multimedia traffic across wireless networks is a controlled sharing of the wireless link by different packet streams. So far this problem has been treated as that of providing support for quality of service in time division multiplexing based medium access control protocols (MAC). Adopting a different perspective to the problem, this paper describes an approach based on extending the class-based queueing (CBQ) based controlled hierarchical link sharing model proposed for the Internet. Our scheme enhances CBQ, which works well in wired links such as point-to-point wires of fixed bandwidth, to also work well with wireless links based on radio channels that are (i) inherently shared on-demand among multiple radios, and (ii) are subject to highly dynamic bandwidth variations due to spatially and temporally varying fading with accompanying burst errors. The proposed scheme is based on combining a modified version of CBQ with channel-state dependent packet scheduling.

1997

  1. P. Lettieri, C. Fragouli and M. B. Srivastava, Low power error control for wireless links, ACM/IEEE Mobicom, 1997
     
    Citation: BibTeX RIS
    Energy efficiency, which directly affects battery life and portability, is perhaps the single most important design metric in hand-held computing devices capable of mobile networking over wireless radio links. By virtue of their being relatively thin clients, a high fraction of the power consumption in portable wireless computing devices is accounted for by the transport of packet data over the wireless link. In particular, the error control strategy (eg. convolutional and block channel coding for forward error correction (FEC), ARQ protocols, hybrids) used for wireless link data transport has a direct impact on battery power consumption. Error control has traditionally been studied by channel coding researchers from the perspective of selecting an error control scheme to achieve a desired level of radio channel performance. We instead study the problem of error control from a perspective more relevant to battery operated devices: the amount of battery energy consumed to transmit bits across a wireless link. This includes both the physical transmission of useful and redundancy data, as well as the computation of the error control redundancy. We first describe a novel error control where the most battery energy efficient hybrid combination of an appropriate FEQ and ARQ protocol is chosen, and adapted over time, for each stream (ATM virtual circuit or IP/RSVP flow). Next, we present analysis and simulation results to guide the selection and adaptation of the most energy efficient error control scheme as a function of quality of service, packet size, and channel state.

publications.txt · Last modified: 2012/07/03 13:53 by lokeller
© ARNI/EPFL, 1015 Lausanne
webmaster