IEN-74










                        Sequence Number Arithmetic



                            William W. Plummer


                       Bolt Beranek and Newman, Inc.
                             50 Moulton Street
                           Cambridge MA   02138


                             21 September 1978

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


1.      Introduction

TCP deals with 32-bit numbers for sequencing  and  acknowledging  data.   A
basic  concept  is  that  of  a "window", a range of sequence numbers which
begins at a "left" pointer and ends at a "right" pointer.  Because a window
may contain sequence number zero, deciding whether a given number is within
a window is somewhat complicated.  This paper describes some techniques for
dealing with sequence numbers as they apply to TCP.


2.      Representation

The space of 2**32 sequence numbers will be shown as a (rough) circle:


                          0
                          | 2**32 - 1
                        .....
                       .     .
        Increasing |  .       .
        Numbers    |  .       .
                   V  .       .
                       .     .
                        .....

Segments of sequence numbers will be shown as:

                ........************.........>
                                           Increasing numbers

                        ^           ^
                        |           |
                      Left         Right

Note that Left is the the first number within the segment.   Right  is  not
included.  That is, the segment is semi-open.  If Left = Right, the segment
is considered to have zero length, not 2**32.



3.      The CheckWindow Function


Because the sequence number space is actually a ring and arithmetic is done
modulo  2**32, there is no concept of one sequence number being greater (or
less) than  another.   The  fundamental  function  for  comparing  sequence
numbers  is CheckWindow(Left, Sequence, Right).  This function returns true
if Sequence is contained in the semi-open segment between Left  and  Right.


                                   - 1 -

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


For  machines  with  word  sizes  greater  than  32-bits  or using unsigned
arithmetic on 32-bit machines, the definition of CheckWindow is:

        CheckWindow(L, S, R) := (L le R) =>
                                        L le S and S lt R  ,
                                  not ( R le S and S lt L)

The second branch of the conditional is expressed in a way that it  is  the
complement of the first branch when  L  and  R are interchanged.  Advantage
is  taken of this symmetry in the PDP-10 code which implements CheckWindow.
Otherwise the second branch may be expressed as  (R gt S) or (S ge L).

The first branch of the conditional is explained by the following  diagram:

                           0
                           | 2**32 - 1
                           |
                           |oooo
                         xxx    o
                        x  |     o
                       x .....    o
                      x .     .    o
                     x .       .    o
                     x .       .    o <--- Right
        Left --> o   x *       * x  o
                 o   x  *     *  x  o
                  o   x  *****  x  o
                   o   x       x  o
                    o   xxxxxxx  o
                     o          o
                      oooooooooo

        Key:    ......  Basic sequence space

                ******  Segment between Left and Right

                xxxxxx  Sequence space where Sequence lt Right

                oooooo  Sequence space where Sequence ge Left











                                   - 2 -

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


The  second branch of the conditional is the case where the segment crosses
zero:
                          0
                          | 2**32 - 1
                          |
                          |oooo
                       xxxx    o
                      x   |     o
                     x  *****    o
                    x  *     *    o
                    x *       *   o
                    x *       *   o
        Right -->     .       *   o  <-- Left
                       .     .
                        .....


        Key:    .....   Sequence space

                *****   Segment between Left and Right

                ooooo   Sequence numbers ge Left

                xxxxx   Sequence numbers lt Right


A useful identity is:  CheckWindow(L, S, R) =  not  CheckWindow(R,  S,  L).
This  says  that  either   S  is in the segment between  L  and  R or it is
not.




4.      OverLap(L1, R1, L2, R2)

OverLap(L1, R1, L2, R2)  is a predicate which tells if the two segments  L1
to  R1   and   L2  to R2  have at least one point in common.  If an overlap
exists, then one segment must have its Left end within the other:

        OverLap(L1, R1, L2, R2) :=

         CheckWindow(L1, L2, R1) or CheckWindow(L2, L1, R2)

Either  L2  is within segment one or it is not.  So either  CheckWindow(L1,
L2, R1)  or  not CheckWindow(L2, L1, R2)  is true.  In the first case there
is  an overlap even if it is just at the point  L2.  The second term can be
rewritten:



                                   - 3 -

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


        not CheckWindow(L2, L1, R2)  =  CheckWindow(R2, L1, L2).

Since L2 is outside segment one, it is the position of R2 which  determines
whether an overlap exists.  R2 can be either between L2  and  L1  or it can
be   between    L1   and   L2.   Thus,  there  are  two  subcases:   either
CheckWindow(L2, R2, L1)  or  CheckWindow(L1, R2, L2) must be true.  In  the
first  case  there  is no overlap and segment one does not contain  R2.  If
the first case is not true then the second case must be  since  it  is  the
complement of the first with the first and third arguments switched.



5.      Include(L1, R1, L2, R2)


Include  is  true if segment one includes all of segment two.  This is true
only if the complement of segment one does not contain any of segment  two.

        Include(L1, R1, L2, R2) := not Overlap(R1, L1, L2, R2)

                = CheckWindow(L1, L2, R1) and CheckWindow(R2, R1, L2)

The  expansion  states  that   L2   must  lie  in  segment one and that the
complement of segment two must contain the right end of segment one.



6.      Uses Within a TCP

The functions CheckWindow, Overlap, and Include have many uses  within  the
TCP.   A few of these are described below.  Some definitions are needed.  A
TCB contains a Send.Left cell, a Send.Window, and Send.Sequence  having  to
do with packet generation.  Send.Right does not exist explicitly but may be
computed by adding Send.Left and Send.Window (mod 2**32).

The  receive side of a connection has the cells Recv.Left and Recv.Window .
Again, Recv.Right may be easily computed.

Each packet has its sequence number Pkt.Seq and an  acknowledgement  number
Pkt.AckSeq.   The number called Pkt.End may be computed by counting one for
each control bit and data byte in the packet and adding this to Pkt.Seq mod
2**32.  Note that Pkt.End is actually the  sequence  number  following  the
packet.   Currently  only SYN and FIN occupy sequence space and these occur
only at the start and end of a connection; otherwise, all sequence space is
occupied by data only.





                                   - 4 -

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


These variables define several segments.  The send window between Send.Left
and Send.Right,  the receive window between Recv.Left and  Recv.Right,  and
the  packet segment between Pkt.Seq and Pkt.End.  All of these segments are
semi-open and are suitable for manipulation  by  the  previously  described
functions such as CheckWindow.

The  Retransmitter uses OverLap(Send.Left, Send.Right, Pkt.Seq, Pkt.End) to
tell if a packet has anything transmittable in it.   Note  that  Send.Right
may  lie within the segment between Send.Left and Send.Seq.  This indicates
that the window shrank due to Send.Right having moved "backwards".  In this
case  data  between  Send.Right   and   Send.Seq   is   (temporarily)   not
retransmittable.

The  InputProcessor  makes  heavy  use  of all of the functions.  The basic
acceptance test for  packets  arriving  on  an  ESTABLISHED  connection  is
OverLap(Recv.Left, Recv.Right, Pkt.Seq, Pkt.End).  If this is not true, the
packet  is  assumed  to  be  either from the future or a duplicate from the
past.

Processing the Acknowledgement field of a packet involves  a  scan  of  the
retransmission  queue to see which packets may be deleted.  For each packet
on the queue CheckWindow(Send.Left, Pkt.End-1, Acknowledgement) is true  if
the  packet has been acknowledged.  Pkt.End-1 is the sequence number of the
last byte in the packet.  Note that any packet on the retransmission  queue
must  occupy  at  least  one  sequence number and therefore no special case
checks must be made worry about Pkt.End-1 being less than Pkt.Seq .

TCP11  sends  each  newly   typed   character   in   a   separate   packet.
Retransmissions carry all unacknowledged data.  TCP for the PDP-10/20 tries
to  minimize internal storage requirements by saving a retransmitted packet
and releasing the storage for the original transmissions.  Given a incoming
packet InPkt, the following test is performed against  each  packet  queued
for   action  by  the  buffer  reassembler:  Include(InPkt.Seq,  InPkt.End,
QdPkt.Seq, QdPkt.End) means that the incoming packet contains at  least  as
much as the already queued packet and that the latter may be released.















                                   - 5 -

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


7.      Sample Code

The  following  routines  have  been  excerpted from the hand coded TCP for
TENEX and TOPS20.  They have been included here to provide an indication of
complexity.  Note that the PDP-10 has a 36-bit word size  and  thus  32-bit
numbers  are  always  positive.   Operations  such  as CAM which are signed
compares on 36-bit quantites are unsigned operations on 32-bit  numbers  as
required.


; CheckWindow(Left, Sequence, Right)

; Test "Sequence" to see if it is between "Left" (inclusive) and "Right"
; (not incl.).  Sequence numbers are  modulo MAXSEQ and are always
; positive when represented in a 36-bit word.

;T1/    Left
;T2/    Sequence
;T3/    Right
;
;       CALL CHKWND
;Ret+1: always.  T1 non-zero if Sequence is in the window

CHKWND::TEMP <VAL,SEQ,RIGHT,LEFT> ; Give names to T1, T2, T3, T4
        MOVEM T1,LEFT           ; Make T1 available for value
        SETO VAL,               ; Init value to TRUE
        CAMG LEFT,RIGHT         ; Crosses 0?
         TDZA VAL,VAL           ; No.  Set VAL to FALSE.
         EXCH LEFT,RIGHT        ; Yes.  Reverse Left and Right.
        CAMGE SEQ,RIGHT
        CAMGE SEQ,LEFT
        CAIA
         SETCA VAL,             ; Complement VAL.
        RESTORE
        RET

By   way  of  comparison,  the  BCPL  expression  for  this  compiles  into
approximately 40 instructions on the PDP-10.  This expression is:

    let CheckWindow(L, S, R) := (L le R) => (L le S < R), (R le S < L)










                                   - 6 -

Internet Experiment Note 74                              21 September 1978
Sequence Number Arithmetic                               William W. Plummer


; Test to see if two sequence number segments have one or more common
; points.  The two segments are semi-open on the right, similar
; to CHKWND.

;T1/    Left1
;T2/    Right1
;T3/    Left2
;T4/    Right2
;
;       CALL OVRLAP
;Ret+1  always, T1 non-zero if overlap exists

OVRLAP::LOCAL <LEFT1,LEFT2,RIGHT2> ; Define some local ACs.
        MOVEM T1,LEFT1
        DMOVEM T3,LEFT2         ; T3,T4 to LEFT2,RIGHT2
        EXCH T2,T3
        CALL CHKWND
        JUMPN T1,OVRLAX
        MOVE T1,LEFT2
        MOVE T2,LEFT1
        MOVE T3,RIGHT2
        CALL CHKWND
OVRLAX: RESTORE
        RET


























                                   - 7 -