【大學】信息通信專業(yè)：CAN 算法的實現(xiàn)與分析

1、整理課件整理課件 CAN 算法的實現(xiàn)與分析算法的實現(xiàn)與分析整理課件整理課件應用層組播主要算法l小規(guī)模多元組播方案l大規(guī)模多元組播方案l基于多樹的方案l基于特定邏輯的方案（CAN)l其它整理課件整理課件研究主要內容：lCAN算法1.負載均衡2.路由優(yōu)化整理課件整理課件負載均衡問題的引出：隨機選取節(jié)點進行劃分會導致各節(jié)點負擔不一。可行解決方案：1.廣播2.梯度法3.分布式堆整理課件整理課件廣播：l這是一種基于泛洪查詢的方法，新節(jié)點利用多播協(xié)議獲取其他所有節(jié)點的負載信息，并把負載最重的節(jié)點選為目標節(jié)點進行劃分。l缺點：網(wǎng)絡開銷大整理課件整理課件梯度法 每個節(jié)點每隔T時間與其鄰居節(jié)點交換信息 如果周圍

2、沒有負載比自己大的節(jié)點，則把next指針指向自己。否則，把next指針指向鄰居節(jié)點中負載最大的節(jié)點。 整理課件整理課件分布式堆算法整理課件整理課件路由優(yōu)化l多維坐標空間l多哈希l最大面積尋路整理課件整理課件CAN算法的C語言仿真l運行l(wèi)演示功能： 加入節(jié)點 節(jié)點失效 節(jié)點合并 節(jié)點接管仿真：中等規(guī)模網(wǎng)絡負載均衡仿真整理課件整理課件一種簡單的負載均衡優(yōu)化策略l基于隨機選擇節(jié)點l引入梯度法l多次（N）隨機選取節(jié)點進行梯度搜索以尋找負載最大的節(jié)點整理課件整理課件仿真結果1：橫坐標：不同的N值縱坐標縱坐標：系統(tǒng)平均負載偏差2001(.)200isizeofNode iAE整理課件整理課件仿真結果2整理

3、課件整理課件仿真結果3：整理課件整理課件組播消息傳遞機制（基于CAN）1.源節(jié)點將消息發(fā)至它的所有鄰居節(jié)點。2.收到鄰居節(jié)點的消息后向在第1維到第i-1維的鄰居節(jié)點轉發(fā)，和向它接收到消息的反方向的第i維鄰居節(jié)點轉發(fā)。3.如果一個消息已經(jīng)沿著從源節(jié)點沿著那一維走了這一維空間一半的尺度，則節(jié)點不再轉發(fā)向本維節(jié)點轉發(fā)，以避免洪泛出現(xiàn)循環(huán)。4.節(jié)點不轉發(fā)緩存中已有序號的消息。對于一個均勻分配的空間，上述算法保證了每個節(jié)點可以收到正好一次消息。對于不是均勻分配的空間，節(jié)點可能從鄰居節(jié)點收到多次相同的消息。整理課件整理課件組播消息傳遞機制（基于CAN）節(jié)點C和D都互相知道而且均知道E的坐標，因此可以使用某種特定的方法使只有一個節(jié)點向E發(fā)送數(shù)據(jù)。但這條規(guī)則，僅僅能消除第1維的復制 。高維情況就不成立了。如果一個節(jié)點依據(jù)特定規(guī)則不向第2維鄰居轉發(fā)消息，但不能保證其他節(jié)點最終會在第2維向這個鄰居節(jié)點轉發(fā)消息。因為，節(jié)點可能從第1維收到這個消息因此就不會在第2維轉發(fā)這個消息。例如，我們假設A不向E轉發(fā)。由于