Effektiv drift av trådlösa nätverk och switchar kräver att man använder enkla schemaläggningsalgoritmer. I allmänhet, enkla giriga algoritmer (känd som Greedy Maximal Scheduling -GMS) garanteras att uppnå endast en bråkdel av den maximala möjliga genomströmning. Det visades nyligen att i nätverk där de lokala poolningsvillkoren är uppfyllda uppnår GMS 100 % genomströmning. I nätverk där de lokala poolningsvillkoren råder uppnår GMS dessutom genomströmningen på σ %. I detta utdragna abstract karakteriserar vi alla nätverksdiagram i vilka lokal poolning håller under primära interferensbegränsningar. Vi visar sedan att i alla bipartite grafer (dvs. input-queued switchs) av storlek upp till 7 × n, GMS garanteras att uppnå 66% genomströmning, vilket förbättrar på den tidigare kända 50% lägre gränsen. Slutligen studerar vi GMS prestanda i interferensdiagram och visar att dess prestanda i vissa specifika topologier kan vara mycket dålig. Sammantaget visar vi att med hjälp av grafteoretiska tekniker kan avsevärt bidra till vår förståelse av giriga schemaläggningsalgoritmer. Bevisen för resultaten har utelämnats för korthet och kan hittas i [1].
Författarna i REF karakteriserar exakt, med hjälp av grafteoretiska metoder, uppsättningen nätverksgrafer (med endast de primära interferensbegränsningarna) där GMS är optimal (LPF = 1).
Analyzing the performance of greedy maximal scheduling via local pooling and graph theory
{'venue': "S3 '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}