Revision [3612]

Last edited on 2009-12-19 18:09:28 by EvanD [rv spam]
Deletions:
[[http://www.mastersthesiswriting.com/dissertation.html Online Dissertation]]

Revision [3597]

Edited on 2009-12-16 16:25:26 by AlexHaffey [!]
Additions:
[[http://www.mastersthesiswriting.com/dissertation.html Online Dissertation]]

Revision [3549]

Edited on 2009-11-18 04:20:51 by EvanD [rv spam]
Additions:
The transport layer provides a similar service to TCP: reliable, congestion-controlled delivery of FNP messages. However, the needs of FNP are slightly different from those of a typical TCP application in two ways: first, FNP does not require messages to be delivered in the same order in which they were sent (although we **must** do a thorough audit of the protocol to confirm this before deploying the new transport layer); and second, FNP connections are typically long-lived (whereas TCP connections in environments like the web are often used to transfer only a few KB of data). The first difference affects how out-of-order packets are handled by the receiver, and makes selective acknowledgements more efficient that cumulative acknowledgements; the second difference affects congestion control. Apart from these differences, the design of the new transport layer is closely based on TCP, and provides duplicate detection, retransmission, and congestion control in similar ways to TCP.
Deletions:
The transport layer provides a similar service to TCP: reliable, congestion-controlled delivery of FNP messages. However, the needs of FNP are slightly different from those of a typical TCP application in two ways: first, FNP does not require messages to be delivered in the same order in which they were sent (although we **must** do a thorough audit of the protocol to confirm this before deploying the new transport layer); and second, FNP connections are typically long-lived (whereas TCP connections in environments like the web are often used to transfer only a few KB of data). The first difference affects how out-of-order packets are handled by the receiver, and makes selective acknowledgements more efficient that cumulative acknowledgements; the second difference affects congestion control. Apart from these differences, the design of the new transport layer is closely based on TCP [[http://www.bestdissertation.com/services/thesis.html thesis]], and provides duplicate detection, retransmission, and congestion control in similar ways to TCP.

Revision [3532]

Edited on 2009-11-15 23:04:11 by NoaSedan
Additions:
The transport layer provides a similar service to TCP: reliable, congestion-controlled delivery of FNP messages. However, the needs of FNP are slightly different from those of a typical TCP application in two ways: first, FNP does not require messages to be delivered in the same order in which they were sent (although we **must** do a thorough audit of the protocol to confirm this before deploying the new transport layer); and second, FNP connections are typically long-lived (whereas TCP connections in environments like the web are often used to transfer only a few KB of data). The first difference affects how out-of-order packets are handled by the receiver, and makes selective acknowledgements more efficient that cumulative acknowledgements; the second difference affects congestion control. Apart from these differences, the design of the new transport layer is closely based on TCP [[http://www.bestdissertation.com/services/thesis.html thesis]], and provides duplicate detection, retransmission, and congestion control in similar ways to TCP.
Deletions:
The transport layer provides a similar service to TCP: reliable, congestion-controlled delivery of FNP messages. However, the needs of FNP are slightly different from those of a typical TCP application in two ways: first, FNP does not require messages to be delivered in the same order in which they were sent (although we **must** do a thorough audit of the protocol to confirm this before deploying the new transport layer); and second, FNP connections are typically long-lived (whereas TCP connections in environments like the web are often used to transfer only a few KB of data). The first difference affects how out-of-order packets are handled by the receiver, and makes selective acknowledgements more efficient that cumulative acknowledgements; the second difference affects congestion control. Apart from these differences, the design of the new transport layer is closely based on TCP, and provides duplicate detection, retransmission, and congestion control in similar ways to TCP.

Revision [3523]

Edited on 2009-11-13 16:27:10 by EvanD [rv spam]
Additions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.
Deletions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's [[http://www.bestdissertation.com/services/thesis.html thesis]] retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.

Revision [3499]

Edited on 2009-11-08 23:45:05 by KateWoods [typo]
Additions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's [[http://www.bestdissertation.com/services/thesis.html thesis]] retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.
Deletions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.

Revision [3482]

Edited on 2009-11-06 20:23:52 by Infinity0 [rm linkspam]
Additions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.
6) When a packet is retransmitted due to the retransmission timer, the congestion window is reset to the maximum packet size and the connection enters slow start. The number of bytes in flight is not modified. (A retransmission timeout is taken as an indication of severe congestion; returning to slow start allows the available bandwidth to be re-estimated.)
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet?
Deletions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission, as indicated on a [[http://www.bestdissertation.com/services/thesis.html thesis]], because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.
6) When a packet is retransmitted due to the retransmission timer, the congestion window is reset to the maximum packet size and the connection enters slow start and it needs [[www.HydrocodoneHelp.com help]]. The number of bytes in flight is not modified. (A retransmission timeout is taken as an indication of severe congestion; returning to slow start allows the available bandwidth to be re-estimated.)
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet? How about a about this for further more research?

Revision [3463]

Edited on 2009-10-30 01:17:08 by DouHou
Additions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission, as indicated on a [[http://www.bestdissertation.com/services/thesis.html thesis]], because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.
Deletions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.

Revision [3462]

Edited on 2009-10-29 18:46:28 by SteveJones [Small Revision]
Additions:
6) When a packet is retransmitted due to the retransmission timer, the congestion window is reset to the maximum packet size and the connection enters slow start and it needs [[www.HydrocodoneHelp.com help]]. The number of bytes in flight is not modified. (A retransmission timeout is taken as an indication of severe congestion; returning to slow start allows the available bandwidth to be re-estimated.)
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet? How about a about this for further more research?
Deletions:
6) When a packet is retransmitted due to the retransmission timer, the congestion window is reset to the maximum packet size and the connection enters slow start. The number of bytes in flight is not modified. (A retransmission timeout is taken as an indication of severe congestion; returning to slow start allows the available bandwidth to be re-estimated.)
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet? How about a [[http://www.bestdissertation.com/services/thesis.html thesis]] about this for further more research?

Revision [3440]

Edited on 2009-10-21 07:42:13 by FayeLee [re-edit]
Additions:
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet? How about a [[http://www.bestdissertation.com/services/thesis.html thesis]] about this for further more research?
Deletions:
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet? How about a [[http://www.bestdissertation.com thesis]] about this for further more research?

Revision [3437]

Edited on 2009-10-21 07:30:38 by FayeLee [more info]
Additions:
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet? How about a [[http://www.bestdissertation.com thesis]] about this for further more research?
Deletions:
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet?

Revision [2606]

Edited on 2008-03-01 19:00:53 by MichaelRogers [Made a few cleanups and added some FIXMEs]
Additions:
Packets may be lost by the network as a result of congestion or other problems; the transport layer uses acknowledgements and timeouts to work out which packets have been lost. TCP uses cumulative acknowledgements, but to support out-of-order delivery Freenet uses selective acknowledgements: every payload is explicitly acknowledged, even if it arrives out of order. This makes it easy to maintain an estimate of the round-trip time: the sender uses an exponential moving average of the time between a packet being sent and the acknowledgement being received.
Fast retransmission should detect and repair most packet losses, but in cases of severe congestion or long periods without sending new data, a fallback mechanism is needed. This mechanism is the //retransmission timer//: every 100ms the node checks all its connections for payloads that were last sent at least RTO round-trip times ago and have not yet been acknowledged. Any payloads that meet these conditions are retransmitted, their timestamps are updated, and the connection's congestion window is modified (see below). The node's connections should be checked in a random order each time, to avoid giving some connections preferential access to the available bandwidth. A suggested value for RTO is 4. TCP uses a more sophisticated scheme that tracks the variance as well as the average of the round-trip time. RFC 2988 give the best description of the algorithm, but here's a summary:
FIXME: the congestion window may grow very large when the amount of data that can be sent is limited by something other than congestion (e.g. the bandwidth limiter). See RFC 2861 for details of how TCP handles this.
FIXME: do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? Why not wait until we can send a larger packet?
FIXME: searches now take priority over transfers.
Deletions:
Packets may be lost by the network as a result of congestion or other problems; the transport layer uses acknowledgements and timeouts to work out which packets have been lost. TCP uses cumulative acknowledgements, but in order to allow out-of-order delivery Freenet uses selective acknowledgements: every payload is explicitly acknowledged, even if it arrives out of order. This makes it easy to maintain an estimate of the round-trip time: the sender uses an exponential moving average of the time between a packet being sent and the acknowledgement being received.
Fast retransmission should detect and repair most packet losses, but in cases of severe congestion or long periods without sending new data, a fallback mechanism is needed. This mechanism is the //retransmission timer//: every 100ms the node checks all its connections for payloads that were last sent at least RTO round-trip times ago and have not yet been acknowledged. Any payloads that meet these conditions are retransmitted, and the connection's congestion window is modified (see below). The node's connections should be checked in a random order each time, to avoid giving some connections preferential access to the available bandwidth. A suggested value for RTO is 4. TCP uses a more sophisticated scheme that tracks the variance as well as the average of the round-trip time. RFC 2988 give the best description of the algorithm, but here's a summary:
FIXME do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? why not wait until we can send a larger packet?

Revision [2170]

Edited on 2007-07-28 19:34:35 by MatthewToseland [add fixme]
Additions:
FIXME do we want to shrink packets and thereby make sends less efficient in response to bandwidth pressure? why not wait until we can send a larger packet?

Revision [2021]

Edited on 2007-04-25 20:21:46 by MichaelRogers [Added notes about RFC 2988 and TCP-style fast retransmission]
Additions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. TCP uses a slightly different method that we should probably copy: if a payload number greater than n+3 is acknowledged and payload n has never been retransmitted, payload n is retransmitted.
Fast retransmission should detect and repair most packet losses, but in cases of severe congestion or long periods without sending new data, a fallback mechanism is needed. This mechanism is the //retransmission timer//: every 100ms the node checks all its connections for payloads that were last sent at least RTO round-trip times ago and have not yet been acknowledged. Any payloads that meet these conditions are retransmitted, and the connection's congestion window is modified (see below). The node's connections should be checked in a random order each time, to avoid giving some connections preferential access to the available bandwidth. A suggested value for RTO is 4. TCP uses a more sophisticated scheme that tracks the variance as well as the average of the round-trip time. RFC 2988 give the best description of the algorithm, but here's a summary:
Initially the retransmission timeout (rto) is set to 3 seconds. We keep a smoothed estimate of the round-trip time (rtt) and a smoothed estimate of the variance (rttVar). G is the granularity of the retransmission timer, in our case 0.1 seconds. ALPHA is 1/8 and BETA is 1/4, so the estimate of the variance is more sensitive to changes than the estimate of the round-trip time. (Note that these are separate from the similarly named parameters ALPHA and BETA for the congestion window.)
When we get the first sample of the round-trip time (r):
rtt = r
rttVar = r/2
rto = rtt + max (G, 4 * rttVar)
For each subsequent sample:
rttVar = (1.0 - BETA) * rttVar + BETA * abs (rtt - r)
rtt = (1.0 - ALPHA) * rtt + ALPHA * r
rto = rtt + max (G, 4 * rttVar)
Round-trip time samples must not be taken from packets that were retransmitted, because the ack might be for the original packet or the retransmission.
Deletions:
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network.
Fast retransmission should detect and repair most packet losses, but in cases of severe congestion or long periods without sending new data, a fallback mechanism is needed. This mechanism is the //retransmission timer//: every 100ms the node checks all its connections for payloads that were last sent at least RTO round-trip times ago and have not yet been acknowledged. Any payloads that meet these conditions are retransmitted, and the connection's congestion window is modified (see below). The node's connections should be checked in a random order each time, to avoid giving some connections preferential access to the available bandwidth. A suggested value for RTO is 4. TCP uses a more sophisticated scheme that tracks the variance as well as the average of the round-trip time.

Revision [1826]

Edited on 2007-02-27 13:27:04 by MichaelRogers
Additions:
The transport layer provides a similar service to TCP: reliable, congestion-controlled delivery of FNP messages. However, the needs of FNP are slightly different from those of a typical TCP application in two ways: first, FNP does not require messages to be delivered in the same order in which they were sent (although we **must** do a thorough audit of the protocol to confirm this before deploying the new transport layer); and second, FNP connections are typically long-lived (whereas TCP connections in environments like the web are often used to transfer only a few KB of data). The first difference affects how out-of-order packets are handled by the receiver, and makes selective acknowledgements more efficient that cumulative acknowledgements; the second difference affects congestion control. Apart from these differences, the design of the new transport layer is closely based on TCP, and provides duplicate detection, retransmission, and congestion control in similar ways to TCP.
The transport layer deals with plaintext payloads, each containing one or more complete FNP messages and identified by a payload number. The transport layer does **not** make use of the unique sequence numbers used by the encryption and authentication layer (see NewPacketFormat). This means the transport layer may receive the same payload more than once, due to retransmissions or packet duplication by the network. To detect and discard duplicates, the receiver maintains a sliding window starting at the lowest payload number not yet received (which is zero when the connection is first established) and covering the next 2^16 payloads. A bitmap is used to record which payloads within the window have been received. (The window is much larger than those used by IPSec and Datagram TLS because of the need to handle retransmissions.)
Packets may be lost by the network as a result of congestion or other problems; the transport layer uses acknowledgements and timeouts to work out which packets have been lost. TCP uses cumulative acknowledgements, but in order to allow out-of-order delivery Freenet uses selective acknowledgements: every payload is explicitly acknowledged, even if it arrives out of order. This makes it easy to maintain an estimate of the round-trip time: the sender uses an exponential moving average of the time between a packet being sent and the acknowledgement being received.
Payloads that have been sent but not acknowledged must be stored by the sender in case they need to be retransmitted. To improve efficiency, the sender may store the entire packet, but packets that contain an ack with no payload must not be stored, since they will not be acknowledged.
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs //fast retransmission//: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network.
Fast retransmission should detect and repair most packet losses, but in cases of severe congestion or long periods without sending new data, a fallback mechanism is needed. This mechanism is the //retransmission timer//: every 100ms the node checks all its connections for payloads that were last sent at least RTO round-trip times ago and have not yet been acknowledged. Any payloads that meet these conditions are retransmitted, and the connection's congestion window is modified (see below). The node's connections should be checked in a random order each time, to avoid giving some connections preferential access to the available bandwidth. A suggested value for RTO is 4. TCP uses a more sophisticated scheme that tracks the variance as well as the average of the round-trip time.
The sender uses an adaptive congestion window to determine the maximum amount of data that can be in flight (sent but not yet acknowledged) at any time. The number of bytes in flight and the congestion window are modified when packets are transmitted, retransmitted or acknowledged. Specifically:
4) When a packet is first acknowledged, its total size is subtracted from the number of bytes in flight. If the connection is in slow start, ALPHA * size / MAX_PACKET_SIZE bytes are added to the congestion window, where 'size' is the total size of the acknowledged packet. If the connection is in congestion avoidance, ALPHA * size / MAX_PACKET_SIZE / cwnd bytes are added to the congestion window, where 'cwnd' is the current size of the congestion window in bytes. Thus the congestion window grows exponentially during slow start, and linearly during congestion avoidance, until a loss occurs. The maximum size of the congestion window is 1,000,000 bytes.
Deletions:
The transport layer provides a similar service to TCP: reliable, congestion-controlled delivery of FNP messages. However, the needs of FNP are slightly different from those of a typical TCP application in two ways: first, FNP does not require messages to be delivered in the same order in which they were sent (although we **must** do a thorough audit of the protocol to confirm this before deploying the new transport layer); and second, FNP connections are typically long-lived (whereas TCP connections in environments like the web are often used to transfer only a few KB of data). The first difference affects how out-of-order packets are handled by the receiver, and makes selective acknowledgements more efficient that cumulative acknowledgements; the second difference affects congestion control. Apart from these differences, the design of the new transport layer is closely based on TCP, and provides duplicate detection, retransmission, and congestion control.
The transport layer deals with plaintext payloads, each containing one or more complete FNP messages and identified by a payload number. The transport layer does **not** make use of the unique sequence numbers used by the encryption and authentication layer (see NewPacketFormat). This means the transport layer may receive the same payload more than once, due to retransmissions or packet duplication by the network. To detect and discard duplicates, the receiver maintains a sliding window starting at the lowest payload number not yet received (which is zero when the connection is first established) and covering the next 2^16 payloads. A bitmap is used to record which payloads within the window have been received.
Packets may be lost by the network as a result of congestion or other problems; the transport layer uses acknowledgements and timeouts to work out which packets have been lost. TCP uses cumulative acknowledgements, but in order to allow out-of-order delivery the Freenet transport layer uses selective acknowledgements: every payload is explicitly acknowledged, even if it arrives out of order. This makes it easy to maintain an estimate of the round-trip time: the sender uses an exponential moving average of the time between a packet being sent and the acknowledgement being received. (FIXME: coalescing delay.)
Payloads that have been sent but not acknowledged must be stored by the sender in case they need to be retransmitted. To improve efficiency, the sender may also store any acks that were sent in the same packet as the payload, but acks that were sent in a packet with no payload must not be stored, since they will not be acknowledged.
When the sender receives an ack, it checks its retransmission buffer for the acknowledged payload. If the payload is found, it is removed (this may allow new payloads to be sent if the sender was waiting for payload n to be acknowledged before sending payload n+2^16). While checking the retransmission buffer, the sender also performs *fast retransmission*: if a payload number greater than n is acknowledged and payload n was last transmitted more than FRTO round-trip times ago, payload n is retransmitted (and the congestion window is modified - see below). Payload n remains in the sender's retransmission buffer, but its timestamp is updated to prevent it from being retransmitted again until another FRTO round-trip times have elapsed. Like the similar mechanism in TCP, this mechanism is called fast retransmission because it infers the loss of a packet before the packet times out, by observing the delivery of subsequent packets. The suggested value for FRTO is 1.5 - values closer to 1 will detect losses more quickly but may trigger unnecessary retransmissions if packets are reordered by the network. (FIXME: coalescing delay.)
Fast retransmission should detect and repair most packet losses, but in cases of severe congestion or long periods without sending new data, a fallback mechanism is needed. This mechanism is the *retransmission timer*: every 100ms the node checks all its connections for payloads that were last sent at least RTO round-trip times ago and have not yet been acknowledged. Any payloads that meet the conditions are retransmitted, and the connection's congestion window is modified (see below). (The node's connections should be checked in a random order each time, to avoid giving some connections preferential access to the available bandwidth.) A suggested value for RTO is 3; TCP uses a more sophisticated scheme that tracks the variance as well as the average of the round-trip time. (FIXME: coalescing delay.)
The sender uses an adaptive congestion window to determine the maximum amount of data that can be in flight (ie sent but not yet acknowledged) at any time. The number of bytes in flight and the congestion window are modified when packets are transmitted, retransmitted or acknowledged. Specifically:
4) When a packet is first acknowledged, its total size is subtracted from the number of bytes in flight. If the connection is in slow start, ALPHA * size / MAX_PACKET_SIZE bytes are added to the congestion window, where 'size' is the total size of the acknowledged packet. If the connection is in congestion avoidance, ALPHA * size / MAX_PACKET_SIZE / cwnd bytes are added to the congestion window, where 'cwnd' is the current size of the congestion window in bytes. Thus the congestion window grows exponentially during slow start, and linearly during congestion avoidance, until a loss occurs. (The maximum size of the congestion window is FIXME bytes.)

Revision [1629]

Edited on 2006-12-24 17:30:38 by MichaelRogers [Unfinished]
Additions:
The sender **must not** transmit payload n+2^16 until payload n has been acknowledged. This limits the size of the sender's retransmission buffer and the size of the receiver's duplicate detection window, preventing denial-of-service attacks.
==Coalescing==
Deletions:
The sender **must not** transmit payload n+2^16 until payload n has been acknowledged. This limits the size of the sender's retransmission buffer and the size of the receiver's duplicate detection window, preventing DoS attacks.
==Coalescing===

Revision [1628]

The oldest known version of this page was created on 2006-12-24 17:29:25 by MichaelRogers [Unfinished]
Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki