Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Design for Optimizability: Traffic Management of a Future Internet Kapitel lesen Erstes Kapitel lesen

2010 | OriginalPaper | Buchkapitel

9. Hash-Based Techniques for High-Speed Packet Processing

verfasst von : Adam Kirsch, Michael Mitzenmacher, George Varghese

Erschienen in: Algorithms for Next Generation Networks

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Hashing is an extremely useful technique for a variety of high-speed packet-processing applications in routers. In this chapter, we survey much of the recent work in this area, paying particular attention to the interaction between theoretical and applied research. We assume very little background in either the theory or applications of hashing, reviewing the fundamentals as necessary.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Overlay Networks: Applications, Coexistence with IP Layer, and Transient Dynamics
Nächstes Kapitel Fast Packet Pattern-Matching Algorithms
Literatur
1.
2.
B. Bloom. Space/Time Tradeoffs in Hash Coding with Allowable Errors. Communications of the ACM, 13(7):422–426, 1970.MATHCrossRef
3.
F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines. In Proceedings of ACM SIGCOMM, pp. 315–326, 2006.
4.
F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. Bloom Filters via d-left Hashing and Dynamic Bit Reassignment. In Proceedings of the Allerton Conference on Communication, Control and Computing, 2006.
5.
F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese. An Improved Construction for Counting Bloom Filters. In Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pp. 684–695, 2006.
6.
7.
A. Broder and A. Karlin. Multilevel Adaptive Hashing. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 43–53, 1990.
8.
9.
A. Broder and M. Mitzenmacher. Using Multiple Hash Functions to Improve IP Lookups. Proceedings of the 20th IEEE International Conference on Computer Communications (INFOCOM), pp. 1454–1463, 2001.
10.
J. L. Carter and M. N. Wegman. Universal Classes of Hash Functions. Journal of Computer and System Sciences, 18(2):143–154, 1979.MathSciNetMATHCrossRef
11.
B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal. The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 30–39, 2004.
12.
S. Cohen and Y. Matias. Spectral Bloom Filters. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 241–252, 2003.
13.
G. Cormode and S. Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. Journal of Algorithms, 55(1):58–75, 2005.MathSciNetMATHCrossRef
14.
E. Demaine, F. Meyer auf der Heide, R. Pagh, and M. Patrascu. De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space). In 7th Latin American Theoertical Informatics Symposium, pp. 349–361, 2006.
15.
16.
S. Dharmapurikar, P. Krishnamurthy, T. S. Sproull, and J. W. Lockwood. Deep Packet Inspection Using Parallel Bloom Filters. IEEE Micro, 24(1):52–61, 2004.CrossRef
17.
S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor. Longest Prefix Matching Using Bloom Filters. IEEE/ACM Transactions on Networks, 14(2):397–409, 2006.CrossRef
18.
S. Dharmapurikar and J. W. Lockwood. Fast and Scalable Pattern Matching for Network Intrusion Detection Systems. IEEE Journal on Selected Areas in Communications, 24(10):1781–1792, 2006.CrossRef
19.
S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood. Fast Packet Classification Using Bloom Filters. In Proceedings of the 2006 ACM/IEEE Symposium on Architecture For Networking and Communications Systems (ANCS), pp. 61–70, 2006.
20.
M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A Reliable Randomized Algorithm for the Closest-Pair Problem. Journal of Algorithms, 25(1):19–51, 1997.MathSciNetMATHCrossRef
21.
M. Dietzfelbinger and C. Weidling. Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. Theoretical Computer Science, 380(1–2):47–68, 2007.MathSciNetMATHCrossRef
22.
B. Donnet, B. Baynat, and T. Friedman. Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives. arxiv, cs.NI/0607038, 2006.
23.
C. Estan, K. Keys, D. Moore, and G. Varghese. Building a Better NetFlow. In Proceedings of ACM SIGCOMM, pp. 245–256, 2004.
24.
C. Estan and G. Varghese. New Directions in Traffic Measurement and Accounting: Focusing on the Elephants, Ignoring the Mice. ACM Transactions on Computer Systems, 21(3):270–313, 2003.CrossRef
25.
C. Estan, G. Varghese, and M. E. Fisk. Bitmap Algorithms for Counting Active Flows on High-Speed Links. IEEE/ACM Transactions on Networks, 14(5):925–937, 2006.CrossRef
26.
L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. IEEE/ACM Transactions on Networking, 8(3):281–293, 2000.CrossRef
27.
W. Fang and L. Peterson. Inter-AS Traffic Patterns and Their Implications. In Proceedings of the Global Telecommunications Conference, 1999 (GLOBECOM), 1999.
28.
29.
P. Flajolet and G. N. Martin. Probabilistic Counting Algorithms for Data Base Applications. Journal of Computer and System Sciences, 31(2):182–209, 1985.MathSciNetMATHCrossRef
30.
D. Fotakis, R. Pagh, P. Sanders, and P. Spirakis. Space Efficient Hash Tables With Worst Case Constant Access Time. Theory of Computing Systems, 38(2):229–248, 2005.MathSciNetMATHCrossRef
31.
P. Gibbons and Y. Matias. New sampling-based summary statistics for improving approximate query answers. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 331–342, 1998.
32.
G. Gonnet. Expected Length of the Longest Probe Sequence in Hash Code Searching. Journal of the Association for Computing Machinery, 28(2):289–304, 1981.MathSciNetMATHCrossRef
33.
J. Hasan, S. Cadambi, V. Jakkula, and S. Chakradhar. Chisel: A Storage-efficient, Collision-free Hash-based Network Processing Architecture. In Proceedings of the 33rd International Symposium on Computer Architecture (ISCA), pp. 203–215, 2006
34.
A. Kirsch and M. Mitzenmacher. On the Performance of Multiple Choice Hash Tables with Moves on Deletes and Inserts. In Proceedings of the Forty-Sixth Annual Allerton Conference, 2008.
35.
A. Kirsch and M. Mitzenmacher. The Power of One Move: Hashing Schemes for Hardware. In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), 2008.
36.
A. Kirsch and M. Mitzenmacher. Simple Summaries for Hashing with Choices. IEEE/ACM Transactions on Networking, 16(1):218–231, 2008.CrossRef
37.
A. Kirsch and M. Mitzenmacher. Using a Queue to De-amortize Cuckoo Hashing in Hardware. In Proceedings of the Forty-Fifth Annual Allerton Conference on Communication, Control, and Computing, 2007.
38.
A. Kirsch, M. Mitzenmacher, and U. Wieder. More Robust Hashing: Cuckoo Hashing with a Stash. To appear in Proceedings of the 16th Annual European Symposium on Algorithms, 2008.
39.
D. Knuth. Sorting and Searching, vol. 3 of The Art of Computer Programming (2nd edition), Addison-Wesley Publishing Company, 1998.
40.
R. R. Kompella, S. Singh, and G. Varghese. On Scalable Attack Detection in the Network. In Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement, pp. 187–200, 2004.
41.
A. Kumar, M. Sung, J. Xu, and J. Wang. Data Streaming Algorithms for Efficient and Accurate Estimation of Flow Size Distribution. In Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance), pp. 177–188, 2004.
42.
S. Kumar and P. Crowley. Segmented Hash: An Efficient Hash Table Implementation for High Performance Networking Subsystems. In Proceedings of the 2005 ACM Symposium on Architecture for Networking and Communications Systems (ANCS), pp. 91–103, 2005.
43.
S. Kumar, J. Turner, and P. Crowley. Peacock Hash: Fast and Updatable Hashing for High Performance Packet Processing Algorithms. In Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM), 2008.
44.
S. Kumar, J. Turner, P. Crowley, and M. Mitzenmacher. HEXA: Compact Data Structures for Faster Packet Processing. In Proceedings of the Fifteenth IEEE International Conference on Network Protocols (ICNP), pp. 246–255, 2007.
45.
Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, and A. Kabbani. Counter Braids: A Novel Counter Architecture for Per-Flow Measurement. Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), 2008.
46.
Y. Lu, B. Prabhakar, and F. Bonomi. Perfect Hashing for Networking Algorithms. In Proceedings of the 2006 IEEE International Symposium on Information Theory (ISIT), pp. 2774–2778, 2006.
47.
Y. Lu, M. Wang, B. Prabhakar, and F. Bonomi. ElephantTrap: A Low Cost Device for Identifying Large Flows. In Proceedings of the 15th Annual IEEE Symposium on High-Performance Interconnects (HOTI), pp. 99–108, 2007.
48.
S. Lumetta and M. Mitzenmacher. Using the Power of Two Choices to Improve Bloom Filters. To appear in Internet Mathematics.
49.
U. Manber and S. Wu. An Algorithm for Approximate Membership checking with Application to Password Security. Information Processing Letters, 50(4), pp. 191–197, 1994.MATHCrossRef
50.
M. Mitzenmacher. Compressed Bloom Filters. IEEE/ACM Transactions on Networking, 10(5):613–620, 2002.CrossRef
51.
M. Mitzenmacher, A. Richa, and R. Sitaraman. The Power of Two Choices: A Survey of Techniques and Results, edited by P. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim. Kluwer Academic Publishers, Norwell, MA, 2001, pp. 255–312.
52.
M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
53.
M. Mitzenmacher and S. Vadhan. Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 746–755, 2008.
54.
A. Östlin and R. Pagh. Uniform Hashing in Constant Time and Linear Space. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pp. 622–628, 2003.
55.
A. Pagh, R. Pagh, and S. S. Rao. An Optimal Bloom Filter Replacement. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 823-829, 2005.
56.
57.
R. Panigrahy. Efficient Hashing with Lookups in Two Memory Accesses. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 830–839, 2005.
58.
F. Putze, P. Sanders, and J. Singler. Cache-, Hash-and Space-Efficient Bloom Filters. In Proceedings of the Workshop on Experimental Algorithms, pp. 108–121, 2007. Available as Springer Lecture Notes in Computer Science, volume 4525.
59.
M. V. Ramakrishna. Hashing Practice: Analysis of Hashing and Universal Hashing. In Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 191–199, 1988.
60.
M. V. Ramakrishna. Practical Performance of Bloom Filters and Parallel Free-Rext Searching. Communications of the ACM, 32(10):1237–1239, 1989.CrossRef
61.
M.V. Ramakrishna, E. Fu, and E. Bahcekapili. Efficient Hardware Hashing Functions for High Performance Computers. IEEE Transactions on Computers, 46(12):1378–1381, 1997.CrossRef
62.
A. Siegel. On Universal Classes of Extremely Random Constant-Time Hash Functions. Siam Journal on Computing, 33(3):505–543, 2004.MathSciNetMATHCrossRef
63.
S. Singh, C. Estan, G. Varghese, and S. Savage. Automated Worm Fingerprinting. In Proceedings of the 6th ACM/USENIX Symposium on Operating System Design and Implementation (OSDI), 2004.
64.
A. Snoeren, C. Partridge, L. Sanchez, C. Jones, F. Tchakountio, B. Schwartz, S. Kent, and W. Strayer. Single-Packet IP Traceback. IEEE/ACM Transactions on Networks, 10(6):721–734, 2002.CrossRef
65.
H. Song, S. Dharmapurikar, J. Turner, and J. Lockwood. Fast Hash Table Lookup Using Extended Bloom Filter: An Aid to Network Processing. In Proceedings of ACM SIGCOMM, pp. 181–192, 2005.
66.
67.
M. Thorup. Even Strongly Universal Hashing is Pretty Fast. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 496–497, 2000.
68.
GIGAswitch System: A High-Performance Packet-Switching Platform. R. J. Souza, P. G. Krishnakumar, C. M. Özveren, R. J. Simcoe, B. A. Spinney, R. E. Thomas, and R. J. Walsh. Digital Technical Journal, 6(1):9–22, 1994.
69.
V. Srinivasan and G. Varghese. Fast Address Lookups Using Controlled Prefix Expansion. ACM Transactions on Computer Systems, 17(1):1–40, 1999.CrossRef
70.
G. Varghese. Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices. Morgan Kaufmann Publishers, 2004.
71.
72.
S. Venkataraman, D. Song, P. B. Gibbons, and A. Blum. New Streaming Algorithms for Fast Detection of Superspreaders. In Proceedings of the 12th ISOC Symposium on Network and Distributed Systems Security (SNDSS), 149–166, 2005.
73.
74.
M. Waldvogel, G. Varghese, J. Turner, and B. Plattner. Scalable High Speed IP Routing Lookups. ACM SIGCOMM Computer Communication Review, 27(4):25–36, 1997.CrossRef
75.
M. N. Wegman and J. L. Carter. New Hash Functions and Their Use in Authentication and Set Equality. Journal of Computer and System Sciences, 22(3):265–279, 1981.MathSciNetMATHCrossRef
76.
P. Woelfel. Asymmetric Balanced Allocation with Simple Hash Functions. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 424–433, 2006.
Metadaten
Titel
Hash-Based Techniques for High-Speed Packet Processing
verfasst von
Adam Kirsch
Michael Mitzenmacher
George Varghese
Copyright-Jahr
2010
Verlag
Springer London
Buch
Algorithms for Next Generation Networks

Print ISBN: 978-1-84882-764-6

Electronic ISBN: 978-1-84882-765-3

Copyright-Jahr: 2010

DOI
https://doi.org/10.1007/978-1-84882-765-3_9

Premium Partner

    Bildnachweise