Applications of Low Density Parity Check Codes for Wiretap Channels and Congestion Localization in Networks

Abstract

Error control coding in some form is present in virtually every communication system today. Recently, Low Density Parity Check (LDPC) codes have been proposed along with a simple iterative decoding algorithm. These codes have been demonstrated to perform very close to the Shannon Limit. The simplicity of LDPC codes have also led to many interesting asymptotic and finite-length properties of these codes. The techniques for designing good LDPC codes over a wide variety of channels have been studied. LDPC codes are being used in a wide variety of applications, such as fading channels, Orthogonal Frequency Division Multiplexing (OFDM) systems, source compression etc. This proposal investigates the use of LDPC codes in wiretap channel systems such as quantum key distribution and for congestion localization in large networks.

Quantum Key Distribution (QKD) is secure key exchange method where the two legitimate parties first transmit information over a quantum channel, which can be eavesdropped on by the eavesdropper. The QKD system can be modeled as a special case of an wiretap channel system. An wiretap chanel system is a broadcast system, where the sender has to send a message to a legitimate party over a main channel. The wiretapper also receives the message through another channel called the wiretap channel. The sender has to code the transmitted message in such a way so that the legitimate party is able to recover the message without errors, whereas the wiretapper essentially has no information about the message. As we will see, the encoder for such a system is stochastic as opposed to a deterministic encoder in error correction coding. In this research, we propose a coding scheme using LDPC codes for such systems.

Congestion in a network occurs when some nodes receive more traffic than they can process. It leads to dropping packets and thus lowering the throughput. On the contrary, if other nodes in the network are aware of the congested nodes, new packets can be dynamically routed through less congested routes. We developed a congestion detection mechanism wherein a few high priority probe packets are routed through the network. A central entity collects the contents of all the probe packets and estimates the state (congested or not) of every node in the network. One important parameter of congeston localization schemes is scalability, i.e. how the number of measurements scales with the size of network as the size of the network grows. We have shown that it is possible to do congestion detection using our scheme for a properly designed network with the number of measurements required growing linearly with the size of the network.