资源描述：
《网络编码在OBS组播中的应用.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、网络编码在OBS组播中的应用传统的多播传输是通过构造多播树实现的。典型的多播树，如最小费的Steiner树，其构造过程一般是个NP完全问题[1]，因此大多数的近似算法[1-3]，均不能使多播传输达到“最大流最小割”(MAX-FLOWMIN-CUT)定理[4]确定的最大理论传输容量。这主要是因为：现有通信网络中使用的路由机制认为网络中传输的信息是不能叠加的,只能进行存储和转发。图1(b)表示的是网络编码方法，节点W对输入的信息进行模二加操作，然后将操作结果发送至输出链路WX，然后又通过链路XY和XZ，最终达到信宿Y和Z。Y收到b1和后，通过译码操作就能解出b2，因此，信宿Y同时收到了b1
2、和b2。同理，通过译码操作，信宿Z也同时收到b1和b2。由此，基于网络编码的多播实现了理论上的最大传输容量网络编码优缺点：1.提高网络吞吐量如果为信源节点的符号空间，为通信网络中的节点数目，则对于每条链路都是单位容量的通信网络，基于网络编码的多播的吞吐量是路由多播的倍[16].2.均衡网络负载图2(a)所示的通信网络，其各链路容量为2。图2(b)表示的是基于多播树的路由多播，为使各个信宿节点达到最大传输容量，该多播共使用SU、UX、UY、SW和WZ共5条链路，且每条链路上传输的可行流为2；图2(c)表示的是基于网络编码的多播，图2(c)所示的网络编码多播所用的传输链路为9条，比图2(b
3、)的多播树传输要多4条链路。3.提高带宽利用率图2(b)消耗的总带宽为：5×2=10；图2(c)消耗总带宽为：9×1=9，因此带宽消耗节省了10%，提高了网络带宽利用率。网络编码的分类如果网络节点对传输的信息进行线性操作，则称为线性网络编码(LinearNetworkCoding)；否则称为非线性网络编码。如果网络节点对信息进行操作的系数是随机选取的，则称为随机网络编码；如果是通过算法确定出来的，则称为确定性网络编码。另外有人已经证明在有限域Fq中，只要域足够大，则通过合适的线性网络编码，就能使多播传输达到最大的传输容量。目前，网络编码研究均限于有限域Fq中的线性网络编码。网络编码的构
4、造算法网络编码构造算法解决的主要问题是如何有效求得每条链路对应的编码向量，并运用该编码向量进行线性操作计算出链路上传输的信息向量。编码算法的复杂性是衡量网络编码能否有效实现的重要依据。典型的算法包括指数时间算法[6]、多项式时间算法[7]和贪婪算法[8]等，其中因多项式时间算法具有较低的复杂性，因此具有重要的理论和应用价值。线性网络编码线性网络编码对单位容量的信道进行编码,当连接两个节点的有向链路的容量大于1时,把这条链路分成多条单位容量的信道。对于节点v∈V,记In(v)和Out(v)分别为输入信道集和输出信道集,
5、In(v)
6、和
7、Out(v)
8、分别为节点v的输入信道数和输出信道数。
9、组播网络中,各节点收到对应的单位信息,或称为字符,在进行数据转发前,需要对这些信息进行编码。我们将这类信息称为源信息。假定一个节点的源信息为X1,X2,……X
10、In(v)
11、,那么应用线性网络编码后各信道输出的信息为:Yi=gi1X1+gi2X2+……+gi
12、In(v)
13、X
14、In(v)
15、公式(3)其中i=1,2,……,
16、Out(v)
17、,gi1,gi2,……,gi
18、In(v)
19、为有限域GF(2m)上的一组系数。我们将系数gi=(gi1,gi2,……,gi
20、In(v)
21、)称为编码向量,将Yi称为信息向量。当输出信息Yi成为下游节点的输入信息时,节点将对接收到的信息进行新一轮的编码。新的编码信
22、息表示如下:Yi’=gi1’X1’+gi2’X2’+……+gi
23、In(v)
24、’X
25、In(v)
26、’公式(4)假设接收节点接收到的编码向量为(g1,g2,……,gm),信息向量为(Y1,Y2,……,Ym),为了求出源点播出的信息,我们需要求解以下等式:Yj=gj1X1+gj2X2+……+gjnXn公式(5)其中,j=1,2,…,m。也相当于求解如下的线性方程组:其中,X1,X2,…,Xn为源点播出的信息。要想恢复出源点播出的信息,只需要解以上的线性方程80组,由线性方程组的求解规则可知,公式(6)中需要m=n才有可能解码,但是由于存在编码向量线性相关的情况,所以m=n不是解码成功的充分条件
27、。只有当该方程组的系数矩阵的秩为源点的组播率h时,才能恢复出源点播出的信息。光网络分层图模型定义 网络的物理拓扑为G(V,E,W)。其中:V表示节点集合,E表示链路,W为波长数。分层图模型的基本思想是将原始网络拓扑G(V,E,W)复制W次,分层图上的每一层对应一个波长,也称一个波长平面;然后在这个分层图上计算源节点到目的节点之间的最优路径。光网络的分层图对业务的路由和波长选择是在不同的波长层面上完成的,即在同一波长层面上完成了路由和波长的选择。
