diff options
Diffstat (limited to 'spec/tor-spec/flow-control.md')
| -rw-r--r-- | spec/tor-spec/flow-control.md | 64 |
1 files changed, 39 insertions, 25 deletions
diff --git a/spec/tor-spec/flow-control.md b/spec/tor-spec/flow-control.md index e0f7ad1..8c3bcce 100644 --- a/spec/tor-spec/flow-control.md +++ b/spec/tor-spec/flow-control.md @@ -33,13 +33,14 @@ information. See [proposal 111] for details. ## Link padding{#link-padding} Link padding can be created by sending PADDING or VPADDING cells -along the connection; relay cells of type "DROP" can be used for -long-range padding. The payloads of PADDING, VPADDING, or DROP -cells are filled with padding bytes. See [Cell Packet format](./cell-packet-format.md#cell-packet-format). +along the connection; relay messages of type "DROP" can be used for +long-range padding. The payloads of PADDING cells, VPADDING cells, or DROP +message are filled with padding bytes. +See [Cell Packet format](./cell-packet-format.md#cell-packet-format). If the link protocol is version 5 or higher, link level padding is enabled as per padding-spec.txt. On these connections, clients may -negotiate the use of padding with a CELL_PADDING_NEGOTIATE command +negotiate the use of padding with a PADDING_NEGOTIATE command whose format is as follows: ```text @@ -69,58 +70,70 @@ For more details on padding behavior, see padding-spec.txt. ## Circuit-level flow control To control a circuit's bandwidth usage, each OR keeps track of two -'windows', consisting of how many RELAY_DATA cells it is allowed to +'windows', consisting of how many DATA-bearing relay cells it is allowed to originate or willing to consume. +(For the purposes of flow control, +we call a relay cell "DATA-bearing" +if it holds a DATA relay message. +Note that this design does _not_ limit relay cells that don't contain +a DATA message; +this limitation may be addressed in the future.) + These two windows are respectively named: the package window (packaged for transmission) and the deliver window (delivered for local streams). Because of our leaky-pipe topology, every relay on the circuit has a pair of windows, and the OP has a pair of windows for every relay on the -circuit. These windows do not apply to relayed cells, however, and a relay -that is never used for streams will never decrement its window or cause the +circuit. +These windows apply only to _originated_ and _consumed_ cells. +They do not, however, apply to _relayed_ cells, +and a relay +that is never used for streams will never decrement its windows or cause the client to decrement a window. Each 'window' value is initially set based on the consensus parameter -'circwindow' in the directory (see dir-spec.txt), or to 1000 data cells if +'circwindow' in the directory (see dir-spec.txt), or to 1000 +DATA-bearing relay cells if no 'circwindow' value is given. In each direction, cells that are not RELAY_DATA cells do not affect the window. -An OR or OP (depending on the stream direction) sends a RELAY_SENDME cell -to indicate that it is willing to receive more cells when its deliver +An OR or OP (depending on the stream direction) sends a RELAY_SENDME message +to indicate that it is willing to receive more DATA-bearing cells when its deliver window goes down below a full increment (100). For example, if the window started at 1000, it should send a RELAY_SENDME when it reaches 900. When an OR or OP receives a RELAY_SENDME, it increments its package window by a value of 100 (circuit window increment) and proceeds to sending the -remaining RELAY_DATA cells. +remaining DATA-bearing cells. If a package window reaches 0, the OR or OP stops reading from TCP connections for all streams on the corresponding circuit, and sends no more -RELAY_DATA cells until receiving a RELAY_SENDME cell. +DATA-bearing cells until receiving a RELAY_SENDME message. If a deliver window goes below 0, the circuit should be torn down. Starting with tor-0.4.1.1-alpha, authenticated SENDMEs are supported (version 1, see below). This means that both the OR and OP need to remember -the rolling digest of the cell that precedes (triggers) a RELAY_SENDME. +the rolling digest of the relay cell that precedes (triggers) a RELAY_SENDME. This can be known if the package window gets to a multiple of the circuit window increment (100). When the RELAY_SENDME version 1 arrives, it will contain a digest that MUST match the one remembered. This represents a proof that the end point of the -circuit saw the sent cells. On failure to match, the circuit should be torn +circuit saw the sent relay cells. On failure to match, the circuit should be torn down. To ensure unpredictability, random bytes should be added to at least one -RELAY_DATA cell within one increment window. In other word, every 100 cells -(increment), random bytes should be introduced in at least one cell. +RELAY_DATA cell within one increment window. In other word, +at every 100 data-bearing cells (increment), +random bytes should be introduced in at least one cell. <a id="tor-spec.txt-7.3.1"></a> -### SENDME Cell Format +### SENDME Message Format -A circuit-level RELAY_SENDME cell always has its StreamID=0. +A circuit-level RELAY_SENDME message always has its StreamID=0. An OR or OP must obey these two consensus parameters in order to know which version to emit and accept. @@ -151,11 +164,11 @@ DATA_LEN and how to handle it. The recognized values are: DIGEST \[20 bytes\] ```text - If the DATA_LEN value is less than 20 bytes, the cell should be + If the DATA_LEN value is less than 20 bytes, the message should be dropped and the circuit closed. If the value is more than 20 bytes, then the first 20 bytes should be read to get the DIGEST value. - The DIGEST is the rolling digest value from the RELAY_DATA cell that + The DIGEST is the rolling digest value from the DATA-bearing relay cell that immediately preceded (triggered) this RELAY_SENDME. This value is matched on the other side from the previous cell sent that the OR/OP must remember. @@ -173,13 +186,14 @@ from the consensus), the circuit should be torn down. ## Stream-level flow control -Edge nodes use RELAY_SENDME cells to implement end-to-end flow +Edge nodes use RELAY_SENDME messages to implement end-to-end flow control for individual connections across circuits. Similarly to -circuit-level flow control, edge nodes begin with a window of cells +circuit-level flow control, edge nodes begin with a window of +DATA-bearing cells (500) per stream, and increment the window by a fixed value (50) -upon receiving a RELAY_SENDME cell. Edge nodes initiate RELAY_SENDME -cells when both a) the window is \<= 450, and b) there are less than +upon receiving a RELAY_SENDME message. Edge nodes initiate RELAY_SENDME +messages when both a) the window is \<= 450, and b) there are less than ten cell payloads remaining to be flushed at that edge. -Stream-level RELAY_SENDME cells are distinguished by having nonzero +Stream-level RELAY_SENDME messages are distinguished by having nonzero StreamID. They are still empty; the body still SHOULD be ignored. |