دورية أكاديمية
Sharper analysis of packet routing on a butterfly
العنوان: | Sharper analysis of packet routing on a butterfly |
---|---|
المؤلفون: | Arvind Krishna, Bruce Hajek, PIETRACAPRINA, ANDREA ALBERTO |
المساهمون: | Arvind, Krishna, Bruce, Hajek, Pietracaprina, ANDREA ALBERTO |
بيانات النشر: | John Wiley & Sons |
سنة النشر: | 1994 |
المجموعة: | Padua Research Archive (IRIS - Università degli Studi di Padova) |
الوصف: | We present an algorithm that does packet routing on an N-node butterfly in time O(log N) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. We simplify the algorithm by focusing on packet routing and prove bounds on its performance for the cases of permutation routing and uniform, random traffic. The main results are upper bounds on the probability that the routing time exceeds t for a fixed queue size. The simplifications made to Ranade's original algorithm and a more careful analysis enabled us to achieve better constants, which, to the best of our knowledge, are the best to date. |
نوع الوثيقة: | article in journal/newspaper |
وصف الملف: | STAMPA |
اللغة: | English |
العلاقة: | info:eu-repo/semantics/altIdentifier/wos/WOS:A1994MZ34700005; volume:24; firstpage:91; lastpage:101; numberofpages:11; journal:NETWORKS; http://hdl.handle.net/11577/2510097Test; info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85025304652 |
DOI: | 10.1002/net.3230240206 |
DOI: | 10.1002/net.3230240206/ |
الإتاحة: | https://doi.org/10.1002/net.3230240206Test http://hdl.handle.net/11577/2510097Test |
رقم الانضمام: | edsbas.876F24E2 |
قاعدة البيانات: | BASE |
DOI: | 10.1002/net.3230240206 |
---|