Network Coding

• Faculty: Athina Markopoulou
• Postdoc: Hulya Seferoglu
• Students: Anh Le, Pegah Sattari, Minas Gjoka, Abinesh Ramakrishnan, Blerim Cici

• Christina Fragouli and Lorenzo Keller, EPFL, Lausanne.
• KK Ramakrishnan, AT&T Labs-Research.
• Syed Jafar, UC Irvine.

This work is currently supported by the following grants:

• NSF CAREER Award 0747110, "Network Coding Mechanisms for the Internet", 02/2008-01/2013.
• AFOSR MURI: "Information Dynamics as Foundation for Network Management". AFOSR MURI prime award FA9550-09-0643 (subcontract to UCI from Princeton). 9/1/2009-8/31/2014.
• AFOSR Award FA9550-10-1-0310, “NetSense: Optimizing Network Configuration for Sensing”, 09/2010-08/2013.

Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsors.

• Teaching: Check out a new graduate class (EECS246/NETSYS256) on Network Coding, offered in Fall 2009 and in Winter 2011.
• Conferences: Athina is co-chairing the NetCod 2012 TPC.

• Implementation of Network Coding on Smartphones
• Cross-Layer Optimization of Coded Wireless Networks
• Network Coding and Security
• Network Coding for Video Streaming
• Network Coding meets Interference Alignment
• Network Coding for Tomography

We are interested in practical applications of network coding. We are currently working on a MicroCast: a prototype of network coding on android phones for a cooperative video streaming application. To the best of our knowledge, our implementation is the first to exploit overhearing on androids.

• H.Seferoglu, L.Keller, B.Cici, A.Le, A. Markopoulou, "Cooperative Video Streaming on Smartphones", in Allerton Conference 2010 (invited paper), Sept. 2011, Monticello, IL. Here are the slides. And here are the demos on the cooperation and overhearing on android phones.

• More presentations and videos can be found here. Some of these materials are also posted at the MURI website.

• A. Ramakrishnan, A. Das, H. Maleki, A. Markopoulou, S. Jafar, S. Vishwanath, Network Coding for Three Unicast Sessions: Interference Alignment Approaches, in Allerton Conference 2010 (invited paper), Sept. 2010, Monticello, IL. (slides)
• A. Das, S. Vishwanath, S. Jafar, A. Markopoulou, "Network Coding for Multiple Unicasts: An Interference Alignment Approach", in Proc. of ISIT 2010, June 2010, Austin, TX. (Finalist for the ISIT 2010 Best Paper Award.)

In this project, we consider flows transmitted over a network that implements network coding. We are interested in the interaction between e2e congestion control and network coding in the middle. For example, should the e2e protocols be aware of network coding in the middle? What is the optimal network coding-aware rate control? How much benefit does it bring? How should existing transport protocols (TCP or TFRC) be modified in the presnce of network coding?

• H. Seferoglu, A. Markopoulou, M. Medard, "NCAPQ: Network Coding-Aware Priority Queueing for UDP Flows over COPE," in Proc. of NetCod 2011, Beijing, China, July 2011.
• H. Seferoglu, A. Markopoulou, K. K. Ramakrishnan, "I2NC: Inter- and Intra- Session Network Coding", in IEEE INFOCOM 2011. Here is technical report,related News Article at AT&T Labs-Research, and slides.
  
• H.Seferoglu, A.Markopoulou, "Network Coding-Aware Queue Management for Unicast Flows over Coded Wireless Networks", in Proc. of NetCod 2010, Toronto, Canada, June 2010. (slides) (arXiv:cs.NI:1002.4885).
• F.Soldo, A.Markopoulou, A. Lopez-Toledo "A Simple Optimi zation Model for Wireless Opportunistic Routing with Intra-session Network Coding", in Proc . of NetCod 2010, Toronto, Canada, June 2010. slides)
• H.Seferoglu, A.Markopoulou, U.Kozat, "Network coding-aware rate control and scheduling in wireless networks", to appear in ICME 2009, Special Session on “Network Coding for Multimedia Streaming”, Cancun, Mexico, June 2009.
• H.Seferoglu, A.Markopoulou, "Distributed Rate Control for Video Streaming over Wireless Networks with Intersession Network Coding", in Proc. of Packet Video 2009, Seattle, May 2009. (slides)

Network coding is content-unaware: it mixes packets so as to increase throughput. However, when the coded flows are video streams, the content of packets matters: packets within the same video stream have unequal importance, due to the video content, coding dependencies and playout deadlines. In this project, we design opportunistic network coding schemes particularly for video streaming, which take into account both considerations (i.e., the decodability of network codes by several receivers and the importance and deadlines of video packets).

• H.Seferoglu, A.Markopoulou, “Delay-Optimized Network Coding for Video Streaming over Wireless Networks”, accepted in ICC 2010, South Africa, May 2010.
• H.Seferoglu, A.Markopoulou, "Video-Aware Opportunistic Network Coding over Wireless Networks", to appear in JSAC, Special Issue on "Network Coding over Wireless Communication Networks", vol.27(5), June 2009.
• H.Seferoglu, A.Markopoulou,"Opportunistic Network Coding for Video Streaming over Wireless", in Proc. of Packet Video 2007, EPFL, Lausanne, Nov. 2007. (slides)

Network Coding is particularly vulnerable to Byzantine modification (a.k.a. pollution) attacks: malicious nodes can inject bogus packets, which get combined with legitimate blocks at downstream nodes, thus preventing decoding of original packets and degrading the overall performance. Various informational theoretical and cryptographic approaches have been proposed to deal with various aspects of the problem, such as, detection and correction of corrupted packets and location of the attackers. In this work, we are interested in both the timely detection of the attack as well as identifying the location of attackers, which allows to eliminate them from the system and stop the attack at this root.

• A. Le and A. Markopoulou, ”On Detecting Pollution Attacks in Inter-Session Network Coding,” accepted to IEEE INFOCOM 2012. (extended version)
• A. Le and A. Markopoulou, ”Cooperative Defense Against Pollution Attacks in Network Coding Using SpaceMac,” accepted to IEEE JSAC on “Cooperative Networking Challenges and Applications” (extended version).
• A. Le and A. Markopoulou, ”TESLA-Based Defense Against Pollution Attacks in P2P Systems with Network Coding,” in Proc. of NetCod 2011, pp. 61-68, Beijing, China, July 25-27, 2011. (slides)
• A. Le and A. Markopoulou, ”Locating Byzantine Attackers using SpaceMac,” in Proc. of NetCod 2010, pp. 1-6, Toronto, Canada, June 9-11, 2010. (slides)
• A. Le, ”On Identifying Pollution Attackers for Randomized Network Coding,” Technical Report, December 2009

Network Tomography is a family of monitoring techniques, which aim at inferring internal network characteristics by sending and collecting probe packets from the edge of the network. Prior work on network tomography considered networks that implement multicast and unicast forwarding. In this work, we consider networks where internal nodes implement network coding and we re-visit two classic network tomography problems: (i) link loss inference and (ii) topology inference. We develop new techniques that make use of the network coding capabilities and we show that they can improve several aspects of interest (including identifiability of links, accuracy of estimation, and complexity of probe path selection) over traditional techniques. If network coding is already deployed in a network, then one can exploit this opportunity to also improve other operations, such as network monitoring.

• P. Sattari, A. Markopoulou, Algebraic Traceback Meets Network Coding , in Proc. of the International Symposium on Network Coding (Poster Session), Beijing, China, July 2011.
• P. Sattari, M. Gjoka, A. Markopoulou, "A Network Coding Approach to IP Traceback", in Proc. of NetCod 2010, Toronto, Canada, June 2010. (slides)
• P.Sattari, C.Fragouli, A.Markopoulou, “Active topology Inference using Network Coding”, submitted for publication. Also on arxiv:1007.3336[cs.IT]
• P.Sattari, A.Markopoulou, C.Fragouli, "Multiple Source Multiple Destination Topology Inference using Network Coding", in NetCod 2009, EPFL, Lausanne, June 2009. (slides)
• C.Fragouli, A.Markopoulou, S.Diggavi, "Topology Inference using Network Coding Techniques", in the Proc. of the Allerton Conference, Monticello, IL, Sept. 2006.

• P. Sattari, A. Markopoulou, C. Fragouli, Maximum Likelihood Estimation for Multiple-Source Loss Tomography with Network Coding, in Proc. of the International Symposium on Network Coding (NetCod'11), Beijing, China, July 2011.
• A.Markopoulou, C.Fragouli, M.Gjoka, A Network Coding Approach to Loss Tomography , under review in ToIT and on arXiv:1005.4769v1[cs.IT].
• M.Gjoka, C.Fragouli, P.Sattari, A.Markopoulou,"Loss Tomography in General Topologies with Network Coding", in Proc. of IEEE Globecom 2007.
• C.Fragouli, A.Markopoulou, R.Srivanasan, S.Diggavi, "Network Monitoring: It Depends on your Points of View", in Proc. of ITA Workshop'07, UCSD, Jan. 2007.
• C.Fragouli, A.Markopoulou, "A Network Coding approach to Overlay Network Monitoring", in Proc. 43rd Allerton Conference on Communication, Control, and Computing, Monticello, IL, Sep. 2005

An overview of this work can be found in this talk presented at UCR, in Dec. 2006.