RKRalf Koetter

Ralf Koetter

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ralf Koetter has a total of 25 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On Counteracting Byzantine Attacks in Network Coded Peer-to-Peer Networks

    by MinJi Kim, Luísa Lima, Fang Zhao, Joao Barros, Muriel Medard, Ralf Koetter, Ton Kalker, Keesook Han

    Random linear network coding can be used in peer-to-peer networks to increase the efficiency of content distribution and distributed storage. However, these systems are particularly susceptible to Byzantine attacks. We quantify the impact of Byzantine attacks on the coded system by evaluating the probability that a receiver node fails to correctly recover a file. We show that even for a small probability of attack, the system fails with overwhelming probability. We then propose a novel signature scheme that allows packet-level Byzantine detection. This scheme allows one-hop containment of the contamination, and saves bandwidth by allowing nodes to detect and drop the contaminated packets. We compare the net cost of our signature scheme with various other Byzantine schemes, and show that when the probability of Byzantine attacks is high, our scheme is the most bandwidth efficient.

  • Robust Self-Authenticating Network Coding

    by Muriel Medard, Keesook Han, Tracey Ho, Ralf Koetter

    The annual accomplishments include new algorithms that use network coding for: data hiding without the use of a key - ensuring sufficient degrees of freedom to decode over the receiver in variable settings, creating efficient coding schemes for Byzantine attacks, and providing quantification of the benefits to network coding.

  • Open Access

    Network Coding in a Multicast Switch

    by MinJi Kim, Jay Kumar Sundararajan, Muriel Medard, Atilla Eryilmaz, Ralf Koetter

    The problem of serving multicast flows in a crossbar switch is considered. Intra-flow linear network coding is shown to achieve a larger rate region than the case without coding. A traffic pattern is presented which is achievable with coding but requires a switch speedup when coding is not allowed. The rate region with coding can be characterized in a simple graph-theoretic manner, in terms of the stable set polytope of the "enhanced conflict graph". No such graph-theoretic characterization is known for the case of fanout splitting without coding. The minimum speedup needed to achieve 100% throughput with coding is shown to be upper bounded by the imperfection ratio of the enhanced conflict graph. When applied to KxN switches with unicasts and broadcasts only, this gives a bound of min{(2K-1)/K,2N/(N+1)} on the speedup. This shows that speedup, which is usually implemented in hardware, can often be substituted by network coding, which can be done in software. Computing an offline schedule (using prior knowledge of the flow rates) is reduced to fractional weighted graph coloring. A graph-theoretic online scheduling algorithm (using only queue occupancy information) is also proposed, that stabilizes the queues for all rates within the rate region.

  • Open Access

    A Rank-Metric Approach to Error Control in Random Network Coding

    by Danilo Silva, Frank R. Kschischang, Ralf Kötter

    The problem of error control in random linear network coding is addressed from a matrix perspective that is closely related to the subspace perspective of K\"otter and Kschischang. A large class of constant-dimension subspace codes is investigated. It is shown that codes in this class can be easily constructed from rank-metric codes, while preserving their distance properties. Moreover, it is shown that minimum distance decoding of such subspace codes can be reformulated as a generalized decoding problem for rank-metric codes where partial information about the error is available. This partial information may be in the form of erasures (knowledge of an error location but not its value) and deviations (knowledge of an error value but not its location). Taking erasures and deviations into account (when they occur) strictly increases the error correction capability of a code: if $\mu$ erasures and $\delta$ deviations occur, then errors of rank $t$ can always be corrected provided that $2t \leq d - 1 + \mu + \delta$, where $d$ is the minimum rank distance of the code. For Gabidulin codes, an important family of maximum rank distance codes, an efficient decoding algorithm is proposed that can properly exploit erasures and deviations. In a network coding application where $n$ packets of length $M$ over $F_q$ are transmitted, the complexity of the decoding algorithm is given by $O(dM)$ operations in an extension field $F_{q^n}$.

  • Open Access

    Coding Strategies for Noise-Free Relay Cascades with Half-Duplex Constraint

    by Tobias Lutz, Christoph Hausl, Ralf Kötter

    Two types of noise-free relay cascades are investigated. Networks where a source communicates with a distant receiver via a cascade of half-duplex constrained relays, and networks where not only the source but also a single relay node intends to transmit information to the same destination. We introduce two relay channel models, capturing the half-duplex constraint, and within the framework of these models capacity is determined for the first network type. It turns out that capacity is significantly higher than the rates which are achievable with a straightforward time-sharing approach. A capacity achieving coding strategy is presented based on allocating the transmit and receive time slots of a node in dependence of the node's previously received data. For the networks of the second type, an upper bound to the rate region is derived from the cut-set bound. Further, achievability of the cut-set bound in the single relay case is shown given that the source rate exceeds a certain minimum value.

  • Open Access

    Coding for Errors and Erasures in Random Network Coding

    by Ralf Koetter, Frank Kschischang

    The problem of error-control in random linear network coding is considered. A ``noncoherent'' or ``channel oblivious'' model is assumed where neither transmitter nor receiver is assumed to have knowledge of the channel transfer characteristic. Motivated by the property that linear network coding is vector-space preserving, information transmission is modelled as the injection into the network of a basis for a vector space $V$ and the collection by the receiver of a basis for a vector space $U$. A metric on the projective geometry associated with the packet space is introduced, and it is shown that a minimum distance decoder for this metric achieves correct decoding if the dimension of the space $V \cap U$ is sufficiently large. If the dimension of each codeword is restricted to a fixed integer, the code forms a subset of a finite-field Grassmannian, or, equivalently, a subset of the vertices of the corresponding Grassmann graph. Sphere-packing and sphere-covering bounds as well as a generalization of the Singleton bound are provided for such codes. Finally, a Reed-Solomon-like code construction, related to Gabidulin's construction of maximum rank-distance codes, is described and a Sudan-style ``list-1'' minimum distance decoding algorithm is provided.

  • Performance of Iterative Algebraic Decoding of Codes Defined on Graphs: An Initial Investigation

    by Xiangyu Tang, Ralf Koetter

    We investigate iterative algebraic decoding of codes defined on graphs. Practical codes that can achieve the Shannon limit are codes defined on graphs with its associated iterative decoding algorithms. Yet, the complexity of these algorithms is high, especially for long codes that attain capacity. For the foreseeable future, algebraic decoding will still be a standard in industry. We aim to harness the power of iterative processes and the low complexity of algebraic techniques by decoding codes on graphs using iterative algebraic techniques. We study the performance of codes on graphs decoded with this method taking into account the case of undetected errors. More specifically, we examine the threshold under which decoding is successful for the BEC and the BSC and compare these with that of certain LDPC codes. Our initial investigation shows that although a significant loss of performance is incurred on the BEC when compared to belief propagation decoding, for transmission over the BSC the threshold value is somewhat close to belief propagation. Especially for high rate codes iterative algebraic decoding could have good performance while maintaining low decoding complexity.


  • Open Access

    A Rank-Metric Approach to Error Control in Random Network Coding

    by Danilo Silva, Frank R. Kschischang, Ralf Koetter

    The problem of error control in random network coding is considered, and a formulation of the problem is given in terms of rank-metric codes. This formulation allows many of the tools developed for rank-metric codes to be applied to random network coding. A random network code induces a generalized decoding problem for rank-metric codes in which the channel may supply partial information about the error in the form of erasures (knowledge of an error location not its values) and deviations (knowledge of an error value but not its location).


  • Breaking Network Logjams

    by Michelle Effros, Ralf Koetter, Muriel Médard


  • A Low Complexity Algorithm and Architecture for Systematic Encoding of Hermitian Codes

    by Rachit Agarwal, Ralf Koetter, Emanuel M. Popovici

    We present an algorithm for systematic encoding of Hermitian codes. For a Hermitian code defined over GF(q 2), the proposed algorithm achieves a run time complexity of O(q 2) and is suitable for VLSI implementation. The encoder architecture uses as main blocks q varying-rate Reed-Solomon encoders and achieves a space complexity of O(q 2) in terms of finite field multipliers and memory elements.