Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules | Zendy

Tom Leighton | Zendy; Bruce M. Maggs | Zendy; Andr x E a W. Richa | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules

Author(s) -

Tom Leighton,

Bruce M. Maggs,

Andr x E a W. Richa

Publication year - 1999

Publication title -

combinatorica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.106

H-Index - 58

eISSN - 1439-6912

pISSN - 0209-9683

DOI - 10.1007/s004930050061

Subject(s) - dilation (metric space) , network packet , mathematics , queue , combinatorics , constant (computer programming) , algorithm , constructive proof , lemma (botany) , schedule , bipartite graph , path (computing) , discrete mathematics , graph , computer science , computer network , ecology , poaceae , biology , programming language , operating system

O (c+d) steps using constant-size queues, where c is the congestion of the paths in the network, and d is the length of the longest path. The proof, however, used the Lovász Local Lemma and was not constructive. In this paper, we show how to find such a schedule in time, with probability , for any positive constant β, where is the sum of the lengths of the paths taken by the packets in the network, and m is the number of edges used by some packet in the network. We also show how to parallelize the algorithm so that it runs in NC. The method that we use to construct the schedules is based on the algorithmic form of the Lovász Local Lemma discovered by Beck.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research