计划
1.Michael Tartre and Bill Lin. Frame-Based Multicast Switching. 2010
2. 师兄论文
实施情况
本周做的工作：
1. 读了师兄论文中的机制分析的部分，梁师兄部分比较好理解，袁师兄用数学语言描述，理解难度比较大。
2. 复习了读懂论文需要的一些数学知识如线性代数等
3. frame-based相关的内容。
下周计划：
1. 再读一读 2016 Non-blocking frame-based multicast scheduler for IQ switches和A Dynamic Frame Sizing Algorithm for CICQ Switches with 100% Throughput 可能会有新的理解。
2. 多看几篇frame-based的文章，梳理一下常见的思路和方法，目前已知的是转换为图上色的问题。
3. 明确输入排队队列的结构（N+K or N？） 输入调度算法（frame-based的算法）
4.找师兄咨询实验产生的结果文件怎么看。 争取下周能确定方案并仿真。
袁师兄论文
- 结构配置：N个单播队列，k个组播队列
- Work-conserving： 任一时隙中存在去往某个输出端口的分组，则该时隙必有分组离开该输出端口。
- 由HOL阻塞引起的非work-conserving问题：在调度过程中，属于同一组播队列的分组扇出不完全一致，若组播队列中的后续分组中存在使交换机满足work-conserving状态的扇出去向，二头分组不存在，则发生了头分组阻塞。
- 由于考虑整个组播队列中全部后续分组的扇出过于复杂，本文算法只考虑头分组对次分组的阻塞影响（ 思考： 那我们可以多考虑几个后面的分组作为改进？）
对防止头分组阻塞的机制分析（几个定理）见纸上，有些许问题，整理下问师兄。
Frame-Based Multicast Switching
Tartre， Lin
提到BvN by Chang：
- 100% throughput
- decompoese any admissible traffic matric into convex combination of permutation matricesfor switch configurations.
- O(N^2)
- Partial offline. Online part: PGPS (Packetized Generalized Process Sharing) Algorithm to schedule the generated permutation matrices
When applicable, frame-based decomposition approaches offer several advantages over the BvN approach.
FRAME-BASED OFFLINE MULTICAST SCHEDULING
基于流理论 flow
FOR : integer flow rates, and a fixed frame size, multicast
Formulated as a graph coloring problem
In this queueing model, when a multicast cell receives partial service, the cell is dequeued from its current queue and requeued in the virtual queue corresponding to the residue (the unserviced part of the multicast).
关于Flow theory：
- Flow Def： flow P 由三个变量定义， 源 S， 目的地D， 和flow rate R（R取值为0~1之间实数）
- Conflict Graph冲突图： G = (F,C) F代表所有flow， C表示Flow之间的冲突。 如果(g，h)∈C，则说明flow g和 h在同一个valid switch configuration中不能共存。在图中，每个flow代表一个vertex， 如果两个flow间有冲突，则两个vertex间会有一条edge。 —— 转化为graph coloring 问题
- Conflict：1）Same sources S 2）Overlapping destination D .
(2,1)表示input2—>output1的unicast； 1：[1,2]表示input1->output2,3的multicast
由graph coloring能确定需要的configuration 数 K， 帧长为 T。 则内部需要的加速比speedup为 K/T .
总结：
本文很不错！详细介绍了将frame-based的调度过程转换成graph coloring问题的一种思路和过程，之后就可以用graphing coloring的算法来解决这个问题。比如D. Br´elaz, “New methods to color the vertices of a graph,” Commun. ACM, vol. 22, no. 4, pp, 251–256, Apr. 1979.、
可以再读一读 2016 Non-blocking frame-based multicast scheduler for IQ switches 和A Dynamic Frame Sizing Algorithm for CICQ Switches with 100% Throughput 可能会有新的理解。
初步设计思路：
入队阶段： 使用Module算法，实现简单，速度快；因为后面还会在帧内调整分组顺序，没有必要在入队的时候大费周折。这样的话似乎RR更好？
输入调度阶段：
- 基于帧的调度 帧长 N = 三个值对比效果
- 梳理frame-based算法
输出调度阶段：从非空交叉缓存中，依据权重选取分组调度出交换机。权重设立依据：缓解头分组阻塞。 具体？ EDF? or 等待时间？ 那只要尽量使crossbuffer中均衡似乎就行了。
业务类型： 均匀伯努利、非均匀伯努利、均匀ON-OFF,非均匀ON-OFF
归一化负载：0.9, 0.95, 0.99
指标：平均时延/时隙，通过率
对比算法：MF-MRSF, LCNS， OQ
（这些仿真平台都能直接计算得到）
一个突然想到的关于输入调度的想法：
如果设置N个队列，按照扇出数量进入不同队列，那么不同队列的扇出数量是有互补关系的，比如扇出(N-1）的队列头分组，就可以找一个扇出为1的队列中的分组结合进行调度，即使找不到，那也是这个time slot里扇出最多的选择。也就是说，每一个time slot中
STEP1:从分组扇出最大的队列Q(0<Q<N+1)开始考虑，选取其头分组
STEP2：从扇出为(N-Q)<Q的队列开始考虑，从前往后找队列中能与其互补的分组.IF能找到，分为一组，在同一个time slot里调度， ELSE NEXT STEP
STEP3：以(N-Q-1）,（N-Q-2），，2,1的顺序考虑，在队列中找能兼容的分组，直到扇出为1（单播）的队列都找不到，则这个time slot 只能调度Q的头分组。 注意，在执行的过程中，找到的概率其实是逐渐增大的，要找到合起来扇出为N的扇出比较难，但是找到合起来扇出为Q+1其实很容易。 这里有个选择，假设N=16， Q= 10，现在找到了一个扇出为4的分组结合，那此时一个时隙的扇出已经14很高了，是否还要从fanout=2和1的队列面找合适的？
分析：
1.复杂度。最坏情况就是每次都找不到互补的，与帧长F和端口数N有关，几乎都是平方关系。(F^2 * N^2)?
2.并没有考虑crossbuffer的情况，和研究思路不同。研究思路是缓解头分组阻塞，那最核心的应该是考虑crossbuffer为空的情况，尽量调度那些扇出为空buffer 的分组
3.也没考虑等待时间，会有饿死情况。
问题： 优先级、突发性考虑吗？如何简化近似？
