一種基於推拉結合的純分布式數據交換方法
2023-11-06 08:04:22 1
專利名稱：一種基於推拉結合的純分布式數據交換方法
技術領域：
本發明屬於網絡中的數據交換技術領域，特別涉及一種應用於超大規模直播環境下的純分布式數據交換方法。
背景技術：
目前流行的網絡中數據交換方式可分為三種集中式，分布式，以及介於集中式與分布式之間的半分布式。集中式的數據交換雖然易於管理，但在可擴展性、容錯性和數據互動性方面存在先天缺陷。分布式的數據交換在一定程度上彌補了集中式的不足，但對管理提出了更高的要求。半分布式的數據交換是集中式與分布式的一種折中，試圖尋求一種集分布式與集中式優勢於一體的數據交換方式，但其各項性能不是全部最優。
集中式的數據交換方法完全依賴於中央伺服器網絡出口帶寬，由此決定了網絡的負載能力。在集中式的數據交換方式下，對於出口帶寬1000兆的中央伺服器，需要給每個客戶端結點提供1兆帶寬流量的情況下，單臺中央伺服器可同時支持的服務上限是1000人。半分布式的數據交換雖然在一定程度上優於集中式的數據交換方式，但仍部分依賴於中央伺服器的網絡帶寬。在半分布式的數據交換方法下，對於出口帶寬1000兆的中央伺服器，需要給每個客戶端結點提供1兆帶寬流量的相同情況下，單臺中央伺服器可同時支持的服務上限在理論上可達數千人甚至上萬人。分布式的數據交換方式，由於受到技術方面的限制，目前在超大規模直播環境下沒有能夠得到應用。
發明內容
本發明的目的是為克服已有技術的不足之處，提出一種基於推拉結合的純分布式數據交換方法，是基於只有一臺或多臺中央伺服器參與網絡中客戶端結點進入與退出網絡的登記與註銷，中央伺服器不承擔此外的任何功能，包括但不限於數據交換與服務提供。本發明方法較集中式與半分布式有了本質的改變，擁有良好的可擴展性、容錯性和數據互動性等特性，理論上單臺中央伺服器可同時支持的服務數量沒有上限。
本發明提出的一種基於推拉結合的純分布式數據交換方法，其特徵在於，對於單臺中央伺服器與網絡中各個客戶端結點通過周期性地循環進行數據交換，在循環過程中的每個時間周期內，完成一組數據包的發送、接收、請求服務；所述每個客戶端結點在該結點進入網絡時，由中央伺服器統一分配結點編號，並告知該結點網絡中多個鄰居結點的編號、位置等信息；所述每一個客戶端結點的數據交換包括以下步驟(1)該結點建立並更新用於數據交換的本地數據包列表，在該本地數據包列表中包括在該結點的本地緩存中已經收到的並可以為鄰居結點提供服務的數據包的序列號(該序列號的分配是按數據包內容順序連續遞增的，且唯一的)；(2)該結點將其本地數據包列表發送給已知曉的鄰居結點；同時，該結點接收來自已知曉的鄰居結點的本地數據包列表；(3)該結點將所有收到的本地數據包列表進行分析，並建立、更新每一個數據包可以提供服務的候選鄰居結點列表，該候選鄰居結點列表包括所有己收到的本地數據包列表中含有的數據包序列號，每一個數據包序列號對應的可提供服務的若干個的候選鄰居結點編號；(4)若本地數據包列表中存在缺失的數據包(該結點還沒有收到的、造成本地數據包列表中數據包序列號不連續的數據包)，該結點在相對應的數據包候選鄰居結點列表中選取一個或多個鄰居結點，並向該鄰居結點發出對於該數據包的數據請求；同時接收上一個數據請求所返回的數據包；若該結點收到來自鄰居結點的數據請求，對數據請求作出服務響應，將相對應的數據包發送給數據請求方；本發明稱之為基於雙向傳輸的數據請求的過程處於「拉」模式；(5)若該結點自動發送該鄰居結點的本地數據包列表中缺失的數據包給該鄰居結點，本發明稱之為該結點到其某個鄰居結點處於「推」模式；若該結點接收來自該鄰居結點自動發送來的其本地數據包列表中缺失的數據包，本發明稱之為該結點的某個鄰居結點到該結點處於「推」模式，即上述兩種「推」模式均基於單向傳輸的數據廣播；(6)當處於「拉」模式中的某個鄰居結點響應服務請求的各項指標滿足給定的要求時，則其鄰居結點到該結點的通信視為流暢，則該鄰居結點到該結點的數據交換模式由原來的「拉」模式轉換為該結點的某個鄰居結點到該結點的「推」模式(即由該結點的鄰居結點通知該結點開始自動發送該鄰居結點本地數據包列表中的所有數據包給該結點)；(7)若該結點自動發送其本地數據包列表中所有數據給某個鄰居結點期間(即該結點到其鄰居結點處於「推」模式)，數據各指標(延時、丟包等)滿足給定要求時，則該結點到其鄰居結點之間的通信視為阻塞，則該結點到其鄰居結點的數據交換模式由所述的「推」轉為「拉」(即由該結點通知該鄰居結點停止自動發送其本地數據包列表中的所有數據包給該結點)。
以上步驟(1)-(7)構成一個時間周期，循環執行。
所述的本地數據包列表的建立採用一個位向量實現，該位向量由一個上界值和長度確定，其長度(通常為一個固定值)不大於該結點的本地緩存可以容納的數據包數量；該位向量可採用循環隊列的邏輯存儲結構來實現，在實際應用中，可以採用鍊表、數組等方式。
所述本地數據包列表的更新方法為當有新的數據包到達該結點時，對本地數據包列表進行更新，該更新的原則是始終保持位向量的上界值等於該結點當前已經收到的數據包中序列號的最大值。
所述的本地數據包列表中的數據包序列號所指向的數據包是本地緩存中已經收到的數據包的全部或部分。
所述候選鄰居結點列表的建立採用一個位向量實現，該位向量由一個上界值和長度確定，其長度(通常為一個固定值)不大於該結點的本地緩存可以容納的數據包數量；該位向量，可採用循環隊列的邏輯存儲結構來實現，在實際應用中，可以採用鍊表、數組等方式。
所述候選鄰居結點列表的更新方法為當鄰居結點有新的本地數據包列表到達該結點時，對候選鄰居結點列表進行更新，其中更新的原則是始終保持位向量的上界值等於該鄰居結點當前已經收到的本地數據包列表中數據包序列號的最大值，同時更新每一個數據包可以提供服務的候選鄰居結點編號；所述候選鄰居結點列表是用於在「拉」模式中用戶請求數據的可選鄰居結點列表。
所述候選鄰居結點列表中鄰居結點的選取方法，包括但不限於隨機選取、輪盤賭和啟發式方法。
所述鄰居結點到該結點的通信視為流暢的判定方法為匯總與統計該結點與其鄰居結點之間的統計數據(包括但不限於響應率、丟包率和延時時間)，當統計數據滿足給定條件時，該結點與其鄰居結點之間的通信視為流暢。
所述該結點到其鄰居結點之間的通信視為阻塞的判定方法為匯總與統計該結點與其鄰居結點之間的統計數據(包括但不限於響應率、丟包率和延時時間)，當統計數據滿足給定條件時，該結點與其鄰居結點之間的通信視為阻塞。
本發明的特點及技術效果本發明方法提出的純分布式的數據交換，是基於只有一臺或多臺中央伺服器參與網絡中客戶端結點進入與退出網絡的登記與註銷，中央伺服器不承擔此外的任何功能，包括但不限於數據交換與服務提供。本發明方法較集中式與半分布式有了本質的改變，擁有良好的可擴展性、容錯性和數據互動性等特性，理論上單臺中央伺服器可同時支持的服務數量沒有上限。本發明方法結合數據交換二種模式基於單向傳輸的數據廣播的「推」模式和基於雙向傳輸的數據請求的「拉」模式。經過理論論證和實驗證明，推拉結合的純分布式數據交換不但充分發揮了分布式數據交換的優勢，而且使網絡始終保持在一個相對最優的動態平衡點上，大大增加了網絡穩定性。
圖1是本發明方法的流程圖。
圖2是本發明實施例中的某結點的本地數據包列表。
圖3是本發明實施例中的某結點的鄰居結點列表。
圖4是本發明實施例中的某結點的候選鄰居結點列表。
具體實施例方式
本發明提出的一種基於推拉結合的純分布式數據交換方法結合附圖1、2、3、4及實施例詳細說明如下本發明提出的一種基於推拉結合的純分布式數據交換方法，對於單臺中央伺服器與網絡中各個客戶端結點通過周期性地循環進行數據交換(多臺中央伺服器與網絡中各個客戶端結點通過周期性地循環進行數據交換的情況相同)，在循環過程中的每個時間周期內，完成一組數據包的發送、接收、請求服務；所述每個客戶端結點在該結點進入網絡時，由中央伺服器統一分配結點編號，並告知該結點網絡中多個鄰居結點的編號、位置等信息；所述每一個客戶端結點的數據交換實施例，如圖1所示，包括以下步驟(1)結點Point013568建立並更新該結點的用於數據交換的本地數據包列表(結點Point013568的本地數據包列表如圖2所示，有5個數據包序列號，)，在該本地數據包列表中包括在該結點的本地緩存中已經收到的並可以為鄰居結點提供服務的數據包的序列號(該序列號的分配是按數據包內容順序連續遞增的，且唯一的，可以看出其中存在缺失的數據包)；上述的本地數據包列表的建立採用一個位向量實現，該位向量由一個上界值和長度確定，其長度(通常為一個固定值)不大於該結點的本地緩存可以容納的數據包數量，在本實施例中本地數據包列表的長度為1000(如圖2所示，為方便示意，示例中本地數據包列表長度用10代替)；該位向量可採用循環隊列的邏輯存儲結構來實現，本實施例的程序設計中，採用靜態數組的方式實現。
本地數據包列表的更新與維護方法為當有新的數據包到達該結點時，對本地數據包列表進行更新，該更新的原則是始終保持位向量的上界值等於該結點當前已經收到的數據包中序列號的最大值。
本地數據包列表中的數據包序列號所指向的數據包是本地緩存中已經收到的序列號相對大的那一半數據包。
(2)該結點將其本地數據包列表發送給已知曉的鄰居結點(結點Point013568的鄰居結點列表如圖3所示，其有5個鄰居結點)；同時，該結點接收來自己知曉的鄰居結點的本地數據包列表；(3)該結點將所有收到的本地數據包列表進行分析，並建立、更新和維護每一個數據包可以提供服務的候選鄰居結點列表，該列表包括所有己收到的本地數據包列表中含有的數據包序列號，每一個數據包序列號對應的可提供服務的若干個的候選鄰居結點編號(結點Point013568的候選鄰居結點列表如圖4所示，有20個數據包序列號，以及一個或多個可提供這些數據包服務的候選鄰居結點編號)；上述候選鄰居結點列表的建立可採用一個位向量實現，該位向量由一個上界值和長度確定，其長度(通常為一個固定值)不大於該結點的本地緩存可以容納的數據包數量，在本實施例中候選鄰居結點列表的長度為2000(如圖4所示，為方便示意，示例中候選鄰居結點列表長度用20代替)；該位向量，可採用循環隊列的邏輯存儲結構來實現，本實施例的程序設計中，採用鍊表的方式實現。
上述候選鄰居結點列表的更新與維護方法為當鄰居結點有新的本地數據包列表到達該結點時，對候選鄰居結點列表進行更新，其中更新的原則是始終保持位向量的上界值等於該鄰居結點當前已經收到的本地數據包列表中數據包序列號的最大值，同時更新每一個數據包可以提供服務的候選鄰居結點編號；(4)在本地數據包列表中缺失的數據包(該結點還沒有收到的、造成本地數據包列表中數據包序列號不連續的數據包)，該結點在相對應的數據包候選鄰居結點列表中選取一個或多個鄰居結點，並向該鄰居結點發出對於該數據包的數據請求；同時接收上一個數據請求所返回的數據包；該結點收到來自鄰居結點的數據請求，對數據請求作出服務響應，將相對應的數據包發送給數據請求方；即處於基於雙向傳輸的數據請求的「拉」模式；上述候選鄰居結點列表中鄰居結點的選取方法，在本實施例中，綜合考慮網絡性能和系統負載，選擇輪盤賭的方法來實現。
(5)該結點自動發送該鄰居結點本地數據包列表中缺失的數據包給該鄰居結點，即為該結點到其某個鄰居結點處於基於單向傳輸的數據廣播的「推」模式；該結點接收來自該鄰居結點發送過來的其緩衝池中缺失的數據包，即為該結點的某個鄰居結點到該結點處於基於單向傳輸的數據廣播的「推」模式；上述候選鄰居結點列表是用於在「拉」模式中用戶請求數據的可選鄰居結點列表。
(6)當處於「拉」模式中的某個鄰居結點響應服務請求的各項指標滿足給定的要求時，則其鄰居結點到該結點的通信視為流暢，則該鄰居結點到該結點的數據交換模式由原來的「拉」模式轉換為該結點的某個鄰居結點到該結點的「推」模式(即由該結點的鄰居結點通知該結點開始自動發送該鄰居結點本地數據包列表中的所有數據包給該結點)；上述鄰居結點到該結點的通信視為流暢的判定方法為匯總與統計該結點與其鄰居結點之間的統計數據(在本實施例中，包括響應率、丟包率和延時時間)，當統計數據滿足給定條件(同時滿足響應率80％以上，丟包率1％以下，延時時間小於1秒)時，該結點與其鄰居結點之間的通信視為流暢。
(7)若該結點自動發送其本地數據包列表中所有數據給某個鄰居結點期間(即該結點到其鄰居結點處於「推」模式)，數據延時、丟包等指標滿足給定要求時，則該結點到其鄰居結點之間的通信視為阻塞，則該結點到其鄰居結點的數據交換模式由所述的「推」轉為「拉」(即由該結點通知該鄰居結點停止自動發送其本地數據包列表中的所有數據包給該結點)。
上述該結點到其鄰居結點之間的通信視為阻塞的判定方法為匯總與統計該結點與其鄰居結點之間的統計數據(在本實施例中，包括響應率、丟包率和延時時間)，當統計數據滿足給定條件(響應率50％以下，丟包率10％以上，延時時間大於3秒，滿足其中任何一項)時，該結點與其鄰居結點之間的通信視為阻塞。
以上步驟(1)-(7)構成一個時間周期，循環執行。
權利要求
1.一種基於推拉結合的純分布式數據交換方法，其特徵在於，對於單臺中央伺服器與網絡中各個客戶端結點通過周期性地循環進行數據交換，在循環過程中的每個時間周期內，完成一組數據包的發送、接收、請求服務；所述每個客戶端結點在該結點進入網絡時，由中央伺服器統一分配結點編號，並告知該結點網絡中多個鄰居結點的編號、位置等信息；所述每一個客戶端結點的數據交換包括以下步驟(1)該結點建立並更新用於數據交換的本地數據包列表，在該本地數據包列表中包括在該結點的本地緩存中已經收到的並可以為鄰居結點提供服務的數據包的序列號；(2)該結點將其本地數據包列表發送給已知曉的鄰居結點；同時，該結點接收來自已知曉的鄰居結點的本地數據包列表；(3)該結點將所有收到的本地數據包列表進行分析，並建立、更新每一個數據包可以提供服務的候選鄰居結點列表，該候選鄰居結點列表包括所有已收到的本地數據包列表中含有的數據包序列號，每一個數據包序列號對應的可提供服務的若干個的候選鄰居結點編號；(4)若本地數據包列表中存在缺失的數據包，該結點在相對應的數據包候選鄰居結點列表中選取一個或多個鄰居結點，並向該鄰居結點發出對於該數據包的數據請求；同時接收上一個數據請求所返回的數據包；若該結點收到來自鄰居結點的數據請求，對數據請求作出服務響應，將相對應的數據包發送給數據請求方；該過程處於基於雙向傳輸的數據請求的「拉」模式；(5)若該結點自動發送該鄰居結點的本地數據包列表中缺失的數據包給該鄰居結點，則該結點到其某個鄰居結點處於基於單向傳輸的數據廣播「推」模式；若該結點接收來自該鄰居結點自動發送來的其本地數據包列表中缺失的數據包，則該結點的某個鄰居結點到該結點處於基於單向傳輸的數據廣播「推」模式基於單向傳輸的數據廣播；(6)當處於「拉」模式中的某個鄰居結點響應服務請求的各項指標滿足給定的要求時，則其鄰居結點到該結點的通信視為流暢，則該鄰居結點到該結點的數據交換模式由原來的「拉」模式轉換為該結點的某個鄰居結點到該結點的「推」模式；(7)若該結點到其鄰居結點處於「推」模式，數據各指標滿足給定要求時，則該結點到其鄰居結點之間的通信視為阻塞，則該結點到其鄰居結點的數據交換模式由所述的「推」轉為「拉」；以上步驟(1)-(7)構成一個時間周期，循環執行。
2.如權利要求1所述的基於推拉結合的純分布式數據交換方法，其特徵在於，所述的本地數據包列表的建立採用一個位向量實現，該位向量由一個上界值和長度確定，其長度不大於該結點的本地緩存可以容納的數據包數量；該位向量採用循環隊列的邏輯存儲結構來實現。
3.如權利要求1所述的基於推拉結合的純分布式數據交換方法，其特徵在於，所述本地數據包列表的更新方法為當有新的數據包到達該結點時，對本地數據包列表進行更新，該更新的原則是始終保持位向量的上界值等於該結點當前已經收到的數據包中序列號的最大值。
4.如權利要求1所述的基於推拉結合的純分布式數據交換方法，所述候選鄰居結點列表的建立採用一個位向量實現，該位向量由一個上界值和長度確定，其長度(不大於該結點的本地緩存可以容納的數據包數量；該位向量採用循環隊列的邏輯存儲結構來實現。
5.如權利要求1所述的基於推拉結合的純分布式數據交換方法，其特徵在於，所述候選鄰居結點列表的更新方法為當鄰居結點有新的本地數據包列表到達該結點時，對候選鄰居結點列表進行更新，其中更新的原則是始終保持位向量的上界值等於該鄰居結點當前已經收到的本地數據包列表中數據包序列號的最大值，同時更新每一個數據包可以提供服務的候選鄰居結點編號；
6.如權利要求1所述的基於推拉結合的純分布式數據交換方法，其特徵在於，所述候選鄰居結點列表中鄰居結點的選取方法採用隨機選取、輪盤賭和啟發式之一種方法。
7.如權利要求1所述的基於推拉結合的純分布式數據交換方法，其特徵在於，所述鄰居結點到該結點的通信視為流暢的判定方法為匯總與統計該結點與其鄰居結點之間的統計數據，當統計數據滿足給定條件時，該結點與其鄰居結點之間的通信視為流暢。
8.如權利要求1所述的基於推拉結合的純分布式數據交換方法，其特徵在於，所述該結點到其鄰居結點之間的通信視為阻塞的判定方法為匯總與統計該結點與其鄰居結點之間的統計數據，當統計數據滿足給定條件時，該結點與其鄰居結點之間的通信視為阻塞。
全文摘要
本發明涉及一種基於推拉結合的純分布式數據交換方法，屬於網絡中的數據交換技術領域，對於單臺中央伺服器與網絡中各個客戶端結點通過周期性地循環進行數據交換，完成一組數據包的發送、接收、請求服務；包括該結點建立並更新用於數據交換的本地數據包列表；將其本地數據包列表發送給已知曉的鄰居結點；並建立、更新每一個數據包可以提供服務的候選鄰居結點列表；當處於「拉」模式中時的通信流暢，則該鄰居結點到該結點由原來的「拉」模式轉換為「推」模式；若該結點到其鄰居結點處於「推」模式的通信阻塞，則該結點到其鄰居結點由所述的「推」轉為「拉」。本發明方法擁有良好的可擴展性、容錯性和數據互動性等特性。
文檔編號H04L12/56GK1665223SQ20051005150
公開日2005年9月7日 申請日期2005年3月4日 優先權日2005年3月4日
發明者趙黎, 張萌, 毛子青, 羅建光, 吳南山, 楊士強 申請人:清華大學