Subject: [Softwires] Presentation of the port mapping algorithm in draft-ietf-softwire-map-02.txt

From: Tom Taylor <[email-masked]>
Date: Mon, 24 Dec 2012 08:41:38 -0500

I think Section 5.1 of draft-ietf-softwire-map-02.txt, which presents 
the port mapping algorithm, can be improved a bit. Partly the problem is 
that a couple of symbols are not explained clearly enough. In addition, 
it would be helpful to the general reader to explain the underlying 
strategy represented by the formula before getting into the formula 
itself. I propose modified text below. Minor changes are marked with 
^^^, while larger additions and deletions are delimited by <new> .. 
</new> and <delete> .. </delete>.

Tom Taylor

5.1.  Port mapping algorithm

    The port mapping algorithm is used in domains whose rules allow IPv4
    address sharing.  Different CEs indexed by Port-Set Identifier
                                ^^^^^^^^^^^^^^                    ^
(PSID) sharing the same external IPv4 address MUST have
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    non-overlapping port-sets.  The two extreme cases are: (1) the port
    numbers are not contiguous for each PSID, but uniformly distributed
    across the port range (0-65535); (2) the port numbers are contiguous
    in a single range for each PSID.
<new>
These two extremes can be encompassed by a single port allocation 
strategy as follows. The available range of port space is divided into a 
sequence of blocks of M*R consecutive values, where M is the maximum 
number of consecutive port values to be allocated to a given CE within a 
given block, and R is the number of CEs sharing each external IPv4 
address. Each CE is then allocated a range of M bits within each 
successive block. The position of the CE's allocated range is determined 
by the value of its assigned PSID.
</new>
The port mapping algorithm proposed
    here to implement that strategy is called the Generalized Modulus
         ^^^^^^^^^^^^^^^^^^^^^^^^^^
  Algorithm (GMA).
                ^^^

    For a given sharing ratio (R) and the maximum number of contiguous
    ports (M), the GMA algorithm is defined as:

    1.  The set of port numbers (P) allocated to a given PSID is
            ^^^^^^            ^     ^^^^^^^^^^^^             ^^
  composed of:

<deleted>
    P = R * M * j + M * K + i
</deleted>
<new>
    P = (j * M*R) + (PSID * M) + i

    where j, PSID, and i are indexes with ranges given below. The
    first term of this formula points to the first port number in
    the j'th block of M*R bits. The second term points to the first
    port number in the range allocated to a given PSID within that
    block. Finally, the index i selects a specific port number
    within that range.
</new>

        Where:

        *  PSID = 0 to R - 1
               ^^

        *  Block index: j = (4096 / (M*R)) to ((65536 / (M*R)) - 1,
           ^^^^^                    ^^^^^               ^^^^^
           if the port numbers (0 - 4095) are excluded.
<new>
              If M and R are not powers of 2, the lower end of the
              range of j has to be rounded up and the upper end rounded
              down to avoid allocating port numbers outside the range
              4096-65535. In that case, some port numbers at the ends
              of that range are not allocated (wasted).
</new>

        *  Contiguous Port index: i = 0 to M - 1

<deleted>
    2.  The PSID (K) of a given port number (P) is determined by:

    K = (floor(P/M)) % R
</deleted>

<new>
    2. Given a port number P, the corresponding PSID can be calculated as

    PSID = (floor(P / M)) % R
</new>

        Where:

        *  % is the modulus operator

        *  floor(arg) is a function that returns the largest integer not
           greater than arg.

5.1.1.  Bit Representation of the Algorithm

    Given a sharing ratio (R=2^k) and a maximum number of contiguous
                                  ^^^^^
  ports (M=2^m),

<deleted>
for any PSID (K) and available ports (P) can be represented
    as:
</deleted>

<new>
the binary representation of a given port number P partitions neatly 
into three fields, as shown in Figure 2 below. The rightmost m bits 
contain the value of the range index i. The middle k bits contain the 
value of the PSID. Finally, the leftmost a bits contain the block index 
j, where a is the number of bits required to represent the quantity
A = (65536 / (M*R)) - 1 which is the upper bound of j.
</new>

    0                          8                         15
    +---------------+----------+------+-------------------+
    |                     P                               |
    ----------------+-----------------+-------------------+
    |        A (j)  |       PSID      |        M  (i)     |
                            ^^^^
    +---------------+----------+------+-------------------+
    |<----a bits--->|<-----k bits---->|<------m bits----->|

                        Figure 2: Bit representation

<deleted>
    Where j and i are the same indexes defined in the port mapping
    algorithm.
</deleted>

    Thus for any port number P, the PSID can be obtained by bit mask
    ^^^^                     ^
operation.

    For a > 0, j MUST be larger than 0.  This ensures that the algorithm
    excludes the system ports ([I-D.ietf-tsvwg-iana-ports]).  For a = 0,
    j MAY be 0 to allow for the provisioning of the system ports.