RoutingTables
Implementation.RoutingTables History
Hide minor edits - Show changes to output
Changed lines 56-58 from:
Now each path in the graph represents a real payment that we can actually make.
to:
Now each path in the graph represents a real payment that we can actually make.
Well, that's not quite true: Because each account between users is represented by two separate nodes in our routing graph, it's possible that a path in the routing graph crosses back over the same underlying account in the opposite direction without making a loop in the routing graph. So we have to watch for this. Going back through the same user is OK, because it might be the only way to make the required exchanges, or to get to the target account -- so long as we don't cross back over the same account.
Well, that's not quite true: Because each account between users is represented by two separate nodes in our routing graph, it's possible that a path in the routing graph crosses back over the same underlying account in the opposite direction without making a loop in the routing graph. So we have to watch for this. Going back through the same user is OK, because it might be the only way to make the required exchanges, or to get to the target account -- so long as we don't cross back over the same account.
Changed lines 34-35 from:
to:
!! Network representations
Changed lines 31-56 from:
to:
Jevgenij: Could you explain here: why does it require all the routing tables to be in memory? - I don't see serious reasons for that. Did you mean '''the whole adjacency list'''? Or, would you prefer to have no topology representation other than routing tables at all?
!!! Network representations
The obvious way to represent the network is to give each user one or more nodes, where each node connects accounts that it exchanges between:
Attach:nodegraph.png
The problem with this is that it does not allow a natural representation of one-way exchanges. One-way exchanges are not expected to be the norm, but ought to be allowed, for example, when someone wants to convert from a foreign currency to their local one, but not back.
To represent the directionality of exchanges that a user can perform, exchanges must become the edges of the new graph, and then accounts, which are the edges of the old graph, become the nodes of the new graph:
Attach:acctgraph_bad.png
Here we have labelled accounts by the two users they connected in the original graph.
This seems OK at first, and it also gives a natural way to specify payments to a particular account. But what it does not specify is which account partner will receive the payment. What if user 1 wants to pay user 2, and user 2 wants to receive payment on her account with user 3, labelled (2,3)?
From the graph we currently have, it looks like we could just take path (1,2) -> (2,3). But we see from the original graph that that makes no sense, since it is asking user 2 to receive payment on her account with user 1, and then call that equivalent to her account with 3, since she has declared an exchange rate between the two. But what she really wants is to hold obligations from user 3 instead of from user 1, and our current graph is misleading.
What we really need to do is turn account (2,3) into two separate nodes, one where user 2 receives payment, and one where user 3 receives payment. We will call the one where user 2 receives payment (3,2), and the one where user 3 receives payment (2,3). Now the graph looks like:
Attach:acctgraph_good.png
Now each path in the graph represents a real payment that we can actually make.
!!! Network representations
The obvious way to represent the network is to give each user one or more nodes, where each node connects accounts that it exchanges between:
Attach:nodegraph.png
The problem with this is that it does not allow a natural representation of one-way exchanges. One-way exchanges are not expected to be the norm, but ought to be allowed, for example, when someone wants to convert from a foreign currency to their local one, but not back.
To represent the directionality of exchanges that a user can perform, exchanges must become the edges of the new graph, and then accounts, which are the edges of the old graph, become the nodes of the new graph:
Attach:acctgraph_bad.png
Here we have labelled accounts by the two users they connected in the original graph.
This seems OK at first, and it also gives a natural way to specify payments to a particular account. But what it does not specify is which account partner will receive the payment. What if user 1 wants to pay user 2, and user 2 wants to receive payment on her account with user 3, labelled (2,3)?
From the graph we currently have, it looks like we could just take path (1,2) -> (2,3). But we see from the original graph that that makes no sense, since it is asking user 2 to receive payment on her account with user 1, and then call that equivalent to her account with 3, since she has declared an exchange rate between the two. But what she really wants is to hold obligations from user 3 instead of from user 1, and our current graph is misleading.
What we really need to do is turn account (2,3) into two separate nodes, one where user 2 receives payment, and one where user 3 receives payment. We will call the one where user 2 receives payment (3,2), and the one where user 3 receives payment (2,3). Now the graph looks like:
Attach:acctgraph_good.png
Now each path in the graph represents a real payment that we can actually make.
Changed lines 25-26 from:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs('''distance1''' - '''distance2''') > 1
to:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1 - d2) > 1
Changed lines 25-26 from:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs('''distance1'''-'''distance2''') > 1
to:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs('''distance1''' - '''distance2''') > 1
Changed lines 25-26 from:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2) > 1
to:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs('''distance1'''-'''distance2''') > 1
Changed lines 25-26 from:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<id2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2) > 1
to:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<ID2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2) > 1
Changed lines 25-26 from:
SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id='''ID1''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='node_1717') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2)>1
to:
->SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id = '''<ID1>''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='''<id2>''') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2) > 1
Added lines 23-26:
Jevgenij: some interesting observations here. It's easy to locate nodes whose routing table entries will be affected: the condition is abs(d1 - d2) > 1. The PostgreSQL query (looking more tricky than it actually is - a query on a <join of two queries> - I hope it can be made more elegant) for that is something like:
SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id='''ID1''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='node_1717') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2)>1
SELECT * FROM (SELECT * FROM (SELECT dest_node_id, distance as d1 FROM routing_table WHERE src_node_id='''ID1''') AS leftpart JOIN (SELECT dest_node_id,distance AS d2 from routing_table WHERE src_node_id='node_1717') AS rightpart USING (dest_node_id)) AS nodes_n_dists WHERE abs(d1-d2)>1
Changed lines 25-26 from:
Recompute from scratch. The problem is that usual methods require loading all routing tables into memory simultaneously.
to:
Recompute from scratch. The problem is that usual methods require loading all routing tables into memory simultaneously.
Jevgenij: Could you explain here: why does it require all the routing tables to be in memory? - I don't see serious reasons for that. Did you mean '''the whole adjacency list'''? Or, would you prefer to have no topology representation other than routing tables at all?
Jevgenij: Could you explain here: why does it require all the routing tables to be in memory? - I don't see serious reasons for that. Did you mean '''the whole adjacency list'''? Or, would you prefer to have no topology representation other than routing tables at all?
Changed lines 9-11 from:
# Clear routing tables of all ''dirty'' nodes, and initiatize them with neighbour nodes at a distance of 1, and all others at a distance of ''inf''.
to:
# Make a temporary copy of each ''dirty'' node's old routing table. Update each ''dirty'' node's routing table in the following fashion:
## For each new edge, set the distance to the new neighbour to 1.
## For each deleted edge, set the distance to the old neighbour to ''inf''.
## For each new edge, set the distance to the new neighbour to 1.
## For each deleted edge, set the distance to the old neighbour to ''inf''.
Changed lines 14-16 from:
## For every entry S[X] in S's routing table such that S[X] != ''inf'', set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## For every entry N[Y] such that S[Y] == ''inf'', set N[Y] = min(M[Y]) for all neighbours M of N.
## If N's routing table is changed, mark N as''seed''
## For every entry
## If N's routing table is changed, mark N as
to:
## Store a temporary copy of N's soon-to-be old routing table.
## (Propagating new edges.) For every entry S[X] in S's routing table, set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## (Propagating deleted edges.) For every entry N[Y] != ''inf'' such that S[Y] == ''inf'', look at S'[Y], the distance from S to Y in S's old routing table. If S'[Y] == N[Y] - 1, set N[Y] = min(M[Y]) for all neighbours M of N. (This could be an expensive step.)
## If N's routing table is changed, mark N as ''seed''. Otherwise, delete the temporary copy of N's old routing table.
# Delete the temporary copy of S's old routing table.
## (Propagating new edges.) For every entry S[X] in S's routing table, set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## (Propagating deleted edges.) For every entry N[Y] != ''inf'' such that S[Y] == ''inf'', look at S'[Y], the distance from S to Y in S's old routing table. If S'[Y] == N[Y] - 1, set N[Y] = min(M[Y]) for all neighbours M of N. (This could be an expensive step.)
## If N's routing table is changed, mark N as ''seed''. Otherwise, delete the temporary copy of N's old routing table.
# Delete the temporary copy of S's old routing table.
Added lines 21-22:
Does not require loading all tables into memory simultaneously.
Changed line 25 from:
Recompute from scratch. (May even be faster?)
to:
Recompute from scratch. The problem is that usual methods require loading all routing tables into memory simultaneously.
Changed lines 15-19 from:
# Repeat step 3 until no more ''seed'' nodes remain.
to:
# Repeat step 3 until no more ''seed'' nodes remain.
!!!! Alternative algorithm
Recompute from scratch. (May even be faster?)
!!!! Alternative algorithm
Recompute from scratch. (May even be faster?)
Changed line 9 from:
# Clear routing tables of all ''dirty'' nodes, and initiatize them with neighbour nodes at a distance of 1.
to:
# Clear routing tables of all ''dirty'' nodes, and initiatize them with neighbour nodes at a distance of 1, and all others at a distance of ''inf''.
Changed lines 12-13 from:
## For every entry S[X] in S's routing table such that S[X] != inf, set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## For every entry N[Y] such that S[Y] = inf, set N[Y] = min(M[Y]) for all neighbours M of N.
## For every entry N[Y] such that S[Y] = inf, set N[Y] = min(M[Y]) for all neighbours M of N.
to:
## For every entry S[X] in S's routing table such that S[X] != ''inf'', set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## For every entry N[Y] such that S[Y] == ''inf'', set N[Y] = min(M[Y]) for all neighbours M of N.
## For every entry N[Y] such that S[Y] == ''inf'', set N[Y] = min(M[Y]) for all neighbours M of N.
Added lines 1-15:
!!! Updating Routing Tables
(Proposed algorithm by Ryan)
* When new edges are added or deleted, mark incident nodes as ''dirty''.
'''Updating process:'''
# Clear routing tables of all ''dirty'' nodes, and initiatize them with neighbour nodes at a distance of 1.
# Mark each dirty node as ''seed''.
# For each ''seed'' node S, and each of its neighbours N, update N's routing table in the following fashion:
## For every entry S[X] in S's routing table such that S[X] != inf, set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## For every entry N[Y] such that S[Y] = inf, set N[Y] = min(M[Y]) for all neighbours M of N.
## If N's routing table is changed, mark N as ''seed''
# Repeat step 3 until no more ''seed'' nodes remain.
(Proposed algorithm by Ryan)
* When new edges are added or deleted, mark incident nodes as ''dirty''.
'''Updating process:'''
# Clear routing tables of all ''dirty'' nodes, and initiatize them with neighbour nodes at a distance of 1.
# Mark each dirty node as ''seed''.
# For each ''seed'' node S, and each of its neighbours N, update N's routing table in the following fashion:
## For every entry S[X] in S's routing table such that S[X] != inf, set the corresponding entry N[X] in N's routing table to N[X] = min(S[X] + 1, N[X])
## For every entry N[Y] such that S[Y] = inf, set N[Y] = min(M[Y]) for all neighbours M of N.
## If N's routing table is changed, mark N as ''seed''
# Repeat step 3 until no more ''seed'' nodes remain.