网络编码介绍.ppt

An Introduction to Network Coding Muriel Médard Associate Professor EECS Massachusetts Institute of Technology Ralf Koetter Director Institute for Communications Engineering Technical University of Munich Outline of course An introduction to network coding: Network model 网络模型 Algebraic aspects 代数问题 Delay issues 时延问题 Network coding for wireless multicast: 无线组播的网络编码 Distributed randomized coding 分布式随机编码 Erasure reliability 擦除可靠性 Use of feedback 使用反馈 Optimization in choice of subgraphs 选择子图的最优化 Distributed optimization 分布式的最优化 Dealing with mobility 解决移动的问题 Relation to compression 与压缩的关系 Network coding in non-multicast: 非组播的网络编码 Algorithms 运算法则 Heuristics 推断 Network coding for delay reduction in wireless downloading 为无线下载减少时延的 Security with network coding: 网络编码的安全 Byzantine security Wiretapping aspects 窃听问题  Network coding Canonical example [Ahslwede et al. 00] What choices can we make? No longer distinct flows, but information Network coding Picking a single bit does not work Time sharing does not work No longer distinct flows, but information Network coding Need to use algebraic nature of data No longer distinct flows, but information A simple example A simple example Transfer matrix Linear network system Solutions Multicast Multicast One source, disjoint multicasts Delays Delays Delays Network coding for multicast: Distributed randomized coding Erasure reliability Use of feedback Optimization in choice of subgraphs Distributed optimization Dealing with mobility Randomized network coding The effect of the network is that of a transfer matrix from sources to receivers To recover symbols at the receivers, we require sufficient degrees of freedom – an invertible matrix in the coefficients of all nodes The realization of the determinant of the matrix will be non-zero with high probability if the coefficients are chosen independently and randomly Probability of success over field F ≈ Randomized network coding can use