Fast algorithms for finding O(Congestion+Dilation) packet routing schedules
Scheduling of movements of packets whose paths through a network with \(n\) nodes (switches) and \(m\) edges (communication chanels) is considered. Each node serves as the source or destination of a number of packets. The goal is to route the \(N\) packets from their origins to their destinations via a series of synchronized time steps, where at each step at most one packet can traverse each edge and each packet can traverse at most one edge. Timing the movements of the packets along their paths was studied. It was shown how to produce schedules in \(O(m(c+d)(\log\mathcal P)^4(\log\log \mathcal P))\) time with probability at least \(1-1/\mathcal P^\delta\) for any positive constant \(\beta\) (\(\mathcal P\) is the sum of the lengths of the paths). Algorithms for constructing optimal schedules and for reducing the frame size were described.
- Efficient delay routing
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- Adaptive packet routing for bursty adversarial traffic
- Approximation algorithms for shop scheduling problems with minsum objective
- A \(2n-2\) step algorithm for routing in an \(n \times n\) array with constant-size queues
- FIFO and randomized competitive packet routing games
- Scheduling problems over a network of machines
- Direct routing: Algorithms and complexity
- Scheduling on unrelated machines under tree-like precedence constraints
- Online packet-routing in grids with bounded buffers
- Scheduling problems in transportation networks of line topology
- Universal packet routing with arbitrary bandwidths and transit times
- Solving the job-shop scheduling problem optimally by dynamic programming
- On the power of randomization for job shop scheduling withk-units length tasks
- UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS
- Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma
- scientific article; zbMATH DE number 1559580 (Why is no real title available?)
- A packet routing protocol for arbitrary networks
- Scheduling nonuniform traffic in a packet switching system with large propagation delay
- Scheduling problems over network of machines
- Train scheduling on a unidirectional path
- \(O(\log m)\)-approximation for the routing open shop problem
- Oblivious routing for sensor network topologies
- Evaluation of a method for enumerating the most probable packet arrangements
- Time-optimum packet scheduling for many-to-one routing in wireless sensor networks
- A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES
- Bounding Residence Times for Atomic Dynamic Routings
- On the benefit of supporting virtual channels in wormhole routers
- Approximation Algorithms for Generalized Path Scheduling
- Two exact algorithms for the packet scheduling problem
- Near-optimal schedules for simultaneous multicasts
- On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion
- Scheduling trains with small stretch on a unidirectional line
- The impact of local policies on the quality of packet routing in paths, trees, and rings
- Atomic routing games on maximum congestion
This page was built for publication: Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1964594)
