Vi anser att problemet med online paket schemaläggning i Kombinerade Input och Output Queued (CIOQ) och buffrade crossbar switchar. I de allmänt använda CIOQ-omkopplarna placeras paketbuffertar (queues) vid både ingångs- och utgångsportar. En N × N CIOQ-omkopplare har N-inmatningsportar och N-utmatningsportar, där varje ingångsport är utrustad med N-köer, som var och en motsvarar en utgångsport, och varje utgångsport är utrustad med endast en kö. I varje steg kan godtyckligt många paket komma fram till varje ingångsport, och endast ett paket kan överföras från varje utgångsport. Packets överförs från köerna för inmatningsportar till köerna för utgångsportar via den interna strukturen. Buffrade crossbar switchar följer en liknande design, men är utrustade med ytterligare buffertar i sitt inre tyg. I båda modellerna är vårt mål att maximera antalet eller, om paketen har vikter, den totala vikten av överförda paket. Vårt huvudmål är att ta fram online-algoritmer som är både konkurrenskraftiga och effektiva. Vi förbättrar de tidigare kända resultaten för båda switchmodellerna, både för oviktade och viktade paket. För oviktade paket ger Kesselman och Rosén (J. Algorithms '06) en onlinealgoritm som är 3-kompetitiv för CIOQ-brytare. Vi ger en snabbare, mer praktisk algoritm som uppnår samma konkurrensförhållande. I den buffrade crossbar modellen visar vi också 3-konkurrenskraft, vilket förbättrar den tidigare kända kvoten på 4. För viktade paket ger vi 5.83- och 14.83-kompetitiva algoritmer med en elegant analys för CIOQ respektive buffrade crossbar switchar. Detta förbättras med de tidigare kända nyckeltalen 6 och 16.24.
De för närvarande bästa resultaten i denna riktning tillhandahölls av Al-Bawani et al. REF, som presenterade en snabbare 3-konkurrenskraftig algoritm för enhetliga paket, en 5.83-konkurrenskraftig algoritm för CIOQ switch, och en 14.83-konkurrenskraftig algoritm för en buffrad crossbar switch.
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches
{'venue': "SPAA '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}