JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Course Objectives:

• 1. Learn the fundamentals of network coding theory.
• 2. Understand the performance parameters required for network coding.
• 3. Gain the knowledge of the network coding design methods.
• 4. Learn different approaches for the network coding.
• 5. Understand error correction and detection methods of adversarial errors.

Course Outcomes:

• 1. Demonstrate knowledge and understanding of the fundamentals of Network Coding Theory.
• 2. Summarize all the performance parameters and resources for network coding.
• 3. Construct the network code for different networks.
• 4. Deal with different approaches of Network Coding in lossy and lossless networks.
• 5. Deal with multiple sources network coding and detect adversarial errors.

UNIT - I

Introduction: A historical Perspective, Network Coding; Network Coding Benefits: Throughput, Robustness, Complexity, Security; Network Model. Main Theorem of Network Multicast: The Min-Cut Max-flow Theorem, The Main network coding Theorem, Theoretical Framework for Network Coding: A Network Multicast Model, algebraic Framework, Combinatorial Framework, Information-Theoretic Framework, Types of Routing and coding.

UNIT - II

Throughput Benefits of Network Coding: Throughput Measures, Linear Programming Approach, Configurations with Large Network Coding Benefits, Configurations with Small Network Coding Benefits, Undirected Graphs. Networks with Delay and Cycles: Dealing with Delay, Optimizing for Delay, Dealing with Cycles. Resources for Network Coding: Bounds on Code Alphabet Size, Bounds on the Number of Coding Points, Coding with Limited Resources.

UNIT - III

Network Code Design Methods For Multicasting: Common initial procedure, centralized algorithms, decentralized algorithms, scalability to network changes. Single-Source Linear Network Coding: Acyclic Networks: Acyclic Networks, Linear network code, Desirable properties of a linear network code, Existence and construction, Algorithm refinement for multicast. Cyclic Networks: Delay-Free Cyclic Code, Non-equivalence between local and global descriptions, Convolutional network code, decoding of convolutional network code.

UNIT - IV

Inter-Session Network Coding: Scalar and vector linear network coding, Fractional coding problem formulation, Insufficiency of linear network coding, Information theoretic approaches: Multiple unicast networks; Constructive approaches: Pairwise XOR coding in wireline networks, XOR coding in wireless networks. Network Coding in Lossy Networks: Random linear network coding, Coding theorems: Unicast connections, Multicast connections, Error exponents for Poisson traffic with i.i.d. losses.

Subgraph Selection: Flow-based approaches: Intra-session coding, Computation-constrained coding, Inter-session coding; Queue-Length-Based approaches: Intra-session network coding for multicast sessions, Inter-session coding.

UNIT - V

Multiple Sources Network Coding: Superposition coding and max-flow bound; Network Codes for Acyclic Networks: Achievable information rate region, Inner bound Rin, Outer bound Rout, RLP – An explicit outer bound. Security against adversarial Errors: Error correction: Error Correcting bounds for centralized network coding, Distributed random network coding and polynomial-complexity error correction; Detection of adversarial errors: Model and problem formulation, Detection probability.

TEXT BOOKS:

• 1. Raymond W. Yeung, Shuo-Yen Robert Li, Ning Cai, Zhen Zhang, “Network Coding Theory”, now publishers Inc, 2006, ISBN: 1-933019-24-7.
• 2. Christina Fragouli, Emina Soljanin, “Network Coding Fundamentals”, now publishers Inc, 2007, ISBN: 978-1-60198-032-8.

REFERENCES:

• 1. Tracey Ho, Desmond Lun, “Network Coding: An Introduction”, Cambridge University Press, 2008, ISBN: 978-0-521-87310-9.
• 2. Muriel Medard, Alex Sprintson, “Network Coding: Fundamentals and Applications”, 1st Edition, 2012, Academic Press, Elsevier, ISBN: 978-0-12-380918-6.