Protocol /
PathDiscovery
Protocol.PathDiscovery History
Hide minor edits - Show changes to output
Changed lines 82-83 from:
The @path_amount@@ allows the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. The @@path_amount@@ does not change as queries are propagated through the network, except where a query is forked into two or more directions, in which case the @@path_amount@@ is divided among the directions so that the sum of the @@path_amounts@@ of the forked directions is equal to the @@path_amount@@ of the incoming query.
to:
The @@path_amount@@ allows the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. The @@path_amount@@ does not change as queries are propagated through the network, except where a query is forked into two or more directions, in which case the @@path_amount@@ is divided among the directions so that the sum of the @@path_amounts@@ of the forked directions is equal to the @@path_amount@@ of the incoming query.
December 05, 2006, at 04:37 AM
by - fixed last one
Deleted lines 0-53:
* improve Goal & Method section - be more descriptive so the message fields make more sense and can have shorter descriptions
* once target is reached, queries must be returned so that intermediaries learn about the final path IDs and amounts
* can be used to give precise amounts to forward queries!
* recipient must inform payer of queries received and their amounts
* screws up path amount/units because payer may send query with exact amount in path units, but it reaches recipient as another amount!
* maybe exclude path_amount & path_units from forward queries?
* once payer receives return values for amounts in account units, it can decide to search further if necessary
* routing onion
* forking
* routing queries with no target or where the target is an intermediary
* when forking, append a new entry to a path-ID list, so that a query's path-ID forking history is self-contained
* avoids need for list of aliases to avoid looping!
* avoids need for nodes to recall which path ID forked from which path ID -- only need to store which neighbour sent query for which path ID
* when returning, can remove path-ID layers that you created, and return back original path ID with aggregate fork amounts, etc.
* once payer (or recipient?) receives queries totalling the payment amount from a single search, can immediately begin promise phase without waiting for queries to fully return! (Since the only thing preventing this was intermediaries not knowing what the final path IDs referred to in their context.)
* limiting query propagation using max-fee field (backward) or path_amount (forward)
-----------------------
Deleted lines 2-3:
Deleted line 3:
Deleted lines 5-6:
Deleted lines 7-8:
Deleted lines 9-10:
Deleted lines 11-12:
Deleted lines 13-14:
Deleted lines 15-16:
Deleted lines 17-18:
Deleted lines 19-20:
Deleted line 20:
Deleted lines 22-23:
Deleted lines 24-25:
Deleted lines 26-27:
Deleted lines 28-29:
Deleted line 29:
Deleted lines 31-32:
Deleted lines 33-34:
Deleted line 34:
Deleted line 35:
Deleted line 36:
Deleted line 37:
Deleted line 38:
Deleted line 39:
Deleted line 40:
Deleted line 41:
Deleted line 42:
Deleted line 43:
Deleted line 44:
Deleted line 45:
Deleted line 46:
Deleted line 47:
Deleted line 48:
Deleted line 49:
Deleted line 50:
Deleted lines 52-53:
Deleted line 53:
Deleted line 54:
Deleted line 55:
Deleted line 56:
Deleted line 57:
Deleted line 58:
Deleted line 59:
Deleted line 60:
Deleted line 61:
Deleted line 62:
Deleted line 63:
Deleted line 64:
Deleted line 65:
Deleted line 66:
Deleted line 67:
Deleted line 68:
Deleted line 69:
Deleted line 70:
Deleted line 71:
Deleted line 72:
Deleted line 73:
Deleted line 74:
Deleted line 75:
Deleted lines 77-78:
Deleted lines 79-80:
Deleted lines 81-82:
Deleted lines 83-84:
Deleted lines 85-86:
Deleted lines 87-88:
Deleted lines 89-90:
Deleted lines 91-92:
Deleted lines 93-94:
Deleted lines 95-96:
Deleted lines 97-98:
Deleted lines 99-100:
Deleted lines 101-102:
Deleted line 102:
Deleted line 103:
Deleted line 104:
Deleted line 105:
Deleted line 106:
Deleted lines 108-109:
Deleted lines 110-111:
Deleted lines 112-113:
Deleted line 113:
Deleted lines 115-116:
Deleted lines 117-118:
Deleted line 118:
Deleted lines 120-121:
Deleted lines 122-123:
Deleted line 123:
Deleted line 124:
Deleted lines 126-127:
Deleted lines 128-129:
Deleted line 129:
Deleted lines 131-132:
December 05, 2006, at 04:28 AM
by - added method description & partial JSON
Added lines 1-54:
*** To do:
* improve Goal & Method section - be more descriptive so the message fields make more sense and can have shorter descriptions
* once target is reached, queries must be returned so that intermediaries learn about the final path IDs and amounts
* can be used to give precise amounts to forward queries!
* recipient must inform payer of queries received and their amounts
* screws up path amount/units because payer may send query with exact amount in path units, but it reaches recipient as another amount!
* maybe exclude path_amount & path_units from forward queries?
* once payer receives return values for amounts in account units, it can decide to search further if necessary
* routing onion
* forking
* routing queries with no target or where the target is an intermediary
* when forking, append a new entry to a path-ID list, so that a query's path-ID forking history is self-contained
* avoids need for list of aliases to avoid looping!
* avoids need for nodes to recall which path ID forked from which path ID -- only need to store which neighbour sent query for which path ID
* when returning, can remove path-ID layers that you created, and return back original path ID with aggregate fork amounts, etc.
* once payer (or recipient?) receives queries totalling the payment amount from a single search, can immediately begin promise phase without waiting for queries to fully return! (Since the only thing preventing this was intermediaries not knowing what the final path IDs referred to in their context.)
* limiting query propagation using max-fee field (backward) or path_amount (forward)
-----------------------
* improve Goal & Method section - be more descriptive so the message fields make more sense and can have shorter descriptions
* once target is reached, queries must be returned so that intermediaries learn about the final path IDs and amounts
* can be used to give precise amounts to forward queries!
* recipient must inform payer of queries received and their amounts
* screws up path amount/units because payer may send query with exact amount in path units, but it reaches recipient as another amount!
* maybe exclude path_amount & path_units from forward queries?
* once payer receives return values for amounts in account units, it can decide to search further if necessary
* routing onion
* forking
* routing queries with no target or where the target is an intermediary
* when forking, append a new entry to a path-ID list, so that a query's path-ID forking history is self-contained
* avoids need for list of aliases to avoid looping!
* avoids need for nodes to recall which path ID forked from which path ID -- only need to store which neighbour sent query for which path ID
* when returning, can remove path-ID layers that you created, and return back original path ID with aggregate fork amounts, etc.
* once payer (or recipient?) receives queries totalling the payment amount from a single search, can immediately begin promise phase without waiting for queries to fully return! (Since the only thing preventing this was intermediaries not knowing what the final path IDs referred to in their context.)
* limiting query propagation using max-fee field (backward) or path_amount (forward)
-----------------------
Changed lines 57-60 from:
The goal is to find a set of paths from payer to recipient that together have enough available credit to complete the payment. The fastest method to discover these paths would be to flood the network with queries in a circle outward from payer and recipient, but this approach would not scale. A more scalable approach is a targetted depth-first search, guided by a routing system (see [[Protocol/Routing]]), with an intelligent approach to forking where there is insufficient credit in the optimal direction. The result of each search is a set of paths totalling the precise amount needed for the payment.
to:
[[#method-description]]
'''Method Description'''
The goal of Ripple path discovery is to find a set of paths from payer to recipient that together have enough available credit to complete the payment. The fastest method to discover these paths would be to flood the network with queries along every possible path, but this approach would not scale. The more scalable approach adopted is a targetted depth-first search, guided by a routing system (see [[Protocol/Routing]]), with an intelligent approach to parallel forking where there is insufficient credit along a unique shortest path. The result of each search is a set of paths totalling the precise amount needed for the payment.
A search begins by either the payer or recipient sending out one or more queries asking their neighbour(s) to find a set of paths for transferring up to a certain amount to/from the other transaction endpoint. The sum of all the query amounts is equal to the payment amount (in the case of the recipient) or the payment amount plus estimated fees (in the case of the payer). Each neighbour receiving a query then adds/deducts fees to the amount (depending on the direction of the query), and passes it along to one or more of its neighbours, according to the available credit on their accounts and distance to the target as determined by the routing scheme.
Queries that have forked in multiple directions do not recombine if they end up back on the same path later: for simplicity, they remain logically split into separate amounts with different path IDs sent in separate messages. Therefore each query represents a unique path back to its origin. Queries from the same search may not reserve the same credit since when those paths are used, the amounts will be added together.
When a query reaches its target or a dead end, the query recipient returns the amount of available credit discovered along the unique path defined by that query. When a node receives a query return value, it compares it to the requested amount on the query it sent. If the return value is less than the amount requested, and there is account credit left unrequested for this particular search, it forks a new query to search for the remainder. Once all queries forked from a single incoming query have returned, the their total available amount is returned as the result for the incoming query.
To avoid loops, each node records the IDs of the queries it has seen, and refuses to accept them a second time. When a query forks in multiple directions, each fork has a different new ID appended to the original ID so the IDs of all previous queries along each path can be read as a prefix of the current ID.
Added lines 87-88:
Added lines 91-112:
[[#the-routing-onion]]
'''The Routing Onion'''
Whenever path discovery messages are propagating from recipient to payer, be it for query messages originating from the recipient, or return values for queries originating at the payer, a sort of routing onion may be optionally constructed by each node in the path adding a layer of data and encryption to an onion-routing blob. That blob is to be included in promise messages during the next phase of payment ([[Protocol/PaymentTransaction]]), and decrypted layer-by-layer by the node that encrypted it in the first place.
In this path-discovery scenario, nodes may put whatever data they wish into the blob. For example, a node may wish to leave itself directions on where the path goes next, and what exchange rates it is going to use. The reasons for incorporating a routing onion into the promise messages is to allow the transaction phase of the payment to be theoretically independent of the path-discovery phase, so that other path discovery methods might be used that do not require communicating with every single intermediary directly to inform them ahead of time how to route promise messages for a given payment. Since the standard method of path-discovery outlined here requires the intermediaries to construct the paths themselves, meaning they already know how to route promise messages for the payment, the routing onion is not strictly required, but it may be used to store data somewhere other than in the node's local persistent storage. If an intermediary does not wish to use this facility, it can simply neglect to add a layer to the routing-onion blob.
For more information on onion routing during the transaction phase, see [[Onion Routing -> Protocol/PaymentTransaction#onion-routing]].
[[#path-queries-and-responses]]
Changed lines 115-116 from:
The payer and recipient send out @@path-query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> Protocol/Routing]]. A path-query message consists of:
to:
The payer and recipient send out @@path_query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> Protocol/Routing]]. A @@path_query@@ message consists of:
Added line 122:
Added line 124:
Added line 126:
Changed lines 128-129 from:
* path units (optional)
* credit available along this path so far, in transaction units
* credit available along this path so far, in transaction units
to:
* path units (backward direction only, optional)
* credit available for paying the recipient along this path so far, in path units (backward direction only)
Added line 134:
Added line 136:
Added line 138:
Changed lines 140-142 from:
* promise penalty deadline (forward: maximum offered (optional); backward: minimum required), in connection time
* promise daily penalty rate (forward: maximum offered(optional); backward: minimum required)
* promise final deadline (forward: maximum offered(optional); backward: minimum required), in connection time
* promise daily penalty rate (forward: maximum offered
* promise final deadline (forward: maximum offered
to:
* promise penalty deadline (forward: maximum offered; backward: minimum required), in connection time
* promise daily penalty rate (forward: maximum offered; backward: minimum required)
* promise final deadline (forward: maximum offered; backward: minimum required), in connection time
Changed lines 148-150 from:
* a list containing aliases for each of the locations visited on this paths
to:
* a list containing aliases for each of the locations visited on this path
Changed lines 152-153 from:
* the accumulated fee limit for this query (as a percentage of the query amount)
to:
* the total accumulated fee limit for this query (as a percentage of the query amount -- backward only)
* routing-onion blob (backward direction only)
Added line 160:
Added line 162:
Added line 164:
Added line 166:
Changed lines 168-174 from:
"path_id": "781e22d3-8d91-46ef-8002-8a6b1e0b4bc2",
to:
"path_id": [
"781e22d3-8d91-46ef-8002-8a6b1e0b4bc2"
],
Changed lines 176-177 from:
"path_units": "urn:ripple:units:CAD",
"path_amount":100.00,
"path_amount":
to:
"path_units": "urn:ripple:units:USD",
"path_amount": 89.9326,
Changed lines 182-184 from:
"account_amount": 76.8244,
to:
"account_amount": 100.00,
Added line 186:
Added line 188:
Added line 190:
Added line 192:
Added line 194:
Changed lines 196-198 from:
"c40b2e7ec38e53482a02e9ad7c650946ccdfe6d3",
]
to:
Changed lines 198-204 from:
"fee_limit": 0.01
to:
"onion": "[base64-encoded encrypted onion blob]"
}
}
Changed lines 207-220 from:
Final payment will be made using the paths found by queries within a single swarm. Therefore, queries within a single swarm may not reserve the same credit. Queries within different swarms, but with the same payment ID, may reserve the same credit. Queries with different payment IDs may not reserve the same credit. When a query forks in two separate directions, it splits into two different paths, but each maintain the same swarm ID. To avoid overlap, payer-initiated (forward) queries should use even-numbered swarm IDs, and recipient-initiated (backward) queries odd-numbered swarm IDs. See [[Query Routing -> #query-routing]].
The payer sends out "forward" queriesthe recipient sends out "backward" queries, refering to the direction the payment will ultimately take. If fees are permitted, the backward queries are more precise: the payment amount is generally interpreted as the amount to be received by the recipient (Paypal notwithstanding), and the backward queries begin by specifying this amount and accumulate fees as they propagate towards the payer. Forward queries that permit fees must begin with an estimate of the payment amount including intermediary fees, which would generally be too high and result in too much credit being reserved. However, forward queries play an important role as signposts towards the payer for the more-precise backward queries.
The transaction units allow the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. Intermediaries that do not recognize the transaction units cannot enforce overall fee limits on queries.
The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path, if there is more than one. The amount in account units is the amount that is to be reserved on that account for this query's payment path. It also defines a conversion rate between account units and transaction units that can be used to calculate whether or not the full query amount can be passed on to a single neighbour, and what proportion to pass on to various neighbours otherwise. This conversion rate is also used in subsequent payment messages.
The target location is used by each intermediary to route the query. Generally the target for forward queries is the recipient's location, and the target for backward queries is the payer's location, but this is not strictly required. Either payer or recipient may direct the other to route their queries to a different target location, and then ensure that the node with this target location receives a query from the opposite direction to point back to the correct target.
The credit guarantee expiry time gives a deadline for the next phase of the payment to occur. If this time limit is reached, the credit held for this path will be released and made available to other payments. Each intermediary should subtract from this time before passing it on to give themselves a small buffer in which to process messages from the next payment phase. The time is given in the connection time between each of the intermediaries, so each one must convert if the time on the incoming account is not in sync with the time on the outgoing account. See [[Connection Time -> #connection-time]].
The promise penalty deadline, penalty rate, and final deadline refer to fields in the @@promise@@ message in the next payment phase. In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds. The times are again given in connection time, and the penalty rate is a daily percentage.
The payer sends out "forward" queries
The transaction units allow the payer and
The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path
The target location is used by each intermediary to route the query. Generally
The credit guarantee expiry time gives a deadline for the next phase of the payment to occur. If this time limit is reached,
The promise penalty deadline, penalty rate, and final deadline refer to fields in the @@promise@@ message in the next payment phase. In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds. The times are again given in connection time, and the penalty rate
to:
Final payment will be made using the paths found by queries within a single search (i.e., having the same search ID). Therefore, queries within a single search may not reserve the same credit. Queries within different searches, but with the same payment ID, may reserve the same credit. Queries with different payment IDs may not reserve the same credit. When a query forks in two or more separate directions, it splits into different paths with different IDs, but each maintain the same swarm ID. One forked path maintains the original path ID. To avoid overlap, payer-initiated (forward) queries should use even-numbered swarm IDs, and recipient-initiated (backward) queries odd-numbered swarm IDs. (Technically, this means that the @@direction@@ field is redundant.) See [[Query Routing -> #/Protocol/Routing]].
The payer sends out @@fwd@@ (forward) queries, and the recipient sends out @@bwd@@ (backward) queries, refering to the direction the payment will ultimately take. The backward queries are more precise: the @@path_amount@@ is the amount to be received by the recipient, and the backward queries can begin with this exact amount converted to @@account_amount@@s which will have fees added to them. The forward queries cannot know how much of their initial amount will reach the recipient and how much will be deducted as fees, so they cannot know precisely the @@path_amount@@ that will reach the recipient. Therefore the @@path_amount@@ on forward-direction queries is interpreted as a lower bound. Forward queries should begin with @@account_amount@@s that add up to the maximum the payer is willing to spend, and then the recipient will convert the received @@account_amount@@s to exact @@path_amount@@s in the return values.
The @path_amount@@ allows the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. The @@path_amount@@ does not change as queries are propagated through the network, except where a query is forked into two or more directions, in which case the @@path_amount@@ is divided among the directions so that the sum of the @@path_amounts@@ of the forked directions is equal to the @@path_amount@@ of the incoming query.
The @@path_units@@ used to measure the @@path_amount@@ may or may not be divulged to intermediaries. The only purpose of allowing intermediaries to know the @@path_units@@ is so they may gauge whether the overall fee limit has been surpassed, and abort the query. When the account units at a particular hop are the same as the @@path_units@@, the fees charged along the path so far may be calculated precisely, but if they are different, the total fees can only be estimated using the intermediary's own exchange rate between account units and @@path_units@@. If an intermediary does not recognize the @@path_units@@, or cannot convert them into its account units at that particular hop, then that intermediary simply does not have the opportunity to check whether the overall fee limit has been surpassed, and should route the query regardless.
The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path, if there is more than one. The amount in account units is the amount that is to be reserved on that account for this query's payment path. It also defines a conversion rate between account units and path units that can be used to calculate whether or not the full path amount can be passed on to a single neighbour, and what proportion to pass on to various neighbours otherwise. This conversion rate is also used in subsequent payment messages. (*** Routing onion to store this ***)
The target location is used by each intermediary to route the query. Generally the target for forward queries is the recipient's location, and the target for backward queries is the payer's location, but this is not strictly required. Either payer or recipient may direct the other to route their queries to a different target location, and then ensure that the node with this target location receives a query from the opposite direction to point back to the correct target. For more on how nodes route queries, see [[Protocol/Routing]].
The @@guarantee_expiry@@ gives a deadline for the next phase of the payment to occur. If this time limit is reached, the credit held for this path will be released and made available to other payments. Each intermediary should subtract from this time before passing it on to give themselves a small buffer in which to process messages from the next payment phase. The time is given in the connection time between each of the intermediaries, so each one must convert if the time on the incoming account is not in sync with the time on the outgoing account. See [[Connection Time -> #connection-time]]. If there is to be no guarantee of available credit for this path, then @@guarantee_expiry@@ should be omitted.
The @@promise_penalty_deadline@@, @@promise_penalty_rate@@, and @@promise_final_deadline@@ refer to fields in the @@promise@@ message in the next payment phase. In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds. The times are again given in connection time, and the penalty rate is a daily proportion of the total amount.
Changed lines 243-244 from:
The bloom filter containing aliases of the locations already visited is to prevent loops -- no location should occur twice in the same path. Nodes can use any alias they want as long as it is unique among potential intermediaries with high probability and they remember it to compare against incoming queries with the same payment and swarm IDs.
to:
The list containing aliases of the locations already visited is to prevent loops -- no location should occur twice in the same path. Nodes can use any alias they want as long as it is unique among potential intermediaries with high probability and they remember it to compare against incoming queries with the same payment and swarm IDs.
Added lines 251-252:
Added lines 255-256:
Added line 258:
Added line 260:
Added line 262:
Added line 264:
Added line 266:
Added lines 269-270:
Added lines 273-274:
Added lines 277-278:
Added line 280:
Added lines 283-284:
Added lines 287-288:
Added line 290:
Added lines 293-294:
Added lines 297-298:
Added line 300:
Added line 302:
Added lines 305-306:
Added lines 309-316:
[[#rendezvous-intermediaries]]
'''Rendezvous Intermediaries'''
Added lines 3-10:
'''Goal & Method'''
The goal is to find a set of paths from payer to recipient that together have enough available credit to complete the payment. The fastest method to discover these paths would be to flood the network with queries in a circle outward from payer and recipient, but this approach would not scale. A more scalable approach is a targetted depth-first search, guided by a routing system (see [[Protocol/Routing]]), with an intelligent approach to forking where there is insufficient credit in the optimal direction. The result of each search is a set of paths totalling the precise amount needed for the payment.
Both payer and recipient may conduct multiple simultaneous searches in order to maximize the chances of finding a useable path set in a reasonable amount of time. Finding multiple path sets also allows the payer to choose the one with the lowest fees.
As each hop, the potential payment intermediary may guarantee the availability of credit for that path for a certain amount of time. If the next phase of payment ([[transaction phase -> Protocol/PaymentTransaction]]) has not happened by that time, then the credit guarantee expires. This does not mean that the transaction will fail if attempted, only that its success has not been assured by each intermediary. Since only one search will ultimately be chosen to perform the payment, the same credit may be used to guarantee all searches with the same payment ID.
The goal is to find a set of paths from payer to recipient that together have enough available credit to complete the payment. The fastest method to discover these paths would be to flood the network with queries in a circle outward from payer and recipient, but this approach would not scale. A more scalable approach is a targetted depth-first search, guided by a routing system (see [[Protocol/Routing]]), with an intelligent approach to forking where there is insufficient credit in the optimal direction. The result of each search is a set of paths totalling the precise amount needed for the payment.
Both payer and recipient may conduct multiple simultaneous searches in order to maximize the chances of finding a useable path set in a reasonable amount of time. Finding multiple path sets also allows the payer to choose the one with the lowest fees.
As each hop, the potential payment intermediary may guarantee the availability of credit for that path for a certain amount of time. If the next phase of payment ([[transaction phase -> Protocol/PaymentTransaction]]) has not happened by that time, then the credit guarantee expires. This does not mean that the transaction will fail if attempted, only that its success has not been assured by each intermediary. Since only one search will ultimately be chosen to perform the payment, the same credit may be used to guarantee all searches with the same payment ID.
Changed line 16 from:
* swarm ID
to:
* search ID
Changed line 19 from:
* transaction units
to:
* path units (optional)
Changed lines 24-29 from:
* the time this available credit guarantee will expire, measured in connection time between sender and recipient
* promise penalty deadline (forward: maximum offered; backward: minimum required)
* promise daily penalty rate(forward: maximum offered; backward: minimum required)
* promise final deadline (forward: maximum offered; backward: minimum required)
*the remaining hop limit for the query
* a bloom filter containing aliases for each of the locations visited on this paths
* promise daily penalty rate
*
* a bloom filter
to:
* the time this available credit guarantee will expire, measured in connection time between sender and recipient (optional)
* promise penalty deadline (forward: maximum offered (optional); backward: minimum required), in connection time
* promise daily penalty rate (forward: maximum offered (optional); backward: minimum required)
* promise final deadline (forward: maximum offered (optional); backward: minimum required), in connection time
* the deadline for the query to reach its goal, in connection time
* a list containing aliases for each of the locations visited on this paths
* promise penalty deadline (forward: maximum offered (optional); backward: minimum required), in connection time
* promise daily penalty rate (forward: maximum offered (optional); backward: minimum required)
* promise final deadline (forward: maximum offered (optional); backward: minimum required), in connection time
* the deadline for the query to reach its goal, in connection time
* a list containing aliases for each of the locations visited on this paths
Added lines 33-56:
[@
{
"path_query": {
"payment_id": "393ff635-de8b-486f-b650-c4f1b151172c",
"search_id": 0,
"path_id": "781e22d3-8d91-46ef-8002-8a6b1e0b4bc2",
"direction": "fwd",
"path_units": "urn:ripple:units:CAD",
"path_amount": 100.00,
"account_id": "c074162d-d3df-4dcc-9150-3aa634adf4c8",
"account_amount": 76.8244,
"target": "7136976c-251d-4be4-b6e2-74baf4b4a53c",
"guarantee_expiry": "2006-11-25 12:55:49.504000",
"promise_penalty_deadline": "2006-11-25 13:55:49.504000",
"promise_penalty_rate": 0.5,
"promise_final_deadline": "2006-11-27 12:55:49.504000",
"query_expiry": "2006-11-25 12:45:49.504000",
"visited_nodes": [
"c40b2e7ec38e53482a02e9ad7c650946ccdfe6d3",
]
"per_hop_fee_limit": 0.001,
"fee_limit": 0.01
@]
{
"path_query": {
"payment_id": "393ff635-de8b-486f-b650-c4f1b151172c",
"search_id": 0,
"path_id": "781e22d3-8d91-46ef-8002-8a6b1e0b4bc2",
"direction": "fwd",
"path_units": "urn:ripple:units:CAD",
"path_amount": 100.00,
"account_id": "c074162d-d3df-4dcc-9150-3aa634adf4c8",
"account_amount": 76.8244,
"target": "7136976c-251d-4be4-b6e2-74baf4b4a53c",
"guarantee_expiry": "2006-11-25 12:55:49.504000",
"promise_penalty_deadline": "2006-11-25 13:55:49.504000",
"promise_penalty_rate": 0.5,
"promise_final_deadline": "2006-11-27 12:55:49.504000",
"query_expiry": "2006-11-25 12:45:49.504000",
"visited_nodes": [
"c40b2e7ec38e53482a02e9ad7c650946ccdfe6d3",
]
"per_hop_fee_limit": 0.001,
"fee_limit": 0.01
@]
Changed lines 5-6 from:
The payer and recipient send out @@path-query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> #query-routing]]. A path-query message consists of:
to:
The payer and recipient send out @@path-query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> Protocol/Routing]]. A path-query message consists of:
Changed lines 54-55 from:
These path-responses are propagated back to the query originator in the following fashion: When an intermediary receives a path-response, it checks whether the available amounts equal the amount on the query to which it is a response. If the sum of the path amounts is less than the original query, it sends out new secondary queries for the remaining amounts, if possible. (Multiple queries are permitted on the same accounts, but each must have a different path ID as described in [[Query Routing -> #query-routing]].) Unused hop limit may be used for this purpose. Credit amounts held for the outgoing query should be reduced to reflect the amounts in the path-response.
to:
These path-responses are propagated back to the query originator in the following fashion: When an intermediary receives a path-response, it checks whether the available amounts equal the amount on the query to which it is a response. If the sum of the path amounts is less than the original query, it sends out new secondary queries for the remaining amounts, if possible. (Multiple queries are permitted on the same accounts, but each must have a different path ID as described in [[Query Routing -> Protocol/Routing]].) Unused hop limit may be used for this purpose. Credit amounts held for the outgoing query should be reduced to reflect the amounts in the path-response.
Added lines 63-73:
[[#cancelling-paths]]
'''Cancelling Unneeded Paths'''
The payer and recipient should send a @@path-cancel@@ down each path they know they will not need:
* payment ID
* swarm ID
* path ID
When passing a @@path-cancel@@ before having returned a @@path-response@@, intermediaries should fork the @@path-cancel@@ just as they did the @@path-query@@ with the same identifiers.
'''Cancelling Unneeded Paths'''
The payer and recipient should send a @@path-cancel@@ down each path they know they will not need:
* payment ID
* swarm ID
* path ID
When passing a @@path-cancel@@ before having returned a @@path-response@@, intermediaries should fork the @@path-cancel@@ just as they did the @@path-query@@ with the same identifiers.
Deleted lines 62-86:
'''Query Routing'''
Ripple uses the Metropolis-Hastings algorithm for routing, as described in Clarke and Sandberg's presentation [[Routing in the Dark -> http://www.math.chalmers.se/~ossa/defcon13/vegas1_print.pdf]] (PDF).
Each node partitions its accounts into separate routing classes such that obligations are convertible between any accounts within a class (in other words, an incoming payment on any account might be routed out along any other account in its routing class). Each routing class is then given a location, which is a decimal number between 0 and 1 representing a position on the boundary of a circle. The distance between any two locations is defined as the distance along the boundary of the circle between their locations:
[@
d(x, y) = min(abs(x - y), 1 - abs(x - y))
@]
Each node regularly swaps locations with other randomly-chosen nodes in a systematic way to minimize the product of the distances to its neighbours. Thus a node's location comes to be close in a certain sense to the location of its neighbours. Path-finding messages can then be routed by passing them to those neighbours with locations closest to the target location.
See below for a [[specification of location-swapping -> #location-swapping]].
A @@path-query@@ is routed first in directions path-queries in the opposite direction were received for the same payment ID. From among these directions, the neighbour with the location closest to the query's target location is chosen first. If there is not enough credit, as determined by available credit specified on the opposing query received from that direction, to fulfill the entire query, new queries with new path IDs are forked off in subsequent directions which have received opposing queries. Path IDs must be unique within a swarm. Once directions having received opposing path-queries are used up, all the accounts in the routing class may be considered on the basis of distance to the target location, using available credit as determined by the account balances and limits.
Remember that credit amounts reported as available on queries must be held for that path and made unavailable for other payments until they time out. Only other swarms from the same payment may access amounts held.
At all times, per-hop fee limits must be obeyed. If a node would charge more than the per-hop fee limit, it must respond as though it were a dead end. An account with a minimum fee on through payments higher than the per-hop fee limit on the query should therefore be ignored for the purposes of routing that query.
Note that with Metropolis-Hastings routing there is no requirement for nodes to report their own exact location as the routing target of messages from transaction partners. They may report slightly inexact locations for privacy reasons, or the location of a neighbour, or an average of a group of neighbours to route the message through them. This requires informing those neighbours ahead of time that the message is coming, by sending a @@path-query@@.
The performance of path-finding will be critical to the success of Ripple, and therefore the protocol should be as flexible as possible in terms of its ability to incorporate new and diverse methods of path-finding.
Added lines 1-88:
[[Protocol/Path Discovery Work Page]]
'''Path Queries & Responses'''
The payer and recipient send out @@path-query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> #query-routing]]. A path-query message consists of:
* payment ID
* swarm ID
* path ID
* direction of query, forward or backward, depending on whether query originates at payer or recipient
* transaction units
* credit available along this path so far, in transaction units
* ID for the account between message sender and recipient that will form part of the path
* credit available along path so far, in account units for that account (defines a conversion rate from transaction units to account units)
* the target's routing information
* the time this available credit guarantee will expire, measured in connection time between sender and recipient
* promise penalty deadline (forward: maximum offered; backward: minimum required)
* promise daily penalty rate (forward: maximum offered; backward: minimum required)
* promise final deadline (forward: maximum offered; backward: minimum required)
* the remaining hop limit for the query
* a bloom filter containing aliases for each of the locations visited on this paths
* the per-hop fee limit for this query (as a percentage of the query amount)
* the accumulated fee limit for this query (as a percentage of the query amount)
Final payment will be made using the paths found by queries within a single swarm. Therefore, queries within a single swarm may not reserve the same credit. Queries within different swarms, but with the same payment ID, may reserve the same credit. Queries with different payment IDs may not reserve the same credit. When a query forks in two separate directions, it splits into two different paths, but each maintain the same swarm ID. To avoid overlap, payer-initiated (forward) queries should use even-numbered swarm IDs, and recipient-initiated (backward) queries odd-numbered swarm IDs. See [[Query Routing -> #query-routing]].
The payer sends out "forward" queries, and the recipient sends out "backward" queries, refering to the direction the payment will ultimately take. If fees are permitted, the backward queries are more precise: the payment amount is generally interpreted as the amount to be received by the recipient (Paypal notwithstanding), and the backward queries begin by specifying this amount and accumulate fees as they propagate towards the payer. Forward queries that permit fees must begin with an estimate of the payment amount including intermediary fees, which would generally be too high and result in too much credit being reserved. However, forward queries play an important role as signposts towards the payer for the more-precise backward queries.
The transaction units allow the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. Intermediaries that do not recognize the transaction units cannot enforce overall fee limits on queries.
The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path, if there is more than one. The amount in account units is the amount that is to be reserved on that account for this query's payment path. It also defines a conversion rate between account units and transaction units that can be used to calculate whether or not the full query amount can be passed on to a single neighbour, and what proportion to pass on to various neighbours otherwise. This conversion rate is also used in subsequent payment messages.
The target location is used by each intermediary to route the query. Generally the target for forward queries is the recipient's location, and the target for backward queries is the payer's location, but this is not strictly required. Either payer or recipient may direct the other to route their queries to a different target location, and then ensure that the node with this target location receives a query from the opposite direction to point back to the correct target.
The credit guarantee expiry time gives a deadline for the next phase of the payment to occur. If this time limit is reached, the credit held for this path will be released and made available to other payments. Each intermediary should subtract from this time before passing it on to give themselves a small buffer in which to process messages from the next payment phase. The time is given in the connection time between each of the intermediaries, so each one must convert if the time on the incoming account is not in sync with the time on the outgoing account. See [[Connection Time -> #connection-time]].
The promise penalty deadline, penalty rate, and final deadline refer to fields in the @@promise@@ message in the next payment phase. In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds. The times are again given in connection time, and the penalty rate is a daily percentage.
The hop limit is the maximum number of hops for all queries spawned from the one received, including forks. When a query forks in several different directions, the hop limit must be divided up amongst them.
The bloom filter containing aliases of the locations already visited is to prevent loops -- no location should occur twice in the same path. Nodes can use any alias they want as long as it is unique among potential intermediaries with high probability and they remember it to compare against incoming queries with the same payment and swarm IDs.
The per-hop fee limit is a limit on the percentage fee charged per hop in the path. The accumulated fee limit is an overall limit to the fees on this query. This can only be enforced if intermediaries recognize the transaction units.
When the query reaches the opposing payment endpoint, or creates a loop or otherwise hits a dead end, the node receiving the query message returns a @@path-response@@ message:
* payment ID
* swarm ID
* list of path IDs with corresponding available amounts in transaction units
* path ID of query to which this message is a response
* expiry time for these paths
* unused hop limit
These path-responses are propagated back to the query originator in the following fashion: When an intermediary receives a path-response, it checks whether the available amounts equal the amount on the query to which it is a response. If the sum of the path amounts is less than the original query, it sends out new secondary queries for the remaining amounts, if possible. (Multiple queries are permitted on the same accounts, but each must have a different path ID as described in [[Query Routing -> #query-routing]].) Unused hop limit may be used for this purpose. Credit amounts held for the outgoing query should be reduced to reflect the amounts in the path-response.
If the path amounts equal the original query amount, if there is no unused hop limit, or if there are no directions remaining to query, it waits until it has received responses to all its queries, and then packages the nonzero paths together into a new query response. The new expiry time is the soonest expiry time of any of the path-responses. The unused hop limit is the total unused hop limit from all the responses that hasn't been used in a secondary query fork.
[[#fees]]
'''Fees'''
Fees charged may be integrated as a percentage into conversion rates between units. There is no provision for flat fees at the moment. Minimum fees for any payment through an account are shared with account partners as part of the account data.
[[#query-routing]]
'''Query Routing'''
Ripple uses the Metropolis-Hastings algorithm for routing, as described in Clarke and Sandberg's presentation [[Routing in the Dark -> http://www.math.chalmers.se/~ossa/defcon13/vegas1_print.pdf]] (PDF).
Each node partitions its accounts into separate routing classes such that obligations are convertible between any accounts within a class (in other words, an incoming payment on any account might be routed out along any other account in its routing class). Each routing class is then given a location, which is a decimal number between 0 and 1 representing a position on the boundary of a circle. The distance between any two locations is defined as the distance along the boundary of the circle between their locations:
[@
d(x, y) = min(abs(x - y), 1 - abs(x - y))
@]
Each node regularly swaps locations with other randomly-chosen nodes in a systematic way to minimize the product of the distances to its neighbours. Thus a node's location comes to be close in a certain sense to the location of its neighbours. Path-finding messages can then be routed by passing them to those neighbours with locations closest to the target location.
See below for a [[specification of location-swapping -> #location-swapping]].
A @@path-query@@ is routed first in directions path-queries in the opposite direction were received for the same payment ID. From among these directions, the neighbour with the location closest to the query's target location is chosen first. If there is not enough credit, as determined by available credit specified on the opposing query received from that direction, to fulfill the entire query, new queries with new path IDs are forked off in subsequent directions which have received opposing queries. Path IDs must be unique within a swarm. Once directions having received opposing path-queries are used up, all the accounts in the routing class may be considered on the basis of distance to the target location, using available credit as determined by the account balances and limits.
Remember that credit amounts reported as available on queries must be held for that path and made unavailable for other payments until they time out. Only other swarms from the same payment may access amounts held.
At all times, per-hop fee limits must be obeyed. If a node would charge more than the per-hop fee limit, it must respond as though it were a dead end. An account with a minimum fee on through payments higher than the per-hop fee limit on the query should therefore be ignored for the purposes of routing that query.
Note that with Metropolis-Hastings routing there is no requirement for nodes to report their own exact location as the routing target of messages from transaction partners. They may report slightly inexact locations for privacy reasons, or the location of a neighbour, or an average of a group of neighbours to route the message through them. This requires informing those neighbours ahead of time that the message is coming, by sending a @@path-query@@.
The performance of path-finding will be critical to the success of Ripple, and therefore the protocol should be as flexible as possible in terms of its ability to incorporate new and diverse methods of path-finding.
[[Protocol/Path Discovery Work Page]]
'''Path Queries & Responses'''
The payer and recipient send out @@path-query@@ messages to one or more account partners, which they in turn pass on to one or more of their partners as described in [[Query Routing -> #query-routing]]. A path-query message consists of:
* payment ID
* swarm ID
* path ID
* direction of query, forward or backward, depending on whether query originates at payer or recipient
* transaction units
* credit available along this path so far, in transaction units
* ID for the account between message sender and recipient that will form part of the path
* credit available along path so far, in account units for that account (defines a conversion rate from transaction units to account units)
* the target's routing information
* the time this available credit guarantee will expire, measured in connection time between sender and recipient
* promise penalty deadline (forward: maximum offered; backward: minimum required)
* promise daily penalty rate (forward: maximum offered; backward: minimum required)
* promise final deadline (forward: maximum offered; backward: minimum required)
* the remaining hop limit for the query
* a bloom filter containing aliases for each of the locations visited on this paths
* the per-hop fee limit for this query (as a percentage of the query amount)
* the accumulated fee limit for this query (as a percentage of the query amount)
Final payment will be made using the paths found by queries within a single swarm. Therefore, queries within a single swarm may not reserve the same credit. Queries within different swarms, but with the same payment ID, may reserve the same credit. Queries with different payment IDs may not reserve the same credit. When a query forks in two separate directions, it splits into two different paths, but each maintain the same swarm ID. To avoid overlap, payer-initiated (forward) queries should use even-numbered swarm IDs, and recipient-initiated (backward) queries odd-numbered swarm IDs. See [[Query Routing -> #query-routing]].
The payer sends out "forward" queries, and the recipient sends out "backward" queries, refering to the direction the payment will ultimately take. If fees are permitted, the backward queries are more precise: the payment amount is generally interpreted as the amount to be received by the recipient (Paypal notwithstanding), and the backward queries begin by specifying this amount and accumulate fees as they propagate towards the payer. Forward queries that permit fees must begin with an estimate of the payment amount including intermediary fees, which would generally be too high and result in too much credit being reserved. However, forward queries play an important role as signposts towards the payer for the more-precise backward queries.
The transaction units allow the payer and recipient to recognize what percentage of the payment is actually being paid and received down a given path, regardless of fees or varying conversion rates between account units along the path. For example, suppose node A is paying node C $100 through intermediary node B. A's account with B may be in Euros, and B's account with C may be in Pounds. Before paying 82 Euros to B, A must know how many dollars that represents to recipient C. Intermediaries that do not recognize the transaction units cannot enforce overall fee limits on queries.
The account ID changes with each step the query is forwarded along, and lets the query recipient know which account with the sender is intended as part of the path, if there is more than one. The amount in account units is the amount that is to be reserved on that account for this query's payment path. It also defines a conversion rate between account units and transaction units that can be used to calculate whether or not the full query amount can be passed on to a single neighbour, and what proportion to pass on to various neighbours otherwise. This conversion rate is also used in subsequent payment messages.
The target location is used by each intermediary to route the query. Generally the target for forward queries is the recipient's location, and the target for backward queries is the payer's location, but this is not strictly required. Either payer or recipient may direct the other to route their queries to a different target location, and then ensure that the node with this target location receives a query from the opposite direction to point back to the correct target.
The credit guarantee expiry time gives a deadline for the next phase of the payment to occur. If this time limit is reached, the credit held for this path will be released and made available to other payments. Each intermediary should subtract from this time before passing it on to give themselves a small buffer in which to process messages from the next payment phase. The time is given in the connection time between each of the intermediaries, so each one must convert if the time on the incoming account is not in sync with the time on the outgoing account. See [[Connection Time -> #connection-time]].
The promise penalty deadline, penalty rate, and final deadline refer to fields in the @@promise@@ message in the next payment phase. In the forward query, they represent maximum bounds for those fields, and in the backward query, minimum bounds. The times are again given in connection time, and the penalty rate is a daily percentage.
The hop limit is the maximum number of hops for all queries spawned from the one received, including forks. When a query forks in several different directions, the hop limit must be divided up amongst them.
The bloom filter containing aliases of the locations already visited is to prevent loops -- no location should occur twice in the same path. Nodes can use any alias they want as long as it is unique among potential intermediaries with high probability and they remember it to compare against incoming queries with the same payment and swarm IDs.
The per-hop fee limit is a limit on the percentage fee charged per hop in the path. The accumulated fee limit is an overall limit to the fees on this query. This can only be enforced if intermediaries recognize the transaction units.
When the query reaches the opposing payment endpoint, or creates a loop or otherwise hits a dead end, the node receiving the query message returns a @@path-response@@ message:
* payment ID
* swarm ID
* list of path IDs with corresponding available amounts in transaction units
* path ID of query to which this message is a response
* expiry time for these paths
* unused hop limit
These path-responses are propagated back to the query originator in the following fashion: When an intermediary receives a path-response, it checks whether the available amounts equal the amount on the query to which it is a response. If the sum of the path amounts is less than the original query, it sends out new secondary queries for the remaining amounts, if possible. (Multiple queries are permitted on the same accounts, but each must have a different path ID as described in [[Query Routing -> #query-routing]].) Unused hop limit may be used for this purpose. Credit amounts held for the outgoing query should be reduced to reflect the amounts in the path-response.
If the path amounts equal the original query amount, if there is no unused hop limit, or if there are no directions remaining to query, it waits until it has received responses to all its queries, and then packages the nonzero paths together into a new query response. The new expiry time is the soonest expiry time of any of the path-responses. The unused hop limit is the total unused hop limit from all the responses that hasn't been used in a secondary query fork.
[[#fees]]
'''Fees'''
Fees charged may be integrated as a percentage into conversion rates between units. There is no provision for flat fees at the moment. Minimum fees for any payment through an account are shared with account partners as part of the account data.
[[#query-routing]]
'''Query Routing'''
Ripple uses the Metropolis-Hastings algorithm for routing, as described in Clarke and Sandberg's presentation [[Routing in the Dark -> http://www.math.chalmers.se/~ossa/defcon13/vegas1_print.pdf]] (PDF).
Each node partitions its accounts into separate routing classes such that obligations are convertible between any accounts within a class (in other words, an incoming payment on any account might be routed out along any other account in its routing class). Each routing class is then given a location, which is a decimal number between 0 and 1 representing a position on the boundary of a circle. The distance between any two locations is defined as the distance along the boundary of the circle between their locations:
[@
d(x, y) = min(abs(x - y), 1 - abs(x - y))
@]
Each node regularly swaps locations with other randomly-chosen nodes in a systematic way to minimize the product of the distances to its neighbours. Thus a node's location comes to be close in a certain sense to the location of its neighbours. Path-finding messages can then be routed by passing them to those neighbours with locations closest to the target location.
See below for a [[specification of location-swapping -> #location-swapping]].
A @@path-query@@ is routed first in directions path-queries in the opposite direction were received for the same payment ID. From among these directions, the neighbour with the location closest to the query's target location is chosen first. If there is not enough credit, as determined by available credit specified on the opposing query received from that direction, to fulfill the entire query, new queries with new path IDs are forked off in subsequent directions which have received opposing queries. Path IDs must be unique within a swarm. Once directions having received opposing path-queries are used up, all the accounts in the routing class may be considered on the basis of distance to the target location, using available credit as determined by the account balances and limits.
Remember that credit amounts reported as available on queries must be held for that path and made unavailable for other payments until they time out. Only other swarms from the same payment may access amounts held.
At all times, per-hop fee limits must be obeyed. If a node would charge more than the per-hop fee limit, it must respond as though it were a dead end. An account with a minimum fee on through payments higher than the per-hop fee limit on the query should therefore be ignored for the purposes of routing that query.
Note that with Metropolis-Hastings routing there is no requirement for nodes to report their own exact location as the routing target of messages from transaction partners. They may report slightly inexact locations for privacy reasons, or the location of a neighbour, or an average of a group of neighbours to route the message through them. This requires informing those neighbours ahead of time that the message is coming, by sending a @@path-query@@.
The performance of path-finding will be critical to the success of Ripple, and therefore the protocol should be as flexible as possible in terms of its ability to incorporate new and diverse methods of path-finding.
[[Protocol/Path Discovery Work Page]]