XOR-Based Schemes for Fast Parallel IP Lookups View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003-05-13

AUTHORS

Giancarlo Bongiovanni , Paolo Penna

ABSTRACT

An IP router must forward packets at gigabit speed in order to guarantee a good QoS. Two important factors make this task a challenging problem: (i) for each packet, the longest matching preffix in the forwarding table must be computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work, we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router to also reduce the size of the routing table. Our method is scalable and requires onlya minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T1 and T2 such that: (a) |T1| can be any positive integer k ≤ |T| and |T2| ≤ |T| ∑ k; (b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent on the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: (a) |T1| is roughly 7% of the original table T; (b) the lookup on table T2 does not require the best matching preffix computation. More... »

PAGES

238-250

References to SciGraph publications

  • 2003-01-14. IP Address LookupMade Fast and Simple in ALGORITHMS - ESA’ 99
  • Book

    TITLE

    Algorithms and Complexity

    ISBN

    978-3-540-40176-6
    978-3-540-44849-5

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-44849-7_28

    DOI

    http://dx.doi.org/10.1007/3-540-44849-7_28

    DIMENSIONS

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


    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/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Scienze dell\u2019Informazione, Universit\u00e0 di Roma \u201cLa Sapienza\u201d, via Salaria 113, I-00133, Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bongiovanni", 
            "givenName": "Giancarlo", 
            "id": "sg:person.015720366465.66", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015720366465.66"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Salerno", 
              "id": "https://www.grid.ac/institutes/grid.11780.3f", 
              "name": [
                "Dipartimento di Informatica ed Applicazioni \u201cR.M. Capocelli\u201d, Universit\u00e0 di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Penna", 
            "givenName": "Paolo", 
            "id": "sg:person.013624103516.76", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/263105.263136", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003362247"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48481-7_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008294320", 
              "https://doi.org/10.1007/3-540-48481-7_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48481-7_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008294320", 
              "https://doi.org/10.1007/3-540-48481-7_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/510726.510751", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024598781"
            ], 
            "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.1109/infcom.2002.1019301", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094410056"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infcom.1999.749286", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094428744"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2003-05-13", 
        "datePublishedReg": "2003-05-13", 
        "description": "An IP router must forward packets at gigabit speed in order to guarantee a good QoS. Two important factors make this task a challenging problem: (i) for each packet, the longest matching preffix in the forwarding table must be computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work, we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router to also reduce the size of the routing table. Our method is scalable and requires onlya minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T1 and T2 such that: (a) |T1| can be any positive integer k \u2264 |T| and |T2| \u2264 |T| \u2211 k; (b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent on the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: (a) |T1| is roughly 7% of the original table T; (b) the lookup on table T2 does not require the best matching preffix computation.", 
        "editor": [
          {
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "type": "Person"
          }, 
          {
            "familyName": "Persiano", 
            "givenName": "Giuseppe", 
            "type": "Person"
          }, 
          {
            "familyName": "Silvestri", 
            "givenName": "Riccardo", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-44849-7_28", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-40176-6", 
            "978-3-540-44849-5"
          ], 
          "name": "Algorithms and Complexity", 
          "type": "Book"
        }, 
        "name": "XOR-Based Schemes for Fast Parallel IP Lookups", 
        "pagination": "238-250", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-44849-7_28"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "008f0af64f31a478f6c9d49b7fa88e0328d4696a57d94f498db0eb603e5d1452"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1000117487"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-44849-7_28", 
          "https://app.dimensions.ai/details/publication/pub.1000117487"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:28", 
        "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/0000000345_0000000345/records_64119_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-44849-7_28"
      }
    ]
     

    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-44849-7_28'

    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-44849-7_28'

    Turtle is a human-readable linked data format.

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

    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-44849-7_28'


     

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

    113 TRIPLES      23 PREDICATES      35 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-44849-7_28 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author N73df590a45d1453c94b681598af1c4e1
    4 schema:citation sg:pub.10.1007/3-540-48481-7_7
    5 https://doi.org/10.1109/35.568212
    6 https://doi.org/10.1109/65.120723
    7 https://doi.org/10.1109/90.700888
    8 https://doi.org/10.1109/infcom.1999.749286
    9 https://doi.org/10.1109/infcom.2002.1019301
    10 https://doi.org/10.1145/263105.263136
    11 https://doi.org/10.1145/263109.263133
    12 https://doi.org/10.1145/510726.510751
    13 schema:datePublished 2003-05-13
    14 schema:datePublishedReg 2003-05-13
    15 schema:description An IP router must forward packets at gigabit speed in order to guarantee a good QoS. Two important factors make this task a challenging problem: (i) for each packet, the longest matching preffix in the forwarding table must be computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work, we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router to also reduce the size of the routing table. Our method is scalable and requires onlya minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T1 and T2 such that: (a) |T1| can be any positive integer k ≤ |T| and |T2| ≤ |T| ∑ k; (b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent on the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: (a) |T1| is roughly 7% of the original table T; (b) the lookup on table T2 does not require the best matching preffix computation.
    16 schema:editor N2d28f17ce1e54e09bf31458c9d004196
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf Ndda352bbbb394bd0a34bda78bf9e871e
    21 schema:name XOR-Based Schemes for Fast Parallel IP Lookups
    22 schema:pagination 238-250
    23 schema:productId N02ccffa2493b42cd9a229374f8bce935
    24 N28c92f4a3d764d7c9f4a9470df536661
    25 N9085a61774c54a278d56e2aa62c79d00
    26 schema:publisher Nbf878239a67b43a9902e543fc1aa425d
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000117487
    28 https://doi.org/10.1007/3-540-44849-7_28
    29 schema:sdDatePublished 2019-04-16T05:28
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N2a85cd413528430a94d96a17d0c71054
    32 schema:url https://link.springer.com/10.1007%2F3-540-44849-7_28
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N02ccffa2493b42cd9a229374f8bce935 schema:name readcube_id
    37 schema:value 008f0af64f31a478f6c9d49b7fa88e0328d4696a57d94f498db0eb603e5d1452
    38 rdf:type schema:PropertyValue
    39 N22d139acde4f4b95b84803bde5c1bd02 rdf:first sg:person.013624103516.76
    40 rdf:rest rdf:nil
    41 N28c92f4a3d764d7c9f4a9470df536661 schema:name doi
    42 schema:value 10.1007/3-540-44849-7_28
    43 rdf:type schema:PropertyValue
    44 N2a85cd413528430a94d96a17d0c71054 schema:name Springer Nature - SN SciGraph project
    45 rdf:type schema:Organization
    46 N2d28f17ce1e54e09bf31458c9d004196 rdf:first N66dc74286f394547989636a955d4d2eb
    47 rdf:rest N5af2d51e3bb1483dba59f63ea8cab13f
    48 N3fdc1bf05edd40b181f616f3614c1107 schema:familyName Persiano
    49 schema:givenName Giuseppe
    50 rdf:type schema:Person
    51 N564aaf927039487181c253ca328cc2d3 schema:familyName Silvestri
    52 schema:givenName Riccardo
    53 rdf:type schema:Person
    54 N5af2d51e3bb1483dba59f63ea8cab13f rdf:first N3fdc1bf05edd40b181f616f3614c1107
    55 rdf:rest N6c1fcada5a994df687d477fe1d91ce58
    56 N66dc74286f394547989636a955d4d2eb schema:familyName Petreschi
    57 schema:givenName Rossella
    58 rdf:type schema:Person
    59 N6c1fcada5a994df687d477fe1d91ce58 rdf:first N564aaf927039487181c253ca328cc2d3
    60 rdf:rest rdf:nil
    61 N73df590a45d1453c94b681598af1c4e1 rdf:first sg:person.015720366465.66
    62 rdf:rest N22d139acde4f4b95b84803bde5c1bd02
    63 N9085a61774c54a278d56e2aa62c79d00 schema:name dimensions_id
    64 schema:value pub.1000117487
    65 rdf:type schema:PropertyValue
    66 Nbf878239a67b43a9902e543fc1aa425d schema:location Berlin, Heidelberg
    67 schema:name Springer Berlin Heidelberg
    68 rdf:type schema:Organisation
    69 Ndda352bbbb394bd0a34bda78bf9e871e schema:isbn 978-3-540-40176-6
    70 978-3-540-44849-5
    71 schema:name Algorithms and Complexity
    72 rdf:type schema:Book
    73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Mathematical Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Statistics
    78 rdf:type schema:DefinedTerm
    79 sg:person.013624103516.76 schema:affiliation https://www.grid.ac/institutes/grid.11780.3f
    80 schema:familyName Penna
    81 schema:givenName Paolo
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624103516.76
    83 rdf:type schema:Person
    84 sg:person.015720366465.66 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    85 schema:familyName Bongiovanni
    86 schema:givenName Giancarlo
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015720366465.66
    88 rdf:type schema:Person
    89 sg:pub.10.1007/3-540-48481-7_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008294320
    90 https://doi.org/10.1007/3-540-48481-7_7
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1109/35.568212 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061159373
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1109/65.120723 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061205336
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1109/90.700888 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247387
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1109/infcom.1999.749286 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094428744
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1109/infcom.2002.1019301 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094410056
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1145/263105.263136 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003362247
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1145/263109.263133 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063163891
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1145/510726.510751 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024598781
    107 rdf:type schema:CreativeWork
    108 https://www.grid.ac/institutes/grid.11780.3f schema:alternateName University of Salerno
    109 schema:name Dipartimento di Informatica ed Applicazioni “R.M. Capocelli”, Università di Salerno, via S. Allende 2, I-84081, Baronissi (SA), Italy
    110 rdf:type schema:Organization
    111 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    112 schema:name Dipartimento di Scienze dell’Informazione, Università di Roma “La Sapienza”, via Salaria 113, I-00133, Roma, Italy
    113 rdf:type schema:Organization
     




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


    ...