Cheng-Shang Chang, Yu-Hao Hsu, Jay Cheng, and Duan-Shin Lee
Institute of Communications Engineering, National Tsing Hua University
Published in IEEE INFOCOM 2009
Abstract:A Combined Input and Crosspoint Queueing (CICQ) switch is a switch that has both buffers at the crosspoints of the switch fabric and buffers at the inputs. Inspired by the fixed frame-based algorithm for an input-buffered switch in [19] and the smooth scheduling algorithm for a CICQ switch in [11], in this paper we propose using a dynamic frame sizing algorithm for a CICQ switch. It is formally shown that such a CICQ switch indeed achieves 100% throughput for certain Poisson-like traffic models. This is done without using the framed Birkhoff-von Neumann decomposition needed in [19]. Moreover, such a CICQ switch only requires a two-cell buffer at each crosspoint when there is only unicast traffic. Unlike input-buffered switches, the dynamic frame sizing algorithm also achieves 100% throughput in the setting of multicast traffic. This is done at the cost of increasing the buffer size at each crosspoint.
Index Terms —
Combined input and crosspoint queueing, input-buffered switches, 100% throughput.
Mentioned in abstract:
[11] He, “On guaranteed smooth switching for buffered crossbar switches,”
[19] Neely, “Logarithmic delay for N × N packet switches under the crossbar constraint,”

---

Introduction

• One of the most salient features of crosspoint buffered switches: decoupling property of the scheduling policies between inputs and outputs. Buffers at the crosspoints provide additional flexibility for designing scheduling policies in the input/outputs of crosspoint buffered switches.
• CICQ: A switch that has both buffers at the crosspiubts and at the inputs
• 提到了一堆CICQ中实现100%通过率的算法
• This paper proposes another approach to achieve 100% throughput in an N*N CICQ switch.
  注意：该文重点是实现100%通过率，和可变dynamic frame sizing，而我的重点是避免头分组阻塞吗，分清侧重点，借鉴有用部分
• 本文结构：
  • Section Ⅱ：IQ , frame-based, UNIcast, 100% throughput
  • Section III : extend to CICQ, frame-based, Unicast, 100% throughput
  • Section Ⅳ：CICQ, frame-based， MULTIcast， 100% throughput
    （with the help if the smooth scheduling policy in [11])\
• Key Idea: to operate the system in frames and clear up all the backlogs that appear in the input buffers at the beginning of a frame before the end of that frame.
• Nice features:
  (i)it achieves 100% throughput for certain Poisson-like traffic
  models
  (ii) it only requires a finite buffer at each crosspoint,
  (iii) it is also applicable to the setting with multicast traffic,
  (iv) there is no need to carry out the framed Birkhoff-von
  Neumann decomposition in [19].

Basic Assumption:

• packets are of the same size
• time is slotted in every link so that a packet can be transmitted within a time slot
• time starts from 0 with an empty system
• packet arrives since time 1(including time 1)

Section Ⅱ

Dynamic Frame Sizing Algorithms for Input-Buffered Switches

• Introduce the dynamic frame sizing algorithm and show it achieves 100% throuput in an IQ switch( VOQ).

• Symbols: 都是N*N矩阵,带上下标表示其中一个元素，表示的都是packet的数目！
  

  Symbols1

• Frame size is determined by the minimum clearance time at the beginning of every frame

• minimum clearance time : the minimum amount of time to clear all the packets currently stored in VOQs if there are no future arrivals, maximum of the { (maximum column sum) and (maximum row sum) } of the matrix :
  

  minimum clearance time
  第一个是最大的行和，表示缓存packet最多的那个输入端口的分组数
  第二个是最大的列和，表示前往分组最多的那个输出端口的分组数
  由于每个时隙，输入/输出端口都只能传递一个分组，所以这个定义了最少清空时间

分析推导

本节下面就是基于各种traffic model来证明frame size的bound

比如：

• Bernoulli traffic model：

  
  Bernoulli traffic model

Section III

FROM INPUT-BUFFERED SWITCHES TO CICQ SWITCHES

• The need for carrying out the framed Birkhoff-von Neumann decomposition(IN SECTION 2） can be avoided by using Combined Input and Crosspoint Queueing (CICQ) switches as previously proposed in [11] for providing guaranteed rate services in CICQ switches.
• The EDF policy is the policy that serves the packet with the earliest deadline among all the packets in the buffer in every time slot (ties are broken arbitrarily)
  提出了调度算法（注意这一节针对的依然是unicast）

Section Ⅳ

CICQ SWITCHES WITH MULTICAST TRAFFIC

• The main objective of this section is to show that our dynamic frame sizing algorithm also achieves 100% throughput for CICQ switches with multicast traffic. However, this is at the cost of increasing the buffer size at each crosspoint.

• 加大了buffer的容量，其他类似

  
  CICQ for multicast

Section V Simulation

Section VI Conclusion

基本复述了摘要
There are several problems that require further study: (i) variable length packets, (ii) long range dependent input [15], (iii) networks of CICQ switches, and (iv) the use of network coding [16].

本文的核心主要还是在证明这种变帧长的方法对于不同情景可以实现100%通过率，除了对一些变量的数学表示可以借鉴一下，总体来说可以借鉴的东西不是很多，思考角度完全不一样。（也许是因为没读懂）
准备读下[11] He, “On guaranteed smooth switching for buffered crossbar switches,” 看下情况