IP Address LookupMade Fast and Simple View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2003-01-14

AUTHORS

Pierluigi Crescenzi , Leandro Dardini , Roberto Grossi

ABSTRACT

The IP address lookup problem is one of the major bottlenecks in high performance routers. Previous solutions to this problem first describe it in the general terms of longest prefix matching and, then, are experimented on real routing tables T. In this paper, we follow the opposite direction. We start out from the experimental analysis of real data and, based upon our findings, we provide a new and simple solution to the IP address lookup problem. More precisely, our solution for m-bit IP addresses is a reasonable trade-off between performing a binary search on T with O(log |T|) accesses, where |T| is the number of entries in T, and executing a single access on a table of 2m entries obtained by fully expanding T. While the previous results start out from space-efficient data structures and aim at lowering the O(log |T|) access cost, we start out from the expanded table with 2m entries and aim at compressing it without an excessive increase in the number of accesses. Our algorithm takes exactly three memory accesses and occupies O(2m/2 + |T|2) space in the worst case. Experiments on real routing tables for m = 32 show that the space bound is overly pessimistic. Our solution occupies approximately one megabyte for the MaeEast routing table (which has |T| ≈ 44; 000 and requires approximately 250 KB) and, thus, takes three cache accesses on any processor with 1MB of L2 cache. According to the measurement obtained by the VTune tool on a Pentium II processor, each lookup requires 3 additional clock cycles besides the ones needed for the memory accesses. Assuming a clock cycle of 3.33 nanoseconds and an L2 cache latency of 15 nanoseconds, search of MaeEast can be estimated in 55 nanoseconds or, equivalently, our method performs 18 millions of lookups per second. More... »

PAGES

65-76

Book

TITLE

Algorithms - ESA’ 99

ISBN

978-3-540-66251-8
978-3-540-48481-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48481-7_7

DOI

http://dx.doi.org/10.1007/3-540-48481-7_7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1008294320


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Florence", 
          "id": "https://www.grid.ac/institutes/grid.8404.8", 
          "name": [
            "Dipartimento di Sistemi e Informatica, Universit\u00e0 degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Crescenzi", 
        "givenName": "Pierluigi", 
        "id": "sg:person.01173734710.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01173734710.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Florence", 
          "id": "https://www.grid.ac/institutes/grid.8404.8", 
          "name": [
            "Dipartimento di Sistemi e Informatica, Universit\u00e0 degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dardini", 
        "givenName": "Leandro", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Pisa", 
          "id": "https://www.grid.ac/institutes/grid.5395.a", 
          "name": [
            "Dipartimento di Informatica, Universit\u00e0 degli Studi di Pisa, Corso Italia 40, 56125, Pisa, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grossi", 
        "givenName": "Roberto", 
        "id": "sg:person.01062373707.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01062373707.91"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/321479.321481", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032866802"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/35.568212", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061159373"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/65.120723", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061205336"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/90.700888", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061247387"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/263109.263133", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063163891"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/263109.263136", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063163892"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003-01-14", 
    "datePublishedReg": "2003-01-14", 
    "description": "The IP address lookup problem is one of the major bottlenecks in high performance routers. Previous solutions to this problem first describe it in the general terms of longest prefix matching and, then, are experimented on real routing tables T. In this paper, we follow the opposite direction. We start out from the experimental analysis of real data and, based upon our findings, we provide a new and simple solution to the IP address lookup problem. More precisely, our solution for m-bit IP addresses is a reasonable trade-off between performing a binary search on T with O(log |T|) accesses, where |T| is the number of entries in T, and executing a single access on a table of 2m entries obtained by fully expanding T. While the previous results start out from space-efficient data structures and aim at lowering the O(log |T|) access cost, we start out from the expanded table with 2m entries and aim at compressing it without an excessive increase in the number of accesses. Our algorithm takes exactly three memory accesses and occupies O(2m/2 + |T|2) space in the worst case. Experiments on real routing tables for m = 32 show that the space bound is overly pessimistic. Our solution occupies approximately one megabyte for the MaeEast routing table (which has |T| \u2248 44; 000 and requires approximately 250 KB) and, thus, takes three cache accesses on any processor with 1MB of L2 cache. According to the measurement obtained by the VTune tool on a Pentium II processor, each lookup requires 3 additional clock cycles besides the ones needed for the memory accesses. Assuming a clock cycle of 3.33 nanoseconds and an L2 cache latency of 15 nanoseconds, search of MaeEast can be estimated in 55 nanoseconds or, equivalently, our method performs 18 millions of lookups per second.", 
    "editor": [
      {
        "familyName": "Ne\u0161et\u0159il", 
        "givenName": "Jaroslav", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48481-7_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66251-8", 
        "978-3-540-48481-3"
      ], 
      "name": "Algorithms - ESA\u2019 99", 
      "type": "Book"
    }, 
    "name": "IP Address LookupMade Fast and Simple", 
    "pagination": "65-76", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48481-7_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2783918bd850fce988a9e20e33e2bd4b75bc13c5b4dd6add20d677283433c046"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008294320"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48481-7_7", 
      "https://app.dimensions.ai/details/publication/pub.1008294320"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000346_0000000346/records_99803_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-48481-7_7"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48481-7_7'


 

This table displays all metadata directly associated to this object as RDF triples.

99 TRIPLES      23 PREDICATES      32 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48481-7_7 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author N945d111b98e74faab946e783eaf9a1a0
4 schema:citation https://doi.org/10.1109/35.568212
5 https://doi.org/10.1109/65.120723
6 https://doi.org/10.1109/90.700888
7 https://doi.org/10.1145/263109.263133
8 https://doi.org/10.1145/263109.263136
9 https://doi.org/10.1145/321479.321481
10 schema:datePublished 2003-01-14
11 schema:datePublishedReg 2003-01-14
12 schema:description The IP address lookup problem is one of the major bottlenecks in high performance routers. Previous solutions to this problem first describe it in the general terms of longest prefix matching and, then, are experimented on real routing tables T. In this paper, we follow the opposite direction. We start out from the experimental analysis of real data and, based upon our findings, we provide a new and simple solution to the IP address lookup problem. More precisely, our solution for m-bit IP addresses is a reasonable trade-off between performing a binary search on T with O(log |T|) accesses, where |T| is the number of entries in T, and executing a single access on a table of 2m entries obtained by fully expanding T. While the previous results start out from space-efficient data structures and aim at lowering the O(log |T|) access cost, we start out from the expanded table with 2m entries and aim at compressing it without an excessive increase in the number of accesses. Our algorithm takes exactly three memory accesses and occupies O(2m/2 + |T|2) space in the worst case. Experiments on real routing tables for m = 32 show that the space bound is overly pessimistic. Our solution occupies approximately one megabyte for the MaeEast routing table (which has |T| ≈ 44; 000 and requires approximately 250 KB) and, thus, takes three cache accesses on any processor with 1MB of L2 cache. According to the measurement obtained by the VTune tool on a Pentium II processor, each lookup requires 3 additional clock cycles besides the ones needed for the memory accesses. Assuming a clock cycle of 3.33 nanoseconds and an L2 cache latency of 15 nanoseconds, search of MaeEast can be estimated in 55 nanoseconds or, equivalently, our method performs 18 millions of lookups per second.
13 schema:editor N2129330c52a94a239192fd8c56989608
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf N0c1a28fc625344a7bfd6dc5689d7b0cd
18 schema:name IP Address LookupMade Fast and Simple
19 schema:pagination 65-76
20 schema:productId N4d80bb63578b4fc09f914c6beb3103b1
21 N59fc285477ed428dbaf154b01d8f2d3c
22 Na5eec06cb9cb46fb8cbd831fc8edc11f
23 schema:publisher N08882bbd030941e9b680905d43b71499
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008294320
25 https://doi.org/10.1007/3-540-48481-7_7
26 schema:sdDatePublished 2019-04-16T05:30
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N16da7215ba334b2a9538bf428abced09
29 schema:url https://link.springer.com/10.1007%2F3-540-48481-7_7
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N08882bbd030941e9b680905d43b71499 schema:location Berlin, Heidelberg
34 schema:name Springer Berlin Heidelberg
35 rdf:type schema:Organisation
36 N0c1a28fc625344a7bfd6dc5689d7b0cd schema:isbn 978-3-540-48481-3
37 978-3-540-66251-8
38 schema:name Algorithms - ESA’ 99
39 rdf:type schema:Book
40 N16da7215ba334b2a9538bf428abced09 schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N2129330c52a94a239192fd8c56989608 rdf:first Nc3ac70e78d094dceb9945a0f94e8cfbb
43 rdf:rest rdf:nil
44 N48352ebd1f844301908d78ff3a29125a rdf:first sg:person.01062373707.91
45 rdf:rest rdf:nil
46 N4d80bb63578b4fc09f914c6beb3103b1 schema:name readcube_id
47 schema:value 2783918bd850fce988a9e20e33e2bd4b75bc13c5b4dd6add20d677283433c046
48 rdf:type schema:PropertyValue
49 N538cd9a0a0f3462aa8723499cff33345 schema:affiliation https://www.grid.ac/institutes/grid.8404.8
50 schema:familyName Dardini
51 schema:givenName Leandro
52 rdf:type schema:Person
53 N59fc285477ed428dbaf154b01d8f2d3c schema:name doi
54 schema:value 10.1007/3-540-48481-7_7
55 rdf:type schema:PropertyValue
56 N945d111b98e74faab946e783eaf9a1a0 rdf:first sg:person.01173734710.11
57 rdf:rest N9d845799999e41d0aa25804efb2f5ad2
58 N9d845799999e41d0aa25804efb2f5ad2 rdf:first N538cd9a0a0f3462aa8723499cff33345
59 rdf:rest N48352ebd1f844301908d78ff3a29125a
60 Na5eec06cb9cb46fb8cbd831fc8edc11f schema:name dimensions_id
61 schema:value pub.1008294320
62 rdf:type schema:PropertyValue
63 Nc3ac70e78d094dceb9945a0f94e8cfbb schema:familyName Nešetřil
64 schema:givenName Jaroslav
65 rdf:type schema:Person
66 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
67 schema:name Technology
68 rdf:type schema:DefinedTerm
69 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
70 schema:name Communications Technologies
71 rdf:type schema:DefinedTerm
72 sg:person.01062373707.91 schema:affiliation https://www.grid.ac/institutes/grid.5395.a
73 schema:familyName Grossi
74 schema:givenName Roberto
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01062373707.91
76 rdf:type schema:Person
77 sg:person.01173734710.11 schema:affiliation https://www.grid.ac/institutes/grid.8404.8
78 schema:familyName Crescenzi
79 schema:givenName Pierluigi
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01173734710.11
81 rdf:type schema:Person
82 https://doi.org/10.1109/35.568212 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061159373
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1109/65.120723 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061205336
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1109/90.700888 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247387
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1145/263109.263133 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063163891
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1145/263109.263136 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063163892
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1145/321479.321481 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032866802
93 rdf:type schema:CreativeWork
94 https://www.grid.ac/institutes/grid.5395.a schema:alternateName University of Pisa
95 schema:name Dipartimento di Informatica, Università degli Studi di Pisa, Corso Italia 40, 56125, Pisa, Italy
96 rdf:type schema:Organization
97 https://www.grid.ac/institutes/grid.8404.8 schema:alternateName University of Florence
98 schema:name Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Via C. Lombroso 6/17, 50134, Firenze, Italy
99 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...