Ontology type: schema:ScholarlyArticle Open Access: True
2017-09-21
AUTHORSShaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, Pramod Viswanath
ABSTRACTHybrid 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... »
PAGES311-347
http://scigraph.springernature.com/pub.10.1007/s11134-017-9546-x
DOIhttp://dx.doi.org/10.1007/s11134-017-9546-x
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1091892284
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
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