idnits 2.17.1 draft-leipnitz-spring-pms-implementation-report-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == There are 1 instance of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (June 22, 2016) is 2864 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 700 -- Looks like a reference, but probably isn't: '1' on line 652 -- Looks like a reference, but probably isn't: '2' on line 653 ** Obsolete normative reference: RFC 2679 (Obsoleted by RFC 7679) ** Obsolete normative reference: RFC 4379 (Obsoleted by RFC 8029) == Outdated reference: A later version (-10) exists of draft-ietf-spring-oam-usecase-03 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 spring R. Leipnitz, Ed. 3 Internet-Draft R. Geib 4 Intended status: Informational Deutsche Telekom 5 Expires: December 24, 2016 June 22, 2016 7 A scalable and topology aware MPLS data plane monitoring system 8 draft-leipnitz-spring-pms-implementation-report-00 10 Abstract 12 This document reports round-trip delay measurements captured by a 13 single MPLS Path Monitoring System (PMS) compared with results of an 14 IPPM conformant measurement system, consisting of three different 15 Measurement Agents. The measurements were made in a research 16 backbone with an LDP control plane. The packets of the MPLS PMS use 17 label stacks similar to those to be used by a segment routing MPLS 18 PMS. The measurement packets of the MPLS PMS remained in the network 19 data plane. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on December 24, 2016. 38 Copyright Notice 40 Copyright (c) 2016 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Measurement system implementation . . . . . . . . . . . . . . 3 57 2.1. A PMS based round-trip delay measurement system . . . . . 3 58 2.2. Perfas+ IPPM measurement system . . . . . . . . . . . . . 4 59 3. Test set up . . . . . . . . . . . . . . . . . . . . . . . . . 4 60 4. Measurement Result Evaluation . . . . . . . . . . . . . . . . 6 61 5. Measurement results . . . . . . . . . . . . . . . . . . . . . 6 62 5.1. Round-trip delay measurement and ADK test results . . . . 6 63 5.2. PMS delay measurements with IP-address variation . . . . 9 64 6. Error Calibration . . . . . . . . . . . . . . . . . . . . . . 10 65 7. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 66 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12 67 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 68 10. Security Considerations . . . . . . . . . . . . . . . . . . . 12 69 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 70 11.1. Normative References . . . . . . . . . . . . . . . . . . 12 71 11.2. Informative References . . . . . . . . . . . . . . . . . 13 72 Appendix A. ADK2 Test Source Code . . . . . . . . . . . . . . . 13 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 75 1. Introduction 77 Deutsche Telekom has implemented an MPLS Path Monitoring System 78 (PMS). The PMS operates on MPLS networks with LDP control plane. 79 Forwarding follows the principles of Segment Routing, i.e. the 80 packets sent by the PMS use stacked transport labels to execute a 81 combination of MPLS paths and finally return to the PMS. The PMS is 82 connected to a research backbone of Deutsche Telekom spanning parts 83 of Germany. One of the new network monitoring features enabled by 84 Segment Routing are round-trip delay measurements purely executed in 85 data plane. Deutsche Telekom captured delays between three IPPM 86 standard conformant Measurement Agents and compared these with delays 87 measured along identical backbone paths by a single PMS. To prove 88 that the same delays were measured the IPPM results were then 89 compared with the PMS results by applying IPPM methodology as 90 specified by [RFC6576]. Some results passed this test, while others 91 did not. The results of both systems seemed to differ by very small 92 and relatively stable latencies. As the research network only 93 offered single paths between the involved routers, processing of 94 different flows in parallel forwarding instances of the routers along 95 the paths offered an explanation. The PMS was used to execute some 96 measurements whose results at least are not contradicting that 97 assumption. 99 The results reported here show that a PMS 100 [I-D.ietf-spring-oam-usecase] can be built and operated (also as part 101 of an LDP based MPLS network). To set up packets with proper label 102 stacks, the PMS needs to be aware of the MPLS topology of the 103 network. MPLS topology awareness within an LDP based network 104 requires reasonable effort. Segment Routing will significantly 105 simplify detection of the MPLS topology. Delay measurements where 106 picked here to give an example of a feature which can be supported by 107 a PMS. Others are possible, like checking continuity of arbitrary 108 segmented routed MPLS paths [I-D.ietf-spring-oam-usecase]. 110 The remaining document is organized as follows: Section 2 briefly 111 informs about the PMS and IPPM measurement system implementation. 112 Section 3 introduces the measurement set up within the research 113 network. Section 4 briefly discusses the test by which the 114 measurements were compared. Section 5 informs about the test results 115 and Section 6 about an IPPM error calibration. Section 7 sums up the 116 document. 118 2. Measurement system implementation 120 Deutsche Telekom operates an IPPM standard conformant performance 121 measurement system called Perfas+. Deutsche Telekom intends 122 deployment of an MPLS PMS to monitor the IP performance in network 123 segments connecting roughly 1000 edge routers to the IP-backbone. 11 124 MPLS PMS are supposed to execute backbone to edge performance 125 monitoring. Had the monitoring system been based on IPPM, one IPPM 126 system had been required per edge router. 128 2.1. A PMS based round-trip delay measurement system 130 Deutsche Telekom has implemented an MPLS PMS. The PMS is part of an 131 MPLS research and development backbone of Deutsche Telekom. This 132 backbone only supports LDP routing. The PMS works with an LDP 133 control plane. Detecting the MPLS topology of an LDP based MPLS 134 network is more complex, than doing this by Segment Routing. The PMS 135 consists of the following logical components: 137 o An MPLS Label detection system. It is collecting MPLS routing 138 information from all MPLS routers of the MPLS network by 139 management plane access (see e.g. [LDP-TE], [BCP-TX]) 141 o An MPLS topology database. 143 o A measurement system able to compose packets executing any 144 combination MPLS Label Switched Paths (MPLS LSP) which are part of 145 the MPLS topology database. The measurement system further is 146 able to measure delays, if the final address information of the 147 measurement packet directs the packet back to the PMS after the 148 MPLS LSPs to be measured have been passed. 150 o An IGP topology detection system. It is passively listening to 151 IGP routing. 153 o A measurement system which is complying to [RFC4379]. 155 Note that the final two MPLS PMS functionalities are required if ECMP 156 routed paths should be detected and addressed by [RFC4379] functions. 157 No ECMP routed paths are present between the sites involved in the 158 measurement set up. The role of these components is reduced to 159 detection of operational issues, should the measurement not work as 160 expected. 162 While the control plane of the network monitored by the PMS is LDP 163 based, the measurement packets used to execute MPLS LSPs apply the 164 forwarding mechanisms as within a Segment Routing network. 166 2.2. Perfas+ IPPM measurement system 168 IPPM conformant one-way delay measurements were performed by Perfas+ 169 Measurement Agents. Three Perfas+ Measurement Agents are connected 170 to edge routers at three different sites of the research network. 171 Perfas+ is one of the few IPPM implementations with proven 172 conformance to some standard IPPM metrics, like one-way delay 173 [RFC6808]. Two of the Perfas+ Measurement Agents were synchronized 174 by NTP only. Due to this restriction, the comparison with the PMS 175 measurements are limited to round-trip times (round-trip delays, 176 RTD). As no ECMP routed paths are active between the sites used for 177 test execution, two back and forth Perfas+ one-way delay measurements 178 between two sites were added to result in an RTD value. 180 3. Test set up 182 The test set up is shown in the figure below. The PMS and Perfas+ 183 Measurement Agent 1 (PerfMA 1) are connected to the same LER. 185 +--------+ 186 |PerfMA 1| 187 +--------+ 188 | 189 +---+ +-----+ 190 |PMS|---|LER 1| 191 +---+ +-----+ 192 | 193 ~~~~~~~ 194 / \ +-----+ +--------+ 195 ( MPLS )--|LER 2|--|PerfMA 2| 196 ( Network ) +-----+ +--------+ 197 \ / 198 ~~~~~~~ 199 | 200 +-----+ +--------+ 201 |LER 3|--|PerfMA 3| 202 +-----+ +--------+ 204 Figure 1: Test set up 206 The Perfas+ Measurement Agents (MAs) measure the one-way delay to 207 each of the remote Perfas+ MAs. The PMS measures the round-trip 208 delay from LER 1 to LER 2 and back as well the round-trip delay from 209 LER 1 to LER 3 and back. The measurements start and terminate at the 210 PMS, but this segment is omitted here. The round-trip delay from LER 211 2 to LER 3 is measured along two path combinations by the PMS. The 212 first measurement path is LER 1 to LER 2 to LER 3 and back exactly 213 that way. The round-trip delay LER 1 to LER 2 captured earlier by 214 the PMS is subtracted from the result. The other measurement is LER 215 1 to LER 3 to LER 2 and back exactly that way. Here, the PMS round- 216 trip delay LER 1 to LER 3 is subtracted to receive the round-trip 217 delay LER 2 to LER 3. 219 There is a small LAN section causing limited additional latencies for 220 the IPPM measurement. The measurements were executed with an IP 221 packet size of 64 Byte. Perfas is attached by an IP-VPN. The PMS 222 label stack is differing slightly. The assumption is that both 223 differences have minor impact. Note that IPPM metrics expect similar 224 results if differences in measurement set up can be neglected. The 225 sending interval is 10 seconds periodic. A measurement mean is 226 calculated from 10 consecutive measurement packets. The measurements 227 were repeated for 8 hours, resulting in 288 mean values collected per 228 round-trip delay measurement path and measurement system. 230 The resulting round-trip delays are divided by two and indicate the 231 one-way delay. This seems sound, as there is no path diversity in 232 the research network and the low standard deviation of the results 233 (single digit [us] figures in all cases, see test results below) 234 indicate that no link was congested. 236 4. Measurement Result Evaluation 238 IPPM WG applies the Anderson-Darling-K-Sample (ADK) test to compare 239 up to which temporal resolution the results of two measurements share 240 the same statistical distribution [RFC6576]. To decide, whether 241 Perfas+ and the PMS were measuring identical data, the round-trip 242 delays captured along identical measurement paths were compared by an 243 ADK test. (The ADK test source code is given at Appendix A). Note 244 that the ADK test does not judge accuracy (i.e. it does not test 245 whether the result is close to the true value?), ADK rather judges 246 precision (that the test estimates whether the same value was 247 measured by repeated measurements). As applied here, an RTD sample 248 of Perfas+ was compared with one of the PMS captured along the same 249 path. 251 To illustrate, how sensible the ADK test is to changes in a 252 measurement environment, a PMS round-trip delay test was set up where 253 all configurations were identical and only packet size was variable. 254 Obviously all paths are identical, so any difference in results is 255 caused by the packet size only (64, 128 and 256 Byte were picked). 256 The ADK test indicated a reasonably high probability that results do 257 not follow the same distribution in roughly half of the cases (i.e. 258 ADK test said that the distribution of round-trip delays captured 259 with packet size of 64 bytes follows a different distribution than 260 the round-trip delays captured with a packet size of 128 Byte). 262 5. Measurement results 264 5.1. Round-trip delay measurement and ADK test results 266 The one-way delays between Perfas MA 1 and Perfas MA 2 calculated on 267 basis of the round-trip Delay and the ADK test results comparing them 268 to the measurement results captured by the PMS are shown in Table 1. 270 +-------------------------------------+---------+---------+ 271 | Test metric | PERFAS+ | PMS | 272 +-------------------------------------+---------+---------+ 273 | minimum [us] | 691.5 | 695.5 | 274 | maximum [us] | 701 | 704.5 | 275 | mean [us] | 695.4 | 699.6 | 276 | median [us] | 695.5 | 699.5 | 277 | standard deviation [us] | 1.4 | 1.7 | 278 | ADK value | | 278.445 | 279 | ADK value with adjustment of mean | | 1.701 | 280 | ADK value with adjustment of median | | 1.982 | 281 +-------------------------------------+---------+---------+ 283 Perfas+ and PMS OWD measurement results for path LER 1 to LER 2 and 284 ADK test results 286 Table 1: Perfas+ and PMS OWD measurement results for path LER 1 to 287 LER 2 and ADK test results 289 The ADK test result is surprisingly good and was not expected a 290 priori. As mentioned, ADK is a very sensible test. When IPPM WG 291 worked on [RFC6808], the packets used by two different IPPM 292 implementation only passed ADK after a network emulator was inserted 293 into the measurement path. As IPPM puts more emphasis on precision 294 than on accuracy, correcting tests samples to result by the same mean 295 for small and constant differences is plausible. Still, the smallest 296 temporal resolution of the standard deviation by which ADK was passed 297 when used to compare two IPPM implementations for [RFC6808] was 298 single digit milliseconds. No network emulator has been used when 299 comparing Perfas+ and the PMS. After adjusting the means, ADK is 300 passed by a temporal resolution of the standard deviation of single 301 digit microseconds! 303 The one-way delays between Perfas MA 1 and Perfas MA 3 calculated on 304 basis of the round-trip Delay and the ADK test results comparing them 305 to the measurement results as captured by the PMS are shown in 306 Table 2. 308 +-------------------------------------+---------+---------+ 309 | Test metric | PERFAS+ | PMS | 310 +-------------------------------------+---------+---------+ 311 | minimum [us] | 2991.5 | 2983 | 312 | maximum [us] | 3008.5 | 2994.5 | 313 | mean [us] | 2995.7 | 2988.1 | 314 | median [us] | 2995.5 | 2988 | 315 | standard deviation [us] | 1.9 | 2.1 | 316 | ADK value | | 231.638 | 317 | ADK value with adjustment of mean | | 1.886 | 318 | ADK value with adjustment of median | | 2.026 | 319 +-------------------------------------+---------+---------+ 321 Perfas+ and PMS OWD measurement results for path LER 1 to LER 3 and 322 ADK test results 324 Table 2: Perfas+ and PMS OWD measurement results for path LER 1 to 325 LER 3 and ADK test results 327 After adjustment of the means values, also here the ADK test is 328 passed. Comparing Table 1 with Table 2 readers figure can see, that 329 once mean the one-way delay measured by Perfas+ is lower, while in 330 the other case the mean one-way delay captured by the PMS is lower. 331 This behavior was visible in all our measurements. The delays 332 measured per path by one system were always bigger than that of the 333 other along the same path (for all single 10 sample mean values of 334 the time series). 336 We now compare the one-way delays between Perfas MA 2 and Perfas MA 3 337 calculated on basis of the round-trip delay and the ADK test results 338 comparing them to the measurement results as captured by the PMS are 339 shown in Table 3. 341 +-----------------------------+---------+-------------+-------------+ 342 | Test metric | PERFAS+ | PMS over | PMS over | 343 | | | LER 2 | LER 3 | 344 +-----------------------------+---------+-------------+-------------+ 345 | minimum [us] | 3606.5 | 3551 | 3542.5 | 346 | maximum [us] | 3659 | 3568 | 3558 | 347 | mean [us] | 3611.9 | 3560.1 | 3549,8 | 348 | median [us] | 3609 | 3560 | 3549,5 | 349 | standard deviation [us] | 8.3 | 2.9 | 2.9 | 350 | ADK value | | 231.144 | 231.094 | 351 | ADK value with adjustment | | 54.591 | 56.589 | 352 | of mean | | | | 353 | ADK value with adjustment | | 8.915 | 10.054 | 354 | of median | | | | 355 +-----------------------------+---------+-------------+-------------+ 357 Perfas+ and PMS OWD measurement results for path LER 2 to LER 3 and 358 ADK test results 360 Table 3: Perfas+ and PMS OWD measurement results for path LER 2 to 361 LER 3 and ADK test results 363 In this case, the ADK test fails (the cause is the difference of the 364 standard deviation, not the mean or median difference). Note that in 365 terms of mean values the difference is around 50 us between Perfas 366 and PMS. The relative error is 1,75%. While ADK indicates that both 367 distributions deviate, human perception may confirm that both results 368 capture delays along the same path. 370 It is interesting however, that the two PMS measurements deviate in 371 the mean values. And again, the one showing the lower delay does so 372 sample mean measurements. A brief test investigating this symptom 373 was performed. Test and results follow in the next section. 375 5.2. PMS delay measurements with IP-address variation 377 The PMS allows to send measurement packets with different destination 378 IP-addresses (routing based on IP-addresses only occurs from LER 1 to 379 PMS and only in this direction). While the IP-address varied, the 380 MPLS Label stack and thus the MPLS path was kept identical. This 381 measurement can only be configured by CLI configuration. Per IP 382 destination address, the mean-value of 10 round-trip delay times was 383 captured. After some measurements the IP-addresses showing the 384 biggest round-trip delay difference were selected for further 385 testing. With these IP-addresses, the test was repeated at different 386 days and daytimes. Overall we had at least 10 more measurement 387 values of every of these IP-addresses. The PMS is connected with two 388 interfaces to two different LERs of the same site. Both interfaces 389 and LERs respectively were used to perform the measurements. As has 390 been mentioned already, the network does not have ECMP-paths. 391 Table 4 shows the results of the two measurements with the biggest 392 difference in results. The mean delays measured with IP-address 393 a.b.c.0 were the smallest. They were always smaller than those 394 delays captured with IP-address a.b.c.32, which were the biggest. 395 The difference of the mean values from the measurement over the first 396 interface was 19.5 us and 14.4 us over the second interface. 398 +------------------------+-----------+-------------+ 399 | Interface / IP-address | mean [us] | median [us] | 400 +------------------------+-----------+-------------+ 401 | one / a.b.c.0 | 1413.2 | 1412 | 402 | one / a.b.c.32 | 1432.7 | 1433 | 403 | two / a.b.c.0 | 1446.4 | 1446 | 404 | two / a.b.c.32 | 1460.8 | 1460.5 | 405 +------------------------+-----------+-------------+ 407 Table 4: Destination-IP-address variation 409 Parallel hardware processing within some or all of the routers passed 410 on the measurement paths may be a plausible explanation. 411 Investigating the cause for this behavior was however not the main 412 aim of the test activities documented here. Further activities 413 related to this issue are left to interested research. 415 6. Error Calibration 417 Section 3.7. and following of [RFC2679] recommend an error 418 calibration of the (IPPM) measurement clients. The one-way delay of 419 a back-to-back connection of two PERFAS+ clients is measured. 420 Table 5 shows the characteristics of this calibration measurement. 421 The negative values for the one-way delay shown in the table, are 422 physically impossible. The standard deviation is very high. It was 423 decided to calibrate with the round-trip delay which is shown in 424 Table 6. Referring to section 3.7.3 of [RFC2679] there is a 425 systematic error and a random error. The systematic error is the 426 median of the measurement with 49.5 us. The random error is the 427 difference between the median and the 2.5% percentile, which is 17 428 us. (The random error is the larger absolute value between the 429 median and the 2.5% percentile and the 97.5% percentile; the 430 calculation is |49.5 - 32.5| > |49.5 - 59.5|). The resolution of the 431 PERFAS+ Measurement Agents is 1 us, so the absolute random error is 432 19 us. So measurement error is 49.5 +/- 19 us. (The synchronization 433 error is 0, as two one-way delays are added, making this error 434 disappear). There was no possibility to calibrate the PMS. The 435 error is assumed to be the same like that of PERAS+, because the PMS 436 is based on the same hardware (and possibly the same host-system). 438 +-------------------------+---------+ 439 | Test metric | PERFAS+ | 440 +-------------------------+---------+ 441 | minimum [us] | -55 | 442 | maximum [us] | 39 | 443 | mean [us] | -38 | 444 | median [us] | -23.1 | 445 | standard deviation [us] | 29.4 | 446 +-------------------------+---------+ 448 Table 5: measurement results of one-way delay of back-to-back 449 connection from two PERFAS+ clients at 64 Bytes 451 +-------------------------+---------+ 452 | Test metric | PERFAS+ | 453 +-------------------------+---------+ 454 | minimum [us] | 26 | 455 | maximum [us] | 205 | 456 | mean [us] | 49.1 | 457 | median [us] | 49.5 | 458 | standard deviation [us] | 7.6 | 459 | 2.5% percentile [us] | 32.5 | 460 | 97.5% percentile [us] | 59.5 | 461 +-------------------------+---------+ 463 Table 6: measurement results of both one-way delays of back-to-back 464 connection between two PERFAS+ clients at 64 Bytes 466 7. Summary 468 By an IPPM measurement system like PERFAS+ three physical measurement 469 clients are needed to measure the round-trip delay between all sites. 470 With the PMS the same measurements can be performed with only one 471 client. In theory one PMS could monitor a whole MPLS-enabled 472 backbone. The GPS receivers of two IPPM measurement agents were not 473 available, hence the one-way delay could not be captured with the 474 IPPM system PERFAS+. Otherwise a direct comparison with calculated 475 one-way delay values based on the PMS measured values would have been 476 possible. This could be done in future. The results shown in 477 Section 4 indicate, that the PMS measurements equal those captured by 478 an IPPM conformant measurement system. The ADK test is successful by 479 comparing the measurement values of the round-trip delays for packets 480 with a size of 64 bytes. The network does not include an impairment 481 generator (which was required within a test set up to compare 482 independent IPPM implementations, see [RFC6808]). An impairment 483 generator as part of the test set up will have a positive effect on 484 the measurements and the measurements with bigger packet size will 485 also succeed at a temporal resolution above [us] level. 487 8. Acknowledgements 489 Joachim Mende, Marc Wieland, Ralf Widera and Jens Wyduba helped to 490 implement and operate the LDP PMS in our research network. In 491 memoriam of Holger Zarwel, who gave our project unconditional 492 support. 494 9. IANA Considerations 496 This memo includes no request to IANA. 498 10. Security Considerations 500 A PMS monitoring packet should never leave the domain where it 501 originated. It therefore should never use stale MPLS or IGP routing 502 information. If the Label Switch Path is broken, a packet with the 503 destination address 127.0.0.0/26 should not be routed, it should be 504 discarded. The PMS must be configured with a measurement interval 505 (or sum of all measurement stream intervals) that does not overload 506 the network. Too many measurement streams with a big packet size 507 could overload a link. 509 11. References 511 11.1. Normative References 513 [RFC2679] Almes, G., Kalidindi, S., and M. Zekauskas, "A One-way 514 Delay Metric for IPPM", RFC 2679, DOI 10.17487/RFC2679, 515 September 1999, . 517 [RFC4379] Kompella, K. and G. Swallow, "Detecting Multi-Protocol 518 Label Switched (MPLS) Data Plane Failures", RFC 4379, 519 DOI 10.17487/RFC4379, February 2006, 520 . 522 [RFC6576] Geib, R., Ed., Morton, A., Fardid, R., and A. Steinmitz, 523 "IP Performance Metrics (IPPM) Standard Advancement 524 Testing", BCP 176, RFC 6576, DOI 10.17487/RFC6576, March 525 2012, . 527 [RFC6808] Ciavattone, L., Geib, R., Morton, A., and M. Wieser, "Test 528 Plan and Results Supporting Advancement of RFC 2679 on the 529 Standards Track", RFC 6808, DOI 10.17487/RFC6808, December 530 2012, . 532 11.2. Informative References 534 [BCP-TX] NANOG, "Best Practices for Determining Traffic Matrices in 535 IP Networks V 4.0", 2008. 537 [I-D.ietf-spring-oam-usecase] 538 Geib, R., Filsfils, C., Pignataro, C., and N. Kumar, "A 539 Scalable and Topology-Aware MPLS Dataplane Monitoring 540 System", draft-ietf-spring-oam-usecase-03 (work in 541 progress), April 2016. 543 [LDP-TE] VDE-Verlag, "Traffic Matrices for MPLS Networks with LDP 544 Traffic Statistics", 2004. 546 Appendix A. ADK2 Test Source Code 548 The following C++ source code is a modified version of the Code at 549 [RFC6576]. This version allows to test two files containing values 550 with the ADK2. It is not necessary that the values are sorted, 551 because in the first step the values get sorted. 553 /* 554 Copyright (c) 2012 IETF Trust and the persons identified 555 as authors of the code. All rights reserved. 557 Redistribution and use in source and binary forms, with 558 or without modification, is permitted pursuant to, and subject 559 to the license terms contained in, the Simplified BSD License 560 set forth in Section 4.c of the IETF Trust's Legal Provisions 561 Relating to IETF Documents (http://trustee.ietf.org/license-info). 562 */ 564 /* Routines for computing the Anderson-Darling 2 sample 565 * test statistic. 566 * 567 * Implemented based on the description in 568 * "Anderson-Darling K Sample Test" Heckert, Alan and 569 * Filliben, James, editors, Dataplot Reference Manual, 570 * Chapter 15 Auxiliary, NIST, 2004. 571 * Official Reference by 2010 572 * Heckert, N. A. (2001). Dataplot website at the 573 * National Institute of Standards and Technology: 574 * http://www.itl.nist.gov/div898/software/dataplot.html/ 575 * June 2001. 576 */ 578 // this code is a modified version of the code in RFC6576 579 // use '-std=c++11' for compiling 581 #include 582 #include 583 #include 584 #include 585 #include 587 #include 589 using namespace std; 591 /* This function reads the values and sorts this in an ascending 592 * order. 593 * The format is: one value per line followed by a line break. 594 * A blank line at the end of the file will crash the program. 595 */ 596 vector read_file_sort (string filename) { 597 vector vec; 598 // variable for one line of the file and the value 599 string line; 600 double tmp; 602 ifstream file; 603 file.open(filename, ios::in); 604 if (!file) { 605 cout << "Error in file " << filename << endl; 606 } 607 else { 608 // read file in a vector 609 while(!file.eof()) { 610 getline (file, line); 611 tmp = stod (line); 612 vec.push_back(tmp); 613 } 614 // sort the vector ascending 615 sort(vec.begin(), vec.end()); 616 } 617 file.close(); 618 return vec; 619 } 621 int main(int argn, char *argv[]) { 623 if (argn != 1 && argn != 3) { 624 cout << "wrong invocation" << endl; 625 cout << "start with " << argv[0] << " file1 file2" << endl; 626 cout << "start with " << argv[0] << " without parameter, if \ 627 the files are named file1.csv and file2.csv" << endl; 628 return 1; 629 } 631 vector vec1, vec2; 632 double adk_result; 633 static int k, val_st_z_samp1, val_st_z_samp2, 634 val_eq_z_samp1, val_eq_z_samp2, 635 j, n_total, n_sample1, n_sample2, L, 636 max_number_samples, line, maxnumber_z; 637 static int column_1, column_2; 638 static double adk, n_value, z, sum_adk_samp1, 639 sum_adk_samp2, z_aux; 640 static double H_j, F1j, hj, F2j, denom_1_aux, denom_2_aux; 641 static bool next_z_sample2, equal_z_both_samples; 642 static int stop_loop1, stop_loop2, stop_loop3,old_eq_line2, 643 old_eq_line1; 645 static double adk_criterium = 1.993; 647 string filename1 = "file1.csv"; 648 string filename2 = "file2.csv"; 650 // if called with filenames 651 if (argn == 3) { 652 filename1 = argv[1]; 653 filename2 = argv[2]; 654 } 656 // sort the two files i a vector 657 vec1 = read_file_sort(filename1); 658 vec2 = read_file_sort(filename2); 660 k = 2; 661 n_sample1 = vec1.size() - 1; 662 n_sample2 = vec2.size() - 1; 664 // -1 because vec[0] is a dummy value 665 n_total = n_sample1 + n_sample2; 667 /* value equal to the line with a value = zj in sample 1. 668 * Here j=1, so the line is 1. 669 */ 670 val_eq_z_samp1 = 1; 672 /* value equal to the line with a value = zj in sample 2. 673 * Here j=1, so the line is 1. 675 */ 676 val_eq_z_samp2 = 1; 678 /* value equal to the last line with a value < zj 679 * in sample 1. Here j=1, so the line is 0. 680 */ 681 val_st_z_samp1 = 0; 683 /* value equal to the last line with a value < zj 684 * in sample 1. Here j=1, so the line is 0. 685 */ 686 val_st_z_samp2 = 0; 688 sum_adk_samp1 = 0; 689 sum_adk_samp2 = 0; 690 j = 1; 692 // as mentioned above, j=1 693 equal_z_both_samples = false; 695 next_z_sample2 = false; 697 // assuming the next z to be of sample 1 698 stop_loop1 = n_sample1 + 1; 700 // + 1 because vec[0] is a dummy, see n_sample1 declaration 701 stop_loop2 = n_sample2 + 1; 702 stop_loop3 = n_total + 1; 704 /* The required z values are calculated until all values 705 * of both samples have been taken into account. See the 706 * lines above for the stoploop values. Construct required 707 * to avoid a mathematical operation in the while condition. 708 */ 709 while (((stop_loop1 > val_eq_z_samp1) 711 || (stop_loop2 > val_eq_z_samp2)) && stop_loop3 > j) { 712 if (val_eq_z_samp1 < n_sample1+1) { 713 /* here, a preliminary zj value is set. 714 * See below how to calculate the actual zj. 715 */ 716 z = vec1[val_eq_z_samp1]; 718 /* this while sequence calculates the number of values 719 * equal to z. 720 */ 721 while ((val_eq_z_samp1+1 < n_sample1) 722 && z == vec1[val_eq_z_samp1+1] ) { 723 val_eq_z_samp1++; 724 } 725 } 726 else { 727 val_eq_z_samp1 = 0; 728 val_st_z_samp1 = n_sample1; 730 // this should be val_eq_z_samp1 - 1 = n_sample1 731 } 733 if (val_eq_z_samp2 < n_sample2+1) { 734 z_aux = vec2[val_eq_z_samp2]; 736 /* this while sequence calculates the number of values 737 * equal to z_aux 738 */ 740 while ((val_eq_z_samp2+1 < n_sample2) 741 && z_aux == vec2[val_eq_z_samp2+1] ) { 742 val_eq_z_samp2++; 743 } 745 /* the smaller of the two actual data values is picked 746 * as the next zj. 747 */ 749 if(z > z_aux) { 750 z = z_aux; 751 next_z_sample2 = true; 752 } 753 else { 754 if (z == z_aux) { 755 equal_z_both_samples = true; 756 } 758 /* This is the case if the last value of column1 is 759 * smaller than the remaining values of column2. 760 */ 761 if (val_eq_z_samp1 == 0) { 762 z = z_aux; 763 next_z_sample2 = true; 764 } 765 } 766 } 767 else { 768 val_eq_z_samp2 = 0; 769 val_st_z_samp2 = n_sample2; 770 // this should be val_eq_z_samp2 - 1 = n_sample2 771 } 773 /* in the following, sum j = 1 to L is calculated for 774 * sample 1 and sample 2. 775 */ 776 if (equal_z_both_samples) { 778 /* hj is the number of values in the combined sample 779 * equal to zj 780 */ 781 hj = val_eq_z_samp1 - val_st_z_samp1 782 + val_eq_z_samp2 - val_st_z_samp2; 784 /* H_j is the number of values in the combined sample 785 * smaller than zj plus one half the number of 786 * values in the combined sample equal to zj 787 * (that's hj/2). 788 */ 789 H_j = val_st_z_samp1 + val_st_z_samp2 + hj / 2; 791 /* F1j is the number of values in the 1st sample 792 * that are less than zj plus one half the number 793 * of values in this sample that are equal to zj. 794 */ 796 F1j = val_st_z_samp1 + (double) 797 (val_eq_z_samp1 - val_st_z_samp1) / 2; 799 /* F2j is the number of values in the 1st sample 800 * that are less than zj plus one half the number 801 * of values in this sample that are equal to zj. 802 */ 803 F2j = val_st_z_samp2 + (double) 804 (val_eq_z_samp2 - val_st_z_samp2) / 2; 806 /* set the line of values equal to zj to the 807 * actual line of the last value picked for zj. 808 */ 809 val_st_z_samp1 = val_eq_z_samp1; 811 /* Set the line of values equal to zj to the actual 812 * line of the last value picked for zj of each 813 * sample. This is required as data smaller than zj 814 * is accounted differently than values equal to zj. 815 */ 816 val_st_z_samp2 = val_eq_z_samp2; 817 /* next the lines of the next values z, i.e., zj+1 818 * are addressed. 819 */ 820 val_eq_z_samp1++; 822 /* next the lines of the next values z, i.e., 823 * zj+1 are addressed 824 */ 825 val_eq_z_samp2++; 826 } 827 else { 829 /* the smaller z value was contained in sample 2; 830 * hence, this value is the zj to base the following 831 * calculations on. 832 */ 833 if (next_z_sample2){ 834 /* hj is the number of values in the combined 835 * sample equal to zj; in this case, these are 836 * within sample 2 only. 837 */ 838 hj = val_eq_z_samp2 - val_st_z_samp2; 840 /* H_j is the number of values in the combined sample 841 * smaller than zj plus one half the number of 842 * values in the combined sample equal to zj 843 * (that's hj/2). 844 */ 845 H_j = val_st_z_samp1 + val_st_z_samp2 + hj / 2; 847 /* F1j is the number of values in the 1st sample that 848 * are less than zj plus one half the number of values in 849 * this sample that are equal to zj. 850 * As val_eq_z_samp2 < val_eq_z_samp1, these are the 851 * val_st_z_samp1 only. 852 */ 853 F1j = val_st_z_samp1; 855 /* F2j is the number of values in the 1st sample that 856 * are less than zj plus one half the number of values in 857 * this sample that are equal to zj. The latter are from 858 * sample 2 only in this case. 859 */ 861 F2j = val_st_z_samp2 + (double) 862 (val_eq_z_samp2 - val_st_z_samp2) / 2; 864 /* Set the line of values equal to zj to the actual line 865 * of the last value picked for zj of sample 2 only in 866 * this case. 867 */ 868 val_st_z_samp2 = val_eq_z_samp2; 870 /* next the line of the next value z, i.e., zj+1 is 871 * addressed. Here, only sample 2 must be addressed. 872 */ 874 val_eq_z_samp2++; 875 if (val_eq_z_samp1 == 0) { 876 val_eq_z_samp1 = stop_loop1; 877 } 878 } 879 /* the smaller z value was contained in sample 2; 880 * hence, this value is the zj to base the following 881 * calculations on. 882 */ 884 else { 886 /* hj is the number of values in the combined 887 * sample equal to zj; in this case, these are 888 * within sample 1 only. 889 */ 890 hj = val_eq_z_samp1 - val_st_z_samp1; 892 /* H_j is the number of values in the combined 893 * sample smaller than zj plus one half the number 894 * of values in the combined sample equal to zj 895 * (that's hj/2). 896 */ 898 H_j = val_st_z_samp1 + val_st_z_samp2 + hj / 2; 900 /* F1j is the number of values in the 1st sample that 901 * are less than zj plus; in this case, these are within 902 * sample 1 only one half the number of values in this 903 * sample that are equal to zj. The latter are from 904 * sample 1 only in this case. 905 */ 907 F1j = val_st_z_samp1 + (double) 908 (val_eq_z_samp1 - val_st_z_samp1) / 2; 910 /* F2j is the number of values in the 1st sample that 911 * are less than zj plus one half the number of values 912 * in this sample that are equal to zj. As 913 * val_eq_z_samp1 < val_eq_z_samp2, these are the 914 * val_st_z_samp2 only. 915 */ 917 F2j = val_st_z_samp2; 919 /* Set the line of values equal to zj to the actual line 920 * of the last value picked for zj of sample 1 only in 921 * this case. 922 */ 924 val_st_z_samp1 = val_eq_z_samp1; 925 /* next the line of the next value z, i.e., zj+1 is 926 * addressed. Here, only sample 1 must be addressed. 927 */ 928 val_eq_z_samp1++; 930 if (val_eq_z_samp2 == 0) { 931 val_eq_z_samp2 = stop_loop2; 932 } 933 } 934 } 936 denom_1_aux = n_total * F1j - n_sample1 * H_j; 937 denom_2_aux = n_total * F2j - n_sample2 * H_j; 939 sum_adk_samp1 = sum_adk_samp1 + hj 940 * (denom_1_aux * denom_1_aux) / 941 (H_j * (n_total - H_j) 942 - n_total * hj / 4); 943 sum_adk_samp2 = sum_adk_samp2 + hj 944 * (denom_2_aux * denom_2_aux) / 945 (H_j * (n_total - H_j) 946 - n_total * hj / 4); 948 next_z_sample2 = false; 949 equal_z_both_samples = false; 951 /* index to count the z. It is only required to prevent 952 * the while slope to execute endless 953 */ 954 j++; 955 } 957 // calculating the adk value is the final step. 958 adk_result = (double) (n_total - 1) / (n_total 959 * n_total * (k - 1)) 960 * (sum_adk_samp1 / n_sample1 961 + sum_adk_samp2 / n_sample2); 963 /* if(adk_result <= adk_criterium) 964 * adk_2_sample test is passed 965 */ 966 //return adk_result <= adk_criterium; 967 cout << "Result: " << adk_result << endl; 968 } 970 Authors' Addresses 972 Raik Leipnitz (editor) 973 Deutsche Telekom 974 Olgastr. 67 975 Ulm 89073 976 Germany 978 Email: r.leipnitz@telekom.de 980 Ruediger Geib 981 Deutsche Telekom 982 Heinrich Hertz Str. 3-7 983 Darmstadt 64295 984 Germany 986 Phone: +49 6151 5812747 987 Email: Ruediger.Geib@telekom.de