【文章內(nèi)容簡(jiǎn)介】 se If Addable(X) 選擇一個(gè)子節(jié)點(diǎn) Y Addable(Y ) 并且 D(Y )+d(Y , P)最小 轉(zhuǎn)發(fā)加入請(qǐng)求到 Y Else 選擇一個(gè)子節(jié)點(diǎn) Y Reachable(Y ) 并且 D(Y )+d(Y , P)最小 轉(zhuǎn)發(fā)加入請(qǐng)求到 Y 當(dāng)新節(jié)點(diǎn)加入后，若集群的尺寸超過(guò)了 3k，則需要進(jìn)行拆分。 節(jié)點(diǎn)離 開(kāi)： 若一個(gè)節(jié)點(diǎn) X 離開(kāi)，由于控制協(xié)議，使得 X 的父節(jié)點(diǎn)和子節(jié)點(diǎn)，和所有同一集群的節(jié)點(diǎn)都能發(fā)現(xiàn)。 X 的父節(jié)點(diǎn)將刪除到 X 的連接。若 X 的最高層 j0，對(duì)于 j1 層 X 的子節(jié)點(diǎn)所在集群，頭節(jié)點(diǎn) Y 將在 j 層的集群同伴中為它們尋找一個(gè)度最小的節(jié)點(diǎn) Z 作為它們新的父節(jié)點(diǎn)。并且，由于 X 為 0~j1 層集群的頭節(jié)點(diǎn)，需要從第 0 層的 X 的下屬中隨機(jī)選出一個(gè)節(jié)點(diǎn) X’替代 X 的位置，并且 X’出現(xiàn)在第 j 層接受 X 的父節(jié)點(diǎn)的連接。 當(dāng)節(jié)點(diǎn)離開(kāi)使得集群尺寸過(guò)小時(shí)，還須與別的集群進(jìn)行聚合。 圖 ZIGZAG 的組播樹(shù) 2. 基于樹(shù)優(yōu)先的策略 Host Multicast Tree Protocol（ HMTP） [13] University of California 和 University of Michigan 提出 結(jié)構(gòu) 在 Host Multicast 中， 每個(gè) IP 組播網(wǎng)絡(luò)選出一個(gè)代表成員 (Designated Member)來(lái)代表整個(gè)組播網(wǎng)絡(luò)，代表成員組成應(yīng)用層組播網(wǎng)絡(luò)，在它們之間構(gòu)造共享組播樹(shù)。 Host Multicast 體系結(jié)構(gòu)可以支持任意規(guī)模的 IP 組播網(wǎng)絡(luò)，包括單個(gè)主機(jī)，局域網(wǎng)，校園網(wǎng)等。所有成員節(jié)點(diǎn)都具有 IP 組播能力（目前大部分操作系統(tǒng)都支持 IP 組播）。在每一個(gè) IP 組 播網(wǎng)絡(luò)中，使用 IP 組播接收和發(fā)送數(shù)據(jù)。每個(gè) IP 組播網(wǎng)絡(luò)中選舉出一個(gè)代表成員（ Designated Member）代表整個(gè)組播網(wǎng)絡(luò)。不同的代表節(jié)點(diǎn)之間通過(guò) UDP 隧道相連。所有的代表節(jié)點(diǎn)之間組成一棵共享樹(shù)，也就是說(shuō)，從根節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)都只有一條無(wú)循環(huán)的路徑，稱為根路徑。每個(gè)組播組都需要一個(gè)匯集節(jié)點(diǎn) HMRP(Host Multicast Rendezvous Point)，匯集節(jié)點(diǎn)的功能是為新節(jié)點(diǎn)提供組的成員信息。 HMRP 知道共享樹(shù)的根節(jié)點(diǎn)信息，當(dāng)新節(jié)點(diǎn)向它發(fā)出查詢請(qǐng)求時(shí)，它會(huì)把根節(jié)點(diǎn)的地址返回給新節(jié)點(diǎn)。 HMRP 并不參加數(shù)據(jù)轉(zhuǎn)發(fā)，因此 HMM 的位置并不會(huì)對(duì)轉(zhuǎn)發(fā)性能產(chǎn)生任何影響。一個(gè) HMRP 可以同時(shí)為多個(gè)組服務(wù)。 圖 樹(shù)的構(gòu)建 節(jié)點(diǎn)加入算法如下 1) 所有的成員被看作是潛在的有效雙親節(jié)點(diǎn)，用棧 S來(lái)保存以前的潛在雙親節(jié)點(diǎn) 2) 找出查詢 HMRP所得的根節(jié)點(diǎn)，把所得的根看作潛在的雙親節(jié)點(diǎn) 3) 查詢潛在的雙親節(jié)點(diǎn)來(lái)找出它的所有子節(jié)點(diǎn)，跟蹤衡量雙親和它的子節(jié)點(diǎn) 4) 找出潛在雙親和它所有子節(jié)點(diǎn)最近的成員，除了這些，其他節(jié)點(diǎn)都是無(wú)效的。果所有的節(jié)點(diǎn)都是無(wú)效的，將 棧清空，并返回第三步 5) 如果最近的成員不是目前潛在的雙親節(jié)點(diǎn)，則將目前潛在的雙親節(jié)點(diǎn)入棧，并將最近成員設(shè)成潛在的雙親節(jié)點(diǎn)，返回第三步 6) 否則，給潛在雙親節(jié)點(diǎn)發(fā)送一個(gè)節(jié)點(diǎn)加入請(qǐng)求，如果被拒絕，則將潛在雙親節(jié)點(diǎn)設(shè)成無(wú)效并返回第四步，反之，發(fā)現(xiàn)雙親節(jié)點(diǎn)，建立通向他的隧道。 例子如下 Host Multicast 中的成員自己在共享樹(shù)中尋找父節(jié)點(diǎn)。一個(gè)新節(jié)點(diǎn) H 采用下面的過(guò)程尋找自己的父節(jié)點(diǎn)。 H 首先通過(guò)詢問(wèn) HMRP 獲得共享樹(shù)的根節(jié)點(diǎn)。如圖 18 所示， H 知道 A 是樹(shù)的根節(jié)點(diǎn)， H 將把 A 設(shè)置成可行的父節(jié)點(diǎn)，并要求 A 告訴自 己 A 的子節(jié)點(diǎn)的信息。從 A和 A 的子節(jié)點(diǎn)列表中， H 選擇一個(gè)離自己最近的成員，圖中是 D，作為自己的新的可行父節(jié)點(diǎn)。 H 重復(fù)這一過(guò)程，又得到了下一個(gè)可行的父節(jié)點(diǎn) F。于是 H 向 F 發(fā)送加入請(qǐng)求，請(qǐng)求把 F 作為自己的父節(jié)點(diǎn)。 F 將根據(jù)自己的配置策略，帶寬和負(fù)載情況來(lái)決定是否接收 H的加入請(qǐng)求。如果 F 拒絕了 H 的加入請(qǐng)求， H 將把 F 標(biāo)記為不可行并回到上一層的 D 節(jié)點(diǎn)繼續(xù)查找過(guò)程，最后將 G 節(jié)點(diǎn)作為父節(jié)點(diǎn)。 成員維護(hù)自己的根路徑上的所有成員的信息。每個(gè)成員周期性的通過(guò)向根路徑上某個(gè)隨機(jī)節(jié)點(diǎn)發(fā)出加入請(qǐng)求操作來(lái)尋找更好的父節(jié)點(diǎn)（之所以不直接向根節(jié) 點(diǎn)發(fā)出請(qǐng)求是為了降低根節(jié)點(diǎn)的負(fù)擔(dān)）。掌握整個(gè)根路徑的信息可以使成員檢測(cè)是否出現(xiàn)環(huán)路。 Host Multicast 使用的是循環(huán)檢測(cè)機(jī)制而不是循環(huán)避免機(jī)制。 Host Multicast 并不創(chuàng)建 Mesh， Host Multicast 中采用的機(jī)制是讓每個(gè)成員周期性地發(fā)現(xiàn)并緩存樹(shù)中其它一些節(jié)點(diǎn)的信息。當(dāng) HMRP 失效時(shí)而共享樹(shù)又出現(xiàn)分割現(xiàn)象時(shí)，這些信息可以幫助恢復(fù)共享樹(shù)。 圖 節(jié)點(diǎn)退出 HMTP 通過(guò)周期性的與鄰居節(jié)點(diǎn)交換信息來(lái)更新?tīng)顟B(tài)，每個(gè)孩子發(fā)送更新消息給他的父母，父母通過(guò)發(fā)送回路消息來(lái)回應(yīng)。父母發(fā)送的路徑消息包含父母的根路徑。通過(guò)把它添加到父母的根路徑中，成員自己構(gòu)建了根路徑。每個(gè)成員必須維持它的孩子和根路徑表的更新。根發(fā)送更新消息給 HMRP，因此 HMRP 總能知道當(dāng)前的根節(jié)點(diǎn) 當(dāng)一個(gè)成員離開(kāi)組時(shí)，他通報(bào)給他的父母和孩子，父母簡(jiǎn)單的從他的孩子中將他刪除。離開(kāi)的孩子自己尋找新的父母節(jié)點(diǎn)。一個(gè)孩子通過(guò)下面的節(jié)點(diǎn)加入算法的反過(guò)程來(lái)尋找它的父母。 如果根節(jié)點(diǎn)離開(kāi)，他的孩子經(jīng)過(guò)一段時(shí)間的延遲再與 HMRP 聯(lián)系，第一個(gè)與 HMRP 聯(lián)系的成員將成為新的根節(jié)點(diǎn) 。 3. 基于隱含組播轉(zhuǎn)發(fā) NICE NICE [4]是一種可擴(kuò)展的應(yīng)用層組播 ,主要針對(duì)大量接收者的低帶寬、 大規(guī)模網(wǎng)絡(luò)中的 數(shù)據(jù)流應(yīng)用 ,它基于分層的結(jié)構(gòu) ,同時(shí)具有較小的控制負(fù)荷 ,有利于它的擴(kuò)展性。 NICE 的數(shù)據(jù)拓?fù)潆[含在它的控制拓?fù)渲?,因而還可以支持不同源的數(shù)據(jù)分發(fā)樹(shù) 。并且由于它的分層 結(jié)構(gòu) ,進(jìn)行錯(cuò)誤檢測(cè)較為迅速。 NICE 協(xié)議把組播組成員安排成層次型的拓?fù)浣Y(jié)構(gòu) ,由于總有新成員加入或舊成員退出 ,協(xié)議的基本功能就是維護(hù)這一拓?fù)浣Y(jié)構(gòu) . 拓?fù)浣Y(jié)構(gòu)隱 含了組播數(shù)據(jù)的轉(zhuǎn)發(fā)路徑 , 而且它也是確 保 NICE 協(xié)議具有良好可擴(kuò)展性的關(guān)鍵因素 。 NICE 通過(guò)把組成員分配到不同的層次結(jié)構(gòu)來(lái)創(chuàng)建層次型拓?fù)浣Y(jié)構(gòu) 。 從最低層開(kāi)始順序編號(hào) ， 最低層標(biāo)號(hào)為 0 ， 用 Layer 0 表示 ， 依次類推 。 每個(gè)層次的節(jié)點(diǎn)都被分成多個(gè)節(jié)點(diǎn)集群 ,通常物理位置較近的節(jié)點(diǎn)位于同一個(gè)集群中 。 每個(gè)集群有一個(gè)領(lǐng)導(dǎo)節(jié)點(diǎn) ， 協(xié)議依據(jù)集群的拓?fù)浣Y(jié)構(gòu)選擇中心的節(jié)點(diǎn)作為領(lǐng)導(dǎo)節(jié)點(diǎn) ,即領(lǐng)導(dǎo)節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離之和在這個(gè)集群的所有節(jié)點(diǎn)中最小 . 集群領(lǐng)導(dǎo)的選擇對(duì)新節(jié)點(diǎn)加入時(shí)經(jīng)過(guò)很少的查詢次數(shù)就可以在層次結(jié)構(gòu)中找到合適的位置非 常重要 . 協(xié)議按照下面的規(guī)則將成員分配到各層次中 ： 所有成員都屬于最低層次 Layer 0 ,然后使用集群協(xié)議把Layer 0 層的成員分成多個(gè)集群并選擇出每個(gè)集群的領(lǐng)導(dǎo)節(jié)點(diǎn) ,所有集群的領(lǐng)導(dǎo)節(jié)點(diǎn)便構(gòu)成Layer 1 層的成員 ,依次類推 .如圖所示： 圖 層次結(jié)構(gòu)示意圖 Layer 0 的集群 是 [A,B,C,D][E,F,G,H][J,K,L,M], C,F,M 分別為這 三 個(gè) 集群 的中心，由 它 們組成了 Layer 1， Layer 1 只包含一個(gè) 集群 [C,F,M],而 F 又是這個(gè) 集群 的中心，出現(xiàn)在了 Layer 2 層，以 此 類推，最高則只有一個(gè)成員。歸納以上，可以用以下幾條性質(zhì)來(lái)描述： 1) 一個(gè)數(shù)據(jù)成員在每一層只能屬于一個(gè)集群 。 2) 如果某個(gè)成員出現(xiàn)在了 Layer i 層，那么它也一定會(huì)出現(xiàn)在 Layer i1,Layer i2…… Layer 0 層，實(shí)際上它也是這些層所在 集群 的中心點(diǎn)。 3) 如果某成員沒(méi)有出現(xiàn)在 Layer i 層，那么它也不會(huì)出現(xiàn)在 Layer j 層其中 ji 4) 每個(gè)集群 的大小都限制在（ k,3k1） ,k 為常數(shù)。其領(lǐng)導(dǎo)節(jié)點(diǎn) 正 是集群 在圖論中的中心點(diǎn)。 5) 整個(gè)層次結(jié)構(gòu)最多有 Mklog 層，且最高層 只有一個(gè)成員 在這個(gè)控制拓?fù)渲校總€(gè)集群 中的每個(gè)成員都保留著其所屬 集群 中的其它成員的狀態(tài)信息，并且互相間周期性地交換這些狀態(tài)信息，來(lái)確保所有成員能夠快速地對(duì)成員變化作出反應(yīng)，并能夠?qū)σ恍┩負(fù)浣Y(jié)構(gòu)的破壞進(jìn)行快速地修復(fù)。 當(dāng)一個(gè)新的成員加入到這個(gè)組中時(shí)，它將會(huì)被最終分配到 Layer 0 層 中離它最近的 集群中去。以圖為例，假設(shè) 有一個(gè)節(jié)點(diǎn) RP 了解所有成員的信息， 新成員 H 要加入到組播組中，首先， H 詢問(wèn) RP,RP 返回最高層的成員的信息 C0，然后 H 去查詢最高層的成員 C0，得到它下一層的 集群 的所有成員（ B0， B1， B2）的 信息，找出距離它最近的成員，設(shè)為 B2，然后查詢 B2 得到其下一層 集群 的所有成員信息， ??， A3 將最終找到 Layer 0 層中離它最近的集群 。當(dāng)一個(gè)節(jié)點(diǎn) A 要離開(kāi)組播組時(shí) ,它向與它建立聯(lián)系的所有集群發(fā)送移除消息 . 這是理想的離開(kāi)方式 ,但是 ,如果 A 失效了 ,與 A 建立聯(lián)系的所有的集群成員將在指定周期內(nèi)不能收到來(lái)自 A更新消息 ,從而認(rèn)為 A 離開(kāi)了 . 如果 A 節(jié)點(diǎn)是一個(gè)集