Introduction

This document outlines the "Binary Search" algorithm implemented within the Provider Connectivity Assurance hardware sensors and Sensor Control platforms.

In standard RFC 2544 testing, the IETF defines a linear search paradigm for most tests within the methodology. To optimize execution time, our implementation introduces a preliminary Binary Search phase. This phase efficiently identifies the highest achievable bitrate value, based on a specific step size, between a user-defined range. Once the optimal bitrate is determined, the formal RFC 2544 linear search sequences are executed.

The use of binary search techniques to accelerate testing is a recognized and encouraged practice within the RFC 2544 standard.

The binary search algorithm acts as a precursor to the following tests within the Provider Connectivity Assurance RFC 2544 suite:

• Throughput Test

• Delay (Latency) Test

• Frame Loss Rate Test

The algorithm is executed independently for each configured Frame Size.

Key Parameters

The algorithm initializes using the following user-configured parameters from the Throughput Test settings:

• Maximum Rate: The upper bitrate limit for the search.

• Minimum Rate: The lower bitrate limit for the search.

• Step Size: The smallest incremental value used to refine the test bitrate.

• Binary Search Duration: The length of time each trial is run (e.g., 2 seconds).

Binary Search Implementation Details

The execution of the following tests in the Provider Connectivity Assurance RFC 2544 Test suite is preceded by a binary search algorithm:

• Throughput Test

• Delay Test

• Frame Loss Rate Test

The binary search in the mentioned cases is executed independently for each configured Frame Size.

Execution Flow

A description of the binary search execution logic is depicted in the following flow diagram:

Execution Flow Description

The objective of the binary search algorithm is to find the maximum bitrate within the defined range. It realizes this objective through an iterative process.

The execution begins by initializing the algorithm variables using the values configured by the user in the Throughput Test. The key parameters utilized are:

• Maximum Rate: The upper bitrate limit defined by the user.

• Minimum Rate: The lower bitrate limit specified by the user.

• Step Size: The incremental discrete value defined by the user. It is used by the algorithm to adjust the test bitrate during the search process.

• Binary Search Duration: The length of time each trial is run (e.g., 2 seconds).

The algorithm iteratively adjusts the test bitrate based on the outcome of each trial:

• If a binary search trial passes, the algorithm increases the test bitrate to explore higher bandwidths.

• If a binary search trial fails, the algorithm decreases the test bitrate to search for a suitable lower value.

This iterative process continues until either the highest viable bitrate is determined, or no suitable bitrate can be found within the configured limits. At this point the execution flow concludes.

Once the binary search algorithm identifies the optimal bandwidth, this value is applied as the test rate for the current RFC 2544 test trial. If the algorithm is unable to determine an optimal rate within the specified parameters, the current test trial is skipped, and the process advances to the next scheduled test trial.

Example

The following is a practical example of the behavior of the binary search algorithm implementation in the RFC 2544 Test Suite. Note that this is just an example and the results may differ if the conditions are not the same as the ones hereby mentioned.

Conditions:

• Throughput test Max Rate = 500 Mbps

• Throughput test Min Rate= 1 Mbps

• Throughput test Step Size = 1 Mbps

• Binary Search Duration: 2 seconds

• Throughput test Frame Loss tolerance: 0

• Service Under Test Bandwidth = 75 Mbps

Execution steps

Platform-Specific Behaviors

Sensor Control

• Logic:

  • Executes an independent binary search run for every Frame Size across all supported tests (Throughput, Delay, and Frame Loss).

  • Uses the maximum bitrate obtained from the first binary search of a test as the minimum bitrate for all subsequent trials within that same test.

• Reporting: Failed binary search trials are explicitly included in the RFC 2544 test reports and are denoted by the value ‘(1)’.

Assurance Sensors GT/GT-S, LT-S, and LX-S

• Logic: Executes an independent binary search run for every Frame Size across all supported tests (Throughput, Delay, and Frame Loss).

• Reporting:

  • If the algorithm fails to identify a valid rate, it returns ‘(1)’ in the test report.

  • Individual trial results (the step-by-step iterations) are not included in the final RFC 2544 test reports.