【大学课件】信息通信专业：应用层组播方案举例

1、 应用层组播应用层组播应用层组播方案举例编辑课件应用层组播分类应用层组播分类现有的应用层组播主要可以分为4大类：1.分发算法 Mesh-first方法 Tree-first方法 Implicit方法2.集中算法应用层组播的体系结构(ALMI）3.基于优先度的应用层组播 4.基于空间坐标的应用层组播编辑课件应用层组播算法举例应用层组播算法举例1. TAG2. ALMI3. 基于优先度的应用层组播基于优先度的应用层组播4. 三维三维Delaunary三角网三角网5. 组播方案比较组播方案比较6. 总结总结编辑课件TAGlTopology Aware GroupingPurdue Universit

2、y提出Tree-first方法将延迟作为最重要的指标，同时考虑带宽编辑课件1.1 TAG：路径匹配算法：路径匹配算法(1) lComplete Path Matching Algorithmlfamily table (FT) 定义了当前节点的父子关系 IPaddr（A）：指明节点A的IP地址 P（S，A）：节点S到A的最短路径 len（P）：P所经过的路由器数l 基于最小延时构建算法，减少传播过程中数据的复制次数l 主要思想是使新加入的节点和父节点能够共用尽可能长的网络路径。 编辑课件TAG：路径匹配算法：路径匹配算法(2)l 路由匹配算法 存在三种情况如下图：（a）新成员D8将成为D4的子

3、节点（b）D8加入FT表。D4、D7将成为D8的子成员， 且从当前FT表中退出。（c）D8加入FT表编辑课件1.2 TAG：组播：组播Tree构建构建l成员加入新节点N发送JOIN消息给根节点S，S收到后计算到N需经过的路由器数（spath），执行路径匹配算法。会有两种结果：1）N成为S的子节点，相应的修改S的FT（family table）表2）发送FIND消息（包括N的IP地址， spath ）到子节点，子节点在执行相应的路由匹配算法，直到找到N的父节点。编辑课件TAG：组播：组播Tree构建构建节点加入的一个具体的实例1）D1的加入 D1发送JOIN消息给根节点S，D1成为 S的子节点，

4、且修改其FT表，见图（a）2）D2的加入，图（b）S根据spath的值（R1，R2，R4）执行路径匹配算法，发现D1作为D2的 父节点比其本身要好，于是S发送FIND消息给D13）D3的加入，图（c）与D2类似，选择D2为其父节点编辑课件TAG：组播：组播Tree构建构建4）D4的加入，图（d） D4加入时，决定D1作为其父节点，D3成为D4的子节点。更新D1和D4的FT表。5）D5的加入与D2，D3的加入类似，选择D4为其父节点。 图（e）给出了整个的多播转发树每个节点的FT表编辑课件l成员离开 通过发送LEAVE消息给其父节点 例如，如果D4要离开，D4发送LEAVE给D1，其中消息中包括

5、D4的FT表。D1收到LEAVE消息后，D1把D4从其FT表中移走，并且把D4的子节点全部加入到自己的FT表中。右图（a）（b）描述整个过程编辑课件l节点维护 节点之间定期交换可达消息，当子节点不可达时，父节点将其从FT表中除去；当父节点不可达时，各子节点必须重新发送JOIN消息加入。编辑课件1.3 TAG：性能：性能l 时间复杂度： k(logkN )2 假定有n个成员，每个成员有k个子节点l 成员退出复杂度：klogkN 编辑课件1.4 TAG：优缺点：优缺点lTAG 通过利用拓扑信息获得了性能上的提高，但是它破坏了网络的分层结构，使应用层获取网络层的信息；另外拓扑的测量和网络性能的测量目

6、前仍是没有很好解决的问题。编辑课件2 ALMIl应用层组播的体系结构采用集中式对成员进行管理主要针对成员数量较少的组播应用 ALMI是美国华盛顿大学分校计算机系从2000年开始进行的研究项目，提出了将应用层组播作为端系统基础服务功能的体系结构。ALMI设计了在操作系统的套接口(socket)之上，以中间件(middleware)的形式向上层应用提供组播服务的结构，中间件实现自组织组网、组播复制和转发功能，在组播成员节点之间组成一个应用层组播网。ALMI研究组以Java代码实现了中间件的原型。ALMI的自组织协议在组成员节点之间建立和维护一棵共享的最小代价生成树(minimum spanning

7、 tree)，支持组规模较小的多方通信。ALMI可以针对上层的应用需求构建不同性能的叠加网。编辑课件2.1 ALMI特点在成员之间维护最小生成树减小了维护开销，但是维护开销仍然大无法单独优化从每个源出发的传输开销编辑课件2.2 ALMI主要思想l 在ALMI中，一个组播组由一个会话控制器和多个组播成员组成。利用控制器集中对成员的管理和组播树的构造，并可以提供基于Java的中间组件。l 会话控制器：是一个程序实体，它运行在所有成员都能访问到的位置，它可以与某个成员运行在同一台计算机上，通常是与组的发起成员在一起，或者位于ISP提供的某个组播服务网关上。组播成员之间形成一棵组播树。组播树中的一条链

8、路代表两个成员之间的一条单播连接。数据信息沿着组播树进行分发，而控制信息则通过会话控制器与各个成员之间的单播连接进行传输。编辑课件会话控制器的主要功能会话控制器的主要功能l 主要功能：1. 对加入成员进行注册和维持组播树。2. 通常放置于成员容易接人的地方。3. 它保证连接性： 当成员加入、离开会话或网络或主机的失效时保证网络的连接性 保证传输效率：定期从所有成员收集信息计算最小剪枝树。l 结构：编辑课件2.3 ALMI控制协议：1. 功能：ALMI利用控制协议在会话控制器和成员之间进行通信。主要负责成员管理，性能监控，路由等工作。2. 包头格式：编辑课件2.4 控制协议包头格式说明l 标志位

9、的作用为：连接请求和回应；性能监测信息；分发树信息；邻居监测更新信息；分离信息。l 树的表示域指明树的版本数，可以用来防止组播树的循环和分离。循环可能的原因，丢失树的更新信息、成员间不同的响应延迟。编辑课件2.5 ALMI中成员的操作l 当有成员要加入组的时候首先成员定位到控制器，在组初始化的时候控制器已经用不同的方式对会话ID和控制器地址及端口号进行了声明。接着成员就向控制器发送加入消息，并从控制器获得它的ID和父节点的地址。然后该成员就发送嫁接消息给它的父节点，完成后就可以传输数据了。编辑课件2.6 ALMI组播树的构造l ALMI组播树是一棵连接所有成员的虚拟最小剪枝树。它是利用控制器与

10、所有成员用(父，子)表通信结果计算所得的。可以根据不同的性能指标进行分发树的构造，如带宽、延迟等。l 组播树的优化，成员将它们的监测报告发送给控制器，控制器就可以根据这些信息对分发树进行优化。编辑课件3 基于优先度的应用层组播基于优先度的应用层组播 l 背景 ： （ALMI，ESM，YOID等）应用层组播协议仅仅是利用网络层参数作为建树依据。在这些协议中，每个节点的优先度是相同的。在一些应用中的确存在这样的情况，例如：视频点播，视频会议等。 但在其他一些应用却有不同的情况。如：大规模网络游戏，大规模分布式仿真系统等。节点在这些系统中由于所处位置不同而具有不同的优先度。优先度越大的实体则它收到的

11、更新时间越短，也就意味着两个节点之间的路径越短。而当节点的优先度小时，两个节点之间的路径不是最优，协议会根据优先度选择合适的路径给这两个节点。 编辑课件基于优先度的应用层组播协议 l 在结构上被分为两部分： 起始节点：在系统启动的初级阶段，选定一个节点作为起始节点，它的IP地址通过广播的方式通知所有别的系统成员。这个节点一方面记录分布式虚拟环境中所有实体的位置，并不断更新它们的位置，另一方面根据这些实体的位置采用HLA机制，为每个有状态更新的实体确定组播组。并把组播成员信息发送给这个状态更新实体所在的节点。它本身不参与数据发送，同时也不参与建树过程。这样做最大限度的保证了系统的稳定性，一旦起始

12、节点出现异常，也不会影响到整个系统的工作。仅仅是新的节点无法加入到系统中。 发送节点：发送节点就是那些有状态更新的实体所在的节点。这些节点负责组播树的构建，它们自身是树的根节点。在建树过程中，根据从起始节点收到的成员的优先度来构建组播树。编辑课件建树的过程 首先由起始节点计算出组播组中成员的优先度。 当每个发送实体所在节点接收到组播成员信息和优先度信息时，若实体的优先度等于1，则它进入到队列1中；若是小于1，则进入到队列2。采用两个队列的目的是为了方便的构建出基于优先度的组播树。 若队列1不为空，则所有队列1中的实体所在节点直接连到发送节点上，而队列2中的节点会选择队列1中的节点作为其父节点，

13、这一选择是周期性的。在此不考虑节点的带宽承受能力。若队列1为空，则队列2中的节点会直接连接到发送节点上。这样即充分考虑到了实体优先度的作用，同时也充分利用了带宽。 随着节点状态的更新，以上算法会重复执行，以保持组播树的有效性。 编辑课件实例： l 图1给出了虚拟环境中实体的位置情况。其中A是状态更新实体，而B、C、D在实体A的碰撞区域中，而E、F、G中实体A的发现区域中，所以B、C、D进入队列1中，而E、F、G进入队列2中。根据图1 而构建的组播树见图2。图1 实体在分布式虚拟环境中的位置图2 实体A的组播树HEFGDABCColisionRegionObservationN Region编辑

14、课件优缺点： 那些具有较高优先度的节点会进入到队列1中，因此在建树中会直接连到发送节点上去。直连表示的路径是最短的，也就是符合了依靠优先度建树的思想。 组播树不会超过3层，同时又是单步建树，所以建树的时间要短于最小生成树。 同YOID一样，这里采用的是单步建树。但有一点与YOID不同，它不需要循环检测机制，这是由于每个节点都有优先值的原因。同时优先值大的不会成为优先值小的子节点，所以不可能产生循环的情况。编辑课件4 Delaunay三角网三角网二维二维DelaunayDelaunay三角网（三角网（DTDT）：）： 网中的任意三角形的外接圆内不含任何网中的任意三角形的外接圆内不含任何一个组内其

15、它节点。一个组内其它节点。编辑课件 Delaunay三角网三角网二维二维DelaunayDelaunay三角网（三角网（DTDT）特性：）特性：1.1.任意两点间有一组可互换的无重复路径；任意两点间有一组可互换的无重复路径；2.2.每个节点的棱数少于每个节点的棱数少于6 6条；条；3.3.只要拓扑结构建立，数据包传输信息就已只要拓扑结构建立，数据包传输信息就已包含在节点中包含在节点中，不需路由协议，不需路由协议。编辑课件 Delaunay三角网三角网Jorg Liebeherr和和Michael Nahas提出提出DT叠加：网中每个节点都对应着一个参与叠加：网中每个节点都对应着一个参与组播组的

16、网络终端。即由叠加网所有节组播组的网络终端。即由叠加网所有节点组成的点组成的Delaunay三角网中，如果两个三角网中，如果两个节点相连，它们对应的两个实际节点在节点相连，它们对应的两个实际节点在DT叠加网中就有逻辑链接，互为邻居叠加网中就有逻辑链接，互为邻居编辑课件Delaunay三角网三角网DT应用层组播协议的实现：应用层组播协议的实现： 坐标映射坐标映射 组织拓扑组织拓扑 实现路由实现路由编辑课件 Delaunay三角网三角网三维三维DelaunayDelaunay三角网（三角网（DTDT）：）：1.1.二维的扩展，有类似性质，适于应用层二维的扩展，有类似性质，适于应用层组播叠加网的构建

17、组播叠加网的构建2.2.节点间的传输时延与距离相关，而节点节点间的传输时延与距离相关，而节点存在于三维物理空间存在于三维物理空间编辑课件 Delaunay三角网三角网三维三维DelaunayDelaunay三角网（三角网（DTDT）：）：特定源节点的组播树由特定源节点的组播树由DTDT网唯一确定；网唯一确定；组播和单播在组播和单播在DTDT网生成树的棱上进行，发网生成树的棱上进行，发送者是树的根节点；送者是树的根节点；节点根据旋转路由做出局部传输决定。节点根据旋转路由做出局部传输决定。编辑课件 Delaunay三角网三角网三维三维DelaunayDelaunay三角网（三角网（DTDT）：）：

18、旋转路由用于确定组播的路由树，以分布方旋转路由用于确定组播的路由树，以分布方式计算它们的孩子节点。式计算它们的孩子节点。编辑课件 Delaunay三角网三角网具体而言：对于以具体而言：对于以R R为根节点的生成树，如果棱是和为根节点的生成树，如果棱是和的分界边，如果节点的分界边，如果节点C C基于节点基于节点A A到根节点到根节点R R的角度比的角度比节点节点B,DB,D小，那么节点小，那么节点C C就是节点就是节点A A的孩子节点。每个的孩子节点。每个节点按如上步骤进行，就生成了以节点按如上步骤进行，就生成了以R R为根节点的树为根节点的树编辑课件 Delaunay三角网三角网三维三维Delau