Agrégation de ressources avec contrainte de distance : applications aux plateformes de grande échelle, Resource clustering with distance constraint : applications to large scale platforms

Hubert Larchevêque

Description

Sous la direction de Olivier Beaumont, Nicolas Bonichon, Philippe Duchon
Thèse soutenue le 27 septembre 2010: Bordeaux 1
Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans plusieurs espaces métriques spécifiques, et, en particulier, ceux générés par certains de ces outils, comme Vivaldi et Sequoia.
-Bin packing
-Bin covering
-Augmentation de ressources
-Algorithme d'approximation
-Réseaux de grande échelle
-Algorithme distribué
-Plongement d'Internet
During this Ph.D we introduced Bin Covering under Distance Constraint (BCCD in French) and Bin Packing under Distance Constraint (BPCD in French). Those two problems find their applications in the context of large scale networks, like Internet. We studied those problems in general metric spaces, and proved that using resource augmentation is mandatory. Resource augmentation allows to build algorithms working on solutions with less constraints than the optimal solution to which it is compared to. We found interesting approximations algorithms using this relaxation, and proved the necessity of this resource augmentation. However many tools are used to embed large networks we are interested in in specific metric spaces. Thus we studied those problems in different specific metric spaces, in particular those generated by the use of Vivaldi and Sequoia, two of those tools.
-Bin Packing
-Bin covering
-Resource augmentation
-Distributed algorithms
-Probabilistic data structures
-Large scale networks
-Embedding of the Internet
Source: http://www.theses.fr/2010BOR14067/document

Sujets

• Algorithme d'approximation

Informations

• Publié par: Thesee
• Nombre de lectures: 21
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

oN
.DireLad'ordreBenoit:vis4067d'examenTH?SEorteurPR?SENT?EBeaumon?.L'UNIVERSIT?:DEanBORDEA:UXJuryIault?COLE.DOCTORALETh?seDEPhilippMA2010TH?MArappTIQUESLaforestETaultD'INFlaORMAos?eTIQUEtPtarLaforestHubLaertorteurLarc.hevExaminateur?queDirecteurPOURBonicOBTENIRdeLEDucGRADEdeDEaDOCTEURdesSP?CIALIT?orteurs:ChristianINFChristianORvMADevTIQUEtAgr?gationcommissiondcompederessourcesLaurenaViennotvPr?sidenecduconChristiantrainRappteChristiandevdistanceRapp:Anneapplications.aux.plateformes.deOliviergrandet?cdehelle.NicolasSoutenhonuecteurleTh?se:e27honSeptemDirecteurbreTh?se2010Apr?sparvienneiiiquiRemerciemeneutsmemMestspremierstroisremerciemenentsautreironsatens?e?(ouil'attenpristionmesdemoi.mesetdeuirecteursparendeleth?sed:auOliviert,Beaumonpassaget,ArthNicolasailler.Bonicauhond'?eteuPhiliptpAnne-Laureem'onDuceilhond?ma(l'ordre?nedecomptedepase!).oirJ'ai?galemeneersonnesuergbeteaucoupRomain,delescanihancekdevpplaisirouvtoutesoirmabde?n?cierdansdleur'unes'esttelleautrescompl?men?tarit?,ercie?delaaussifoisersonnsciend'unetiqueth?se.maisRivi?re,aussimehnumaine.aIlseur,ong?n?ralementccquehacunisupm'appMerciorterusunmessoutienfaitdi?renailleurs,t,ourdeslesquellesouvtroiserturesKipu,etorterdesfoireusesid?esGoulvdi?renFlorian,tes,maisethsurfersdescofa?onshabitatdivPersesetetSarthouvquiari?eseaucoupdetrad?monjetrerpl'inexactitudetdesupreuvauestroisqueco-bureauxjeb?timenleuretpropeosais.DamienJeundqueovuRobin,temainqueJenomtbrered'?tudianFtsparticulier,aitylalescshaidaountceclindeAba?n?cierpatienced'unlestriohes,aussiqueecace?danssimiler.leusrfr?re,encadremenett.maJepaslesherremercieoirpfaisourvcettequecethancequequ'ilsfaismmes'vod'anmercitparenoert.vJed?placemensouhaitePeunenuesuitelesremerciervsinc?remenvtdeChristian?LaforestduetonChsristianth?oriesLaexpvJohan,ault,C?line,pLaetitia,ourEmmanleurtephen,relecture?aattenttivuesquatteursdeauronmontribu?manerustcrr?re,riatrict.ChervJeetsouhaiteur?galemenatecadresserj'aimesbremerciemendets??vAnneEnnBenremercieolesiersonnestonpcrois?ourroatevLaBRIoircoursaccept?cesdeans,faireancienspartieexil?sdelemontjuryc?t?detouteth?se,?quip?,LaurenparticuliertquiViennotattard?ppourplusalesvaoirecaccept?Allezd'enc'estassurertoilatenanpr?sidence,!etremglobalemen?galementles?bl'ensemsblel'AdesoDIB,memenbresmaisduCathjuryRoubineaudetoutesmapth?seepquiourtleurs?questionsfa?onquid'uneondurantcetter?vUn?l?d'ol'in?t?r?tlicequ'ilsquiontoujourstlapdeor??xpliquerrt?m?mes?rcmsaonstrajevjamaisail.lesJestiensMerci?maremercierol'ensemmonblemesdestsmemplusbrestdefamille,l'?quipneetropC?page,herctr?s?dvispceoniblejeetmaisasavoecrquijeilfaisestdetr?senserfacilejd'alevbien.oir?desparendiscussionsd'?trescienentiquesetinvt?ressancohabit?,tes,?et,grandsentsparticulier,'aLioneloirEyraud-Dubleois,tat.varecj'aiquipj'ai?mtrapvtoutesaill?pauacoursecdej'aima?cuth?se.coursJecesremercieann?estoutesl'AublesepChatersonnesquiatv?ecuppqmesufumeusesimesj'ai?riencespu:traPierre-LaurenvGregoire,aillJulie,eren,dansBaturan,leJulien,cadreuelle,deSmesLe?laenseignementoutts!),??galemenl'Univtousersit?codecBordeaux,etNicolasdelequipremier,tmaisnaussi,?enmtrenotreautres,duranFcesr?d?riqueann?es.CaersivunivEnn,l'apaour!),nirdansenparticuliermvusique,usicalemenjeenseraiind?ninnimenAutfanfare,reconnaissanAtt?trac?elascienGrassetrottinetteBandeacceptedepm'asonvtocoiderdefaittiensd?couvrirreunquimondeetparall?lesuiviquisinptraermetdeuxdt,eetlaisst,eC?cile,rfolies'expriunemallererandestidiablemen?ancr?sesmonquieur.n'seinocetnerstlapasjeveno?cationmercier?dam,fairem'yaamen?vdonancerj'ailalarecoiehercueusehe?!vEllcesemondes,metiquemenfutmn?cessaire,tsalutaireenet(zeugmatiquementr?sm?meenricethissanquite,maetetsesfaitmemforcebourresdehautsvent.couleursnamelyvoAgr?gationBindekle.ressourcesd'Inatheirvtheectoconnettrainthitendethosedistanceallo:approapplicationsatauxrplateformesappdeugrandeapplications?cducedhelle.tsR?sum?(BPCD:likDuranealedtorkcetteourth?se,enousaugmenaerevwonsspaces.ingeneratedtroBinduittation,lesInprobl?mes?cdewithBinplatforms.Cowvproblems,eringunderarencvunderech).Conscaletrainternet.temdeimpDistanceh(BCCD)resourceetbdeeareBinbPthatacarekingorkainvngecyConedtrainetespdeofDistanceSequoia.(BPCD),BinquimtrouvdataenbtplongemenleurdeapplicationplongemendansResourcelesconstrainr?seauxlarged:ePh.grandein?cwhelle,ectivtelvInCon-ternet.inL'?tudeanddeaccesConstrainprobl?mesFqueproblemsnousineewctutheostudyninsspacesdansitdestoespacesinm?triquesgeneralquelconquesusmon-tation,tresolutionsqu'iloneesttoimpconstrainedossiblesolutiondeto.travvinaillerresults,dansusingunthoseteltocadrethissanseainvolsoirbrecoursscale?aimeddapplicationseellletri'augmeusnotationindemetricressources,yuntoproaldic?d?ordsqacuviximationpresourceermetalgorithms,d'?lablargeorerorks,desofalgorithmeseconstruisand'Intxdesgrandesoluhelle,tionstmoinsternet.conclusteringtraindistancetest:quetolascalesolutionAbstractoptimaleDuring?slaquelleD.ellesesontrottcomoprespar?elyesCo.eringEnDistanceplstrainus(BCCDdFeh)r?sulBitaPtskingd'apDistance-tsproinximationrencinBotht?ressanndts,applicationsnouslargeprouvnetonorks,selaIndicult?Thedeofcesproblemsprobl?mesgeneralsietriccerevprothatc?d?isn'estossiblepaswutilis?.rkPsucaraailleurs,framewdewithningoaugmenmthatbreuxwsoutilsbuiltonytofpalgorithmsourboblessjectifthandeoptimalplongertheylescomparedgraWnprodser?seauxothquiterestingnximationousandinwithoutt?reresourcestationsenproblemtharddanstacdesInespaceswm?triqueswbienwd?crits.alsoNousterestedatovaimingonsemalorseddi?largetunetdi?orksnosbprobl?mesourdansinleswespacesdescribm?triquesmg?n?r?scparThcertainswdstudiedeucesproblemsoutils,somecommeecicVivspaces,aldibetsomeSequoia.thoseMotsols,cl?sViv:andBinKeywP:acPking,king,BinCoCoering,vroering,algorithalgorithmess,d'approaugmenximation,distributedaugmenprobabilistictationstructures,descaleressources,walgo-emrithmeseddingdistribu?s,thestructureterndet.donn?estprobabiliste,ternet.r?seaviK
.1traIn.troBPCDduction.1.1.1.Conestexte.et2.1.2Motiv.ations............et.......P.......Notations.......Comparaison.....vii...2.1.1.li?s............1161.2BQuelques.d?nitions.d'ordre.g?n?ralD?nition...............2.2.3.a.....di?ren.de.Quelques...............du.v3.1.2.1.NP-Dicult?-F.acteur.d'appro.ximation..................De.cking...............173probl?me1.2.2auxEspaces.M?triques......17...................en.-cen.ec.......21.v.probl.placemen.eurs.23.suppl?men........6.1.2.3.Mo.d?le.d'algorithmique.di.stribu?e......15.D?nition.probl?me.tra.aux...................15.Notations....7.1.3.Con.tributions.d.e.cette.th?se................2.2.Bin.a.?.PCD.............................2.2.19duIetInvtli?sro.duction.de.con.train.te.de.distance.?.deux2.2.2probl?mes.clas.siques,.le.Bin.Co.v.ering.et.le.Bin.P.ac.kin.g.13.2.Bin19CoLienveringtre/etPlanBintrePvacapacit?scking.a.v.ec.Con.train.te.de2.2.4Daiecsttsa?mncede15t2.1servDe.Bin.Co2.3veringnotations?tairesBCCD......................29..(7=3; 2)
K
Tuusniformes......sur.........ximation...3.5.1.ersions.....?ciques...et...3.4.2.......ec.BPCD.....v.......m?triques.de..30.2.5tConclusion.partielle......e.....te.....des.-cen...ondance.....p.....Cons?quences.....partielle.........x.e.t?.PCD...Inappro..31.3.Tr?sultatsra.v.aux.a.v.ec.augmen.tation.deetressourcesfacteurdans.des.espaces.m?triques3.4.3g?n?rauxv33de3.1.In.tro.duction.du3.5conceptltatsd'augmenourtationade.ressources..de.v.........3.5.2.les.........6633our3.2nonInappro.ximabilit?.en.d?pit3.6de.l'utilisation.d'augmen.tation.de.ressources......I36v3.2.1desInappro69ximabilit?m?triquesde4.1BCCDinappro.et.......72.de.............les.d'Epstein.Levin................36.3.2.2.Inappro.ximabilit?.de.BPCD..49.Algorithme.preuv.du.d'appro.............52.Note.la.arian.uniforme.BPCD............38.3.3.(2/5,4)-algorithme60d'approCons?quencesximationr?sucenobtentralis?ppletesourtreBCCDv.capacit?s.....61.Th?or?me.corresp.a.ec......40.3.3.1.Algorithme.et.preuv.e61duCons?quencesfacteurourd'approvximationuniformes.................3.5.3.p.les.ersions40uniformes3.3.2.Augmen.tation.de.ressources.sur.le66pConclusionoids.des.group.es.....................45.3.4.Un67arianIVra2.4auPlandansviiiespaces4particuliers?espaRestriction-algorithmedesd'approcximationspspour71BPCDNP-dicul.et.ximabilit?.BCCD.B...............4.1.1.ximabilit?.BCCD48.3.4.1.Outils.p.our.la.preuv.e.du.facteur.d'appro.ximation72utilisanL1
D(1=3; 4) R
L1
(2=5; 4)
(1=3; 4)
....i.auteur.115........76.4.2123BCCDendans.le.plan......en.....d?l...4.4.....4.4.1...1...tre.Ev...BCCD...............de.......124.du.un76.4.2.1.Un.algorithme.d'appronotationsximation.sans.augmen.tationjorationde.ressources.p105ourskip-graphsBCCD..tale...............4.6.dans...un.............ers.ternet.des.d'In...i...........de...san......77.4.2.2.D?tection.d'un.group.e.vd?lesalide.en.temps.p.olynomial......4.4.2.la.skip-list.........Lien.al?atoires79.4.2.3.Cons?quence107dansexple.plan.m.uni.de.la.norme109.un..,.sans.augmen.tation.de.ressources....sans.de.plan.....BPCD...........................5.utilisa.sur.5.1.a.de.du.......Viv..84.4.2.4.A.v.ec.augmen.ta.ti.o.n100deAm?liorationressources,l'ecacit?....d'approet-algorithmeuneximationnutili-otrmeskip-graphquelconque.............84.4.3.Un...........-algorithme.d'appro102ximationModistribu?etp.our.BCCD.dans.....m.uni.de.la.norme...BPCD....03.Ma.de.h.d'une...................4.4.3.en.skip-lists.et.al?atoires.........4.4.4.aluation.?rimen..............86.4.3.1.Structurer.nos.?l?men.ts..4.5.dans.arbre...............................110.BPCD.augm.tation.ressources.le.euclidien..87.4.3.2.Une.adaptation4.7distribu?edansduarbrede.ximabilit?.Inappro.4.1.2.ix.........4.8.partielle.....-algorithme.d'appro.ximation118.Conclusion..92.4.3.3.Analyse.de.complexit?......................120.V.une.t.on.In