Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-08-29

AUTHORS

Hsueh-I Lu

ABSTRACT

We address the problem of designing compact routing tables for an unlabeled connected n-node planar network G. For each node r of G, the designer is given a routing spanning tree Tr of G rooted at r, which specifies the routes for sending packets from r to the rest of G. Each node r of G is equipped with ports 1,2,...,dr, where dr is the degree of r in Tr. Each port of r is supposed to be assigned to a neighbor of r in Tr in a one-to-one manner. For each node v of G with υ ≠ r, let portr (υ) be the port to which r should forward packets with destination υ. Under the assumption that the designer has the freedom to determine the label and the port assignment of each node in G, the routing table design problem is to design a compact routing table Rr for r such that portr(υ) can be determined only from Rr and the label of υ.Compact routing tables for various network topologies have been extensively studied in the literature. Planar networks are particularly important for routing with geometric metrics. Based upon four-page decompositions of G, Gavoille and Hanusse gave the best previously known result for this problem: Each portr(υ) is computable in O(log2+∈n) bit operations for any positive constant ɛ; and the number of bits required to encode their Rr is at most 8n + o(n). We give a new design that improves the code length of Rr to at most 7.181n + o(n) bits without increasing the time required to compute portr(v). More... »

PAGES

57-66

Book

TITLE

Computing and Combinatorics

ISBN

978-3-540-43996-7
978-3-540-45655-1

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45655-4_8

DOI

http://dx.doi.org/10.1007/3-540-45655-4_8

DIMENSIONS

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


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/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Academia Sinica, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Academia Sinica, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-08-29", 
    "datePublishedReg": "2002-08-29", 
    "description": "We address the problem of designing compact routing tables for an unlabeled connected n-node planar network G. For each node r of G, the designer is given a routing spanning tree Tr of G rooted at r, which specifies the routes for sending packets from r to the rest of G. Each node r of G is equipped with ports 1,2,...,dr, where dr is the degree of r in Tr. Each port of r is supposed to be assigned to a neighbor of r in Tr in a one-to-one manner. For each node v of G with \u03c5 \u2260 r, let portr (\u03c5) be the port to which r should forward packets with destination \u03c5. Under the assumption that the designer has the freedom to determine the label and the port assignment of each node in G, the routing table design problem is to design a compact routing table Rr for r such that portr(\u03c5) can be determined only from Rr and the label of \u03c5.Compact routing tables for various network topologies have been extensively studied in the literature. Planar networks are particularly important for routing with geometric metrics. Based upon four-page decompositions of G, Gavoille and Hanusse gave the best previously known result for this problem: Each portr(\u03c5) is computable in O(log2+\u2208n) bit operations for any positive constant \u025b; and the number of bits required to encode their Rr is at most 8n + o(n). We give a new design that improves the code length of Rr to at most 7.181n + o(n) bits without increasing the time required to compute portr(v).", 
    "editor": [
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar H.", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhang", 
        "givenName": "Louxin", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45655-4_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-43996-7", 
        "978-3-540-45655-1"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "compact routing tables", 
      "routing tables", 
      "network topology", 
      "planar networks", 
      "number of bits", 
      "node r", 
      "bit operations", 
      "code length", 
      "spanning tree", 
      "network G.", 
      "packets", 
      "node v", 
      "port assignment", 
      "design problem", 
      "designers", 
      "network", 
      "labels", 
      "geometric metrics", 
      "table", 
      "nodes", 
      "Gavoille", 
      "neighbors", 
      "topology", 
      "metrics", 
      "bits", 
      "new design", 
      "ports", 
      "assignment", 
      "operation", 
      "design", 
      "trees", 
      "decomposition", 
      "manner", 
      "assumption", 
      "number", 
      "time", 
      "freedom", 
      "literature", 
      "results", 
      "route", 
      "rest", 
      "DR", 
      "degree", 
      "TR", 
      "length", 
      "RR", 
      "G.", 
      "problem", 
      "orderly spanning trees"
    ], 
    "name": "Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees", 
    "pagination": "57-66", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033792654"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45655-4_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45655-4_8", 
      "https://app.dimensions.ai/details/publication/pub.1033792654"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_463.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45655-4_8"
  }
]
 

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-45655-4_8'

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-45655-4_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45655-4_8'

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-45655-4_8'


 

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

114 TRIPLES      23 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45655-4_8 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author N0cfa7f5f3d9a431db02bcbeb998d641a
4 schema:datePublished 2002-08-29
5 schema:datePublishedReg 2002-08-29
6 schema:description We address the problem of designing compact routing tables for an unlabeled connected n-node planar network G. For each node r of G, the designer is given a routing spanning tree Tr of G rooted at r, which specifies the routes for sending packets from r to the rest of G. Each node r of G is equipped with ports 1,2,...,dr, where dr is the degree of r in Tr. Each port of r is supposed to be assigned to a neighbor of r in Tr in a one-to-one manner. For each node v of G with υ ≠ r, let portr (υ) be the port to which r should forward packets with destination υ. Under the assumption that the designer has the freedom to determine the label and the port assignment of each node in G, the routing table design problem is to design a compact routing table Rr for r such that portr(υ) can be determined only from Rr and the label of υ.Compact routing tables for various network topologies have been extensively studied in the literature. Planar networks are particularly important for routing with geometric metrics. Based upon four-page decompositions of G, Gavoille and Hanusse gave the best previously known result for this problem: Each portr(υ) is computable in O(log2+∈n) bit operations for any positive constant ɛ; and the number of bits required to encode their Rr is at most 8n + o(n). We give a new design that improves the code length of Rr to at most 7.181n + o(n) bits without increasing the time required to compute portr(v).
7 schema:editor N222105a2543e4cba91e74cffb10fe68e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nea70f3cc14a54ae3b2b40fd6128c917c
12 schema:keywords DR
13 G.
14 Gavoille
15 RR
16 TR
17 assignment
18 assumption
19 bit operations
20 bits
21 code length
22 compact routing tables
23 decomposition
24 degree
25 design
26 design problem
27 designers
28 freedom
29 geometric metrics
30 labels
31 length
32 literature
33 manner
34 metrics
35 neighbors
36 network
37 network G.
38 network topology
39 new design
40 node r
41 node v
42 nodes
43 number
44 number of bits
45 operation
46 orderly spanning trees
47 packets
48 planar networks
49 port assignment
50 ports
51 problem
52 rest
53 results
54 route
55 routing tables
56 spanning tree
57 table
58 time
59 topology
60 trees
61 schema:name Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees
62 schema:pagination 57-66
63 schema:productId N30bd039314254d7eb500e7a757c385eb
64 N937f04cea3224dfdb36607fbeb755f1b
65 schema:publisher N080a488500284251bb7c0fb529f65dc4
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033792654
67 https://doi.org/10.1007/3-540-45655-4_8
68 schema:sdDatePublished 2022-05-10T10:54
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N2520377896ba4987b4df3cf92c6e4759
71 schema:url https://doi.org/10.1007/3-540-45655-4_8
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N080a488500284251bb7c0fb529f65dc4 schema:name Springer Nature
76 rdf:type schema:Organisation
77 N0cfa7f5f3d9a431db02bcbeb998d641a rdf:first sg:person.013345515575.46
78 rdf:rest rdf:nil
79 N222105a2543e4cba91e74cffb10fe68e rdf:first N60d03296c94c41b6ae558f4fc40daf97
80 rdf:rest Nbd070e921b32443e965c42f22b83419b
81 N2520377896ba4987b4df3cf92c6e4759 schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 N30bd039314254d7eb500e7a757c385eb schema:name doi
84 schema:value 10.1007/3-540-45655-4_8
85 rdf:type schema:PropertyValue
86 N60d03296c94c41b6ae558f4fc40daf97 schema:familyName Ibarra
87 schema:givenName Oscar H.
88 rdf:type schema:Person
89 N6fb3788270944c25be95f07161989ccd schema:familyName Zhang
90 schema:givenName Louxin
91 rdf:type schema:Person
92 N937f04cea3224dfdb36607fbeb755f1b schema:name dimensions_id
93 schema:value pub.1033792654
94 rdf:type schema:PropertyValue
95 Nbd070e921b32443e965c42f22b83419b rdf:first N6fb3788270944c25be95f07161989ccd
96 rdf:rest rdf:nil
97 Nea70f3cc14a54ae3b2b40fd6128c917c schema:isbn 978-3-540-43996-7
98 978-3-540-45655-1
99 schema:name Computing and Combinatorics
100 rdf:type schema:Book
101 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
102 schema:name Technology
103 rdf:type schema:DefinedTerm
104 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
105 schema:name Communications Technologies
106 rdf:type schema:DefinedTerm
107 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.28665.3f
108 schema:familyName Lu
109 schema:givenName Hsueh-I
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
111 rdf:type schema:Person
112 grid-institutes:grid.28665.3f schema:alternateName Academia Sinica, Taiwan
113 schema:name Academia Sinica, Taiwan
114 rdf:type schema:Organization
 




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


...