Search

We study the optimal scaling of the expected total queue size in an n×n input-queued switch, as a function of the number of ports n and the load factor ρ, which has been conjectured to be Θ(n/(1−ρ)) (cf. [15]). In a recent work [16], the validity of this conjecture has been established for the regime where 1−ρ=O(1/n2). In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as O(n1.5(1−ρ)−1log(1/(1−ρ))) when 1−ρ=O(1/n). This is an improvement over the state of the art; for example, for ρ=1−1/n the best known bound was O(n3), while ours is O(n2.5logn).

We propose and analyze a multi-server model that captures a performance trade-off between centralized and distributed processing. In our model,a fraction p of an available resource is deployed in a centralized manner (e.g., to serve a most-loaded station) while the remaining fraction 1 − p is allocated to local servers that can only serve requests addressed specifically to their respective stations. Using a fluid model approach, we demonstrate a surprising phase transition in the steady-state delay scaling, as p changes:in the limit of a large number of stations, and when any amount of centralization is available (p > 0), the average queue length insteady state scales as $log_{frac{1}{1-p}}{frac{1}{1-lambda}}$ when the traffic intensity λ goes to 1. This is exponentially smaller than the usual M/M/1-queue delay scaling of $frac{1}{1-lambda}$, obtained when all resources are fully allocated to local stations (p = 0). This indicates a strong qualitative impact of even a small degree of resource pooling.We prove convergence to a fluid limit, and characterize both the transient and steady-state behavior of the actual system, in the limit as the number of stations N goes to infinity. We show that the sequence of queue-length processes converges to a unique fluid trajectory (over any finite time interval, as N → ∞),and that this fluid trajectory converges to a unique invariant state vI, for which a simple closed-form expression is obtained.We also show that the steady-state distribution of the N-server system concentrates on vI as N goes to infinity.

Abstract Using models to simulate and analyze biological networks requires principled approaches to parameter estimation and model discrimination. We use Bayesian and Monte Carlo methods to recover the full probability distributions of free parameters (initial protein concentrations and rate constants) for mass‐action models of receptor‐mediated cell death. The width of the individual parameter distributions is largely determined by non‐identifiability but covariation among parameters, even those that are poorly determined, encodes essential information. Knowledge of joint parameter distributions makes it possible to compute the uncertainty of model‐based predictions whereas ignoring it (e.g., by treating parameters as a simple list of values and variances) yields nonsensical predictions. Computing the Bayes factor from joint distributions yields the odds ratio (∼20‐fold) for competing ‘direct’ and ‘indirect’ apoptosis models having different numbers of parameters. Our results illustrate how Bayesian approaches to model calibration and discrimination combined with single‐cell data represent a generally useful and rigorous approach to discriminate between competing hypotheses in the face of parametric and topological uncertainty.