Understanding SEQ frames:
BEEP flow control and bandwidth management

1. Introduction

On this article is explained how SEQ frames relates to BEEP, why they are required, how they are used, and how help BEEP to implement a required flow control mechanism at a channel level.

It is also explained the head-of-line problem and how SEQ frames allow BEEP framework to avoid it.

At the end of the article there are also found some examples and a short FAQ with common questions and additional resources.

2. Which is the purpose of SEQ frames

Inside BEEP protocol, it is possible to open several channels, and exchange data at the same time, with the same or different profiles. This is a great feature for many reasons. However, this requires an special treatment to avoid several problems that may arise around flow control.

One of these problems that every application protocol have to solve, uless they turn a blind eye, which is quite common, is the flow control. Flow control allow network entities to control, and notify its partner which is the status of its receiving buffers, that are used to serve application payload to upper levels. It also allows to avoid that a particular send operation do not monopolize the transmission chanel so all operations can progress at the same time, or at the policy rate previously established.

Under some situations, an entity could not be able to process more data, that is, to receive more, because either the application level is not reading its buffer, or the network entity doesn't have the enough capacity to process and deliver incoming information.

But, "Does not TCP already handle this?". Yes, you are right, TCP implements a flow control mechanism, based on ACK datagrams. However, this mechanism doesn't fit BEEP because it is implemented for the whole TCP connection, which in turn supports the BEEP session, and over this BEEP session you have different independent channels running and exchaging data at the same time.

TCP flow control was designed for a single entity to be consuming payload data, in other words, for only one logical channel to be working at the same time.

Because BEEP allows to have several logical channels exchanging data, there are several buffers to control, and it is required a mechanism that allow BEEP entities to implement flow control and buffer status notification at channel level.

As for TCP protocol, the ACK notification is used to implement flow control. In the case of BEEP, SEQ frames are used to implement such flow control mechanism for every channel.

However, SEQ frames's main purpose is not just implement a per channel flow control mechanism but also to solve a problem which is commonly referred to as "head of line".

3. The head of line problem

The head-of-line affects to each protocol in a different way but, the final result to the end user is that bandwidth allocated by the logical connection is affected in a way that only one big request is properly being served but, until it finish, previous request are stuck.

This is because, on many protocols, once a request was performed, there is no way to stop i in the middle of a response being received, to look around and to make a better decision about what request are waiting to be served, what is the priority policy to apply it to current status, etc.

As an example, for the ubiquitous HTTP protocol, [Gettys & Freier] show us that the head-of-line problem appear when several request are multiplexed into a single HTTP connection. Because of that, inside HTTP, every request performed have to wait until a complete reply is received, multiplexing several request could cause an very bad effect where only one request is being served, maybe because it is downloading a huge file or because the server reply is unresponsive, and previous waiting replies are never served.

In the case of BEEP, SEQ frames allows BEEP peers to totally control how replies are received, enabling them to, for example, freeze all incoming replies being received because:

  • A really high priority channel is receiving data.
  • The user application, through its API with its BEEP implementation, has decided to stop incoming data for a certain group of channel, maybe those selected due to a SASL identity negotiated, a profile criteria, or ...
  • The channels frozen have consumed all available bandwidth assigned to them until the next round.

SEQ frame definition is an important part inside the BEEP protocol because it enables peers to properly implement several appealing features related to the flow control, bandwidth management, channel priorities, but also to solve a big problem such as the head-of-line.

4. Features that provide the SEQ frame

SEQ frames not only allows to perform flow control for channel running inside a BEEP session. It also allows to implement bandwidth management and channel priority.

SEQ frames are mainly designed to enable BEEP peers to be able to take decisions about how data is received in the middle of a transmission, avoiding the head-of-line problem.

5. How SEQ frames works

Later on, we will explain with more details how SEQ frame works. For now, let's see how this special frame looks, its fields, etc. Here is a diagram:

SEQ frame diagram

As we can see, the SEQ frame is composed by a BEEP frame header, ended with a trailing "\r\n" (hexadecimal values "\x0D\x0A"), containing a channel number, which this frame applies to, followed by two values, ackno and window, which, in conjunction, are used to figure out and notify buffer status.

SEQ frames are generated by BEEP peers to report to its partner, current reception buffer's status for a particular channel. This information is reported using the ackno value as the seqno value of an already received octet, followed by the window value, representing the amount of bytes that is prepared to accept starting from previous value.

One thing to keep in mind is that: "a SEQ frame represents the status of a channel at a particular time, even knowing such status could change once the SEQ frame was received."

SEQ frames could be read as follows:

  • As BEEP peers, when we receive a SEQ frame, our BEEP partner it is telling us: "At the time I've received the byte stream identified by ackno I'm able to receive an amount of octets equal to window".
  • Or, as a BEEP peer wanting to notify current channel buffer status: "I'm notifying you that you can send more octets within the >seqno stream range starting from ackno up to ackno + window."

Knowing previous concepts, BEEP peers are required to process and generate SEQ frames to control how messages, splitted into frames, are transmitted over channels to finally reach its destination.

If a BEEP peer doesn't follow indications advertised by a SEQ frame received, it is considered a protocol violation, and the BEEP session is simply dropped.

As a side effect, if a BEEP peer doesn't generate SEQ frames for a particular channel, the channel will stale once the initial buffer is exhausted. This initial value is bound to 4096 octets. This means that, BEEP peers, without receiving a SEQ frame, will be able to send up to 4096 bytes, identified by the seqno range {0..4095}. Beyond that limit, and supposing no SEQ frame is received, the channel is stale.

6. Example: SEQ frame in action

Here is a set of graphical examples explaining how SEQ frames modify current buffer status, and what happens when a SEQ frame is generated.

1) Channel 1 is created, under some profile, and its initial, implicit accepted, buffer size for incoming data, is 4096.

SEQ frame example 1: 01

2) Channel 1 receives a frame with a payload of 275 octets, so, the incoming buffer gets to the following state:

SEQ frame example 1: 02

3) Channel 1 doesn't generate a SEQ frame and receives a new frame containing exactly 3821 octets. So the channel is stale, making no further data to be received:

SEQ frame example 1: 03

4) Channel 1 now gets to the following state:

SEQ frame example 1: 04

7. Common SEQ frame FAQ

Q. Is the SEQ frame a way to report remote peer that it shouldn't send frames larger than the size advertised?

No. SEQ frames aren't used to make remote peer to split messages into frames equal or smaller than the value advertised. SEQ frames are used to perform flow control and channel bandwidth.

Although it may seems that this is the purpose, because under some circumstances this is what happening, SEQ frame advertised information must be understood as the maximum amount of data that it is possible to send, without causing a protocol violation, until a new SEQ frame is received extending the window size, that may (or may not) be equal to previous windows sizes.

Q. What happens if a BEEP peer needs to send a message larger than the buffer size available that is either implicitly accepted or figured out according to the last SEQ frame received (ackno and window values)?

BEEP peers must be able to handle incoming SEQ frames and to generate SEQ frames during the transmission of a message.

This means that, if there is only available a 4096 buffer size, and the message to be sent is 10000 bytes sized, then:

  • The BEEP sending peer should send an initial frame with 4096 payload size, setting the more flag to true (*), and wait until the remote peer sends a SEQ frame extending the window size.
  • Once a SEQ frame is received, for the channel being used for the sending operation, a new frame (or several frames) is sent, using as maximum seqno value, the one defined by the limit ackno + window.

Q. Is there are way a to reduce the receiving window size?

Yes. But it can't be done over the advertised values. This means that, if a BEEP peer sends a SEQ frame, advertising that it is willing to accept some amount of octets (window SEQ value), starting from a given ackno value (representing an already received octet identified by a seqno), then it can't deny receiving those octet, or perform any bandwidth or window resizing operation.

Then, for the next SEQ frames to be sent, advertised values could be reduced, including the frequency used to report SEQ frames.

As a rule: "The receiving window, advertised either due to previous SEQ frame received or implicit initial values, never shrunk by a SEQ frame received. The window is only, and always, shrunk as the result of receiving data."

Which is the same as: "The receiving window, is only, and always, extended by sending new SEQ frames, reporting willingness to receive more octets."

8. Resources

9. Acknowledgements

This article is mainly based on the discussions that took place at the beepcore.org community mailing list, in special, gratefully thanks for its comments goes to: Peter Hall, David Blacka, David Kramer and Marshall T. Rose.

An special mention for Marshall T. Rose who have provided useful comments and reference to other documents explaining the head-of-line issue.