## Abstract

We consider an 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 ρ) simultaneously become large. We devise an algorithm with expected total queue length equal to O((n^{5 / 4}(1 - ρ) ^{- 1}) log max (1 / ρ, n)) for large n and ρ such that (1 - ρ) ^{- 1}≥ n^{3 / 4}. This result improves the previous best queue length bound in the regime n^{3 / 4}< (1 - ρ) ^{- 1}< n^{7 / 4}. Under same conditions, the algorithm has an amortized time complexity O(n+ (1 - ρ) ^{2}n^{7 / 2}/ log max (1 / ρ, n)). The time complexity becomes O(n) when (1 - ρ) ^{- 1}≥ n^{5 / 4}.

Original language | English (US) |
---|---|

Pages (from-to) | 135-166 |

Number of pages | 32 |

Journal | Queueing Systems |

Volume | 100 |

Issue number | 1-2 |

DOIs | |

State | Published - Feb 2022 |

## Keywords

- Input-queued switch
- Large systems
- Queue-size scaling
- Stochastic network

## ASJC Scopus subject areas

- Statistics and Probability
- Computer Science Applications
- Management Science and Operations Research
- Computational Theory and Mathematics