Trinity的路由演算法概述

買賣虛擬貨幣
網路上資料的傳輸有幾個猶待解決的問題:· 如何快速找到通往目的節點的路徑· 各節點之間如何保證網路拓撲是一致的· 節點狀態的改變如何能快速同步交織尋路(Interweave Routing)演算法是Trinity針對以上問題而提出的尋路演算法,該演算法的好處在於無論網路環境如何變化都能保證連線到通道網路的節點能夠得到全網的網路拓撲,從而讓通道網路達到對等的去中心化網路。這樣很好地規避了由於不同網路的拓撲導致尋路出現偏差,使得A->n 與 n->A之間的路徑變得不一樣,極大地降低使用者的體驗。可靠性證明
交織尋路演算法的可靠性證明:在兩個節點的情況下,很容易證明兩個節點之間的網路拓撲是一樣的。

3個節點的情況下(a,b,c),從a這邊的通路有a-b,a-c. 同樣b也有b-a,b-c. c-a,c-b。 因為a-b和b-a實際上是同一路徑,即a->b恆等於b->a. 因此得證a,b,c三個節點的網路拓撲是完全一樣。

在a,b,c環上繼續增加一個節點a,b,c節點已經是相同的網路拓撲。

接下來只需要把a->d的路徑增加到環狀即可,然後把a,b,c的拓撲同步給d。這樣在a,b,c,d之間保證了網路拓撲的一致

當節點增加到n個時,

當節點增加到n個的情況下(a,b,c……n),每一個節點至少有n-1條路徑,我們記為Ω(n-1), 交織網任意兩節點所輻射的路徑a-b-c…-n,那麼必有一條反向路徑能夠到達a節點(n->n-1->….->a),因為反向路徑可以等同於原路徑,即得證任意兩節點之間的網路拓撲圖是一樣的。

既然已經證明任意兩節點之間的交織網是完全一樣,這樣就解決任意兩節點之間來回傳遞資料的可靠路徑的選擇。Trinity交織網路又增加了對尋路可靠性、時效性、最優費用的綜合考慮,能夠快速地找到來回交易的最最佳化路徑。

交織尋路演算法

search(N,p,s)
initialize-single-source(N,s)
S=Ф
Q=N,V
while Q≠Φ
u=extract-min(Q)
S=S∪{u}
for each vertex v∈G.Adj[u]
relax(u,v,p)

每個交織網的節點記為V,路徑記為P

這個演算法可以在有加權的情況下,在演算法結束的時候,對於所有節點v∈V,我們有v.d=δ(s,v)

那麼尋找節點所需要時間為:Θ(V),使用聚合分析,對每個節點v∈V來說,每次尋找的次數剛好為一次。路徑會有多條,從a->n點,找尋路徑為Σ(v + 2v + … + (n-1)v)=O(n2)。路徑尋找計算公式為:=Θ(P). 所有總搜尋時間為Θ(V2+P)。

為了更好解決尋路演算法Trinity使用路徑標記演算法,使得路徑能在常數時間內操作,即演算法進一步最佳化為Θ(V2)
如果再進一步使用稀疏矩陣加權,使得每次搜尋的攤還時間為O(lgV).那麼時間又會最佳化成O((V+P)lgV)。

節點同步演算法

Delta_add(u,s)
Initialize-change_node(N,v)
v∈V
p∈N
add_delta(v,p,s)
search(N,p,s)
send(p)

Trinity交織網路對於增加、刪除節點是相當迅速,得益於一種增量加權計算模型。能夠快速在交織網路內部實現節點的改動。而且證明該模型也是很簡單的,可靠的。

該模型的主要思想是每次同步不需要攜帶整個拓撲資訊,因為前面已經證明了任意節點之間的拓撲是完全相同的。那麼只要把增量和減量傳送出去即可。對端節點能很快速地更新自己節點的資訊。

Dealdeltanode(S,Delta)
Search_node(S)
If Detla ∈ S
Do add or delete for this Delta Node.
Remove self in Node list.

而且增量加權模型也能輕鬆地解決交織網路中的資料包文的迷失和環路。又能極大地解少報文的長度,避免網路擁擠和阻塞。因為節點可以看作是一個常量,所以在攜帶增量資訊的時候,發起節點會攜帶上網路上其他節點的鏈,當其他節點處理完後,會把自己從節點鏈上摘除自己。當訊息環回的時候就不會再一次處理。資訊量也會隨著節點處理的深入而減少大小。


更多區塊鏈資訊:www.qukuaiwang.com.cn/news

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;