首页> 外文期刊>IEEE/ACM Transactions on Networking >Cell Switching Versus Packet Switching in Input-Queued Switches
【24h】

Cell Switching Versus Packet Switching in Input-Queued Switches

机译:输入排队交换机中的信元交换与分组交换

获取原文
获取原文并翻译 | 示例

摘要

Input Queued (IQ) switches have been well studied in the past two decades by researchers. The main problem concerning IQ switches is scheduling the switching fabric in order to transfer packets from input ports to output ports. Scheduling is relatively easier when all packets are of the same size. However, in practice, packets are of variable length. In the current implementation of switches, variable length packets are segmented into fixed length packets—also knowns as cells—for the purpose of scheduling. However, such cell-based switching comes with some significant disadvantages: (a) loss of bandwidth due to the existence of incomplete cells; and (b) additional overhead of segmentation of packets and re-assembly of cells. This is a strong motivation to study packet-based scheduling, i.e., scheduling the transfer of packets without segmenting them. The problem of packet scheduling was first considered by Marsan They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this paper, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan are strongly dependent on the arrival distribution. Next, we propose a new class of “waiting” algorithms. We show that the “waiting”-MWM algorithm is stable for any admissible traffic using the fluid limit technique. We would like to note that the algorithms presented in this paper are distribution independent or universal. The algorithms and proof methods of this paper may be useful in the context of other scheduling problems.
机译:研究人员对输入排队(IQ)开关进行了很好的研究。与IQ交换机有关的主要问题是调度交换结构,以便将数据包从输入端口传输到输出端口。当所有分组的大小相同时,调度相对容易一些。但是,实际上,分组的长度是可变的。在交换机的当前实现中,出于调度目的,将可变长度的数据包分为固定长度的数据包(也称为信元)。然而,这种基于信元的交换具有一些明显的缺点:(a)由于不完整的信元的存在造成带宽损失; (b)分组分割和信元重组的额外开销。这是研究基于分组的调度的强烈动机,即,调度分组的传输而不对它们进行分段。 Marsan首先考虑了数据包调度的问题,他们表明,在任何允许的Bernoulli IID(独立且分布均匀)的到达流量下,对最大权重匹配(MWM)算法的简单修改即可实现100%的吞吐量。在本文中,我们首先表明,对于任意可允许的到达过程,没有基于工作保存(即最大)数据包的算法是稳定的。因此,Marsan的结果在很大程度上取决于到达分布。接下来,我们提出了一类新的“等待”算法。我们证明了使用流体限制技术,“等待” -MWM算法对于任何允许的交通都是稳定的。我们想指出的是,本文提出的算法是独立于分布的或通用的。本文的算法和证明方法在其他调度问题中可能很有用。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号