BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Maury Bramson

Maury Bramson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRDistributed, Parallel, and Cluster Computingmath.MGmath.OCNetworking and Internet ArchitecturePerformance

Catalog footprint

What is connected

11works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2021arXiv

Stability and Instability of the MaxWeight Policy

Consider a switched queueing network with general routing among its queues. The MaxWeight policy assigns available service by maximizing the objective function $\sum_j Q_j σ_j$ among the different feasible service options, where $Q_j$ denotes queue size and $σ_j$ denotes the amount of service to be executed at queue $j$. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. These properties, as well as its simple formulation, suggest MaxWeight as a serious candidate for implementation in the setting of switched queueing networks; MaxWeight has been extensively studied in the context of communication networks. However, a fluid model variant of MaxWeight was shown by Andrews--Zhang (2003) not to be maximally stable. Here, we prove that MaxWeight itself is not in general maximally stable. We also prove MaxWeight is maximally stable in a much more restrictive setting, and that a weighted version of MaxWeight, where the weighting depends on the traffic intensity, is always stable.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convergence in law of the maximum of nonlattice branching random walk

Let $η^*_n$ denote the maximum, at time $n$, of a nonlattice one-dimensional branching random walk $η_n$ possessing (enough) exponential moments. In a seminal paper, Aidekon demonstrated convergence of $η^*_n$ in law, after recentering, and gave a representation of the limit. We give here a shorter proof of this convergence by employing reasoning motivated by Bramson, Ding and Zeitouni. Instead of spine methods and a careful analysis of the renewal measure for killed random walks, our approach employs a modified version of the second moment method that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Proportional switching in FIFO networks

We consider a family of discrete time multihop switched queueing networks where each packet moves along a fixed route. In this setting, BackPressure is the canonical choice of scheduling policy; this policy has the virtues of possessing a maximal stability region and not requiring explicit knowledge of traffic arrival rates. BackPressure has certain structural weaknesses because implementation requires information about each route, and queueing delays can grow super-linearly with route length. For large networks, where packets over many routes are processed by a queue, or where packets over a route are processed by many queues, these limitations can be prohibitive. In this article, we introduce a scheduling policy for FIFO networks, the Proportional Scheduler, which is based on the proportional fairness criterion. We show that, like BackPressure, the Proportional Scheduler has a maximal stability region and does not require explicit knowledge of traffic arrival rates. The Proportional Scheduler has the advantage that information about the network's route structure is not required for scheduling, which substantially improves the policy's performance for large networks. For instance, packets can be routed with only next-hop information and new nodes can be added to the network with only knowledge of the scheduling constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Decay of tails at equilibrium for FIFO join the shortest queue networks

In join the shortest queue networks, incoming jobs are assigned to the shortest queue from among a randomly chosen subset of $D$ queues, in a system of $N$ queues; after completion of service at its queue, a job leaves the network. We also assume that jobs arrive into the system according to a rate-$αN$ Poisson process, $α<1$, with rate-1 service at each queue. When the service at queues is exponentially distributed, it was shown in Vvedenskaya et al. [Probl. Inf. Transm. 32 (1996) 15-29] that the tail of the equilibrium queue size decays doubly exponentially in the limit as $N\rightarrow\infty$. This is a substantial improvement over the case D=1, where the queue size decays exponentially. The reasoning in [Probl. Inf. Transm. 32 (1996) 15-29] does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating general service time distributions was introduced in Bramson et al. [In Proc. ACM SIGMETRICS (2010) 275-286]. The program relies on an ansatz that asserts, in equilibrium, any fixed number of queues become independent of one another as $N\rightarrow\infty$. This ansatz was demonstrated in several settings in Bramson et al. [Queueing Syst. 71 (2012) 247-292], including for networks where the service discipline is FIFO and the service time distribution has a decreasing hazard rate. In this article, we investigate the limiting behavior, as $N\rightarrow \infty$, of the equilibrium at a queue when the service discipline is FIFO and the service time distribution has a power law with a given exponent $-β$, for $β>1$. We show under the above ansatz that, as $N\rightarrow\infty$, the tail of the equilibrium queue size exhibits a wide range of behavior depending on the relationship between $β$ and $D$. In particular, if $β>D/(D-1)$, the tail is doubly exponential and, if $β<D/(D-1)$, the tail has a power law. When $β=D/(D-1)$, the tail is exponentially distributed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Shy couplings, CAT(0) spaces, and the lion and man

Two random processes X and Y on a metric space are said to be $\varepsilon$-shy coupled if there is positive probability of them staying at least a positive distance $\varepsilon$ apart from each other forever. Interest in the literature centres on nonexistence results subject to topological and geometric conditions; motivation arises from the desire to gain a better understanding of probabilistic coupling. Previous nonexistence results for co-adapted shy coupling of reflected Brownian motion required convexity conditions; we remove these conditions by showing the nonexistence of shy co-adapted couplings of reflecting Brownian motion in any bounded CAT(0) domain with boundary satisfying uniform exterior sphere and interior cone conditions, for example, simply-connected bounded planar domains with $C^2$ boundary. The proof uses a Cameron-Martin-Girsanov argument, together with a continuity property of the Skorokhod transformation and properties of the intrinsic metric of the domain. To this end, a generalization of Gauss' lemma is established that shows differentiability of the intrinsic distance function for closures of CAT(0) domains with boundaries satisfying uniform exterior sphere and interior cone conditions. By this means, the shy coupling question is converted into a Lion and Man pursuit-evasion problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Positive Recurrent Reflecting Brownian Motion with Divergent Fluid Path

Semimartingale reflecting Brownian motions (SRBMs) are diffusion processes with state space the d-dimensional nonnegative orthant, in the interior of which the processes evolve according to a Brownian motion, and that reflect against the boundary in a specified manner. The data for such a process are a drift vector θ, a nonsingular d \times d covariance matrix Σ, and a d \times d reflection matrix R. A standard problem is to determine under what conditions the process is positive recurrent. Necessary and sufficient conditions for positive recurrence are easy to formulate for d = 2, but not for d > 2. Associated with the pair (θ, R) are fluid paths, which are solutions of deterministic equations corresponding to the random equations of the SRBM. A standard result of Dupuis and Williams [6] states that when every fluid path associated with the SRBM is attracted to the origin, the SRBM is positive recurrent. Employing this result, El Kharroubi et al. [7, 8] gave sufficient conditions on (θ,Σ,R) for positive recurrence for d = 3; Bramson et al. [2] showed that these conditions are, in fact, necessary. Relatively little is known about the recurrence behavior of SRBMs for d > 3. This pertains, in particular, to necessary conditions for positive recurrence. Here, we provide a family of examples, in d = 6, with θ = (-1, -1, . >. ., -1)T, Σ = I and appropriate R, that are positive recurrent, but for which a linear fluid path diverges to infinity. These examples show in particular that, for d >= 6, the converse of the Dupuis-Williams result does not hold.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Network stability under max--min fair bandwidth sharing

There has recently been considerable interest in the stability of different fair bandwidth sharing policies for models that arise in the context of Internet congestion control. Here, we consider a connection level model, introduced by Massoulié and Roberts [Telecommunication Systems 15 (2000) 185--201], that represents the randomly varying number of flows present in a network. The weighted $α$-fair and weighted max-min fair bandwidth sharing policies are among important policies that have been studied for this model. Stability results are known in both cases when the interarrival times and service times are exponentially distributed. Partial results for general service times are known for weighted $α$-fair policies; no such results are known for weighted max--min fair policies. Here, we show that weighted max--min fair policies are stable for subcritical networks with general interarrival and service distributions, provided the latter have $2+δ_1$ moments for some $δ_1>0$. Our argument employs an appropriate Lyapunov function for the weighted max--min fair policy.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Positive recurrence of reflecting Brownian motion in three dimensions

Consider a semimartingale reflecting Brownian motion (SRBM) $Z$ whose state space is the $d$-dimensional nonnegative orthant. The data for such a process are a drift vector $θ$, a nonsingular $d\times d$ covariance matrix $Σ$, and a $d\times d$ reflection matrix $R$ that specifies the boundary behavior of $Z$. We say that $Z$ is positive recurrent, or stable, if the expected time to hit an arbitrary open neighborhood of the origin is finite for every starting state. In dimension $d=2$, necessary and sufficient conditions for stability are known, but fundamentally new phenomena arise in higher dimensions. Building on prior work by El Kharroubi, Ben Tahar and Yaacoubi [Stochastics Stochastics Rep. 68 (2000) 229--253, Math. Methods Oper. Res. 56 (2002) 243--258], we provide necessary and sufficient conditions for stability of SRBMs in three dimensions; to verify or refute these conditions is a simple computational task. As a byproduct, we find that the fluid-based criterion of Dupuis and Williams [Ann. Probab. 22 (1994) 680--702] is not only sufficient but also necessary for stability of SRBMs in three dimensions. That is, an SRBM in three dimensions is positive recurrent if and only if every path of the associated fluid model is attracted to the origin. The problem of recurrence classification for SRBMs in four and higher dimensions remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stability of Join the Shortest Queue Networks

Join the shortest queue (JSQ) refers to networks whose incoming jobs are assigned to the shortest queue from among a randomly chosen subset of the queues in the system. After completion of service at the queue, a job leaves the network. We show that, for all non- idling service disciplines and for general interarrival and service time distributions, such networks are stable when they are subcritical. We then obtain uniform bounds on the tails of the marginal distributions of the equilibria for families of such networks; these bounds are employed to show relative compactness of the marginal distributions. We also present a family of subcritical JSQ networks whose workloads in equilibrium are much larger than for the corresponding networks where each incoming job is assigned randomly to a queue. Part of this work generalizes results in Foss and Chernova [12], which applied fluid limits to study networks with the FIFO discipline. Here, we apply an appropriate Lyapunov function.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Tightness of the recentered maximum of the two-dimensional discrete Gaussian Free Field

We consider the maximum of the discrete two dimensional Gaussian free field (GFF) in a box, and prove that its maximum, centered at its mean, is tight, settling a long-standing conjecture. The proof combines a recent observation of Bolthausen, Deuschel and Zeitouni with elements from (Bramson 1978) and comparison theorems for Gaussian fields. An essential part of the argument is the precise evaluation, up to an error of order 1, of the expected value of the maximum of the GFF in a box. Related Gaussian fields, such as the GFF on a two-dimensional torus, are also discussed.

0 citations0 reviewsNo code linkedOpen access