Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
type: Item
instance of: scholarly article
title: Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
zbMATH Open document ID: 0932.68005
published in: Combinatorica
publication date: 2000-02-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68M07
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68M10
zbMATH DE Number: 1404392
zbMATH Keywords: scheduling
zbMATH Keywords: computer networks
zbMATH Keywords: computer architectures
zbMATH Keywords: combinatorial probability
author: Tom Leighton
author: Bruce M. Maggs
author: Andrea Richa
MaRDI profile type: Publication
full work available at URL: s004930050061
OpenAlex ID: W3015891365
DOI: 10.1007/S004930050061
description: scientific article; zbMATH DE number 1404392