Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-06-25

AUTHORS

Alex Fabrikant , Elias Koutsoupias , Christos H. Papadimitriou

ABSTRACT

We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999] based on a toy model of Internet growth in which two objectives are optimized simultaneously: “last mile” connection costs, and transmission delays measured in hops. We also point out a similar phenomenon, anticipated in [Carlson and Doyle, Physics Review E 1999], in the distribution of file sizes. Our results seem to suggest that power laws tend to arise as a result of complex, multi-objective optimization. More... »

PAGES

110-122

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45465-9_11

DOI

http://dx.doi.org/10.1007/3-540-45465-9_11

DIMENSIONS

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


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/18", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Law and Legal Studies", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Law", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fabrikant", 
        "givenName": "Alex", 
        "id": "sg:person.07731456073.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731456073.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Department, University of Athens and UCLA, 3731 Boelter Hall, 90095, Los Angeles, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "Computer Science Department, University of Athens and UCLA, 3731 Boelter Hall, 90095, Los Angeles, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Koutsoupias", 
        "givenName": "Elias", 
        "id": "sg:person.016555647611.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016555647611.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-06-25", 
    "datePublishedReg": "2002-06-25", 
    "description": "We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999] based on a toy model of Internet growth in which two objectives are optimized simultaneously: \u201clast mile\u201d connection costs, and transmission delays measured in hops. We also point out a similar phenomenon, anticipated in [Carlson and Doyle, Physics Review E 1999], in the distribution of file sizes. Our results seem to suggest that power laws tend to arise as a result of complex, multi-objective optimization.", 
    "editor": [
      {
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Eidenbenz", 
        "givenName": "Stephan", 
        "type": "Person"
      }, 
      {
        "familyName": "Triguero", 
        "givenName": "Francisco", 
        "type": "Person"
      }, 
      {
        "familyName": "Morales", 
        "givenName": "Rafael", 
        "type": "Person"
      }, 
      {
        "familyName": "Conejo", 
        "givenName": "Ricardo", 
        "type": "Person"
      }, 
      {
        "familyName": "Hennessy", 
        "givenName": "Matthew", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45465-9_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-43864-9", 
        "978-3-540-45465-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "multi-objective optimization", 
      "power law distribution", 
      "Internet topology", 
      "toy model", 
      "transmission delay", 
      "power law", 
      "law distribution", 
      "connection cost", 
      "optimization", 
      "law", 
      "Trade-Offs", 
      "topology", 
      "graph", 
      "delay", 
      "Internet growth", 
      "distribution", 
      "last mile", 
      "model", 
      "hop", 
      "results", 
      "new paradigm", 
      "cost", 
      "objective", 
      "phenomenon", 
      "file size", 
      "Internet", 
      "paradigm", 
      "similar phenomenon", 
      "degree", 
      "size", 
      "explanation", 
      "plausible explanation", 
      "miles", 
      "growth", 
      "Optimized Trade-Offs"
    ], 
    "name": "Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet", 
    "pagination": "110-122", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024402121"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45465-9_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45465-9_11", 
      "https://app.dimensions.ai/details/publication/pub.1024402121"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_259.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45465-9_11"
  }
]
 

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-45465-9_11'

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-45465-9_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45465-9_11'

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-45465-9_11'


 

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

137 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45465-9_11 schema:about anzsrc-for:18
2 anzsrc-for:1801
3 schema:author Nb2270e2e31c548a1a885c0c72a1adf53
4 schema:datePublished 2002-06-25
5 schema:datePublishedReg 2002-06-25
6 schema:description We propose a plausible explanation of the power law distributions of degrees observed in the graphs arising in the Internet topology [Faloutsos, Faloutsos, and Faloutsos, SIGCOMM 1999] based on a toy model of Internet growth in which two objectives are optimized simultaneously: “last mile” connection costs, and transmission delays measured in hops. We also point out a similar phenomenon, anticipated in [Carlson and Doyle, Physics Review E 1999], in the distribution of file sizes. Our results seem to suggest that power laws tend to arise as a result of complex, multi-objective optimization.
7 schema:editor N19cf6df8fcf74fc0b834071aa32f1236
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nae5117aabe30475b9c3e7b9d16a82e92
12 schema:keywords Internet
13 Internet growth
14 Internet topology
15 Optimized Trade-Offs
16 Trade-Offs
17 connection cost
18 cost
19 degree
20 delay
21 distribution
22 explanation
23 file size
24 graph
25 growth
26 hop
27 last mile
28 law
29 law distribution
30 miles
31 model
32 multi-objective optimization
33 new paradigm
34 objective
35 optimization
36 paradigm
37 phenomenon
38 plausible explanation
39 power law
40 power law distribution
41 results
42 similar phenomenon
43 size
44 topology
45 toy model
46 transmission delay
47 schema:name Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet
48 schema:pagination 110-122
49 schema:productId N4430d3bdd10e4416b3bc41722368af97
50 N85cac1c7c809494aa5d702ac7a6084c3
51 schema:publisher N8624a1c6938e4e11b8ed70a00d28da30
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024402121
53 https://doi.org/10.1007/3-540-45465-9_11
54 schema:sdDatePublished 2021-12-01T20:02
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher N82e35b8e1560431ab6f2e66df4d1cfd0
57 schema:url https://doi.org/10.1007/3-540-45465-9_11
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N05d6a03944a742b9a62e97917fec908b schema:familyName Triguero
62 schema:givenName Francisco
63 rdf:type schema:Person
64 N0ea27cbe08644b32a802abe79e464beb schema:familyName Eidenbenz
65 schema:givenName Stephan
66 rdf:type schema:Person
67 N19cf6df8fcf74fc0b834071aa32f1236 rdf:first N862dc57e212c4f439411aebf2833c92d
68 rdf:rest Nad3bb5787c5442a694d3b654f9bffd76
69 N26b1cf35de6b4b2ca948610f6f135e86 schema:familyName Conejo
70 schema:givenName Ricardo
71 rdf:type schema:Person
72 N275a343107d44a4fb500736952d7cc99 schema:familyName Morales
73 schema:givenName Rafael
74 rdf:type schema:Person
75 N4430d3bdd10e4416b3bc41722368af97 schema:name dimensions_id
76 schema:value pub.1024402121
77 rdf:type schema:PropertyValue
78 N7d3eb615a68741808660c0eaf1b1401e rdf:first sg:person.013233165465.63
79 rdf:rest rdf:nil
80 N82e35b8e1560431ab6f2e66df4d1cfd0 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 N85cac1c7c809494aa5d702ac7a6084c3 schema:name doi
83 schema:value 10.1007/3-540-45465-9_11
84 rdf:type schema:PropertyValue
85 N8624a1c6938e4e11b8ed70a00d28da30 schema:name Springer Nature
86 rdf:type schema:Organisation
87 N862dc57e212c4f439411aebf2833c92d schema:familyName Widmayer
88 schema:givenName Peter
89 rdf:type schema:Person
90 N893ce51c7a3d4e40a5e9f85c7959a3fc rdf:first Ne2beefbe89bc431c807d65ad83ece5ce
91 rdf:rest rdf:nil
92 Nad3bb5787c5442a694d3b654f9bffd76 rdf:first N0ea27cbe08644b32a802abe79e464beb
93 rdf:rest Nf11dbb40904745a38b5f02b03abc68b6
94 Nae5117aabe30475b9c3e7b9d16a82e92 schema:isbn 978-3-540-43864-9
95 978-3-540-45465-6
96 schema:name Automata, Languages and Programming
97 rdf:type schema:Book
98 Nb2270e2e31c548a1a885c0c72a1adf53 rdf:first sg:person.07731456073.04
99 rdf:rest Nd61668736d1f4e0fb9934caa32e0184c
100 Nd61668736d1f4e0fb9934caa32e0184c rdf:first sg:person.016555647611.20
101 rdf:rest N7d3eb615a68741808660c0eaf1b1401e
102 Nd85a50fedfd6434988eb348b2dfcb4aa rdf:first N26b1cf35de6b4b2ca948610f6f135e86
103 rdf:rest N893ce51c7a3d4e40a5e9f85c7959a3fc
104 Ne2beefbe89bc431c807d65ad83ece5ce schema:familyName Hennessy
105 schema:givenName Matthew
106 rdf:type schema:Person
107 Nedff38b7f6754ca4a609543429848453 rdf:first N275a343107d44a4fb500736952d7cc99
108 rdf:rest Nd85a50fedfd6434988eb348b2dfcb4aa
109 Nf11dbb40904745a38b5f02b03abc68b6 rdf:first N05d6a03944a742b9a62e97917fec908b
110 rdf:rest Nedff38b7f6754ca4a609543429848453
111 anzsrc-for:18 schema:inDefinedTermSet anzsrc-for:
112 schema:name Law and Legal Studies
113 rdf:type schema:DefinedTerm
114 anzsrc-for:1801 schema:inDefinedTermSet anzsrc-for:
115 schema:name Law
116 rdf:type schema:DefinedTerm
117 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
118 schema:familyName Papadimitriou
119 schema:givenName Christos H.
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
121 rdf:type schema:Person
122 sg:person.016555647611.20 schema:affiliation grid-institutes:grid.19006.3e
123 schema:familyName Koutsoupias
124 schema:givenName Elias
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016555647611.20
126 rdf:type schema:Person
127 sg:person.07731456073.04 schema:affiliation grid-institutes:grid.47840.3f
128 schema:familyName Fabrikant
129 schema:givenName Alex
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731456073.04
131 rdf:type schema:Person
132 grid-institutes:grid.19006.3e schema:alternateName Computer Science Department, University of Athens and UCLA, 3731 Boelter Hall, 90095, Los Angeles, CA, USA
133 schema:name Computer Science Department, University of Athens and UCLA, 3731 Boelter Hall, 90095, Los Angeles, CA, USA
134 rdf:type schema:Organization
135 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA
136 schema:name Computer Science Division, University of California at Berkeley, Soda Hall 689, 94720, Berkeley, CA, USA
137 rdf:type schema:Organization
 




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


...