【大学课件】信息通信专业：CAN 算法的实现与分析PPT.ppt

《【大学课件】信息通信专业：CAN 算法的实现与分析PPT.ppt》由会员分享，可在线阅读，更多相关《【大学课件】信息通信专业：CAN 算法的实现与分析PPT.ppt（15页珍藏版）》请在三一办公上搜索。

1、CAN 算法的实现与分析,应用层组播主要算法,小规模多元组播方案大规模多元组播方案基于多树的方案基于特定逻辑的方案（CAN)其它,研究主要内容：,CAN算法1.负载均衡2.路由优化,负载均衡,问题的引出：随机选取节点进行划分会导致各节点负担不一。可行解决方案：1.广播2.梯度法3.分布式堆,广播：,这是一种基于泛洪查询的方法，新节点利用多播协议获取其他所有节点的负载信息，并把负载最重的节点选为目标节点进行划分。缺点：网络开销大,梯度法,每个节点每隔T时间与其邻居节点交换信息 如果周围没有负载比自己大的节点，则把next指针指向自己。否则，把next指针指向邻居节点中负载最大的节点。,分布式堆算

2、法,路由优化,多维坐标空间多哈希最大面积寻路,CAN算法的C语言仿真,运行CAN.exe演示功能：加入节点 节点失效 节点合并 节点接管仿真：中等规模网络负载均衡仿真,一种简单的负载均衡优化策略,基于随机选择节点引入梯度法多次（N）随机选取节点进行梯度搜索以寻找负载最大的节点,仿真结果1：,横坐标：不同的N值纵坐标纵坐标：系统平均负载偏差,仿真结果2,仿真结果3：,组播消息传递机制（基于CAN）,1.源节点将消息发至它的所有邻居节点。2.收到邻居节点的消息后向在第1维到第i-1维的邻居节点转发，和向它接收到消息的反方向的第i维邻居节点转发。3.如果一个消息已经沿着从源节点沿着那一维走了这一维空

3、间一半的尺度，则节点不再转发向本维节点转发，以避免洪泛出现循环。4.节点不转发缓存中已有序号的消息。对于一个均匀分配的空间，上述算法保证了每个节点可以收到正好一次消息。对于不是均匀分配的空间，节点可能从邻居节点收到多次相同的消息。,组播消息传递机制（基于CAN）,节点C和D都互相知道而且均知道E的坐标，因此可以使用某种特定的方法使只有一个节点向E发送数据。但这条规则，仅仅能消除第1维的复制。高维情况就不成立了。如果一个节点依据特定规则不向第2维邻居转发消息，但不能保证其他节点最终会在第2维向这个邻居节点转发消息。因为，节点可能从第1维收到这个消息因此就不会在第2维转发这个消息。例如，我们假设A不向E转发。由于C在第1维空间从A得到消息，它不会向第2维邻居发送消息，因此节点E和其他有相同Y坐标的节点将永远不会收到消息。,