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

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 Ne89e1460960b4dbf914eda9192de05c4
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 N569bffb3a98b4d96bf19ff46df65aef1
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N71bfb802969e48a0af9714ebf49d2328
21 schema:name XOR-Based Schemes for Fast Parallel IP Lookups
22 schema:pagination 238-250
23 schema:productId N28d1a1335cc0430b9e127a6ccdcb3681
24 N54975fa4a9ab4b04bdcc4676e833e7f1
25 Nce790183576043e09cf5102df05a3bf4
26 schema:publisher N41026c517f4647f19bf0d861cf359b19
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 N62bd6b2b78af46498ba234e6eb775398
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 N28d1a1335cc0430b9e127a6ccdcb3681 schema:name readcube_id
37 schema:value 008f0af64f31a478f6c9d49b7fa88e0328d4696a57d94f498db0eb603e5d1452
38 rdf:type schema:PropertyValue
39 N405a8e17435e4adaa542ce254d14d30d rdf:first N412e7300f6b245baa0869763be51cda7
40 rdf:rest Nb4d713504233426fbea3352e17f53eb7
41 N41026c517f4647f19bf0d861cf359b19 schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N412e7300f6b245baa0869763be51cda7 schema:familyName Persiano
45 schema:givenName Giuseppe
46 rdf:type schema:Person
47 N54975fa4a9ab4b04bdcc4676e833e7f1 schema:name dimensions_id
48 schema:value pub.1000117487
49 rdf:type schema:PropertyValue
50 N569bffb3a98b4d96bf19ff46df65aef1 rdf:first N832f1a8deec040e0b4238f0882dc8263
51 rdf:rest N405a8e17435e4adaa542ce254d14d30d
52 N62bd6b2b78af46498ba234e6eb775398 schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N71bfb802969e48a0af9714ebf49d2328 schema:isbn 978-3-540-40176-6
55 978-3-540-44849-5
56 schema:name Algorithms and Complexity
57 rdf:type schema:Book
58 N832f1a8deec040e0b4238f0882dc8263 schema:familyName Petreschi
59 schema:givenName Rossella
60 rdf:type schema:Person
61 Nb4d713504233426fbea3352e17f53eb7 rdf:first Nb66e0a6dd5c341c38384e2aedc67a76b
62 rdf:rest rdf:nil
63 Nb66e0a6dd5c341c38384e2aedc67a76b schema:familyName Silvestri
64 schema:givenName Riccardo
65 rdf:type schema:Person
66 Nce790183576043e09cf5102df05a3bf4 schema:name doi
67 schema:value 10.1007/3-540-44849-7_28
68 rdf:type schema:PropertyValue
69 Ne89e1460960b4dbf914eda9192de05c4 rdf:first sg:person.015720366465.66
70 rdf:rest Neb34c3f0bb96453b9e1204104d3f5d7b
71 Neb34c3f0bb96453b9e1204104d3f5d7b rdf:first sg:person.013624103516.76
72 rdf:rest rdf:nil
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)


...