Online packet-routing in grids with bounded buffers

DOI10.1007/s00453-016-0177-0zbMath1372.68310arXiv1407.4498OpenAlexW2464743683WikidataQ59528556 ScholiaQ59528556MaRDI QIDQ2408091

Guy Even, Moti Medina

Publication date: 9 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.4498

zbMATH Keywords

online algorithmsadmission controlgrid networkspacket routingbounded buffers

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items

Online packet-routing in grids with bounded buffers, Universal stability in multi-hop radio networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Time-constrained scheduling of weighted packets on trees and meshes
• Scheduling time-constrained communication in linear networks
• On-line routing in all-optical networks
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• The network as a storage device: dynamic routing with bounded buffers
• Online packet-routing in grids with bounded buffers
• Online Primal-Dual Algorithms for Covering and Packing
• An O(logn)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines
• Efficient algorithms for interval graphs and circular-arc graphs
• A Constant Approximation Algorithm for Scheduling Packets on Line Networks
• Probability and Computing
• Algorithms – ESA 2005