idnits 2.17.1 draft-li-mpls-entropy-01.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 : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([RFC6790], [I-D.bocci-mpls-miad-adi-requirements], [I-D.andersson-mpls-mna-fwk]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (12 May 2022) is 715 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: '1' on line 762 -- Looks like a reference, but probably isn't: '2' on line 763 -- Looks like a reference, but probably isn't: '3' on line 764 -- Looks like a reference, but probably isn't: '0' on line 709 == Outdated reference: A later version (-04) exists of draft-andersson-mpls-mna-fwk-01 Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 MPLS Working Group T. Li 3 Internet-Draft Juniper Networks 4 Intended status: Informational 12 May 2022 5 Expires: 13 November 2022 7 Entropy Values 8 draft-li-mpls-entropy-01 10 Abstract 12 Equal Cost Multi-Path (ECMP) forwarding is an essential function in 13 distributing traffic across parallel paths. Packets within a flow 14 must be kept on a single path to avoid reordering, while different 15 flows must be distributed across paths to achieve parallelism. 17 Previously, MPLS has addressed this through the use of an entropy 18 label, providing up to 20 bits of entropy that can be added to the 19 label stack to distinguish different flows. [RFC6790] With the 20 interest in MPLS Network Actions, there are proposals to embedding 21 entropy into alternate structures, so it is an appropriate time to 22 consider how many bits should be used for entropy in the future. 23 [I-D.bocci-mpls-miad-adi-requirements][I-D.andersson-mpls-mna-fwk] 25 In this document, we examine the question of how to provide adequate 26 entropy through a simple stochastic simulation. This is not intended 27 to be a comprehensive and extensive treatise, but rather a simple 28 investigation to build intuition into the issues. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on 13 November 2022. 47 Copyright Notice 49 Copyright (c) 2022 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 54 license-info) in effect on the date of publication of this document. 55 Please review these documents carefully, as they describe your rights 56 and restrictions with respect to this document. Code Components 57 extracted from this document must include Revised BSD License text as 58 described in Section 4.e of the Trust Legal Provisions and are 59 provided without warranty as described in the Revised BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 64 1.1. Model . . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 1.2. Methodology . . . . . . . . . . . . . . . . . . . . . . . 3 66 2. Randomness . . . . . . . . . . . . . . . . . . . . . . . . . 3 67 3. Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 68 4. Future Hardware Considerations . . . . . . . . . . . . . . . 5 69 5. Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 70 6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 6 71 7. Validation . . . . . . . . . . . . . . . . . . . . . . . . . 8 72 8. Security Considerations . . . . . . . . . . . . . . . . . . . 9 73 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 74 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 75 10.1. Normative References . . . . . . . . . . . . . . . . . . 9 76 10.2. Informative References . . . . . . . . . . . . . . . . . 9 77 Appendix A. Source Code . . . . . . . . . . . . . . . . . . . . 10 78 Appendix B. Full results . . . . . . . . . . . . . . . . . . . . 17 79 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 41 81 1. Introduction 83 Equal Cost Multi-Path (ECMP) forwarding is an essential function in 84 distributing traffic across parallel paths. Packets within a flow 85 must be kept on a single path to avoid reordering, while different 86 flows must be distributed across paths to achieve parallelism. 88 Previously, MPLS has addressed this through the use of an entropy 89 label, providing up to 20 bits of entropy that can be added to the 90 label stack to distinguish different flows. [RFC6790] With the 91 interest in MPLS Network Actions, there are proposals to embedding 92 entropy into alternate structures, so it is an appropriate time to 93 consider how many bits should be used for entropy in the future. 94 [I-D.bocci-mpls-miad-adi-requirements][I-D.andersson-mpls-mna-fwk] 95 In this document, we examine the question of how to provide adequate 96 entropy through a simple stochastic simulation. This is not intended 97 to be a comprehensive and extensive treatise, but rather a simple 98 investigation to build intuition into the issues. 100 1.1. Model 102 In a typical ECMP situation, a Label Edge Router (LER) [RFC4221] 103 would examine incoming traffic and use values in the incoming packet 104 to compute an Entropy Label (EL). This would be placed in the label 105 stack. Subsequent routers on the path could use this EL as input to 106 a hashing function and the resulting hash value would then be used to 107 select one of the possible output paths. If the entropy label and 108 the hashing function are implemented correctly, packets would be 109 uniformly distributed across the possible paths. If packet sizes are 110 uniformly distributed, this would also imply that bandwidth would be 111 uniformly distributed across paths. 113 Moving forward, we expect that entropy will continue to be carried in 114 the label stack, but may not occupy a Label field inside of a Label 115 Stack Entry (LSE) [RFC3032]. We generalize this to an Entropy Value 116 (EV) and seek to understand the necessary size of this field. 118 1.2. Methodology 120 To study this, we employ a pseudo-random number generator to create 121 Entropy Values and then we apply a hashing function to them. 122 Ideally, the results of the hash will be uniformly distributed. 123 Error metrics are used to characterize how far results are from this 124 ideal. 126 2. Randomness 128 Real hardware does not use a random number generator to create 129 entropy. Doing so would require mapping each flow to an entropy 130 value and this would be painful to implement due to scale. Rather, 131 implementations that we are familiar with use a hashing function on 132 the packet header to create an entropy value. Ideally, the results 133 of this would be uniformly distributed. However, we cannot assume 134 that all traffic will be quite so cooperative. 136 Conversely, we also cannot assume that the LER will generate no 137 entropy. If an LER does nothing except place a constant in the 138 entropy value, no downstream hashing function will be able to extract 139 any entropy. 141 To model this, we intentionally choose an imperfect random number 142 generator, specifically, we choose one that has a normal distribution 143 (i.e., Gaussian or bell curve). This should produce many different 144 entropy values and if the hashing function is doing its job, the 145 resulting entropy should result in a uniform distribution of hash 146 values. 148 3. Hashing 150 Similarly, there is no standardized way of implementing the hash 151 function that downstream routers will use to convert an entropy value 152 into a hash value. In cases where the entropy value has more bits 153 than the hash value can support, it is up to the hashing function to 154 fold the entropy from all of the entropy value bits into the hash 155 value. 157 Thus, we consider a number of hashing functions: 159 * Addition: High order bits are added to the low order bits to 160 produce the hash value. 162 * Masking: High order bits are simply discarded. 164 * Mixing and Masking: Bits are shifted, added, and then masked. 166 * Xor: High order bits are XOR'ed into the low order bits. 168 * CRC-CCITT: Compute a CRC over the entropy value and XOR the 169 resulting bits together. 171 * MD4: Compute the MD4 digest over the entropy value and XOR the 172 resulting bits together. 174 * MD4: Compute the MD5 digest over the entropy value and XOR the 175 resulting bits together. 177 * SHA1: Compute the SHA1 digest over the entropy value and XOR the 178 resulting bits together. 180 * SHA256: Compute the SHA256 digest over the entropy value and XOR 181 the resulting bits together. 183 Some of these hash functions work better than others. Additional 184 hash functions could easily be added. 186 To simplify our simulation, we have primarily focused on hashes that 187 have a range that is a power of two. However, in a practical 188 application, that is not appropriate and the range must be an 189 arbitrary integer, so that we can support n-way ECMP. This is 190 discussed further below. 192 4. Future Hardware Considerations 194 When ECMP was first implemented, 4-way ECMP was the norm. In the 195 early days of sparse networks, that was frequently adequate. As the 196 number of interfaces on a router has grown, ECMP has followed suit, 197 and 128-way and 256-way ECMP is now in production. 199 While hardware has provided an impetetus to grow the breadth of ECMP, 200 it is also suggesting that there is an upper bound to what needs to 201 be supported. It is fairly clear that with current networking 202 trends, we will never need more paths from a single router than it 203 has physical interfaces. While logically, more would be possible, 204 the growth in bandwidth has driven the need for ECMP and that 205 bandwidth is most easily provided through the use of non-fractional 206 interfaces. 208 Concurrently, we note a trend away from building multi-chassis 209 routers with an arbitrary number of physical interfaces, so this 210 implies a bound of around 1000 physical interface per router for the 211 foreseable future. 213 Hardware is also most conveniently impelemented on power of two 214 boundaries. Thus, we investigate ECMP from 4-way to 4096-way, in 215 powers of two. 217 5. Results 219 For hash values from 8 to 12 bits, we consider entropy values with 0 220 to 5 additional bits (i.e., 8 to 17 bits). We generate enough random 221 samples so that each hash bucket should ideally have 1000 entries. 223 The error for each has bucket is then difference between the number 224 of hash results and 1000. We then compute the following error 225 metrics for each combination of algorithm, hash value bits, and 226 additional bits: 228 * Root Mean Square Error (RMSE): The Root Mean Square Error is the 229 square root of the sum of the squares of the errors for each 230 bucket, divided by the number of buckets. 232 * Mean Average Error (MAE): The Mean Average Error is the arithmetic 233 mean of the absolute value of the error for each bucket. 235 * Mean Average Percentage Error (MAPE): The Mean Average Percentage 236 Error is the arithmetic mean of the percentage of error for each 237 bucket. 239 We then summarize the results based on the number of additional bits 240 and on algorithm, computing the mean of each of the above metrics. 242 6. Conclusion 244 The arguments in Section 4 suggest that 4096-way ECMP will be 245 sufficient for some time to come. This suggests that a base of 12 246 bits would be a good start. 248 We arbitrarily select a MAPE of 5.0 as a threshold of acceptability. 249 This represents a distribution that is within 5% of our goal of a 250 uniform distribution. 252 A solution to the issue would be a number of bits entropy value and a 253 set of hashing algorithms that would provide acceptable performance 254 over the full range of hash values, from 2 to 12 bits. 256 We observe that for some entropy values, we get unacceptable 257 solutions across all algorithms: 259 For 2-way ECMP with 0 more bits of entropy: 260 +-----------+-------+-------+------+ 261 | Hash | RMSE | MAE | MAPE | 262 +-----------+-------+-------+------+ 263 | add | 687.0 | 687.0 | 68.7 | 264 | mask | 378.0 | 378.0 | 37.8 | 265 | xor | 687.0 | 687.0 | 68.7 | 266 | crc-ccitt | 687.0 | 687.0 | 68.7 | 267 | md4 | 687.0 | 687.0 | 68.7 | 268 | md5 | 376.0 | 376.0 | 37.6 | 269 | sha1 | 378.0 | 378.0 | 37.8 | 270 | sha256 | 378.0 | 378.0 | 37.8 | 271 +-----------+-------+-------+------+ 273 Clearly, a 2 bit entropy value is not acceptable. 275 We also observe that some algorithms perform better than others: 277 For 16-way ECMP with 1 more bits of entropy: 278 +-----------+-------+-------+------+ 279 | Hash | RMSE | MAE | MAPE | 280 +-----------+-------+-------+------+ 281 | add | 46.0 | 35.0 | 3.5 | 282 | mask | 30.1 | 27.2 | 2.7 | 283 | xor | 48.3 | 43.9 | 4.4 | 284 | crc-ccitt | 24.4 | 19.9 | 2.0 | 285 | md4 | 234.5 | 197.4 | 19.7 | 286 | md5 | 262.5 | 196.1 | 19.6 | 287 | sha1 | 183.4 | 150.0 | 15.0 | 288 | sha256 | 281.1 | 251.2 | 25.1 | 289 +-----------+-------+-------+------+ 291 Understanding why some algorithms perform poorly is not understood at 292 this time and a subject for future research. 294 Once we reach about 10 bits of entropy value, most algorithms work 295 well, most of the time: 297 For 1024-way ECMP with 0 more bits of entropy: 298 +-----------+------+------+------+ 299 | Hash | RMSE | MAE | MAPE | 300 +-----------+------+------+------+ 301 | add | 32.2 | 25.8 | 2.6 | 302 | mask | 32.6 | 26.2 | 2.6 | 303 | xor | 33.5 | 26.6 | 2.7 | 304 | crc-ccitt | 31.2 | 24.9 | 2.5 | 305 | md4 | 55.4 | 44.4 | 4.4 | 306 | md5 | 55.9 | 44.7 | 4.5 | 307 | sha1 | 57.2 | 45.4 | 4.5 | 308 | sha256 | 57.0 | 46.1 | 4.6 | 309 +-----------+------+------+------+ 311 For 256-way ECMP with 2 more bits of entropy: 312 +-----------+------+------+------+ 313 | Hash | RMSE | MAE | MAPE | 314 +-----------+------+------+------+ 315 | add | 30.3 | 23.9 | 2.4 | 316 | mask | 32.6 | 26.2 | 2.6 | 317 | xor | 28.9 | 23.1 | 2.3 | 318 | crc-ccitt | 35.2 | 28.0 | 2.8 | 319 | md4 | 59.0 | 46.5 | 4.6 | 320 | md5 | 54.7 | 44.0 | 4.4 | 321 | sha1 | 56.8 | 44.3 | 4.4 | 322 | sha256 | 54.5 | 44.1 | 4.4 | 323 +-----------+------+------+------+ 324 If we look at summaries by additional bits and by algorithm we see: 326 Error per added bit 327 +------------+-------+-------+-------+ 328 | Added bits | MRMSE | MMAE | MMAPE | 329 +------------+-------+-------+-------+ 330 | 0 | 171.0 | 150.6 | 15.1 | 331 | 1 | 115.8 | 100.2 | 10.0 | 332 | 2 | 74.9 | 61.6 | 6.2 | 333 | 3 | 58.5 | 49.0 | 4.9 | 334 | 4 | 51.1 | 43.2 | 4.3 | 335 | 5 | 47.1 | 39.8 | 4.0 | 336 +------------+-------+-------+-------+ 338 Error per algorithm 339 +-----------+-------+-------+-------+ 340 | Algorithm | MRMSE | MMAE | MMAPE | 341 +-----------+-------+-------+-------+ 342 | add | 52.7 | 45.8 | 4.6 | 343 | mask | 34.1 | 28.6 | 2.9 | 344 | xor | 54.0 | 48.0 | 4.8 | 345 | crc-ccitt | 48.7 | 43.2 | 4.3 | 346 | md4 | 137.7 | 119.8 | 12.0 | 347 | md5 | 131.3 | 110.7 | 11.1 | 348 | sha1 | 110.5 | 93.0 | 9.3 | 349 | sha256 | 122.2 | 103.3 | 10.3 | 350 +-----------+-------+-------+-------+ 352 This leads us to propose that use at least 4 additional bits for our 353 entropy value, resulting in total of 16 (12 + 4). Please note that 354 this is a minimum. Most proposals are proposing higher numbers of 355 bits, thus exceeding this minimum. 357 7. Validation 359 To further validate that 16 bits of entropy is sufficient, we also 360 simulated hashing with a non-power of two result to support n-way 361 ECMP. To map the hash to a range of n possible results, we performed 362 a 'mod n' operation after each of the above hashes. We then selected 363 10 random n values that are not powers of two and repeated the above 364 experiment. 366 In this step, we generated 16 bits of entropy, hashed that and then 367 folded it to down to 16 bits. We then applied the 'mod n' operation 368 to get down to a range of n results. In these circumstances, the 369 'add', 'mask', and 'xor' hashes are all identical and result in no 370 changes, as they simply are the identity function on 16 bits. The 371 'add' and 'xor' functions were removed for efficiency. 373 The results demonstrate that the 'mask' (identity) function performs 374 adequately in this circumstance, again supporting the claim that 16 375 bits is sufficient entropy. 377 For 3023-way ECMP, 16 bits of entropy: 378 +-----------+-------+-------+------+ 379 | Hash | RMSE | MAE | MAPE | 380 +-----------+-------+-------+------+ 381 | mask | 31.8 | 25.6 | 2.6 | 382 | crc-ccitt | 238.2 | 191.1 | 19.1 | 383 | md4 | 320.7 | 254.9 | 25.5 | 384 | md5 | 319.7 | 253.8 | 25.4 | 385 | sha1 | 329.1 | 262.8 | 26.3 | 386 | sha256 | 328.0 | 261.6 | 26.2 | 387 +-----------+-------+-------+------+ 389 8. Security Considerations 391 No security issues are discussed in this document. 393 9. IANA Considerations 395 This document makes no requests of IANA. 397 10. References 399 10.1. Normative References 401 [RFC6790] Kompella, K., Drake, J., Amante, S., Henderickx, W., and 402 L. Yong, "The Use of Entropy Labels in MPLS Forwarding", 403 RFC 6790, DOI 10.17487/RFC6790, November 2012, 404 . 406 [RFC4221] Nadeau, T., Srinivasan, C., and A. Farrel, "Multiprotocol 407 Label Switching (MPLS) Management Overview", RFC 4221, 408 DOI 10.17487/RFC4221, November 2005, 409 . 411 [RFC3032] Rosen, E., Tappan, D., Fedorkow, G., Rekhter, Y., 412 Farinacci, D., Li, T., and A. Conta, "MPLS Label Stack 413 Encoding", RFC 3032, DOI 10.17487/RFC3032, January 2001, 414 . 416 10.2. Informative References 418 [I-D.bocci-mpls-miad-adi-requirements] 419 Bocci, M. and S. Bryant, "Requirements for MPLS Network 420 Action Indicators and MPLS Ancillary Data", Work in 421 Progress, Internet-Draft, draft-bocci-mpls-miad-adi- 422 requirements-04, 11 April 2022, 423 . 426 [I-D.andersson-mpls-mna-fwk] 427 Andersson, L., Bryant, S., Bocci, M., and T. Li, "MPLS 428 Network Actions Framework", Work in Progress, Internet- 429 Draft, draft-andersson-mpls-mna-fwk-01, 27 April 2022, 430 . 433 Appendix A. Source Code 435 #!/usr/bin/python3 436 # 437 # Copyright 2022, Juniper Networks, Inc. 438 # Tony Li (tli) 439 # 440 # Statistical study on the number of entropy bits necessary. 441 # 442 # Equal Cost Multi-Path (ECMP) forwarding directs traffic down 443 # multiple paths. An entropy label is included in the MPLS label 444 # stack or in the MPLS Network Action sub-stack to help 445 # implementations keep individual flows on a consistent path but 446 # spread different flows across different paths. 447 # 448 # The entropy label is supposed to be used by an implementation 449 # as input to a hash function, producing a hash value that is an 450 # index into the set of paths. If the hash values are uniformly 451 # distributed, then the paths will be equally used. If the hash 452 # function is poor or there is not enough entropy in the entropy 453 # label, then the hash values will not be uniformly distribute. 454 # 455 # To gain some intuition about how many bits of entropy are 456 # necessary, we simulate the hashing of a large number of random 457 # values and then measure the uniformity of the results. 458 # 460 import crcmod 461 from numpy import random, round 462 import matplotlib.pyplot as plt 463 import math 464 from tabulate import tabulate 465 import binascii 466 import hashlib 468 # To get an interesting volume of data, we need about this many 469 # samples per bucket. 470 DEPTH = 1000 472 # ECMP is typically up to N way, where N is 2 ** P. We study a 473 # range of P values to get an understanding of the number of 474 # necessary bits as a function of P. 476 P_RANGE = range(1, 13) 477 #P_RANGE = range(2, 6) 479 # Consider this many additional bits of entropy, above and beyond 480 # P. 481 MORE_BITS_RANGE = range(0, 6) 483 # Format for floating point numbers 484 FLT = '%.1f' 486 class HashFunc(object): 487 def __init__ (self, p, name): 488 self.bits = p 489 self.name = name 490 # Mask of bits inside of the target range 491 self.lowmask = (2 ** p - 1) 492 # Mask of bits outside of the target range 493 self.highmask = ~self.lowmask 495 def hashfunc(self, v): 496 raise NotImplementedError() 498 class AddHash(HashFunc): 499 def __init__(self, p): 500 super().__init__(p, 'add') 502 def hashfunc(self, v): 503 old = v 504 if self.highmask & v: 505 v = (v & self.lowmask) + ((v & self.highmask) >> 506 self.bits) 507 return v & self.lowmask 509 class MaskHash(HashFunc): 510 def __init__(self, p): 511 super().__init__(p, 'mask') 513 def hashfunc(self, v): 514 return v & self.lowmask 516 class XorHash(HashFunc): 518 def __init__(self, p): 519 super().__init__(p, 'xor') 521 def hashfunc(self, v): 522 while self.highmask & v: 523 v = (v & self.lowmask) ^ ((v & self.highmask) >> 524 self.bits) 525 return v 527 class CrcHash(HashFunc): 528 # CRC-CCITT 529 def __init__(self, p): 530 super().__init__(p, 'crc-ccitt') 532 def hashfunc(self, v): 533 v = binascii.crc_hqx(v.to_bytes(4, 'little'), 0) 534 while self.highmask & v: 535 v = (v & self.lowmask) ^ ((v & self.highmask) >> 536 self.bits) 537 return v 539 class Md4Hash(HashFunc): 540 def __init__(self, p): 541 super().__init__(p, 'md4') 542 self.func = hashlib.new('md4') 544 def hashfunc(self, v): 545 m = self.func.copy() 546 m.update(v.to_bytes(4, 'little')) 547 d = m.digest() 548 v = int.from_bytes(d, 'little') 549 while self.highmask & v: 550 v = (v & self.lowmask) ^ ((v & self.highmask) >> 551 self.bits) 552 return v 554 class Md5Hash(HashFunc): 555 def __init__(self, p): 556 super().__init__(p, 'md5') 557 self.func = hashlib.md5() 559 def hashfunc(self, v): 560 m = self.func.copy() 561 m.update(v.to_bytes(4, 'little')) 562 d = m.digest() 563 v = int.from_bytes(d, 'little') 564 while self.highmask & v: 565 v = (v & self.lowmask) ^ ((v & self.highmask) >> 566 self.bits) 567 return v 569 class Sha1Hash(HashFunc): 570 def __init__(self, p): 571 super().__init__(p, 'sha1') 572 self.func = hashlib.sha1() 574 def hashfunc(self, v): 575 m = self.func.copy() 576 m.update(v.to_bytes(4, 'little')) 577 d = m.digest() 578 v = int.from_bytes(d, 'little') 579 while self.highmask & v: 580 v = (v & self.lowmask) ^ ((v & self.highmask) >> 581 self.bits) 582 return v 584 class Sha256Hash(HashFunc): 585 def __init__(self, p): 586 super().__init__(p, 'sha256') 587 self.func = hashlib.sha256() 589 def hashfunc(self, v): 590 m = self.func.copy() 591 m.update(v.to_bytes(4, 'little')) 592 d = m.digest() 593 v = int.from_bytes(d, 'little') 594 while self.highmask & v: 595 v = (v & self.lowmask) ^ ((v & self.highmask) >> 596 self.bits) 597 return v 599 def rmse( error ): 600 # Compute the root mean square error of this run. 601 errsq = [ err ** 2 for err in error ] 602 rmse = math.sqrt( sum( errsq ) / len( error ) ) 603 return rmse 605 def mae( error ): 606 # Compute the mean average error of this run. 607 mae = sum( [ abs( err ) for err in error ] ) / len( error ) 608 return mae 610 def mape( error ): 611 # Compute the mean average percentage error of this run. 612 mape = 0.0 613 for ( ind, err ) in enumerate( error ): 615 if err != 0.0: 616 mape += abs( err / DEPTH) 617 mape = mape / len( error ) 618 return mape * 100.0 620 def mean(vec): 621 return sum(vec)/len(vec) 623 def samples(buckets, bits): 624 # Uniform distribution 625 #samples = random.randint(0, (2 ** bits), buckets * DEPTH) 626 # Normal distribution 627 # This emulates a 'poor' random number generator 628 floats = random.normal(2 ** (bits - 1), 629 scale=2 ** (bits - 3), 630 size=(buckets * DEPTH)) 631 rounded = round(floats) 632 samples = [ int(x) for x in rounded ] 633 samples = [ x if x > 0 else -x for x in samples ] 634 samples = [ x if x < 2 ** bits else (2 ** bits - 1) for x in 635 samples ] 636 # Debugging 637 # print (samples) 638 # 639 #count, bins, ignored = plt.hist(samples, bins = 2 ** bits) 640 #plt.title('Random samples using %d bits of entropy' % 641 # bits) 642 #plt.show() 643 # 644 return samples 646 headers = ['Hash', 'RMSE', 'MAE', 'MAPE'] 647 summary_headers = ['Added bits', 'MRMSE', 'MMAE', 'MMAPE'] 648 algo_summary_headers = ['Algorithm', 'MRMSE', 'MMAE', 'MMAPE'] 650 def power_of_two(): 652 def simulate(p, bits): 653 total = p + bits 654 entropy = samples(2 ** p, total) 655 hashes = [ AddHash(p), MaskHash(p), XorHash(p), CrcHash(p), 656 Md4Hash(p), Md5Hash(p), Sha1Hash(p), 657 Sha256Hash(p) ] 658 results = [] 659 for h in hashes: 660 hashvals = [ h.hashfunc(x) for x in entropy ] 661 # print(hashvals) 662 buckets = [ 0 ] * 2 ** p 663 for x in hashvals: 664 buckets[x] += 1 665 # print(h.name, buckets, sum(buckets)) 666 error = [ DEPTH - x for x in buckets ] 667 # print(error) 668 # print(rmse(error), mae(error), mape(error)) 669 results.append( [ h.name, FLT % rmse(error), FLT % 670 mae(error), FLT % mape(error) ] ) 671 return results 673 summary = [] 674 per_algo = {} 675 for more in MORE_BITS_RANGE: 676 per_bit = [] 677 for p in P_RANGE: 678 print( 'For %d-way ECMP with %d more bits of entropy:' % 679 (2 ** p, more)) 680 results = simulate(p, p + more) 681 print(tabulate(results, headers=headers, tablefmt='pretty', 682 stralign='right')) 683 rmsevec = [ float(x[1]) for x in results ] 684 maevec = [ float(x[2]) for x in results ] 685 mapevec = [ float(x[3]) for x in results ] 686 per_bit.append([FLT % mean(rmsevec), FLT % mean(maevec), 687 FLT % mean(mapevec)]) 688 print() 690 for result in results: 691 if not per_algo.get(result[0]): 692 per_algo[result[0]] = [ [], [], [] ] 693 for i in range(1,4): 694 per_algo[result[0]][i-1].append(float(result[i])) 696 rmsevec = [ float(x[0]) for x in per_bit ] 697 maevec = [ float(x[1]) for x in per_bit ] 698 mapevec = [ float(x[2]) for x in per_bit ] 699 summary.append([more, FLT % mean(rmsevec), FLT % mean(maevec), 700 FLT % mean(mapevec)]) 702 print('Error per added bit') 703 print(tabulate(summary, headers=summary_headers, 704 tablefmt='pretty', stralign='right')) 706 algo_summary = [] 707 for algo in per_algo: 708 algo_summary.append([algo, 709 FLT % mean(per_algo[algo][0]), 710 FLT % mean(per_algo[algo][1]), 711 FLT % mean(per_algo[algo][2])]) 712 print('\nError per algorithm') 713 print(tabulate(algo_summary, headers=algo_summary_headers, 714 tablefmt='pretty', stralign='right')) 716 def multibit(): 717 # Analyze hashes for non-power-of-two ranges. 718 ENTROPY_BITS = 16 719 SAMPLES = 10 721 # For this case, Add, Xor, and Mask are equivalent: a NOP 722 hashes = [ #AddHash(ENTROPY_BITS), XorHash(ENTROPY_BITS), 723 MaskHash(ENTROPY_BITS), CrcHash(ENTROPY_BITS), 724 Md4Hash(ENTROPY_BITS), Md5Hash(ENTROPY_BITS), 725 Sha1Hash(ENTROPY_BITS), Sha256Hash(ENTROPY_BITS) ] 727 def waygen(): 728 start = 2 ** min(P_RANGE) 729 stop = 2 ** max(P_RANGE) 730 for x in range(start, stop): 731 # Don't bother with powers of two again. 732 if x & (x - 1) != 0: 733 yield x 735 def simulate(nways): 736 entropy = samples(nways, ENTROPY_BITS) 737 results = [] 738 for h in hashes: 739 hashvals = [ h.hashfunc(x) for x in entropy ] 740 # print(hashvals) 741 buckets = [ 0 ] * nways 742 for x in hashvals: 743 buckets[x % nways] += 1 744 #print(h.name, buckets, sum(buckets)) 745 error = [ DEPTH - x for x in buckets ] 746 # print(error) 747 results.append( [ h.name, FLT % rmse(error), FLT % 748 mae(error), FLT % mape(error) ] ) 749 return results 751 per_way = [] 752 nways = [ x for x in waygen() ] 753 for nway in random.choice(nways, size=SAMPLES, replace=False): 754 results = simulate(nway) 755 print('\nFor %d-way ECMP, %d bits of entropy:' % 756 (nway, ENTROPY_BITS)) 757 print(tabulate(results, headers=headers, tablefmt='pretty', 758 stralign='right')) 760 # print('%d-way' % nway) 762 rmsevec = [ float(x[1]) for x in results ] 763 maevec = [ float(x[2]) for x in results ] 764 mapevec = [ float(x[3]) for x in results ] 765 per_way.append([nway, FLT % mean(rmsevec), 766 FLT % mean(maevec), FLT % mean(mapevec)]) 768 summary_headers = ['n-ways', 'MRMSE', 'MMAE', 'MMAPE'] 769 print('\nFor n-way ECMP, with %d bits of entropy, ' 770 'across hash functions' % ENTROPY_BITS) 771 print(tabulate(per_way, headers=summary_headers, 772 tablefmt='pretty', 773 stralign='right')) 775 power_of_two() 776 multibit() 778 Appendix B. Full results 780 For 2-way ECMP with 0 more bits of entropy: 781 +-----------+-------+-------+------+ 782 | Hash | RMSE | MAE | MAPE | 783 +-----------+-------+-------+------+ 784 | add | 687.0 | 687.0 | 68.7 | 785 | mask | 378.0 | 378.0 | 37.8 | 786 | xor | 687.0 | 687.0 | 68.7 | 787 | crc-ccitt | 687.0 | 687.0 | 68.7 | 788 | md4 | 687.0 | 687.0 | 68.7 | 789 | md5 | 376.0 | 376.0 | 37.6 | 790 | sha1 | 378.0 | 378.0 | 37.8 | 791 | sha256 | 378.0 | 378.0 | 37.8 | 792 +-----------+-------+-------+------+ 794 For 4-way ECMP with 0 more bits of entropy: 795 +-----------+-------+-------+------+ 796 | Hash | RMSE | MAE | MAPE | 797 +-----------+-------+-------+------+ 798 | add | 376.0 | 315.5 | 31.6 | 799 | mask | 39.0 | 36.5 | 3.7 | 800 | xor | 470.9 | 444.0 | 44.4 | 801 | crc-ccitt | 56.5 | 48.5 | 4.9 | 802 | md4 | 990.4 | 936.0 | 93.6 | 803 | md5 | 532.6 | 504.0 | 50.4 | 804 | sha1 | 593.1 | 500.0 | 50.0 | 805 | sha256 | 358.4 | 260.5 | 26.1 | 806 +-----------+-------+-------+------+ 807 For 8-way ECMP with 0 more bits of entropy: 808 +-----------+-------+-------+------+ 809 | Hash | RMSE | MAE | MAPE | 810 +-----------+-------+-------+------+ 811 | add | 167.9 | 150.8 | 15.1 | 812 | mask | 35.5 | 28.8 | 2.9 | 813 | xor | 227.2 | 213.2 | 21.3 | 814 | crc-ccitt | 443.4 | 442.5 | 44.2 | 815 | md4 | 355.3 | 277.8 | 27.8 | 816 | md5 | 292.2 | 252.2 | 25.2 | 817 | sha1 | 321.3 | 284.8 | 28.5 | 818 | sha256 | 439.9 | 377.8 | 37.8 | 819 +-----------+-------+-------+------+ 821 For 16-way ECMP with 0 more bits of entropy: 822 +-----------+-------+-------+------+ 823 | Hash | RMSE | MAE | MAPE | 824 +-----------+-------+-------+------+ 825 | add | 75.4 | 60.1 | 6.0 | 826 | mask | 40.2 | 35.8 | 3.6 | 827 | xor | 120.2 | 112.0 | 11.2 | 828 | crc-ccitt | 33.6 | 28.6 | 2.9 | 829 | md4 | 423.0 | 316.2 | 31.6 | 830 | md5 | 374.6 | 272.2 | 27.2 | 831 | sha1 | 345.7 | 282.9 | 28.3 | 832 | sha256 | 407.9 | 285.5 | 28.5 | 833 +-----------+-------+-------+------+ 835 For 32-way ECMP with 0 more bits of entropy: 836 +-----------+-------+-------+------+ 837 | Hash | RMSE | MAE | MAPE | 838 +-----------+-------+-------+------+ 839 | add | 50.9 | 44.6 | 4.5 | 840 | mask | 32.1 | 26.8 | 2.7 | 841 | xor | 58.5 | 48.7 | 4.9 | 842 | crc-ccitt | 32.7 | 29.1 | 2.9 | 843 | md4 | 251.6 | 191.8 | 19.2 | 844 | md5 | 245.9 | 202.4 | 20.2 | 845 | sha1 | 274.4 | 228.1 | 22.8 | 846 | sha256 | 257.5 | 211.2 | 21.1 | 847 +-----------+-------+-------+------+ 849 For 64-way ECMP with 0 more bits of entropy: 850 +-----------+-------+-------+------+ 851 | Hash | RMSE | MAE | MAPE | 852 +-----------+-------+-------+------+ 853 | add | 33.5 | 26.2 | 2.6 | 854 | mask | 25.1 | 18.7 | 1.9 | 855 | xor | 33.1 | 27.1 | 2.7 | 856 | crc-ccitt | 32.9 | 26.4 | 2.6 | 857 | md4 | 204.7 | 168.9 | 16.9 | 858 | md5 | 173.4 | 140.5 | 14.0 | 859 | sha1 | 227.9 | 182.1 | 18.2 | 860 | sha256 | 165.2 | 131.5 | 13.2 | 861 +-----------+-------+-------+------+ 863 For 128-way ECMP with 0 more bits of entropy: 864 +-----------+-------+-------+------+ 865 | Hash | RMSE | MAE | MAPE | 866 +-----------+-------+-------+------+ 867 | add | 27.8 | 22.4 | 2.2 | 868 | mask | 30.9 | 24.8 | 2.5 | 869 | xor | 34.2 | 26.9 | 2.7 | 870 | crc-ccitt | 33.2 | 27.0 | 2.7 | 871 | md4 | 131.9 | 105.5 | 10.5 | 872 | md5 | 123.1 | 100.9 | 10.1 | 873 | sha1 | 129.5 | 106.8 | 10.7 | 874 | sha256 | 133.4 | 105.0 | 10.5 | 875 +-----------+-------+-------+------+ 877 For 256-way ECMP with 0 more bits of entropy: 878 +-----------+-------+------+------+ 879 | Hash | RMSE | MAE | MAPE | 880 +-----------+-------+------+------+ 881 | add | 29.6 | 23.8 | 2.4 | 882 | mask | 31.4 | 25.1 | 2.5 | 883 | xor | 32.5 | 26.1 | 2.6 | 884 | crc-ccitt | 31.2 | 24.9 | 2.5 | 885 | md4 | 94.6 | 76.1 | 7.6 | 886 | md5 | 100.6 | 81.3 | 8.1 | 887 | sha1 | 102.3 | 81.1 | 8.1 | 888 | sha256 | 98.6 | 79.6 | 8.0 | 889 +-----------+-------+------+------+ 891 For 512-way ECMP with 0 more bits of entropy: 892 +-----------+------+------+------+ 893 | Hash | RMSE | MAE | MAPE | 894 +-----------+------+------+------+ 895 | add | 31.4 | 24.9 | 2.5 | 896 | mask | 32.2 | 25.8 | 2.6 | 897 | xor | 34.1 | 27.0 | 2.7 | 898 | crc-ccitt | 30.7 | 25.0 | 2.5 | 899 | md4 | 72.6 | 58.2 | 5.8 | 900 | md5 | 71.7 | 56.6 | 5.7 | 901 | sha1 | 77.6 | 62.1 | 6.2 | 902 | sha256 | 72.2 | 57.6 | 5.8 | 903 +-----------+------+------+------+ 905 For 1024-way ECMP with 0 more bits of entropy: 906 +-----------+------+------+------+ 907 | Hash | RMSE | MAE | MAPE | 908 +-----------+------+------+------+ 909 | add | 32.2 | 25.8 | 2.6 | 910 | mask | 32.6 | 26.2 | 2.6 | 911 | xor | 33.5 | 26.6 | 2.7 | 912 | crc-ccitt | 31.2 | 24.9 | 2.5 | 913 | md4 | 55.4 | 44.4 | 4.4 | 914 | md5 | 55.9 | 44.7 | 4.5 | 915 | sha1 | 57.2 | 45.4 | 4.5 | 916 | sha256 | 57.0 | 46.1 | 4.6 | 917 +-----------+------+------+------+ 919 For 2048-way ECMP with 0 more bits of entropy: 920 +-----------+------+------+------+ 921 | Hash | RMSE | MAE | MAPE | 922 +-----------+------+------+------+ 923 | add | 31.5 | 25.1 | 2.5 | 924 | mask | 31.3 | 25.0 | 2.5 | 925 | xor | 31.9 | 25.6 | 2.6 | 926 | crc-ccitt | 31.9 | 25.2 | 2.5 | 927 | md4 | 46.1 | 36.8 | 3.7 | 928 | md5 | 45.8 | 36.4 | 3.6 | 929 | sha1 | 46.9 | 38.0 | 3.8 | 930 | sha256 | 47.0 | 37.6 | 3.8 | 931 +-----------+------+------+------+ 933 For 4096-way ECMP with 0 more bits of entropy: 934 +-----------+------+------+------+ 935 | Hash | RMSE | MAE | MAPE | 936 +-----------+------+------+------+ 937 | add | 31.4 | 24.9 | 2.5 | 938 | mask | 31.5 | 24.9 | 2.5 | 939 | xor | 31.2 | 24.9 | 2.5 | 940 | crc-ccitt | 31.7 | 25.2 | 2.5 | 941 | md4 | 39.0 | 31.2 | 3.1 | 942 | md5 | 39.8 | 31.9 | 3.2 | 943 | sha1 | 39.1 | 31.1 | 3.1 | 944 | sha256 | 39.2 | 31.2 | 3.1 | 945 +-----------+------+------+------+ 947 For 2-way ECMP with 1 more bits of entropy: 948 +-----------+-------+-------+------+ 949 | Hash | RMSE | MAE | MAPE | 950 +-----------+-------+-------+------+ 951 | add | 269.0 | 269.0 | 26.9 | 952 | mask | 3.0 | 3.0 | 0.3 | 953 | xor | 94.0 | 94.0 | 9.4 | 954 | crc-ccitt | 94.0 | 94.0 | 9.4 | 955 | md4 | 761.0 | 761.0 | 76.1 | 956 | md5 | 381.0 | 381.0 | 38.1 | 957 | sha1 | 104.0 | 104.0 | 10.4 | 958 | sha256 | 771.0 | 771.0 | 77.1 | 959 +-----------+-------+-------+------+ 961 For 4-way ECMP with 1 more bits of entropy: 962 +-----------+-------+-------+------+ 963 | Hash | RMSE | MAE | MAPE | 964 +-----------+-------+-------+------+ 965 | add | 153.0 | 131.5 | 13.2 | 966 | mask | 34.5 | 27.0 | 2.7 | 967 | xor | 161.6 | 161.0 | 16.1 | 968 | crc-ccitt | 36.9 | 31.0 | 3.1 | 969 | md4 | 332.6 | 307.0 | 30.7 | 970 | md5 | 562.9 | 443.5 | 44.4 | 971 | sha1 | 219.2 | 184.0 | 18.4 | 972 | sha256 | 358.9 | 325.0 | 32.5 | 973 +-----------+-------+-------+------+ 975 For 8-way ECMP with 1 more bits of entropy: 976 +-----------+-------+-------+------+ 977 | Hash | RMSE | MAE | MAPE | 978 +-----------+-------+-------+------+ 979 | add | 74.6 | 67.2 | 6.7 | 980 | mask | 17.3 | 15.8 | 1.6 | 981 | xor | 76.0 | 75.5 | 7.5 | 982 | crc-ccitt | 167.8 | 166.5 | 16.6 | 983 | md4 | 458.2 | 408.5 | 40.9 | 984 | md5 | 340.7 | 247.8 | 24.8 | 985 | sha1 | 487.6 | 382.2 | 38.2 | 986 | sha256 | 355.5 | 282.5 | 28.2 | 987 +-----------+-------+-------+------+ 989 For 16-way ECMP with 1 more bits of entropy: 990 +-----------+-------+-------+------+ 991 | Hash | RMSE | MAE | MAPE | 992 +-----------+-------+-------+------+ 993 | add | 46.0 | 35.0 | 3.5 | 994 | mask | 30.1 | 27.2 | 2.7 | 995 | xor | 48.3 | 43.9 | 4.4 | 996 | crc-ccitt | 24.4 | 19.9 | 2.0 | 997 | md4 | 234.5 | 197.4 | 19.7 | 998 | md5 | 262.5 | 196.1 | 19.6 | 999 | sha1 | 183.4 | 150.0 | 15.0 | 1000 | sha256 | 281.1 | 251.2 | 25.1 | 1001 +-----------+-------+-------+------+ 1003 For 32-way ECMP with 1 more bits of entropy: 1004 +-----------+-------+-------+------+ 1005 | Hash | RMSE | MAE | MAPE | 1006 +-----------+-------+-------+------+ 1007 | add | 35.9 | 28.9 | 2.9 | 1008 | mask | 31.2 | 26.1 | 2.6 | 1009 | xor | 32.6 | 26.8 | 2.7 | 1010 | crc-ccitt | 40.0 | 32.5 | 3.3 | 1011 | md4 | 190.5 | 164.8 | 16.5 | 1012 | md5 | 194.2 | 152.2 | 15.2 | 1013 | sha1 | 188.4 | 155.7 | 15.6 | 1014 | sha256 | 145.6 | 121.2 | 12.1 | 1015 +-----------+-------+-------+------+ 1017 For 64-way ECMP with 1 more bits of entropy: 1018 +-----------+-------+-------+------+ 1019 | Hash | RMSE | MAE | MAPE | 1020 +-----------+-------+-------+------+ 1021 | add | 34.4 | 27.7 | 2.8 | 1022 | mask | 31.3 | 26.4 | 2.6 | 1023 | xor | 38.2 | 31.6 | 3.2 | 1024 | crc-ccitt | 32.3 | 24.3 | 2.4 | 1025 | md4 | 127.3 | 96.7 | 9.7 | 1026 | md5 | 123.8 | 101.7 | 10.2 | 1027 | sha1 | 150.6 | 122.3 | 12.2 | 1028 | sha256 | 145.4 | 108.1 | 10.8 | 1029 +-----------+-------+-------+------+ 1031 For 128-way ECMP with 1 more bits of entropy: 1032 +-----------+-------+------+------+ 1033 | Hash | RMSE | MAE | MAPE | 1034 +-----------+-------+------+------+ 1035 | add | 32.2 | 25.5 | 2.5 | 1036 | mask | 33.4 | 25.7 | 2.6 | 1037 | xor | 34.5 | 27.6 | 2.8 | 1038 | crc-ccitt | 27.7 | 20.7 | 2.1 | 1039 | md4 | 94.6 | 77.5 | 7.7 | 1040 | md5 | 105.4 | 83.5 | 8.4 | 1041 | sha1 | 96.2 | 77.4 | 7.7 | 1042 | sha256 | 100.2 | 75.9 | 7.6 | 1043 +-----------+-------+------+------+ 1045 For 256-way ECMP with 1 more bits of entropy: 1046 +-----------+------+------+------+ 1047 | Hash | RMSE | MAE | MAPE | 1048 +-----------+------+------+------+ 1049 | add | 31.0 | 24.9 | 2.5 | 1050 | mask | 30.8 | 25.1 | 2.5 | 1051 | xor | 28.7 | 22.5 | 2.3 | 1052 | crc-ccitt | 33.8 | 27.6 | 2.8 | 1053 | md4 | 72.6 | 59.9 | 6.0 | 1054 | md5 | 69.4 | 55.5 | 5.5 | 1055 | sha1 | 72.8 | 58.6 | 5.9 | 1056 | sha256 | 72.7 | 56.7 | 5.7 | 1057 +-----------+------+------+------+ 1059 For 512-way ECMP with 1 more bits of entropy: 1060 +-----------+------+------+------+ 1061 | Hash | RMSE | MAE | MAPE | 1062 +-----------+------+------+------+ 1063 | add | 31.7 | 25.4 | 2.5 | 1064 | mask | 29.7 | 23.5 | 2.3 | 1065 | xor | 31.9 | 25.4 | 2.5 | 1066 | crc-ccitt | 30.9 | 24.7 | 2.5 | 1067 | md4 | 53.8 | 43.2 | 4.3 | 1068 | md5 | 57.3 | 46.7 | 4.7 | 1069 | sha1 | 59.7 | 47.2 | 4.7 | 1070 | sha256 | 56.2 | 45.4 | 4.5 | 1071 +-----------+------+------+------+ 1073 For 1024-way ECMP with 1 more bits of entropy: 1074 +-----------+------+------+------+ 1075 | Hash | RMSE | MAE | MAPE | 1076 +-----------+------+------+------+ 1077 | add | 31.6 | 25.1 | 2.5 | 1078 | mask | 31.0 | 25.0 | 2.5 | 1079 | xor | 31.5 | 25.1 | 2.5 | 1080 | crc-ccitt | 30.2 | 24.1 | 2.4 | 1081 | md4 | 45.0 | 35.4 | 3.5 | 1082 | md5 | 47.6 | 38.0 | 3.8 | 1083 | sha1 | 45.7 | 36.7 | 3.7 | 1084 | sha256 | 46.5 | 36.8 | 3.7 | 1085 +-----------+------+------+------+ 1087 For 2048-way ECMP with 1 more bits of entropy: 1088 +-----------+------+------+------+ 1089 | Hash | RMSE | MAE | MAPE | 1090 +-----------+------+------+------+ 1091 | add | 32.7 | 26.0 | 2.6 | 1092 | mask | 31.9 | 25.5 | 2.6 | 1093 | xor | 31.8 | 25.4 | 2.5 | 1094 | crc-ccitt | 32.4 | 25.8 | 2.6 | 1095 | md4 | 39.5 | 31.8 | 3.2 | 1096 | md5 | 38.6 | 30.8 | 3.1 | 1097 | sha1 | 39.3 | 31.1 | 3.1 | 1098 | sha256 | 39.7 | 31.9 | 3.2 | 1099 +-----------+------+------+------+ 1101 For 4096-way ECMP with 1 more bits of entropy: 1102 +-----------+------+------+------+ 1103 | Hash | RMSE | MAE | MAPE | 1104 +-----------+------+------+------+ 1105 | add | 31.7 | 25.3 | 2.5 | 1106 | mask | 31.5 | 25.1 | 2.5 | 1107 | xor | 31.8 | 25.5 | 2.6 | 1108 | crc-ccitt | 32.3 | 25.9 | 2.6 | 1109 | md4 | 35.9 | 28.5 | 2.9 | 1110 | md5 | 35.7 | 28.5 | 2.9 | 1111 | sha1 | 35.2 | 28.1 | 2.8 | 1112 | sha256 | 36.3 | 28.9 | 2.9 | 1113 +-----------+------+------+------+ 1115 For 2-way ECMP with 2 more bits of entropy: 1116 +-----------+-------+-------+------+ 1117 | Hash | RMSE | MAE | MAPE | 1118 +-----------+-------+-------+------+ 1119 | add | 2.0 | 2.0 | 0.2 | 1120 | mask | 15.0 | 15.0 | 1.5 | 1121 | xor | 44.0 | 44.0 | 4.4 | 1122 | crc-ccitt | 44.0 | 44.0 | 4.4 | 1123 | md4 | 197.0 | 197.0 | 19.7 | 1124 | md5 | 123.0 | 123.0 | 12.3 | 1125 | sha1 | 238.0 | 238.0 | 23.8 | 1126 | sha256 | 20.0 | 20.0 | 2.0 | 1127 +-----------+-------+-------+------+ 1129 For 4-way ECMP with 2 more bits of entropy: 1130 +-----------+-------+-------+------+ 1131 | Hash | RMSE | MAE | MAPE | 1132 +-----------+-------+-------+------+ 1133 | add | 14.1 | 12.5 | 1.2 | 1134 | mask | 8.2 | 8.0 | 0.8 | 1135 | xor | 9.5 | 7.5 | 0.8 | 1136 | crc-ccitt | 66.0 | 57.5 | 5.8 | 1137 | md4 | 119.6 | 94.5 | 9.4 | 1138 | md5 | 553.7 | 472.0 | 47.2 | 1139 | sha1 | 163.8 | 134.5 | 13.5 | 1140 | sha256 | 366.7 | 298.5 | 29.8 | 1141 +-----------+-------+-------+------+ 1142 For 8-way ECMP with 2 more bits of entropy: 1143 +-----------+-------+-------+------+ 1144 | Hash | RMSE | MAE | MAPE | 1145 +-----------+-------+-------+------+ 1146 | add | 30.2 | 22.5 | 2.2 | 1147 | mask | 24.0 | 19.8 | 2.0 | 1148 | xor | 43.9 | 36.5 | 3.7 | 1149 | crc-ccitt | 25.8 | 22.2 | 2.2 | 1150 | md4 | 245.6 | 163.5 | 16.3 | 1151 | md5 | 233.6 | 187.2 | 18.7 | 1152 | sha1 | 337.1 | 295.8 | 29.6 | 1153 | sha256 | 247.0 | 194.2 | 19.4 | 1154 +-----------+-------+-------+------+ 1156 For 16-way ECMP with 2 more bits of entropy: 1157 +-----------+-------+-------+------+ 1158 | Hash | RMSE | MAE | MAPE | 1159 +-----------+-------+-------+------+ 1160 | add | 23.0 | 19.0 | 1.9 | 1161 | mask | 33.5 | 27.9 | 2.8 | 1162 | xor | 26.4 | 21.5 | 2.2 | 1163 | crc-ccitt | 26.1 | 22.4 | 2.2 | 1164 | md4 | 212.4 | 151.2 | 15.1 | 1165 | md5 | 227.4 | 174.5 | 17.5 | 1166 | sha1 | 180.4 | 146.9 | 14.7 | 1167 | sha256 | 193.3 | 155.8 | 15.6 | 1168 +-----------+-------+-------+------+ 1170 For 32-way ECMP with 2 more bits of entropy: 1171 +-----------+-------+-------+------+ 1172 | Hash | RMSE | MAE | MAPE | 1173 +-----------+-------+-------+------+ 1174 | add | 35.4 | 28.9 | 2.9 | 1175 | mask | 26.6 | 22.8 | 2.3 | 1176 | xor | 30.8 | 23.7 | 2.4 | 1177 | crc-ccitt | 30.4 | 23.6 | 2.4 | 1178 | md4 | 131.6 | 107.1 | 10.7 | 1179 | md5 | 136.4 | 104.9 | 10.5 | 1180 | sha1 | 121.8 | 101.3 | 10.1 | 1181 | sha256 | 137.0 | 112.8 | 11.3 | 1182 +-----------+-------+-------+------+ 1184 For 64-way ECMP with 2 more bits of entropy: 1185 +-----------+-------+------+------+ 1186 | Hash | RMSE | MAE | MAPE | 1187 +-----------+-------+------+------+ 1188 | add | 30.6 | 24.7 | 2.5 | 1189 | mask | 28.6 | 21.5 | 2.1 | 1190 | xor | 35.1 | 28.8 | 2.9 | 1191 | crc-ccitt | 37.4 | 30.3 | 3.0 | 1192 | md4 | 95.3 | 80.0 | 8.0 | 1193 | md5 | 110.5 | 89.8 | 9.0 | 1194 | sha1 | 106.2 | 85.4 | 8.5 | 1195 | sha256 | 104.7 | 84.9 | 8.5 | 1196 +-----------+-------+------+------+ 1198 For 128-way ECMP with 2 more bits of entropy: 1199 +-----------+------+------+------+ 1200 | Hash | RMSE | MAE | MAPE | 1201 +-----------+------+------+------+ 1202 | add | 30.5 | 24.5 | 2.4 | 1203 | mask | 33.6 | 27.0 | 2.7 | 1204 | xor | 31.1 | 25.5 | 2.6 | 1205 | crc-ccitt | 31.7 | 25.4 | 2.5 | 1206 | md4 | 69.0 | 55.2 | 5.5 | 1207 | md5 | 72.6 | 55.3 | 5.5 | 1208 | sha1 | 76.9 | 60.5 | 6.1 | 1209 | sha256 | 75.9 | 59.8 | 6.0 | 1210 +-----------+------+------+------+ 1212 For 256-way ECMP with 2 more bits of entropy: 1213 +-----------+------+------+------+ 1214 | Hash | RMSE | MAE | MAPE | 1215 +-----------+------+------+------+ 1216 | add | 30.3 | 23.9 | 2.4 | 1217 | mask | 32.6 | 26.2 | 2.6 | 1218 | xor | 28.9 | 23.1 | 2.3 | 1219 | crc-ccitt | 35.2 | 28.0 | 2.8 | 1220 | md4 | 59.0 | 46.5 | 4.6 | 1221 | md5 | 54.7 | 44.0 | 4.4 | 1222 | sha1 | 56.8 | 44.3 | 4.4 | 1223 | sha256 | 54.5 | 44.1 | 4.4 | 1224 +-----------+------+------+------+ 1226 For 512-way ECMP with 2 more bits of entropy: 1227 +-----------+------+------+------+ 1228 | Hash | RMSE | MAE | MAPE | 1229 +-----------+------+------+------+ 1230 | add | 32.2 | 25.4 | 2.5 | 1231 | mask | 32.4 | 25.8 | 2.6 | 1232 | xor | 31.8 | 25.1 | 2.5 | 1233 | crc-ccitt | 33.2 | 26.6 | 2.7 | 1234 | md4 | 47.0 | 36.5 | 3.7 | 1235 | md5 | 45.4 | 36.5 | 3.6 | 1236 | sha1 | 44.1 | 35.6 | 3.6 | 1237 | sha256 | 45.7 | 36.5 | 3.6 | 1238 +-----------+------+------+------+ 1240 For 1024-way ECMP with 2 more bits of entropy: 1241 +-----------+------+------+------+ 1242 | Hash | RMSE | MAE | MAPE | 1243 +-----------+------+------+------+ 1244 | add | 31.2 | 25.2 | 2.5 | 1245 | mask | 30.8 | 24.5 | 2.5 | 1246 | xor | 31.6 | 24.8 | 2.5 | 1247 | crc-ccitt | 31.9 | 25.5 | 2.5 | 1248 | md4 | 39.5 | 31.4 | 3.1 | 1249 | md5 | 39.4 | 31.8 | 3.2 | 1250 | sha1 | 39.3 | 31.4 | 3.1 | 1251 | sha256 | 38.6 | 31.0 | 3.1 | 1252 +-----------+------+------+------+ 1254 For 2048-way ECMP with 2 more bits of entropy: 1255 +-----------+------+------+------+ 1256 | Hash | RMSE | MAE | MAPE | 1257 +-----------+------+------+------+ 1258 | add | 31.5 | 25.1 | 2.5 | 1259 | mask | 32.4 | 25.6 | 2.6 | 1260 | xor | 32.7 | 26.0 | 2.6 | 1261 | crc-ccitt | 32.1 | 25.5 | 2.6 | 1262 | md4 | 36.4 | 29.1 | 2.9 | 1263 | md5 | 35.8 | 28.6 | 2.9 | 1264 | sha1 | 34.9 | 27.6 | 2.8 | 1265 | sha256 | 35.3 | 27.9 | 2.8 | 1266 +-----------+------+------+------+ 1268 For 4096-way ECMP with 2 more bits of entropy: 1269 +-----------+------+------+------+ 1270 | Hash | RMSE | MAE | MAPE | 1271 +-----------+------+------+------+ 1272 | add | 31.9 | 25.4 | 2.5 | 1273 | mask | 31.2 | 24.9 | 2.5 | 1274 | xor | 32.1 | 25.8 | 2.6 | 1275 | crc-ccitt | 31.4 | 25.0 | 2.5 | 1276 | md4 | 33.3 | 26.7 | 2.7 | 1277 | md5 | 33.8 | 27.0 | 2.7 | 1278 | sha1 | 34.0 | 27.1 | 2.7 | 1279 | sha256 | 34.3 | 27.2 | 2.7 | 1280 +-----------+------+------+------+ 1282 For 2-way ECMP with 3 more bits of entropy: 1283 +-----------+-------+-------+------+ 1284 | Hash | RMSE | MAE | MAPE | 1285 +-----------+-------+-------+------+ 1286 | add | 10.0 | 10.0 | 1.0 | 1287 | mask | 0.0 | 0.0 | 0.0 | 1288 | xor | 1.0 | 1.0 | 0.1 | 1289 | crc-ccitt | 1.0 | 1.0 | 0.1 | 1290 | md4 | 28.0 | 28.0 | 2.8 | 1291 | md5 | 372.0 | 372.0 | 37.2 | 1292 | sha1 | 36.0 | 36.0 | 3.6 | 1293 | sha256 | 99.0 | 99.0 | 9.9 | 1294 +-----------+-------+-------+------+ 1296 For 4-way ECMP with 3 more bits of entropy: 1297 +-----------+-------+-------+------+ 1298 | Hash | RMSE | MAE | MAPE | 1299 +-----------+-------+-------+------+ 1300 | add | 16.4 | 13.5 | 1.3 | 1301 | mask | 26.5 | 21.5 | 2.1 | 1302 | xor | 25.8 | 22.5 | 2.2 | 1303 | crc-ccitt | 24.4 | 21.0 | 2.1 | 1304 | md4 | 411.4 | 408.5 | 40.8 | 1305 | md5 | 191.2 | 163.0 | 16.3 | 1306 | sha1 | 88.6 | 72.0 | 7.2 | 1307 | sha256 | 177.6 | 152.5 | 15.2 | 1308 +-----------+-------+-------+------+ 1310 For 8-way ECMP with 3 more bits of entropy: 1311 +-----------+-------+-------+------+ 1312 | Hash | RMSE | MAE | MAPE | 1313 +-----------+-------+-------+------+ 1314 | add | 29.4 | 27.0 | 2.7 | 1315 | mask | 34.4 | 30.0 | 3.0 | 1316 | xor | 38.2 | 25.5 | 2.5 | 1317 | crc-ccitt | 35.2 | 32.0 | 3.2 | 1318 | md4 | 133.3 | 115.2 | 11.5 | 1319 | md5 | 257.9 | 179.2 | 17.9 | 1320 | sha1 | 139.7 | 109.5 | 10.9 | 1321 | sha256 | 120.1 | 108.8 | 10.9 | 1322 +-----------+-------+-------+------+ 1324 For 16-way ECMP with 3 more bits of entropy: 1325 +-----------+-------+-------+------+ 1326 | Hash | RMSE | MAE | MAPE | 1327 +-----------+-------+-------+------+ 1328 | add | 29.5 | 22.5 | 2.3 | 1329 | mask | 21.8 | 17.5 | 1.8 | 1330 | xor | 29.8 | 26.1 | 2.6 | 1331 | crc-ccitt | 23.4 | 18.9 | 1.9 | 1332 | md4 | 116.8 | 83.8 | 8.4 | 1333 | md5 | 156.1 | 130.5 | 13.1 | 1334 | sha1 | 144.3 | 116.9 | 11.7 | 1335 | sha256 | 138.1 | 113.6 | 11.4 | 1336 +-----------+-------+-------+------+ 1338 For 32-way ECMP with 3 more bits of entropy: 1339 +-----------+-------+------+------+ 1340 | Hash | RMSE | MAE | MAPE | 1341 +-----------+-------+------+------+ 1342 | add | 27.9 | 22.9 | 2.3 | 1343 | mask | 33.4 | 23.9 | 2.4 | 1344 | xor | 27.4 | 22.1 | 2.2 | 1345 | crc-ccitt | 27.6 | 21.4 | 2.1 | 1346 | md4 | 90.3 | 70.6 | 7.1 | 1347 | md5 | 75.9 | 60.9 | 6.1 | 1348 | sha1 | 96.7 | 76.5 | 7.7 | 1349 | sha256 | 116.8 | 96.2 | 9.6 | 1350 +-----------+-------+------+------+ 1352 For 64-way ECMP with 3 more bits of entropy: 1353 +-----------+------+------+------+ 1354 | Hash | RMSE | MAE | MAPE | 1355 +-----------+------+------+------+ 1356 | add | 32.0 | 25.9 | 2.6 | 1357 | mask | 27.7 | 22.1 | 2.2 | 1358 | xor | 32.2 | 26.0 | 2.6 | 1359 | crc-ccitt | 32.1 | 25.1 | 2.5 | 1360 | md4 | 64.5 | 51.1 | 5.1 | 1361 | md5 | 76.9 | 60.4 | 6.0 | 1362 | sha1 | 77.1 | 62.1 | 6.2 | 1363 | sha256 | 78.3 | 62.7 | 6.3 | 1364 +-----------+------+------+------+ 1366 For 128-way ECMP with 3 more bits of entropy: 1367 +-----------+------+------+------+ 1368 | Hash | RMSE | MAE | MAPE | 1369 +-----------+------+------+------+ 1370 | add | 29.4 | 24.2 | 2.4 | 1371 | mask | 32.1 | 25.5 | 2.5 | 1372 | xor | 30.7 | 24.7 | 2.5 | 1373 | crc-ccitt | 33.8 | 26.7 | 2.7 | 1374 | md4 | 52.7 | 42.8 | 4.3 | 1375 | md5 | 55.5 | 45.0 | 4.5 | 1376 | sha1 | 60.3 | 48.5 | 4.8 | 1377 | sha256 | 57.0 | 46.2 | 4.6 | 1378 +-----------+------+------+------+ 1380 For 256-way ECMP with 3 more bits of entropy: 1381 +-----------+------+------+------+ 1382 | Hash | RMSE | MAE | MAPE | 1383 +-----------+------+------+------+ 1384 | add | 31.2 | 25.5 | 2.5 | 1385 | mask | 30.3 | 24.3 | 2.4 | 1386 | xor | 32.6 | 26.4 | 2.6 | 1387 | crc-ccitt | 31.4 | 25.7 | 2.6 | 1388 | md4 | 50.2 | 39.8 | 4.0 | 1389 | md5 | 44.2 | 34.9 | 3.5 | 1390 | sha1 | 46.7 | 37.0 | 3.7 | 1391 | sha256 | 46.9 | 36.5 | 3.6 | 1392 +-----------+------+------+------+ 1394 For 512-way ECMP with 3 more bits of entropy: 1395 +-----------+------+------+------+ 1396 | Hash | RMSE | MAE | MAPE | 1397 +-----------+------+------+------+ 1398 | add | 31.8 | 25.4 | 2.5 | 1399 | mask | 31.7 | 25.5 | 2.5 | 1400 | xor | 31.5 | 25.2 | 2.5 | 1401 | crc-ccitt | 32.1 | 25.5 | 2.6 | 1402 | md4 | 39.8 | 32.2 | 3.2 | 1403 | md5 | 38.7 | 30.8 | 3.1 | 1404 | sha1 | 38.6 | 31.4 | 3.1 | 1405 | sha256 | 39.9 | 31.2 | 3.1 | 1406 +-----------+------+------+------+ 1408 For 1024-way ECMP with 3 more bits of entropy: 1409 +-----------+------+------+------+ 1410 | Hash | RMSE | MAE | MAPE | 1411 +-----------+------+------+------+ 1412 | add | 33.1 | 26.5 | 2.6 | 1413 | mask | 32.7 | 26.3 | 2.6 | 1414 | xor | 31.5 | 25.1 | 2.5 | 1415 | crc-ccitt | 31.9 | 25.5 | 2.5 | 1416 | md4 | 35.5 | 28.1 | 2.8 | 1417 | md5 | 36.9 | 29.2 | 2.9 | 1418 | sha1 | 35.7 | 28.6 | 2.9 | 1419 | sha256 | 35.8 | 28.5 | 2.8 | 1420 +-----------+------+------+------+ 1422 For 2048-way ECMP with 3 more bits of entropy: 1423 +-----------+------+------+------+ 1424 | Hash | RMSE | MAE | MAPE | 1425 +-----------+------+------+------+ 1426 | add | 31.3 | 24.9 | 2.5 | 1427 | mask | 31.5 | 24.9 | 2.5 | 1428 | xor | 32.3 | 25.7 | 2.6 | 1429 | crc-ccitt | 30.9 | 24.4 | 2.4 | 1430 | md4 | 33.7 | 26.6 | 2.7 | 1431 | md5 | 33.8 | 27.3 | 2.7 | 1432 | sha1 | 32.6 | 26.4 | 2.6 | 1433 | sha256 | 33.5 | 26.6 | 2.7 | 1434 +-----------+------+------+------+ 1436 For 4096-way ECMP with 3 more bits of entropy: 1437 +-----------+------+------+------+ 1438 | Hash | RMSE | MAE | MAPE | 1439 +-----------+------+------+------+ 1440 | add | 32.2 | 25.5 | 2.5 | 1441 | mask | 31.3 | 25.1 | 2.5 | 1442 | xor | 31.8 | 25.2 | 2.5 | 1443 | crc-ccitt | 31.7 | 25.1 | 2.5 | 1444 | md4 | 33.3 | 26.4 | 2.6 | 1445 | md5 | 32.8 | 26.2 | 2.6 | 1446 | sha1 | 32.9 | 26.3 | 2.6 | 1447 | sha256 | 32.8 | 26.2 | 2.6 | 1448 +-----------+------+------+------+ 1450 For 2-way ECMP with 4 more bits of entropy: 1451 +-----------+-------+-------+------+ 1452 | Hash | RMSE | MAE | MAPE | 1453 +-----------+-------+-------+------+ 1454 | add | 24.0 | 24.0 | 2.4 | 1455 | mask | 5.0 | 5.0 | 0.5 | 1456 | xor | 26.0 | 26.0 | 2.6 | 1457 | crc-ccitt | 26.0 | 26.0 | 2.6 | 1458 | md4 | 46.0 | 46.0 | 4.6 | 1459 | md5 | 250.0 | 250.0 | 25.0 | 1460 | sha1 | 75.0 | 75.0 | 7.5 | 1461 | sha256 | 262.0 | 262.0 | 26.2 | 1462 +-----------+-------+-------+------+ 1464 For 4-way ECMP with 4 more bits of entropy: 1465 +-----------+-------+-------+------+ 1466 | Hash | RMSE | MAE | MAPE | 1467 +-----------+-------+-------+------+ 1468 | add | 39.3 | 32.0 | 3.2 | 1469 | mask | 17.7 | 13.5 | 1.4 | 1470 | xor | 28.4 | 22.5 | 2.2 | 1471 | crc-ccitt | 29.5 | 22.0 | 2.2 | 1472 | md4 | 180.0 | 151.5 | 15.2 | 1473 | md5 | 148.5 | 130.0 | 13.0 | 1474 | sha1 | 116.0 | 100.0 | 10.0 | 1475 | sha256 | 128.4 | 113.5 | 11.3 | 1476 +-----------+-------+-------+------+ 1477 For 8-way ECMP with 4 more bits of entropy: 1478 +-----------+-------+-------+------+ 1479 | Hash | RMSE | MAE | MAPE | 1480 +-----------+-------+-------+------+ 1481 | add | 32.7 | 27.0 | 2.7 | 1482 | mask | 32.7 | 25.2 | 2.5 | 1483 | xor | 37.7 | 26.2 | 2.6 | 1484 | crc-ccitt | 30.3 | 23.2 | 2.3 | 1485 | md4 | 79.2 | 68.5 | 6.9 | 1486 | md5 | 148.2 | 133.0 | 13.3 | 1487 | sha1 | 112.1 | 101.8 | 10.2 | 1488 | sha256 | 120.7 | 108.8 | 10.9 | 1489 +-----------+-------+-------+------+ 1491 For 16-way ECMP with 4 more bits of entropy: 1492 +-----------+-------+------+------+ 1493 | Hash | RMSE | MAE | MAPE | 1494 +-----------+-------+------+------+ 1495 | add | 26.7 | 21.0 | 2.1 | 1496 | mask | 42.9 | 34.9 | 3.5 | 1497 | xor | 31.5 | 24.0 | 2.4 | 1498 | crc-ccitt | 33.9 | 29.1 | 2.9 | 1499 | md4 | 120.1 | 94.6 | 9.5 | 1500 | md5 | 106.8 | 86.4 | 8.6 | 1501 | sha1 | 90.1 | 71.1 | 7.1 | 1502 | sha256 | 65.7 | 58.9 | 5.9 | 1503 +-----------+-------+------+------+ 1505 For 32-way ECMP with 4 more bits of entropy: 1506 +-----------+------+------+------+ 1507 | Hash | RMSE | MAE | MAPE | 1508 +-----------+------+------+------+ 1509 | add | 33.2 | 25.9 | 2.6 | 1510 | mask | 30.3 | 24.7 | 2.5 | 1511 | xor | 38.8 | 32.2 | 3.2 | 1512 | crc-ccitt | 28.0 | 21.9 | 2.2 | 1513 | md4 | 63.9 | 48.1 | 4.8 | 1514 | md5 | 79.4 | 61.7 | 6.2 | 1515 | sha1 | 63.1 | 49.9 | 5.0 | 1516 | sha256 | 83.0 | 69.1 | 6.9 | 1517 +-----------+------+------+------+ 1519 For 64-way ECMP with 4 more bits of entropy: 1520 +-----------+------+------+------+ 1521 | Hash | RMSE | MAE | MAPE | 1522 +-----------+------+------+------+ 1523 | add | 28.7 | 22.3 | 2.2 | 1524 | mask | 30.2 | 25.5 | 2.6 | 1525 | xor | 33.2 | 26.8 | 2.7 | 1526 | crc-ccitt | 30.2 | 23.3 | 2.3 | 1527 | md4 | 52.5 | 42.5 | 4.2 | 1528 | md5 | 62.2 | 51.2 | 5.1 | 1529 | sha1 | 55.1 | 45.0 | 4.5 | 1530 | sha256 | 52.0 | 42.3 | 4.2 | 1531 +-----------+------+------+------+ 1533 For 128-way ECMP with 4 more bits of entropy: 1534 +-----------+------+------+------+ 1535 | Hash | RMSE | MAE | MAPE | 1536 +-----------+------+------+------+ 1537 | add | 31.6 | 25.0 | 2.5 | 1538 | mask | 29.0 | 21.8 | 2.2 | 1539 | xor | 30.1 | 23.0 | 2.3 | 1540 | crc-ccitt | 29.7 | 24.4 | 2.4 | 1541 | md4 | 46.5 | 36.9 | 3.7 | 1542 | md5 | 46.1 | 36.6 | 3.7 | 1543 | sha1 | 42.9 | 33.8 | 3.4 | 1544 | sha256 | 50.0 | 40.4 | 4.0 | 1545 +-----------+------+------+------+ 1547 For 256-way ECMP with 4 more bits of entropy: 1548 +-----------+------+------+------+ 1549 | Hash | RMSE | MAE | MAPE | 1550 +-----------+------+------+------+ 1551 | add | 31.3 | 24.9 | 2.5 | 1552 | mask | 30.5 | 23.8 | 2.4 | 1553 | xor | 31.0 | 25.4 | 2.5 | 1554 | crc-ccitt | 32.7 | 26.1 | 2.6 | 1555 | md4 | 40.8 | 32.7 | 3.3 | 1556 | md5 | 41.5 | 33.0 | 3.3 | 1557 | sha1 | 36.4 | 28.5 | 2.8 | 1558 | sha256 | 38.4 | 30.1 | 3.0 | 1559 +-----------+------+------+------+ 1561 For 512-way ECMP with 4 more bits of entropy: 1562 +-----------+------+------+------+ 1563 | Hash | RMSE | MAE | MAPE | 1564 +-----------+------+------+------+ 1565 | add | 31.4 | 25.3 | 2.5 | 1566 | mask | 32.5 | 26.0 | 2.6 | 1567 | xor | 31.5 | 24.7 | 2.5 | 1568 | crc-ccitt | 31.6 | 25.1 | 2.5 | 1569 | md4 | 34.3 | 27.3 | 2.7 | 1570 | md5 | 36.1 | 29.2 | 2.9 | 1571 | sha1 | 35.9 | 28.6 | 2.9 | 1572 | sha256 | 37.1 | 29.5 | 2.9 | 1573 +-----------+------+------+------+ 1575 For 1024-way ECMP with 4 more bits of entropy: 1576 +-----------+------+------+------+ 1577 | Hash | RMSE | MAE | MAPE | 1578 +-----------+------+------+------+ 1579 | add | 31.3 | 24.8 | 2.5 | 1580 | mask | 31.7 | 25.2 | 2.5 | 1581 | xor | 31.4 | 25.1 | 2.5 | 1582 | crc-ccitt | 31.5 | 25.3 | 2.5 | 1583 | md4 | 33.1 | 26.3 | 2.6 | 1584 | md5 | 34.1 | 27.0 | 2.7 | 1585 | sha1 | 33.7 | 27.1 | 2.7 | 1586 | sha256 | 32.8 | 26.1 | 2.6 | 1587 +-----------+------+------+------+ 1589 For 2048-way ECMP with 4 more bits of entropy: 1590 +-----------+------+------+------+ 1591 | Hash | RMSE | MAE | MAPE | 1592 +-----------+------+------+------+ 1593 | add | 31.9 | 25.4 | 2.5 | 1594 | mask | 31.8 | 25.5 | 2.5 | 1595 | xor | 32.2 | 25.7 | 2.6 | 1596 | crc-ccitt | 31.4 | 24.8 | 2.5 | 1597 | md4 | 32.7 | 26.1 | 2.6 | 1598 | md5 | 32.9 | 26.1 | 2.6 | 1599 | sha1 | 33.0 | 26.3 | 2.6 | 1600 | sha256 | 31.9 | 25.7 | 2.6 | 1601 +-----------+------+------+------+ 1603 For 4096-way ECMP with 4 more bits of entropy: 1604 +-----------+------+------+------+ 1605 | Hash | RMSE | MAE | MAPE | 1606 +-----------+------+------+------+ 1607 | add | 31.7 | 25.4 | 2.5 | 1608 | mask | 32.5 | 25.8 | 2.6 | 1609 | xor | 31.7 | 25.2 | 2.5 | 1610 | crc-ccitt | 32.0 | 25.7 | 2.6 | 1611 | md4 | 32.6 | 26.0 | 2.6 | 1612 | md5 | 31.6 | 25.1 | 2.5 | 1613 | sha1 | 31.7 | 25.1 | 2.5 | 1614 | sha256 | 32.3 | 25.9 | 2.6 | 1615 +-----------+------+------+------+ 1617 For 2-way ECMP with 5 more bits of entropy: 1618 +-----------+-------+-------+------+ 1619 | Hash | RMSE | MAE | MAPE | 1620 +-----------+-------+-------+------+ 1621 | add | 29.0 | 29.0 | 2.9 | 1622 | mask | 11.0 | 11.0 | 1.1 | 1623 | xor | 7.0 | 7.0 | 0.7 | 1624 | crc-ccitt | 7.0 | 7.0 | 0.7 | 1625 | md4 | 358.0 | 358.0 | 35.8 | 1626 | md5 | 174.0 | 174.0 | 17.4 | 1627 | sha1 | 108.0 | 108.0 | 10.8 | 1628 | sha256 | 10.0 | 10.0 | 1.0 | 1629 +-----------+-------+-------+------+ 1631 For 4-way ECMP with 5 more bits of entropy: 1632 +-----------+-------+-------+------+ 1633 | Hash | RMSE | MAE | MAPE | 1634 +-----------+-------+-------+------+ 1635 | add | 41.3 | 35.0 | 3.5 | 1636 | mask | 42.7 | 33.5 | 3.4 | 1637 | xor | 17.5 | 15.5 | 1.6 | 1638 | crc-ccitt | 14.2 | 12.5 | 1.2 | 1639 | md4 | 135.3 | 125.0 | 12.5 | 1640 | md5 | 128.0 | 109.0 | 10.9 | 1641 | sha1 | 114.3 | 106.5 | 10.7 | 1642 | sha256 | 175.5 | 141.5 | 14.2 | 1643 +-----------+-------+-------+------+ 1645 For 8-way ECMP with 5 more bits of entropy: 1646 +-----------+-------+-------+------+ 1647 | Hash | RMSE | MAE | MAPE | 1648 +-----------+-------+-------+------+ 1649 | add | 23.5 | 20.0 | 2.0 | 1650 | mask | 29.0 | 20.2 | 2.0 | 1651 | xor | 27.1 | 24.5 | 2.4 | 1652 | crc-ccitt | 27.6 | 20.2 | 2.0 | 1653 | md4 | 105.4 | 91.5 | 9.2 | 1654 | md5 | 53.3 | 43.5 | 4.3 | 1655 | sha1 | 74.8 | 63.8 | 6.4 | 1656 | sha256 | 124.7 | 102.2 | 10.2 | 1657 +-----------+-------+-------+------+ 1659 For 16-way ECMP with 5 more bits of entropy: 1660 +-----------+------+------+------+ 1661 | Hash | RMSE | MAE | MAPE | 1662 +-----------+------+------+------+ 1663 | add | 39.1 | 33.2 | 3.3 | 1664 | mask | 38.5 | 29.5 | 2.9 | 1665 | xor | 41.3 | 33.6 | 3.4 | 1666 | crc-ccitt | 27.0 | 21.2 | 2.1 | 1667 | md4 | 71.6 | 59.1 | 5.9 | 1668 | md5 | 86.5 | 73.8 | 7.4 | 1669 | sha1 | 79.3 | 63.4 | 6.3 | 1670 | sha256 | 59.3 | 50.9 | 5.1 | 1671 +-----------+------+------+------+ 1673 For 32-way ECMP with 5 more bits of entropy: 1674 +-----------+------+------+------+ 1675 | Hash | RMSE | MAE | MAPE | 1676 +-----------+------+------+------+ 1677 | add | 31.2 | 25.1 | 2.5 | 1678 | mask | 33.7 | 28.6 | 2.9 | 1679 | xor | 32.6 | 27.6 | 2.8 | 1680 | crc-ccitt | 28.7 | 22.0 | 2.2 | 1681 | md4 | 51.4 | 42.0 | 4.2 | 1682 | md5 | 54.2 | 44.8 | 4.5 | 1683 | sha1 | 68.5 | 49.2 | 4.9 | 1684 | sha256 | 56.7 | 47.8 | 4.8 | 1685 +-----------+------+------+------+ 1687 For 64-way ECMP with 5 more bits of entropy: 1688 +-----------+------+------+------+ 1689 | Hash | RMSE | MAE | MAPE | 1690 +-----------+------+------+------+ 1691 | add | 33.0 | 26.6 | 2.7 | 1692 | mask | 29.4 | 22.9 | 2.3 | 1693 | xor | 33.9 | 27.1 | 2.7 | 1694 | crc-ccitt | 29.6 | 22.0 | 2.2 | 1695 | md4 | 46.6 | 35.8 | 3.6 | 1696 | md5 | 48.5 | 39.8 | 4.0 | 1697 | sha1 | 43.4 | 33.8 | 3.4 | 1698 | sha256 | 44.4 | 36.2 | 3.6 | 1699 +-----------+------+------+------+ 1701 For 128-way ECMP with 5 more bits of entropy: 1702 +-----------+------+------+------+ 1703 | Hash | RMSE | MAE | MAPE | 1704 +-----------+------+------+------+ 1705 | add | 32.3 | 25.7 | 2.6 | 1706 | mask | 28.8 | 22.9 | 2.3 | 1707 | xor | 30.0 | 24.5 | 2.5 | 1708 | crc-ccitt | 31.3 | 23.9 | 2.4 | 1709 | md4 | 41.7 | 34.7 | 3.5 | 1710 | md5 | 38.5 | 31.1 | 3.1 | 1711 | sha1 | 36.4 | 28.8 | 2.9 | 1712 | sha256 | 35.0 | 28.0 | 2.8 | 1713 +-----------+------+------+------+ 1715 For 256-way ECMP with 5 more bits of entropy: 1716 +-----------+------+------+------+ 1717 | Hash | RMSE | MAE | MAPE | 1718 +-----------+------+------+------+ 1719 | add | 30.8 | 24.4 | 2.4 | 1720 | mask | 31.0 | 24.6 | 2.5 | 1721 | xor | 31.3 | 24.7 | 2.5 | 1722 | crc-ccitt | 31.1 | 24.3 | 2.4 | 1723 | md4 | 37.0 | 29.6 | 3.0 | 1724 | md5 | 31.5 | 26.0 | 2.6 | 1725 | sha1 | 35.5 | 27.7 | 2.8 | 1726 | sha256 | 37.0 | 29.6 | 3.0 | 1727 +-----------+------+------+------+ 1729 For 512-way ECMP with 5 more bits of entropy: 1730 +-----------+------+------+------+ 1731 | Hash | RMSE | MAE | MAPE | 1732 +-----------+------+------+------+ 1733 | add | 32.0 | 25.2 | 2.5 | 1734 | mask | 30.9 | 24.7 | 2.5 | 1735 | xor | 30.3 | 24.3 | 2.4 | 1736 | crc-ccitt | 31.6 | 25.0 | 2.5 | 1737 | md4 | 36.0 | 28.6 | 2.9 | 1738 | md5 | 33.9 | 26.5 | 2.6 | 1739 | sha1 | 32.7 | 25.9 | 2.6 | 1740 | sha256 | 33.7 | 26.5 | 2.6 | 1741 +-----------+------+------+------+ 1743 For 1024-way ECMP with 5 more bits of entropy: 1744 +-----------+------+------+------+ 1745 | Hash | RMSE | MAE | MAPE | 1746 +-----------+------+------+------+ 1747 | add | 32.5 | 25.7 | 2.6 | 1748 | mask | 32.1 | 25.7 | 2.6 | 1749 | xor | 32.4 | 26.1 | 2.6 | 1750 | crc-ccitt | 31.2 | 25.5 | 2.5 | 1751 | md4 | 33.4 | 26.8 | 2.7 | 1752 | md5 | 32.2 | 25.9 | 2.6 | 1753 | sha1 | 33.4 | 26.3 | 2.6 | 1754 | sha256 | 33.3 | 26.5 | 2.7 | 1755 +-----------+------+------+------+ 1757 For 2048-way ECMP with 5 more bits of entropy: 1758 +-----------+------+------+------+ 1759 | Hash | RMSE | MAE | MAPE | 1760 +-----------+------+------+------+ 1761 | add | 30.9 | 24.8 | 2.5 | 1762 | mask | 32.1 | 25.9 | 2.6 | 1763 | xor | 31.9 | 25.5 | 2.5 | 1764 | crc-ccitt | 31.3 | 24.9 | 2.5 | 1765 | md4 | 32.3 | 25.8 | 2.6 | 1766 | md5 | 32.4 | 25.9 | 2.6 | 1767 | sha1 | 32.6 | 26.1 | 2.6 | 1768 | sha256 | 32.6 | 25.9 | 2.6 | 1769 +-----------+------+------+------+ 1771 For 4096-way ECMP with 5 more bits of entropy: 1772 +-----------+------+------+------+ 1773 | Hash | RMSE | MAE | MAPE | 1774 +-----------+------+------+------+ 1775 | add | 31.8 | 25.2 | 2.5 | 1776 | mask | 31.5 | 24.9 | 2.5 | 1777 | xor | 31.6 | 25.1 | 2.5 | 1778 | crc-ccitt | 31.6 | 25.3 | 2.5 | 1779 | md4 | 31.9 | 25.5 | 2.6 | 1780 | md5 | 31.8 | 25.2 | 2.5 | 1781 | sha1 | 32.2 | 25.7 | 2.6 | 1782 | sha256 | 32.2 | 26.0 | 2.6 | 1783 +-----------+------+------+------+ 1785 Error per added bit 1786 +------------+-------+-------+-------+ 1787 | Added bits | MRMSE | MMAE | MMAPE | 1788 +------------+-------+-------+-------+ 1789 | 0 | 171.0 | 150.6 | 15.1 | 1790 | 1 | 115.8 | 100.2 | 10.0 | 1791 | 2 | 74.9 | 61.6 | 6.2 | 1792 | 3 | 58.5 | 49.0 | 4.9 | 1793 | 4 | 51.1 | 43.2 | 4.3 | 1794 | 5 | 47.1 | 39.8 | 4.0 | 1795 +------------+-------+-------+-------+ 1797 Error per algorithm 1798 +-----------+-------+-------+-------+ 1799 | Algorithm | MRMSE | MMAE | MMAPE | 1800 +-----------+-------+-------+-------+ 1801 | add | 52.7 | 45.8 | 4.6 | 1802 | mask | 34.1 | 28.6 | 2.9 | 1803 | xor | 54.0 | 48.0 | 4.8 | 1804 | crc-ccitt | 48.7 | 43.2 | 4.3 | 1805 | md4 | 137.7 | 119.8 | 12.0 | 1806 | md5 | 131.3 | 110.7 | 11.1 | 1807 | sha1 | 110.5 | 93.0 | 9.3 | 1808 | sha256 | 122.2 | 103.3 | 10.3 | 1809 +-----------+-------+-------+-------+ 1811 For 3597-way ECMP, 16 bits of entropy: 1812 +-----------+-------+-------+------+ 1813 | Hash | RMSE | MAE | MAPE | 1814 +-----------+-------+-------+------+ 1815 | mask | 31.7 | 25.2 | 2.5 | 1816 | crc-ccitt | 264.8 | 210.5 | 21.0 | 1817 | md4 | 356.1 | 283.5 | 28.3 | 1818 | md5 | 357.9 | 286.4 | 28.6 | 1819 | sha1 | 358.9 | 284.9 | 28.5 | 1820 | sha256 | 357.1 | 283.1 | 28.3 | 1821 +-----------+-------+-------+------+ 1823 For 911-way ECMP, 16 bits of entropy: 1824 +-----------+-------+-------+------+ 1825 | Hash | RMSE | MAE | MAPE | 1826 +-----------+-------+-------+------+ 1827 | mask | 31.5 | 25.4 | 2.5 | 1828 | crc-ccitt | 163.2 | 133.3 | 13.3 | 1829 | md4 | 181.9 | 144.9 | 14.5 | 1830 | md5 | 190.0 | 150.5 | 15.0 | 1831 | sha1 | 181.6 | 147.2 | 14.7 | 1832 | sha256 | 180.3 | 143.8 | 14.4 | 1833 +-----------+-------+-------+------+ 1835 For 3023-way ECMP, 16 bits of entropy: 1836 +-----------+-------+-------+------+ 1837 | Hash | RMSE | MAE | MAPE | 1838 +-----------+-------+-------+------+ 1839 | mask | 31.8 | 25.6 | 2.6 | 1840 | crc-ccitt | 238.2 | 191.1 | 19.1 | 1841 | md4 | 320.7 | 254.9 | 25.5 | 1842 | md5 | 319.7 | 253.8 | 25.4 | 1843 | sha1 | 329.1 | 262.8 | 26.3 | 1844 | sha256 | 328.0 | 261.6 | 26.2 | 1845 +-----------+-------+-------+------+ 1847 For 2288-way ECMP, 16 bits of entropy: 1848 +-----------+-------+-------+------+ 1849 | Hash | RMSE | MAE | MAPE | 1850 +-----------+-------+-------+------+ 1851 | mask | 31.5 | 25.2 | 2.5 | 1852 | crc-ccitt | 190.8 | 156.0 | 15.6 | 1853 | md4 | 282.4 | 225.8 | 22.6 | 1854 | md5 | 279.8 | 220.4 | 22.0 | 1855 | sha1 | 280.8 | 225.2 | 22.5 | 1856 | sha256 | 281.9 | 223.5 | 22.3 | 1857 +-----------+-------+-------+------+ 1859 For 2761-way ECMP, 16 bits of entropy: 1860 +-----------+-------+-------+------+ 1861 | Hash | RMSE | MAE | MAPE | 1862 +-----------+-------+-------+------+ 1863 | mask | 32.1 | 25.4 | 2.5 | 1864 | crc-ccitt | 225.4 | 179.9 | 18.0 | 1865 | md4 | 318.4 | 253.0 | 25.3 | 1866 | md5 | 309.4 | 247.8 | 24.8 | 1867 | sha1 | 304.6 | 244.0 | 24.4 | 1868 | sha256 | 309.2 | 247.2 | 24.7 | 1869 +-----------+-------+-------+------+ 1871 For 1845-way ECMP, 16 bits of entropy: 1872 +-----------+-------+-------+------+ 1873 | Hash | RMSE | MAE | MAPE | 1874 +-----------+-------+-------+------+ 1875 | mask | 31.4 | 25.0 | 2.5 | 1876 | crc-ccitt | 161.2 | 129.6 | 13.0 | 1877 | md4 | 260.3 | 207.3 | 20.7 | 1878 | md5 | 257.3 | 203.1 | 20.3 | 1879 | sha1 | 259.9 | 206.1 | 20.6 | 1880 | sha256 | 245.7 | 196.3 | 19.6 | 1881 +-----------+-------+-------+------+ 1883 For 3508-way ECMP, 16 bits of entropy: 1884 +-----------+-------+-------+------+ 1885 | Hash | RMSE | MAE | MAPE | 1886 +-----------+-------+-------+------+ 1887 | mask | 31.4 | 25.2 | 2.5 | 1888 | crc-ccitt | 209.0 | 167.7 | 16.8 | 1889 | md4 | 352.0 | 280.6 | 28.1 | 1890 | md5 | 346.1 | 277.6 | 27.8 | 1891 | sha1 | 357.4 | 284.2 | 28.4 | 1892 | sha256 | 344.9 | 274.3 | 27.4 | 1893 +-----------+-------+-------+------+ 1895 For 1963-way ECMP, 16 bits of entropy: 1896 +-----------+-------+-------+------+ 1897 | Hash | RMSE | MAE | MAPE | 1898 +-----------+-------+-------+------+ 1899 | mask | 31.4 | 25.3 | 2.5 | 1900 | crc-ccitt | 163.5 | 131.9 | 13.2 | 1901 | md4 | 257.7 | 205.5 | 20.6 | 1902 | md5 | 257.2 | 204.8 | 20.5 | 1903 | sha1 | 264.4 | 213.0 | 21.3 | 1904 | sha256 | 266.7 | 214.1 | 21.4 | 1905 +-----------+-------+-------+------+ 1907 For 1168-way ECMP, 16 bits of entropy: 1908 +-----------+-------+-------+------+ 1909 | Hash | RMSE | MAE | MAPE | 1910 +-----------+-------+-------+------+ 1911 | mask | 32.2 | 25.4 | 2.5 | 1912 | crc-ccitt | 107.5 | 86.1 | 8.6 | 1913 | md4 | 198.6 | 158.4 | 15.8 | 1914 | md5 | 203.3 | 161.8 | 16.2 | 1915 | sha1 | 201.1 | 162.3 | 16.2 | 1916 | sha256 | 201.4 | 159.0 | 15.9 | 1917 +-----------+-------+-------+------+ 1919 For 2274-way ECMP, 16 bits of entropy: 1920 +-----------+-------+-------+------+ 1921 | Hash | RMSE | MAE | MAPE | 1922 +-----------+-------+-------+------+ 1923 | mask | 31.7 | 25.0 | 2.5 | 1924 | crc-ccitt | 208.9 | 166.0 | 16.6 | 1925 | md4 | 277.2 | 221.8 | 22.2 | 1926 | md5 | 279.8 | 224.9 | 22.5 | 1927 | sha1 | 285.5 | 225.7 | 22.6 | 1928 | sha256 | 288.4 | 229.6 | 23.0 | 1929 +-----------+-------+-------+------+ 1931 For n-way ECMP, with 16 bits of entropy, across hash functions 1932 +--------+-------+-------+-------+ 1933 | n-ways | MRMSE | MMAE | MMAPE | 1934 +--------+-------+-------+-------+ 1935 | 3597 | 287.8 | 228.9 | 22.9 | 1936 | 911 | 154.8 | 124.2 | 12.4 | 1937 | 3023 | 261.2 | 208.3 | 20.8 | 1938 | 2288 | 224.5 | 179.3 | 17.9 | 1939 | 2761 | 249.9 | 199.5 | 19.9 | 1940 | 1845 | 202.6 | 161.2 | 16.1 | 1941 | 3508 | 273.5 | 218.3 | 21.8 | 1942 | 1963 | 206.8 | 165.8 | 16.6 | 1943 | 1168 | 157.3 | 125.5 | 12.5 | 1944 | 2274 | 228.6 | 182.2 | 18.2 | 1945 +--------+-------+-------+-------+ 1947 Author's Address 1949 Tony Li 1950 Juniper Networks 1951 Email: tony.li@tony.li