计划：

    1. 浏览目前多篇相关文献，找出与研究课题最相关的、可能值得借鉴的内容。

        1）[2005]输入排队结构交换机分组调度研究 

                    熊老师综述 建立总体认识

        2）师兄提供的papers

                    文件分类：分组调度-理想信道-固定长度-组播-调度算法-IQ-Best Effort

    2. 重读三篇硕士博士论文。

实施情况：

2/27下午：实验室电脑安装必要软件

晚上：读熊老师综述

2/28 :

1. 浏览文件夹中所有文献的abstract，找出与FIFO，帧分组相关的文章

2.重读熊老师综述

3. 阅读相关的文章

3/1 Plan

1.详细了解[1997]A High Performance Cell Scheduling Algorithm in Broadband Multicast Switching Systems的算法 特点：cell split，frame-based

2.再读一篇相关

3.IEEE以CICQ, frame-based，switch为keyword查找文献，找出相关——发现Chang的貌似很先进，从他的paper里找需要的？

3/2 3/3

阅读：

Chang，A Dynamic Frame Sizing Algorithm for CICQ Switches with 100% Throughput

Lien，Chang. Generalized dynamic frame sizing algorithm for finite-internal-buffered networks. Oct,2009.

总结

1. 这段时间主要详细了解了两种frame-based的方法。

    1)Wen-Tsuen Chen主要用了cell-splitting的方法使得一个cell里的packet（文章里用的copies of the cell，为什么？是copy了地址吗？）可以拆分开传输,来缓解HoL Blocking，感觉比较接近熊老师给的思路

    2)Chang等人主要提出动态帧长的策略，重点对通过率，crosspoint的buffer大小，frame size等变量的bound给出了证明

2.积累了一些调度算法如最大扇出优先、最匹配优先、最大服务率优先等

3. 还没读到重点关于对分组顺序控制的文章，需要再积累。 另外 “分组顺序”的具体含义再明确一下？

        信元（Cell）：分组交换网络中，数据都是以分组的形式在网络中传输的。分组的长度可以固定也可以改变，其中将长度固定的数据分组称为信元。

        我的理解是，multicast情况下，一个cell里会有多个packet，每个packet要发往不同的output。 

        如果信元就是定长的分组，分组顺序具体指的是什么的顺序？cell的顺序/发往每个输出端口的packet 的顺序？

    所谓multicast指的是一个信元（cell，分组）的目标是多个outut port， 交换机将其复制多份给每个目的端口发一份。比如一号输入端口到达一个分组p，其目的地是1，2，4号输出端口，交换机就将其复制三份，给1，2，4号各发一份。

    所谓fan-out splitting 就是说p的目的地是1，2，4；但是同一个time slot中1，2，4不都是空闲的，比如4号被其他输入端口的分组占用了，那么这个时隙就先发给1和2 output， 1->4这个调度就放在下一个time slot或者更后面执行。

    控制分组失序： 一般认为从同一个输入端口输入，并且扇出相同的分组是同一业务（也可以自己定义），比如1—>1,3,4 ， 2->1，3，4和它就不是同一业务。只要保证统一业务的分组没有失序就ok。 一般两大思路：输入调度的时候不乱序 or 输出的时候重新排序。

    基于帧的调度：确定一个帧长，比如10，那就是10个分组（cell）作为一帧，一次把一帧内的cell调度顺序都安排好，再安排下一帧。那么我们的思路可以考虑在同一帧内的cell先找出同一业务的cell，他们之间的相对顺序不能变化，然后以其他的多可以换顺序，使交换机尽量工作保持。

4. 文件夹中读了摘要认为相关但还没详细阅读的paper：

【1997】Multicast Scheduling for Input-Queued Switches

【2001】On the Throughput of Input-Queued Cell-Based Switches with Multicast Traffic

【2002】Multicast scheduling for switches with multiple input-queues

【2009】A Multiple Slot Cell Scheduling Algorithm for Multicast Switching Systems

【2011】Multi-Level Round-Robin Multicast Scheduling with Look-Ahead Mechanism（look ahead 是什么）

【2016】Non-blocking frame based multicast scheduler for IQ switches(比较相关，重点读）

以下部分为阅读笔记

[2005]输入排队结构交换机分组调度研究 

熊老师综述 建立总体认识

研究对象：单播业务，固定长度分组

VOQ中分组调度算法三类： cell-based， permutation-based，frame-based

    均匀业务:通常采用极大数目匹配法(MSM, Maximal size matching）

    非均匀业务：通常采用基于权重的匹配

    对可接入业务（输入输出端口分组平均到达率不大于线速），最大权重匹配法可达到100%通过率

CICQ 结构也被称为IQ-BXP (IQ with buffered cross-point)结构

[1997]A High Performance Cell Scheduling Algorithm in Broadband Multicast Switching Systems

Wen-Tsuen Chen

Therefore, HOL blocking may occur due to FIFO input queuing discipline. To avoid HOL blocking, our algorithm relaxes the strict FIFO queueing discipline for input queue to increase its throughput.

One-shot discipline VS Cell splitting discipline

This paper: 1. cell splitting discipline. 2. Relaxes the strict FIFO ququeing discipline, but the sequence of cells is still preserved!  3.Every multicast cell scanned only 1 time.

Compared with: Window Policy

# Problem Formulation

Traffic Matrix

用一个 N*N 的Traffic Matrix 用来描述目前队列中排队情况：

        h：第 h 个 time-slot；

        ：第 i 行，第 j 列格子里的数字。表示在第 h 个time-slot时，从第 i 个输入端口，有多少个去往第 j 个输出端口的copy；      另外，由于每一个time slot只传输一个copy到一个output port，所以也表示了传输这些cells里的所有copies所需要的time slot 个数。

Switching Matrix

用一个 N*N 的 Switching Matrix  来描述每个时隙的调度情况：

        k： 第 k 个time-slot

        : 第 i 行，第 j 列的元素。只能为1或0。 为1时表示有从输入端口到 i 到输出端口j的调度(cell?)。 

        注意：

            1. 每一列最多有一个非零元素，否则会有output conflict。 

            2.switching fabric 是multicast functionality的，一个组播cell里的多个copies可以在一个time slot里传输给交换机网络——每一行里可以有多个非零元素。

引入了一个dummy traffic matrix来描述一个frame中剩余可调度的空间的情况，避免了每次重新扫描排队分组，降低了复杂度。

HOW to preserve the sequence?

文章说的是 preserve the sequence of cells 但是并没有具体分析

算法是否是保持了顺序的呢？ 如何证明？

总结：本文对分组拆分的建模和算法有点意思，也许可以借鉴，但是如何保持顺序没有具体分析，看看后续文献有没有。

2013基于CICQ结构的多播交换技术研究

董林林

1、在每个输入端口要分别为单播和多播信元设置多个地址队列，用来相应地存储单播信元和多播信元的地址，也即信元的指针。另外专门设置一个单独的信元存储队列，用来缓存所有到达的信元。每个输入端口还要设置一个多播状态字队列，以对多播调度进行有效的管理。

2、为了解决HOL阻塞，很多算法采用扇出分割来提高吞吐量。但这篇文献不使用扇出分割的思路。作者认为，组播信元需要扇出分割说明该信元不能一次性发送到目的端口，是冲突的体现，所以应该直接解决冲突问题。解决思路是尽量让输入端口的组播信元能够一次性完全输出，尽量减少扇出分割。（思考：这个逻辑感觉有点奇怪？？直观上并不能感觉到可以缓解HOL BLOCKING）

3、改进了传统的CICQ结构的crossbar，在每个交叉结点处增加了一个行向量寄存器SR来记录交叉结点缓存了多少个信元，作为信息传递给输入输出接口，增加输入输出调度的协同性。

4、提出了以下调度策略

    1）最大扇出优先-轮询调度（MF-RR）

        输入最大扇出，优先选扇出数目最多的组播信元。优点1.降低扇出大的信元的时延（思考：那fan-out小的信元就不管了？？）2.可以尽快占满交叉结点缓存，输入尽快输出，输入端口可获得最大扇出机会（思考？？？）

        输出轮询。

最大扇出优先-轮询调度（MF-RR）

    2）最大扇出优先-最匹配优先调度（MF-MM）

最大扇出优先-最匹配优先调度（MF-MM）

3）最大扇出优先-最大服务率优先调度（MF-MRSF）

        输入使用最大扇出优先，接下来，分别计算各个多播地址队列队头指针所指向多播信元的服务率，选择具有最大服务率的活动信元发送到相应交叉点缓存。为了公平性考虑，计算各个多播地址队列对应信元服务率时要轮询进行。在输入端口采取最大服务率优先的调度方案是优先选择可以一次性完全扇出的多播信元，若一个多播信元不需要进行扇出分割而可以一次性发送到交叉点缓存，就避免了输入口的冲突，也就解决了队头阻塞问题。

最大扇出优先-最大服务率优先调度（MF-MRSF）        

        (思考： 1. 既然是选择最大服务率，那轮询计算服务率对公平性有何意义？反正都是全部算一次进行比较.  2. 不进行扇出分割就避免了队头阻塞？？这什么逻辑？扇出分割是为了解决队头阻塞的方式之一，而不是阻塞的标志啊！ 3.最大服务率怎么算？)

总结：1. 本文的逻辑目前还不太能够理解，但是它提出的一些调度算法可以作为知识储备。

            2.关于对信元分配地址队列的方式是否常用？

A Dynamic Frame Sizing Algorithm for CICQ Switches with 100% Throughput

Chang

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 and the smooth scheduling algorithm for a CICQ switch, 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. 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.

The key idea of our dynamic frame sizing algorithm is 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.( 应该就是说以frame为单位进行操作，在一帧里干掉所有的backlog）

Bound：As long as the traffic is admissible,the expected frame size is shown to have an O(logN) bound

为了实现Dynamic frame sizing(DFS）algorithm，之前需要执行the framed Birkhoff-von Neumann decomposition [5]，复杂度较高O(N^2.5 T)，并且在输入缓存结构的交换机中必须使用。本文采用[11]提出的 a smooth scheduling policy，复杂度O（logN），是基于CICQ结构提出的，可以实现100% throughput

优点总结： To summarize, an N × N CICQ switch with the dynamicframe sizing algorithm has the following nice features: 

    (i)it achieves 100% throughput for certain Poisson-like trafficmodels, 

    (ii) it only requires a finite buffer at each crosspoint,

    (iii) it is also applicable to the setting with multicast traffic,and (iv) there is no need to carry out the framed Birkhoff-vonNeumann decomposition in [19].

采用结构：

CICQ 

调度算法：

Step1： Determine the size of a new frame: 

The size of the frame is set to be:

size of new frame

     : the number of packets in the VOQ of the  input at time 

    : the last time slot of the (n−1)th frame

    be the beginning time slot of the nth frame).注意这个是第n个frame 的第一个time slot

Step2: Schedule packets in the VOQs with the rates proportional to their sizes at the beginning of a frame consider the ith input. 在VOQ中生成tokens，分配一个eligible time和一个deadline，用Earliest Deadline First(EDF) Policy,在N个eligible tokens中选择earlist deadline，复杂度O（logN）。 

    问题： 所谓的tokens是什么？

Step3:  Schedule packets in the crosspoint buffers with the same rates of their corresponding VOQs consider the jth output. 把上面那个过程重复一遍（所以其实这个策略可以应用于多级网络，而不仅仅是CICQ，作者之后一篇文章就将这个方法推广到了一个generalized的网路结构。）

An illustrating example of the scheduling algorithm for q~i,j=3 and Tn=10.

The eligible times of these three tokens are marked with “×”.

The time slots marked with “ □ ”  are the time slots when the tokens for the jth VOQ of the ith input are served. 

The time slots marked with “◦” are the time slots when the tokens for the (i, j)th crosspoint buffer are served.

总结：

    本文的方法是frame-based，核心在于可以使frame 的长度动态变化因此不需要提前知道业务非类型或者强度。从IQ过渡到CICQ，还对几种业务类型进行了数学描述并基于此进行证明

    本文的重点是各种证明如1.在几种场景下可以达到100% throughput。 2. crosspoint 的 buffer size 的bound 数学证明较多，比较复杂，目前还没有特别看懂，需要结合引用的文献继续深入阅读，特别是：[11] S.-M. He, S.-T. Sun, H.-T. Guan, Q. Zheng, Y.-J. Zhao, and W.Gao, “On guaranteed smooth switching for buffered crossbar switches,” to appear in IEEE/ACM Transactions on Networking， 2008。 这篇文章里面提出了本文一直使用的EDF ALGORITHM.

    对于初步的理解可以先阅读Lien，Chang. Generalized dynamic frame sizing algorithm for finite-internal-buffered networks. Oct,2009.  将本文说的算法应用与一种更普遍的网络结构，证明少一点，思路描述多一点，更好理解。（已读）

    似乎也没有考虑分组顺序的问题？

    需要思考dynamic frame的方式是否适用于卫星通信背景。

一些基本的概念

REF:2013基于CICQ结构的多播交换技术研究_董林林

信元（Cell）：分组交换网络中，数据都是以分组的形式在网络中传输的。分组的长度可以固定也可以改变，其中将长度固定的数据分组称为信元。

输入端口（Input port）：输入端口通常设置在线卡（Line Card）上，是数据分组进入交换系统的入口。数据分组到达输入端口时要根据一定的策略进行排队缓存，并按照一定的规则进入交换单元进行处理。

线路速率（Line rate）：一般用R表示，指的是交换系统外部链路的传输带宽，单位通常为bps。

时隙（Time slot）：时隙是指以线路速率R传输一个固定长度的信元所需要的时间。在基于定长信元的交换系统中，调度算法都是以时隙为基本单位。

交换单元：输入端口和输出端口之间连通的链路，是交换系统的核心单元。调度算法都是基于一定的交换单元进行业务的调度。

加速比（Speedup）：指的是交换系统内部链路的传输速率与外部链路传输速率的比值。对于交换系统来说所需求的加速比越小越好。

输出端口（Output port）：经过交换系统处理的信元从输出端口输出发送到外部物理链路，对于输出端口有缓存的交换系统信元输出交换系统时要先缓存在输出端口等待处理。

交叉开关（crossbar）：一般称作交叉开关矩阵或纵横式交换矩阵，是一种内部无阻塞的交换单元，输入端口和输出端口有多条可用的路径连接起来，在目前交换网络中得到广泛应用。

性能指标

1．时延： 是指一个信元从到达交换结构输入端口开始计时，到从输出端口输出该信元所需的平均处理时间。时延特性可分为平均时延和最大时延，平均时延指交换结构处理所有信元的时延的平均值，最大时延是指通过交换结构的所有信元中时延最大的那个信元的时延值。时延特性体现了交换系统对不同业务模型的服务质量。优秀的调度算法应当能在各种流量模型下提供端到端的时延保证。

2、吞吐率 ：吞吐率是指在一定时间内交换系统处理的信元总数与业务源所产生的信元总数的比值，其值在“0”和“1”之间。吞吐率体现了交换结构处理数据分组的能力与交换系统资源利用的效率，优秀调度算法应当具有高吞吐率的特性。

3、丢包率（drop rate）是指一定时间内交换系统丢弃信元的数目与通过交换系统的信元总数目的比值。输入端口每个VOQ队列的容量是有限的，当交换系统处理信元的速率跟不上信元的到达速率时，VOQ队列可能会出现溢出，出现丢包的情况。在实际应用中增加VOQ队列长度可以减小丢包率，但是会导致时延和交换设备成本的增加，因此应综合考虑，采用合适的存储队列长度。

4、稳定性要求交换系统在容许的流量模型下，对存储队列资源的要求不会趋于无限大。稳定性是系统鲁棒性（robustness）的体现，是系统在各项参数发生变化时仍能维持服务质量保证的特性。

5、公平性（fairness）指所有输入端口的信元队列都应当获得公平合理的调度机会，即链路资源要平等的分配给各个业务流，没有某些流接受过度服务而其他流出现“饿死”的现象发生。高性能的调度算法要能够对所有流量模型公平的处理，即使偶尔的高突发性流量也不会对其他正常的流量产生大的影响。