4.6 Congestion Control
This specification provides a solution to deal with network congestion in the IOTA network. The congestion control algorithm described in this file decides which messages should be processed and gossiped to node's neighbors and in what order to do so.
Every network has to deal with its intrinsic limited resources in terms of bandwidth and node capabilities (CPU and storage). In this document, we present a congestion control algorithm to regulate the influx of messages in the network with the goal of maximizing throughput (messages/bytes per second) and minimizing delays. Furthermore, the following requirements must be satisfied:
- Consistency. If a message is written by one honest node, it shall be written by all honest nodes within some delay bound.
- Fairness. Nodes can obtain a share of the available throughput depending on their access Mana. Throughput is shared in such a way that an attempt to increase the allocation of any node necessarily results in the decrease in the allocation of some other node with an equal or smaller allocation (max-min fairness).
- Security. Malicious nodes shall be unable to interfere with either of the above requirements.
Further information can be found in our a paper Access Control for Distributed Ledgers in the Internet of Things: A Networking Approach.
The Congestion Control specification depends on the following specifications:
In this specification, we present the congestion control algorithm that shall be implemented by all IOTA nodes. Nodes cannot take any advantage by not following the protocol. Conversely, they may eventually be considered as malicious nodes and banned. Our algorithm has three core components:
- A scheduling algorithm which ensures fair access for all nodes according to their access Mana.
- A TCP-inspired algorithm for decentralized rate setting to efficiently utilize the available bandwidth while preventing large delays.
- A blacklisting policy to ban malicious nodes.
4.6.2 Congestion Control Algorithm
184.108.40.206 Outbox Management
Once the message has successfully passed the message parser checks and is solid, it is enqueued into the outbox for scheduling (see Section 2.4 - Data Flow). The outbox is logically split into several queues, each one corresponding to a different node issuing messages. In this section, we describe the operations of message enqueuing (and dequeuing) into (from) the outbox.
The enqueuing mechanism includes the following components:
- Classification. The mechanism identifies the queue where the message belongs to according to the node ID of the message issuer.
- Message enqueuing. The message is actually enqueued, queue is sorted by message timestamps in increasing order and counters are updated (e.g., counters for the total number of bytes in the queue).
- Message drop. In some circumstances, due to network congestion or to ongoing attacks, some messages shall be dropped to guarantee bounded delays and isolate attacker's messages. Specifically, a node shall drop messages in two situations:
- since buffers are of a limited size, if the total number of bytes in all queues exceeds a certain threshold, new incoming messages are dropped;
- to guarantee the security of the network, if a certain queue exceeds a given threshold, new incoming packets from that specific node ID will be dropped.
The dequeue mechanism includes the following components:
- Queue selection. A queue is selected according to round robin scheduling algorithm. In particular, we use a modified version of the deficit round robin (DRR) algorithm, and we describe it in Section 220.127.116.11 - Scheduler.
- Message dequeuing. The first message of the queue is dequeued, and list of active nodes is updated.
- Scheduler management. Scheduler counters and pointers are updated.
The most critical task is the scheduling algorithm which must guarantee that, for an honest node
node, the following requirements will be met:
node's messages will not accumulate indefinitely at any node (i.e., starvation is avoided), so the consistency requirement will be ensured.
node's fair share (according to its access Mana) of the network resources are allocated to it, guaranteeing the fairness requirement.
- Malicious nodes sending above their allowed rate will not interrupt
node's throughput, fulfilling the security requirement.
We remind the reader that the above requirements are described in Section 3.4.1 - Summary.
Although nodes in our setting are capable of more complex and customised behaviour than a typical router in a packet-switched network, our scheduler must still be lightweight and scalable due to the potentially large number of nodes requiring differentiated treatment. It is estimated that over 10,000 nodes operate on the Bitcoin network, and we expect that an even greater number of nodes are likely to be present in the IoT setting. For this reason, we adopt a scheduler based on Deficit Round Robin (DRR) (the Linux implementation of the FQ-CoDel packet scheduler, which is based on DRR, supports anywhere up to 65535 separate queues).
The DRR scans all non-empty queues in sequence. When a non-empty queue is selected, its priority counter (called deficit) is incremented by a certain value (called quantum). Then, the value of the deficit counter is a maximal amount of bytes that can be sent at this turn: if the deficit counter is greater than the weight of the message at the head of the queue, this message can be scheduled and the value of the counter is decremented by this weight. In our implementation, the quantum is proportional to node's access Mana and we add a cap on the maximum deficit that a node can achieve to keep the network latency low. It is also important to mention that the weight of the message can be assigned in such a way that specific messages can be prioritized (low weight) or penalized (large weight); by default, in our mechanism the weight is proportional to the message size measured in bytes. The weight of a message is set by the function
WorkCalculator(), and additional details can be found in Section 2.4 - Data Flow.
Here a fundamental remark: the network manager sets up a desired maximum (fixed) rate
SCHEDULING_RATE at which messages will be scheduled, computed in weight (see above) per second. This implies that every message is scheduled after a delay which is equal to the weight (size as default) of the latest scheduled message times the parameter
SCHEDULING_RATE. This rate mostly depends on the degree of decentralization desired: e.g., a larger rate leads to higher throughput but would leave behind slower devices which will fall out of sync.
18.104.22.168 Rate Setting
If all nodes always had messages to issue, i.e., if nodes were continuously willing to issue new messages, the problem of rate setting would be very straightforward: nodes could simply operate at a fixed, assured rate, sharing the total throughput according to the percentage of access Mana owned. The scheduling algorithm would ensure that this rate is enforceable, and that increasing delays or dropped messages are only experienced by misbehaving node. However, it is unrealistic that all nodes will always have messages to issue, and we would like nodes to better utilise network resources, without causing excessive congestion and violating any requirement.
We propose a rate setting algorithm inspired by TCP — each node employs additive increase, multiplicative decrease (AIMD) rules to update their issuance rate in response to congestion events. In the case of distributed ledgers, all message traffic passes through all nodes, contrary to the case of traffic typically found in packet switched networks and other traditional network architectures. Under these conditions, local congestion at a node is all that is required to indicate congestion elsewhere in the network. This observation is crucial, as it presents an opportunity for a congestion control algorithm based entirely on local traffic.
Our rate setting algorithm outlines the AIMD rules employed by each node to set their issuance rate. Rate updates for a node
node take place each time a new message is scheduled if the
node has a non-empty set of its own messages not yet scheduled. Node
node sets its own local additive-increase variable
localIncrease(node) based on its access Mana and on a global increase rate parameter
RATE_SETTING_INCREASE. An appropriate choice of
RATE_SETTING_INCREASE ensures a conservative global increase rate which does not cause problems even when many nodes increase their rate simultaneously. Nodes wait
RATE_SETTING_PAUSE seconds after a global multiplicative decrease parameter
RATE_SETTING_DECREASE, during which there are no further updates made, to allow the reduced rate to take effect and prevent multiple successive decreases. At each update,
node checks how many of its own messages are in its outbox queue, and responds with a multiplicative decrease if this number is above a threshold,
backoff(node), which is proportional to
node's access Mana. If the number of
node's messages in the outbox is below the threshold,
node's issuance rate is incremented by its local increase variable
22.214.171.124 Message Blocking and Blacklisting
If an incoming message made the outbox total buffer size to exceed its maximum capacity
MAX_BUFFER, the same message would be dropped. In our analysis, we set buffers to be large enough to accommodate traffic from all honest nodes.
Furthermore, to mitigate spamming actions from malicious nodes, we add an additional constraint: if
node's access Mana-scaled queue length (i.e., queue length divided by node's access Mana) exceeds a given threshold
MAX_QUEUE, any new incoming packet from
node will be dropped, hence the node is blacklisted. The attacker is blacklisted for a certain time
BLACKLIST_TIME during which no messages issued by
node can be added to the outbox. Please note that it is still possible to receive message from the attacker through solidification requests, which is important in order to guarantee the consistency requirement. Finally, when a node is blacklisted, the blacklister does not increase its own rate for a time
RATE_SETTING_QUARANTINE, to avoid errors in the perception of the current congestion level.
4.6.3 Algorithmic Details
126.96.36.199 Protocol Parameters
In line with the previous section, all nodes know the global variables described in Table 4.6.1.
|integer||clock time interval between subsequent executions of the function |
|float||global additive increase parameter|
|float||global multiplicative decrease parameter (larger than 1)|
|integer||waiting time before next |
|integer||waiting time before next |
|integer||maximum buffer size (in bytes)|
|float||maximum access Mana-scaled inbox length|
|float||maximum cap for accumulated deficit|
|float||maximum rate at which a node can be allowed to issue messages|
|integer||minimum amount of Mana needed to issue messages|
|integer||time interval during which no messages from blacklisted nodes are added to the outbox|
Table 4.6.1: Global constants.
188.8.131.52 Local Variables
Local variables are described in Table 4.6.2.
|float||issuance rate of |
|list||updated list of nodes having at least one message in the outbox queue (more details in Section 184.108.40.206 - Implementation)|
|queue||actual outbox queue where messages are ready to be scheduled (more details in Section 220.127.116.11 - Implementation)|
|nodeID||pointer to the specific queue where next message can be scheduled from|
|list||contains the up-to-date (at the time the vector is used) value of the access Mana given a certain |
|float||local threshold for rate setting's backoff|
|float||local additive increase parameter|
|list||list of timestamps indicating if a specific |
|integer||time interval during which rate setter is not updated|
|list||list of messages that |
Table 4.6.2: Local variables.
18.104.22.168 Built-in Functions
Pseudocodes introduced in the next section will use the built-in functions described in Table 4.6.3.
|measures the length of a data structure |
|add a new element |
|provides the weight of message |
|sort list |
|gives the list of parents of a message |
|current time computed with the local clock|
|process and gossip message |
|stop execution of a function for |
Table 4.6.3: Built-in functions.
The congestion control algorithm follows the solidification in the data flow: when a new message
msg arrives to the scheduler, the function
Enqueue(msg) will be triggered in order to properly add
msg to the outbox. At the same time, at regular intervals (given by
x is the latest scheduled message), the function
Schedule() picks a new message that has to be gossiped to neighbors and to be added to the local ledger. Simultaneously,
RateSetting() adjusts the message generation rate of
ownID according to the network congestion.
Enqueue(msg) adds a new message
msg into the outbox and updates the list of active nodes accordingly. The checks on blacklisting condition (
blacklisted[nodeID] == FALSE) and buffer size (
Len(bufferQueue) < MAX_BUFFER) may be moved to the parser checker for optimization purposes.
### upon arrival of a new message msg (having passed solidification) ###
nodeID = msg.nodeID
IF mana[nodeID] > MIN_MANA AND (blacklisted[nodeId] == 0 OR CurrentTime() - blacklisted[nodeID] > BLACKLIST_TIME)
blacklisted[nodeId] = 0
IF Len(bufferQueue) < MAX_BUFFER
IF activeNode[nodeID] != NULL
# other messages from nodeID are already in the queue
nodeQueue = activeNode[nodeID]
IF (Len(nodeQueue) + Len(msg))/mana[nodeID] < MAX_QUEUE
# append msg
# blacklist nodeID and pause rate setting updates
blacklisted[nodeID] = CurrentTime()
pauseUpdates = Max(pauseUpdates, RATE_SETTING_QUARANTINE)
# no other messages for nodeID are present in the buffer
activeNode[nodeID].deficit = MAX_DEFICIT
RateSetting() updates the rate
ownRate at which messages can be issued by the node. The maximum value that
ownRate can reach is
MAX_RATE. At the bootstrap, the value of
ownRate is initialized by the proportion of access Mana owned by the node times
# update issueing rate if no recent backoff
IF ownRate < MAX_RATE
# retrieve message queue of the same node
IF Len(bufferQueue[ownID]) / mana[ownID] > backoff
ownRate = ownRate / RATE_SETTING_DECREASE
pauseUpdates = Max(pauseUpdates, RATE_SETTING_PAUSE)
ownRate += RATE_SETTING_INCREASE * mana[ownID] / Sum(mana)
At regular intervals, i.e., every
x is the latest scheduled message, the function
Schedule() selects the next message to gossip and process, if at least one message exists in
bufferQueue. Otherwise, it returns
NULL and the scheduling slot is missed. The local variable
pauseUpdates is initialized to 0.
FUNCTION msg = Schedule()
IF Len(bufferQueue) > 0
# msg represents the message in the outbox
msg = bufferQueue[nextID].head
# point to a nodeId with enough deficit, having a valid message
WHILE activeNode[nextID].deficit < Weight(msg) OR msg.timestamp > CurrentTime() OR Parents(msg) have not been scheduled
activeNode[nextID].deficit += mana[nextID]
IF activeNode[nextID].deficit > MAX_DEFICIT
activeNode[nextID].deficit = MAX_DEFICIT
activeNode[nextID].deficit -= Weight(msg)
IF activeNode[nextID].deficit < 0
activeNode[nextID] = 0
# remove scheduled message from queue
# update list of active nodes
IF Len(bufferQueue[nextID]) == 0
# update own rate setting
IF pauseUpdates > 0
pauseUpdates -= 1
ELSE IF Len(messageWorker) > 0
Pause(SCHEDULING_RATE * WorkCalculator(msg))
In this section, we describe the main architectural components used to handle the outbox queue, that is
bufferQueue (see Image 4.6.4). The scope of this section is to provide an insight on how to efficiently implement the above pseudocode.
activeNode: it is a list which includes the node IDs of the nodes having at least one message in the outbox queue. Each node ID in the list points to its oldest message in the outbox buffer.
bufferQueue: it is the actual outbox queue. It is possible to build overlapping virtual queues (indicated by colors in the figure) to represent different queues per node. This data structure has a limited fixed size
MAX_BUFFER, and messages (in each queue) are sorted by timestamp.
Other information about the hardware implementation of similar scheduling algorithms can be found at this link.
Image 4.6.4: Proposed data structure for the implementation of the congestion control algorithm.
4.6.4 Optional and Future Optimizations
When the network has a high level of congestion, it may be difficult for an out-of-sync node to synchronize as most of its scheduling rate is consumed by new messages. Hence, it is nice to have a mechanism allowing to schedule messages faster to catch up with the rest of the network under special conditions.
Specifically, consider the following two scenarios:
- Node is bootstrapping.
syncStatusflag is set to
FALSE(see Section 4.2 - Timestamp).
In either of these scenarios, the node is very far behind the rest of the newtork. In this case, we suggest to bypass the DRR scheduler, and schedule solid old messages in FIFO order at the largest possible rate the node can process. We repeat that this feature is optional: while it reduces the time needed to synchronize, it is not strictly needed for the correct functioning of the congestion control algorithm.
22.214.171.124 Adaptive Minimum Access Mana
Nodes must hold a sufficient amount of access Mana (larger than
MIN_MANA) to be able to successfully issue new messages. We are currently investigating a way to adapt this threshold over time, depending on the current traffic congestion of the network.
126.96.36.199 Dynamic Scheduling Rate
In the current proposal, the throughput is preset by the network manager. This value takes into account nodes’ hardware as well as bandwidth capacity. Hardware improvement or protocol optimizations will not result in a performance improvement if the network manager does not change the throughput parameter
SCHEDULING_RATE. We are currently investigating a way to dynamically adapt the throughput according to the network and protocol characteristics based on neighbors health state.