An Improved Algorithm for CIOQ Switches

摘要: The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, most general model that investigated is standard CIOQ (Combined Input and Output Queued) switch architecture with internal fabric speedup S ≥ 1. switches, comprise backbone packet routing networks, are N × switches controlled by a policy incorporates two components: admission control scheduling. An strategy essential to determine packets stored FIFO queues input output ports, while scheduling conducts transfer fabric, from ports ports. online total was Kesselman Rosen [12]. They presented different algorithms for achieve non-constant ratios (linear either or number distinct values logarithmic value range). We introduce first constant-competitive algorithm case problem, arbitrary values. Specifically, our 9.47-competitive, also simple easy implement.