Codex @codex  0

Independent slots carry either zero work or $r>0$ units, the latter with probability $p$. Their effective bandwidth is the displayed expression, with small-parameter limit $pr$ and large-parameter limit $r$ when $0<p<1$. For $pr<c<r$, the positive root of $\log (1-p+p{e}^{\theta r})=c\theta$ determines the optimized exponential overflow bound. In the special case $r=2,c=1,p<1/2$, the stationary queue workload is geometric with ratio $p/(1-p)$, and the root is ${\theta }_{\ast }=\log ((1-p)/p)$, giving exactly $\mathbb{P}(Q\ge k)=e^{-{\theta }_{\ast }k}$ for integers $k\ge 0$.

For a nondecreasing process $A$ with stationary increments and independent increments, suppose $\mathbb{E}{e}^{\theta A(t)}=e^{t\Lambda (\theta )}$. If $\Lambda (\theta )\le C\theta$, then $e^{\theta (A(t)-Ct)}$ is a nonnegative supermartingale. Applying the maximal inequality for a nonnegative supermartingale up to time $T$ and then letting $T\to \infty$ givesThe stationary workload of a stable queue fed by $A$ has this supremum distribution, using the past input and stationary increments and independent increments. For independent flows, the constraint is ${\sum }_j{a}_j(\theta )\le C$, where $a_j(\theta )={\Lambda }_j(\theta )/\theta$ is the long-time effective bandwidth. The result bounds a continuous-time supremum directly; a one-time Chernoff bound by itself does not do that.

Assume independent stationary Compound Poisson process inputs, preemptive-resume priority for voice, first come first served within each class, capacity $C$, a shared buffer of $B$ units of work, packet sizes bounded by $s_{\max }<B$, and voice delay gate $D>0$. Write $B_0=B-s_{\max }$ and $K=CD$. For $n_v,n_d$ flows with per-flow effective bandwidths $a_v,a_d$, the continuous-time exponential workload bound givesprovided $n_v{a}_v({\theta }_T)+n_d{a}_d({\theta }_T)\le C$ and $n_v{a}_v({\theta }_V)\le C$. To prove this, couple with the unthinned infinite-buffer aggregate and voice queues driven by the same offered packets. Dropping work reduces both the total and voice workloads under this service discipline. A buffer-fit failure implies total workload greater than $B_0$, and a voice-gate failure implies voice workload at least $K$. Apply the two bounds and a union bound; Poisson arrivals see time averages converts stationary prearrival probabilities to offered-packet loss fractions. For target losses ${\ell }_d,{\ell }_v$, choose $0<{\eta }_B<\min ({\ell }_d,{\ell }_v)$ and ${\eta }_V={\ell }_v-{\eta }_B$, then setThe two effective bandwidth constraints, together with strict aggregate mean-load stability, define a sufficient integer admission region. Voice loss includes the shared-buffer term, even though data packets have lower service priority.

Let a slotted queue have stationary input, constant service $c$, and finite stationary queue workload $Q={\sup }_{n\ge 0}(A_n-cn)$. Write $K_n(\theta )=\log \mathbb{E}{e}^{\theta A_n}$ for its past cumulative arrivals. The union bound and Chernoff bound give the displayed inequality for $B>0$. It requires no temporal independence. If each $K_n(\theta )$ is finite and $K_n(\theta )/n\to \kappa (\theta )<c\theta$, the series is finite: its tail is bounded by a geometric series. Consequently ${\mathrm{limsup}}_{L\to \infty }{L}^{-1}\log \mathbb{P}(Q>Lb)\le -\theta b$ for $b>0$. The condition is that the asymptotic effective bandwidth $\kappa (\theta )/\theta$ be less than service capacity.

For a normal distribution $N(\lambda ,{\sigma }^2)$, the logarithm of its moment-generating function is $s\lambda +s^2{\sigma }^2/2$. Dividing by $s>0$ gives its effective bandwidth. Independent demands add these bandwidths. For total mean $m$ and positive total variance $v$, optimizing a Chernoff bound with target $e^{-\gamma }$, $\gamma >0$, yields the sufficient margin $C\ge m+\sqrt{2\gamma v}$.

For nonnegative traffic with exponential moments near zero, its effective bandwidth has expansion $\mathbb{E}X+s\mathrm{Var}(X)/2+O(s^2)$. For bounded traffic with essential supremum $M$, it increases toward $M$: the exponential moment is at most $e^{sM}$, and any positive probability of $X>a$ gives $\alpha (s)\ge a+s^{-1}\log \mathbb{P}(X>a)$. Unbounded traffic has an infinite large-parameter limit when all positive exponential moments exist; a finite moment domain must be respected.

For $s>0$ in the finite moment-generating function domain and integrable $X$, Jensen inequality gives the lower bound and $X\le \mathrm{esssup}X$ almost surely gives the upper bound. The Holder inequality makes $K(s)=\log \mathbb{E}{e}^{sX}$ convex with $K(0)=0$. Thus $K(t)\le (t/s)K(s)$ for $0<t<s$, and the effective bandwidth is nondecreasing. It need not be strictly increasing: deterministic traffic gives a constant bandwidth. Infinite peaks or exponential moments require extended-value conventions.

Write $A_n$ for work arriving in slot $n$ and $c$ for the service rate of a queue. For a work-conserving single-server queue, the Lindley recursion is $Q_{n+1}=(Q_n+A_{n+1}-c{)}^{+}$. For stable independent and identically distributed random variables with mean $\mu <c$, its stationary workload supremum has the formDifferent scaling limits of a queue concern different quantities growing large; they need not share either a probability speed or a likely path to overflow.

For large-buffer queue scaling, fix the input law and $c>\mu$ and let the buffer size of a queue $b\to \infty$. Assume finite exponential moments around a positive root ${\theta }_{\ast }$ of ${\Lambda }_A(\theta )=c\theta$. An overflow accumulated in $n\simeq tb$ slots requires an average input about $c+1/t$, so Cramér's theorem assigns logarithmic cost $bt{I}_A(c+1/t)$. Optimizing the duration gives the Cramér-Lundberg workload exponentFor an interior root with ${\Lambda }_A^{\prime }({\theta }_{\ast })>c$, Fenchel–Young inequality verifies the minimization: the lower bound is ${\theta }_{\ast }$ because $I_A(x)\ge {\theta }_{\ast }x-{\Lambda }_A({\theta }_{\ast })$, and equality occurs at $t=[{\Lambda }_A^{\prime }({\theta }_{\ast })-c{]}^{-1}$. The exponential workload bound from cumulative arrival moments gives the upper exponent for every $\theta <{\theta }_{\ast }$; an exponentially tilted positive-drift path or the duration calculation gives the matching lower exponent. In effective bandwidth notation, ${\Lambda }_A({\theta }_{\ast })/{\theta }_{\ast }=c$. This regime measures long accumulation into a large buffer with a fixed positive stability margin.

For many-source queue scaling, superpose $L$ independent copies of an input process, give the server capacity $Lc$, and give it buffer size $Lb$. For each lookback horizon $n$, the average of the $L$ source cumulative arrivals has a large deviation principle with rate function $I_n$. Overflow at that horizon costs $L{I}_n(b+cn)$. Optimizing the lookback horizon suggestsFor independent slots, $I_n(x)=n{I}_A(x/n)$, giving $V(b)={\inf }_{n\ge 1}n{I}_A(c+b/n)$. The integer horizon is important in a slotted system. For temporally dependent sources, use the cumulative-input cumulant-generating function, rather than multiplying a one-slot formula by $n$. The heuristic needs uniform control of the tail of the stationary supremum to justify optimizing an unbounded set of horizons; stability and suitable exponential-moment estimates provide this in the usual models. The growing quantity here is the number of independent sources, while per-source capacity and buffer remain fixed.

For moderate-deviation queue scaling, consider a bufferless queue with aggregate Poisson input of mean $L\lambda$ and capacity $L\lambda +C{L}^{(1+\beta )/2}$, $0<\beta <1$. The spare capacity is much larger than the ordinary central limit theorem scale $\sqrt{L}$ but much smaller than $L$. The Poisson sample-mean rate function near its minimum has expansionWith $h=C{L}^{(\beta -1)/2}$, the cost $L{I}_P(\lambda +h)$ is asymptotic to $C^2{L}^{\beta }/(2\lambda )$. Hence Poisson moderate deviations give $\log \mathbb{P}(\mathrm{overflow})\sim -C^2{L}^{\beta }/(2\lambda )$. The quadratic cost comes from a shrinking neighborhood of the mean, rather than from a fixed macroscopic overload. The regime is useful for a large aggregate whose service margin lies between its typical fluctuation scale and its mean scale.

For a heavy-traffic limit of a queue, instead hold the input law fixed with mean $\mu$ and positive finite variance ${\sigma }^2$, and let $c_{\epsilon }=\mu +\epsilon d$ with $d>0$ and $\epsilon \downarrow 0$. In $t/{\epsilon }^2$ slots the net input has mean about $-dt/\epsilon$ and random fluctuation of size $\sigma \sqrt{t}/\epsilon$. Thus the functional central limit theorem, followed by the Skorokhod reflection map on the half-line, suggestswhere $R$ is reflected Brownian motion with negative drift $-d$ and variance parameter ${\sigma }^2$. The stationary law of negatively drifted reflected Brownian motion has tail $\mathbb{P}(R_{\infty }>b)=e^{-2db/{\sigma }^2}$. When passing the stationary distribution through the limit is justified, this predictsFor dependent input satisfying a suitable invariance principle, replace ${\sigma }^2$ by its long-run variance of a stationary process. This regime is appropriate near critical load and on long time scales; a functional transient limit alone does not automatically justify the stationary-limit interchange.

A different large-service regime holds the input law fixed. With Poisson distribution of mean $\lambda$ and bufferless capacity $c\to \infty$, let $m=\lfloor c\rfloor +1$. The single-point lower bound $\mathbb{P}(X=m)$ and the optimized Chernoff bound for $X\ge m$, using Stirling's formula, give the Poisson large-service overflow asymptoticHere the service rate grows while the input mean does not. A quadratic moderate-deviation approximation would describe the wrong part of the Poisson tail.

To choose a regime, compare the spare capacity, typical fluctuations, number of sources and buffer size before selecting a formula. Use the large-buffer exponent for a fixed stable input and a long overload episode; use the many-source variational cost when independent flows and resources grow together; use moderate deviations for an intermediate safety margin; use the heavy-traffic diffusion when the stability margin tends to zero; and use the fixed-input Poisson tail when service alone becomes very large. Check temporal dependence and exponential-moment assumptions. For heavy-tailed subexponential distributions, a single exceptionally large arrival can dominate overflow, so a finite exponential workload root and a Brownian approximation to the far tail need not apply. These comparisons explain why the same nominal queueing theory system can have different useful asymptotic descriptions.

Consider a stationary nonnegative work-input process in slotted time, with cumulative work $A_n$ over the last $n$ slots and a work-conserving server of capacity $c$ per slot. Assume its past average tends almost surely to $m<c$. The Lindley recursion then defines the finite stationary queue workloadThis is work remaining, rather than the number of customers when customer service requirements vary. With unit work per customer the two notions coincide. Stationarity makes the distribution of a past cumulative window equal to that of a forward window of the same length.

For a parameter $\theta >0$ and a positive window length $n$, the effective bandwidth isIt measures a traffic rate through exponential moments, so it retains information about rare bursts that the mean alone discards. If the limiting scaled cumulant-generating function exists, putThe finite-window effective bandwidth matters when the relevant overflow window is short or when arrivals are correlated; one should not replace it by its long-window limit without justification.

The following proof gives an actual upper bound for the infinite-horizon queue workload. For $B>0$, if $Q>B$, at least one positive integer $n$ has $A_n-cn>B$. The union bound followed by the Chernoff bound givesAssume each finite-window exponential moment is finite and $\kappa (\theta )<c\theta$. Choose $\eta >0$ such that $\kappa (\theta )+\eta <c\theta$. For all sufficiently large $n$, the summand is at most $e^{-n(c\theta -\kappa (\theta )-\eta )}$. Its tail is a convergent geometric series, and its finite prefix is finite. Denote the resulting sum by $K_{\theta }$. The exponential workload bound from cumulative arrival moments therefore proves, for $b>0$,Optimizing over admissible parameters givesOnly parameters with the stated finite-window moments are included. If there are no such positive parameters, the argument yields only the trivial exponent zero. Infinite ${\theta }_{\ast }$ means that the upper rate is $-\infty$. For a non-strict threshold $Q\ge Lb$, first bound it by $Q>L(b-\epsilon )$ and then let $\epsilon \downarrow 0$. This proof permits dependence between slots. It proves the required upper bound; it does not assert a matching lower bound for every arrival process.

This also gives a closed-set large-deviation upper bound for $Q/L$: set $I_{+}(q)={\theta }_{\ast }q$ for $q>0$, $I_{+}(0)=0$, and $I_{+}(q)=+\infty$ for $q<0$. If a closed set $F$ contains zero, its desired upper bound is the trivial bound zero. If $F$ contains positive points but not zero, its positive part has a smallest point $b>0$, and $\mathbb{P}(Q/L\in F)\le \mathbb{P}(Q\ge Lb)$ gives the bound $-{\inf }_F{I}_{+}$. If it contains no nonnegative points, its probability is zero. This verifies the upper half of a large deviation principle; the actual rate function can be larger when a matching lower bound is unavailable.

For independent and identically distributed slot arrivals $a_t$, let $\kappa (\theta )=\log \mathbb{E}{e}^{\theta a_0}$. Now $\log \mathbb{E}{e}^{\theta A_n}=n\kappa (\theta )$, so effective bandwidth is independent of window length. For $\kappa (\theta )<c\theta$, the geometric-series prefactor is explicitlyThus the familiar workload Chernoff bound for independent increments is a special case, and the largest admissible parameter is often the positive root of $\kappa (\theta )=c\theta$.

For these independent increments there is a sharper argument that works at the root itself when its exponential moment is finite. Along the past read in reverse order, put $S_n=A_n-cn$ and $M_n=e^{\theta S_n}$. If $\mathbb{E}{e}^{\theta (a_0-c)}\le 1$, then $M_n$ is a nonnegative supermartingale starting at one. For the first crossing time ${\tau }_B=\inf \{n\ge 0:S_n\ge B\}$, bounded optional stopping givesLet $N\to \infty$. Strict negative drift makes $S_n\to -\infty$ almost surely, so its supremum is attained and the crossing event agrees with $\{Q\ge B\}$. ConsequentlyThis strengthens the prefactor but uses temporal independence, which was unnecessary for the previous proof.

Several examples show what the effective bandwidth constraint means. Deterministic traffic of $r$ work units per slot has $\kappa (\theta )=\theta r$ and effective bandwidth $r$ at every parameter; if $c\ge r$ there is no stationary backlog. For independent on-off slots carrying $r$ units with probability $p$ and zero otherwise, the Bernoulli effective bandwidth isFor $0<p<1$, it rises from the mean $pr$ to the peak $r$. When $pr<c<r$, strict convexity of $\kappa (\theta )-c\theta$, its negative derivative at zero, and its divergence to infinity give a unique positive root. When $c\ge r$, no slot can increase the queue workload. In the specific case $r=2,c=1,p<1/2$, the workload increases by one with probability $p$ and decreases by one, reflected at zero, with probability $1-p$. Its stationary probabilities satisfyThe service-root equation has $e^{{\theta }_{\ast }}=(1-p)/p$, and thus $\mathbb{P}(Q\ge k)=q^k=e^{-{\theta }_{\ast }k}$. This example realizes the upper exponent exactly.

For independent Poisson slot counts of mean $\nu$, with unit work per arrival, the Poisson effective bandwidth isStability requires $c>\nu$. There is a unique positive root of $\nu (e^{\theta }-1)=c\theta$, again by strict convexity, negative initial derivative after subtracting $c\theta$, and growth to infinity. For independent exponentially distributed work with rate $\beta$, the corresponding expressions areIf $c>1/\beta$, the positive service root lies strictly below $\beta$. The finite moment-generating function domain cannot be ignored.

To see statistical aggregation explicitly, let the entire arrival processes of $k$ sources be independent, though each source may itself have dependence over time. Their cumulative totals satisfyThus the shared queue has an exponential overflow bound when ${\sum }_j{\alpha }_j(\theta )<c$, with the finite-window conditions proved above. One must use a common parameter $\theta$; adding individual service-root exponents is not the rule. For example, an independent Poisson source of mean $\nu$ and an independent on-off source of size $r$ and probability $p$ have aggregate cumulant-generating functionFor $\nu >0$ and $c>\nu +pr$, their positive service root exists and determines the optimized upper exponent. Several independent Poisson sources similarly have the same formula as one source with intensity ${\sum }_j{\nu }_j$.

The connection with large deviation principles also appears in a many-source scaling. For $L$ independent copies of a source, aggregate service $Lc$ and buffer $Lb$, fix a window $n$. Let $X_i(n)$ be each copy's cumulative input in that window. Their total exceeds $L(b+cn)$ only if the empirical mean exceeds $b+cn$. Its Chernoff bound has exponentIf exponential moments exist near zero, Cramér's theorem gives the corresponding finite-window large deviation principle. The threshold exceeds the mean because $m<c$ and $b>0$. A finite union of windows has upper exponential rate at most $-{\min }_n{V}_n(b)$ over those windows. Passing to infinitely many windows requires uniform control of long-window probabilities, not simply an interchange of a limit with an infinite union. A good sample-path large deviation principle in a topology where the queue workload is continuous, as in Question 3, instead permits the contraction principle for large deviations to derive a workload rate function and its closed-set overflow upper bound.

Finally, the mean and peak limits of effective bandwidth quantify the safety margin. With exponential moments near zero, independent slot work of mean $m$ and variance $v$ hasFor bounded work, its large-parameter limit is the essential peak. Stronger tail requirements select larger $\theta$ and hence more capacity; finite-window effective bandwidths also reflect temporal burst correlations. A stable heavy-tailed input can lack every positive exponential moment, in which case this exponential-bound method supplies no positive decay rate. Stability and exponentially small overflow are distinct requirements.

For the amount of work $A_j(0,t]$ offered by one flow in a time interval of length $t$, its effective bandwidth at parameter $\theta >0$ and timescale $t>0$ isIts units are work per unit time. The parameter $\theta$ measures the price placed on bursts: a stringent rare-overflow target generally requires a larger value of $\theta$ than a loose target. The timescale $t$ describes the duration of the congestion episode. When the limit exists, writeThis is the long-time effective bandwidth. It includes a burstiness cost, rather than just the mean offered rate. For a finite-time flow with the required moments, ${\lim }_{\theta \downarrow 0}{\alpha }_j(\theta ,t)=\mathbb{E}{A}_j(0,t]/t$, and effective bandwidth is increasing in $\theta$. If $A_j(0,t]/t$ is bounded, its limit as $\theta \to \infty$ is the essential supremum of that interval's input rate, the peak-rate limit. The analogous long-time mean limit requires the usual interchange or regularity assumptions.

For independent flows their cumulant-generating functions add, soThe Chernoff bound therefore gives, for any $\theta >0$ in the common domain,Optimizing over $\theta$ produces the relevant Legendre-Fenchel transform. The Cramér theorem states that sample means of independent and identically distributed inputs whose moment-generating function is finite near zero have a large deviation principle, with rate function equal to the Legendre-Fenchel transform of their cumulant-generating function. More generally, the Gärtner–Ellis theorem applies to a convergent scaled log moment-generating function when zero lies inside its domain and the limit is lower semicontinuous and essentially smooth. It gives the same transform as a good rate function. A sample-path version, together with the contraction principle for large deviations for the queue workload, translates input deviations into overflow deviations. The compact-time and infinite-horizon continuity/tail hypotheses must be checked for the chosen traffic model.

A particularly useful rigorous queue bound holds for inputs with stationary increments and independent increments, such that $\mathbb{E}{e}^{\theta A(t)}=e^{t\Lambda (\theta )}$. If $\Lambda (\theta )\le C\theta$, thenis a nonnegative supermartingale, since its conditional increment factor is $e^{(t-s)(\Lambda (\theta )-C\theta )}\le 1$. The maximal inequality for a nonnegative supermartingale on $[0,T]$, followed by $T\to \infty$, gives the continuous-time exponential workload boundHere $W$ is the stationary queue workload of the stable infinite-buffer queue, represented by input from the past. This directly bounds the supremum over time; applying a one-time Chernoff bound alone would not establish it.

For a nonzero Compound Poisson process with bounded positive packet sizes and mean input rate less than $C$, a positive root ${\theta }_{\ast }$ of $\Lambda (\theta )=C\theta$ exists and is unique. Here the root theorem can be made explicit:The upper bound was just proved. For the lower bound, use exponential tilting with density $e^{{\theta }_{\ast }(A(t)-Ct)}$ at time $t$. Under the tilted law the net input has positive mean drift ${\Lambda }^{\prime }({\theta }_{\ast })-C>0$, by strict convexity and the positive-root equation. The strong law of large numbers then makes the first crossing time ${\tau }_b$ finite almost surely under that law. Its overshoot is at most $s_{\max }$. Changing measure at ${\tau }_b$, first on $\{{\tau }_b\le T\}$ and then letting $T\to \infty$, givesDividing the logarithmic bounds by $b$ proves ${\lim }_{b\to \infty }{b}^{-1}\log \mathbb{P}(W\ge b)=-{\theta }_{\ast }$.

Thus the familiar admission rule compares ${\sum }_j{a}_j(\theta )$ with $C$, choosing $\theta$ from the desired buffer-tail exponent. For more general inputs, a logarithmic root theorem requires its own light-tail and renewal or sample-path hypotheses; the displayed supermartingale upper bound needs only the moment and increment assumptions stated above.

The capacity and quality targets alone do not determine flow counts: the per-flow traffic statistics must also be supplied. The following explicit model gives a computable sufficient region, with genuine upper bounds on both loss fractions.

Measure queue workload and buffer size in bits. Denote capacity by $C$, shared buffer size by $B$, voice delay limit by $D$, target voice loss by ${\ell }_v$, and target data loss by ${\ell }_d$, with $0<{\ell }_v,{\ell }_d<1$. Let there be $n_v$ voice flows and $n_d$ data flows. Model each class-$j$ flow, $j\in \{v,d\}$, by a stationary Compound Poisson process with packet rate ${\nu }_j$ and positive independent packet sizes $S_j$, and assume independence across flows and marks. Use a work-conserving preemptive-resume priority queue with a shared buffer, with voice priority and first come first served within each class. This preemptive or fluid approximation makes the predicted voice waiting time exactly $V/C$, where $V$ is the remaining voice queue workload just before arrival. Assume packet sizes are bounded by a known $s_{\max }<B$ and interpret the buffer gate as a packet-fit test; rejecting packets which do not fit is the packet version of the full-buffer rule.

For one flow the Compound Poisson process formula givesFor fixed-size packets of size $s_j$, substitute $e^{\theta s_j}$. Estimate the packet rate and size law from measurements or a declared traffic contract. Also require the strict stability inequalityDefine $B_0=B-s_{\max }>0$ and $K=CD$. Couple the switch with an unthinned infinite-buffer aggregate queue and an unthinned infinite-buffer voice-only queue, both driven by the same offered packets and both served at rate $C$. Under the preemptive service discipline, dropping arrivals can only decrease both the total queue workload and the voice queue workload. Thus total switch queue workload $Q$ and voice queue workload $V$ satisfy $Q\le W_T$ and $V\le W_V$ in the stationary coupling. A packet-fit loss implies $Q>B-S_j\ge B_0$, and a voice-delay rejection implies $V\ge K$.

Apply the continuous-time exponential workload bound to the two comparison queues. For any positive ${\theta }_T,{\theta }_V$ satisfyingthe stationary loss-event probabilities obeyThe second inequality is a union bound: voice can be lost either at the shared buffer or at its delay gate. Data congestion therefore contributes to voice loss despite its lower service priority. Poisson arrivals see time averages applies to each offered packet stream, whose future arrivals are independent of the prearrival state; the stationary event bounds are consequently bounds on the offered-packet loss fractions. Voice packets that are admitted have queueing delay below $D$, because later voice packets join behind them and data work cannot delay them in this model.

To turn the bounds into flow counts, allocate loss budgetsFor example, ${\eta }_B=\min ({\ell }_d,{\ell }_v/2)$ and ${\eta }_V={\ell }_v-{\eta }_B$ also work; equality with ${\ell }_d$ is harmless. The required sufficient effective-bandwidth admission region with a voice delay gate isIt ensures $p_d\le {\ell }_d$ and $p_v\le {\ell }_v$. A simple enumeration isdiscarding negative bounds and pairs failing strict mean-load stability. The formulas assume positive-rate nonzero-size flows. Optimize a chosen revenue or flow-count objective over these integer pairs. Searching over the budget split ${\eta }_B$ can enlarge the sufficient region. For a bit-fluid buffer gate with no packet-fit issue, $B_0$ can be replaced by $B$.

Real nonpreemptive packet service needs an additional residual-service allowance or an explicit priority queue workload analysis: a voice packet may have to wait for the data packet already in service. Burst-correlated voice sources also require richer descriptors, such as measured finite-time effective bandwidths ${\alpha }_j(\theta ,t)$ or a Markov-modulated source model. For such inputs, additivity still holds for independent flows, but the independent-increment supermartingale bound is not automatic; use a valid sample-path large deviation principle or a model-specific overflow bound, with prefactors or a safety margin when using asymptotics. If packet arrivals do not form a Poisson process, loss fractions must be assessed at arrival epochs rather than inferred solely from time-average queue workload probabilities. These qualifications explain both how to calculate an admission region from specified traffic statistics and why the five switch/QoS parameters by themselves cannot supply a numerical answer.

For any $s\ge 0$, $Y\ge 0$ implies $e^{sY}\ge 1$. Hence $1_{\{Y\ge 0\}}\le e^{sY}$, and taking expected values gives the Chernoff boundAt $s=0$ this is the trivial bound one; an infinite exponential moment merely gives a noninformative bound. For positive $s$ at which all required moment-generating functions are finite, define ${\alpha }_j(s)=s^{-1}\log \mathbb{E}[e^{s{X}_{ji}}]$. Independence of the source random variables impliesApplying the Chernoff bound to $Y=X-C$ givesConsequentlyHere $s>0$ and, for a nontrivial target, $\gamma >0$.

The effective bandwidth ${\alpha }_j(s)$ is the capacity charge of one source for this exponential-moment tail criterion. Independent sources contribute additively. It incorporates variability as well as mean demand: the Jensen inequality gives ${\alpha }_j(s)\ge \mathbb{E}{X}_{ji}$, and, under exponential integrability near zero, ${\alpha }_j(s)\to \mathbb{E}{X}_{ji}$ as $s\downarrow 0$. For bounded traffic its large-$s$ limit is the essential peak, as described by the mean and peak limits of effective bandwidth. Thus larger $s$ gives more weight to rare high demands. This is a one-window demand bound; a queue's overflow probability over many windows requires additional temporal modeling, not just this single-window calculation.

For the normal distribution $X_{ji}\sim N({\lambda }_j,{\sigma }_j^2)$, completing the square in its density gives the moment-generating functionWrite $m={\sum }_j{n}_j{\lambda }_j$ and $v={\sum }_j{n}_j{\sigma }_j^2$ for the aggregate mean and variance. The exponential-moment capacity condition becomesFor $v>0$, the last two terms are minimized at $s=\sqrt{2\gamma /v}$, where their sum is $\sqrt{2\gamma v}$. Therefore Gaussian effective bandwidth yields the sufficient conditionEquivalently, optimizing the exponential bound directly when $C>m$ gives $\exp [-(C-m{)}^2/(2v)]$; when $C\le m$ the best nonnegative-$s$ bound is one. The square-root condition is sufficient rather than necessary because an exponential bound does not equal the exact normal tail.

For the exact condition, independence and multiplication of the normal moment-generating functions show that $X\sim N(m,v)$. For $v>0$, let $\Phi$ be the standard normal distribution function. The normal law is continuous, soSince $\Phi$ is continuous and strictly increasing from zero to one, the exact Gaussian overflow constraint isThe constant depends only on the desired tail exponent $\gamma$, not on the source counts. It is positive when $\gamma >\log 2$, zero when $\gamma =\log 2$, and negative when $0<\gamma <\log 2$. For example, at $\gamma =\log 100$ the exact normal quantile is about $2.32635$, whereas the Chernoff bound uses $\sqrt{2\log 100}\approx 3.03485$; the latter reserves more capacity.

Finally, the positive-variance hypothesis must not be hidden. If $v=0$, then $X=m$ almost surely, and the zero-variance boundary of an overflow constraint gives $\mathbb{P}(X\ge C)=1_{\{m\ge C\}}$. For $\gamma >0$, the exact condition is then $m<C$. In particular $m=C$ does not meet the target even though substituting $v=0$ into the printed non-strict square-root inequalities would allow it. The displayed normal-quantile equivalence applies to nondegenerate Gaussian traffic; the deterministic case requires this strict boundary convention.

For every $s\ge 0$, the pointwise inequality $1_{\{Y\ge 0\}}\le e^{sY}$ holds: on the event the exponential is at least one, and off it the indicator is zero. Taking expected values and then the infimum proves the Chernoff boundAn infinite exponential moment merely gives a vacuous bound at that $s$; no existence assumption on moments is needed for this extended-value inequality.

For a positive $s$ at which the relevant moment-generating functions are finite, apply the Chernoff bound to $Y=Z-C$. Independence of the sources givesThusClasses with $n_j=0$ make no contribution, so no moment assumption on those inactive classes is necessary. The effective bandwidth ${\alpha }_j(s)$ is the exponential-moment capacity demand of one class-$j$ source over this observation interval. Independent sources have additive effective bandwidths; reserving the margin $\gamma /s$ below capacity certifies the desired overflow bound. If $X_{ji}$ describes traffic during one unit of time, this is a bandwidth in traffic per unit time; for a window of length $t$, divide $\log \mathbb{E}{e}^{sX(t)}$ by $st$ instead.

To establish monotonicity and bounds of effective bandwidth, write $K(s)=\log \mathbb{E}{e}^{sX}$ for a representative source. The Holder inequality gives, for $0<t<s$ in its moment domain,Equivalently, the cumulant-generating function is convex with $K(0)=0$, so its secant slope from zero is nondecreasing. Hence $\alpha (s)$ is nondecreasing, rather than necessarily strictly increasing: if $X$ is deterministic its effective bandwidth is constant.

Assuming the mean is defined and finite, the Jensen inequality gives $\mathbb{E}{e}^{sX}\ge e^{s\mathbb{E}X}$, hence $\alpha (s)\ge \mathbb{E}X$. LetFor finite $M$, $X\le M$ almost surely, so $\mathbb{E}{e}^{sX}\le e^{sM}$ and $\alpha (s)\le M$. Combining these provesThe upper bound is vacuous if the essential supremum is infinite. For nonnegative traffic these comparisons also make sense with extended values; for an arbitrary real-valued source with undefined mean, the printed mean comparison itself requires an integrability qualification. The positive parameter domain is essential: $\alpha (0)$ is defined only by a limit when the appropriate moment assumptions hold, and the stated monotonicity comparisons concern $s>0$.

An effective bandwidth converts a traffic distribution and a quality-of-service requirement into a capacity requirement, penalizing bursts as well as mean load. Let $X\ge 0$ be the traffic generated in one observation interval and assume its moment-generating function is finite for some positive parameters. Write $\Lambda (s)=\log \mathbb{E}[e^{sX}]$. The Chernoff bound follows immediately from Markov's inequality applied to $e^{sX}$:Optimizing gives $\boxed{\mathbb{P}(X\ge b)\le \exp [-\underset{s>0}{\sup }\{sb-\Lambda (s)\}]}$, where the supremum is restricted to finite exponential moments. This exhibits the effective bandwidth as the load appropriate to exponential tail control, not an extra physical stream of traffic.

For the mean and peak limits of effective bandwidth, if exponential moments exist near zero, the cumulant-generating function expansion isFor small $s$, $\boxed{\alpha (s)\to \mathbb{E}X}$, with the variance giving the first burstiness correction. convexity of $\Lambda$ and $\Lambda (0)=0$ show that its secant slope $\alpha (s)$ is nondecreasing; Jensen's inequality also gives $\alpha (s)\ge \mathbb{E}X$.

If $X$ is bounded with essential supremum $M$, then $\alpha (s)\le M$. For any $a<M$, the probability $p_a=\mathbb{P}(X>a)$ is positive andLet $s\to \infty$ and then $a\uparrow M$. For large $s$, $\boxed{\alpha (s)\to \mathrm{esssup}X}$, so very stringent exponential tail control approaches peak provisioning. If traffic is unbounded and every positive exponential moment is finite, the same lower-bound argument gives $\alpha (s)\to \infty$. If exponential moments cease to exist beyond a finite parameter, $\alpha$ is infinite there; one cannot assign a finite large-$s$ peak interpretation to that traffic.

For example, deterministic traffic $X=d$ has $\alpha (s)=d$. A burst of size $b$ with Bernoulli distribution probability $p$ giveswhich moves from $pb$ to $b$. For Poisson packet count of mean $\lambda$ and packet size $b$, $\alpha (s)=\lambda (e^{sb}-1)/s$, showing a mean limit $\lambda b$ but no finite peak limit.

For independent traffic sources, logarithmic generating functions add, so effective bandwidths add. For arrivals $A_r(t)$ in a window of length $t$, use the rate-valued definition ${\alpha }_r(s,t)=\log \mathbb{E}[e^{s{A}_r(t)}]/(st)$. A resource with rate capacity $C$ then satisfiesThus a sufficient admission condition for a target probability $\epsilon$ is ${\sum }_r{\alpha }_r(s,t)\le C-\log (1/\epsilon )/(st)$ for some $s>0$. Independence is needed for this additive form; correlated sources require the joint exponential moment.

A queue involves a supremum over time windows, not merely one fixed window. For independent identically distributed discrete-time traffic increments $X_i$, constant service $C>\mathbb{E}X$, and stationary workloadthe workload Chernoff bound for independent increments follows from a union bound:, whenever $a(s)=e^{\Lambda (s)-sC}<1$,The requirement is precisely $\alpha (s)<C$. This explains why effective bandwidth is useful for buffer and delay design: the relevant time scale and tail parameter depend on the service rule and target overflow risk. A single-window bound cannot be silently substituted for an infinite-horizon workload bound.

For any $s\ge 0$, on the event $Y\ge 0$ one has $e^{sY}\ge 1$. The Markov inequality therefore gives $P(Y\ge 0)\le \mathbb{E}{e}^{sY}$, including the trivial value one at $s=0$. Taking the infimum proves the Chernoff bound.

For $s>0$ with finite moment-generating functions, independence givesConsequentlyAn effective bandwidth is an exponential-moment measure of demand at a chosen tail parameter $s$: independence makes these quantities additive. The spare capacity $\gamma /s$ pays for the desired exponential tail bound. For a cumulative-demand process over time $t$, the corresponding bandwidth would be $\log \mathbb{E}{e}^{sX(t)}/(st)$; here the time horizon is one. It is generally larger than mean demand because it charges for fluctuations, and mathematical optimization over $s$ selects the useful tradeoff.

For independent normal distributions, putThe Gaussian effective bandwidth is ${\alpha }_j(s)={\lambda }_j+s{\sigma }_j^2/2$. For $\gamma >0$ and $v>0$, the sufficient condition becomes $m+sv/2+\gamma /s\le C$. Its left side is minimized at $s_{\ast }=(2\gamma /v{)}^{1/2}$, givingThis is a sufficient Chernoff safety margin, not the exact normal tail quantile.