An algorithm for improved delay-scaling in input-queued switches
Abstract We consider an $$n\times n$$ n × n input-queued...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2022
|
| Online Access: | https://hdl.handle.net/1721.1/141072 |
| _version_ | 1811075364248616960 |
|---|---|
| author | Weng, Wentao Srikant, R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Weng, Wentao Srikant, R. |
| author_sort | Weng, Wentao |
| collection | MIT |
| description | Abstract
We consider an
$$n\times n$$
n
×
n
input-queued switch with uniform Bernoulli traffic and study the delay (or equivalently, the queue length) in the regime where the size of the switch n and the load (denoted by
$$\rho $$
ρ
) simultaneously become large. We devise an algorithm with expected total queue length equal to
$$O((n^{5/4}(1-\rho )^{-1})\log \max (1/\rho ,n))$$
O
(
(
n
5
/
4
(
1
-
ρ
)
-
1
)
log
max
(
1
/
ρ
,
n
)
)
for large n and
$$\rho $$
ρ
such that
$$(1-\rho )^{-1} \ge n^{3/4}$$
(
1
-
ρ
)
-
1
≥
n
3
/
4
. This result improves the previous best queue length bound in the regime
$$n^{3/4}< (1-\rho )^{-1} < n^{7/4}$$
n
3
/
4
<
(
1
-
ρ
)
-
1
<
n
7
/
4
. Under same conditions, the algorithm has an amortized time complexity
$$O(n+(1-\rho )^2 n^{7/2} / \log \max (1/\rho ,n))$$
O
(
n
+
(
1
-
ρ
)
2
n
7
/
2
/
log
max
(
1
/
ρ
,
n
)
)
. The time complexity becomes O(n) when
$$(1-\rho )^{-1} \ge n^{5/4}.$$
(
1
-
ρ
)
-
1
≥
n
5
/
4
. |
| first_indexed | 2024-09-23T10:04:52Z |
| format | Article |
| id | mit-1721.1/141072 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:04:52Z |
| publishDate | 2022 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1410722023-03-28T16:04:20Z An algorithm for improved delay-scaling in input-queued switches Weng, Wentao Srikant, R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abstract We consider an $$n\times n$$ n × n input-queued switch with uniform Bernoulli traffic and study the delay (or equivalently, the queue length) in the regime where the size of the switch n and the load (denoted by $$\rho $$ ρ ) simultaneously become large. We devise an algorithm with expected total queue length equal to $$O((n^{5/4}(1-\rho )^{-1})\log \max (1/\rho ,n))$$ O ( ( n 5 / 4 ( 1 - ρ ) - 1 ) log max ( 1 / ρ , n ) ) for large n and $$\rho $$ ρ such that $$(1-\rho )^{-1} \ge n^{3/4}$$ ( 1 - ρ ) - 1 ≥ n 3 / 4 . This result improves the previous best queue length bound in the regime $$n^{3/4}< (1-\rho )^{-1} < n^{7/4}$$ n 3 / 4 < ( 1 - ρ ) - 1 < n 7 / 4 . Under same conditions, the algorithm has an amortized time complexity $$O(n+(1-\rho )^2 n^{7/2} / \log \max (1/\rho ,n))$$ O ( n + ( 1 - ρ ) 2 n 7 / 2 / log max ( 1 / ρ , n ) ) . The time complexity becomes O(n) when $$(1-\rho )^{-1} \ge n^{5/4}.$$ ( 1 - ρ ) - 1 ≥ n 5 / 4 . 2022-03-09T13:41:07Z 2022-03-09T13:41:07Z 2022-01-15 2022-03-09T04:15:24Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/141072 Weng, Wentao and Srikant, R. 2022. "An algorithm for improved delay-scaling in input-queued switches." en https://doi.org/10.1007/s11134-021-09726-7 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Weng, Wentao Srikant, R. An algorithm for improved delay-scaling in input-queued switches |
| title | An algorithm for improved delay-scaling in input-queued switches |
| title_full | An algorithm for improved delay-scaling in input-queued switches |
| title_fullStr | An algorithm for improved delay-scaling in input-queued switches |
| title_full_unstemmed | An algorithm for improved delay-scaling in input-queued switches |
| title_short | An algorithm for improved delay-scaling in input-queued switches |
| title_sort | algorithm for improved delay scaling in input queued switches |
| url | https://hdl.handle.net/1721.1/141072 |
| work_keys_str_mv | AT wengwentao analgorithmforimproveddelayscalingininputqueuedswitches AT srikantr analgorithmforimproveddelayscalingininputqueuedswitches AT wengwentao algorithmforimproveddelayscalingininputqueuedswitches AT srikantr algorithmforimproveddelayscalingininputqueuedswitches |