應(yīng)用層網(wǎng)絡(luò)Application-layerOverlayNetworks覆蓋網(wǎng)絡(luò)（OverlayNetwork）網(wǎng)絡(luò)：一群互連的、可以相互通信的計(jì)算機(jī)，定義了主機(jī)間通信所使用的編址、路由及服務(wù)模型。覆蓋網(wǎng)絡(luò)：建立在一個(gè)或多個(gè)已有網(wǎng)絡(luò)之上的邏輯網(wǎng)絡(luò)；改變底層網(wǎng)絡(luò)的一個(gè)或幾個(gè)特性，以實(shí)現(xiàn)底層網(wǎng)絡(luò)所不能提供的某種網(wǎng)絡(luò)服務(wù)。替代覆蓋網(wǎng)絡(luò)的方案：修改已有網(wǎng)絡(luò)因特網(wǎng)是一個(gè)覆蓋網(wǎng)絡(luò)因特網(wǎng)是建立在眾多物理網(wǎng)絡(luò)及電信線(xiàn)路上的邏輯網(wǎng)絡(luò)增加了一個(gè)在網(wǎng)間尋址及路由的IP層實(shí)現(xiàn)數(shù)據(jù)包跨物理網(wǎng)絡(luò)的傳輸覆蓋網(wǎng)絡(luò)的應(yīng)用路由（如路由覆蓋網(wǎng)絡(luò)）尋址（如對(duì)等網(wǎng)絡(luò)）安全（如VPN）多播（如MBone）移動(dòng)（如移動(dòng)IP）……覆蓋網(wǎng)絡(luò)的優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：一般不需要部署新的設(shè)備，不修改或很少修改已有的軟件/協(xié)議（但需要在已有軟件上部署新的軟件）。不需要在每一個(gè)節(jié)點(diǎn)上都部署新軟件。缺點(diǎn)：協(xié)議棧中增加了一個(gè)層次，增加了包頭及包處理開(kāi)銷(xiāo)節(jié)點(diǎn)的負(fù)擔(dān)加重了擴(kuò)放性問(wèn)題應(yīng)用層網(wǎng)絡(luò)應(yīng)用層網(wǎng)絡(luò)是在因特網(wǎng)上構(gòu)建的一個(gè)完全位于應(yīng)用層的網(wǎng)絡(luò)系統(tǒng)。應(yīng)用層網(wǎng)絡(luò)由分布在因特網(wǎng)上的一組主機(jī)組成：為一個(gè)或多個(gè)應(yīng)用程序提供下層基礎(chǔ)設(shè)施（網(wǎng)絡(luò)服務(wù)）采用與目前因特網(wǎng)不同的方法轉(zhuǎn)發(fā)和處理應(yīng)用程序的數(shù)據(jù)由第三方運(yùn)營(yíng)和管理，不是當(dāng)前因特網(wǎng)體系結(jié)構(gòu)的一部分。應(yīng)用層網(wǎng)絡(luò)實(shí)際上是基于因特網(wǎng)的大規(guī)模分布式應(yīng)用，因借助網(wǎng)絡(luò)層的一些技術(shù)來(lái)進(jìn)行成員之間的尋址和路由而具有了網(wǎng)絡(luò)層的某些特征。典型的應(yīng)用層網(wǎng)絡(luò)系統(tǒng)路由覆蓋網(wǎng)絡(luò)應(yīng)用層組播內(nèi)容分發(fā)網(wǎng)絡(luò)P2P系統(tǒng)1路由覆蓋網(wǎng)絡(luò)因特網(wǎng)路由策略?xún)H反映ISP對(duì)開(kāi)銷(xiāo)和運(yùn)行效率的考慮，端用戶(hù)和應(yīng)用程序無(wú)法參與。對(duì)于有些應(yīng)用來(lái)說(shuō)，因特網(wǎng)路由協(xié)議（OSPF/RIP、BGP）所選的路由不能滿(mǎn)足其要求。路由覆蓋網(wǎng)絡(luò)的目的是為上層應(yīng)用提供更好的路由服務(wù)，滿(mǎn)足其特殊的應(yīng)用需求。1.1彈性覆蓋網(wǎng)絡(luò)

ResilientOverlayNetworks（RON）RON是為解決BGP路由失效恢復(fù)慢的問(wèn)題而提出的，其設(shè)計(jì)目標(biāo)為：快速檢測(cè)和恢復(fù)路由失效20秒內(nèi)檢測(cè)到路由失效（停運(yùn)或性能下降）并恢復(fù)緊密集成路由選擇與應(yīng)用允許應(yīng)用定義路由失效和對(duì)失效的響應(yīng)允許應(yīng)用選擇適合自己的路徑度量來(lái)選擇路徑靈活的策略路由允許針對(duì)單個(gè)用戶(hù)或主機(jī)定義路由策略

RON概述RON是建立在已有因特網(wǎng)路由結(jié)構(gòu)上的一個(gè)應(yīng)用層覆蓋網(wǎng)絡(luò)。RON節(jié)點(diǎn)監(jiān)視在它們之間的因特網(wǎng)路徑的質(zhì)量，使用這些信息決定直接使用因特網(wǎng)的路由結(jié)構(gòu)，還是將數(shù)據(jù)包路由到其它RON節(jié)點(diǎn)，以?xún)?yōu)化應(yīng)用特定的路由度量。RON體系結(jié)構(gòu)模型RON客戶(hù)通過(guò)管道（conduit）與RON節(jié)點(diǎn)交互Probes負(fù)責(zé)探測(cè)虛鏈接狀態(tài)Router實(shí)現(xiàn)路由協(xié)議Forwarder提供分組轉(zhuǎn)發(fā)功能性能數(shù)據(jù)庫(kù)保存虛鏈接狀態(tài)信息（延遲、分組丟失率、鏈路吞吐量）RON節(jié)點(diǎn)RON節(jié)點(diǎn)是運(yùn)行了RON軟件的主機(jī)，實(shí)現(xiàn)和路由器類(lèi)似的功能。任意兩個(gè)RON節(jié)點(diǎn)之間維護(hù)一條由下層因特網(wǎng)鏈路構(gòu)成的路徑（虛鏈接）。每個(gè)節(jié)點(diǎn)及時(shí)探測(cè)到其余節(jié)點(diǎn)的虛鏈接狀態(tài)，保存在本地的性能數(shù)據(jù)庫(kù)中。RON的設(shè)計(jì)目標(biāo)是為一組RON客戶(hù)（使用RON轉(zhuǎn)發(fā)數(shù)據(jù)的應(yīng)用程序）提供更可靠的IP路由機(jī)制。RON工作過(guò)程第一個(gè)RON節(jié)點(diǎn)（入節(jié)點(diǎn)）對(duì)分組進(jìn)行分類(lèi)，決定分組要使用的路徑類(lèi)型（低延遲或高吞吐率等），為其選擇一條路由。若下一跳為一個(gè)RON節(jié)點(diǎn)，入節(jié)點(diǎn)為分組封裝一個(gè)RON報(bào)頭（包含一個(gè)流標(biāo)簽），發(fā)送到下一個(gè)RON節(jié)點(diǎn)。入節(jié)點(diǎn)對(duì)后續(xù)到達(dá)的屬于同一個(gè)客戶(hù)的分組標(biāo)上相同的流標(biāo)簽，直接查找流緩存表轉(zhuǎn)發(fā)。后續(xù)RON節(jié)點(diǎn)根據(jù)目的地址和流標(biāo)簽決定下一跳（不再進(jìn)行分類(lèi)）。最后一個(gè)RON節(jié)點(diǎn)（出節(jié)點(diǎn)）將分組交給RON客戶(hù)。RON路由的特點(diǎn)支持不同的路由策略：使用不同的鏈路度量參數(shù)維護(hù)多條路徑根據(jù)RON客戶(hù)程序的需要選擇最合適的路徑RON路由的工作要點(diǎn)路徑評(píng)估：節(jié)點(diǎn)使用停運(yùn)檢測(cè)（outagedetection）算法，主動(dòng)探測(cè)到其它RON節(jié)點(diǎn)之間的虛鏈路是否工作。針對(duì)每一種路徑度量（延遲、丟包率、吞吐率），給出表明路徑有多“好”的數(shù)值。鏈路狀態(tài)傳播：節(jié)點(diǎn)周期性地從本地性能數(shù)據(jù)庫(kù)中取出到其它節(jié)點(diǎn)的各種路徑度量的匯總信息，通過(guò)RON本身的網(wǎng)絡(luò)發(fā)送。路由表構(gòu)成針對(duì)每一種路由策略計(jì)算一組路由表，每一個(gè)路由表針對(duì)一種路徑度量計(jì)算得到。路由表的層次結(jié)構(gòu)：每個(gè)策略標(biāo)簽指向一個(gè)路由偏好表。每個(gè)路由偏好對(duì)應(yīng)一種路徑度量的路由表。RON轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)器檢查每個(gè)到來(lái)分組的RON報(bào)頭，確定要發(fā)給本地客戶(hù)還是一個(gè)遠(yuǎn)程節(jié)點(diǎn)：如果去往本地客戶(hù)，利用RON報(bào)頭中的packettype將數(shù)據(jù)包交給對(duì)應(yīng)的RON客戶(hù)。如果flowID匹配流緩存表中的一個(gè)表項(xiàng)，使用表項(xiàng)中的路由信息。如果flowID不匹配流緩存表中的任何表項(xiàng)，利用RON報(bào)頭查找路由表。RON報(bào)頭結(jié)構(gòu)路由表查找過(guò)程路由表查找分三步完成：基于策略類(lèi)型查找基于路由偏好查找基于目的地址查找1.2服務(wù)覆蓋網(wǎng)絡(luò)

ServiceOverlayNetworks（SON）每個(gè)ISP只關(guān)心自己網(wǎng)絡(luò)的性能，并只對(duì)自己的用戶(hù)提供服務(wù)保證。BGP只能找到一條可達(dá)的路由，無(wú)法保證端-端應(yīng)用性能。SON是為了在因特網(wǎng)上提供端-端服務(wù)質(zhì)量（QualityofService，QoS）而提出的，以方便創(chuàng)建和部署QoS敏感的增值業(yè)務(wù)。SON的實(shí)現(xiàn)基礎(chǔ)SON服務(wù)商通過(guò)雙邊服務(wù)協(xié)議（ServiceLevelAgreement，SLA）從各個(gè)ISP購(gòu)買(mǎi)具有一定QoS保證的帶寬，在已有因特網(wǎng)上構(gòu)造一個(gè)邏輯的端-端服務(wù)投送網(wǎng)絡(luò)。用戶(hù)通過(guò)業(yè)務(wù)合同，直接向SON服務(wù)商付費(fèi)來(lái)使用SON提供的增值服務(wù)。SON體系結(jié)構(gòu)SON由服務(wù)網(wǎng)關(guān)連接而成兩個(gè)服務(wù)網(wǎng)關(guān)之間的邏輯連接由底層ISP提供，帶寬和服務(wù)質(zhì)量由雙邊SLA保證。SON的優(yōu)點(diǎn)引入一個(gè)新的流量聚合層次（服務(wù)聚合）：ISP按流量所屬的SON進(jìn)行流量聚合。解除了應(yīng)用服務(wù)與網(wǎng)絡(luò)服務(wù)的耦合：ISP根據(jù)SLA設(shè)置數(shù)據(jù)傳輸服務(wù)（粗粒度）。SON采用與服務(wù)相關(guān)的帶寬管理、流量工程和QoS保證機(jī)制，確保服務(wù)的端-端服務(wù)質(zhì)量（細(xì)粒度）。減小了管理和控制網(wǎng)絡(luò)服務(wù)的復(fù)雜性允許靈活地創(chuàng)建和部署新的增值服務(wù)1.3面向服務(wù)的因特網(wǎng)

ServiceOrientedInternet（SOI）

覆蓋網(wǎng)絡(luò)的缺點(diǎn)：由于完全不考慮網(wǎng)絡(luò)層，一定程度的低效率是不可避免的。有些覆蓋網(wǎng)絡(luò)提供的服務(wù)需要底層網(wǎng)絡(luò)的支持才能發(fā)揮作用。有些功能在多個(gè)覆蓋網(wǎng)中重復(fù)實(shí)現(xiàn)。服務(wù)覆蓋網(wǎng)下面需要一個(gè)底層基礎(chǔ)架構(gòu)，解決覆蓋網(wǎng)的低效問(wèn)題，并支持新的應(yīng)用需求。SOI概述SOI在邏輯上分離數(shù)據(jù)傳輸網(wǎng)絡(luò)和服務(wù)覆蓋網(wǎng)絡(luò)：數(shù)據(jù)傳輸網(wǎng)絡(luò)：大致對(duì)應(yīng)當(dāng)前的自治系統(tǒng)，為服務(wù)覆蓋網(wǎng)提供比特管道服務(wù)。服務(wù)覆蓋網(wǎng)絡(luò)：由服務(wù)提供商運(yùn)營(yíng)，向訂戶(hù)（服務(wù)訂購(gòu)者）提供特殊的增值服務(wù)。服務(wù)覆蓋網(wǎng)絡(luò)被抽象成服務(wù)云，在多個(gè)地方與數(shù)據(jù)傳輸網(wǎng)絡(luò)接口。用戶(hù)請(qǐng)求在數(shù)據(jù)網(wǎng)絡(luò)上被路由到某個(gè)服務(wù)云的最近（或最合適）入口，由服務(wù)云中的某個(gè)主機(jī)服務(wù)。SOI體系結(jié)構(gòu)SOI概述（續(xù)）數(shù)據(jù)網(wǎng)絡(luò)與服務(wù)網(wǎng)絡(luò)邏輯分離的好處：允許這兩種網(wǎng)絡(luò)獨(dú)立進(jìn)化，在支持已有服務(wù)的同時(shí)方便未來(lái)因特網(wǎng)服務(wù)的靈活部署。實(shí)現(xiàn)邏輯獨(dú)立性的機(jī)制：徹底分離數(shù)據(jù)網(wǎng)絡(luò)與服務(wù)網(wǎng)絡(luò)的編址、路由和轉(zhuǎn)發(fā)機(jī)制每個(gè)服務(wù)云可以獨(dú)立實(shí)現(xiàn)自己的編址、路由和轉(zhuǎn)發(fā)機(jī)制SOI的抽象SOI是建立在已有IP網(wǎng)絡(luò)之上、為靈活部署新的因特網(wǎng)服務(wù)而提供的一個(gè)公共平臺(tái)。SOI架構(gòu)基于三個(gè)重要的抽象：服務(wù)云面向服務(wù)的編址方案（服務(wù)云，云中的對(duì)象）服務(wù)層（服務(wù)網(wǎng)關(guān)，服務(wù)存在點(diǎn)）（1）服務(wù)云服務(wù)云是一群部署在因特網(wǎng)上、相互協(xié)作向用戶(hù)提供應(yīng)用服務(wù)的服務(wù)實(shí)體（如服務(wù)器、代理、緩存、內(nèi)容交換機(jī)等）。服務(wù)云是一個(gè)虛擬的服務(wù)覆蓋網(wǎng)絡(luò)，依靠下層網(wǎng)絡(luò)域在因特網(wǎng)范圍傳輸數(shù)據(jù)。服務(wù)云和因特網(wǎng)的接口稱(chēng)為服務(wù)存在點(diǎn)，數(shù)據(jù)對(duì)象進(jìn)出服務(wù)云只能通過(guò)服務(wù)存在點(diǎn)。（2）面向服務(wù)的編址方案SOI的編址方案提供服務(wù)云及服務(wù)云中對(duì)象的位置無(wú)關(guān)標(biāo)識(shí)：每個(gè)服務(wù)云被分配一個(gè)固定長(zhǎng)度（32位）的ID（稱(chēng)sid），由一個(gè)中央權(quán)威機(jī)構(gòu)管理。服務(wù)云中的對(duì)象用一個(gè)對(duì)象ID（稱(chēng)oid）標(biāo)識(shí)，其語(yǔ)法和語(yǔ)義由各個(gè)服務(wù)云定義，只在服務(wù)云內(nèi)部使用。命名與名字解析服務(wù)云的命名與解析：每個(gè)服務(wù)云大致對(duì)應(yīng)了目前具有兩層或三層域名的一個(gè)機(jī)構(gòu)（如），機(jī)構(gòu)的域名就作為服務(wù)名。可以重用DNS或建一個(gè)類(lèi)似的名字解析系統(tǒng)，將服務(wù)名解析為sid。對(duì)象的命名與解析：服務(wù)云根據(jù)自己的商業(yè)需要定義對(duì)象的命名和編址系統(tǒng)。服務(wù)云提供對(duì)象解析的功能。將兩級(jí)地址的解析分開(kāi)，增加了靈活性和安全性。（3）服務(wù)層SOI架構(gòu)的基礎(chǔ)是位于IP層之上的一個(gè)服務(wù)層，包含兩個(gè)網(wǎng)絡(luò)單元：服務(wù)網(wǎng)關(guān)：可看成是下層網(wǎng)絡(luò)域的擴(kuò)展，通常部署在網(wǎng)絡(luò)域邊緣，負(fù)責(zé)穿過(guò)網(wǎng)絡(luò)域的路由和服務(wù)交付。服務(wù)存在點(diǎn)：服務(wù)云與網(wǎng)絡(luò)域接口的地方，邏輯上是服務(wù)云的一部分，負(fù)責(zé)在服務(wù)云內(nèi)部交付對(duì)象。進(jìn)出服務(wù)云的數(shù)據(jù)都要經(jīng)過(guò)服務(wù)網(wǎng)關(guān)，服務(wù)網(wǎng)關(guān)提供服務(wù)區(qū)分、識(shí)別和跟蹤服務(wù)云流量的功能。服務(wù)層在協(xié)議棧中的位置服務(wù)層協(xié)議數(shù)據(jù)單元（服務(wù)對(duì)象）服務(wù)對(duì)象頭部分為sid部分和oid部分服務(wù)修正符由服務(wù)云定義，對(duì)服務(wù)對(duì)象的轉(zhuǎn)發(fā)有影響。服務(wù)網(wǎng)關(guān)（ServiceGateway）數(shù)據(jù)面功能：根據(jù)目的sid（或目的sid+源sid）及相關(guān)的服務(wù)修正符，將服務(wù)對(duì)象轉(zhuǎn)發(fā)到去往目的服務(wù)云的下一跳（相鄰的S-POP或另一個(gè)SG）。控制面功能：運(yùn)行服務(wù)網(wǎng)關(guān)路由協(xié)議，建立服務(wù)路由表。服務(wù)路由表包含目的sid（及相關(guān)的服務(wù)修正符）到下一跳SG/S-POP（用IP地址表示）的映射。服務(wù)存在點(diǎn)（S-POP）服務(wù)存在點(diǎn)有兩個(gè)主要功能：與服務(wù)網(wǎng)關(guān)合作，為它所代理的服務(wù)云路由和轉(zhuǎn)發(fā)服務(wù)對(duì)象（發(fā)往服務(wù)云外部）。和服務(wù)云中的其它S-POP合作，在服務(wù)云內(nèi)部路由和轉(zhuǎn)發(fā)服務(wù)對(duì)象。（服務(wù)云內(nèi)部機(jī)制）為實(shí)現(xiàn)第一個(gè)功能：控制面：參與服務(wù)網(wǎng)關(guān)路由協(xié)議，建立（部分的）服務(wù)路由表，表中包含從sid空間到相鄰S(chǎng)G的映射。數(shù)據(jù)面：利用服務(wù)路由表，將服務(wù)對(duì)象轉(zhuǎn)發(fā)到服務(wù)云外。服務(wù)網(wǎng)關(guān)路由協(xié)議服務(wù)網(wǎng)關(guān)路由協(xié)議主要負(fù)責(zé)建立服務(wù)路由表，包括兩個(gè)部分：S-POP注冊(cè)和公告：S-POP向本地服務(wù)網(wǎng)關(guān)注冊(cè)，通告其存在、所代表的服務(wù)云sid、能夠處理的流量類(lèi)型（一組服務(wù)修正符）。傳播服務(wù)可達(dá)性：從鄰居服務(wù)網(wǎng)關(guān)學(xué)習(xí)路徑和向它們發(fā)布路徑（類(lèi)似BGP）。參考文獻(xiàn)ResilientOverlayNetworks.SOSP2001.ServiceOverlayNetworks:SLAs,QoSandBandwidthProvisioning.ICNP’02.ServiceOrientedInternet.2應(yīng)用層組播IP組播體系結(jié)構(gòu)：路由器采用分布式算法構(gòu)造一棵數(shù)據(jù)轉(zhuǎn)發(fā)樹(shù)；組播分組沿轉(zhuǎn)發(fā)樹(shù)轉(zhuǎn)發(fā)時(shí)，在樹(shù)的分支節(jié)點(diǎn)處由路由器進(jìn)行復(fù)制。IP組播協(xié)議：MOSPF、DVMRP等。IP多播骨干網(wǎng)：MBoneIP組播是實(shí)現(xiàn)組播轉(zhuǎn)發(fā)的最有效方法，可使全網(wǎng)范圍的分組復(fù)制數(shù)量最少。IP組播的缺點(diǎn)路由器必須為每個(gè)組播組單獨(dú)保存狀態(tài)，路由表和轉(zhuǎn)發(fā)表也需要為每個(gè)組播組維護(hù)一個(gè)地址項(xiàng)（組播地址不能聚合），擴(kuò)展性很差。要求所有路由器支持組播功能，給IP組播的推廣使用帶來(lái)很大困難。試圖用一種統(tǒng)一的組播模型來(lái)適應(yīng)所有的應(yīng)用，給組播算法的設(shè)計(jì)造成很大困難。組播組的管理開(kāi)銷(xiāo)大。在IP組播中實(shí)現(xiàn)可靠性和擁塞控制非常困難。在經(jīng)濟(jì)方面，尚沒(méi)有針對(duì)組播的流量計(jì)費(fèi)機(jī)制。應(yīng)用層組播在應(yīng)用層上，依靠端系統(tǒng)之間的單播實(shí)現(xiàn)組播。優(yōu)點(diǎn)：不需要改變現(xiàn)有路由器，能夠很快進(jìn)入應(yīng)用。單播技術(shù)較成熟，基于單播實(shí)現(xiàn)的應(yīng)用層組播易于實(shí)現(xiàn)差錯(cuò)控制、流量控制、擁塞控制等。缺點(diǎn)：延遲較大：應(yīng)用層組播不考慮網(wǎng)絡(luò)本身的拓?fù)浣Y(jié)構(gòu)。效率不如IP組播：應(yīng)用層組播會(huì)產(chǎn)生較多數(shù)據(jù)冗余。

應(yīng)用層組播研究如何構(gòu)造并維護(hù)高效率的覆蓋網(wǎng)絡(luò)。應(yīng)用層組播的例子：OvercastOvercast網(wǎng)絡(luò)用于單源組播，由以下幾個(gè)部分組成：一個(gè)源服務(wù)器任意數(shù)目分布在因特網(wǎng)上的中間節(jié)點(diǎn)（有永久存儲(chǔ)的PC機(jī)）分布在因特網(wǎng)上的標(biāo)準(zhǔn)HTTP客戶(hù)（Web瀏覽器）分發(fā)樹(shù)建立協(xié)議：將中間節(jié)點(diǎn)組織成一棵以源為根的分發(fā)樹(shù)。多播組的命名Overcast借用HTTPURL表示多播組：hostname指出一個(gè)Overcast網(wǎng)絡(luò)的根，源相同的所有組共享一棵分發(fā)樹(shù)。Path指示該網(wǎng)絡(luò)中的一個(gè)多播組。標(biāo)準(zhǔn)的HTTP客戶(hù)都可以加入這些多播組。使用URL作為多播組的名字空間有以下好處：分層的名字空間解決了多播組地址空間缺乏的問(wèn)題。基于HTTP的應(yīng)用不加修改就能使用到多播。URL結(jié)構(gòu)豐富，表達(dá)能力強(qiáng)。Overcast的應(yīng)用：視頻分發(fā)系統(tǒng)系統(tǒng)由一個(gè)studio和在一些合適位置放置的appliance組成，appliance和studio協(xié)作組織成一棵分發(fā)樹(shù)。studio存儲(chǔ)內(nèi)容，并根據(jù)需要調(diào)度內(nèi)容到appliance上。內(nèi)容發(fā)布者生成一個(gè)web頁(yè)，發(fā)布內(nèi)容的鏈接。用戶(hù)點(diǎn)擊內(nèi)容的URL后，瀏覽器根據(jù)hostname將請(qǐng)求發(fā)送到studio。Studio根據(jù)path將請(qǐng)求發(fā)送到客戶(hù)附近的appliance。節(jié)點(diǎn)初始化節(jié)點(diǎn)初始化（節(jié)點(diǎn)配置和注冊(cè)）：確定節(jié)點(diǎn)進(jìn)行一般IP連接所需要的IP地址和網(wǎng)關(guān)地址（DHCP服務(wù)或手工配置）。向一個(gè)全局的、熟知的注冊(cè)機(jī)構(gòu)發(fā)送自己的序列號(hào)。注冊(cè)機(jī)構(gòu)提供給節(jié)點(diǎn)一個(gè)應(yīng)當(dāng)加入的Overcast網(wǎng)絡(luò)列表、一個(gè)可選的永久IP配置、應(yīng)當(dāng)服務(wù)的網(wǎng)絡(luò)區(qū)域、應(yīng)當(dāng)執(zhí)行的訪(fǎng)問(wèn)控制。建立分發(fā)樹(shù)Overcast建立轉(zhuǎn)發(fā)樹(shù)的原則是，最大化從根（源服務(wù)器）到所有中間結(jié)點(diǎn)的帶寬：將節(jié)點(diǎn)放置在盡可能遠(yuǎn)離根的地方，同時(shí)不犧牲到根的帶寬。得到一棵較深的分發(fā)樹(shù)，節(jié)點(diǎn)在分發(fā)樹(shù)上得到的帶寬不低于其直接從根獲取內(nèi)容得到的帶寬。分發(fā)樹(shù)的建立過(guò)程當(dāng)有一個(gè)新節(jié)點(diǎn)向根注冊(cè)時(shí)，啟動(dòng)分發(fā)樹(shù)建立過(guò)程：設(shè)根為“當(dāng)前節(jié)點(diǎn)”；新節(jié)點(diǎn)檢測(cè)直接到“當(dāng)前節(jié)點(diǎn)”的帶寬，以及經(jīng)過(guò)“當(dāng)前節(jié)點(diǎn)”的各個(gè)孩子節(jié)點(diǎn)到達(dá)“當(dāng)前節(jié)點(diǎn)”的帶寬；如果經(jīng)由某個(gè)孩子節(jié)點(diǎn)到“當(dāng)前節(jié)點(diǎn)”的帶寬和從它直接到達(dá)“當(dāng)前節(jié)點(diǎn)”的帶寬一樣高，該孩子節(jié)點(diǎn)成為“當(dāng)前節(jié)點(diǎn)”，繼續(xù)探測(cè)。如果有多個(gè)孩子節(jié)點(diǎn)滿(mǎn)足條件，距離新節(jié)點(diǎn)最近（跳數(shù)最少）的孩子節(jié)點(diǎn)成為“當(dāng)前節(jié)點(diǎn)”。如果沒(méi)有一個(gè)孩子節(jié)點(diǎn)滿(mǎn)足條件，“當(dāng)前節(jié)點(diǎn)”成為父節(jié)點(diǎn)，搜索過(guò)程結(jié)束。分發(fā)樹(shù)的自適應(yīng)調(diào)整節(jié)點(diǎn)周期性地重新評(píng)估它在樹(shù)中的位置：如果到某個(gè)兄弟節(jié)點(diǎn)的帶寬不低于到父節(jié)點(diǎn)的帶寬，將自己置于該兄弟節(jié)點(diǎn)之下。如果直接到祖父節(jié)點(diǎn)的帶寬大于到父節(jié)點(diǎn)的帶寬，將自己置為當(dāng)前父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。Overcast網(wǎng)絡(luò)容忍非根節(jié)點(diǎn)的失效：當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)父節(jié)點(diǎn)不可達(dá)時(shí)，將自己連接到祖父節(jié)點(diǎn)下。如果祖父節(jié)點(diǎn)不可達(dá)，節(jié)點(diǎn)繼續(xù)沿系譜往上移，直到找到一個(gè)當(dāng)前活躍的節(jié)點(diǎn)。網(wǎng)絡(luò)維護(hù)每個(gè)節(jié)點(diǎn)維護(hù)一張表，記錄在樹(shù)中低于自己的節(jié)點(diǎn)的信息，根節(jié)點(diǎn)的信息表包含樹(shù)中所有節(jié)點(diǎn)的最新信息。每個(gè)節(jié)點(diǎn)周期性地向父節(jié)點(diǎn)報(bào)告自己的存在：如果一個(gè)孩子節(jié)點(diǎn)在預(yù)定的時(shí)間間隔內(nèi)沒(méi)有報(bào)告，父節(jié)點(diǎn)在表中記錄該孩子及其子孫節(jié)點(diǎn)“死了”。節(jié)點(diǎn)還會(huì)報(bào)告其觀察到或被告知的信息，如錯(cuò)過(guò)報(bào)告時(shí)間的孩子和新增的孩子等。

加入多播組web客戶(hù)發(fā)送一個(gè)包含該多播組URL的HTTPGET請(qǐng)求，URL的hostname指出分發(fā)樹(shù)的根，path指出多播組。根節(jié)點(diǎn)使用path、用戶(hù)位置以及當(dāng)前狀態(tài)數(shù)據(jù)庫(kù)決定將用戶(hù)從樹(shù)的哪個(gè)位置接入。用Overcast實(shí)現(xiàn)多播數(shù)據(jù)在父節(jié)點(diǎn)和子節(jié)點(diǎn)之間通過(guò)TCP傳輸：內(nèi)容可能會(huì)流水地通過(guò)樹(shù)上的幾代節(jié)點(diǎn)。一個(gè)大文件或一段長(zhǎng)時(shí)間的實(shí)時(shí)流可能會(huì)同時(shí)在幾十個(gè)不同的TCP流中傳輸。如果出現(xiàn)路徑失效：重建分發(fā)樹(shù)；節(jié)點(diǎn)檢查日志，重新啟動(dòng)未完成的傳輸。參考文獻(xiàn)Overcast:ReliableMulticastingwithanOverlayNetwork.OSDI2000.

3內(nèi)容分發(fā)網(wǎng)絡(luò)

ContentDeliveryNetworks（CDN）提高Web服務(wù)性能主要圍繞網(wǎng)絡(luò)傳輸和服務(wù)器兩個(gè)方面：提高單臺(tái)web服務(wù)器的性能：增加更多的內(nèi)存和磁盤(pán)空間，使用更高速的處理器（或多處理器），使用緩存來(lái)減少讀盤(pán)次數(shù)等。性能提高有限，響應(yīng)延遲受網(wǎng)絡(luò)擁塞影響大。建立服務(wù)器集群（serverfarm）：多個(gè)web服務(wù)器分擔(dān)對(duì)同一個(gè)web站點(diǎn)的訪(fǎng)問(wèn)請(qǐng)求。響應(yīng)延遲受網(wǎng)絡(luò)擁塞影響大。提高Web服務(wù)性能的方法（續(xù)）建立分級(jí)的web緩存機(jī)制：將用戶(hù)最近訪(fǎng)問(wèn)過(guò)的網(wǎng)頁(yè)保留在高速緩存中，使用一個(gè)代理（proxy）來(lái)管理緩存。瀏覽器配置為向代理請(qǐng)求網(wǎng)頁(yè)，若本地緩存沒(méi)有，向上一級(jí)代理或源服務(wù)器請(qǐng)求。提高Web服務(wù)性能的方法（續(xù)）建立內(nèi)容分發(fā)網(wǎng)絡(luò)：在因特網(wǎng)的不同地方設(shè)置鏡像服務(wù)器，將用戶(hù)請(qǐng)求重定向到最近的服務(wù)器。有助于減小網(wǎng)絡(luò)傳輸和服務(wù)器負(fù)載對(duì)請(qǐng)求響應(yīng)時(shí)間的影響。

CDN涉及的主體內(nèi)容提供商（customer）：提供內(nèi)容服務(wù)的機(jī)構(gòu)或公司，其內(nèi)容保存在源服務(wù)器（originserver）。CDN提供商：擁有CDN架構(gòu)，為內(nèi)容提供商提供快速可靠的內(nèi)容遞送服務(wù)。端用戶(hù)（client）：從內(nèi)容提供商的網(wǎng)站上訪(fǎng)問(wèn)內(nèi)容的實(shí)體。內(nèi)容分發(fā)環(huán)境CDN的內(nèi)容CDN一般保存靜態(tài)內(nèi)容：如圖像、視頻、媒體剪輯、廣告、動(dòng)態(tài)網(wǎng)頁(yè)中的嵌入式對(duì)象等。在CDN的上下文中，內(nèi)容泛指任何數(shù)字形式的數(shù)據(jù)資源，主要包括兩大部分：經(jīng)過(guò)編碼的媒體。元數(shù)據(jù)：用來(lái)標(biāo)識(shí)、發(fā)現(xiàn)和管理媒體數(shù)據(jù)的內(nèi)容描述。CDN的客戶(hù)CDN的客戶(hù)一般是媒體和因特網(wǎng)廣告公司、數(shù)據(jù)中心、ISP、在線(xiàn)音樂(lè)零售商、移動(dòng)運(yùn)營(yíng)商、消費(fèi)電子生產(chǎn)商等。CDN客戶(hù)希望可靠而及時(shí)地在因特網(wǎng)上向端用戶(hù)發(fā)布和投送內(nèi)容。CDN提供商根據(jù)投送給端用戶(hù)的內(nèi)容（即流量）向內(nèi)容提供商收費(fèi)。CDN的體系結(jié)構(gòu)基礎(chǔ)結(jié)構(gòu)：提供基礎(chǔ)設(shè)施資源，由通過(guò)高速網(wǎng)絡(luò)連接的分布式計(jì)算資源和網(wǎng)絡(luò)基礎(chǔ)設(shè)施組成。通信和連接：提供核心的互連網(wǎng)協(xié)議、CDN特定的協(xié)議、認(rèn)證協(xié)議、安全通信協(xié)議SSL。CDN：CDN核心功能。端用戶(hù)：web用戶(hù)，在web瀏覽器上給出內(nèi)容提供商網(wǎng)站的URL連接到CDN。CDN提供的服務(wù)和功能內(nèi)容存儲(chǔ)和管理在代理服務(wù)器間分發(fā)內(nèi)容緩存管理靜態(tài)、動(dòng)態(tài)和流內(nèi)容投送備份和災(zāi)難恢復(fù)解決方案監(jiān)視、測(cè)量和報(bào)告性能內(nèi)容簡(jiǎn)介從以下三個(gè)方面介紹CDN：CDN組成內(nèi)容分發(fā)和管理請(qǐng)求路求參考文獻(xiàn)：

ATaxonomyandSurveyofContentDeliveryNetworks.Http:///reports/CDN-Taxonomy.pdf

3.1CDN的組成CDN的任務(wù)是結(jié)合網(wǎng)絡(luò)條件和緩存服務(wù)器負(fù)載等動(dòng)態(tài)信息，在多個(gè)反向代理（surrogate）之間重定向請(qǐng)求和平衡負(fù)載。在一個(gè)CDN中，通常使用一組反向代理來(lái)建立內(nèi)容分發(fā)設(shè)施，使用一些機(jī)制將用戶(hù)請(qǐng)求重定向到一個(gè)反向代理，各單元之間使用特定的協(xié)議進(jìn)行通信。Surrogate和ProxyProxy用于代理內(nèi)部網(wǎng)絡(luò)對(duì)因特網(wǎng)的連接請(qǐng)求。客戶(hù)機(jī)將本來(lái)要直接發(fā)送到外部服務(wù)器上的服務(wù)請(qǐng)求發(fā)送到代理服務(wù)器，由代理服務(wù)器中繼服務(wù)請(qǐng)求。Surrogate用于代理外部網(wǎng)絡(luò)上的主機(jī)訪(fǎng)問(wèn)內(nèi)部網(wǎng)絡(luò)，此時(shí)Surrogate對(duì)外表現(xiàn)為一個(gè)web服務(wù)器。反向代理可以增強(qiáng)web服務(wù)器的安全性，和作為后端服務(wù)器集群的負(fù)載均衡器。反向代理方式和普通代理方式?jīng)]有沖突，可以在防火墻設(shè)備中同時(shí)使用。

CDN的結(jié)構(gòu)特性3.1.1CDN的組織方式網(wǎng)絡(luò)方法：在路由器和交換機(jī)等網(wǎng)絡(luò)組件上安裝相關(guān)軟件，將內(nèi)容請(qǐng)求重定向到本地緩存或特定的內(nèi)容服務(wù)器。覆蓋方法：使用放置于網(wǎng)絡(luò)中多個(gè)地方的應(yīng)用特定服務(wù)器（反向代理，高速緩存服務(wù)器）處理特殊內(nèi)容（web內(nèi)容、流媒體等）的分發(fā)。除了提供基本的網(wǎng)絡(luò)連接和QoS保證外，核心網(wǎng)絡(luò)組件在內(nèi)容分發(fā)過(guò)程中不發(fā)揮積極作用。3.1.2CDN服務(wù)器源服務(wù)器（originserver）：存放資源的權(quán)威版本，由內(nèi)容提供商更新。復(fù)制服務(wù)器（replicaserver）：存放資源的拷貝，并被授權(quán)響應(yīng)用戶(hù)的請(qǐng)求。通過(guò)源服務(wù)器進(jìn)行內(nèi)容更新。CDN的復(fù)制服務(wù)器CDN的復(fù)制服務(wù)器可以作為媒體服務(wù)器、web服務(wù)器或高速緩存服務(wù)器：媒體服務(wù)器（mediaserver）：提供數(shù)字編碼的內(nèi)容，安裝有媒體服務(wù)器軟件，用音頻或視頻素材響應(yīng)用戶(hù)的請(qǐng)求。Web服務(wù)器：包含到流媒體的鏈接，以及CDN希望提供的其它基于web的內(nèi)容。高速緩存服務(wù)器（cacheserver）：在網(wǎng)絡(luò)邊緣復(fù)制內(nèi)容，以減少對(duì)源服務(wù)器的訪(fǎng)問(wèn)。流媒體應(yīng)用的實(shí)現(xiàn)音/視頻文件存儲(chǔ)在媒體服務(wù)器上，元文件存儲(chǔ)在Web服務(wù)器上。媒體播放器和媒體服務(wù)器之間通過(guò)RTP/UDP傳輸音/視頻流，使用RTSP進(jìn)行交互性操作。3.1.3CDN組件之間的關(guān)系CDN的各個(gè)組件通過(guò)相互協(xié)作來(lái)實(shí)現(xiàn)CDN內(nèi)部的內(nèi)容復(fù)制和高速緩存：復(fù)制：在不同的計(jì)算機(jī)系統(tǒng)上創(chuàng)建和維護(hù)內(nèi)容拷貝，典型地是將內(nèi)容從源服務(wù)器“推送”到復(fù)制服務(wù)器。（Push）緩存（caching）：將可緩存的響應(yīng)保存在本地，以便將來(lái)響應(yīng)相同的請(qǐng)求。（Pull）用戶(hù)-反向代理-源服務(wù)器內(nèi)容投遞的基本關(guān)系是在用戶(hù)、反向代理服務(wù)器和源服務(wù)器之間：用戶(hù)一般同反向代理服務(wù)器通信。反向代理服務(wù)器用本地緩存的內(nèi)容響應(yīng)用戶(hù)請(qǐng)求，或作為源服務(wù)器的網(wǎng)關(guān)。用戶(hù)-網(wǎng)元-高速緩存代理（cachingproxy）在網(wǎng)絡(luò)方法中，網(wǎng)元（路由器、交換機(jī)）上的控制邏輯將用戶(hù)請(qǐng)求轉(zhuǎn)發(fā)到相應(yīng)的高速緩存代理（代理陣列）。高速緩存代理-高速緩存代理根據(jù)高速緩存代理之間的通信方式，高速緩存代理可以組織成代理陣列或代理網(wǎng)：Proxyarray：緊耦合結(jié)構(gòu)，有一個(gè)權(quán)威代理作為主代理，與其它代理通信。Proxymesh：松耦合結(jié)構(gòu)，每個(gè)代理都和其它代理有聯(lián)系，構(gòu)成代理網(wǎng)。Proxymesh需要一個(gè)高速緩存服務(wù)器作為網(wǎng)關(guān)，轉(zhuǎn)發(fā)來(lái)自用戶(hù)本地緩存代理的請(qǐng)求。代理陣列和代理網(wǎng)3.1.4協(xié)議CDN中的通信協(xié)議分為兩類(lèi)：網(wǎng)元交互協(xié)議：用于將用戶(hù)請(qǐng)求重定向到一個(gè)合適的服務(wù)器，涉及路由器、內(nèi)容交換機(jī)/負(fù)載均衡器、服務(wù)器等實(shí)體。高速緩存交互協(xié)議：用于在分布式高速緩存中確定所請(qǐng)求的內(nèi)容在哪個(gè)高速緩存中。網(wǎng)元-服務(wù)器（NECP）運(yùn)行在服務(wù)器（源服務(wù)器、攔截代理）與其前端設(shè)備（內(nèi)容交換機(jī)、負(fù)責(zé)均衡路由器）之間的控制協(xié)議：服務(wù)器啟動(dòng)時(shí)，與網(wǎng)元的熟知端口建立TCP連接，在TCP連接上進(jìn)行雙向消息交換。網(wǎng)元通過(guò)消息交換了解服務(wù)器的能力、可用性、可以獲得哪些內(nèi)容等，作為重定向用戶(hù)請(qǐng)求的依據(jù)。重定向路由器-攔截代理（WCCP）運(yùn)行在重定向路由器和攔截代理之間，建立和維護(hù)用戶(hù)請(qǐng)求的透明重定向：若干攔截代理和若干重定向路由器組成一個(gè)服務(wù)組，指定一個(gè)代理（IP地址最小）作為首領(lǐng)，負(fù)責(zé)在代理群之間分配負(fù)載，并將負(fù)載分配方法在組內(nèi)傳播。通過(guò)該協(xié)議，路由器知道如何重定向用戶(hù)請(qǐng)求；攔截代理知道如何管理高速緩存中的內(nèi)容。防火墻安全會(huì)話(huà)轉(zhuǎn)換協(xié)議SOCKSSOCKS是為客戶(hù)-服務(wù)器應(yīng)用安全通過(guò)防火墻而提供的一個(gè)通用框架。當(dāng)內(nèi)網(wǎng)用戶(hù)想訪(fǎng)問(wèn)外網(wǎng)服務(wù)器時(shí)，首先與SOCKS代理服務(wù)器建立連接，進(jìn)行認(rèn)證。若認(rèn)證通過(guò)，SOCKS代理服務(wù)器與外網(wǎng)服務(wù)器建立連接，并中繼用戶(hù)請(qǐng)求；否則終止與用戶(hù)的連接。SOCKS代理服務(wù)器只是簡(jiǎn)單地傳遞包，而不關(guān)心是何種應(yīng)用協(xié)議，因此SOCKS是一種通用的服務(wù)，在概念上位于應(yīng)用層和傳輸層之間。InternetCacheProtocol（ICP）Cache被組織成層次結(jié)構(gòu)：用戶(hù)請(qǐng)求發(fā)送到本地緩存。若本地緩存沒(méi)有，本地緩存向同伴緩存廣播請(qǐng)求。若同伴均回復(fù)沒(méi)有或超時(shí)，本地緩存向父緩存請(qǐng)求。若父緩存沒(méi)有，父緩存或本地緩存向源服務(wù)器請(qǐng)求。ICP基于查詢(xún)/應(yīng)答實(shí)現(xiàn)，通信開(kāi)銷(xiāo)大，延遲大。CacheDigest每個(gè)節(jié)點(diǎn)保存其它節(jié)點(diǎn)中所緩存的內(nèi)容的摘要：本地緩存收到用戶(hù)請(qǐng)求后，檢查本地緩存的內(nèi)容和其它節(jié)點(diǎn)的緩存內(nèi)容摘要；若本地緩存有內(nèi)容，直接響應(yīng)用戶(hù)的請(qǐng)求；若有緩存內(nèi)容摘要，向相應(yīng)的緩存節(jié)點(diǎn)請(qǐng)求；若沒(méi)有緩存內(nèi)容摘要，向源服務(wù)器請(qǐng)求內(nèi)容。優(yōu)點(diǎn)：不需要發(fā)送查詢(xún)消息到其它緩存節(jié)點(diǎn)。缺點(diǎn)：存儲(chǔ)摘要的代價(jià)很高，節(jié)點(diǎn)之間需要更新摘要。

Cachearrayroutingprotocol（CARP）瀏覽器利用cache陣列成員表、一個(gè)查找函數(shù)和用戶(hù)請(qǐng)求的URL，就能確定最合適的cache服務(wù)器。Cache陣列成員表定義在一個(gè)可公開(kāi)獲取的文本文件中，文件中列出了每臺(tái)代理服務(wù)器的名字、IP地址和負(fù)載因子（管理員指定）。瀏覽器需要下載Cache陣列成員表和一個(gè)查找函數(shù)（JavaScript函數(shù)）。CARP（續(xù)）查找函數(shù)實(shí)現(xiàn)CARP算法：使用指定的哈希函數(shù)計(jì)算URL的散列值及每個(gè)成員名字的散列值，兩個(gè)值結(jié)合得到每個(gè)成員對(duì)該URL的一個(gè)分值。將該分值與成員的負(fù)載因子結(jié)合，得到每個(gè)成員對(duì)該URL的總分。總分最高的cache服務(wù)器選中。

優(yōu)點(diǎn)：沒(méi)有緩存冗余，緩存命中率高。緩存節(jié)點(diǎn)間不需要通信，沒(méi)有查詢(xún)和更新開(kāi)銷(xiāo)。3.1.5內(nèi)容/服務(wù)類(lèi)型CDN提供的內(nèi)容/服務(wù)有三類(lèi)：靜態(tài)內(nèi)容，流媒體，各種內(nèi)容服務(wù)。靜態(tài)內(nèi)容：HTML頁(yè)、圖片、文檔、軟件補(bǔ)丁、音/視頻文件等。更新頻率很低，易于緩存。所有CDN提供商都支持靜態(tài)內(nèi)容的投遞。流媒體流媒體包括：現(xiàn)場(chǎng)音/視頻：內(nèi)容從編碼器立即送到媒體服務(wù)器，然后送給媒體用戶(hù)。點(diǎn)播音/視頻：內(nèi)容預(yù)先被編碼，作為流媒體文件保存在媒體服務(wù)器中，用戶(hù)請(qǐng)求時(shí)投送。流媒體服務(wù)需要專(zhuān)門(mén)的流式服務(wù)器，使用特定軟件實(shí)現(xiàn)流媒體在IP網(wǎng)絡(luò)中的傳輸。投送流媒體內(nèi)容對(duì)于CDN是一個(gè)挑戰(zhàn)。內(nèi)容服務(wù)將CDN作為服務(wù)分發(fā)渠道，允許增值服務(wù)提供商在上面提供增值服務(wù)（內(nèi)容服務(wù)），如：目錄服務(wù)：將用戶(hù)的查詢(xún)請(qǐng)求定向到包含請(qǐng)求內(nèi)容的數(shù)據(jù)庫(kù)服務(wù)器，并將頻繁請(qǐng)求的查詢(xún)結(jié)果緩存在CDN的邊緣服務(wù)器上。網(wǎng)頁(yè)壓縮服務(wù)：提供對(duì)網(wǎng)頁(yè)的實(shí)時(shí)壓縮，并對(duì)源服務(wù)器和用戶(hù)透明。電子商務(wù)服務(wù)：比如在CDN的邊緣服務(wù)器上保存和維護(hù)購(gòu)物車(chē)、進(jìn)行在線(xiàn)交易等，減輕源站的壓力。3.2內(nèi)容分發(fā)和管理內(nèi)容分發(fā)：反向代理放置：確定反向代理服務(wù)器的放置位置及數(shù)量，最小化用戶(hù)訪(fǎng)問(wèn)延遲和網(wǎng)絡(luò)帶寬消耗。內(nèi)容選擇和投送：正確選擇要復(fù)制到CDN的內(nèi)容，減少用戶(hù)下載時(shí)間和服務(wù)器負(fù)載。內(nèi)容外包：如何將選擇的內(nèi)容復(fù)制到放置好的反向代理服務(wù)器？復(fù)制到哪一個(gè)反向代理服務(wù)器？?jī)?nèi)容管理：高速緩存組織：緩存技術(shù)、緩存更新、緩存策略。3.2.1反向代理服務(wù)器的放置目標(biāo)：確定反向代理服務(wù)器的個(gè)數(shù)和放置位置。問(wèn)題模型：給定一個(gè)圖G（V,E）和要放置的中心數(shù)量k，確定中心的位置，使得所有節(jié)點(diǎn)到最近中心的最大距離最小化。理論算法：計(jì)算復(fù)雜度大。啟發(fā)式算法：利用來(lái)自CDN的一些信息，如負(fù)載模式、網(wǎng)絡(luò)拓?fù)涞龋暂^低的計(jì)算代價(jià)獲得次優(yōu)解。啟發(fā)式算法（1）Greedyreplicaplacement：前提：知道網(wǎng)絡(luò)中所有用戶(hù)的位置，以及每一對(duì)節(jié)點(diǎn)間的距離。算法思想：從N個(gè)可能的站點(diǎn)中選擇訪(fǎng)問(wèn)代價(jià)最小的M個(gè)站點(diǎn)放置反向代理。過(guò)程：第一輪計(jì)算每個(gè)站點(diǎn)的代價(jià)，計(jì)算時(shí)假定所有用戶(hù)的訪(fǎng)問(wèn)都匯聚到該站點(diǎn)，代價(jià)最小的站點(diǎn)被選中。結(jié)合已選中的站點(diǎn)，第二輪搜索代價(jià)第二小的站點(diǎn)。依次類(lèi)推，直至M個(gè)站點(diǎn)選出來(lái)。啟發(fā)式算法（2）Topology-informedplacementstrategy：假設(shè)：有較大出度的節(jié)點(diǎn)可用較小的延遲到達(dá)更多的節(jié)點(diǎn)。算法基本思想：使用自治域一級(jí)的拓?fù)洌總€(gè)節(jié)點(diǎn)代表一個(gè)AS，每一條鏈路對(duì)應(yīng)一對(duì)BGP對(duì)等體。按節(jié)點(diǎn)出度的降序選擇M個(gè)節(jié)點(diǎn)放置反向代理。改進(jìn)的算法：用路由器一級(jí)的拓?fù)浯鍭S一級(jí)的拓?fù)洌c路由器相連的每個(gè)局域網(wǎng)都可以放置一個(gè)反向代理。啟發(fā)式算法（3）Hotspot算法：按照產(chǎn)生流量的大小對(duì)站點(diǎn)進(jìn)行排序；將M個(gè)反向代理放置在生成流量最大的M個(gè)站點(diǎn)上。確定反向代理服務(wù)器的數(shù)量單ISP方法：僅在CDN提供商的網(wǎng)絡(luò)邊緣放置反向代理服務(wù)器。放置策略：在ISP覆蓋的區(qū)域內(nèi)，每個(gè)大城市放置一個(gè)或兩個(gè)反向代理服務(wù)器。缺點(diǎn)：反向代理服務(wù)器可能離用戶(hù)很遠(yuǎn)。多ISP方法：在盡可能多的互聯(lián)網(wǎng)入網(wǎng)點(diǎn)（ISPPointsofPresence）上放置反向代理服務(wù)器。優(yōu)點(diǎn)：反向代理服務(wù)器位于請(qǐng)求用戶(hù)的ISP上。缺點(diǎn)：建設(shè)成本及復(fù)雜性高，服務(wù)器使用率低。

3.2.2內(nèi)容選擇和投送正確選擇要復(fù)制到CDN的內(nèi)容，以減少用戶(hù)下載時(shí)間和服務(wù)器負(fù)載。兩類(lèi)方法：全站點(diǎn)內(nèi)容選擇和投送：將源服務(wù)器上的全部對(duì)象外包給反向代理服務(wù)器。部分站點(diǎn)內(nèi)容選擇和投送：只將源服務(wù)器上的部分內(nèi)容復(fù)制到反向代理服務(wù)器。全站點(diǎn)內(nèi)容選擇和投送內(nèi)容提供商配置其DNS，令所有對(duì)其web站點(diǎn)的請(qǐng)求都由一個(gè)CDN服務(wù)器解析，這樣全部?jī)?nèi)容都由CDN投送。優(yōu)點(diǎn)：簡(jiǎn)單。缺點(diǎn)：不具有可行性（邊緣服務(wù)器不可能擁有足夠的存儲(chǔ)空間，更新也很難做到）。部分站點(diǎn)內(nèi)容選擇和投送反向代理服務(wù)器只投送內(nèi)置于網(wǎng)頁(yè)的對(duì)象（如圖片）。內(nèi)容提供商修改其內(nèi)容，將特定對(duì)象URL中的hostname改為CDN提供商權(quán)威域中的域名。HTML基礎(chǔ)網(wǎng)頁(yè)從源服務(wù)器獲取，內(nèi)嵌的對(duì)象從CDN反向代理服務(wù)器獲取。優(yōu)點(diǎn)：降低了對(duì)反向代理服務(wù)器的存儲(chǔ)容量需求；只投送靜態(tài)的或更新較慢的內(nèi)容，減輕更新壓力。部分站點(diǎn)方法（1）基于實(shí)證的（empirical-based）方法：管理員依據(jù)經(jīng)驗(yàn)選擇復(fù)制到反向代理服務(wù)器的內(nèi)容。缺點(diǎn)：選擇正確經(jīng)驗(yàn)的不確定性。基于流行的（popularity-based）方法：最流行的對(duì)象被復(fù)制到反向代理服務(wù)器。缺點(diǎn)：耗時(shí)（要對(duì)對(duì)象的流行程度進(jìn)行評(píng)估和排序）難以得到可靠的對(duì)象請(qǐng)求統(tǒng)計(jì)信息（流行性變化大）新內(nèi)容的統(tǒng)計(jì)信息得不到部分站點(diǎn)方法（2）基于對(duì)象的（object-based）方法：內(nèi)容以對(duì)象為單位復(fù)制到反向代理服務(wù)器。在滿(mǎn)足存儲(chǔ)容量的前提下，每復(fù)制一個(gè)對(duì)象到反向代理服務(wù)器都試圖最大化性能增益（貪婪算法）。優(yōu)點(diǎn)：可獲得最佳性能缺點(diǎn)：實(shí)現(xiàn)復(fù)雜度高部分站點(diǎn)方法（3）基于聚類(lèi)的（cluster-based）方法：web內(nèi)容依據(jù)相關(guān)性或訪(fǎng)問(wèn)頻度分組，并以?xún)?nèi)容聚類(lèi)為單位進(jìn)行復(fù)制。基于用戶(hù)會(huì)話(huà)的內(nèi)容聚類(lèi)：利用web日志文件，確定具有關(guān)聯(lián)內(nèi)容的網(wǎng)頁(yè)組。基于URL的內(nèi)容聚類(lèi)：依據(jù)web站點(diǎn)的拓?fù)鋪?lái)匯聚web內(nèi)容，從一個(gè)web站點(diǎn)中識(shí)別出最流行的對(duì)象，然后按URL之間的相關(guān)距離進(jìn)行聚類(lèi)。這類(lèi)方法可以減少用戶(hù)下載時(shí)間和服務(wù)器負(fù)載，但實(shí)施的復(fù)雜度高。3.2.3內(nèi)容外包（contentoutsourcing）如何將選擇的內(nèi)容復(fù)制到一組放置好的反向代理服務(wù)器上？cooperativepush-based（內(nèi)容預(yù)取）：內(nèi)容從源服務(wù)器推送到反向代理服務(wù)器，反向代理服務(wù)器通過(guò)相互協(xié)作來(lái)降低復(fù)制和更新代價(jià)。CDN維護(hù)內(nèi)容和反向代理之間的映射，用戶(hù)請(qǐng)求被定向到最近的反向代理服務(wù)器或源服務(wù)器。適合采用全局貪婪啟發(fā)式算法在合作的反向代理服務(wù)器之間進(jìn)行復(fù)制決策。該方法還處于實(shí)驗(yàn)階段，未被任何CDN提供商使用。基于“拉”的內(nèi)容外包方法Non-cooperativepull-based：用戶(hù)請(qǐng)求被定向到最近的反向代理服務(wù)器；如果緩存不命中，反向代理從源服務(wù)器取內(nèi)容。大多數(shù)流行的CDN提供商使用該方法。Cooperativepull-based：用戶(hù)請(qǐng)求被定向到最近的反向代理服務(wù)器；如果緩存不命中，反向代理使用一個(gè)分布式索引在附近找到所請(qǐng)求內(nèi)容的拷貝。外包內(nèi)容的最佳放置問(wèn)題：外包內(nèi)容復(fù)制到哪一個(gè)反向代理服務(wù)器最好？各種啟發(fā)式算法（略）：考慮負(fù)載均衡和/或下載延遲3.2.4緩存組織（cacheorganization）內(nèi)容管理主要由CDN的緩存組織方式?jīng)Q定：緩存技術(shù)：如何從分布式緩存中找到要請(qǐng)求的內(nèi)容？緩存更新：如何保證緩存內(nèi)容的一致性和新鮮性？（1）緩存技術(shù)（cachingtechniques）CDN中的內(nèi)容緩存分為簇內(nèi)緩存和簇間緩存簇內(nèi)緩存基于查詢(xún)的緩存方案：當(dāng)一個(gè)反向代理服務(wù)器發(fā)現(xiàn)cachemiss后，向簇內(nèi)的其它反向代理服務(wù)器廣播一個(gè)查詢(xún)。若所有的反向代理服務(wù)器都沒(méi)有該內(nèi)容，該反向代理向源服務(wù)器請(qǐng)求。缺點(diǎn)：查詢(xún)流量大（查詢(xún)洪泛），延遲長(zhǎng)（需要等待所有的反向代理服務(wù)器返回響應(yīng)）。簇內(nèi)緩存（續(xù)）基于摘要的緩存方案：每個(gè)反向代理服務(wù)器維護(hù)其它服務(wù)器中內(nèi)容的摘要，內(nèi)容更新的通知發(fā)送給所有的反向代理。反向代理服務(wù)器檢查保存于本地的內(nèi)容摘要后，決定將內(nèi)容請(qǐng)求路由到哪個(gè)反向代理。優(yōu)點(diǎn)：解決了查詢(xún)洪泛的問(wèn)題。缺點(diǎn)：存儲(chǔ)量大，更新流量大（頻繁發(fā)送更新通知）。簇內(nèi)緩存（續(xù)）基于目錄的緩存方案：摘要方法的集中式版本，一個(gè)集中的目錄服務(wù)器保存簇內(nèi)所有反向代理服務(wù)器上內(nèi)容的信息。每個(gè)反向代理只將內(nèi)容改變通知目錄服務(wù)器，并在本地cachemiss后查詢(xún)目錄服務(wù)器。缺點(diǎn)：目錄服務(wù)器接收來(lái)自所有反向代理的更新和查詢(xún)流量，是性能瓶頸和單故障點(diǎn)。簇內(nèi)緩存（續(xù)）基于哈希的緩存方案：所有反向代理服務(wù)器使用相同的哈希函數(shù)和一組反向代理IP地址，根據(jù)內(nèi)容的URL確定內(nèi)容存在哪個(gè)服務(wù)器（稱(chēng)為內(nèi)容的指定服務(wù)器）上。對(duì)內(nèi)容的請(qǐng)求全都定向到其指定服務(wù)器。優(yōu)點(diǎn)：實(shí)現(xiàn)代價(jià)最小（沒(méi)有查詢(xún)流量，也不需要維護(hù)摘要或目錄），內(nèi)容共享效率最高（沒(méi)有緩存冗余）。缺點(diǎn)：對(duì)本地請(qǐng)求的擴(kuò)放性不好（本地用戶(hù)的請(qǐng)求會(huì)被引導(dǎo)到其它的反向代理服務(wù)器）。簇內(nèi)緩存（續(xù)）基于半哈希的緩存方案：本地反向代理服務(wù)器劃出一部分磁盤(pán)空間，用于緩存本地用戶(hù)經(jīng)常請(qǐng)求的內(nèi)容，其余空間采用基于哈希的方法與其它服務(wù)器協(xié)作。優(yōu)點(diǎn)：實(shí)現(xiàn)開(kāi)銷(xiāo)小，內(nèi)容共享效率高，本地內(nèi)容命中率高。簇間緩存基于摘要或目錄的方法：（不可行）擴(kuò)放性差（每個(gè)簇的代表服務(wù)器必須維護(hù)其它簇的服務(wù)器中所存內(nèi)容的信息）。基于哈希（半哈希）的方法：（不可行）局部性不好。基于查詢(xún)的方法：唯一可以應(yīng)用到簇間緩存的方法。簇內(nèi)、簇間使用不同的緩存技術(shù)簇間使用基于查詢(xún)的緩存技術(shù)，簇內(nèi)使用基于哈希的緩存技術(shù)：當(dāng)一個(gè)簇不能服務(wù)某個(gè)內(nèi)容請(qǐng)求時(shí)，其代表服務(wù)器向鄰近的簇（代表服務(wù)器）發(fā)出詢(xún)問(wèn)。在每個(gè)簇內(nèi)，代表服務(wù)器只向內(nèi)容的指定服務(wù)器詢(xún)問(wèn)。（2）緩存更新緩存更新技術(shù)用于保證緩存服務(wù)器上的內(nèi)容是最新的。周期性更新：內(nèi)容提供商配置源web服務(wù)器，向緩存服務(wù)器提供緩存指示，如內(nèi)容的可緩存性、過(guò)期時(shí)間、向源服務(wù)器的核對(duì)時(shí)間等。缺點(diǎn)：每個(gè)更新間隔會(huì)產(chǎn)生大量不必要的更新流量。緩存更新（續(xù)）更新傳播：每當(dāng)源服務(wù)器上的一個(gè)內(nèi)容發(fā)生了改變，更新的內(nèi)容就被主動(dòng)推送到所有的緩存服務(wù)器。缺點(diǎn)：內(nèi)容頻繁更新時(shí)產(chǎn)生過(guò)多的更新流量。按需更新：僅當(dāng)內(nèi)容被請(qǐng)求時(shí)，最新的內(nèi)容拷貝才被投送到發(fā)出請(qǐng)求的緩存服務(wù)器。缺點(diǎn)：源服務(wù)器和緩存服務(wù)器之間來(lái)回傳遞消息（如詢(xún)問(wèn)最新的版本），延遲大。緩存更新（續(xù)）無(wú)效（invalidation）：當(dāng)源服務(wù)器中的某個(gè)文檔發(fā)生改變時(shí)，源服務(wù)器向所有的代理服務(wù)器發(fā)送一個(gè)無(wú)效消息。需要時(shí)，每個(gè)代理服務(wù)器單獨(dú)向源服務(wù)器獲取文檔的最新拷貝。優(yōu)點(diǎn)：消除了不必要的內(nèi)容推送和更新查詢(xún)。缺點(diǎn)：沒(méi)有充分利用CDN的資源，每個(gè)代理服務(wù)器需單獨(dú)向源服務(wù)器獲取文檔的最新拷貝。（3）內(nèi)部緩存策略使用規(guī)則集定義緩存策略：內(nèi)容提供商用一個(gè)規(guī)則集向CDN提供商描述緩存策略；CDN提供商將規(guī)則集傳播給自己的緩存服務(wù)器。使用啟發(fā)式算法：令緩存服務(wù)器使用某種啟發(fā)式算法，自動(dòng)學(xué)習(xí)源服務(wù)器上的內(nèi)容更新頻率，相應(yīng)調(diào)整它們的行為。3.3請(qǐng)求路由（request-routing）請(qǐng)求路由負(fù)責(zé)將用戶(hù)請(qǐng)求發(fā)送到包含該內(nèi)容的一個(gè)最合適的反向代理服務(wù)器上。請(qǐng)求路由系統(tǒng)使用一組度量參數(shù)（如網(wǎng)絡(luò)鄰近性、延遲、距離、服務(wù)器負(fù)載）確定最合適的服務(wù)器。內(nèi)容選擇和投送技術(shù)對(duì)請(qǐng)求路由系統(tǒng)的設(shè)計(jì)有直接影響：若使用全站點(diǎn)方法：用戶(hù)請(qǐng)求被發(fā)送到代理服務(wù)器。若使用部分站點(diǎn)方法：源服務(wù)器投送基本內(nèi)容，代理服務(wù)器投送內(nèi)置的對(duì)象。請(qǐng)求路由的示意圖請(qǐng)求路由系統(tǒng)的關(guān)鍵技術(shù)CDN的請(qǐng)求路由系統(tǒng)包括兩個(gè)關(guān)鍵的部分：請(qǐng)求路由算法：針對(duì)某個(gè)內(nèi)容請(qǐng)求選擇一個(gè)反向代理服務(wù)器的方法。請(qǐng)求路由機(jī)制：將選擇結(jié)果通知用戶(hù)的方法。3.3.1請(qǐng)求路由算法非自適應(yīng)算法：使用某種啟發(fā)式來(lái)選擇緩存服務(wù)器，不考慮當(dāng)前網(wǎng)絡(luò)狀態(tài)，實(shí)現(xiàn)簡(jiǎn)單。當(dāng)啟發(fā)式的假設(shè)滿(mǎn)足時(shí)，算法很有效。自適應(yīng)算法：在選擇緩存服務(wù)器時(shí)考慮當(dāng)前的網(wǎng)絡(luò)狀態(tài)（通過(guò)估計(jì)某些度量參數(shù)獲得），實(shí)現(xiàn)復(fù)雜。面對(duì)瞬間突發(fā)事件時(shí)，算法有很好的魯棒性。（1）非自適應(yīng)算法輪轉(zhuǎn)：假設(shè)所有服務(wù)器具有相同的處理能力，且任何服務(wù)器可以服務(wù)任何請(qǐng)求.內(nèi)容請(qǐng)求按輪轉(zhuǎn)順序發(fā)送給各個(gè)服務(wù)器處理。優(yōu)點(diǎn)：對(duì)于放置在一起的服務(wù)器機(jī)群較有效。缺點(diǎn)：對(duì)于廣域分布式系統(tǒng)不適合（沒(méi)有考慮距離）未充分實(shí)現(xiàn)負(fù)載均衡（沒(méi)有考慮不同請(qǐng)求的計(jì)算開(kāi)銷(xiāo)有差異）非自適應(yīng)算法（續(xù)）基于負(fù)載分級(jí)：假設(shè)服務(wù)器負(fù)載和用戶(hù)-服務(wù)器間距離是影響請(qǐng)求處理效率的最重要因素。所有服務(wù)器按照預(yù)估的負(fù)載（到目前為止已服務(wù)的請(qǐng)求數(shù)）劃分等級(jí)。算法首先根據(jù)負(fù)載等級(jí)選擇侯選服務(wù)器，然后在侯選服務(wù)器中根據(jù)用戶(hù)-服務(wù)器距離再選擇服務(wù)器。優(yōu)點(diǎn)：既考慮了負(fù)載均衡，又考慮了網(wǎng)絡(luò)距離。缺點(diǎn)：需要整個(gè)網(wǎng)絡(luò)的同步，要求較高。非自適應(yīng)算法（續(xù)）基于服務(wù)器的能力：假設(shè)：服務(wù)器接收用戶(hù)請(qǐng)求的比例越高，說(shuō)明服務(wù)器能力越強(qiáng)。用戶(hù)請(qǐng)求被路由到能力強(qiáng)的服務(wù)器，以充分利用資源。基于對(duì)服務(wù)器的偏好：定義對(duì)不同服務(wù)器的偏好，用戶(hù)請(qǐng)求被路由到最偏好的服務(wù)器。（2）自適應(yīng)算法基于網(wǎng)絡(luò)鄰近性：利用一個(gè)周期性更新的路徑長(zhǎng)度來(lái)估計(jì)網(wǎng)絡(luò)鄰近性，將用戶(hù)請(qǐng)求發(fā)送給最近的服務(wù)器。缺點(diǎn)：距離度量的估計(jì)過(guò)程不太精確。基于用戶(hù)-服務(wù)器延遲：利用用戶(hù)訪(fǎng)問(wèn)日志或服務(wù)器側(cè)的延遲測(cè)量值，將用戶(hù)請(qǐng)求發(fā)送到最近報(bào)告了最小延遲的服務(wù)器。優(yōu)點(diǎn)：考慮了延遲缺點(diǎn)：需要維護(hù)集中的測(cè)量數(shù)據(jù)庫(kù)，擴(kuò)放性差。自適應(yīng)算法（續(xù)）基于多種度量值的加權(quán)值：比如，Cisco的DD算法使用AS間距離、AS內(nèi)距離和端到端延遲三種度量值的加權(quán)和。優(yōu)點(diǎn)：靈活性更高。缺點(diǎn)：在每個(gè)服務(wù)器上需要配置一個(gè)測(cè)量代理，增加復(fù)雜度和處理開(kāi)銷(xiāo)。3.3.2請(qǐng)求路由機(jī)制請(qǐng)求路由機(jī)制通知用戶(hù)所選擇的代理服務(wù)器。（1）全局服務(wù)器負(fù)載均衡

（GlobalServerLoadBalancing，GSLB）

服務(wù)節(jié)點(diǎn)：由一個(gè)支持GSLB的web交換機(jī)和許多實(shí)際的web服務(wù)器組成。GSLB交換機(jī)具有全局感知能力：每個(gè)GSLB交換機(jī)知道本地web服務(wù)器的健康和性能信息，并與其它GSLB交換機(jī)交換信息。GSLB交換機(jī)充當(dāng)某些域的權(quán)威DNS服務(wù)器：GSLB交換機(jī)接收特定域的DNS請(qǐng)求，選擇最好的代理服務(wù)器，返回服務(wù)器IP地址。GSLB的請(qǐng)求-路由機(jī)制用戶(hù)鍵入域名解析器