Off-line and on-line call-scheduling in stars and trees
Identifieur interne : 001668 ( Istex/Corpus ); précédent : 001667; suivant : 001669Off-line and on-line call-scheduling in stars and trees
Auteurs : Thomas Erlebach ; Klaus JansenSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1997.
Abstract
Abstract: Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most $$2\frac{2}{3}$$ . In tree networks with n nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5 log n.
Url:
DOI: 10.1007/BFb0024499
Links to Exploration step
ISTEX:862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Off-line and on-line call-scheduling in stars and trees</title><author><name sortKey="Erlebach, Thomas" sort="Erlebach, Thomas" uniqKey="Erlebach T" first="Thomas" last="Erlebach">Thomas Erlebach</name><affiliation><mods:affiliation>Institut für Informatik, TU München, D-80290, München</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: erlebach@informatik.tu-muenchen.de</mods:affiliation></affiliation></author><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><affiliation><mods:affiliation>Fachbereich IV - Mathematik, Universität Trier, Postfach 3825, D-54286, Trier</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jansen@dm3.uni-trier.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45</idno><date when="1997" year="1997">1997</date><idno type="doi">10.1007/BFb0024499</idno><idno type="url">https://api.istex.fr/document/862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001668</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001668</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Off-line and on-line call-scheduling in stars and trees</title><author><name sortKey="Erlebach, Thomas" sort="Erlebach, Thomas" uniqKey="Erlebach T" first="Thomas" last="Erlebach">Thomas Erlebach</name><affiliation><mods:affiliation>Institut für Informatik, TU München, D-80290, München</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: erlebach@informatik.tu-muenchen.de</mods:affiliation></affiliation></author><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><affiliation><mods:affiliation>Fachbereich IV - Mathematik, Universität Trier, Postfach 3825, D-54286, Trier</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: jansen@dm3.uni-trier.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1997</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45</idno><idno type="DOI">10.1007/BFb0024499</idno><idno type="ChapterID">18</idno><idno type="ChapterID">Chap18</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most $$2\frac{2}{3}$$ . In tree networks with n nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5 log n.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Thomas Erlebach</name><affiliations><json:string>Institut für Informatik, TU München, D-80290, München</json:string><json:string>E-mail: erlebach@informatik.tu-muenchen.de</json:string></affiliations></json:item><json:item><name>Klaus Jansen</name><affiliations><json:string>Fachbereich IV - Mathematik, Universität Trier, Postfach 3825, D-54286, Trier</json:string><json:string>E-mail: jansen@dm3.uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most $$2\frac{2}{3}$$ . In tree networks with n nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5 log n.</abstract><qualityIndicators><score>7.1</score><pdfVersion>1.3</pdfVersion><pdfPageSize>440 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1051</abstractCharCount><pdfWordCount>8075</pdfWordCount><pdfCharCount>35272</pdfCharCount><pdfPageCount>15</pdfPageCount><abstractWordCount>175</abstractWordCount></qualityIndicators><title>Off-line and on-line call-scheduling in stars and trees</title><chapterId><json:string>18</json:string><json:string>Chap18</json:string></chapterId><refBibs><json:item><host><author></author><title>are scheduled in time s.:ep ~ -1.) The bandwidths of the calls from (3) scheduled during one of the time steps 0,..., g-1 add up to at most k~__!. Hence, they can be scheduled concurrently with call z. The call with bandwidth</title></host></json:item><json:item><author><json:item><name>Y Aumann</name></json:item><json:item><name>Y Rabani</name></json:item></author><host><pages><last>576</last><first>567</first></pages><author></author><title>Proceedings of the 6th Annual A CM-SfAM Symposium on Discrete Algorithms SODA '95</title><publicationDate>1995</publicationDate></host><title>Improved bounds for all optical routing</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>B Awerbuch</name></json:item><json:item><name>Y Bartal</name></json:item><json:item><name>A Fiat</name></json:item><json:item><name>A Ros~n</name></json:item></author><host><pages><last>320</last><first>312</first></pages><author></author><title>Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms SODA '94</title><publicationDate>1994</publicationDate></host><title>Competitive non-preemptive call control</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>Y Bartal</name></json:item><json:item><name>S Leonardi</name></json:item></author><host><pages><last>526</last><first>516</first></pages><author></author><title>Proceedings of the 24th International Colloquium on Automata, Languages and Programming [CALP '97</title><publicationDate>1997</publicationDate></host><title>On-line routing in all-optical networks</title><publicationDate>1997</publicationDate></json:item><json:item><author><json:item><name>E Coffman</name></json:item><json:item><name>M Jr</name></json:item><json:item><name>D Garey</name></json:item><json:item><name>A Johnson</name></json:item><json:item><name> Lapaugh</name></json:item></author><host><volume>14</volume><pages><last>780</last><first>744</first></pages><issue>3</issue><author></author><title>SIAM J. Comput</title><publicationDate>1985-08</publicationDate></host><title>Scheduling file transfers</title><publicationDate>1985-08</publicationDate></json:item><json:item><author><json:item><name>T Erlebach</name></json:item><json:item><name>K Jansen</name></json:item></author><host><pages><last>32</last><first>13</first></pages><author></author><title>Proceedings of the ~th Parallel Systems and Algorithms Workshop PASA '96</title><publicationDate>1997</publicationDate></host><title>Scheduling of virtual connections in fast networks</title><publicationDate>1997</publicationDate></json:item><json:item><author><json:item><name>T Erlebach</name></json:item><json:item><name>K Jansen</name></json:item></author><host><pages><last>222</last><first>221</first></pages><author></author><title>Proceedings of the 30th Hawaii International Conference on System Sciences HICSS-30</title><publicationDate>1997</publicationDate></host><title>Call scheduling in trees, rings and meshes</title><publicationDate>1997</publicationDate></json:item><json:item><host><author><json:item><name>A Feldmann</name></json:item><json:item><name>B Maggs</name></json:item><json:item><name>J Sgall</name></json:item><json:item><name>D,D Sleator</name></json:item><json:item><name>A Tomkins</name></json:item></author><title>Competitive analysis of call admission algorithms that allow delay</title><publicationDate>1995-01</publicationDate></host></json:item><json:item><host><author><json:item><name>A Feldmann</name></json:item></author><title>On-line call admission for high-speed networks (Ph.D. Thesis)</title><publicationDate>1995-10</publicationDate></host></json:item><json:item><author><json:item><name>R Graham</name></json:item></author><host><volume>17</volume><pages><last>429</last><first>416</first></pages><issue>2</issue><author></author><title>SIAM J. Appl. Math</title><publicationDate>1969-03</publicationDate></host><title>Bounds on multiprocessing timing anomalies</title><publicationDate>1969-03</publicationDate></json:item><json:item><author><json:item><name>R Graham</name></json:item></author><host><pages><last>227</last><first>165</first></pages><author></author><title>Computer and Job-Shop Scheduling Theory</title><publicationDate>1976</publicationDate></host><title>Bounds on the performance of scheduling algorithms</title><publicationDate>1976</publicationDate></json:item><json:item><author><json:item><name>J Hoogeveen</name></json:item><json:item><name>S Van De</name></json:item><json:item><name>B Velde</name></json:item><json:item><name> Veltman</name></json:item></author><host><volume>55</volume><pages><last>272</last><first>259</first></pages><author></author><title>Discrete Appl. Math</title><publicationDate>1994</publicationDate></host><title>Complexity of scheduling multiprocessor tasks with prespecified processor allocations</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>C Kaklamanis</name></json:item><json:item><name>P Persiano</name></json:item><json:item><name>T Erlebach</name></json:item><json:item><name>K Jansen</name></json:item></author><host><pages><last>504</last><first>493</first></pages><author></author><title>Proceedings of the 24th International Colloquium on Automata, Languages and Programming ICALP ~97, LNCS 1256</title><publicationDate>1997</publicationDate></host><title>Constrained bipartite edge coloring with applications to wavelength routing</title><publicationDate>1997</publicationDate></json:item><json:item><author><json:item><name>T Nishizeki</name></json:item><json:item><name>K Kashiwagi</name></json:item></author><host><volume>3</volume><pages><last>410</last><first>391</first></pages><issue>3</issue><author></author><title>SIAM J. Disc. Math</title><publicationDate>1990-08</publicationDate></host><title>On the 1.1 edge-coloring of multigraphs</title><publicationDate>1990-08</publicationDate></json:item><json:item><author><json:item><name>D,B Shmoys</name></json:item><json:item><name>J Wein</name></json:item><json:item><name>D,P Williamson</name></json:item></author><host><pages><last>140</last><first>131</first></pages><author></author><title>Proceedings of the 32nd Annual Symposium on Foundations of Computer Science FOCS '91</title><publicationDate>1991</publicationDate></host><title>Scheduling parallel machines online</title><publicationDate>1991</publicationDate></json:item><json:item><host><author><json:item><name>Atm The</name></json:item><json:item><name> Forum</name></json:item></author><title>Upper Saddle River, NJ. ATM User-Network Interface (UNI) Specification Version 3.1</title><publicationDate>1995</publicationDate></host></json:item><json:item><host><author></author><title>Handbook of Theoretical Computer Science. Volume A: Algorithms and complexity</title><publicationDate>1990</publicationDate></host></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1997</copyrightDate></serie><host><editor><json:item><name>Rolf H. Möhring</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Data Structures</value></json:item><json:item><value>Combinatorics</value></json:item></subject><isbn><json:string>978-3-540-63757-8</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Graph-Theoretic Concepts in Computer Science</title><bookId><json:string>3540637575</json:string></bookId><volume>1335</volume><pages><last>213</last><first>199</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-69643-8</json:string></eisbn><copyrightDate>1997</copyrightDate><doi><json:string>10.1007/BFb0024481</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1997</copyrightDate><doi><json:string>10.1007/BFb0024499</json:string></doi><id>862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45</id><score>0.38293618</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Off-line and on-line call-scheduling in stars and trees</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1997</p></availability><date>1997</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Off-line and on-line call-scheduling in stars and trees</title><author xml:id="author-1"><persName><forename type="first">Thomas</forename><surname>Erlebach</surname></persName><email>erlebach@informatik.tu-muenchen.de</email><affiliation>Institut für Informatik, TU München, D-80290, München</affiliation></author><author xml:id="author-2"><persName><forename type="first">Klaus</forename><surname>Jansen</surname></persName><email>jansen@dm3.uni-trier.de</email><affiliation>Fachbereich IV - Mathematik, Universität Trier, Postfach 3825, D-54286, Trier</affiliation></author></analytic><monogr><title level="m">Graph-Theoretic Concepts in Computer Science</title><title level="m" type="sub">23rd International Workshop, WG'97 Berlin, Germany, June 18–20, 1997 Proceedings</title><idno type="pISBN">978-3-540-63757-8</idno><idno type="eISBN">978-3-540-69643-8</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/BFb0024481</idno><idno type="book-ID">3540637575</idno><idno type="book-title-ID">55826</idno><idno type="book-volume-number">1335</idno><idno type="book-chapter-count">29</idno><editor><persName><forename type="first">Rolf</forename><forename type="first">H.</forename><surname>Möhring</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-17"></date><biblScope unit="volume">1335</biblScope><biblScope unit="page" from="199">199</biblScope><biblScope unit="page" to="213">213</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1997</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45</idno><idno type="DOI">10.1007/BFb0024499</idno><idno type="ChapterID">18</idno><idno type="ChapterID">Chap18</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1997</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most $$2\frac{2}{3}$$ . In tree networks with n nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5 log n.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>I17028</label><label>I16013</label><label>I15017</label><label>M17009</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Discrete Mathematics in Computer Science</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Data Structures</term></item><item><term>Combinatorics</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-17">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540637575</BookID><BookTitle>Graph-Theoretic Concepts in Computer Science</BookTitle><BookSubTitle>23rd International Workshop, WG'97 Berlin, Germany, June 18–20, 1997 Proceedings</BookSubTitle><BookVolumeNumber>1335</BookVolumeNumber><BookDOI>10.1007/BFb0024481</BookDOI><BookTitleID>55826</BookTitleID><BookPrintISBN>978-3-540-63757-8</BookPrintISBN><BookElectronicISBN>978-3-540-69643-8</BookElectronicISBN><BookChapterCount>29</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1997</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I17028" Priority="2" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><BookSubject Code="I16013" Priority="3" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I15017" Priority="4" Type="Secondary">Data Structures</BookSubject><BookSubject Code="M17009" Priority="5" Type="Secondary">Combinatorics</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Rolf</GivenName><GivenName>H.</GivenName><FamilyName>Möhring</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap18" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>18</ChapterID><ChapterDOI>10.1007/BFb0024499</ChapterDOI><ChapterSequenceNumber>18</ChapterSequenceNumber><ChapterTitle Language="En">Off-line and on-line call-scheduling in stars and trees</ChapterTitle><ChapterFirstPage>199</ChapterFirstPage><ChapterLastPage>213</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1997</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>17</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540637575</BookID><BookTitle>Graph-Theoretic Concepts in Computer Science</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Thomas</GivenName><FamilyName>Erlebach</FamilyName></AuthorName><Contact><Email>erlebach@informatik.tu-muenchen.de</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Klaus</GivenName><FamilyName>Jansen</FamilyName></AuthorName><Contact><Email>jansen@dm3.uni-trier.de</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>Institut für Informatik</OrgName><OrgAddress><Street>TU München</Street><Postcode>D-80290</Postcode><City>München</City></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Fachbereich IV - Mathematik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postbox>Postfach 3825</Postbox><Postcode>D-54286</Postcode><City>Trier</City></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most <InlineEquation ID="IE1"><InlineMediaObject><ImageObject FileRef="558_3540637575_Chapter_18_TeX2GIFIE1.gif" Format="GIF" Color="BlackWhite" Type="Linedraw" Rendition="HTML"></ImageObject></InlineMediaObject><EquationSource Format="TEX"> $$2\frac{2}{3}$$ </EquationSource></InlineEquation>. In tree networks with <Emphasis Type="Italic">n</Emphasis> nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5 log <Emphasis Type="Italic">n</Emphasis>.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>Partly supported by German Science Foundation (DFG), Contract: SFB 342 TP A7.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Off-line and on-line call-scheduling in stars and trees</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Off-line and on-line call-scheduling in stars and trees</title></titleInfo><name type="personal"><namePart type="given">Thomas</namePart><namePart type="family">Erlebach</namePart><affiliation>Institut für Informatik, TU München, D-80290, München</affiliation><affiliation>E-mail: erlebach@informatik.tu-muenchen.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Klaus</namePart><namePart type="family">Jansen</namePart><affiliation>Fachbereich IV - Mathematik, Universität Trier, Postfach 3825, D-54286, Trier</affiliation><affiliation>E-mail: jansen@dm3.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-17</dateIssued><copyrightDate encoding="w3cdtf">1997</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: Given a communication network and a set of call requests, the goal is to find a minimum makespan schedule for the calls such that the sum of the bandwidth requirements of simultaneously active calls using the same link does not exceed the capacity of that link. In this paper the call-scheduling problem is studied for star and tree networks. Lower and upper bounds on the worst-case performance of List-Scheduling (LS) and variants of it are obtained for call-scheduling with arbitrary bandwidth requirements and either unit call durations or arbitrary call durations. LS does not require advance knowledge of call durations and, hence, is an on-line algorithm. It has performance ratio (competitive ratio) at most 5 in star networks. A variant of LS for calls with unit durations is shown to have performance ratio at most $$2\frac{2}{3}$$ . In tree networks with n nodes, a variant of LS for calls with unit durations has performance ratio at most 6, and a variant for calls with arbitrary durations has performance ratio at most 5 log n.</abstract><relatedItem type="host"><titleInfo><title>Graph-Theoretic Concepts in Computer Science</title><subTitle>23rd International Workshop, WG'97 Berlin, Germany, June 18–20, 1997 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Rolf</namePart><namePart type="given">H.</namePart><namePart type="family">Möhring</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1997</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic></subject><identifier type="DOI">10.1007/BFb0024481</identifier><identifier type="ISBN">978-3-540-63757-8</identifier><identifier type="eISBN">978-3-540-69643-8</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">55826</identifier><identifier type="BookID">3540637575</identifier><identifier type="BookChapterCount">29</identifier><identifier type="BookVolumeNumber">1335</identifier><part><date>1997</date><detail type="volume"><number>1335</number><caption>vol.</caption></detail><extent unit="pages"><start>199</start><end>213</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1997</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1997</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1997</recordOrigin></recordInfo></relatedItem><identifier type="istex">862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45</identifier><identifier type="DOI">10.1007/BFb0024499</identifier><identifier type="ChapterID">18</identifier><identifier type="ChapterID">Chap18</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1997</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1997</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001668 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001668 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:862EA667E4E0CFDD7611F5197ECB54D8C6C1CC45
|texte= Off-line and on-line call-scheduling in stars and trees
}}
| This area was generated with Dilib version V0.6.31. |  |