《《自愈算法设计》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《自愈算法设计》PPT课件.ppt（18页珍藏版）》请在三一文库上搜索。
1、Contents,课题提出背景,1,相关资料解读,2,自愈算法设计,3,今后工作内容,4,Background,Background,虽然分布式网络有以上优点，但它结构上不像传统集中式网络那样存在中心节点而不易于管理。分布式网络的分散性使得网络功能数据分散，因此各个节点必须都要得到照顾 而目前对网络的要求是应当可管、可控的，生存性成为网络技术研究的关键问题之一，其中研究具有自组织特性的自愈机制是生存性研究的重点,Information,恢复 在故障发生后根据网络状态实时的为受影响的业务提供恢复路径,保护 在故障发生前预留资源用于对可能发生故障的业务进行恢复,自愈,Contrast,两种策略优
2、劣性对比,目前研究的多是动态自愈算法，即恢复策略，所以通过以上对比，尽可 能多缩短恢复时延，有效利用网络资源，是目前分布式自愈算法的方向,保护,恢复时间快,消耗固有资源多,恢复,恢复时间延迟,资源利用比较有效,Solution,MDF（多目的地泛播）： 1、整个过程分5个阶段:初始阶段、传播阶段、选择阶段、切换阶段和重置阶段。 2、在该算法中定义了以下几种自愈消息:恢复消息resMSG、证实消息ackMSG、取消消息canMSG、切换消息swiMSG 3、自愈消息的结构包括： sender ID：表示恢复消息的产生处 upSender ID: sender的上游节点号 messageType:
3、用于区分是哪一类自愈消息,Multi-destination Flooding,route:指出自愈消息经过的路由(由节点ID序列组成) route i.nodeID: 指迂回路由中第i条链路的上游节点号 routej.idle:指第J条链路上的空闲容量 failed path ID:故障通道号 failedpath:故障通道容量，峰值速率，即请求的带宽 failedpath route:受损通道的路由 usablepath:可用通道容量 failedlink ID:故障链路号,Self-healing process,初始,传播,选择,切换,重置,Initial phase,初始阶段,Ini
4、tial phase,当C,D节点间发生断缆故障时，与故障链相邻的每个节点(C,D)收到一个告警(AIS)，并检测到故障 对某个受损的通道，其源点为A，宿点为F,A-B-C-D-E-F为通道的路由。 对该通道来讲，确定从C节点到源点A的各节点(C,B,A)分别为senderl ,sender2,sender3，确定从D到宿点F的各节点(D,E,F）为选择方集(chooser set),Transmission,传播阶段 由C产生 resMSGI，并向除B,D以外的相邻节点泛播恢复消息resMSG11，其目的地为chooser set。同时由B节点产生resMSG12，并向除A,C以外的相邻节点
5、发送恢复消息resMSG12，这时，B作为resMSG12的senderlD，以D-E-F作为chooser set在网中泛播。同理，由A产生，resMSG13 当中介节点(如G)收到resMSG时，保留可用的通道容量来用作迁回通道，并将，resMSG泛播，只是将其中的一些数据进行更新。具体在中介节点的处理步骤如下:,Transmission,1,附上中介节点ID，更新当前路由ID，以记录消息所经过的路由,2,更新空闲容量数,3,判断某个方向的链路上的空闲容量是否为0，若为0，停止向该方向传播；不为0，更新可用通道容量后传播,Transmission,4,判断某个方向上的节点是否在routei
6、.nodeID上，若在，则不向该方向泛播resMSG，若不在，则继续泛播,5,当属于同一故障通道的几个resMSG(如resMSG11、12 、13)均到达某个中介节点时，对resMSG的取舍原则是，sender ID离源点越近越优先,6,每个中介节点收到resMSG，将其ID号与消息上的chooserID号比较，若相等，则停止传播，若不相等，则将该消息处理，并向相邻节点发送,Choose,选择阶段 当在网中的任何一个中介节点(除沿该通道路由上的节点外的网中节点)收到第一个恢复消息后，就将该恢复消息传到与其相邻链路的下一个节点，并对随后到达的恢复消息进行保持。 所有的恢复消息都是以D-E-F作
7、为其目的地。当D,E,F中的任何一个节点首先收到某个恢复消息，就启动选择阶段。chooser set中的每个节点收到resMSG之后，就以“容量最大”为原则选取一条迂回通道，并向该受损通道的源点(A)返回一个证实消息(ackMSG)。当A收到第一个到达的ackMSG之后，就选取该路由作为恢复路由，即“时间最短原则”。当该通道容量不能完全恢复故障通道时，就用第二个ackMSG作为恢复路由，直至恢复率达到100%。若恢复完成，则对随后到达的恢复消息以取消消息(canMSG)代替，沿原路返回，同时向其他chooser发送停止信号，表示该故障通道已完全恢复。,Choose&Switch&Reset,中
8、介节点每收到一个ackMSG，要将ackMSG请求预占的空闲容量与实际能提供的空闲容量比较，若够用，则预占该容量，若不够用位（如只有k个)，则留用k个，同时生成一个canMSG消息，回发往chooser，以取消沿途多占的容量。 切换阶段 当源点收到反向传来的一个ackMSG后，即产生一个切换消息(swiMSG) ,沿该路由向chooser方向发送，各中介节点收到swiMSG时，修改其中的通道号 重置阶段 在完成恢复后，节点状态需返回到无故障状态,Complement,补充：由于MDF自愈算法中存在多个sender产生的恢复消息。因此在网中的中介节点就可能收到为恢复同一通道的来自不同sender
9、的恢复消息，原则是只对先到达的resMSG进行泛播，而对于后到的恢复消息，则令其在节点的缓冲器中等待。这就避免了重复保留空闲容量以及网中的消息泛滥问题。当返回的证实消息到达中介节点时，它在缓冲器内保持的resMSG中选取一条最佳路由，并保留空闲容量。如图示：,Advantage,1、一改传统的单选择方和单发送方的恢复方法，而是发送方和选择方都不固定； 首先发送方是沿上游的故障检测点到通道源点所有节点(如:A、B、C），每个发送方都泛播用于恢复故障通道的消息； 其次每个恢复消息的目的地(选择方)是从下游的故障检测点到通道宿点的任何一个节点。这些节点谁最先收到一个恢复消息，就沿该消息所传的迁回路由返回一个证实消息，这都将大大加快最佳路径的搜索速度，减小恢复时延,Advantage,2、由于MDF中多选择方和多发送方策，以及容量最大和最短时间原则的应用，不仅可以快速恢复受损通道的路由（分布式自愈的基本目的），而且可以改善原有路由，使迂回路由比原路由还好,