Ivana Marić, Andrea Goldsmith, Muriel Médard
Abstract — A two-sender, two-receiver channel model with one relay node is considered for the case of multicast traffic. We examine two different cooperative approaches: relaying, in which the...
Minimum-Cost Multicast Over Coded Packet Networks (2009)
Desmond S. Lun, Student Member, Niranjan Ratnakar, Student Member, Muriel Médard, Senior Member, ...
Abstract—We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal...
On the Capacity of a Binary MIMO Channel with Random Interference (2009)
Răzvan Cristescu, Michelle Effros, Muriel Médard
We study the capacity of a binary multiple input multiple output (MIMO) channel with interference. Interference is modelled as a non-linear relation between the input and the output words of the...
ON THE CODING-LINK COST TRADEOFF IN MULTICAST NETWORK CODING (2009)
Minkyu Kim, Muriel Médard, Varun Aggarwal
z s bw
Jay Kumar Sundararajan, Devavrat Shah, Muriel Médard
Abstract—A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly...
Network Coding for Speedup in Switches (2009)
Minji Kim, Jay Kumar Sundararajan, Muriel Médard
Abstract — We present a graph theoretic upper bound on speedup needed to achieve 100 % throughput in a multicast switch using network coding. By bounding speedup, we show the equivalence between...
A Binary Coding Approach for Combination Networks and General Erasure Networks (2009)
Ming Xiao, Muriel Médard, Tor Aulin
Abstract — We investigate a deterministic binary coding approach for combination networks. In the literature, network coding schemes with large alphabet sizes achieve the min-cut capacity. Here, we...
Ali Par, Muriel Médard, Asuman Ozdaglar, Atilla Eryilmaz
Abstract — We consider the problem of rate allocation in a fading Gaussian multiple-access channel with fixed transmission powers. The goal is to maximize a general concave utility function of the...
1 Dynamic Rate Allocation in Fading Multiple Access Channels (2009)
Ali Par, Atilla Eryilmaz, Asuman Ozdaglar, Muriel Médard
Abstract — We consider the problem of rate allocation in a fading Gaussian multiple-access channel (MAC) with fixed transmission powers. Our goal is to maximize a general concave utility function...
1 Rate and Power Allocation in Fading Multiple Access Channels (2009)
Ali Par, Atilla Eryilmaz, Asuman Ozdaglar, Muriel Médard
Abstract — We consider the problem of rate and power allocation in a fading multiple-access channel. Our objective is to obtain rate and power allocation policies that maximize a utility function...
1 Joint Relaying and Network Coding in Wireless Networks (2009)
Sachin Katti, Ivana Marić, Andrea Goldsmith, Dina Katabi, Muriel Médard
Abstract — Relaying is a fundamental building block of wireless networks. Sophisticated relaying strategies at the physical layer have been developed for a single flow, but multiple flows are...
Layered Source-Channel Coding: A Distortion-Diversity Perspective (2009)
Sheng Jing, Lizhong Zheng, Muriel Médard
Abstract—Source-channel coding in time-varying channels without perfect side information at the transmitter suffers from uncertainty which may not always be averaged out. In channel coding, a main...
Source Coding with Distortion through Graph Coloring (2009)
Vishal Doshi, Devavrat Shah, Muriel Médard
Abstract—We consider the following rate distortion problem: given a source X and correlated, decoder side information Y, find the minimum encoding rate for X required to compute f(X, Y) at the...
Online network coding for optimal throughput and delay – the three-receiver case (2009)
Jay Kumar Sundararajan, Devavrat Shah, Muriel Médard
For a packet erasure broadcast channel with three receivers, we propose a new coding algorithm that makes use of feedback to dynamically adapt the code. Our algorithm is throughput optimal, and we...
Capacity Scaling Laws for Underwater Networks (2009)
Lucani, Daniel E., Médard, Muriel, Stojanovic, Milica
The underwater acoustic channel is characterized by a path loss that depends not only on the transmission distance, but also on the signal frequency. Signals transmitted from one user to another over...
Random Linear Network Coding for Time-Division Duplexing: Queueing Analysis (2009)
Lucani, Daniel E., Médard, Muriel, Stojanovic, Milica
We study the performance of random linear network coding for time division duplexing channels with Poisson arrivals. We model the system as a bulk-service queue with variable bulk size. A full...
Broadcasting in Time-Division Duplexing: A Random Linear Network Coding Approach (2009)
Lucani, Daniel E., Médard, Muriel, Stojanovic, Milica
We study random linear network coding for broadcasting in time division duplexing channels. We assume a packet erasure channel with nodes that cannot transmit and receive information simultaneously....
Sachin Katti, Dina Katabi, Wenjun Hu, Hariharan Rahul, Muriel Médard
This paper applies network coding to wireless mesh networks and presents the first implementation results. It introduces COPE, an opportunistic approach to network coding, where each node snoops on...
Random Linear Network Coding For Time Division Duplexing: Energy Analysis (2009)
Lucani, Daniel E., Stojanovic, Milica, Médard, Muriel
We study the energy performance of random linear network coding for time division duplexing channels. We assume a packet erasure channel with nodes that cannot transmit and receive information...
Sachin Katti, Dina Katabi, Wenjun Hu, Hariharan Rahul, Muriel Médard
This paper applies network coding to wireless mesh networks and presents the first implementation results. It introduces COPE, an opportunistic approach to network coding, where each node snoops on...
Sachin Katti, Dina Katabi, Wenjun Hu, Hariharan Rahul, Muriel Médard
This paper applies network coding to wireless mesh networks and presents the first implementation results. It introduces COPE, an opportunistic approach to network coding, where each node snoops on...
Lucani, Daniel E., Stojanovic, Milica, Médard, Muriel
A new random linear network coding scheme for reliable communications for time division duplexing channels is proposed. The setup assumes a packet erasure channel and that nodes cannot transmit and...
Lucani, Daniel E., Médard, Muriel, Stojanovic, Milica
The goal of this paper is two-fold. First, to establish a tractable model for the underwater acoustic channel useful for network optimization in terms of convexity. Second, to propose a network...
Sachin Katti, Dina Katabi, Wenjun Hu, Hariharan Rahul, Muriel Médard
This paper applies network coding to wireless mesh networks and presents the first implementation results. It introduces COPE, an opportunistic approach to network coding, where each node snoops on...
Online network coding for optimal throughput and delay -- the three-receiver case (2008)
Sundararajan, Jay Kumar, Shah, Devavrat, Médard, Muriel
For a packet erasure broadcast channel with three receivers, we propose a new coding algorithm that makes use of feedback to dynamically adapt the code. Our algorithm is throughput optimal, and we...
Resilient Network Coding in the Presence of Byzantine Adversaries (2008)
Jaggi, Sidharth, Langberg, Michael, Katti, Sachin, Ho, Tracey, Katabi, Dina, Médard, Muriel, ...
Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up...
Byzantine Modification Detection in Multicast Networks With Random Network Coding (2008)
Ho, Tracey, Leong, Ben, Koetter, Ralf, Médard, Muriel, Effros, Michelle, Karger, David R.
An information-theoretic approach for detecting Byzantine or adversarial modifications in networks employing random linear network coding is described. Each exogenous source packet is augmented with...
Channel Uncertainty in Communications Channel uncertainty in general commu- (2008)
Finally, even if a channel is quasi-static nication systems, and wireless systems and interference minimal or well known, in particular, is an unavoidable element. uncertainty regarding the channel...
Jay Kumar Sundararajan, Devavrat Shah, Muriel Médard
queueing in coded networks – queue size
Wireless Network Coding: Opportunities & Challenges (2008)
Christina Fragouli, Dina Katabi, Athina Markopoulou, Muriel Médard, Hariharan Rahul
Abstract—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...
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Michelle Effros, Jun Shi, ...
random linear network coding approach to multicast
ON THE CODING-LINK COST TRADEOFF IN MULTICAST NETWORK CODING (2008)
Minkyu Kim, Muriel Médard, Varun Aggarwal
Abstract—We investigate the issue of the tradeoff between network coding and link usage in multicast network coding. Network coding makes minimum-cost multicast, an NP-complete problem with...
A Modification to RED AQM for CIOQ Switches (2008)
Jay Kumar Sundararajan, Fang Zhao, Pamela Youssef-massaad, Muriel Médard
Abstract — In very large networks with heavy traffic, congestion control plays an important role in network resource management. One approach to this is the Active Queue Management (AQM)...
Guaranteeing the BER in Transparent Optical Networks Using OOK Signaling (2008)
Poompat Saengudomlert, Student Member, Muriel Médard, Senior Member
Abstract—A network consisting of transparent optical nodes (TONs) can provide high speed end-to-end communication paths with very low bit-error rates (BERs). However, owing to component crosstalk...
Generalized MultiProtocol Label Switching (GMPLS). The simple, (2008)
Guy Weichenberg, Muriel Médard
the throughput-cost tradeoff of multi-tiered
Processing of Wireless Signals to Preserve Wireline Network Resources (2008)
Abstract- In order increase capacity in the wireless domain, the signals from several distributed receivers may be combined. The combining of these signals typically requires transmission over a...
A Modification to RED AQM for CIOQ Switches (2008)
Jay Kumar Sundararajan, Fang Zhao, Pamela Youssef-massaad, Muriel Médard
Abstract — In very large networks with heavy traffic, congestion control plays an important role in network resource management. One approach to this is the Active Queue Management (AQM)...
Siddharth Ray, Muriel Médard, Lizhong Zheng
FAWNA: A high-speed mobile communication network architecture ∗
PERFORMANCE OF NETWORK CODING IN AD HOC NETWORKS (2008)
Joon-sang Park, Desmond S. Lun, Fabio Soldo, Mario Gerla, Muriel Médard
Abstract — Network coding, the notion of performing coding operations on the contents of packets while in transit through the network, was originally developed for wired networks; recently,...
Using Local Information for WDM Network Protection (2008)
Hungjen Wang, Eytan Modiano, Muriel Médard
Path protection and link protection schemes are the main means of protecting wavelength-division multiplexed (WDM) networks from the losses caused by a link failure such as a fiber cut. We propose a...
Online Network Coding for the Dynamic Multicast Problem (2008)
Abstract — Many of the multimedia applications such as video broadcasting and teleconferencing require the network to support dynamic multicast sessions when the membership of the multicast group...
Random Coding in Noise-Free Multiple Access Networks over Finite Fields (2008)
Siddharth Ray, Muriel Médard, Jinane Abounadi
Abstract — A two transmitter single receiver multiple access noise-free network is considered where interference is additive and the transmit and receive alphabet size is the same. We consider two...
Counteracting Byzantine adversaries with network coding: An overhead analysis (2008)
Minji Kim, Muriel Médard, João Barros
Abstract — Network coding increases throughput and is robust against failures and erasures. However, since it allows mixing of information within the network, a single corrupted packet generated by...
Capacity of Time-Slotted ALOHA Systems (2007)
Muriel Médard, Andrea J. Goldsmith, Jianyi Huang, Sean P. Meyn
. We consider the capacity of time-slotted ALOHA systems, where multiple users synchronously send packets, which may collide at the receiver. Specific coding for ALOHA systems had previously been...
Muriel Médard, Jianyi Huang, Andrea J. Goldsmith, Sean P. Meyn, Todd P. Coleman
ALOHA packetized multiple-access systems
Abstract—We present an upper bound on the probability of error of a signaling scheme that achieves the capacity of the multipath fading channel under an average power constraint in the limit of...
Natanael Peranginangin, Muriel Médard, Robert G. Gallager
Abstract—To help understand distributed processing in the context of channel coding, we study distributed processing in a single input multi output (SIMO) channel with memory. Distributed...
Abstract—We present an upper bound on the probability of error of a signaling scheme that achieves the capacity of the multipath fading channel under an average power constraint in the limit of...
Optimal Uncoded Regeneration for Binary Antipodal Signaling (2007)
Ibrahim Abou-faycal, Muriel Médard
We derive, for a binary antipodal input signal, the optimal uncoded regenerator function when the channels at the ingress and at the egress of the regenerator are degraded by AWGN. We show that the...
Evolutionary Approaches To Minimizing Network Coding Resources (2007)
Kim, Minkyu, Médard, Muriel, Aggarwal, Varun, O'Reilly, Una-May, Kim, Wonsik, Ahn, Chang Wook, ...
We wish to minimize the resources used for network coding while achieving the desired throughput in a multicast scenario. We employ evolutionary approaches, based on a genetic algorithm, that avoid...
On Separation for Multiple Access Channels (2007)
Ray, Siddarth, Médard, Muriel, Effros, Michelle, Koetter, Ralf
We examine the issue of separation for multiple access channels. We demonstrate that source-channel separation holds for noisy multiple access channels, when the channel operates over a common finite...
Network Coding in a Multicast Switch (2007)
Jay Kumar Sundararajan, Muriel Médard, Minji Kim, Atilla Eryilmaz, Devavrat Shah, Ralf Koetter
Abstract—We consider the problem of serving multicast flows in a crossbar switch. We show that linear network coding across packets of a flow can sustain traffic patterns that cannot be served if...
Distributed functional compression through graph coloring (2007)
Vishal Doshi, Devavrat Shah, Muriel Médard, Sidharth Jaggi
We consider the distributed computation of a function of random sources with minimal communication. Specifically, given two discrete memoryless sources, X and Y, a receiver wishes to compute f(X, Y)...
Minimum-cost subgraphs for joint distributed source and network coding (2007)
Abstract — We consider multicast of correlated sources over a network. Assuming the use of random network coding, we provide a linear optimization formulation for allocation of link rates in the...
Siddharth Ray, Muriel Médard, Senior Member, Lizhong Zheng
Abstract—We consider a multiple-input, multiple-output (MIMO) wideband Rayleigh block fading channel where the channel state is unknown to both the transmitter and the receiver and there is only an...
Joint Relaying and Network Coding in Wireless Networks (2007)
Sachin Katti, Ivana Marić, Andrea Goldsmith, Dina Katabi, Muriel Médard
Abstract — Relaying is a fundamental building block of wireless networks. Sophisticated relaying strategies at the physical layer have been developed for a single flow, but multiple flows are...
Genetic representations for evolutionary minimization of network coding resources (2007)
Minkyu Kim, Varun Aggarwal, Muriel Médard, Wonsik Kim
Abstract. We demonstrate how a genetic algorithm solves the problem of minimizing the resources used for network coding, subject to a throughput constraint, in a multicast scenario. A genetic...
Signatures for content distribution with network coding (2007)
Fang Zhao, Ton Kalker, Muriel Médard, Keesook J. Han
Abstract — Recent research has shown that network coding can be used in content distribution systems to improve the speed of downloads and the robustness of the systems. However, such systems are...
Network Coding in a Multicast Switch (2007)
Jay Kumar Sundararajan, Muriel Médard, Minji Kim, Atilla Eryilmaz, Devavrat Shah, Ralf Koetter
Abstract — We consider the problem of serving multicast flows in a crossbar switch. We show that linear network coding across packets of a flow can sustain traffic patterns that cannot be served if...
On feedback for network coding (2007)
Christina Fragouli, Desmond Lun, Muriel Médard, Payam Pakzad
Abstract — In this paper we examine possible ways that feedback can be used, in the context of systems with network coding capabilities. We illustrate, through a number of simple examples, that use...
Evolutionary approaches to minimizing network coding resources (2007)
Minkyu Kim, Muriel Médard, Varun Aggarwal, Wonsik Kim, Chang Wook Ahn, Michelle Effros
Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method...
A Random Linear Network Coding Approach to Multicast (2006)
Ho, Tracey, Médard, Muriel, Koetter, Ralf, Karger, David R., Effros, Michelle, Shi, Jun, ...
We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly...
Low-Complexity Approaches to Slepian–Wolf Near-Lossless Distributed Data Compression (2006)
Coleman, Todd P., Lee, Anna H., Médard, Muriel, Effros, Michelle
This paper discusses the Slepian–Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable...
Interference management via capacity-achieving codes for the deterministic broadcast channel (2006)
Coleman, Todd P., Martinian, Emin, Effros, Michelle, Médard, Muriel
This paper considers the problem, first introduced by Ahlswede and Körner in 1975, of lossless source coding with coded side information. Specifically, let X and Y be two random variables such that...
On some new approaches to practical Slepian-Wolf compression inspired by channel coding (2006)
Coleman, Todd P., Lee, Anna H., Médard, Muriel, Effros, Michelle
This paper considers the problem, first introduced by Ahlswede and Körner in 1975, of lossless source coding with coded side information. Specifically, let X and Y be two random variables such that...
Minimum-cost multicast over coded packet networks (2006)
Lun, Desmond S., Ratnakar, Niranjan, Médard, Muriel, Koetter, Ralf, Karger, David R., Ho, Tracey, ...
We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e., packet networks where the contents of outgoing packets are arbitrary, causal functions of...
Time-sharing vs. source-splitting in the Slepian-Wolf problem: error exponents analysis (2006)
Todd P. Coleman, Todd P., Médard, Muriel, Effros, Michelle
We discuss two approaches for decoding at arbitrary rates in the Slepian-Wolf problem - time sharing and source splitting - both of which rely on constituent vertex decoders. We consider the error...
An analysis of finite-memory random linear coding on packet streams (2006)
Desmond S. Lun, Payam Pakzad, Christina Fragouli, Muriel Médard, Ralf Koetter
Abstract — 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...
Guy Weichenberg, Muriel Médard
Abstract — In this work, we compare three optical transport network architectures: optical packet switching (OPS), optical flow switching (OFS), and optical burst switching (OBS). Our comparison is...
Minimum-cost multicast over coded packet networks (2006)
Desmond S. Lun, Niranjan Ratnakar, Muriel Médard, Ralf Koetter, David R. Karger, Tracey Ho, ...
We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e. packet networks where the contents of outgoing packets are arbitrary, causal functions of...
On minimizing network coding resources: An evolutionary approach (2006)
Minkyu Kim, Chang Wook Ahn, Muriel Médard, Michelle Effros
Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method...
XORs in The Air: Practical Wireless Network Coding (2006)
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft
This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content...
Network coding for efficient wireless unicast (2006)
Abstract — We consider the problem of establishing efficient unicast connections over wireless packet networks. We show how network coding, combined with distributed flow optimization, gives a...
A random linear network coding approach to multicast (2006)
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Associate Member, Michelle Effros, ...
Abstract—We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and...
Graph coloring and conditional graph entropy (2006)
Vishal Doshi, Devavrat Shah, Muriel Médard, Sidharth Jaggi
Abstract — We consider the remote computation of a function of two sources where one is receiver side information. Specifically, given side information Y, we wish to compute f(X, Y) based on...
Low-complexity approaches to Slepian-Wolf near-lossless distributed data compression (2006)
Todd P. Coleman, Anna H. Lee, Student Member, Muriel Médard, Michelle Effros, Senior Member, ...
Abstract — This paper discusses the Slepian-Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the...
Guy Weichenberg, Student Member, Muriel Médard, Senior Member
Abstract – In this work, we evaluate an attractive candidate for optical network data transport: Optical Flow Switching (OFS). We describe the operation and implementation of the architecture,...
XORs in the air: practical wireless network coding (2006)
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft
This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content...
XORs in the air: practical wireless network coding (2006)
Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, Jon Crowcroft
This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content...
Linear complexity universal decoding with exponential error probability decay (2005)
Coleman, Todd P., Médard, Muriel, Effros, Michelle
In this manuscript we consider linear complexity binary linear block encoders and decoders that operate universally with exponential error probability decay. Such scenarios may be relevant in...
Rate-splitting for the deterministic broadcast channel (2005)
Coleman, Todd P., Effros, Michelle, Martinian, Emin, Médard, Muriel
We show that the deterministic broadcast channel, where a single source transmits to M receivers across a deterministic mechanism, may be reduced, via a rate-splitting transformation, to another...
Further results on coding for reliable communication over packet networks (2005)
Lun, Desmond S., Médard, Muriel, Koetter, Ralf, Effros, Michelle
In “On Coding for Reliable Communication over Packet Networks” (Lun, Médard, and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, 2004), a capacity-achieving coding...
On the utility of network coding in dynamic environments (2005)
Ho, Tracey, Leong, Ben, Médard, Muriel, Koetter, Ralf, Chang, Yu-Han, Effros, Michelle
Many wireless applications, such as ad-hoc networks and sensor networks, require decentralized operation in dynamically varying environments. We consider a distributed randomized network coding...
Towards practical minimum-entropy universal decoding (2005)
Coleman, Todd P., Médard, Muriel, Effros, Michelle
Minimum-entropy decoding is a universal decoding algorithm used in decoding block compression of discrete memoryless sources as well as block transmission of information across discrete memoryless...
An information-theoretic view of network management (2005)
Ho, Tracey, Médard, Muriel, Koetter, Ralf
We present an information-theoretic framework for network management for recovery from nonergodic link failures. Building on recent work in the field of network coding, we describe the input-output...
Effros, Michelle, Koetter, Ralf, Goldsmith, Andrea J., Médard, Muriel
We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each possible...
A new source-splitting approach to the Slepian-Wolf problem (2005)
Coleman, Todd, Lee, Anna, Médard, Muriel, Effros, Michelle
It is shown that achieving an arbitrary rate-point in the achievable region of the M-source Slepian-Wolf [1] problem may be reduced via a practical source-splitting transformation to achieving a...
Byzantine modification detection in multicast networks using randomized network coding (2005)
Ho, Tracey, Leong, Ben, Koetter, Ralf, Médard, Muriel, Effros, Michelle, Karger, David R.
Distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without the use of cryptographic...
An Information-Theoretic View of Network Management (2005)
Tracey Ho, Muriel Médard, Senior Member, Ralf Koetter
Abstract—We present an information-theoretic framework for network management for recovery from nonergodic link failures. Building on recent work in the field of network coding, we describe the...
Achieving Minimum-Cost Multicast: ADecentralized Approach Based on Network Coding (2005)
Desmond S. Lun, Niranjan Ratnakar +, Niranjan Ratnakar, Ralf Koetter, Muriel Médard, Ebad Ahmed, ...
We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing decentralized...
How good is random linear coding based distributed networked storage (2005)
Szymon Acedański, Supratim Deb, Muriel Médard, Ralf Koetter
Abstract — We consider the problem of storing a large file or multiple large files in a distributed manner over a network. In the framework we consider, there are multiple storage locations, each...
Network coding for wireless applications: A brief tutorial (2005)
Supratim Deb, Michelle Effros, Tracey Ho, David R. Karger, Ralf Koetter, Desmond S. Lun, ...
Abstract — The advent of network coding promises to change many aspects of networking. Network coding moves away from the classical approach of networking, which treats networks as akin to physical...
Fiber Aided Wireless Network Architecture: A SISO wireless-optical channel (2005)
Siddharth Ray, Muriel Médard, Lizhong Zheng
We introduce the concept of a fiber aided wireless network architecture (FAWNA), which allows high-speed mobile connectivity by leveraging the speed of optical networks. As a first step towards...
On the dynamic multicast problem for coded networks (2005)
Abstract — We consider the problem of finding minimum-cost time-varying subgraphs that can deliver continuous service to dynamic multicast groups in coded networks (i.e. networks that use network...
Cheng Luo, Student Member, Muriel Médard, Senior Member, Lizhong Zheng
In the wideband limit, certain types of “flash ” signaling, such as flash Frequency-Shift Keying (FSK), achieve the capacity of multipath fading channels. It is not clear, however, whether these...
Achieving minimum-cost multicast: A decentralized approach based on network coding (2005)
Desmond S. Lun, Niranjan Ratnakar, Ralf Koetter, Muriel Médard, Ebad Ahmed, Hyunjoo Lee
Abstract — We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing...
Achieving minimum-cost multicast: A decentralized approach based on network coding (2005)
Desmond S. Lun, Niranjan Ratnakar, Ralf Koetter, Muriel Médard, Ebad Ahmed, Hyunjoo Lee
We present decentralized algorithms that compute minimum-cost subgraphs for establishing multicast connections in networks that use coding. These algorithms, coupled with existing decentralized...
On the sublinear behavior of MIMO channel capacity at low SNR (2004)
Siddharth Ray, Muriel Médard, Lizhong Zheng, Jinane Abounadi
We consider wideband wireless communication over a multiple-input, multiple-output (MIMO) Rayleigh fading channel where the transmitter has no channel state information (CSI). We study the channel...
On the utility of network coding in dynamic environments (2004)
Tracey Ho, Ben Leong, Muriel Médard, Ralf Koetter, Yu-han Chang, Michelle Effros
Abstract — Many wireless applications, such as ad-hoc networks and sensor networks, require decentralized operation in dynamically varying environments. We consider a distributed randomized network...
Byzantine modification detection in multicast networks using randomized network coding (2004)
Tracey Ho, Ben Leong, Ralf Koetter, Muriel Médard, Michelle Effros, David R. Karger
Abstract — We show how distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without...
On the performance of peaky capacity-achieving signaling on multipath fading channels (2004)
We analyze the error probability of peaky signaling on band-limited multipath fading channels — the signaling strategy that achieves the capacity of such channels in the limit of infinite bandwidth...
Byzantine modification detection in multicast networks using randomized network coding (2004)
Tracey Ho, Ben Leong, Ralf Koetter, Muriel Médard, Michelle Effros, David R. Karger
This paper gives an information theoretic approach for detecting Byzantine modifications in networks employing random linear network coding. Each exogenous source packet is augmented with a flexible...
Network Coding for Correlated Sources (2004)
Tracey Ho, Muriel Médard, Michelle Effros, Ralf Koetter
Abstract — We consider the ability of a distributed randomized network coding approach to multicast, to one or more receivers, correlated sources over a network where compression may be required....
Network Coding with a Cost Criterion (2004)
Desmond S. Lun, Muriel Médard, Tracey Ho, Ralf Koetter
We consider applying network coding in settings where there is a cost associated with network use.
Error Exponents for Channel Coding and Signal Constellation Design (2004)
Jianyi Huang, Sean Meyn, Muriel Médard
We consider the optimization of the random coding error exponent of a class of memoryless channels where the input is subject to a peak and average-power constraints. The capacity-achieving input is...
Network Coding with a Cost Criterion (2004)
Desmond S. Lun, Muriel Médard, Tracey Ho, Ralf Koetter
We consider applying network coding in settings where there is a cost associated with network use. We show that, while minimum-cost multicast problems without network coding are very di#cult except...
A New Source-Splitting Approach to the Slepian-Wolf Problem (2004)
Todd Coleman Anna, Anna Lee, Muriel Médard, Michelle Effros
It is shown that achieving an arbitrary rate-point in the achievable region of the M-source Slepian-Wolf [1] problem may be reduced via a practical source-splitting transformation to achieving a...
On Source and Channel Codes for Multiple Inputs and Outputs (2004)
Michelle Effros, Ralf Koetter, Andrea J. Goldsmith, Muriel Médard
Abstract — We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each...
On the performance of peaky capacity-achieving signaling on multipath fading channels (2004)
Desmond S. Lun, Student Member, Muriel Médard, Senior Member
Abstract—We analyze the error probability of peaky signaling on bandlimited multipath fading channels, the signaling strategy that achieves the capacity of such channels in the limit of infinite...
On Source and Channel Codes for Multiple Inputs and Outputs (2004)
Michelle Effros, Ralf Koetter, Andrea J. Goldsmith, Muriel Médard
Abstract — We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each...
Algebraic gossip: A network coding approach to optimal multiple rumor mongering (2004)
We study the problem of simultaneously disseminating multiple messages in a large network in a decentralized and distributed manner. We consider a network with n nodes and k (k = O(n)) messages...
Towards using the network as a switch: On the use of TDM in linear optical networks (2004)
A common problem in optical networking is that the large quantity of raw bandwidth available in such networks is often difficult to access. We show that time-division multiplexing (TDM) can be used...
Algebraic gossip: A network coding approach to optimal multiple rumor mongering (2004)
Supratim Deb, Muriel Médard, Clifford Choute
We study the problem of simultaneously disseminating multiple messages in a large network in a decentralized and distributed manner where nodes only have knowledge about their own contents. We...
On coding for reliable communication over packet networks (2004)
Desmond S. Lun, Muriel Médard, Michelle Effros
We present a capacity-approaching coding scheme for unicast or multicast over lossy packet networks. In the scheme, all nodes perform coding, but do not wait for a full block of packets to be...
Capacity of time-slotted aloha packetized multiple-access systems over the awgn channel (2004)
Muriel Médard, Jianyi Huang, Andrea J. Goldsmith, Senior Member, Senior Member, Sean P. Meyn, ...
Abstract—We study different notions of capacity for time-slotted ALOHA systems. In these systems, multiple users synchronously send packets in a bursty manner over a common additive white Gaussian...
Toward a random operation of networks (2004)
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Michelle Effros, Jun Shi, ...
We present a distributed randomized network coding approach for transmission and compression of information in general multi-source multicast networks. Network nodes independently and randomly select...
On coding for reliable communication over packet networks (2004)
D. Medard, R Effros, Subaward No. S, Office Of, Desmond S. Lun, Muriel Médard, ...
We present a capacity-achieving coding scheme for unicast or multicast over lossy packet networks. In the scheme, intermediate nodes perform additional coding yet do not decode nor even wait for a...
On some new approaches to practical Slepian-Wolf compression inspired by channel coding (2004)
Todd P. Coleman, Anna H. Lee, Muriel Médard, Michelle Effros
We introduce three new innovations for compression using LDPCs for the Slepian-Wolf problem. The first is a general iterative Slepian-Wolf decoding algorithm that incorporates the graphical structure...
The benefits of coding over routing in a randomized setting (2003)
Ho, Tracey, Koetter, Ralf, Médard, Muriel, Karger, David R., Effros, Michelle
A novel randomized network coding approach for robust, distributed transmission and compression of information in networks is presented, and its advantages over routing-based approaches is...
Network Coding from a Network Flow Perspective (2003)
Tracey Ho, David R. Karger, Muriel Médard, Ralf Koetter
Abstract — We make precise connections between algebraic network coding and network flows. Our combinatorial formulations offer new insights, mathematical simplicity, and lead to a substantially...
The benefits of coding over routing in a randomized setting (2003)
Tracey Ho, Ralf Koetter, Muriel Médard, David R. Karger, Michelle Effros
Abstract — We present a novel randomized coding approach for robust, distributed transmission and compression of information in networks. We give a lower bound on the success probability of a...
The benefits of coding over routing in a randomized setting (2003)
Tracey Ho, Ralf Koetter, Muriel Médard, David R. Karger, Michelle Effros
Abstract — We present a novel randomized coding approach for robust, distributed transmission and compression of information in networks. We give a lower bound on the success probability of a...
An algebraic approach to network coding (2003)
Ralf Koetter, Muriel Médard, Senior Member
Abstract—We take a new look at the issue of network capacity. It is shown that network coding is an essential ingredient in achieving the capacity of a network. Building on recent work by Li et...
High-reliability architectures for networks under stress (2003)
Guy E. Weichenberg, Muriel Médard
Abstract — In this paper, we consider the task of designing a physical network topology that meets a high level of reliability using unreliable network elements. We are motivated by the use of...
Reliable Architectures for Networks under Stress (2003)
Guy E. Weichenberg, Muriel Médard
In this paper, we consider the task of designing a physical network topology that meets a high level of reliability with unreliable network elements. Our simple network model is one in which nodes...
An Information Theoretic View of Network Management (2003)
Tracey Ho, Muriel Médard, Ralf Koetter
We present an information theoretic framework for network management for recovery from non-ergodic link failures. Building on recent work in the field of network coding, we describe the input-output...
An Information Theoretic View of Network Management (2003)
Tracey Ho, Muriel Médard, Ralf Koetter
We present an information theoretic framework for network management for recovery from non-ergodic link failures. Building on recent work in the field of network coding, we describe the input-output...
On randomized network coding (2003)
Tracey Ho, Muriel Médard, Jun Shi, Michelle Effros, David R. Karger
We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links...
High-reliability architectures for networks under stress (2003)
Guy E. Weichenberg, Muriel Médard
Abstract — In this paper, we consider the design of a physical network topology that meets a high level of reliability using unreliable network elements. We are motivated by the use of networks,...
Certified by.......................................................... (2003)
Minkyu Kim, Muriel Médard, Arthur C. Smith
We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several...
Error Exponents for Multi-tone Frequency Shift Keying on Wideband Rayleigh Fading Channels (2003)
Cheng Luo, Muriel Médard, Lizhong Zheng
Flash signalling (with vanishing duty cycle) Frequency Shift Keying (FSK) is known to be a capacity-achieving modulation for multi-path fading channels in the limit of infinite bandwidth. However,...
A Reliable Architecture for Networks under Stress (2003)
Guy E. Weichenberg, Muriel Médard
In this paper, we consider Harary graphs as candidate solutions for the design of a physical network topology that achieves a high level of reliability using unreliable network elements. Our network...
Generalized loop-back recovery in optical mesh networks (2002)
Muriel Médard, Richard A. Barry, Steven G. Finn, Wenbo He, Steven S. Lumetta
Abstract—Current means of providing loop-back recovery, which is widely used in SONET, rely on ring topologies, or on overlaying logical ring topologies upon physical meshes. Loop-back is desirable...
A Network Management Architecture for Robust Packet Routing in Optical Access Networks (2002)
Muriel Médard, Steven Lumetta, Liuyang Li
We describe an architecture for optical local area network (LAN) or metropolitan area net-work (MAN) access. The architecture allows for bandwidth sharing within a wavelength and is robust to both...
Frequency-Shift Keying for Ultrawideband (2002)
Achieving Rates Of, Cheng Luo, Muriel Médard
In wideband systems that decorrelate in time and frequency, capacity can be reached in the limit of infinite bandwidth by using impulsive frequency-shift keying (FSK) with vanishingly small duty...
Frequency-shift keying for Ultrawideband - How close to capacity can we get? (2002)
In wideband systems that decorrelate in time and frequency, capacity can be reached in the limit of infinite bandwidth by using impulsive frequency-shift keying with vanishingly small duty cycle. The...
A Network Management Architecture for Robust Packet Routing in Optical Access Networks (2002)
Muriel Médard, Senior Member, Steven Lumetta, Liuyang Li
Abstract—We describe an architecture for optical local area network (LAN) or metropolitan area network (MAN) access. The architecture allows for bandwidth sharing within a wavelength and is robust...
Bandwidth scaling for fading multipath channels (2002)
Muriel Médard, Robert G. Gallager, Life Fellow
Abstract—We show that very large bandwidths on fading multipath channels cannot be effectively utilized by spread-spectrum systems that (in a particular sense) spread the available power uniformly...
M edard. Performance of Single-tone and Two-tone - Frequency-shift Keying for Ultrawideband (2002)
By using impulsive frequency-shift keying (FSK) with vanishingly small duty cycle, capacity can be achieved in the limit of infinite bandwidth in wideband systems that decorrelate in time and...
Classification of Two-link Failures for All-optical Networks (2001)
Steven S. Lumetta, Muriel Médard
Abstract: This paper studies the relationship between failure localization and the properties of link restoration algorithms for mesh networks through an examination of recovery from multiple...
Trade-off Between Power Consumption and Delay in Wireless Packetized Systems (2001)
In packetized wireless systems, coding allows correct reception of multiple packets colliding at a receiver. Thus data may not need to incur delays such as those due to backoff schemes in traditional...
Robust Routing for Local Area Optical Access Networks (2000)
uch as buffering, adding packets and dropping packets, or merging packet streams, are done with ease. In optics, however, buffering is onerous. Operations such as retrieving a packet from a traffic...
Capacity-Efficient Restoration for Optical Networks (2000)
Muriel Médard, Muriel Médard, Steven S. Lumetta, Steven S. Lumetta, Yung-ching Tseng, Yung-ching Tseng
Traditional, ring-based restoration reserves half the network capacity for backup. Using generalized loopback, an alternate method for restoration, we show roughly 20 % capacity enhancement and...
Distributed algorithms for attack localization in all-optical networks (1998)
Ruth Bergman, Muriel Médard, Serena Chan
All-Optical Networks provide ultra-fast data rates, but present a new set of challenges for network security. We present a new algorithm for attack localization in networks. The algorithm is...
Attack detection methods for all-optical networks (1998)
Muriel Médard, Douglas Marquis, Stephen R. Chinn
This paper focuses on theoretical methods for detecting intentional attacks upon the infrastructure of an all-optical network. Applications of existing methods used in traditional networks, as well...
Intface.c documentation (internal report (1997)
Siddharth Ray, Muriel Médard, Jinane Abounadi
We consider a time-slotted multiple access noise-free channel where, the received and transmit alphabets belong to a finite field and the transmitters interfere additively over that field. We derive...
The capacity of time varying multiple user channels in wireless communications (1995)
Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1995.
The capacity of time varying multiple user channels in wireless communications (1995)
Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1995.
Security issues in all-optical networks (0000)
All-optical networks are emerging as a promising technology for terabit per second class communications. However, they are intrinsically different from electro-optical networks, particularly because...
Security issues in all-optical networks
All-optical networks are emerging as a promising technology for terabit per second class communications. However, they are intrinsically different from electro-optical networks, particularly because...
On Channel Coherence in the Low SNR Regime
Lizhong Zheng Muriel, Lizhong Zheng, Muriel Médard, David Tse, Cheng Luo
The current study of the low SNR fading channels focuses on two extreme cases: the coherent case with perfect channel state information (CSI) available at the receiver, and the non-coherent case with...