Costly circuits, submodular schedules and approximate Carathéodory Theorems View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-09-21

AUTHORS

Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, Pramod Viswanath

ABSTRACT

Hybrid switching—in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch—is a promising alternative to interconnect servers in today’s large-scale data centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly optimal scheduling algorithm that trades off reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution toward a constructive version of Carathéodory’s Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms the state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi-hop routing, distinct from the well-known load balancing effects. More... »

PAGES

311-347

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s11134-017-9546-x

DOI

http://dx.doi.org/10.1007/s11134-017-9546-x

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Illinois Urbana-Champaign, Champaign, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "University of Illinois Urbana-Champaign, Champaign, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bojja Venkatakrishnan", 
        "givenName": "Shaileshh", 
        "id": "sg:person.010710344773.85", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010710344773.85"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Alizadeh", 
        "givenName": "Mohammad", 
        "id": "sg:person.011753217656.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011753217656.86"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Illinois Urbana-Champaign, Champaign, IL, USA", 
          "id": "http://www.grid.ac/institutes/grid.35403.31", 
          "name": [
            "University of Illinois Urbana-Champaign, Champaign, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Viswanath", 
        "givenName": "Pramod", 
        "id": "sg:person.015161043400.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015161043400.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-31594-7_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028934993", 
          "https://doi.org/10.1007/978-3-642-31594-7_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1011280023547", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016854006", 
          "https://doi.org/10.1023/a:1011280023547"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01581104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003225806", 
          "https://doi.org/10.1007/bf01581104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579273", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010850152", 
          "https://doi.org/10.1007/bf02579273"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-09-21", 
    "datePublishedReg": "2017-09-21", 
    "description": "Hybrid switching\u2014in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch\u2014is a promising alternative to interconnect servers in today\u2019s large-scale data centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly optimal scheduling algorithm that trades off reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution toward a constructive version of Carath\u00e9odory\u2019s Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms the state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi-hop routing, distinct from the well-known load balancing effects.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s11134-017-9546-x", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.6937279", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3580067", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1048269", 
        "issn": [
          "0257-0130", 
          "1572-9443"
        ], 
        "name": "Queueing Systems", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "88"
      }
    ], 
    "keywords": [
      "Carath\u00e9odory theorem", 
      "circuit switches", 
      "multi-hop routing", 
      "high link rates", 
      "large-scale data centers", 
      "optimal scheduling algorithm", 
      "approximate solution", 
      "Birkhoff polytope", 
      "submodular optimization", 
      "link rate", 
      "indirect routing", 
      "benefits of reconfiguration", 
      "packet switch", 
      "constructive version", 
      "hybrid switching", 
      "traffic demand", 
      "theorem", 
      "optimal schedule", 
      "demand settings", 
      "reconfiguration delay", 
      "scheduling algorithm", 
      "routing", 
      "promising alternative", 
      "algorithm", 
      "reconfiguration cost", 
      "polytope", 
      "data centers", 
      "switch", 
      "scheduling", 
      "optimization", 
      "circuit", 
      "solution", 
      "server", 
      "strong connection", 
      "connectivity", 
      "switching", 
      "delay", 
      "reconfiguration", 
      "performance", 
      "version", 
      "phenomenon", 
      "schedule", 
      "connection", 
      "idea", 
      "power", 
      "demand", 
      "cost", 
      "state", 
      "paper", 
      "conjunction", 
      "alternative", 
      "variety", 
      "load", 
      "rate", 
      "art", 
      "effect", 
      "center", 
      "setting", 
      "benefits"
    ], 
    "name": "Costly circuits, submodular schedules and approximate Carath\u00e9odory Theorems", 
    "pagination": "311-347", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1091892284"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s11134-017-9546-x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s11134-017-9546-x", 
      "https://app.dimensions.ai/details/publication/pub.1091892284"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-08-04T17:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_726.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s11134-017-9546-x"
  }
]
 

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/s11134-017-9546-x'

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/s11134-017-9546-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11134-017-9546-x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11134-017-9546-x'


 

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

161 TRIPLES      21 PREDICATES      89 URIs      75 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s11134-017-9546-x schema:about anzsrc-for:01
2 anzsrc-for:0102
3 anzsrc-for:0103
4 anzsrc-for:0104
5 schema:author N97e6e13535f84894bce33d985d7a0937
6 schema:citation sg:pub.10.1007/978-3-642-31594-7_4
7 sg:pub.10.1007/bf01581104
8 sg:pub.10.1007/bf02579273
9 sg:pub.10.1023/a:1011280023547
10 schema:datePublished 2017-09-21
11 schema:datePublishedReg 2017-09-21
12 schema:description Hybrid switching—in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch—is a promising alternative to interconnect servers in today’s large-scale data centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly optimal scheduling algorithm that trades off reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution toward a constructive version of Carathéodory’s Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms the state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi-hop routing, distinct from the well-known load balancing effects.
13 schema:genre article
14 schema:isAccessibleForFree true
15 schema:isPartOf N11dfe5c5678344c9a0d75615c92c6b11
16 N81ff63df306c4aacbfcfc18b42b984b5
17 sg:journal.1048269
18 schema:keywords Birkhoff polytope
19 Carathéodory theorem
20 algorithm
21 alternative
22 approximate solution
23 art
24 benefits
25 benefits of reconfiguration
26 center
27 circuit
28 circuit switches
29 conjunction
30 connection
31 connectivity
32 constructive version
33 cost
34 data centers
35 delay
36 demand
37 demand settings
38 effect
39 high link rates
40 hybrid switching
41 idea
42 indirect routing
43 large-scale data centers
44 link rate
45 load
46 multi-hop routing
47 optimal schedule
48 optimal scheduling algorithm
49 optimization
50 packet switch
51 paper
52 performance
53 phenomenon
54 polytope
55 power
56 promising alternative
57 rate
58 reconfiguration
59 reconfiguration cost
60 reconfiguration delay
61 routing
62 schedule
63 scheduling
64 scheduling algorithm
65 server
66 setting
67 solution
68 state
69 strong connection
70 submodular optimization
71 switch
72 switching
73 theorem
74 traffic demand
75 variety
76 version
77 schema:name Costly circuits, submodular schedules and approximate Carathéodory Theorems
78 schema:pagination 311-347
79 schema:productId N42863fcde335410cbbf551b5ea19007e
80 Ne5e2db2291a947459fa5b52e7ed15935
81 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091892284
82 https://doi.org/10.1007/s11134-017-9546-x
83 schema:sdDatePublished 2022-08-04T17:05
84 schema:sdLicense https://scigraph.springernature.com/explorer/license/
85 schema:sdPublisher N5891acf1f6c347c4b5e6778354cbfe32
86 schema:url https://doi.org/10.1007/s11134-017-9546-x
87 sgo:license sg:explorer/license/
88 sgo:sdDataset articles
89 rdf:type schema:ScholarlyArticle
90 N11dfe5c5678344c9a0d75615c92c6b11 schema:issueNumber 3-4
91 rdf:type schema:PublicationIssue
92 N22a0c0367e14464a9a8d061c75a9a87c rdf:first sg:person.011753217656.86
93 rdf:rest Nafa521e327a34a9a9b8cde628a3fbbe2
94 N42863fcde335410cbbf551b5ea19007e schema:name doi
95 schema:value 10.1007/s11134-017-9546-x
96 rdf:type schema:PropertyValue
97 N5891acf1f6c347c4b5e6778354cbfe32 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 N81ff63df306c4aacbfcfc18b42b984b5 schema:volumeNumber 88
100 rdf:type schema:PublicationVolume
101 N97e6e13535f84894bce33d985d7a0937 rdf:first sg:person.010710344773.85
102 rdf:rest N22a0c0367e14464a9a8d061c75a9a87c
103 Nafa521e327a34a9a9b8cde628a3fbbe2 rdf:first sg:person.015161043400.28
104 rdf:rest rdf:nil
105 Ne5e2db2291a947459fa5b52e7ed15935 schema:name dimensions_id
106 schema:value pub.1091892284
107 rdf:type schema:PropertyValue
108 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
109 schema:name Mathematical Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
112 schema:name Applied Mathematics
113 rdf:type schema:DefinedTerm
114 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
115 schema:name Numerical and Computational Mathematics
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
118 schema:name Statistics
119 rdf:type schema:DefinedTerm
120 sg:grant.3580067 http://pending.schema.org/fundedItem sg:pub.10.1007/s11134-017-9546-x
121 rdf:type schema:MonetaryGrant
122 sg:grant.6937279 http://pending.schema.org/fundedItem sg:pub.10.1007/s11134-017-9546-x
123 rdf:type schema:MonetaryGrant
124 sg:journal.1048269 schema:issn 0257-0130
125 1572-9443
126 schema:name Queueing Systems
127 schema:publisher Springer Nature
128 rdf:type schema:Periodical
129 sg:person.010710344773.85 schema:affiliation grid-institutes:grid.35403.31
130 schema:familyName Bojja Venkatakrishnan
131 schema:givenName Shaileshh
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010710344773.85
133 rdf:type schema:Person
134 sg:person.011753217656.86 schema:affiliation grid-institutes:grid.116068.8
135 schema:familyName Alizadeh
136 schema:givenName Mohammad
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011753217656.86
138 rdf:type schema:Person
139 sg:person.015161043400.28 schema:affiliation grid-institutes:grid.35403.31
140 schema:familyName Viswanath
141 schema:givenName Pramod
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015161043400.28
143 rdf:type schema:Person
144 sg:pub.10.1007/978-3-642-31594-7_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028934993
145 https://doi.org/10.1007/978-3-642-31594-7_4
146 rdf:type schema:CreativeWork
147 sg:pub.10.1007/bf01581104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003225806
148 https://doi.org/10.1007/bf01581104
149 rdf:type schema:CreativeWork
150 sg:pub.10.1007/bf02579273 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010850152
151 https://doi.org/10.1007/bf02579273
152 rdf:type schema:CreativeWork
153 sg:pub.10.1023/a:1011280023547 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016854006
154 https://doi.org/10.1023/a:1011280023547
155 rdf:type schema:CreativeWork
156 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, Cambridge, MA, USA
157 schema:name Massachusetts Institute of Technology, Cambridge, MA, USA
158 rdf:type schema:Organization
159 grid-institutes:grid.35403.31 schema:alternateName University of Illinois Urbana-Champaign, Champaign, IL, USA
160 schema:name University of Illinois Urbana-Champaign, Champaign, IL, USA
161 rdf:type schema:Organization
 




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


...