Trinity Routing Algorithm
Introduction
There are several problems to be solved in the data communication on the network:
How to quickly find the path to the target node?
How to ensure the consistency of network topology between nodes?
How to quickly update the node state?
Interweave Routing is a pathfinding algorithm proposed by Trinity to address the issues mentioned above. The advantage of this algorithm is that the nodes connected to the channel network can get the network topology of the whole network regardless the change of network environment so that the channel network becomes a decentralized network. This is a good way to avoid the deviation in pathfinding due to the topology of different networks, which makes the path between A->n and n->A different and hurts user experience greatly.
Verification
Verification of Interweave Routing
In the case of two nodes, it is easy to prove that the network topology between the two nodes is identical.
In the case of three nodes (a, b, c), the paths from a are: a-b and a-c. Similarly, the paths from b are b-a, b-c, c-a and c-b. As a-b and b-a are the same path, a->b is equivalent to b->a. Therefore, the network topology between the three nodes a, b, and c is identical.
Add a node outside the triangle of a, b, c.
The nodes of a, b, and c have identical network topology. The next step is to add the path of a->d to the triangle and synchronize the topology of a, b, and c with d. This ensures consistency of network topology between a, b, c, and d.
Add n nodes.
When n nodes are added (a, b, c … n), each node has at least n-1 paths, which is denoted by Ω(n-1). In the path of any two nodes on the interweave network, namely, a-b-c…-n, there must be a reverse path to the node of a: n->n-1->….->a. As reverse path can be equivalent to the original path, the network topology between any two nodes is identical.
The verification of identical network topology between any two nodes on the interweave network solves the selection problem of a reliable path for data communication between any two nodes. Taking reliability, timeliness and optimal cost in pathfinding into considerations, the Trinity interweave network is able to find the optimal path for transactions fast.
Interweave Routing Algorithm
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)
Every interweave node is denoted by V, and path by P.
When this algorithm runs through, in weighted terms, for all nodes v∈V, v.d=δ(s,v).
Then the time required for searching nodes isΘ(V). With aggregated analysis, every node v∈V only needs to search once at a time. There are many paths from a->n, with the total number calculated byΣ(v + 2v + … + (n-1)v)=O(n2). The path finding function is
=Θ(P). And the time for searching is Θ(V2+P).
To optimize path finding algorithm, Trinity uses pathmark algorithm, which narrows down the time of path operation within a constant range. Thus, the function is upgraded to Θ(V2).
If we use weighted sparse matrix, the amortized time of every searching will be O(lgV), so the operation time will be further improved as O((V+P)lgV).
Node Synchronization Algorithm
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 interweave network response swiftly to any addition or deletion of nodes. Thanks to the incremental weighted calculation model, changes of nodes in a complex network can be quickly realized. This model is proven simple and reliable. The main idea of this model is not synchronizing all topological information. As the topology between nodes have been proven identical previously, only additional or reduced parameters will be sent. Thus, the corresponding node quickly update itself on the new information.
Dealdeltanode(S,Delta)
Search_node(S)
If Detla ∈ S
Do add or delete for this Delta Node.
Remove self in Node list.
Moreover, the incremental weighted calculation model can easily prevent the loss and loop of data messages while minimizing the length of the message and avoiding network congestion. Nodes in this model can be denoted by a constant. When adding messages, the initiating node will carry the graph of the other nodes of the network. After all other nodes finish synchronization, the initiating node will remove itself from the graph. So the message will not go back and be resent by the initiating node. As nodes matures, the length of the message will be greatly shortened.
Trinity Telegram Channel: https://t.me/TrinityStateChannels
Official Website: https://trinity.tech/#/
Trinity Github: https://github.com/trinity-project
