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