Protocol /
Routing
Protocol.Routing History
Hide minor edits - Show changes to output
Added lines 3-4:
In the following, a routing ID identifies a routing entity that can take an incoming payment on any of its links and convert it to an outgoing payment on any of its other links. A Ripple user on a host may have some accounts that don't convert to other accounts. In that case, the user should form multiple routing entities, so every link in each is convertible to every other link. (This is true for any Ripple routing scheme.) A node may have multiple routing IDs.
Deleted lines 0-1:
Changed lines 6-15 from:
"link-ad": {
"id": (string)
"sender": (routing id),
"link-to": (routing id),
"status": ("up" | "down"),
"hop-limit": (integer),
("fwd-credit": (decimal),)
("bwd-credit": (decimal),)
("units": (URI),)
}
"
to:
"type": "link-ad",
"time": (date/time),
"body": {
"id": (string)
"source": (routing id),
"link-to": (routing id),
"status": ("up" | "down"),
"hop-limit": (integer),
("fwd-credit": (decimal),)
("bwd-credit": (decimal),)
("units": (URI),)
}
"time": (date/time),
"body": {
"id": (string)
"source": (routing id),
"link-to": (routing id),
"status": ("up" | "down"),
"hop-limit": (integer),
("fwd-credit": (decimal),)
("bwd-credit": (decimal),)
("units": (URI),)
}
Changed lines 29-36 from:
"payment-init": {
"payer-routing-id": (routing id),
("max-fee": (decimal),)
("path-units": (URI),)
("min-penalty-deadline": (time delta),)
("min-deadline": (time delta),)
("min-guarantee-expiry": (date/time string))
}
"payer-routing-id": (routing id),
("max-fee": (decimal),)
("path-units": (URI),)
("min-penalty-deadline": (time delta),)
("min-deadline": (time delta),)
("min-guarantee-expiry": (date/time string))
}
to:
"body": {
"payer-routing-id": (routing id),
("max-fee": (decimal),)
("path-units": (URI),)
("min-penalty-deadline": (time delta),)
("min-deadline": (time delta),)
("min-guarantee-expiry": (date/time string))
}
"payer-routing-id": (routing id),
("max-fee": (decimal),)
("path-units": (URI),)
("min-penalty-deadline": (time delta),)
("min-deadline": (time delta),)
("min-guarantee-expiry": (date/time string))
}
Changed lines 43-45 from:
"payment-accept": {
"recipient-routing-id": (routing id)
}
"recipient-routing-id": (routing id)
}
to:
"body": {
"recipient-routing-id": (routing id)
}
"recipient-routing-id": (routing id)
}
Changed lines 52-67 from:
"path-query": {
"payment-id": (string),
"path-id": [(ordered list of strings)],
"path-amount": (decimal),
("max-fee": (decimal),)
("path-units": (URI),)
"account-id": (string),
"amount": (decimal),
"onion": (routing onion data structure),
"target": (routing id),
"ttl": (time/date string),
("min-penalty-deadline": (time delta),)
("max-penalty-rate": (decimal),)
("min-deadline": (time delta),)
"guarantee-expiry": (date/time string),
}
("max-fee": (decimal),)
}
to:
"body": {
"payment-id": (string),
"path-id": [(ordered list of strings)],
"path-amount": (decimal),
("max-fee": (decimal),)
("path-units": (URI),)
"account-id": (string),
"amount": (decimal),
"onion": (routing onion data structure),
"target": (routing id),
"ttl": (time/date string),
("min-penalty-deadline": (time delta),)
("max-penalty-rate": (decimal),)
("min-deadline": (time delta),)
"guarantee-expiry": (date/time string),
}
"payment-id": (string),
"path-id": [(ordered list of strings)],
"path-amount": (decimal),
("max-fee": (decimal),)
("path-units": (URI),)
"account-id": (string),
"amount": (decimal),
"onion": (routing onion data structure),
"target": (routing id),
"ttl": (time/date string),
("min-penalty-deadline": (time delta),)
("max-penalty-rate": (decimal),)
("min-deadline": (time delta),)
"guarantee-expiry": (date/time string),
}
Changed lines 74-76 from:
"promise": {
"target": (routing id),
}
}
to:
"body": {
"target": (routing id),
}
"target": (routing id),
}
Changed lines 83-85 from:
"account": {
"advertise-link": (true | false),
}
to:
"account": {
"advertise-link": (true | false),
}
"advertise-link": (true | false),
}
Deleted lines 86-87:
[[Protocol/Routing Work Page]]
Changed lines 3-27 from:
'''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.
to:
Subprotocol name: @@ripple-routing@@.
Link-State Routing Advertisement
{
"link-ad": {
"id": (string)
"sender": (routing id),
"link-to": (routing id),
"status": ("up" | "down"),
"hop-limit": (integer),
("fwd-credit": (decimal),)
("bwd-credit": (decimal),)
("units": (URI),)
}
}
Routing ID
(string)
Payment Init (extra fields)
{
"payment-init": {
"payer-routing-id": (routing id),
("max-fee": (decimal),)
("path-units": (URI),)
("min-penalty-deadline": (time delta),)
("min-deadline": (time delta),)
("min-guarantee-expiry": (date/time string))
}
}
Payment Accept (extra field)
{
"payment-accept": {
"recipient-routing-id": (routing id)
}
}
Path Query
{
"path-query": {
"payment-id": (string),
"path-id": [(ordered list of strings)],
"path-amount": (decimal),
("max-fee": (decimal),)
("path-units": (URI),)
"account-id": (string),
"amount": (decimal),
"onion": (routing onion data structure),
"target": (routing id),
"ttl": (time/date string),
("min-penalty-deadline": (time delta),)
("max-penalty-rate": (decimal),)
("min-deadline": (time delta),)
"guarantee-expiry": (date/time string),
}
}
Promise (extra field)
{
"promise": {
"target": (routing id),
}
}
Account Data Structure (extra field)
{
"account": {
"advertise-link": (true | false),
}
}
Link-State Routing Advertisement
{
"link-ad": {
"id": (string)
"sender": (routing id),
"link-to": (routing id),
"status": ("up" | "down"),
"hop-limit": (integer),
("fwd-credit": (decimal),)
("bwd-credit": (decimal),)
("units": (URI),)
}
}
Routing ID
(string)
Payment Init (extra fields)
{
"payment-init": {
"payer-routing-id": (routing id),
("max-fee": (decimal),)
("path-units": (URI),)
("min-penalty-deadline": (time delta),)
("min-deadline": (time delta),)
("min-guarantee-expiry": (date/time string))
}
}
Payment Accept (extra field)
{
"payment-accept": {
"recipient-routing-id": (routing id)
}
}
Path Query
{
"path-query": {
"payment-id": (string),
"path-id": [(ordered list of strings)],
"path-amount": (decimal),
("max-fee": (decimal),)
("path-units": (URI),)
"account-id": (string),
"amount": (decimal),
"onion": (routing onion data structure),
"target": (routing id),
"ttl": (time/date string),
("min-penalty-deadline": (time delta),)
("max-penalty-rate": (decimal),)
("min-deadline": (time delta),)
"guarantee-expiry": (date/time string),
}
}
Promise (extra field)
{
"promise": {
"target": (routing id),
}
}
Account Data Structure (extra field)
{
"account": {
"advertise-link": (true | false),
}
}
Added lines 1-28:
[[Protocol/Routing Work Page]]
[[#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/Routing Work Page]]
[[#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/Routing Work Page]]