Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules (Q1964594): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Leighton, Tom / rank | |||
Property / author | |||
Property / author: Bruce M. Maggs / rank | |||
Property / author | |||
Property / author: Andréa W. Richa / rank | |||
Property / author | |||
Property / author: Leighton, Tom / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Bruce M. Maggs / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Andréa W. Richa / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004930050061 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3015891365 / rank | |||
Normal rank |
Latest revision as of 22:37, 19 March 2024
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