Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules (Q1964594)

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.