Show simple item record

Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory

hal.structure.identifier
dc.contributor.authorZussman, Gil*
hal.structure.identifier
dc.contributor.authorSeymour, Paul*
hal.structure.identifier
dc.contributor.authorZwols, Yori*
hal.structure.identifier
dc.contributor.authorBirand, Berk*
hal.structure.identifier
dc.contributor.authorRies, Bernard*
hal.structure.identifier
dc.contributor.authorChudnovsky, Maria*
dc.date.accessioned2011-04-22T14:32:10Z
dc.date.available2011-04-22T14:32:10Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6029
dc.language.isoenen
dc.subjectGreedy Maximal Schedulingen
dc.subjectGraph Theoryen
dc.subjectLocal Poolingen
dc.subject.ddc511en
dc.titleAnalyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theoryen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherDept. of Electr. Eng., Columbia Univ.;États-Unis
dc.description.abstractenThe main task in analyzing a switching network design (including circuit-, multirate-, and photonic-switching) is to determine the minimum number of some switching components so that the design is non-blocking in some sense (e.g., stridor wide-sense). We show that, in many cases, this task can be accomplished with a simple two-step strategy: (1) formulate a linear program whose optimum value is a bound for the minimum number we are seeking, and (2) specify a solution to the dual program, whose objective value by weak duality immediately yields a sufficient condition for the design to be non-blocking. We illustrate this technique through a variety of examples, ranging from circuit to multirate to photonic switching, from unicast to f-cast and multicast, and from strict- to wide-sense non-blocking. The switching architectures in the examples are of Clos-type and Banyan-type, which are the two most popular architectural choices for designing non-blocking switching networks. To prove the result in the multirate Clos network case, we formulate a new problem called DYNAMIC WEIGHTED EDGE COLORING which generalizes the DYNAMIC BIN PACKING problem. We then design an algorithm with competitive ratio 5.6355 for the problem. The algorithm is analyzed using the linear programming technique. We also show that no algorithm can have competitive ratio better than 4-O (log n/n) for this problem. New lower- and upper-bounds for multirate wide-sense non-blocking Clos networks follow, improving upon a couple of 10-year-old bounds on the same problem.en
dc.identifier.citationpages1-9en
dc.relation.ispartoftitleINFOCOM, 2010 Proceedings IEEEen
dc.relation.ispartofpublnameIEEE Press Booken
dc.relation.ispartofpublcityNew Yorken
dc.relation.ispartofdate2010
dc.relation.isversionofdoi10.1109/INFCOM.2010.5462046
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.ispartofisbn978-1-4244-5838-7en
dc.relation.conftitle29th IEEE International Conference on Computer Communicationsen
dc.relation.confdate2010-03
dc.relation.confcitySan Diegoen
dc.relation.confcountryÉtats-Unisen
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
AnalyzingGMS_Infocom10.pdf
Size:
312.5Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record