挠度补偿提升Birkhoff-von-Neumann开关性能应对突发流量

150 浏览量更新于2024-08-27 收藏 199KB PDF 举报

挠度补偿的Birkhoff-von-Neumann (D-BvN) 开关是一种针对高带宽需求和突发流量处理的创新设计，特别是在光通信系统和网络中。传统的Birkhoff-von-Neumann (BvN) 方法基于矩阵分解的静态调度策略，其优点在于能够实现高吞吐量和较低的运营复杂性。然而，当输入流量呈现突发性时，其性能预测性会受到影响。 D-BvN 开关的核心理念是结合平均输入流量矩阵的BvN 分解和挠度（Deflection）机制，以提供对每个虚拟电路（VC）的容量保证。它通过预先分析和分解输入流量模式，为每个VC 分配资源，确保在正常流量条件下保持高吞吐率。对于突发流量，D-BvN 采用一种智能的挠度调度策略。当某个VC 接受超出其预留带宽的流量时，这部分溢出流量会被引导到其他VC，同时为这些转移流量提供额外的带宽，允许它们“回弹”（deflection）并重新路由到它们的目标VC。这种挠度补偿策略有助于平滑流量波动，确保在突发流量期间，整体系统的吞吐量仍然接近于100%的承诺负载。此外，D-BvN 开关的设计也考虑到了数据包序列完整性，通过精心设计的调度算法，降低了数据包出序（out-of-sequence）的概率，从而提高了服务质量。通过理论分析和模拟实验，D-BvN 开关证实了其在应对突发流量挑战、维持高吞吐量和低延迟方面的有效性。这对于现代数据中心、云计算环境和高度动态的网络架构来说，是一项重要的技术突破，有助于提升网络的整体性能和稳定性。研究人员Jinghui Zhang、Tong Ye、Tony T. Lee、Fangfang Yan 和 Weisheng Hu，来自上海交通大学的先进光学通信系统与网络实验室，共同开发了这一创新技术，并可以通过电子邮件{zjhrzbb,yetong,ttlee,yff,wshu}@sjtu.edu.cn联系他们获取更多细节或合作。

Deﬂection-Compensated Birkhoff-von-Neumann

Switches

Jinghui Zhang, Tong Ye, Tony T. Lee, Fangfang Yan, and Weisheng Hu

State Key Laboratory of Advanced Optical Communication Systems and Networks

Shanghai Jiaotong University, Shanghai, China

{zjhrzbb, yetong, ttlee, yff, wshu}@sjtu.edu.cn

Abstract—Although the quasi-static scheduling based on

Birkhoff-von-Neumann (BvN) decomposition can achieve high

throughput with low operational complexity, its performance

becomes less predictable when the input trafﬁc is bursty. In this

paper, we propose a deﬂection-compensated BvN (D-BvN) switch

to enhance the performance. The D-BvN switch provides capacity

guarantee for each virtual circuit (VC) by the BvN decomposition

of average input trafﬁc matrix, while copes with trafﬁc burst

by deﬂection. In particular, deﬂection scheme fully utilizes the

spare capacity of starving VCs to deﬂect overﬂow trafﬁc to other

VCs and provide bandwidth for deﬂection trafﬁc to re-access its

desired VC. Analytical and simulation results show that it can

achieve close to 100% throughput of offered load and the packet

out-of-sequence probability is also negligible.

Index Terms—input-queued switch, Birkhoff-von-Neumann

switch, scheduling, deﬂection, burst trafﬁc

I. I NTRODUCTION

A good scheduler is indispensable for input-queued switch-

es to maximize throughput, reduce end-to-end delay, and lower

computational complexity.

In the past few years, a number of on-line algorithms [1]–[5]

were designed to assign connection patterns of the switching

fabric according to input packet requests on the ﬂy. Although

these on-line algorithms can achieve 100% throughput, they

are not scalable when the number of input ports N and the

line rates are large.

Path switching, a quasi-static algorithm, was proposed in [6]

in order to provide capacity guarantee without computation

on the ﬂy for each input/output (I/O) pair, or virtual circuit

(VC). Later in [7], it was also called Birkhoff-von-Neumann

(BvN) switching. In this algorithm, switch connection patterns

are periodically assigned according to a set of predetermined

permutation matrices calculated by average input trafﬁc ma-

trix. The scalability is enhanced since connection patterns are

not computed on the ﬂy. Also, [8] shows that this algorithm

can achieve 100% throughput and bounded end-to-end delay

as long as the input trafﬁc is bounded by an arrival curve

[9].However, if the input trafﬁc is bursty, the performance of

BvN switches becomes less predictable.

To deal with bursty trafﬁc, [10], [11] introduce a two-stage

load-balanced BvN (LB-BvN) crossbar switch. The trafﬁc

is evenly distributed to all outputs in the ﬁrst stage and

N circular-shift permutations are repeatedly running in the

second stage. Thus, it has a complexity on the order of O(1)

and is able to cope with any trafﬁc pattern. However, this

algorithm results in severe packet out-of-sequence at the output

even when the input trafﬁc is smooth. Then, a number of

amendments were proposed to tackle this problem. However,

these methods require either additional hardware [12], [13] or

higher computational complexity [11], [14].

In this paper, we introduce a trafﬁc deﬂection-compensated

mechanism to enhance quasi-static scheduling based on BvN

decomposition. Unlike immoderate trafﬁc distribution in the

LB-BvN switches, only the overﬂow burst trafﬁc is deﬂected

in our mechanism, thus the out-of-sequence probability is

signiﬁcantly lowered. Besides, our algorithm can achieve close

to 100% throughput of the offered load and requires lower

end-to-end delay.

The rest of the paper is organized as follows. In section II,

we brieﬂy introduce the basic concepts of BvN switches and

discuss their drawbacks due to quasi-static scheduling. Moti-

vated by the discussion, we propose a deﬂection-compensated

switch architecture and the related scheduling algorithm. In

section III, the performance of our proposal is analyzed by

Markovian modulated ﬂuid-ﬂow model of input trafﬁc and

ideal deﬂection approximation. Analytical and simulation re-

sults of minimum VOQ size requirement and out-of-sequence

probability are provided. Section IV concludes this paper.

II. P

RELIMINARY AND OUR PROPOSAL

A. BvN switch

An N × N BvN switch is plotted in Fig.1(a). N virtual

output queues (VOQs) are equipped at each input, where

VOQ

denotes the VOQ that buffers packets from input

i to output j. The quasi-static scheduling algorithm of the

BvN switch is actually based on the Birkhoff-von-Neumann

decomposition theorem of doubly stochastic matrices [15].

According to the input trafﬁc matrix [λ

]

N×N

, where λ

the average trafﬁc rate from input i to output j, and



≤

1 and



≤ 1, we can always ﬁnd a capacity matrix

]

N×N

that satisﬁes λ

≤ c

and



=1.

Based on BvN theorem [15], [c

]

N×N

can be decomposed

into the linear combination of some permutation matrices,

each of which represents a connection pattern of the switch,

as illustrated in Fig.1(b).

Within a frame of F consecutive time slots, these prede-

termined connection patterns are scheduled according to their

weights in the BvN decomposition, as illustrated in Fig.1(c).

By periodically running these connection patterns, the BvN

____________________________________



下载后可阅读完整内容，剩余4页未读，立即下载

weixin_38631182

粉丝: 8
资源: 954

挠度补偿提升Birkhoff-von-Neumann开关性能应对突发流量

圆形荷载作用下土体的挠度剖面：圆形荷载作用下土体的挠度剖面示例-matlab开发

Abaqus悬臂梁和简支梁挠度数据

弹性地基上的梁 示例：绘制弹性地基上梁在两个集中力作用下的剪力、弯矩、斜率和挠度曲线。-matlab开发

悬臂梁分析：数值求解大挠度欧拉-伯努利梁方程-matlab开发

梁的结构分析。：简支梁的挠度图-matlab开发

剪力、弯矩和挠度绘图工具：绘制简支静定梁的 SF、BM 和挠度。-matlab开发

Indeterminate Beam Analysis Program:计算SF，BM，斜率和挠度。-开源

静定梁的挠度：该程序计算横向加载的静定梁的挠度和斜率。-matlab开发

结构分析：计算框架、桁架、板等各种结构的挠度。-matlab开发

压电薄层挠度的有效建模：显示了一种用于快速计算在n掺杂硅片上生长的压电材料薄层的表面挠度的方法。-matlab开发

最新资源

弹性地基上的梁示例：绘制弹性地基上梁在两个集中力作用下的剪力、弯矩、斜率和挠度曲线。-matlab开发