用於網絡解碼及高速緩存輔助內容分配的裝置及方法與流程

2023-06-09 15:42:36 2

本申請案依據35U.S.C.§119(e)主張2014年1月22日申請的第61/930,072號臨時美國申請案的優先權，所述臨時美國申請案的全部內容以引用的方式併入本文中。

背景技術：

目前，內容分配網絡(CDN)面臨與請求式音頻/視頻流的流行度的增加相關聯的容量及效率問題。解決這些問題的一個途徑是通過網絡高速緩存及網絡解碼。舉例來說，常規內容分配網絡(CDN)解決方案採用集中式算法將內容副本放置在網絡內的高速緩存位置中。常規解決方案還包含高速緩存替換策略(例如，LRU(最近最少使用)或LFU(最不常用))以局部管理分布式高速緩存以便提高高速緩存命中率。其它常規解決方案使用隨機線性網絡解碼以按群組傳輸數據包，這可提高容量有限的網絡的處理量。

然而，常規網絡高速緩存及網絡解碼解決方案未考慮高速緩存及傳輸資源的相對效率。這導致每遞送對象或文件的次優化成本。此外，常規內容遞送解決方案未利用網絡高速緩存及網絡解碼的可能的組合益處。

技術實現要素：

根據至少一個實例實施例，一種用於在網絡中傳輸數據文件的方法包含接收來自目的地裝置的針對所述數據文件的數據包的請求。所述方法包含構造衝突圖使得(i)由每一目的地裝置請求的每一數據包由所述衝突圖的多個頂點中的不同頂點表示，(ii)所述多個頂點與所述目的地裝置相關聯，及(iii)基於所述多個頂點中的哪些表示同一請求數據包及哪些請求數據包存儲在屬於目的地裝置的高速緩存中而在所述多個頂點之間創建鏈路。所述方法包含基於所述鏈路將所述多個頂點指派到群組。所述方法包含基於所述指派對所述多個頂點著色以標記所述請求數據包。所述方法包含組合由具有相同顏色的頂點表示的數據包。所述方法包含發送所述經組合的數據包。

根據至少一個實例實施例，創建所述鏈路使得所述多個頂點中的第一者與第二者之間存在鏈路，條件是(i)所述第一及第二頂點不表示同一數據包，及(ii)由所述第一頂點表 示的數據包未存儲在與所述第二頂點相關聯的目的地裝置的高速緩存中，或由所述第二頂點表示的所述數據包未存儲在與所述第一頂點相關聯的目的地裝置的高速緩存中。

根據至少一個實例實施例，所述群組指示到所述多個頂點的若干鏈路。

根據至少一個實例實施例，所述著色包含確定所述多個頂點中的哪些具有最少數目的鏈路且所述多個頂點中的哪些具有最多數目的鏈路。所述著色包含基於到具有最少數目的鏈路的所述頂點的鏈路的數目及到具有最多數目的鏈路的所述頂點的鏈路的數目而計算閾值。所述著色包含基於所述閾值構造所述多個頂點的子集。

根據至少一個實例實施例，所述著色包含從所述子集選擇頂點，確定連結到所述選定頂點的頂點的顏色，以及基於所述確定對所述選定頂點著色。

根據至少一個實例實施例，所述確定顏色將連結到所述選定頂點的頂點的顏色標識為第一組顏色且將所述衝突圖的現有顏色標識為第二組顏色。所述對所述選定頂點著色包含在所述第一組顏色與所述第二組顏色不一致的情況下使用所述第二組中的所要顏色對所述選定頂點著色，以及在所述第一組顏色與所述第二組顏色一致的情況下使用新顏色對所述選定頂點著色。

根據至少一個實例實施例，執行所述著色直到所述多個頂點被著色。

根據至少一個實例實施例，所述方法包含更新所述第二組顏色以包含所述多個經著色的頂點的顏色。

根據至少一個實例實施例，所述方法包含對所述多個經著色的頂點執行局部搜索以減少所述第二組中的顏色的數目。所述局部搜索包含從所述衝突圖的現有顏色中選擇一種顏色，用所述選定顏色標識頂點，以及在未使用不同顏色對連結到所述經標識的頂點的頂點著色的情況下用從所述現有顏色選擇的所述不同顏色替代所述選定顏色。

根據至少一個實例實施例，所述組合對由具有相同顏色的頂點表示的數據包執行異或運算或其它線性組合運算。

應理解，可由通信網絡中的網絡元件(例如，內容源)來執行以上方法。

附圖說明

從以下本文中給出的具體實施方式及附圖將更全面理解實例實施例，其中相似元件由相似參考數字表示，其僅以說明的方式給出且因此未限制實例實施例。

圖1展示根據至少一個實例實施例的內容分配網絡。

圖2為說明根據實例實施例的網絡元件的實例結構的圖式。

圖3A到3B為說明圖2中的網絡元件的實例操作的流程圖。

圖4說明根據至少一個實例實施例的遞送階段的實例操作。

圖5說明根據至少一個實例實施例的構造無向衝突圖的實例操作。

圖6說明根據至少一個實例實施例的對衝突圖著色的實例操作。

圖7A到7D說明根據至少一個實例實施例對衝突圖著色。

具體實施方式

現將參考附圖更全面描述各種實例實施例，其中展示一些實例實施例。

本文揭示詳細說明性實施例。然而，出於描述實例實施例的目的，本文揭示的特定結構及功能細節僅為代表性的。然而，本發明可體現在許多替代形式中且不應被解釋為僅限於本文所闡述的實施例。

因此，雖然實例實施例能夠具有各種修改及替代形式，但實施例僅以圖式中實例的方式展示且在本文中將不對其進行詳細描述。然而，應理解，不希望將實例實施例限於所揭示的特定形式。相反，實例實施例將涵蓋落入本發明範圍內的所有修改、等效物及替代。相似數字貫穿圖式描述指代相似元件。

雖然可在本文中使用術語第一、第二等等以描述各種元件，但這些元件不應受這些術語限制。這些術語僅用於區分一個元件與另一個元件。舉例來說，在不脫離本發明的範圍的情況下，第一元件可被稱為第二元件，且類似地，第二元件可被稱為第一元件。如本文中使用，術語「及/或」包含相關列舉項中的一或多者的任何及全部組合。

當稱元件為「連接」或「耦合」到另一元件時，其可直接連接或耦合到其它元件或可存在介入元件。相反，當稱元件為「直接連接」或「直接耦合」到另一元件時，不存在介入元件。應以相似方式解釋用於描述元件之間的關係的其它詞語(例如，「位於……之間」對「直接位於……之間」、「鄰近」對「直接鄰近」等等)。

本文使用的術語僅用於描述特定實施例的目的且不希望為限制性的。如本文所使用，希望單數形式「一」及「所述」還包含複數形式，除非上下文以其它方式明確指示。進一步將理解，當在本文中使用術語「包括」及/或「包含」時，指定所陳述的特徵、整體、步驟、操作、元件及/或組件的存在，但不排除一或多個其它特徵、整體、步驟、操作、元件、組件及/或其群組的存在或添加。

還應注意的是，在一些替代實施方案中，所指出的功能/動作可不按照圖式中所指出的順序發生。舉例來說，連續展示的兩個圖式事實上可大體上並發地執行或有時可按相反順序執行，這取決於所涉及的功能性/動作。

以下描述中提供特定細節以提供對實例實施例的透徹理解。然而，所屬領域的技術 人員將理解，可在不具有這些特定細節的情況下實踐實例實施例。舉例來說，可在框圖中展示系統以便不在不必要的細節方面使實例實施例混淆。在其它情況中，無需展示眾所周知的過程、結構及技術的不必要的細節以便避免使實例實施例混淆。

在下文描述中，將參考操作的動作及符號表示(例如，以流程圖表、流程圖、數據流程圖、結構圖、框圖等等的形式)描述說明性實施例，操作可被實施為程序模塊，或功能過程包含例程、程序、對象、組件、數據結構等等，其執行特定任務或實施特定抽象數據類型且可使用在現有網絡元件(例如，基站、基站控制器、NodeB、eNodeB等等)處的現有硬體來實施。此現有硬體可包含一或多個中央處理器(CPU)、數位訊號處理器(DSP)、專用集成電路、現場可編程門陣列(FPGA)計算機或類似物。

雖然流程圖可將操作描述為循序過程，但可並行、並發或同時執行許多操作。另外，可重新布置操作的順序。雖然過程可在其操作完成時終止，但還可具有未包含於圖式中的額外步驟。過程可對應於方法、函數、程序、子例程、子程序等等。當過程對應於函數時，其終止可對應於函數返回到調用函數或主函數。

如本文揭示，術語「存儲媒體」或「計算機可讀存儲媒體」可表示用於存儲數據的一或多個裝置，其包含只讀存儲器(ROM)、隨機存取存儲器(RAM)、磁性RAM、磁芯存儲器、磁碟存儲媒體、光學存儲媒體、快閃記憶體裝置及/或用於存儲信息的其它有形機器可讀媒體。術語「計算機可讀媒體」可包含(但不限於)可攜式或固定存儲裝置、光學存儲裝置及能夠存儲、含有或攜載指令及/或數據的各種其它媒體。

此外，可由硬體、軟體、固件、中間件、微碼、硬體描述語言或其任何組合來實施實例實施例。當在軟體、固件、中間件或微碼中實施時，執行必要任務的程序代碼或代碼段可存儲在機器或計算機可讀媒體(例如計算機可讀存儲媒體)中。當在軟體中實施時，一個專用處理器或多個專用處理器將執行必要任務。

代碼段可表示過程、函數、子程序、程序、例程、子例程、模塊、軟體包、類或指令、數據結構或程序語句的任何組合。可通過傳遞及/或接收信息、數據、自變量、參數或存儲器內容將代碼段耦合到另一代碼段或硬體電路。可經由任何合適途徑(包含存儲器共享、消息傳遞、令牌傳遞、網絡傳輸等等)傳遞、轉發或傳輸信息、自變量、參數、數據等等。

圖1展示根據至少一個實例實施例的內容分配網絡。

如圖1中所展示，內容分配網絡(CDN)可包含連接到多個目的地裝置200的網絡元件151。網絡元件151可為用於分配數據文件(例如電影文件)的內容源(例如多播源)。目的地裝置200可為從所述內容源請求數據的終端用戶裝置。舉例來說，每一目的地裝置 200可為允許用戶存取所請求數據的裝置的部分或與所述裝置相關聯。舉例來說，每一目的地裝置200可為機頂盒、個人計算機、平板計算機、行動電話或用於流式音頻及視頻的任何其它相關聯裝置。目的地裝置200中的每一者可包含用於存儲從網絡元件151接收的數據的存儲器。以下將參考圖2及3更詳細描述網絡元件151及目的地裝置200的結構及操作。

圖2為說明根據實例實施例的網絡元件的實例結構的圖式。根據至少一個實例實施例，網絡元件151可經配置以用於通信網絡(例如，圖1的內容分配網絡(CDN))。參考圖2，網絡元件151可包含(例如)數據總線159、發射器152、接收器154、存儲器156及處理器158。雖然為簡明起見，此處不包含單獨描述，但應理解，每一目的地裝置200可具有與網絡元件151相同或類似的結構。

發射器152、接收器154、存儲器156及處理器158可使用數據總線159相互發送數據及/或接收數據。發射器152是包含用於經由到通信網絡中的其它網絡元件的一或多個無線連接來發射無線信號(其包含(例如)數據信號、控制信號及信號強度/質量信息)的硬體及任何必要軟體的裝置。

接收器154是包含用於經由到通信網絡中的其它網絡元件的一或多個無線連接來接收無線信號(其包含(例如)數據信號、控制信號及信號強度/質量信息)的硬體及任何必要軟體的裝置。

存儲器156可為能夠存儲數據的任何裝置，其包含磁性存儲裝置、快快閃記憶體儲裝置等等。

處理器158可為能夠處理數據的任何裝置，其包含(例如)專用處理器，所述專用處理器經配置以基於輸入數據執行特定操作，或能夠執行包含於計算機可讀碼中的指令。舉例來說，應理解，下文所描述的修改及方法可存儲在存儲器156上且由網絡元件151內的處理器158實施。

此外，應理解，可由上文所描述的網絡元件151的元件中的一或多者執行下文修改及方法。舉例來說，接收器154可執行「接收」、「獲取」及類似行為的步驟；發射器152可執行「發射」、「輸出」、「發送」及類似行為的步驟；處理器158可執行「確定」、「產生」、「關聯」、「計算」及類似行為的步驟；且存儲器156可執行「存儲」、「保存」及類似行為的步驟。

圖3A到3B為說明圖2中的網絡元件的實例操作的流程圖表。舉例來說，圖3A到3B展示用於執行通信網絡中的高速緩存方法的實例操作。圖4到6展示用於在已執行高速緩存方法之後遞送數據文件的實例操作。

應理解，圖3A到3B用於執行與下文的算法1相關的高速緩存分配方法，其中每一數據文件『f』被分成『B』相等大小的數據包(由有限域的符號表示)且屬於庫『F』：

算法1：高速緩存算法

在算法1中，『pu＝[pu，1，...pu，m]』是『u』目的地裝置200的高速緩存分配，其中其中u＝1、…、n，且0≤pu，f≤1/Mu，u＝1、…、n，『m』是由網絡元件151託管的文件的數目，且『Mu』是在目的地裝置『u』(即，目的地裝置200)處的高速緩存的存儲容量且Mu，f＝pu，fMuB表示在用戶u處高速緩存的文件f的數據包。網絡元件151執行算法1使得目的地裝置『u』裝置200高速緩存文件『f』的Mu，f＝pu，fMuB數據包。此外，算法1的隨機性質允許網絡裝置151執行操作使得，如果兩個目的地裝置高速緩存給定文件『f』的相同數目的數據包，那麼兩個目的地裝置200中的每一者高速緩存同一文件『f』的不同數據包。可由網絡元件151根據下文圖3A到3B中所描述的操作來實施算法1。

參考圖3A，在操作300中，網絡元件151可確定多個數據文件的流行度。數據文件可為(例如)視頻及/或音頻文件。網絡元件151可基於來自目的地裝置200中的至少一者的針對多個數據文件的請求(例如用戶請求)而確定流行度。用戶請求可形成數據文件的需求分布。網絡元件151可根據所有目的地裝置200的需求分布確定流行度。在此情況中，需求分布可遵循齊夫(Zipf)分布。替代地，網絡元件151可確定每目的地裝置的流行度，其中每一目的地裝置200具有相關聯的需求分布。

網絡元件151可基於來自目的地裝置200的針對數據文件的請求的數目確定流行度。舉例來說，網絡元件151確定由目的地裝置200請求100次的數據文件比被請求50次的數據文件具有更高的流行度。因此，流行度可基於哪些數據文件被目的地裝置200的用戶最經常請求及查看。

網絡元件151可將每一數據文件分成多個數據包。舉例來說，網絡元件151可將每一數據文件分成相同數目的數據包(例如三個數據包)。因此，在操作中310，網絡元件151可基於操作300中確定的流行度而將多個數據文件的隨機數據包發送到至少一個目的地裝置。舉例來說，網絡元件151可將每一數據文件的隨機數據包發送到目的地裝置200使得隨機數據包存儲(或高速緩存)於每一目的地裝置200處。

網絡元件151可發送隨機數據包使得每一目的地裝置200基於確定的流行度及輸入參數(例如，目的地裝置的數目、流行度分布、每一目的地裝置的高速緩存大小、位於網絡元件151處的數據文件庫的大小等等)接收針對數據文件中至少一者的給定數目的隨機數據包。舉例來說，如果目的地裝置200具有相同大小的高速緩存及相同需求分布(例如，目的地裝置是均勻的)，那麼網絡元件151可將相同數目的數據包發送到每一目的地裝置200。在一個實例中，假設存在兩個目的地裝置1及2及兩個文件A及B(分成十個數據包)。如果(i)目的地裝置1及2以相同頻率請求文件A及文件B，且文件A以比文件B更高的頻率被兩個目標請求，及(ii)兩個目的地裝置1及2具有相同高速緩存大小(例如，按數據包計為六個單元)，那麼網絡元件151將執行高速緩存方法，使得兩個目的地裝置1及2高速緩存文件A的四個數據包及文件B的兩個數據包。

如果網絡元件151在操作300中基於每個目的地裝置確定流行度，那麼網絡元件151可在操作310中基於每個目的地裝置發送隨機數據包。舉例來說，如果目的地裝置200具有不同大小的高速緩存或不同需求分布，那麼網絡元件151可將不同數目的數據包發送到每一目標。在此情況中，參考以上的實例，目的地裝置1可接收文件A的七個數據包及文件B的三個數據包，而目的地裝置2可接收文件A的兩個數據包及文件B的五個數據包。此可歸因於以下事實：目的地裝置1請求文件A比請求文件B多得多，且按數據包計具有十個單元的總高速緩存大小，而目的地2裝置請求文件A比請求文件B少得多，且按數據包計具有七個單元的總高速緩存大小。

圖3B說明可根據需要在操作300與310之間執行的網絡元件151的實例操作。舉例來說，在圖3A中的操作300之後，網絡元件151可基於所確定的流行度對數據文件進行排名。舉例來說，在操作301中，網絡元件151可使用操作300中所確定的流行度對數據文件從最流行的數據文件到最不流行的數據文件進行排名。

在操作302中，網絡元件151可基於排名選擇(針對每一數據文件)若干隨機數據包。舉例來說，網絡元件151根據每一數據文件的相應排名及網絡的輸入參數(例如，目的地裝置的數目、流行度分布、每一目的地裝置的高速緩存大小、位於網絡元件151處的數據文件庫的大小等等)中的至少一者針對每一目標200及針對數據文件中的每一者選擇 不同數目的隨機數據包。在操作302之後，網絡元件151可行進回到圖3A中的操作310以發送針對每一數據文件的選定數目的隨機數據包。

應了解，操作302可包含網絡元件151基於至少一個閾值將經排名的數據文件至少分成第一子集及第二子集。所述至少一個閾值可基於經驗證據及/或用戶定義。第一子集可含有比第二子集排名更高的數據文件。因此，在操作310中，網絡元件151可發送僅針對第一子集中的數據文件的選定數目的隨機數據包。相較於常規多播技術，這可允許數據包在目的地裝置200處的更有效的高速緩存，且減少遞送期間的傳輸數目。

應理解，參考圖3A及3B描述的操作允許網絡改進性能，這是因為相較於常規多播技術，方案能夠高速緩存更流行文件的更多數據包，增加(或替代地，最大化)由目的地裝置200共同高速緩存的每一文件的不同數據包的量，且減少遞送期間的傳輸數目。

結合以上描述的高速緩存方法，本申請案揭示用於遞送階段的實例方法，其中數據文件的請求的數據包經遞送到目的地裝置200。用於遞送階段的實例方法是基於圖論。

圖4說明根據至少一個實施例的遞送階段的實例操作。參考圖4，在操作400中，網絡元件151從目的地裝置200(或用戶裝置)接收對數據文件的數據包的請求。由於網絡元件151已執行以上所描述的高速緩存方法，因此每一目的地裝置200僅請求未經高速緩存(或存儲)的那些數據包作為高速緩存方法的結果。因此，遞送階段包括：向每一目的地裝置200提供所請求的文件的丟失部分，即，從目的地裝置200的存儲器丟失的數據包。

在操作410中，網絡元件151構造具有多個頂點的衝突圖，使得由每一目的地裝置200請求的每一數據包由所述衝突圖的多個頂點中的不同頂點表示。因此，即使同一數據包由K個不同用戶請求，所述數據包也被表示為衝突圖中的K個不同頂點。換句話說，衝突圖中的每一頂點與唯一一對目的地裝置200及所請求的數據包相關聯。因此，可以說，衝突圖的每一頂點與目的地裝置200相關聯且表示由那個目的地裝置200請求的數據包。此外，網絡元件151可基於所述多個頂點中的哪些表示同一請求數據包及哪些請求數據包存儲在屬於目的地裝置200的高速緩存中而構造衝突圖。下文參考圖5及6進一步詳細描述操作410。

仍參考圖4，在操作420中，網絡元件151可將多個頂點指派到群組。每一群組可指示到多個頂點的若干鏈路。舉例來說，每一頂點可具有到周圍頂點的給定數目的鏈路。在一個實例中，如果頂點A及頂點B各自具有到其它頂點的三個鏈路，且頂點C及頂點D各自具有到其它頂點的四個鏈路，那麼頂點A及B屬於一個群組(例如群組3)且頂點C及D屬於不用群組(例如群組4)。

在操作445中，網絡元件151對多個頂點著色作為標記衝突圖上的所請求的數據包的途徑。舉例來說，網絡元件151基於操作430中所指派的群組對多個頂點著色。下文參考圖6進一步詳細論述操作445。

在操作480中，網絡元件151組合由具有相同顏色的頂點表示的所請求的數據包。舉例來說，網絡元件151對由具有相同顏色的頂點表示的數據包執行異或(XOR)運算(或有限域上的其它線性組合運算)。

在操作490中，網絡元件151發送經組合的數據包。舉例來說，網絡元件151經由多播傳輸將經組合的數據包發送到目的地裝置200。通過在傳輸之前組合數據包，應理解，根據至少一個實例實施例的遞送方法可減少網絡元件151的傳輸數目，這可減少消耗並提高網絡效率。應理解，目的地裝置200可使用XOR運算(或有限域上的其它線性組合)接收並解碼所傳輸的經組合的數據包。舉例來說，目的地裝置200可使用存儲在高速緩存中作為密鑰的數據包解碼經組合的數據包。

圖5說明根據至少一個實例實施例構造衝突圖的實例操作。舉例來說，圖5進一步詳細論述圖4的操作410。圖5說明用於構造無向衝突圖的實例操作。可結合著色方案使用無向衝突圖，所述著色方案在本申請案中是指貪心隨機算法搜索程序(GRASP)著色方案。下文參考圖6更詳細描述此著色方案。

參考圖5，在操作511中，網絡元件151分析來自在操作410中填入的多個頂點的兩個頂點『Vi』及『Vj』。在操作513中，如果網絡元件確定頂點Vi及Vj表示同一所請求的數據包，那麼網絡元件151在操作515中不創建所述兩個頂點之間的鏈路(或邊)。接著，網絡元件151進行到操作531以確定是否已分析衝突圖中的所有頂點。

在操作513中，如果網絡元件151確定頂點Vi及Vj不表示同一所請求的數據包，那麼網絡元件151進行到操作517且檢查請求由頂點Vi表示的數據包的與頂點Vi相關聯的目的地裝置200的高速緩存(或存儲器)。在操作519中，如果網絡元件151確定表示頂點Vj的數據包在請求由頂點Vi表示的數據包的與頂點Vi相關聯的目的地裝置200的高速緩存中不可用，那麼在操作521中網絡元件151創建頂點Vi與頂點Vj之間的鏈路。接著，網絡元件151進行到操作531以確定是否已分析衝突圖中的所有頂點。

在操作519中，如果網絡元件151確定表示頂點Vj的數據包在請求由頂點Vi表示的數據包的與頂點Vi相關聯的目的地裝置200的高速緩存中可用，那麼在操作523中網絡元件151檢查請求由頂點Vj表示的數據包的與頂點Vj相關聯的目的地裝置200的高速緩存。在操作525中，如果表示頂點Vi的數據包在請求由頂點Vj表示的數據包的與頂點Vj相關聯的目的地裝置200的高速緩存中不可用，那麼網絡元件151在進行到 操作431之前在操作527中創建頂點Vi與Vj之間的鏈路以確定是否已分析衝突圖中的所有頂點。

在操作525中，如果網絡元件151確定表示頂點Vi的數據包在請求由頂點Vj表示的數據包的與頂點Vj相關聯的目的地裝置200的高速緩存中可用，那麼網絡元件151在操作529中不創建頂點Vi與Vj之間的鏈路。接著，網絡元件151進行到操作531以確定是否已分析衝突圖中的所有頂點。

一旦網絡元件151已分析衝突圖中的所有頂點，那麼網絡元件151在操作533中返回經構造的衝突圖。

鑑於圖5，應理解，圖4中的構造操作410可通過創建多個頂點中的第一者與第二者之間的鏈路的操作來總結，條件是(i)第一頂點及第二頂點不表示同一數據包，且(ii)由第一頂點表示的數據包未存儲在與第二頂點相關聯的用戶裝置的高速緩存中，或由第二頂點表示的數據包未存儲在與第一頂點相關聯的用戶裝置的高速緩存中。

圖6說明根據至少一個實例實施例的對衝突圖著色的實例操作。在此應用中，著色方案可稱為貪心隨機算法搜索程序(GRASP)著色方案。圖6中的操作可對應於以下算法。以下是一般GRASP著色方案算法：

將函數「BuildGreedyRandAdaptive」定義為：

將函數「MakeRCL」定義為：

將函數「GetColor」定義為：

將函數「LocalSearch」定義為：

在以上的偽代碼中，HM,W＝(V,E)表示(無向)衝突圖，其中V及E分別表示如上文參考圖5所論述而構造的無向衝突圖HM,W的頂點及邊(或鏈路)的集合。在HM,W中，對於每一頂點i∈V，Adj(i)＝{j∈V|[i,j]∈E}。cbest是表示通過所述算法找到的最佳關聯顏色-頂點。對於所有i∈V，令d(i)＝|Adj(i)|為頂點i的度數(或到頂點i的鏈路的數目)。令為構造解，即，頂點的集合已被指派到顏色(最初是空集)，且令(最初為空集)為關聯到cbest中的至少一個頂點的顏色的集合。在每一迭代處，執行以下運算：

1.對於所有i∈V，令d(i)＝|Adj(i)|為頂點i的度數(或到頂點i的鏈路的數目)。令為構造解(最初是空集)，即，頂點的集合已被指派到顏色，且令(最初為空集)為關聯到cbest中的至少一個頂點的顏色的集合。

2.隨機均勻地在[0,1]中選擇參數β。

3.計算(參見函數MakeRCL)：

gmin，最小貪心值：

gmax，最大貪心值：

閾值tau(τ)：

τ＝gmin+[β·(gmax-gmin)]，其中β∈[0，1]；且

RCL作為其度數為至少τ的候選未經著色的頂點的子集：

RCL＝{i∈V\c|d(i)≥τ}；

4.執行以下運算直到所有頂點被著色：

a.從RCL隨機選擇頂點i(參見函數BuldGreedyRandAdaptive的行4，即，i＝SelectIndex(RCL))。注意β∈[0,1]的值確定待於每一迭代處插入RCL中的頂點的選擇中的貪心度對隨機度的百分比。舉例來說，對於β＝1，選擇為完全貪心且僅具有度數gmax的頂點插入RCL中。作為另一實例，對於β＝0，選擇為完全隨機的且所有候選頂點插入RCL中(即，RCL＝W)；

b.選定頂點i，且分析其鄰近頂點(參見函數GetColor)；可發生四種可能情況：

I.所有鄰近頂點仍未被著色且集合在此情況中，新顏色c被指派到頂點i且C＝C∪{c}(圖7A)；

II.所有鄰近頂點仍未被著色且集合在此情況中，使用可用的第一顏色c∈C對頂點i著色(圖7B)；

III.用顏色c∈C對至少一個鄰近頂點著色且所有當前使用的顏色c∈C已被指派到至少一個鄰近頂點：在此情況中，用新顏色c＇對頂點i著色且C＝C∪{c＇}(圖7C)；且

IV.用顏色c∈C對至少一個鄰近頂點著色且存在未被指派到任一鄰近頂點的顏色c＇∈C：在此情況中，用顏色c＇對頂點i著色(圖7D)。

c.頂點i被插入構造解(c[i]＝c＇或c[i]＝c，根據情況(I)到(IV)及目標函數值一致地更新(即，f(c)＝|C|)。

5.一旦衝突圖的所有頂點被著色，那麼函數BuldGreedyRandAdaptive返回解cbest。

6.實施局部搜索，其將cbest作為輸入且返回新有效顏色c*(參見函數LocalSearch)。迭代地，對於每一顏色c∈C計算用顏色c著色的所有頂點的集合Gc(函數LocalSearch的行2)且執行以下步驟：

a.對於每一頂點i∈Gc，搜索頂點Adj(i)，即，鄰近於頂點i的頂點。如果存在未指派到任何鄰近頂點j∈Adj(i)的顏色c＇∈C，c＇≠c，那麼用顏色c＇對頂點i著色；

b.若且唯若可能用某種顏色c＇(c＇≠c)替代與每一頂點i∈Gc相關聯的c時，將顏色c從集合C移除。

7.如果c*中使用的顏色的數目小於cbest中使用的顏色的數目，那麼集合cbest等於c*，否則將cbest保持為部分解。(參見GRASP算法的行8到12)。

8.重複所有以上運算1到7直到k＝MaxIterations且返回cbest作為解。

從以上描述，應了解，GRASP著色方案執行所要數目的迭代，直到滿足停止準則(例如(舉例來說)最大數目的迭代或所要運行時間)。在每一迭代處，貪心-隨機自適應解c從c開始構建作為初始解，且局部搜索階段經執行以返回局部最優解c*。在迭代結束時，最佳局部最優解cbest(即，對應於最佳函數目標值f(cbest)的解)被返回作為最終解且算法停止。

GRASP著色方案能夠解決以任何圖形拓撲、密度/稀疏度及任何大小為特徵的問題實例。局部搜索策略通過專注於每一頂點(一次一個)檢查冗餘顏色。

現將參考圖6描述以上算法。在操作600中，網絡元件151設置初始條件。舉例來說，網絡元件151設置將針對GRASP著色方案而被執行的若干迭代「maxiter」。迭代「maxiter」的數目可為用戶定義的及/或基於經驗證據。在以下操作中，『V』是衝突圖的頂點的集合，『V_1』是經著色的頂點的集合，且『V_2』是未經著色的頂點的集合。在第一迭代處，V_1是空集且V_2＝V。

在操作605中，網絡元件151基於經指派為『gmin』的群組確定V中頂點中的哪些具有最少數目的鏈路(或邊)。舉例來說，如果存在群組2到6，其中群組2頂點具有兩個鏈路，群組3頂點具有三個鏈路，等等，那麼對於整個衝突圖來說，兩個鏈路是到頂點的最少數目的鏈路，且將gmin設置為『2』。在操作610中，網絡元件151基於經指派為『gmax』的群組確定V中頂點中的哪些具有最多數目的鏈路(或邊)。在以上實例中，由於最大群組數目是群組6，因此可將gmax設置為『6』，這就意味著到衝突圖中的頂點中的任一者的最大數目的鏈路是6個鏈路。在操作615中，網絡元件151基於『gmin』及『gmax』計算閾值tau。舉例來說，網絡元件151可計算閾值使得tau＝gmin+β(gmax-gmin)，其中β為用戶定義的及/或基於經驗證據的常數(例如，可在[0,1]中均勻隨機選擇β)。

在操作620中，網絡元件151可構造屬於具有大於或等於閾值tau的鏈路的數目的群組的未經著色的頂點的子集(或受限候選列表「RCL」)。應理解，β的值取決於在待包含於子集中的頂點的選擇中的「貪心度」的量對「隨機度」的量。舉例來說，對於β＝1，由於僅那些具有最大數目的鏈路的頂點將包含於子集中，因此選擇是完全貪心的。如果(舉例來說)β＝0，那麼所有頂點將包含於子集中。

在操作625中，網絡元件151從在操作620中創建的子集選擇(例如隨機選擇)頂點「Vi」。在操作630中，網絡元件151將鄰近於(或連結到)頂點Vi的頂點的顏色標識為第一組顏色。作為操作630的部分，網絡元件151也可將衝突圖的現有顏色標識為第二 組顏色。在操作635中，網絡元件151確定是否可將衝突圖的現有顏色指派到頂點Vi。舉例來說，在操作640中，在第一組顏色與第二組顏色不一致的情況下，網絡元件151用來自第二組的所要顏色對頂點Vi著色。否則，在操作645中，如果第一組顏色與第二組顏色一致，那麼網絡元件151選擇新顏色，且在操作650中將所述新顏色指派到頂點Vi且使所述新顏色包含於用於對衝突圖著色的現有顏色的集合。下文參考圖7A到7C更詳細論述操作635。

在操作655中，網絡元件151確定是否所有頂點皆被著色。如果並非所有頂點皆被著色，那麼網絡元件151返回到操作605。如果所有頂點皆被著色，那麼網絡元件151在操作660中執行局部搜索(例如上文的LocalSearch算法)以減少用於衝突圖的顏色的數目(即，減少來自集合V_1的顏色的數目)。舉例來說，網絡元件151可從衝突圖的現有顏色選擇顏色，用選定顏色標識頂點，且在未使用不同顏色對連結到所標識的頂點的頂點著色的情況下使用選自現有顏色的不同顏色替代選定顏色。因此，將選定顏色從現有顏色的集合消除。

在操作665中，網絡元件可從由局部搜索產生的解選擇最佳解(即，導致用於衝突圖的最少數目的顏色的解)。在操作670中，網絡元件151確定當前迭代「iter」是否小於操作600中設置的迭代「maxiter」的數目。如果當前迭代「iter」小於操作600中設置的迭代「maxiter」的數目，那麼網絡元件151返回到操作600且使迭代「iter」的數目增加一(即，設置iter＝iter+1)。作為操作670的部分，網絡元件151可將局部搜索的結果存儲在存儲器中(其中結果是經著色的衝突圖)。如果網絡元件151確定迭代「iter」的當前數目等於「maxiter」，那麼網絡元件151進行到操作680且返回在由每一迭代發現的所存儲的解當中的最佳解。舉例來說，網絡元件151返回使用最少數目的顏色的衝突圖。

圖7A到7D說明根據至少一個實例實施例的經著色的衝突圖。舉例來說，圖7A到7D展示與圖6中的操作625到650相關的實例。在圖7A到7D中，操作625中選擇的頂點Vi由頂點「i」表示，且在操作630中將頂點「j」、「k」、「x」及「y」標識為鄰近於(或連結到)頂點「i」(即，Adj(i)＝{j,k,x,y})。

圖7A表示所有鄰近頂點j、k、x及y皆未被著色的情況。圖中現有顏色的集合(即，圖6中的V_1)為空集。在此情況中，網絡元件151在操作645中選擇新顏色『c』(即，黃色)且將顏色黃色指派到頂點i。現有顏色的集合V_1經更新以包含顏色黃色。圖7B說明另一情況，其中現有顏色的集合V_1已包含顏色黃色(且還包含藍色)。此處，由於頂點j、k、x及y皆未用黃色著色，因此網絡元件151通過將黃色(或甚至藍色，因為仍未對其它頂點著色)指派到頂點i來執行操作640。

圖7C展示現有顏色的集合V_1包含已被指派到連結到頂點i的頂點的顏色的情況。在此情況中，網絡元件151執行操作645及650以選擇新顏色『c』(即，黃色)且更新現有顏色的集合V_1以包含顏色黃色。

圖7D展示網絡元件151將顏色藍色指派到頂點『i』的情況，因為連結到頂點『i』的頂點都不具有顏色藍色且因為顏色藍色已在現有顏色的集合V_1中。

應理解，上文描述的操作允許網絡的改進性能，這是因為實例實施例允許能夠在目的地裝置200處高速緩存更流行文件的更多數據包，增加(或替代地，最大化)由目的地裝置200共同高速緩存的每一文件的不同數據包的量，且允許數據文件的所請求的數據包的完整集合內的經解碼的多播傳輸。此外，通過在傳輸之前組合所請求的數據包，應理解，根據至少一個實例實施例的遞送方法及/或裝置可減少網絡元件151的傳輸數目，這可減少消耗且提高網絡效率。

實例實施例的變型不應被視為脫離實例實施例的精神及範圍。所屬領域的技術人員將清楚，所有此類變型希望包含於本發明的範圍內。