Demo Data from VLDB 2026 / reviewers in the wild / expert
Milind Kopikare
dblp:26/4370
· DBLP profile ↗
1ranked-venue papers
0as first author
0since 2021 · last 2002
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Computer networks · 1
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Computer networks
1 paper |
Routing and switching · 76% Network performance modeling · 24% |
Topics — the 6 heaviest of 6, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Network performance modeling › network calculus
delay bounds |
0.0 | 1 | 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switches · INFOCOM 2002 |
Routing and switching
input-queued switch |
0.0 | 1 | 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switches · INFOCOM 2002 |
Routing and switching › input-queued switch
maximum weight matching |
0.0 | 1 | 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switches · INFOCOM 2002 |
Routing and switching
scheduling algorithms |
0.0 | 1 | 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switches · INFOCOM 2002 |
Routing and switching
switching |
0.0 | 1 | 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switches · INFOCOM 2002 |
Network performance modeling › throughput analysis
stable throughput |
0.0 | 1 | 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switches · INFOCOM 2002 |
Methods — techniques the papers use, named apart from their topics
lyapunov function · 0.0approximation analysis · 0.0
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2002 | Delay bounds for the approximate Maximum weight matching algorithm for input queued switchesabstractInput Queued (IQ) switch architecture has been of interest due to its low memory bandwidth requirement. A scheduling algorithm is required to schedule the transfer of packets through cross-bar switch fabric at every time slot. The performance, that is throughput and delay, of a switch depends on the scheduling algorithm. The maximum weight matching (MWM) algorithm is known to deliver 100% throughput under any admissible traffic. Leonardi et. al. (2001) obtained a nontrivial bound on the delay for the MWM algorithm under admissible Bernoulli i.i.d. traffic. There has been a lot of interesting work done over time to analyze throughput of scheduling algorithms. But apart from the work of Leonardi et al. there has not been any work done to obtain bounds on delay of scheduling algorithms. The MWM algorithm is perceived to be a very good scheduling algorithm in general and simulations have suggested that it performs better than most of the known algorithms in terms of delay. But it is very complex to implement. Hence many simple to implement approximations to MWM have been proposed. In this paper, we study a class of approximation algorithms to MWM, which always obtain a schedule whose weight W differs from the weight of MWM schedule W* by at most f(W*), where f(.) is a sub-linear function. We call this difference in weight as "approximation distance" of algorithm from MWM. We denote this class of algorithms by 1-APRX. We prove that any 1-APRX algorithm is stable, that is, it delivers upto 100% of throughput under any admissible Bernoulli i.i.d. input traffic. Under any admissible Bernoulli i.i.d. traffic, we obtain bounds on the average queue length(equivalently delay) of the 1-APRX algorithms using a Lyapunov function technique, which was motivated in Leonardi et al. The delay bounds obtained for the 1-APRX algorithm are linearly related with the "approximation distance", which matches the intuition that the better the weight of the schedule, the better the algorithm will perform. Interestingly, simulations show a linear relationship between the average queue length (equivalently delay) and the "approximation distance". Thus, the "approximation distance" of a scheduling algorithm can serve as a metric to differentiate between the performance of different stable algorithms, even though throughput may be same for these algorithms. We also obtain a novel heuristic tighter bound on the average queue length (equivalently delay) under uniform Bernoulli i.i.d. traffic for MWM using a very simple argument. Devavrat Shah, Milind Kopikare |
INFOCOM | 2 |