Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules (Q1964594)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules |
scientific article |
Statements
Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules (English)
0 references
21 February 2000
0 references
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.
0 references
scheduling
0 references
computer networks
0 references
computer architectures
0 references
combinatorial probability
0 references