Delay Mitigating Codes for Connection Oriented Transmission over Networks

PIC

Due to a significant amount of time that packets remain in queues with other traffic, traditional packet networks are not naturally well suited applications needing a dedicated bit rate at a low delay, such as streaming media or remote control. Additionally, while the use of multiple paths between a source and destination in these networks opens the possibility for more rapid and lower delay data transmission, the possibility of packet reordering becomes likely due to the independent queues through which packets sent on different flows encounter. Traditional techniques for providing constant bit rate low delay transmission in both of these situations involve buffering packets, packet retransmission, and verbatim copying of the data to be transmitted into packets. This project proposes feed-forward techniques for encoding the packet contents to be sent over multiple paths in order to provide a constant bit rate transmission service with a tunable delay. We study the fundamental tradeoff over all such codes between rate and delay using techniques from multiterminal information and coding theory, using the technique outlined in Figure 1.

PIC


Figure 1: This project investigates the design and performance of codes when used to provide fixed bit rate low delay services over multipath packet networks and randomly linear network coded networks. Such services are desirable for live streaming media, as well as remote control over networks. We investigate both the construction of codes, as well as the best possible tradeoff between rate and delay provided by delay mitigating codes by first abstracting the problem the a degraded broadcast channel, then obtaining the rate delay tradeoffs by performing calculus on the capacity region of this broadcast channel.

Another facet of this research considers networks employing a recent discovery, network coding, in order to achieve the multicast capacity (the highest possible average rate of transmission from a source node to multiple destination nodes in the network). Networks employing routing alone can not achieve the multicast capacity, but linear network coding can. A recent technique, random linear network coding, has emerged for providing these services in a distributed manner throughout the network. However, because an encoding vector must be transmitted along with each packet, the high transmission rate is achieved with codes requiring a large initial delay, with the possibility that the earliest source data can not be decoded until an entire large block of packets have been received. In applications requiring a low delay, such as remote control or live streaming media, this large delay may lessen the benefits of the increase in average transmission rate. In order to provide a lower delay, the data being transmitted at the source can be encoded, sacrificing some of the rate. This project studies the codes that can be used to do this, and their associated fundamental tradeoffs between rate and delay. The technique used is similar to that used to study the same tradeoffs for multipath routed networks.

Research Collaborator on this Topic: Dr. Steven Weber & Dr. Jaudelice de Oliveira, Drexel University.

Students Presently Participating in this Research: Ciira Maina. He coauthored and presented the paper from the 2008 ISIT conference below. He also helped coauthor the Transactions on Information Theory journal submission below.

Funding for this Topic:

PIC National Science Foundation Grant CCF-1016588.

Relevant Recent Publications & Presentations

[1]   J. M. Walsh, S. P. Weber, J. C. de Oliveira, A. Eryilmaz, M. Médard, “Trading Rate for Delay at the Application and Transport Layers (Guest Editorial),” IEEE J. Select. Areas Commun., pp. 1–2, May 2011.

[2]   J. M. Walsh, S. Weber, and C. wa Maina, “Optimal Rate Delay Tradeoffs and Delay Mitigating Codes for Multipath Routed and Network Coded Networks,” IEEE Trans. Inform. Theory, vol. 55, no. 12, pp. 5491–5510, Dec. 2009. [Online]. Available: http://www.ece.drexel.edu/walsh/Walsh_TIT_12_09.pdf

[3]   J. M. Walsh and S. Weber, “Capacity Region of the Permutation Channel,” in 46th Annual Allerton Conference on Communication, Control, and Computing, Sep. 2008. [Online]. Available: http://www.ece.drexel.edu/walsh/walshAllerton08.pdf

[4]   John MacLaren Walsh and Steven Weber, “Fundamental Rate Delay Tradeoffs in Multipath Routed and Network Coded Networks,” Sep. 2008, DARPA ITMANET Meeting, Arlington, VA. [Online]. Available: http://www.ece.drexel.edu/walsh/weberITMANET0908.pdf

[5]   ——, “ Capacity Region of the Permutation Channel ,” Sep. 2008, DARPA ITMANET Meeting, Arlington, VA. [Online]. Available: http://www.ece.drexel.edu/walsh/weberITMANET0908poster.pdf

[6]   J. M. Walsh, S. Weber, and C. Maina, “Optimal Rate Delay Tradeoffs for Multipath Routed and Network Coded Networks,” in IEEE International Symposium on Information Theory (ISIT), Jul. 2008, pp. 682 – 686. [Online]. Available: http://www.ece.drexel.edu/walsh/WalshIsit08.pdf

[7]   John MacLaren Walsh and Steven Weber, “Fundamental Rate Delay Tradeoffs in Multipath Routed and Network Coded Networks,” Apr. 2008, MIT Workshop on Geometric Approaches in Communications and Signal Processing. [Online]. Available: http://www.ece.drexel.edu/walsh/weberMITW08.pdf

[8]   J. M. Walsh and S. Weber, “A Concatenated Network Coding Scheme for Multimedia Transmission,” in Fourth Workshop on Network Coding, Theory, and Applications (Netcod 2008), Jan. 2008, pp. 91–96. [Online]. Available: http://www.ece.drexel.edu/walsh/netcod08.pdf

[9]   ——, “Coding to reduce delay on a permutation channel,” in 45th Allerton Conference on Communication, Control, and Computing, Sep. 2007. [Online]. Available: http://www.ece.drexel.edu/walsh/allerton07.pdf