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/ |