论文标题
数据包与本地爆发的对手转发
Packet Forwarding with a Locally Bursty Adversary
论文作者
论文摘要
我们考虑了Borodin等人介绍的对抗排队理论（AQT）模型中的数据包转发。我们介绍了aqt $（ρ，σ）$ - 有限的对手的改进，我们称之为\ emph {局部爆发对手}（lba），该（lba）通过边缘利用率和数据包来参数化注射模式。对于常数（$ o（1）$）参数，LBA模型严格比$（ρ，σ）$模型更具允许性。例如，LBA模型中有一些恒定参数的注入模式，只能实现为$（ρ，σ）$ - 有限注入模式，带有$ρ+σ=ω（n）$（其中$ n $是网络大小）。我们表明，LBA模型（与$（ρ，σ）$模型不同）在数据包捆绑和离散操作下关闭。因此，LBA模型允许人们减少对具有同质数据包的单位容量网络的一般（统一）容量网络和不稳定数据包的研究。 在算法方面，我们专注于信息收集网络 - 即所有数据包共享一个共同目的地的网络，并且数据包路由的结合形成了树。我们表明，Dobrev等人\ \ \和Patt-Shamir和Rosenbaum独立描述的奇数下坡（OED）转发协议可实现$ o（\ log n）$的缓冲空间使用情况，该$（\ log n）$与具有恒定参数的所有LBA。 OED是局部协议，但我们表明，即使与集中协议相比，上限也很紧。我们对LBA模型的下限与$（ρ，σ）$ - 模型相反，其中集中协议可以实现最差的案例缓冲空间使用$ o（1）$ o（1）$ for $ρ，σ= o（1）$，而$ O（\ o（\ log log n）$上限OED的OED仅适用于本地协议。
We consider packet forwarding in the adversarial queueing theory (AQT) model introduced by Borodin et al. We introduce a refinement of the AQT $(ρ, σ)$-bounded adversary, which we call a \emph{locally bursty adversary} (LBA) that parameterizes injection patterns jointly by edge utilization and packet origin. For constant ($O(1)$) parameters, the LBA model is strictly more permissive than the $(ρ, σ)$ model. For example, there are injection patterns in the LBA model with constant parameters that can only be realized as $(ρ, σ)$-bounded injection patterns with $ρ+ σ= Ω(n)$ (where $n$ is the network size). We show that the LBA model (unlike the $(ρ, σ)$ model) is closed under packet bundling and discretization operations. Thus, the LBA model allows one to reduce the study of general (uniform) capacity networks and inhomogenous packet sizes to unit capacity networks with homogeneous packets. On the algorithmic side, we focus on information gathering networks -- i.e., networks in which all packets share a common destination, and the union of packet routes forms a tree. We show that the Odd-Even Downhill (OED) forwarding protocol described independently by Dobrev et al.\ and Patt-Shamir and Rosenbaum achieves buffer space usage of $O(\log n)$ against all LBAs with constant parameters. OED is a local protocol, but we show that the upper bound is tight even when compared to centralized protocols. Our lower bound for the LBA model is in contrast to the $(ρ, σ)$-model, where centralized protocols can achieve worst-case buffer space usage $O(1)$ for $ρ, σ= O(1)$, while the $O(\log n)$ upper bound for OED is optimal only for local protocols.
