[Ntp] [Technical Errata Reported] RFC5905 (6207)

[RFC Errata System <[e-mail]>]

The following errata report has been submitted for RFC5905,
"Network Time Protocol Version 4: Protocol and Algorithms Specification".

--------------------------------------
You may review the report below and at:
https://www.rfc-editor.org/errata/eid6207

--------------------------------------
Type: Technical
Reported by: Tam Phan <[e-mail]>

Section: A.5.5.1

Original Text
-------------
/*
         * Find the largest contiguous intersection of correctness
         * intervals.  Allow is the number of allowed falsetickers;
         * found is the number of midpoints.  Note that the edge values
         * are limited to the range +-(2 ^ 30) < +-2e9 by the timestamp
         * calculations.
         */
        low = 2e9; high = -2e9;
        for (allow = 0; 2 * allow < n; allow++) {

                /*
                 * Scan the chime list from lowest to highest to find
                 * the lower endpoint.
                 */
                found = 0;
                chime = 0;
                for (i = 0; i < n; i++) {
                        chime -= s.m[i].type;
                        if (chime >= n - found) {
                                low = s.m[i].edge;
                                break;
                        }
                        if (s.m[i].type == 0)
                                found++;
                }

                /*
                 * Scan the chime list from highest to lowest to find
                 * the upper endpoint.
                 */
                chime = 0;
                for (i = n - 1; i >= 0; i--) {
                        chime += s.m[i].type;
                        if (chime >= n - found) {
                                high = s.m[i].edge;
                                break;
                        }
                        if (s.m[i].type == 0)
                                found++;
                }




Mills, et al.                Standards Track                   [Page 91]
 
RFC 5905                   NTPv4 Specification                 June 2010


                /*
                 * If the number of midpoints is greater than the number
                 * of allowed falsetickers, the intersection contains at
                 * least one truechimer with no midpoint.  If so,
                 * increment the number of allowed falsetickers and go
                 * around again.  If not and the intersection is
                 * non-empty, declare success.
                 */
                if (found > allow)
                        continue;

                if (high > low)
                        break;
        }

Corrected Text
--------------
/*
         * Find the largest contiguous intersection of correctness
         * intervals.  Allow is the number of allowed falsetickers;
         * found is the number of midpoints.  Note that the edge values
         * are limited to the range +-(2 ^ 30) < +-2e9 by the timestamp
         * calculations.
         */
        low = 2e9; high = -2e9;
        for (allow = 0; 2 * allow < n; allow++) {

                /*
                 * Scan the chime list from lowest to highest to find
                 * the lower endpoint.
                 */
                found = 0;
                chime = 0;
                for (i = 0; i < n; i++) {
                        chime -= s.m[i].type;
                        if (chime >= n - allow) {
                                low = s.m[i].edge;
                                break;
                        }
                        if (s.m[i].type == 0)
                                found++;
                }

                /*
                 * Scan the chime list from highest to lowest to find
                 * the upper endpoint.
                 */
                chime = 0;
                for (i = n - 1; i >= 0; i--) {
                        chime += s.m[i].type;
                        if (chime >= n - allow) {
                                high = s.m[i].edge;
                                break;
                        }
                        if (s.m[i].type == 0)
                                found++;
                }




Mills, et al.                Standards Track                   [Page 91]
 
RFC 5905                   NTPv4 Specification                 June 2010


                /*
                 * If the number of midpoints is greater than the number
                 * of allowed falsetickers, the intersection contains at
                 * least one truechimer with no midpoint.  If so,
                 * increment the number of allowed falsetickers and go
                 * around again.  If not and the intersection is
                 * non-empty, declare success.
                 */
                if (found > allow)
                        continue;

                if (high > low)
                        break;
        }

Notes
-----
The algorithm described in section 11.2.3 is not properly written here; we compare c to n - f in the algorithm, but f != found; f corresponds to the "allowed" falsetickers. This algorithm implementation results in the lower and upper bounds unchanging throughout the described loop, but this change should fix the implementation.

Instructions:
-------------
This erratum is currently posted as "Reported". If necessary, please
use "Reply All" to discuss whether it should be verified or
rejected. When a decision is reached, the verifying party  
can log in to change the status and edit the report, if necessary. 

--------------------------------------
RFC5905 (draft-ietf-ntp-ntpv4-proto-13)
--------------------------------------
Title               : Network Time Protocol Version 4: Protocol and Algorithms Specification
Publication Date    : June 2010
Author(s)           : D. Mills, J. Martin, Ed., J. Burbank, W. Kasch
Category            : PROPOSED STANDARD
Source              : Network Time Protocol
Area                : Internet
Stream              : IETF
Verifying Party     : IESG