信息通信专业：应用层组播方案举例PPT.pptx

应用层组播应用层组播应用层组播方案举例应用层组播分类应用层组播分类现有的应用层组播主要可以分为4大类：1.分发算法Mesh-first方法Tree-first方法 Implicit方法2.集中算法应用层组播的体系结构(ALMI）3.基于优先度的应用层组播 4.基于空间坐标的应用层组播应用层组播算法举例应用层组播算法举例1.TAG2.ALMI3.基于优先度的应用层组播基于优先度的应用层组播4.三维三维Delaunary三角网三角网5.组播方案比较组播方案比较6.总结总结TAGlTopology Aware GroupingPurdue University提出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的子节点（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的子节点，且修改其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，其中消息中包括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 通过利用拓扑信息获得了性能上的提高，但是它破坏了网络的分层结构，使应用层获取网络层的信息；另外拓扑的测量和网络性能的测量目前仍是没有很好解决的问题2 ALMIl应用层组播的体系结构采用集中式对成员进行管理主要针对成员数量较少的组播应用ALMI是美国华盛顿大学分校计算机系从2000年开始进行的研究项目，提出了将应用层组播作为端系统基础服务功能的体系结构。

ALMI设计了在操作系统的套接口(socket)之上，以中间件(middleware)的形式向上层应用提供组播服务的结构，中间件实现自组织组网、组播复制和转发功能，在组播成员节点之间组成一个应用层组播网ALMI研究组以Java代码实现了中间件的原型ALMI的自组织协议在组成员节点之间建立和维护一棵共享的最小代价生成树(minimum spanning tree)，支持组规模较小的多方通信ALMI可以针对上层的应用需求构建不同性能的叠加网2.1 ALMI特点在成员之间维护最小生成树减小了维护开销，但是维护开销仍然大无法单独优化从每个源出发的传输开销2.2 ALMI主要思想l在ALMI中，一个组播组由一个会话控制器和多个组播成员组成利用控制器集中对成员的管理和组播树的构造，并可以提供基于Java的中间组件l会话控制器：是一个程序实体，它运行在所有成员都能访问到的位置，它可以与某个成员运行在同一台计算机上，通常是与组的发起成员在一起，或者位于ISP提供的某个组播服务网关上组播成员之间形成一棵组播树组播树中的一条链路代表两个成员之间的一条单播连接数据信息沿着组播树进行分发，而控制信息则通过会话控制器与各个成员之间的单播连接进行传输。

会话控制器的主要功能会话控制器的主要功能l主要功能：1. 对加入成员进行注册和维持组播树2. 通常放置于成员容易接人的地方3. 它保证连接性： 当成员加入、离开会话或网络或主机的失效时保证网络的连接性 保证传输效率：定期从所有成员收集信息计算最小剪枝树l结构：2.3 ALMI控制协议：1. 功能：ALMI利用控制协议在会话控制器和成员之间进行通信主要负责成员管理，性能监控，路由等工作2. 包头格式： 2.4 控制协议包头格式说明l标志位的作用为：连接请求和回应；性能监测信息；分发树信息；邻居监测更新信息；分离信息l树的表示域指明树的版本数，可以用来防止组播树的循环和分离循环可能的原因，丢失树的更新信息、成员间不同的响应延迟2.5 ALMI中成员的操作l当有成员要加入组的时候首先成员定位到控制器，在组初始化的时候控制器已经用不同的方式对会话ID和控制器地址及端口号进行了声明接着成员就向控制器发送加入消息，并从控制器获得它的ID和父节点的地址然后该成员就发送嫁接消息给它的父节点，完成后就可以传输数据了2.6 ALMI组播树的构造lALMI组播树是一棵连接所有成员的虚拟最小剪枝树它是利用控制器与所有成员用(父，子)表通信结果计算所得的。

可以根据不同的性能指标进行分发树的构造，如带宽、延迟等l组播树的优化，成员将它们的监测报告发送给控制器，控制器就可以根据这些信息对分发树进行优化3 基于优先度的应用层组播基于优先度的应用层组播 l背景 ：（ALMI，ESM，YOID等）应用层组播协议仅仅是利用网络层参数作为建树依据在这些协议中，每个节点的优先度是相同的在一些应用中的确存在这样的情况，例如：视频点播，视频会议等 但在其他一些应用却有不同的情况如：大规模网络游戏，大规模分布式仿真系统等节点在这些系统中由于所处位置不同而具有不同的优先度优先度越大的实体则它收到的更新时间越短，也就意味着两个节点之间的路径越短而当节点的优先度小时，两个节点之间的路径不是最优，协议会根据优先度选择合适的路径给这两个节点 基于优先度的应用层组播协议 l在结构上被分为两部分： 起始节点：在系统启动的初级阶段，选定一个节点作为起始节点，它的IP地址通过广播的方式通知所有别的系统成员这个节点一方面记录分布式虚拟环境中所有实体的位置，并不断更新它们的位置，另一方面根据这些实体的位置采用HLA机制，为每个有状态更新的实体确定组播组并把组播成员信息发送给这个状态更新实体所在的节点。

它本身不参与数据发送，同时也不参与建树过程这样做最大限度的保证了系统的稳定性，一旦起始节点出现异常，也不会影响到整个系统的工作仅仅是新的节点无法加入到系统中发送节点：发送节点就是那些有状态更新的实体所在的节点这些节点负责组播树的构建，它们自身是树的根节点在建树过程中，根据从起始节点收到的成员的优先度来构建组播树建树的过程首先由起始节点计算出组播组中成员的优先度当每个发送实体所在节点接收到组播成员信息和优先度信息时，若实体的优先度等于1，则它进入到队列1中；若是小于1，则进入到队列2采用两个队列的目的是为了方便的构建出基于优先度的组播树 若队列1不为空，则所有队列1中的实体所在节点直接连到发送节点上，而队列2中的节点会选择队列1中的节点作为其父节点，这一选择是周期性的在此不考虑节点的带宽承受能力若队列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优缺点：那些具有较高优先度的节点会进入到队列1中，因此在建树中会直接连到发送节点上去直连表示的路径是最短的，也就是符合了依靠优先度建树的思想组播树不会超过3层，同时又是单步建树，所以建树的时间要短于最小生成树同YOID一样，这里采用的是单步建树但有一点与YOID不同，它不需要循环检测机制，这是由于每个节点都有优先值的原因同时优先值大的不会成为优先值小的子节点，所以不可能产生循环的情况4 Delaunay三角网三角网二维二维DelaunayDelaunay三角网（三角网（DTDT）：）： 网中的任意三角形的外接圆内不含任何网中的任意三角形的外接圆内不含任何一个组内其它节点一个组内其它节点 Delaunay三角网三角网二维二维DelaunayDelaunay三角网（三角网（DTDT）特性：）特性：1.1.任意两点间有一组可互换的无重复路径；任意两点间有一组可互换的无重复路径；2.2.每个节点的棱数少于每个节点的棱数少于6 6条；条；3.3.只要拓扑结构建立，数据包传输信息就已只要拓扑结构建立，数据包传输信息就已包含在节点中包含在节点中，不需路由协议，不需路由协议。

Delaunay三角网三角网Jorg Liebeherr和和Michael Nahas提出提出DT叠加：网中每个节点都对应着一个参与叠加：网中每个节点都对应着一个参与组播组的网络终端即由叠加网所有节组播组的网络终端即由叠加网所有节点组成的点组成的Delaunay三角网中，如果两个三角网中，如果两个节点相连，它们对应的两个实际节点在节点相连，它们对应的两个实际节点在DT叠加网中就有逻辑链接，互为邻居叠加网中就有逻辑链接，互为邻居Delaunay三角网三角网DT应用层组播协议的实现：应用层组播协议的实现： 坐标映射坐标映射 组织拓扑组织拓扑 实现路由实现路由 Delaunay三角网三角网三维三维DelaunayDelaunay三角网（三角网（DTDT）：）：1.1.二维的扩展，有类似性质，适于应用层二维的扩展，有类似性质，适于应用层组播叠加网的构建组播叠加网的构建2.2.节点间的传输时延与距离相关，而节点节点间的传输时延与距离相关，而节点存在于三维物理空间存在于三维物理空间 Delaunay三角网三角网三维三维DelaunayDelaunay三角网（三角网（DTDT）：）：特定源节点的组播树由特定源节点的组播树由DTDT网唯一确定；网唯一确定；组播和单播在组播和单播在DTDT网生成树的棱上进行，发网生成树的棱上进行，发送者是树的根节点；送者是树的根节点；节点根据旋转路由做出局部传输决定。

节点根据旋转路由做出局部传输决定 Delaunay三角网三角网三维三维DelaunayDelaunay三角网（三角网（DTDT）：）：旋转路由用于确定组播的路由树，以分布方旋转路由用于确定组播的路由树，以分布方式计算它们的孩子节点式计算它们的孩子节点。