Transmission over finite buffer channels and deletion channels

Queues form an integral part of packet-switched (IP) networks, being at switches and routers both in the core and edge networks. Pioneering work (Anantharam and Verdu, IEEE Trans. IT, January 1996) has demonstrated that the capacity of infinite-buffer queues can be achieved by coding over inter-packet times. However they also showed that inter-packet coding is sufficient (without the necessity of coding for packet timing) when the packet size is large enough.

The main manifestation of errors in networks are due to packet losses at a finite-buffer queue. We studied the information-carrying capacity of finite queues, allowing for inter-packet coding, but without coding in packet timing. In the presence of side-information about which packets were lost (such as through a packet sequence number mechanism), this problem is reduced to an erasure channel with significant memory and the capacity in this case is directly related to the long-term loss probability of the queue. We showed that even when there is significant memory in the erasures, feedback does not increase the capacity.

Transport protocols such as TCP use sequence numbers in the packet (strictly speaking, in the TCP header) to detect lost packets. Packets sent by the source are numbered sequentially. The destination can infer the loss of one or several packets from the sequence number of the packet following the loss. The sequence number uses up a certain number of bits (32 bits in the case of TCP/IP) to detect lost packets and to request retransmission of those packets. We can view it as a code that converts the deletion channel into an erasure channel.

A fundamental question therefore arises: if we do not assume a-priori the existence of sequence numbers, what is the capacity of the resulting channel? This question naturally leads to the deletion channel, which essentially differs from the erasure channel in that the destination receives no explicit symbol indicating loss of a packet. Instead, the received sequence of symbols is shorter than the original sequence, with deleted symbols simply removed, i.e. only a subsequence of the transmitted symbols is received. The characterization of capacity of the deletion channel is a long-standing open question since the 1960s. We provided the tightest lower bound to this problem since that time. Our work in revived interest in this problem, as evidenced by several follow-up pieces of work and recently Drinea and Mitzenmacher have improved our lower bounds. One of the surprising results we found was that the achievable rate in deletion channels differs from that of erasure channels by a small amount (at most 1 bit). This suggests that the use of sequence numbers to detect deletions is quite inefficient, though it makes the job of coding for such errors much simpler. In doing this analysis we studied questions on common subsequences between Markov processes, a topic perhaps of independent interest. More recently we have developed the tightest known upper bounds for the binary deletion channel.


  1. Download: finbuf.pdf 
    This paper was motivated by the transmission of information over finite buffer channels. Analyzing the capacity of such channels naturally led us to the study of deletion channels. In deletion channels, in contrast to erasure channels, symbols of the transmitted sequence are removed, and the receiver does not know which symbols have been deleted. This was a classic problem from the 1960s in the context of modeling synchronization errors. This paper gave the best known (at the time of publication) lower bounds to capacity of deletion channels since the 1960s. It also studied erasure channels with arbitrary memory in the erasure process. It showed that even when the erasure process has memory, feedback does not increase the capacity.
  2. Download: delubisit07.pdf 
    We present upper bounds on the capacity of the i.i.d. binary deletion channel, where each bit is independently deleted with a fixed probability d. We provide a general approach that gives a numerical answer for fixed d, and provide an argument that gives asymptotic upper bounds as d goes to 1. These appear to be the first non-trivial upper bounds for this probabilistic deletion channel.
  3. S. N. Diggavi and M. Grossglauser, "Bounds on capacity of deletion channels," in Proc. IEEE International Symposium on Information Theory (ISIT), Lausanne, 2002, p. 421.
  4. Download: allerton01.pdf 
    This paper develops the best known (at the time of publication) capacity lower bounds to the deletion channel since the 1960s. It also makes a connection between deletion channels and the well studied problem of the length of the longest common subsequence. It shows that the capacity of the deletion channel for large alphabet size is close to the corresponding erasure channel, though the coding schemes for the two channels are drastically different.
  5. S. N. Diggavi and M. Grossglauser, "Information transmission over a finite buffer channel," in Proc. IEEE International Symposium on Information Theory (ISIT),Sorrento, Italy, 2000, p. 52.