Additions:
==Related papers
http://www.dtek.chalmers.se/~vive/soc2.pdf
http://www.dtek.chalmers.se/~vive/soc2.pdf
Additions:
See also: RoutingCapacityBias.
Revision [1912]
Edited on 2007-03-21 14:04:19 by MatthewToselandNo differences.
Revision [1911]
Edited on 2007-03-21 14:04:04 by MatthewToselandAdditions:
See also: CurrentLoadManagement (this page is more focused on future options, the link is an explanation of what we have now).
Additions:
==Proposed Changes to Load Balancing==
A new load balancing mechanism is being developed as part of the [[http://code.google.com/soc/ Google Summer of Code]]. The mechanism will probably work as follows:
- [[http://citeseer.ist.psu.edu/floyd00comparison.html AIMD]] congestion control on each outgoing link
- A [[http://en.wikipedia.org/wiki/Token_bucket token bucket]] for flow control on each incoming link
- Fill the buckets at equal rates to ensure fairness
- When a peer's bucket is empty, reject its requests
- When a peer's bucket is full (ie when an incoming link is underused), add its tokens to another bucket instead
- Perhaps add them to the emptiest bucket (if there's excess bandwidth, give it to whoever asks for it)
- Perhaps add them to the fullest bucket (giving peers an incentive to ask for as little bandwidth as possible)
- We probably need simulations to discover the knock-on effects of both suggestions
- When forwarding a Rejected''''Overload, possibly reduce the rate at which the rejected peer's bucket is filled
- This provides a stronger incentive to conserve bandwidth, but could adversely affect paths that share one or more links with the path of the rejected request
- Again, simulations are needed
A new load balancing mechanism is being developed as part of the [[http://code.google.com/soc/ Google Summer of Code]]. The mechanism will probably work as follows:
- [[http://citeseer.ist.psu.edu/floyd00comparison.html AIMD]] congestion control on each outgoing link
- A [[http://en.wikipedia.org/wiki/Token_bucket token bucket]] for flow control on each incoming link
- Fill the buckets at equal rates to ensure fairness
- When a peer's bucket is empty, reject its requests
- When a peer's bucket is full (ie when an incoming link is underused), add its tokens to another bucket instead
- Perhaps add them to the emptiest bucket (if there's excess bandwidth, give it to whoever asks for it)
- Perhaps add them to the fullest bucket (giving peers an incentive to ask for as little bandwidth as possible)
- We probably need simulations to discover the knock-on effects of both suggestions
- When forwarding a Rejected''''Overload, possibly reduce the rate at which the rejected peer's bucket is filled
- This provides a stronger incentive to conserve bandwidth, but could adversely affect paths that share one or more links with the path of the rejected request
- Again, simulations are needed
Revision [771]
Edited on 2006-04-11 19:53:13 by MatthewToselandNo differences.
Revision [770]
Edited on 2006-04-11 19:52:29 by MatthewToselandAdditions:
The bottom layer corresponds to CDMA on Ethernet: If a request times out, or a node rejects a request because of overloading (see CongestionControl), we back off from the node. This is exponential, randomized backoff just as with Ethernet: We double the maximum backoff on every consecutive failure, and reset it on a success, and back off for a random time up to the maximum backoff time. This is at the direct connections between peers level.
Deletions:
Additions:
The next layer up corresponds to TCP and indeed uses the same algorithm as TCP for load limiting. If the client node gets a timeout or a rejection due to overload (the latter are forwarded from the origin node back to the request originator), then it reduces the rate at which it sends requests. If it doesn't, it increases it. The algorithm used for increasing and decreasing the request send rate is the same as in TCP. Specifically, we have an average round trip time, and we have a window size (the number of requests that may be in progress at once). If a request completes without either a timeout or a Rejected''''Overload, then the window size is increased by a constant. If a request fails due to a timeout, or if it gets a Rejected''''Overload, then the window size is decreased by a certain fraction. We send a request every (round trip time) / (window size). This AIMD algorithm is the same as is used in TCP. We use a very similar mechanism for data transfer. Recently we have decided to use a single window size for all four types of request (insert/fetch CHK/SSK), but keep a separate round-trip-time average for each; this is to ensure that inserts are not unreasonably slow (since they visit many more nodes than requests, they will hit more overloaded nodes).
Deletions:
Revision [764]
Edited on 2006-04-11 19:23:34 by MatthewToselandAdditions:
The next layer up corresponds to TCP and indeed uses the same algorithm as TCP for load limiting. If the client node gets a timeout or a rejection due to overload (the latter are forwarded from the origin node back to the request originator), then it reduces the rate at which it sends requests. If it doesn't, it increases it. The algorithm used for increasing and decreasing the request send rate is the same as in TCP. Specifically, we have an average round trip time, and we have a window size (the number of requests that may be in progress at once). If a request completes without either a timeout or a Rejected''''Overload, then the window size is increased by a constant. If a request fails due to a timeout, or if it gets a Rejected''''Overload, then the window size is decreased by a certain fraction. We send a request every (round trip time) / (window size). This AIMD algorithm is the same as is used in TCP. We use a very similar mechanism for data transfer.
Deletions:
Revision [763]
Edited on 2006-04-11 19:23:15 by MatthewToselandAdditions:
The next layer up corresponds to TCP and indeed uses the same algorithm as TCP. If the client node gets a timeout or a rejection due to overload (the latter are forwarded from the origin node back to the request originator), then it reduces the rate at which it sends requests. If it doesn't, it increases it. The algorithm used for increasing and decreasing the request send rate is the same as in TCP. Specifically, we have an average round trip time, and we have a window size (the number of requests that may be in progress at once). If a request completes without either a timeout or a Rejected''''Overload, then the window size is increased by a constant. If a request fails due to a timeout, or if it gets a Rejected''''Overload, then the window size is decreased by a certain fraction. We send a request every (round trip time) / (window size). This AIMD algorithm is the same as is used in TCP. We use a very similar mechanism for data transfer.
Deletions:
Revision [762]
Edited on 2006-04-11 19:22:36 by MatthewToselandAdditions:
The next layer up corresponds to TCP and indeed uses the same algorithm as TCP. If the client node gets a timeout or a rejection due to overload (the latter are forwarded from the origin node back to the request originator), then it reduces the rate at which it sends requests. If it doesn't, it increases it. The algorithm used for increasing and decreasing the request send rate is the same as in TCP. Specifically, we have an average round trip time, and we have a window size. If a request completes without either a timeout or a Rejected''''Overload, then the window size is increased by a constant. If a request fails due to a timeout, or if it gets a Rejected''''Overload, then the window size is decreased by a certain fraction. We send a request every (round trip time) / (window size). This AIMD algorithm is the same as is used in TCP. We use a very similar mechanism for data transfer.
Deletions:
Additions:
The next layer up corresponds to TCP and indeed uses the same algorithm as TCP. If the client node gets a timeout or a rejection due to overload (the latter are forwarded from the origin node back to the request originator), then it reduces the rate at which it sends requests. If it doesn't, it increases it. The algorithm used for increasing and decreasing the request send rate is the same as in TCP. Specifically, we have an average round trip time, and we have a window size. If a request completes without either a timeout or a RejectedOverload, then the window size is increased by a constant. If a request fails due to a timeout, or if it gets a RejectedOverload, then the window size is decreased by a certain fraction. We send a request every (round trip time) / (window size). This AIMD algorithm is the same as is used in TCP. We use a very similar mechanism for data transfer.
