3.3 Sequence Numbers

A fundamental notion in the design is that every octet of data sent over a TCP connection has a sequence number. Since every octet is sequenced, each of them can be acknowledged. The acknowledgment mechanism employed is cumulative so that an acknowledgment of sequence number X indicates that all octets up to but not including X have been received. This mechanism allows for straight-forward duplicate detection in the presence of retransmission. Numbering of octets within a segment is that the first data octet immediately following the header is the lowest numbered, and the following octets are numbered consecutively.

It is essential to remember that the actual sequence number space is finite, though very large. This space ranges from 0 to 2**32 - 1. Since the space is finite, all arithmetic dealing with sequence numbers must be performed modulo 2**32. This unsigned arithmetic preserves the relationship of sequence numbers as they cycle from 2**32 - 1 to 0 again. There are some subtleties to computer modulo arithmetic, so great care should be taken in programming the comparison of such values. The symbol "=<" means "less than or equal" (modulo 2**32).

The typical kinds of sequence number comparisons which the TCP must perform include:

    (a)  Determining that an acknowledgment refers to some sequence
         number sent but not yet acknowledged.

    (b)  Determining that all sequence numbers occupied by a segment
         have been acknowledged (e.g., to remove the segment from a
         retransmission queue).

    (c)  Determining that an incoming segment contains sequence numbers
         which are expected (i.e., that the segment "overlaps" the
         receive window).

In response to sending data the TCP will receive acknowledgments. The following comparisons are needed to process the acknowledgments.

    SND.UNA = oldest unacknowledged sequence number

    SND.NXT = next sequence number to be sent

    SEG.ACK = acknowledgment from the receiving TCP (next sequence
              number expected by the receiving TCP)

    SEG.SEQ = first sequence number of a segment

    SEG.LEN = the number of octets occupied by the data in the segment
              (counting SYN and FIN)

    SEG.SEQ+SEG.LEN-1 = last sequence number of a segment

A new acknowledgment (called an "acceptable ack"), is one for which the inequality below holds:

    SND.UNA < SEG.ACK =< SND.NXT

A segment on the retransmission queue is fully acknowledged if the sum of its sequence number and length is less or equal than the acknowledgment value in the incoming segment.

When data is received the following comparisons are needed:

    RCV.NXT = next sequence number expected on an incoming segments, and
        is the left or lower edge of the receive window

    RCV.NXT+RCV.WND-1 = last sequence number expected on an incoming
        segment, and is the right or upper edge of the receive window

    SEG.SEQ = first sequence number occupied by the incoming segment

    SEG.SEQ+SEG.LEN-1 = last sequence number occupied by the incoming
        segment

A segment is judged to occupy a portion of valid receive sequence space if

    RCV.NXT =< SEG.SEQ < RCV.NXT+RCV.WND

or

    RCV.NXT =< SEG.SEQ+SEG.LEN-1 < RCV.NXT+RCV.WND

The first part of this test checks to see if the beginning of the segment falls in the window, the second part of the test checks to see if the end of the segment falls in the window; if the segment passes either part of the test it contains data in the window.

Actually, it is a little more complicated than this. Due to zero windows and zero length segments, we have four cases for the acceptability of an incoming segment:

    Segment Receive  Test
    Length  Window
    ------- -------  -------------------------------------------

       0       0     SEG.SEQ = RCV.NXT

       0      >0     RCV.NXT =< SEG.SEQ < RCV.NXT+RCV.WND

      >0       0     not acceptable

      >0      >0     RCV.NXT =< SEG.SEQ < RCV.NXT+RCV.WND
                  or RCV.NXT =< SEG.SEQ+SEG.LEN-1 < RCV.NXT+RCV.WND

Note that when the receive window is zero no segments should be acceptable except ACK segments. Thus, it is be possible for a TCP to maintain a zero receive window while transmitting data and receiving ACKs. However, even when the receive window is zero, a TCP must process the RST and URG fields of all incoming segments.

We have taken advantage of the numbering scheme to protect certain control information as well. This is achieved by implicitly including some control flags in the sequence space so they can be retransmitted and acknowledged without confusion (i.e., one and only one copy of the control will be acted upon). Control information is not physically carried in the segment data space. Consequently, we must adopt rules for implicitly assigning sequence numbers to control. The SYN and FIN are the only controls requiring this protection, and these controls are used only at connection opening and closing. For sequence number purposes, the SYN is considered to occur before the first actual data octet of the segment in which it occurs, while the FIN is considered to occur after the last actual data octet in a segment in which it occurs. The segment length (SEG.LEN) includes both data and sequence space occupying controls. When a SYN is present then SEG.SEQ is the sequence number of the SYN.

Initial Sequence Number Selection

The protocol places no restriction on a particular connection being used over and over again. A connection is defined by a pair of sockets. New instances of a connection will be referred to as incarnations of the connection. The problem that arises from this is -- "how does the TCP identify duplicate segments from previous incarnations of the connection?" This problem becomes apparent if the connection is being opened and closed in quick succession, or if the connection breaks with loss of memory and is then reestablished.

To avoid confusion we must prevent segments from one incarnation of a connection from being used while the same sequence numbers may still be present in the network from an earlier incarnation. We want to assure this, even if a TCP crashes and loses all knowledge of the sequence numbers it has been using. When new connections are created, an initial sequence number (ISN) generator is employed which selects a new 32 bit ISN. The generator is bound to a (possibly fictitious) 32 bit clock whose low order bit is incremented roughly every 4 microseconds. Thus, the ISN cycles approximately every 4.55 hours. Since we assume that segments will stay in the network no more than the Maximum Segment Lifetime (MSL) and that the MSL is less than 4.55 hours we can reasonably assume that ISN's will be unique.

For each connection there is a send sequence number and a receive sequence number. The initial send sequence number (ISS) is chosen by the data sending TCP, and the initial receive sequence number (IRS) is learned during the connection establishing procedure.

For a connection to be established or initialized, the two TCPs must synchronize on each other's initial sequence numbers. This is done in an exchange of connection establishing segments carrying a control bit called "SYN" (for synchronize) and the initial sequence numbers. As a shorthand, segments carrying the SYN bit are also called "SYNs". Hence, the solution requires a suitable mechanism for picking an initial sequence number and a slightly involved handshake to exchange the ISN's.

The synchronization requires each side to send it's own initial sequence number and to receive a confirmation of it in acknowledgment from the other side. Each side must also receive the other side's initial sequence number and send a confirming acknowledgment.

    1) A --> B  SYN my sequence number is X
    2) A <-- B  ACK your sequence number is X
    3) A <-- B  SYN my sequence number is Y
    4) A --> B  ACK your sequence number is Y

Because steps 2 and 3 can be combined in a single message this is called the three way (or three message) handshake.

A three way handshake is necessary because sequence numbers are not tied to a global clock in the network, and TCPs may have different mechanisms for picking the ISN's. The receiver of the first SYN has no way of knowing whether the segment was an old delayed one or not, unless it remembers the last sequence number used on the connection (which is not always possible), and so it must ask the sender to verify this SYN. The three way handshake and the advantages of a clock-driven scheme are discussed in [3].

Knowing When to Keep Quiet

To be sure that a TCP does not create a segment that carries a sequence number which may be duplicated by an old segment remaining in the network, the TCP must keep quiet for a maximum segment lifetime (MSL) before assigning any sequence numbers upon starting up or recovering from a crash in which memory of sequence numbers in use was lost. For this specification the MSL is taken to be 2 minutes. This is an engineering choice, and may be changed if experience indicates it is desirable to do so. Note that if a TCP is reinitialized in some sense, yet retains its memory of sequence numbers in use, then it need not wait at all; it must only be sure to use sequence numbers larger than those recently used.

The TCP Quiet Time Concept

    This specification provides that hosts which "crash" without
    retaining any knowledge of the last sequence numbers transmitted on
    each active (i.e., not closed) connection shall delay emitting any
    TCP segments for at least the agreed Maximum Segment Lifetime (MSL)
    in the internet system of which the host is a part.  In the
    paragraphs below, an explanation for this specification is given.
    TCP implementors may violate the "quiet time" restriction, but only
    at the risk of causing some old data to be accepted as new or new
    data rejected as old duplicated by some receivers in the internet
    system.

    TCPs consume sequence number space each time a segment is formed and
    entered into the network output queue at a source host. The
    duplicate detection and sequencing algorithm in the TCP protocol
    relies on the unique binding of segment data to sequence space to
    the extent that sequence numbers will not cycle through all 2**32
    values before the segment data bound to those sequence numbers has
    been delivered and acknowledged by the receiver and all duplicate
    copies of the segments have "drained" from the internet.  Without
    such an assumption, two distinct TCP segments could conceivably be
    assigned the same or overlapping sequence numbers, causing confusion
    at the receiver as to which data is new and which is old.  Remember
    that each segment is bound to as many consecutive sequence numbers
    as there are octets of data in the segment.

    Under normal conditions, TCPs keep track of the next sequence number
    to emit and the oldest awaiting acknowledgment so as to avoid
    mistakenly using a sequence number over before its first use has
    been acknowledged.  This alone does not guarantee that old duplicate
    data is drained from the net, so the sequence space has been made
    very large to reduce the probability that a wandering duplicate will
    cause trouble upon arrival.  At 2 megabits/sec. it takes 4.5 hours
    to use up 2**32 octets of sequence space.  Since the maximum segment
    lifetime in the net is not likely to exceed a few tens of seconds,
    this is deemed ample protection for foreseeable nets, even if data
    rates escalate to l0's of megabits/sec.  At 100 megabits/sec, the
    cycle time is 5.4 minutes which may be a little short, but still
    within reason.

    The basic duplicate detection and sequencing algorithm in TCP can be
    defeated, however, if a source TCP does not have any memory of the
    sequence numbers it last used on a given connection. For example, if
    the TCP were to start all connections with sequence number 0, then
    upon crashing and restarting, a TCP might re-form an earlier
    connection (possibly after half-open connection resolution) and emit
    packets with sequence numbers identical to or overlapping with
    packets still in the network which were emitted on an earlier
    incarnation of the same connection.  In the absence of knowledge
    about the sequence numbers used on a particular connection, the TCP
    specification recommends that the source delay for MSL seconds
    before emitting segments on the connection, to allow time for
    segments from the earlier connection incarnation to drain from the
    system.

    Even hosts which can remember the time of day and used it to select
    initial sequence number values are not immune from this problem
    (i.e., even if time of day is used to select an initial sequence
    number for each new connection incarnation).

    Suppose, for example, that a connection is opened starting with
    sequence number S.  Suppose that this connection is not used much
    and that eventually the initial sequence number function (ISN(t))
    takes on a value equal to the sequence number, say S1, of the last
    segment sent by this TCP on a particular connection.  Now suppose,
    at this instant, the host crashes, recovers, and establishes a new
    incarnation of the connection. The initial sequence number chosen is
    S1 = ISN(t) -- last used sequence number on old incarnation of
    connection!  If the recovery occurs quickly enough, any old
    duplicates in the net bearing sequence numbers in the neighborhood
    of S1 may arrive and be treated as new packets by the receiver of
    the new incarnation of the connection.

    The problem is that the recovering host may not know for how long it
    crashed nor does it know whether there are still old duplicates in
    the system from earlier connection incarnations.

    One way to deal with this problem is to deliberately delay emitting
    segments for one MSL after recovery from a crash- this is the "quite
    time" specification.  Hosts which prefer to avoid waiting are
    willing to risk possible confusion of old and new packets at a given
    destination may choose not to wait for the "quite time".
    Implementors may provide TCP users with the ability to select on a
    connection by connection basis whether to wait after a crash, or may
    informally implement the "quite time" for all connections.
    Obviously, even where a user selects to "wait," this is not
    necessary after the host has been "up" for at least MSL seconds.

    To summarize: every segment emitted occupies one or more sequence
    numbers in the sequence space, the numbers occupied by a segment are
    "busy" or "in use" until MSL seconds have passed, upon crashing a
    block of space-time is occupied by the octets of the last emitted
    segment, if a new connection is started too soon and uses any of the
    sequence numbers in the space-time footprint of the last segment of
    the previous connection incarnation, there is a potential sequence
    number overlap area which could cause confusion at the receiver.