draft-ietf-ippm-metrictest-03.txt   draft-ietf-ippm-metrictest-04.txt 
Internet Engineering Task Force R. Geib, Ed. Internet Engineering Task Force R. Geib, Ed.
Internet-Draft Deutsche Telekom Internet-Draft Deutsche Telekom
Intended status: Standards Track A. Morton Intended status: Standards Track A. Morton
Expires: December 31, 2011 AT&T Labs Expires: April 26, 2012 AT&T Labs
R. Fardid R. Fardid
Cariden Technologies Cariden Technologies
A. Steinmitz A. Steinmitz
Deutsche Telekom Deutsche Telekom
June 29, 2011 October 24, 2011
IPPM standard advancement testing IPPM standard advancement testing
draft-ietf-ippm-metrictest-03 draft-ietf-ippm-metrictest-04
Abstract Abstract
This document specifies tests to determine if multiple independent This document specifies tests to determine if multiple independent
instantiations of a performance metric RFC have implemented the instantiations of a performance metric RFC have implemented the
specifications in the same way. This is the performance metric specifications in the same way. This is the performance metric
equivalent of interoperability, required to advance RFCs along the equivalent of interoperability, required to advance RFCs along the
standards track. Results from different implementations of metric standards track. Results from different implementations of metric
RFCs will be collected under the same underlying network conditions RFCs will be collected under the same underlying network conditions
and compared using state of the art statistical methods. The goal is and compared using state of the art statistical methods. The goal is
skipping to change at page 1, line 44 skipping to change at page 1, line 44
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on December 31, 2011. This Internet-Draft will expire on April 26, 2012.
Copyright Notice Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 41 skipping to change at page 2, line 41
4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
5. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 22 5. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 22
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22
7. Security Considerations . . . . . . . . . . . . . . . . . . . 23 7. Security Considerations . . . . . . . . . . . . . . . . . . . 23
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.1. Normative References . . . . . . . . . . . . . . . . . . . 23 8.1. Normative References . . . . . . . . . . . . . . . . . . . 23
8.2. Informative References . . . . . . . . . . . . . . . . . . 24 8.2. Informative References . . . . . . . . . . . . . . . . . . 24
Appendix A. An example on a One-way Delay metric validation . . . 25 Appendix A. An example on a One-way Delay metric validation . . . 25
A.1. Compliance to Metric specification requirements . . . . . 25 A.1. Compliance to Metric specification requirements . . . . . 25
A.2. Examples related to statistical tests for One-way Delay . 27 A.2. Examples related to statistical tests for One-way Delay . 27
Appendix B. Anderson-Darling 2 sample C++ code . . . . . . . . . 29 Appendix B. Anderson-Darling K-sample Reference and 2 sample
C++ code . . . . . . . . . . . . . . . . . . . . . . 29
Appendix C. Glossary . . . . . . . . . . . . . . . . . . . . . . 37 Appendix C. Glossary . . . . . . . . . . . . . . . . . . . . . . 37
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 38 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 38
1. Introduction 1. Introduction
The Internet Standards Process RFC2026 [RFC2026] requires that for a The Internet Standards Process RFC2026 [RFC2026] requires that for a
IETF specification to advance beyond the Proposed Standard level, at IETF specification to advance beyond the Proposed Standard level, at
least two genetically unrelated implementations must be shown to least two genetically unrelated implementations must be shown to
interoperate correctly with all features and options. This interoperate correctly with all features and options. This
requirement can be met by supplying: requirement can be met by supplying:
skipping to change at page 5, line 14 skipping to change at page 5, line 14
The metric RFC advancement process begins with a request for protocol The metric RFC advancement process begins with a request for protocol
action accompanied by a memo that documents the supporting tests and action accompanied by a memo that documents the supporting tests and
results. The procedures of [RFC2026] are expanded in[RFC5657], results. The procedures of [RFC2026] are expanded in[RFC5657],
including sample implementation and interoperability reports. including sample implementation and interoperability reports.
Section 3 of [morton-advance-metrics-01] can serve as a template for Section 3 of [morton-advance-metrics-01] can serve as a template for
a metric RFC report which accompanies the protocol action request to a metric RFC report which accompanies the protocol action request to
the Area Director, including description of the test set-up, the Area Director, including description of the test set-up,
procedures, results for each implementation and conclusions. procedures, results for each implementation and conclusions.
Changes from WG-03 to WG-04:
o Revisions to Appendix B code and add reference to "R" in the
Appendix and the text of section 3.6.
Changes from WG-02 to WG-03: Changes from WG-02 to WG-03:
o Changes stemming from experiments that implemented this plan, in o Changes stemming from experiments that implemented this plan, in
general. general.
o Adoption of the VLAN loopback figure in the main body of the memo o Adoption of the VLAN loopback figure in the main body of the memo
(section 3.2). (section 3.2).
Changes from WG-01 to WG-02: Changes from WG-01 to WG-02:
skipping to change at page 22, line 11 skipping to change at page 22, line 11
differences such that the connectivity differences of the cross- differences such that the connectivity differences of the cross-
implementation tests are also experienced and measured by the same implementation tests are also experienced and measured by the same
implementation. implementation.
Comparative results for the same implementation represent a bound on Comparative results for the same implementation represent a bound on
cross-implementation equivalence. This should be particularly useful cross-implementation equivalence. This should be particularly useful
when the metric does *not* produces a continuous distribution of when the metric does *not* produces a continuous distribution of
singleton values, such as with a loss metric, or a duplication singleton values, such as with a loss metric, or a duplication
metric. Appendix A indicates how the ADK will work for 0ne-way metric. Appendix A indicates how the ADK will work for 0ne-way
delay, and should be likewise applicable to distributions of delay delay, and should be likewise applicable to distributions of delay
variation. variation. Appendix B discusses two possible ways to perform the ADK
analysis, the R statistical language [Rtool] with ADK package [Radk]
and C++ code.
Proposal: the implementation with the largest difference in Proposal: the implementation with the largest difference in
homogeneous comparison results is the lower bound on the equivalence homogeneous comparison results is the lower bound on the equivalence
threshold, noting that there may be other systematic errors to threshold, noting that there may be other systematic errors to
account for when comparing between implementations. account for when comparing between implementations.
Thus, when evaluating equivalence in cross-implementation results: Thus, when evaluating equivalence in cross-implementation results:
Maximum_Error = Same_Implementation_Error + Systematic_Error Maximum_Error = Same_Implementation_Error + Systematic_Error
skipping to change at page 23, line 7 skipping to change at page 23, line 7
Scott Bradner, Vern Paxson and Allison Mankin drafted bradner- Scott Bradner, Vern Paxson and Allison Mankin drafted bradner-
metrictest [bradner-metrictest], and major parts of it are included metrictest [bradner-metrictest], and major parts of it are included
in this document. in this document.
6. IANA Considerations 6. IANA Considerations
This memo includes no request to IANA. This memo includes no request to IANA.
7. Security Considerations 7. Security Considerations
This draft does not raise any specific security issues. This memo does not raise any specific security issues.
8. References 8. References
8.1. Normative References 8.1. Normative References
[RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003, [RFC2003] Perkins, C., "IP Encapsulation within IP", RFC 2003,
October 1996. October 1996.
[RFC2026] Bradner, S., "The Internet Standards Process -- Revision [RFC2026] Bradner, S., "The Internet Standards Process -- Revision
3", BCP 9, RFC 2026, October 1996. 3", BCP 9, RFC 2026, October 1996.
skipping to change at page 24, line 38 skipping to change at page 24, line 38
[GU+Duffield] [GU+Duffield]
Gu, Y., Duffield, N., Breslau, L., and S. Sen, "GRE Gu, Y., Duffield, N., Breslau, L., and S. Sen, "GRE
Encapsulated Multicast Probing: A Scalable Technique for Encapsulated Multicast Probing: A Scalable Technique for
Measuring One-Way Loss", SIGMETRICS'07 San Diego, Measuring One-Way Loss", SIGMETRICS'07 San Diego,
California, USA, June 2007. California, USA, June 2007.
[RFC5357] Hedayat, K., Krzanowski, R., Morton, A., Yum, K., and J. [RFC5357] Hedayat, K., Krzanowski, R., Morton, A., Yum, K., and J.
Babiarz, "A Two-Way Active Measurement Protocol (TWAMP)", Babiarz, "A Two-Way Active Measurement Protocol (TWAMP)",
RFC 5357, October 2008. RFC 5357, October 2008.
[Radk] Scholz, F., "adk: Anderson-Darling K-Sample Test and
Combinations of Such Tests. R package version 1.0.", ,
2008.
[Rtool] R Development Core Team, "R: A language and environment
for statistical computing. R Foundation for Statistical
Computing, Vienna, Austria. ISBN 3-900051-07-0, URL
http://www.R-project.org/", , 2011.
[Rule of thumb] [Rule of thumb]
Hardy, M., "Confidence interval", March 2010. Hardy, M., "Confidence interval", March 2010.
[bradner-metrictest] [bradner-metrictest]
Bradner, S., Mankin, A., and V. Paxson, "Advancement of Bradner, S., Mankin, A., and V. Paxson, "Advancement of
metrics specifications on the IETF Standards Track", metrics specifications on the IETF Standards Track",
draft -bradner-metricstest-03, (work in progress), draft -bradner-metricstest-03, (work in progress),
July 2007. July 2007.
[morton-advance-metrics] [morton-advance-metrics]
skipping to change at page 29, line 7 skipping to change at page 29, line 7
table 1. Comparing column 1 and column 3 of the table by an ADK test table 1. Comparing column 1 and column 3 of the table by an ADK test
shows, that the data contained in these columns passes an ADK tests shows, that the data contained in these columns passes an ADK tests
with 95% confidence. with 95% confidence.
>>> Comment: Extensive averaging was used in this example, because of >>> Comment: Extensive averaging was used in this example, because of
the vastly different sampling frequencies. As a result, the the vastly different sampling frequencies. As a result, the
distributions compared do not exactly align with a metric in distributions compared do not exactly align with a metric in
[RFC2679], but illustrate the ADK process adequately. [RFC2679], but illustrate the ADK process adequately.
Appendix B. Anderson-Darling 2 sample C++ code Appendix B. Anderson-Darling K-sample Reference and 2 sample C++ code
/* Routines for computing the Anderson-Darling 2 sample
* test statistic.
*
* Implemented based on the description in
* "Anderson-Darling K Sample Test" Heckert, Alan and
* Filliben, James, editors, Dataplot Reference Manual,
* Chapter 15 Auxiliary, NIST, 2004.
* Official Reference by 2010
* Heckert, N. A. (2001). Dataplot website at the
* National Institute of Standards and Technology:
* http://www.itl.nist.gov/div898/software/dataplot.html/
* June 2001.
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
using namespace std;
vector<double> vec1, vec2;
double adk_result;
double adk_criterium = 1.993;
/* vec1 and vec2 to be initialised with sample 1 and There are many statistical tools available, and this Appendix
* sample 2 values in ascending order. describes two that are familiar to the authors.
*/
/* example for iterating the vectors The "R tool" is a language and command-line environment for
* for(vector<double>::iterator it = vec1->begin(); statistical computing and plotting [Rtool]. With the optional "adk"
* it != vec1->end(); it++ package installed [Radk], it can perform individual and combined
* { sample ADK computations. The user must consult the package
* cout << *it << endl; documentation and the original paper [ADK] to interpret the results,
* } but this is as it should be.
*/
static int k, val_st_z_samp1, val_st_z_samp2, The C++ code below will perform a 2-sample AD comparison when
val_eq_z_samp1, val_eq_z_samp2, compiled and presented with two column vectors in a file (using white
j, n_total, n_sample1, n_sample2, L, space as separation). This version contains modifications to use the
max_number_samples, line, maxnumber_z; vectors and run as a stand-alone module by Wes Eddy, Sept 2011. The
static int column_1, column_2; status of the comparison can be checked on the command line with "$
static double adk, n_value, z, sum_adk_samp1, echo $?" or the last line can be replaced with a printf statement for
sum_adk_samp2, z_aux; adk_result instead.
static double H_j, F1j, hj, F2j, denom_1_aux, denom_2_aux;
static bool next_z_sample2, equal_z_both_samples;
static int stop_loop1, stop_loop2, stop_loop3,old_eq_line2,
old_eq_line1;
static double adk_criterium = 1.993; /* Routines for computing the Anderson-Darling 2 sample
* test statistic.
*
* Implemented based on the description in
* "Anderson-Darling K Sample Test" Heckert, Alan and
* Filliben, James, editors, Dataplot Reference Manual,
* Chapter 15 Auxiliary, NIST, 2004.
* Official Reference by 2010
* Heckert, N. A. (2001). Dataplot website at the
* National Institute of Standards and Technology:
* http://www.itl.nist.gov/div898/software/dataplot.html/
* June 2001.
*/
k = 2; #include <iostream>
n_sample1 = vec1->size() - 1; #include <fstream>
n_sample2 = vec2->size() - 1; #include <vector>
#include <sstream>
// -1 because vec[0] is a dummy value using namespace std;
n_total = n_sample1 + n_sample2; int main() {
vector<double> vec1, vec2;
double adk_result;
static int k, val_st_z_samp1, val_st_z_samp2,
val_eq_z_samp1, val_eq_z_samp2,
j, n_total, n_sample1, n_sample2, L,
max_number_samples, line, maxnumber_z;
static int column_1, column_2;
static double adk, n_value, z, sum_adk_samp1,
sum_adk_samp2, z_aux;
static double H_j, F1j, hj, F2j, denom_1_aux, denom_2_aux;
static bool next_z_sample2, equal_z_both_samples;
static int stop_loop1, stop_loop2, stop_loop3,old_eq_line2,
old_eq_line1;
/* value equal to the line with a value = zj in sample 1. static double adk_criterium = 1.993;
* Here j=1, so the line is 1.
*/
val_eq_z_samp1 = 1; /* vec1 and vec2 to be initialised with sample 1 and
* sample 2 values in ascending order */
while (!cin.eof()) {
double f1, f2;
cin >> f1;
cin >> f2;
vec1.push_back(f1);
vec2.push_back(f2);
}
/* value equal to the line with a value = zj in sample 2. k = 2;
* Here j=1, so the line is 1. n_sample1 = vec1.size() - 1;
*/ n_sample2 = vec2.size() - 1;
val_eq_z_samp2 = 1; // -1 because vec[0] is a dummy value
n_total = n_sample1 + n_sample2;
/* value equal to the last line with a value < zj /* value equal to the line with a value = zj in sample 1.
* in sample 1. Here j=1, so the line is 0. * Here j=1, so the line is 1.
*/ */
val_eq_z_samp1 = 1;
val_st_z_samp1 = 0; /* value equal to the line with a value = zj in sample 2.
* Here j=1, so the line is 1.
*/
val_eq_z_samp2 = 1;
/* value equal to the last line with a value < zj /* value equal to the last line with a value < zj
* in sample 1. Here j=1, so the line is 0. * in sample 1. Here j=1, so the line is 0.
*/ */
val_st_z_samp1 = 0;
val_st_z_samp2 = 0; /* value equal to the last line with a value < zj
* in sample 1. Here j=1, so the line is 0.
*/
val_st_z_samp2 = 0;
sum_adk_samp1 = 0; sum_adk_samp1 = 0;
sum_adk_samp2 = 0; sum_adk_samp2 = 0;
j = 1; j = 1;
// as mentioned above, j=1 // as mentioned above, j=1
equal_z_both_samples = false;
equal_z_both_samples = false; next_z_sample2 = false;
next_z_sample2 = false;
//assuming the next z to be of sample 1 //assuming the next z to be of sample 1
stop_loop1 = n_sample1 + 1;
stop_loop1 = n_sample1 + 1; // + 1 because vec[0] is a dummy, see n_sample1 declaration
stop_loop2 = n_sample2 + 1;
stop_loop3 = n_total + 1;
// + 1 because vec[0] is a dummy, see n_sample1 declaration /* The required z values are calculated until all values
* of both samples have been taken into account. See the
* lines above for the stoploop values. Construct required
* to avoid a mathematical operation in the While condition
*/
while (((stop_loop1 > val_eq_z_samp1)
|| (stop_loop2 > val_eq_z_samp2)) && stop_loop3 > j)
{
if(val_eq_z_samp1 < n_sample1+1)
{
/* here, a preliminary zj value is set.
* See below how to calculate the actual zj.
*/
z = vec1[val_eq_z_samp1];
stop_loop2 = n_sample2 + 1; /* this while sequence calculates the number of values
stop_loop3 = n_total + 1; * equal to z.
*/
while ((val_eq_z_samp1+1 < n_sample1)
&& z == vec1[val_eq_z_samp1+1] )
{
val_eq_z_samp1++;
}
}
else
{
val_eq_z_samp1 = 0;
val_st_z_samp1 = n_sample1;
/* The required z values are calculated until all values // this should be val_eq_z_samp1 - 1 = n_sample1
* of both samples have been taken into account. See the }
* lines above for the stoploop values. Construct required
* to avoid a mathematical operation in the While condition
*/
while (((stop_loop1 > val_eq_z_samp1) if(val_eq_z_samp2 < n_sample2+1)
|| (stop_loop2 > val_eq_z_samp2)) && stop_loop3 > j) {
{ z_aux = vec2[val_eq_z_samp2];;
if(val_eq_z_samp1 < n_sample1+1)
{
/* here, a preliminary zj value is set. /* this while sequence calculates the number of values
* See below how to calculate the actual zj. * equal to z_aux
*/ */
z = (*vec1)[val_eq_z_samp1]; while ((val_eq_z_samp2+1 < n_sample2)
&& z_aux == vec2[val_eq_z_samp2+1] )
{
val_eq_z_samp2++;
}
/* this while sequence calculates the number of values /* the smaller of the two actual data values is picked
* equal to z. * as the next zj.
*/ */
while ((val_eq_z_samp1+1 < n_sample1) if(z > z_aux)
&& z == (*vec1)[val_eq_z_samp1+1] ) {
{ z = z_aux;
val_eq_z_samp1++; next_z_sample2 = true;
}
} }
else else
{ {
val_eq_z_samp1 = 0; if (z == z_aux)
val_st_z_samp1 = n_sample1; {
equal_z_both_samples = true;
// this should be val_eq_z_samp1 - 1 = n_sample1
} }
if(val_eq_z_samp2 < n_sample2+1) /* This is the case, if the last value of column1 is
* smaller than the remaining values of column2.
*/
if (val_eq_z_samp1 == 0)
{ {
z_aux = (*vec2)[val_eq_z_samp2];; z = z_aux;
next_z_sample2 = true;
/* this while sequence calculates the number of values
* equal to z_aux
*/
while ((val_eq_z_samp2+1 < n_sample2)
&& z_aux == (*vec2)[val_eq_z_samp2+1] )
{
val_eq_z_samp2++;
}
/* the smaller of the two actual data values is picked
* as the next zj.
*/
if(z > z_aux)
{
z = z_aux;
next_z_sample2 = true;
}
else
{
if (z == z_aux)
{
equal_z_both_samples = true;
}
/* This is the case, if the last value of column1 is
* smaller than the remaining values of column2.
*/
if (val_eq_z_samp1 == 0)
{
z = z_aux;
next_z_sample2 = true;
}
}
} }
else }
{ }
val_eq_z_samp2 = 0; else
val_st_z_samp2 = n_sample2; {
val_eq_z_samp2 = 0;
// this should be val_eq_z_samp2 - 1 = n_sample2 val_st_z_samp2 = n_sample2;
} // this should be val_eq_z_samp2 - 1 = n_sample2
/* in the following, sum j = 1 to L is calculated for }
* sample 1 and sample 2.
*/
if (equal_z_both_samples) /* in the following, sum j = 1 to L is calculated for
{ * sample 1 and sample 2.
*/
if (equal_z_both_samples)
{
/* hj is the number of values in the combined sample /* hj is the number of values in the combined sample
* equal to zj * equal to zj
*/ */
hj = val_eq_z_samp1 - val_st_z_samp1 hj = val_eq_z_samp1 - val_st_z_samp1
+ val_eq_z_samp2 - val_st_z_samp2; + val_eq_z_samp2 - val_st_z_samp2;
/* H_j is the number of values in the combined sample /* H_j is the number of values in the combined sample
* smaller than zj plus one half the the number of * smaller than zj plus one half the the number of
* values in the combined sample equal to zj * values in the combined sample equal to zj
* (that's hj/2). * (that's hj/2).
*/ */
H_j = val_st_z_samp1 + val_st_z_samp2
+ hj / 2;
H_j = val_st_z_samp1 + val_st_z_samp2 /* F1j is the number of values in the 1st sample
+ hj / 2; * which are less than zj plus one half the number
* of values in this sample which are equal to zj.
*/
/* F1j is the number of values in the 1st sample F1j = val_st_z_samp1 + (double)
* which are less than zj plus one half the number (val_eq_z_samp1 - val_st_z_samp1) / 2;
* of values in this sample which are equal to zj.
*/
F1j = val_st_z_samp1 + (double) /* F2j is the number of values in the 1st sample
(val_eq_z_samp1 - val_st_z_samp1) / 2; * which are less than zj plus one half the number
* of values in this sample which are equal to zj.
*/
F2j = val_st_z_samp2 + (double)
(val_eq_z_samp2 - val_st_z_samp2) / 2;
/* F2j is the number of values in the 1st sample /* set the line of values equal to zj to the
* which are less than zj plus one half the number * actual line of the last value picked for zj.
* of values in this sample which are equal to zj. */
*/ val_st_z_samp1 = val_eq_z_samp1;
F2j = val_st_z_samp2 + (double)
(val_eq_z_samp2 - val_st_z_samp2) / 2;
/* set the line of values equal to zj to the /* Set the line of values equal to zj to the actual
* actual line of the last value picked for zj. * line of the last value picked for zjof each
*/ * sample. This is required as data smaller than zj
val_st_z_samp1 = val_eq_z_samp1; * is accounted differently than values equal to zj.
/* Set the line of values equal to zj to the actual */
* line of the last value picked for zjof each
* sample. This is required as data smaller than zj
* is accounted differently than values equal to zj.
*/
val_st_z_samp2 = val_eq_z_samp2; val_st_z_samp2 = val_eq_z_samp2;
/* next the lines of the next values z, ie. zj+1 /* next the lines of the next values z, ie. zj+1
* are addressed. * are addressed.
*/ */
val_eq_z_samp1++;
val_eq_z_samp1++;
/* next the lines of the next values z, ie.
* zj+1 are addressed
*/
val_eq_z_samp2++; /* next the lines of the next values z, ie.
} * zj+1 are addressed
else */
{ val_eq_z_samp2++;
}
else
{
/* the smaller z value was contained in sample 2, /* the smaller z value was contained in sample 2,
* hence this value is the zj to base the following * hence this value is the zj to base the following
* calculations on. * calculations on.
*/ */
if (next_z_sample2) if (next_z_sample2)
{ {
/* hj is the number of values in the combined /* hj is the number of values in the combined
* sample equal to zj, in this case these are * sample equal to zj, in this case these are
* within sample 2 only. * within sample 2 only.
*/ */
hj = val_eq_z_samp2 - val_st_z_samp2; hj = val_eq_z_samp2 - val_st_z_samp2;
/* H_j is the number of values in the combined sample /* H_j is the number of values in the combined sample
* smaller than zj plus one half the the number of * smaller than zj plus one half the the number of
* values in the combined sample equal to zj * values in the combined sample equal to zj
* (that's hj/2). * (that's hj/2).
*/ */
H_j = val_st_z_samp1 + val_st_z_samp2 H_j = val_st_z_samp1 + val_st_z_samp2
+ hj / 2; + hj / 2;
/* F1j is the number of values in the 1st sample which /* F1j is the number of values in the 1st sample which
* are less than zj plus one half the number of values in * are less than zj plus one half the number of values in
* this sample which are equal to zj. * this sample which are equal to zj.
* As val_eq_z_samp2 < val_eq_z_samp1, these are the * As val_eq_z_samp2 < val_eq_z_samp1, these are the
* val_st_z_samp1 only. * val_st_z_samp1 only.
*/ */
F1j = val_st_z_samp1; F1j = val_st_z_samp1;
/* F2j is the number of values in the 1st sample which /* F2j is the number of values in the 1st sample which
* are less than zj plus one half the number of values in * are less than zj plus one half the number of values in
* this sample which are equal to zj. The latter are from * this sample which are equal to zj. The latter are from
* sample 2 only in this case. * sample 2 only in this case.
*/ */
F2j = val_st_z_samp2 + (double) F2j = val_st_z_samp2 + (double)
(val_eq_z_samp2 - val_st_z_samp2) / 2; (val_eq_z_samp2 - val_st_z_samp2) / 2;
/* Set the line of values equal to zj to the actual line /* Set the line of values equal to zj to the actual line
* of the last value picked for zj of sample 2 only in * of the last value picked for zj of sample 2 only in
* this case. * this case.
*/ */
val_st_z_samp2 = val_eq_z_samp2; val_st_z_samp2 = val_eq_z_samp2;
/* next the line of the next value z, ie. zj+1 is /* next the line of the next value z, ie. zj+1 is
* addressed. Here, only sample 2 must be addressed. * addressed. Here, only sample 2 must be addressed.
*/ */
val_eq_z_samp2++; val_eq_z_samp2++;
if (val_eq_z_samp1 == 0) if (val_eq_z_samp1 == 0)
{ {
val_eq_z_samp1 = stop_loop1; val_eq_z_samp1 = stop_loop1;
} }
} }
/* the smaller z value was contained in sample 2, /* the smaller z value was contained in sample 2,
* hence this value is the zj to base the following * hence this value is the zj to base the following
* calculations on. * calculations on.
*/ */
else else
{ {
/* hj is the number of values in the combined /* hj is the number of values in the combined
* sample equal to zj, in this case these are * sample equal to zj, in this case these are
* within sample 1 only. * within sample 1 only.
*/ */
hj = val_eq_z_samp1 - val_st_z_samp1; hj = val_eq_z_samp1 - val_st_z_samp1;
/* H_j is the number of values in the combined /* H_j is the number of values in the combined
* sample smaller than zj plus one half the the number * sample smaller than zj plus one half the the number
* of values in the combined sample equal to zj * of values in the combined sample equal to zj
* (that's hj/2). * (that's hj/2).
*/ */
H_j = val_st_z_samp1 + val_st_z_samp2 H_j = val_st_z_samp1 + val_st_z_samp2
+ hj / 2; + hj / 2;
/* F1j is the number of values in the 1st sample which /* F1j is the number of values in the 1st sample which
* are less than zj plus, in this case these are within * are less than zj plus, in this case these are within
* sample 1 only one half the number of values in this * sample 1 only one half the number of values in this
* sample which are equal to zj. The latter are from * sample which are equal to zj. The latter are from
* sample 1 only in this case. * sample 1 only in this case.
*/ */
F1j = val_st_z_samp1 + (double) F1j = val_st_z_samp1 + (double)
(val_eq_z_samp1 - val_st_z_samp1) / 2; (val_eq_z_samp1 - val_st_z_samp1) / 2;
/* F2j is the number of values in the 1st sample which /* F2j is the number of values in the 1st sample which
* are less than zj plus one half the number of values * are less than zj plus one half the number of values
* in this sample which are equal to zj. As * in this sample which are equal to zj. As
* val_eq_z_samp1 < val_eq_z_samp2, these are the * val_eq_z_samp1 < val_eq_z_samp2, these are the
* val_st_z_samp2 only. * val_st_z_samp2 only.
*/ */
F2j = val_st_z_samp2; F2j = val_st_z_samp2;
/* Set the line of values equal to zj to the actual line /* Set the line of values equal to zj to the actual line
* of the last value picked for zj of sample 1 only in * of the last value picked for zj of sample 1 only in
* this case * this case
*/ */
val_st_z_samp1 = val_eq_z_samp1; val_st_z_samp1 = val_eq_z_samp1;
/* next the line of the next value z, ie. zj+1 is /* next the line of the next value z, ie. zj+1 is
* addressed. Here, only sample 1 must be addressed. * addressed. Here, only sample 1 must be addressed.
*/ */
val_eq_z_samp1++; val_eq_z_samp1++;
if (val_eq_z_samp2 == 0) if (val_eq_z_samp2 == 0)
{ {
val_eq_z_samp2 = stop_loop2; val_eq_z_samp2 = stop_loop2;
}
}
} }
}
}
denom_1_aux = n_total * F1j - n_sample1 * H_j; denom_1_aux = n_total * F1j - n_sample1 * H_j;
denom_2_aux = n_total * F2j - n_sample2 * H_j; denom_2_aux = n_total * F2j - n_sample2 * H_j;
sum_adk_samp1 = sum_adk_samp1 + hj
* (denom_1_aux * denom_1_aux) /
(H_j * (n_total - H_j)
- n_total * hj / 4);
sum_adk_samp2 = sum_adk_samp2 + hj
* (denom_2_aux * denom_2_aux) /
(H_j * (n_total - H_j)
- n_total * hj / 4);
next_z_sample2 = false;
equal_z_both_samples = false;
/* index to count the z. It is only required to prevent sum_adk_samp1 = sum_adk_samp1 + hj
* the while slope to execute endless * (denom_1_aux * denom_1_aux) /
*/ (H_j * (n_total - H_j)
j++; - n_total * hj / 4);
} sum_adk_samp2 = sum_adk_samp2 + hj
* (denom_2_aux * denom_2_aux) /
(H_j * (n_total - H_j)
- n_total * hj / 4);
next_z_sample2 = false;
equal_z_both_samples = false;
// calculating the adk value is the final step. /* index to count the z. It is only required to prevent
* the while slope to execute endless
*/
j++;
}
adk_result = (double) (n_total - 1) / (n_total // calculating the adk value is the final step.
* n_total * (k - 1)) adk_result = (double) (n_total - 1) / (n_total
* (sum_adk_samp1 / n_sample1 * n_total * (k - 1))
+ sum_adk_samp2 / n_sample2); * (sum_adk_samp1 / n_sample1
+ sum_adk_samp2 / n_sample2);
/* if(adk_result <= adk_criterium) /* if(adk_result <= adk_criterium)
* adk_2_sample test is passed * adk_2_sample test is passed
*/ */
return adk_result <= adk_criterium;
}
Figure 5 Figure 5
Appendix C. Glossary Appendix C. Glossary
+-------------+-----------------------------------------------------+ +-------------+-----------------------------------------------------+
| ADK | Anderson-Darling K-Sample test, a test used to | | ADK | Anderson-Darling K-Sample test, a test used to |
| | check whether two samples have the same statistical | | | check whether two samples have the same statistical |
| | distribution. | | | distribution. |
| ECMP | Equal Cost Multipath, a load balancing mechanism | | ECMP | Equal Cost Multipath, a load balancing mechanism |
 End of changes. 85 change blocks. 
331 lines changed or deleted 348 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/