RFC 9693: Benchmarking Methodology for Stateful NATxy Gateways

3.1. When Testing with a Single IP Address Pair

The methodology works with any IP version to benchmark stateful NATxy gateways, where x and y are in {4, 6}. To facilitate an easy understanding, two typical examples are used: stateful NAT44 and stateful NAT64.¶

The test setup for the well-known stateful NAT44 (also called Network Address and Port Translation (NAPT)) solution is shown in Figure 1.¶

Note that the private IP addresses from [RFC1918] are used to facilitate an easy understanding of the example, and the usage of the IP addresses reserved for benchmarking is absolutely legitimate.¶

              +--------------------------------------+
     10.0.0.2 |Initiator                    Responder| 198.19.0.2
+-------------|                Tester                |<------------+
| private IPv4|                         [state table]| public IPv4 |
|             +--------------------------------------+             |
|                                                                  |
|             +--------------------------------------+             |
|    10.0.0.1 |                 DUT:                 | 198.19.0.1  |
+------------>|        Stateful NAT44 gateway        |-------------+
  private IPv4|     [connection tracking table]      | public IPv4
              +--------------------------------------+

The test setup for the stateful NAT64 solution [RFC6146], which is also widely used, is shown in Figure 2.¶

              +--------------------------------------+
    2001:2::2 |Initiator                    Responder| 198.19.0.2
+-------------|                Tester                |<------------+
| IPv6 address|                         [state table]| IPv4 address|
|             +--------------------------------------+             |
|                                                                  |
|             +--------------------------------------+             |
|   2001:2::1 |                 DUT:                 | 198.19.0.1  |
+------------>|        Stateful NAT64 gateway        |-------------+
  IPv6 address|     [connection tracking table]      | IPv4 address
              +--------------------------------------+

As for the transport layer protocol, [RFC2544] recommended testing with UDP, and it was also kept in [RFC8219]. UDP is also kept for a general recommendation; thus, the port numbers in the following text are to be understood as UDP port numbers. The rationale and limitations of this approach are discussed in Section 8.¶

The most important elements of the proposed benchmarking system are defined as follows:¶

Connection:

Although UDP itself is a connectionless protocol, stateful NATxy gateways keep track of their translation mappings in the form of a "connection" as well as in the case of UDP using the same kind of entries as in TCP.¶

Connection tracking table:

The stateful NATxy gateway uses a connection tracking table to be able to perform the stateful translation in the server-to-client direction. Its size, policy, and content are unknown to the Tester.¶

Four tuple:

The four numbers that identify a connection are source IP address, source port number, destination IP address, and destination port number.¶

State table:

The Responder of the Tester extracts the four tuple from each received test frame and stores it in its state table. A recommendation is given for the writing and reading order of the state table in Section 4.10.¶

Initiator:

The port of the Tester that may initiate a connection through the stateful DUT in the client-to-server direction. Theoretically, it can use any source and destination port numbers from the ranges recommended by [RFC4814]: if the used four tuple does not belong to an existing connection, the DUT will register a new connection into its connection tracking table.¶

Responder:

The port of the Tester that may not initiate a connection through the stateful DUT in the server-to-client direction. It may only send frames that belong to an existing connection. To that end, it uses four tuples that have been previously extracted from the received test frames and stores in its state table.¶

Test phase 1:

The test frames are sent only by the Initiator to the Responder through the DUT to fill both the connection tracking table of the DUT and the state table of the Responder. This is a newly introduced operation phase for stateful NATxy benchmarking. The necessity of this test phase is explained in Section 4.2.¶

Test phase 2:

The measurement procedures defined by [RFC8219] (e.g., throughput, latency, etc.) are performed in this test phase after the completion of test phase 1. Test frames are sent as required (e.g., a bidirectional test or a unidirectional test in any of the two directions).¶

One further definition is used in the text of this document:¶

Black box testing:

A testing approach when the Tester is not aware of the details of the internal structure and operation of the DUT. It can send input to the DUT and observe the output of the DUT.¶

3.2. When Testing with Multiple IP Addresses

This section considers the number of the necessary and available IP addresses.¶

In Figure 1, the single 198.19.0.1 IPv4 address is used on the WAN side port of the stateful NAT44 gateway. However, in practice, it is not a single IP address, but rather an IP address range that is assigned to the WAN side port of the stateful NAT44 gateways. Its required size depends on the number of client nodes and on the type of the stateful NAT44 algorithm. (The traditional algorithm always replaces the source port number when a new connection is established. Thus, it requires a larger range than the extended algorithm, which replaces the source port number only when it is necessary. Please refer to Tables 1 and 2 of [LEN2015].)¶

When router testing is done, Section 12 of [RFC2544] requires testing using a single source and destination IP address pair first and then using destination IP addresses from 256 different networks. The 16-23 bits of the 198.18.0.0/24 and 198.19.0.0/24 addresses can be used to express the 256 networks. As this document does not deal with router testing, no multiple destination networks are needed; therefore, these bits are available for expressing multiple IP addresses that belong to the same "/16" network. Moreover, both the 198.18.0.0/16 and the 198.19.0.0/16 networks can be used on the right side of the test setup, as private IP addresses from the 10.0.0.0/16 network are used on its left side.¶

10.0.0.2/16 - 10.0.255.254/16      198.19.0.0/15 - 198.19.255.254/15
           \  +--------------------------------------+  /
            \ |Initiator                    Responder| /
+-------------|                Tester                |<------------+
| private IPv4|                         [state table]| public IPv4 |
|             +--------------------------------------+             |
|                                                                  |
|             +--------------------------------------+             |
| 10.0.0.1/16 |                 DUT:                 | public IPv4 |
+------------>|        Stateful NAT44 gateway        |-------------+
  private IPv4|     [connection tracking table]      | \
              +--------------------------------------+  \
                                   198.18.0.1/15 - 198.18.255.255/15

A possible solution for assigning multiple IPv4 addresses is shown in Figure 3. On the left side, the private IP address range is abundantly large. (The 16-31 bits were used for generating nearly 64k potential different source addresses, but the 8-15 bits are also available if needed.) On the right side, the 198.18.0.0./15 network is used, and it was cut into two equal parts. (Asymmetric division is also possible, if needed.)¶

It should be noted that these are the potential address ranges. The actual address ranges to be used are discussed in Section 4.1.¶

In the case of stateful NAT64, a single "/64" IPv6 prefix contains a high number of bits to express different IPv6 addresses. Figure 4 shows an example where bits 96-111 are used for that purpose.¶

2001:2::[0000-ffff]:0002/64       198.19.0.0/15 - 198.19.255.254/15
           \  +--------------------------------------+  /
  IPv6      \ |Initiator                    Responder| /
+-------------|                Tester                |<------------+
| addresses   |                         [state table]| public IPv4 |
|             +--------------------------------------+             |
|                                                                  |
|             +--------------------------------------+             |
| 2001:2::1/64|                 DUT:                 | public IPv4 |
+------------>|        Stateful NAT64 gateway        |-------------+
 IPv6 address |     [connection tracking table]      | \
              +--------------------------------------+  \
                                   198.18.0.1/15 - 198.18.255.255/15

4.1. Restricted Number of Network Flows

When a single IP address pair is used for testing, then the number of network flows is determined by the number of source and destination port number combinations.¶

The Initiator SHOULD use restricted ranges for source and destination port numbers to avoid the exhaustion of the connection tracking table capacity of the DUT as described in Section 2. If it is possible, the size of the source port number range SHOULD be larger (e.g., in the order of a few tens of thousands), whereas the size of the destination port number range SHOULD be smaller (e.g., it may vary from a few to several hundreds or thousands as needed). The rationale is that source and destination port numbers that can be observed in Internet traffic are not symmetrical. Whereas source port numbers may be random, there are a few very popular destination port numbers (e.g., 443 or 80; see [IIR2020]), and others hardly occur. Additionally, it was found that their role is also asymmetric in the Linux kernel routing hash function [LEN2020].¶

However, in some special cases, the size of the source port range is limited. For example, when benchmarking the Customer Edge (CE) and Border Relay (BR) of a Mapping of Address and Port using Translation (MAP-T) system [RFC7599] together (as a compound system performing stateful NAT44), the source port range is limited to the number of source port numbers assigned to each subscriber. (It could be as low as 2048 ports.)¶

When multiple IP addresses are used, then the port number ranges should be even more restricted, as the number of potential network flows is the product of the size of:¶

In addition, the recommended method requires the enumeration of all their possible combinations in test phase 1 as described in Section 4.4.¶

The number of network flows can be used as a parameter. The performance of the stateful NATxy gateway MAY be examined as a function of this parameter as described in Section 5.1.¶

4.2. Test Phase 1

Test phase 1 serves two purposes:¶

Whereas the above two things are always necessary before test phase 2, test phase 1 can be used without test phase 2. This is done when the maximum connection establishment rate is measured (as described in Section 4.5).¶

Test phase 1 MUST be performed before all tests are performed in test phase 2. The following things happen in test phase 1:¶

When test phase 1 is performed in preparation for test phase 2, the applied frame rate SHOULD be safely lower than the maximum connection establishment rate. (It implies that maximum connection establishment rate measurement MUST be performed first.) Please refer to Section 4.4 for further conditions regarding timeout and the enumeration of all possible four tuples.¶

4.3. Consideration of the Cases of Stateful Operation

The authors consider the most important events that may happen during the operation of a stateful NATxy gateway and the Actions of the gateway as follows.¶

Due to "black box" testing, the Tester is not able to directly examine (or delete) the entries of the connection tracking table. However, the entries can and MUST be controlled by setting an appropriate timeout value and carefully selecting the port numbers of the packets (as described in Section 4.4) to be able to produce meaningful and repeatable measurement results.¶

This document aims to support the measurement of the following performance characteristics of a stateful NATxy gateway:¶

4.4. Control of the Connection Tracking Table Entries

It is necessary to control the connection tracking table entries of the DUT to achieve clear conditions for the measurements. One can simply achieve the following two extreme situations:¶

From this point, the following two assumptions are used:¶

The first extreme situation can be achieved by:¶

The second extreme situation can be achieved by:¶

As described in [RFC4814], pseudorandom port numbers are REQUIRED, which the authors believe is a good approximation of the distribution of the source port numbers a NATxy gateway on the Internet may be faced with.¶

Although the enumeration of all possible four tuples is not a requirement for the first extreme situation and the usage of different four tuples in test phase 1 is not a requirement for the second extreme situation, pseudorandom enumeration of all possible four tuples in test phase 1 is a good solution in both cases. Pseudorandom enumeration of all possible four tuples may be generated in a computationally efficient way by using Durstenfeld's random shuffle algorithm [DUST1964] to prepare a random permutation of the previously enumerated all possible four tuples.¶

The enumeration of the four tuples in increasing or decreasing order (or in any other specific order) MAY be used as an additional measurement.¶

4.5. Measurement of the Maximum Connection Establishment Rate

The maximum connection establishment rate is an important characteristic of the stateful NATxy gateway, and its determination is necessary for the safe execution of test phase 1 (without frame loss) before test phase 2.¶

The measurement procedure of the maximum connection establishment rate is very similar to the throughput measurement procedure defined in [RFC2544].¶

The procedure is as follows:¶

The maximum connection establishment rate is the fastest rate at which the count of test frames successfully translated by the DUT is equal to the number of test frames sent to it by the Initiator.¶

Note: In practice, the usage of binary search is RECOMMENDED.¶

4.6. Validation of Connection Establishment

Due to "black box" testing, the entries of the connection tracking table of the DUT may not be directly examined. However, the presence of the connections can be checked easily by sending frames from the Responder to the Initiator in test phase 2 using all four tuples stored in the state table of the Tester (at a low enough frame rate). The arrival of all test frames indicates that the connections are indeed present.¶

The procedure is as follows:¶

When all the desired N number of test frames are sent by the Initiator to the Receiver at frame rate R in test phase 1 for the maximum connection establishment rate measurement and the Receiver has successfully received all the N frames, the establishment of the connections is checked in test phase 2 as follows:¶

Notes:¶

4.7. Test Phase 2

As for the traffic direction, there are three possible cases during test phase 2:¶

If the Initiator sends test frames, then it uses pseudorandom source port numbers and destination port numbers from the restricted port number ranges. (If it uses multiple source and/or destination IP addresses, then their ranges are also limited.) The Responder receives the test frames, updates its state table, and processes the test frames as required by the given measurement procedure (e.g., only counts them for the throughput test, handles timestamps for latency or PDV tests, etc.).¶

If the Responder sends test frames, then it uses the four tuples from its state table. The reading order of the state table may follow different policies (discussed in Section 4.10). The Initiator receives the test frames and processes them as required by the given measurement procedure.¶

As for the actual measurement procedures, the usage of the updated ones from Section 7 of [RFC8219] is RECOMMENDED.¶

4.8. Measurement of the Connection Tear-Down Rate

Connection tear-down can cause significant load for the NATxy gateway. The connection tear-down performance can be measured as follows:¶

The connection tear-down rate can be computed as:¶

connection tear-down rate = N / ( TimestampB - TimestampA)¶

The connection tear-down rate SHOULD be measured for various values of N.¶

It is assumed that the content of the connection tracking table may be deleted by an out-of-band control mechanism specific to the given NATxy gateway implementation (e.g., by removing the appropriate kernel module under Linux).¶

It is noted that the performance of removing the entire content of the connection tracking table at one time may be different from removing all the entries one by one.¶

4.9. Measurement of the Connection Tracking Table Capacity

The connection tracking table capacity is an important metric of stateful NATxy gateways. Its measurement is not easy, because an elementary step of a validated maximum connection establishment rate measurement (defined in Section 4.6) may have only a few distinct observable outcomes, but some of them may have different root causes:¶

Experience shows that the DUT may collapse if its memory is exhausted. Such a situation may make the connection tracking table capacity measurements rather inconvenient. This possibility is included in the recommended measurement procedure, but the detection and elimination of such a situation is not addressed (e.g., how the algorithm can reset the DUT).¶

For the connection tracking table size measurement, first, one needs a safe number: C0. It is a precondition that C0 number of connections can surely be stored in the connection tracking table of the DUT. Using C0, one can determine the maximum connection establishment rate using C0 number of connections. It is done with a binary search using validation. The result is R0. The values C0 and R0 will serve as "safe" starting values for the following two searches.¶

First, an exponential search is performed to find the order of magnitude of the connection tracking table capacity. The search stops if the DUT collapses OR the maximum connection establishment rate severely drops (e.g., to its one tenth) due to doubling the number of connections.¶

Then, the result of the exponential search gives the order of magnitude of the size of the connection tracking table. Before disclosing the possible algorithms to determine the exact size of the connection tracking table, three possible replacement policies for the NATxy gateway are considered:¶

Now, it is examined what happens and how many validation frames arrive in the three cases. Let the size of the connection tracking table be S and the number of preliminary frames be N, where S is less than N.¶

If one knows that the stateful NATxy gateway uses the first or second replacement policy and one also knows that both R and r rates are low enough, then the final step of determining the size of the connection tracking table is simple. If the Responder sent N validation frames and the Initiator received N' of them, then the size of the connection tracking table is N'.¶

In the general case, a binary search is performed to find the exact value of the connection tracking table capacity within E error. The search chooses the lower half of the interval if the DUT collapses OR the maximum connection establishment rate severely drops (e.g., to its half); otherwise, it chooses the higher half. The search stops if the size of the interval is less than the E error.¶

The algorithms for the general case are defined using C-like pseudocode in Figure 5. In practice, this algorithm may be made more efficient in the way that the binary search for the maximum connection establishment rate stops if an elementary test fails at a rate under RS*beta or RS*gamma during the external search or during the final binary search for the capacity of the connection tracking table, respectively. (This saves a high amount of execution time by eliminating the long-lasting tests at low rates.)¶

// The binarySearchForMaximumConnectionCstablishmentRate(c,r)
// function performs a binary search for the maximum connection
// establishment rate in the [0, r] interval using c number of
// connections.

// This is an exponential search for finding the order of magnitude
// of the connection tracking table capacity
// Variables:
//   C0 and R0 are beginning safe values for the connection
//     tracking table size and connection establishment rate,
//     respectively
//   CS and RS are their currently used safe values
//   CT and RT are their values for the current examination
//   beta is a factor expressing an unacceptable drop in R (e.g.,
//     beta=0.1)
//   maxrate is the maximum frame rate for the media
R0=binarySearchForMaximumConnectionCstablishmentRate(C0,maxrate);
for ( CS=C0, RS=R0; 1; CS=CT, RS=RT )
{
  CT=2*CS;
  RT=binarySearchForMaximumConnectionCstablishmentRate(CT,RS);
  if ( DUT_collapsed || RT < RS*beta )
    break;
}
// At this point, the size of the connection tracking table is
// between CS and CT.

// This is the final binary search for finding the connection
// tracking table capacity within E error
// Variables:
//   CS and RS are the safe values for connection tracking table size
//     and connection establishment rate, respectively
//   C and R are the values for the current examination
//   gamma is a factor expressing an unacceptable drop in R
//     (e.g., gamma=0.5)
for ( D=CT-CS;  D>E; D=CT-CS )
{
  C=(CS+CT)/2;
  R=binarySearchForMaximumConnectionCstablishmentRate(C,RS);
  if ( DUT_collapsed || R < RS*gamma )
    CT=C; // take the lower half of the interval
  else
    CS=C,RS=R; // take the upper half of the interval
}
// At this point, the size of the connection tracking table is
// CS within E error.

4.10. Writing and Reading Order of the State Table

As for the writing policy of the state table of the Responder, round robin is RECOMMENDED, because it ensures that its entries are automatically kept fresh and consistent with that of the connection tracking table of the DUT.¶

The Responder can read its state table in various orders, for example:¶

Pseudorandom is RECOMMENDED to follow the approach of [RFC4814]. Round robin may be used as a computationally cheaper alternative.¶

5.1. Scalability Against the Number of Network Flows

The scalability measurements aim to quantify how the performance of the stateful NATxy gateways degrades with the increase of the number of network flows.¶

As for the actual values for the number of network flows to be used during the measurement series, it is RECOMMENDED to use some representative values from the range of the potential number of network flows the DUT may be faced with during its intended usage.¶

It is important how the given number of network flows are generated. The sizes of the ranges of the source and destination IP addresses and port numbers are essential parameters to be reported together with the results. Please also see Section 6 about the reporting format.¶

If a single IP address pair is used, then it is RECOMMENDED to use:¶

5.2. Scalability Against the Number of CPU Cores

Stateful NATxy gateways are often implemented in software that is not bound to a specific hardware but can be executed by commodity servers. To facilitate the comparison of their performance, it can be useful to determine:¶

If the number of the available CPU cores is a power of two, then it is RECOMMENDED to perform the tests with 1, 2, 4, 8, 16, etc. number of active CPU cores of the DUT.¶