More Web Proxy on the site http://driver.im/

Article

Free access

Fast and scalable layer four switching

Authors:

M. WaldvogelAuthors Info & Claims

SIGCOMM '98: Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication

Pages 191 - 202

https://doi.org/10.1145/285237.285282

Published: 01 October 1998 Publication History

Abstract

In Layer Four switching, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as source address, TCP and UDP port numbers. Layer Four switching unifies firewall processing, RSVP style resource reservation filters, QoS Routing, and normal unicast and multicast forwarding into a single framework. In this framework, the forwarding database of a router consists of a potentially large number of filters on key header fields. A given packet header can match multiple filters, so each filter is given a cost, and the packet is forwarded using the least cost matching filter.In this paper, we describe two new algorithms for solving the least cost matching filter problem at high speeds. Our first algorithm is based on a grid-of-tries construction and works optimally for processing filters consisting of two prefix fields (such as destination-source filters) using linear space. Our second algorithm, cross-producting, provides fast lookup times for arbitrary filters but potentially requires large storage. We describe a combination scheme that combines the advantages of both schemes. The combination scheme can be optimized to handle pure destination prefix filters in 4 memory accesses, destination-source filters in 8 memory accesses worst case, and all other filters in 11 memory accesses in the typical case.

References

[1]

M. Bailey et al. PathFinder. Proceedings of OSDI 94.

[2]

S. Bradner. Next generation routers overview. Proc. of Nctworld {nterop 97.

[3]

B. Chapman and E. Zwicky. Building Internet Firewalls. O'Rcilly arid Associate~, 1995.

Digital Library

[4]

B. Chazelle. Lower bounds for orthogonal range searching, I: The reporting case. J. of the ACM, 37, pp. 200- 212, 1990.

Digital Library

[5]

B. Chazelle. Lower bounds for orthogonal range searching, II: The Arithmetic model. Y. of the A CM, 37, pp. 439-463, 1990.

Digital Library

[6]

W. Cheswick and S. Bellovin. Firewalls and Internet Security. Addison- Wesley, 1995.

Digital Library

[7]

D. Decasper, Z. Dittia, G. Parulkar, B. Plattner. Router Plugins: A Software Architecture for Next Generation Routers' Proc. A CM Sigcomm 98, Sep 1998.

Digital Library

[8]

S. Deering and R. }linden. Internet protocol, Version 6 (IPv6) specification RFC 1883. http: //ds. int erni c .net/rf c/rf c 1883. txt.

Digital Library

[9]

M. Degermark, A. Brodnik, S. Carlsson, and S. Pink. Small forwarding tables for fast routing lookups. Proc. A CM Sigcomm 97, October 1997.

Digital Library

[10]

Digital Electronics Corporation. The DEC Alpha. http://www.dec.com.

[11]

D. Engler and M. Kaashoek. DPF: Fast Flexibible Message Demultiplexing using Dynamic Code Generation. Proceedings of A CM $igcomm 96., August 1996

Digital Library

[12]

lntel. The pentium processor. (www.pentium.com.)

[13]

Intel. The Vtune performance measurement tool. (www. intel, com/design/perftool/vtune)

[14]

C. Labovitz, G. Malan, and F. Jahanian. lnternet Routing Instability Proc. ACM Sigcomm 97, October 1997.

Digital Library

[15]

T.V. Lakshman and D. Stiliadis. High Speed Policy-based Packet Forwarding Using Efficient Multidimensional Range Matching. Proc. A CM Sigcomm 98, Sept 1998.

Digital Library

[16]

B. Lampson, V. Srinivasan, and G. Varghese. IP Lookups using Multiway and Multicolumn Search. Proc. lnfocom 98, March 1998.

[17]

S. McCanne and V. Jacobson. The Berkeley Path Finder. Proc. of Winter USENIX 1993.

[18]

N. McKeown, M. Izzard, A. Mekkittikul, B. Ellersick and M. Horowitz. The Tiny Tera: A Packet Switch Core IEEE Micro Jan/Feb 1997, pp 26-33

Digital Library

[19]

J. McQuillan. Layer 4 Switching. Data Communications, October 21, 1997

[20]

Merit Inc. IPMA statistics. (nic.merit.edu.)

[21]

P. Newman, G. Minshall, and L. Huston. IP Switching and Gigabit Routcrs. {EEE Communications Magazine, January 1997.

Digital Library

[22]

S. Nilsson and G. Karlsson. Fast Address Look-Up for Internct Routers. Proceedings of IEEE Broadband Communications 98, April 1998.

Digital Library

[23]

C. Partridge. Locality and route caches. In NSF Workshop on {nternet Statistics Measurement and Analysis, San Diego, CA, USA, February 1996.

[24]

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985.

Digital Library

[25]

H. Samet. The Design and Analysis of Spatial Data Structures. Addison- Wesley, 1989.

Digital Library

[26]

S. Suri, G. Varghese, M. Waldvogel, and V. Srinivasan. Layer Four Switching using Rectangle and Tuple Search. In preparation, 1998.

[27]

V. Srinivasan and George Varghese. Faster IP Lookups using Controlled Prefix Expansion. Proc. A CM Sigmetrics 98, June 1998

Digital Library

[28]

Torrent systems, Inc. http://www.torrent.com

[29]

P. Tsuchiya. A search algorithm for table entries with non-contiguous wildcarding. Unpublished report, Bellcore.

[30]

J Turner. Design of a Gigabit ATM Switch. Proc. $IGCOMM 97, October 1997.

Digital Library

[31]

M. Waldvogel, G. Varghese, J. Turner, and B. Plattner. Scalable high speed IP routing lookups. Proc S{GCOMM 97, October 1997.

Digital Library

[32]

L. Zhang et al. RSVP: A New Resource Reservation Protocol. {EEE Networks Magazine, Sept 1993.

Cited By

Xin YLi WJia CLi XXu YLiu BTian ZZhang W(2024)Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGAIEEE/ACM Transactions on Networking10.1109/TNET.2023.333038132:2(1707-1722)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3330381
Liu QPeng YTang ZJiang HWu JWang TPeng TWang G(2024)veffChain: Enabling Freshness Authentication of Rich Queries over Blockchain DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3316127(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3316127
Lin HWang P(2024)Scalable packet classification based on rule categorization and cross-productingComputer Networks10.1016/j.comnet.2023.110116238(110116)Online publication date: Jan-2024
https://doi.org/10.1016/j.comnet.2023.110116
Show More Cited By

Index Terms

Fast and scalable layer four switching
1. Networks
  1. Network protocols
    1. Transport protocols
  2. Network types
    1. Packet-switching networks
    2. Public Internet

Recommendations

Fast and scalable layer four switching

In Layer Four switching, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as source address, TCP and UDP port numbers. Layer Four switching unifies firewall ...
Scalable QoS-based IP multicast over label-switching wireless ATM networks

A Mobile IP multicast prototype that integrates a label-switching wireless asynchronous transfer mode, the mobile core-based multicast architecture, and an Internet multicast infrastructure is presented. MCOM creates multiple core-based layer 2 ...
Scalable application layer multicast
SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications

We describe a new scalable application-layer multicast protocol, specifically designed for low-bandwidth, data streaming applications with large receiver sets. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '98: Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication

October 1998

328 pages

ISBN:1581130031

DOI:10.1145/285237

Chairmen:
Gerald Neufeld
Univ. of British Columbia, Vancouver, B.C., Canada
,
Gary Delp
IBM Server Group
,
Jonathan Smith
Univ. of Pennsylvania, Philadelphia
,
Editor:
Martha Steenstrup
BBN Technologies, Cambridge, MA

ACM SIGCOMM Computer Communication Review Volume 28, Issue 4
Oct. 1998
311 pages
ISSN:0146-4833
DOI:10.1145/285243
Chairmen:
Gerald Neufeld
Univ. of British Columbia, Vancouver, B.C., Canada
,
Gary Delp
IBM Server Group
,
Jonathan Smith
Univ. of Pennsylvania, Philadelphia
,
Editor:
Martha Steenstrup
BBN Technologies, Cambridge, MA
Issue’s Table of Contents

Copyright © 1998 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGCOMM98

Sponsor:

SIGCOMM

SIGCOMM98: ACM SIGCOMM'98

August 31 - September 4, 1998

British Columbia, Vancouver, Canada

Acceptance Rates

SIGCOMM '98 Paper Acceptance Rate 26 of 247 submissions, 11%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

437
Total Citations
View Citations
2,075
Total Downloads

Downloads (Last 12 months)218
Downloads (Last 6 weeks)36

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xin YLi WJia CLi XXu YLiu BTian ZZhang W(2024)Recursive Multi-Tree Construction With Efficient Rule Sifting for Packet Classification on FPGAIEEE/ACM Transactions on Networking10.1109/TNET.2023.333038132:2(1707-1722)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3330381
Liu QPeng YTang ZJiang HWu JWang TPeng TWang G(2024)veffChain: Enabling Freshness Authentication of Rich Queries over Blockchain DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3316127(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3316127
Lin HWang P(2024)Scalable packet classification based on rule categorization and cross-productingComputer Networks10.1016/j.comnet.2023.110116238(110116)Online publication date: Jan-2024
https://doi.org/10.1016/j.comnet.2023.110116
Zhou GLiu ZFu CLi QXu KCalandrino JTroncoso C(2023)An efficient design of intelligent network data planeProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620584(6203-6220)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620584
Kekely MKořenek J(2023)Optimizing Packet Classification on FPGA2023 26th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS)10.1109/DDECS57882.2023.10139668(7-12)Online publication date: 3-May-2023
https://doi.org/10.1109/DDECS57882.2023.10139668
Trivedi UDokku LSangamesh J(2023)Efficient Memory Optimized Aggregated Bit Vector (EMOABV) Algorithm with Dynamic ABV Intersection Result Cache2023 15th International Conference on COMmunication Systems & NETworkS (COMSNETS)10.1109/COMSNETS56262.2023.10041345(632-639)Online publication date: 3-Jan-2023
https://doi.org/10.1109/COMSNETS56262.2023.10041345
Ma XZhong HXiu NChen YYin GNarayanan VLiu YNi KYang HLi X(2022)CapCAM: A Multilevel Capacitive Content Addressable Memory for High-Accuracy and High-Scalability Search and Compute ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2022.319849230:11(1770-1782)Online publication date: Nov-2022
https://doi.org/10.1109/TVLSI.2022.3198492
Wan XWang JLi JLiu XFu XWang X(2022)Research on Satellite Quality of Service Classifier Based on Modified Recursive Flow Classification Algorithm2022 5th International Conference on Information Communication and Signal Processing (ICICSP)10.1109/ICICSP55539.2022.10050654(414-418)Online publication date: 26-Nov-2022
https://doi.org/10.1109/ICICSP55539.2022.10050654
Kaljic EMaric ANjemcevic P(2022)Bloom filter based acceleration scheme for flow table lookup in SDN switches2022 XXVIII International Conference on Information, Communication and Automation Technologies (ICAT)10.1109/ICAT54566.2022.9811185(1-6)Online publication date: 16-Jun-2022
https://doi.org/10.1109/ICAT54566.2022.9811185
Wang SLiu KJiang CYan JKuang L(2022)EFS: Efficient Storage Optimization for Multistage Flow-Table in Software-Defined Satellite NetworkIEEE Access10.1109/ACCESS.2021.313839910(391-400)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2021.3138399
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents