計劃
在與老師交流后，調(diào)整閱讀重點
1. 重讀袁龍師兄和梁佳誠師兄論文嫁蛇，重點看他們分析問題的部分聂抢。
2. 讀[2016]Non-blocking frame-based multicast scheduler for IQ switches
and?Michael Tartre and Bill Lin. Frame-Based Multicast Switching. 2010
3. 熟悉仿真平臺： 1)了解程序結(jié)構(gòu)，調(diào)用情況? 2）算法的含義
實施情況
3/5：【1997】Multicast Scheduling for Input-Queued Switches?
3/6： 1. 與老師交流棠众，總結(jié)琳疏。 2. lab電腦上安裝VS2017 3. 初步熟悉仿真代碼
3/7： 1.繼續(xù)熟悉仿真平臺，找?guī)熜纸涣?2.讀[2016]Non-blocking frame-based multicast scheduler for IQ switches
3/8-3/10 熟悉平臺闸拿，師兄論文
本周剩余工作空盼，下周繼續(xù)：
1.?Michael Tartre and Bill Lin. Frame-Based Multicast Switching. 2010
2. 袁龍師兄論文
【1997】Multicast Scheduling for Input-Queued Switches?
Prabhakar
- Design of a scheduler of an M x N input-queued multicast switch.
- Assumption:
? ? - 每個input保持single queue for multicast cells
? ? - cell at the HOL 頭分組才能被觀察
- Requirement
? ? -? work-conserving: 只要輸入端有某輸出端口為目的地的cell，該輸出端口不會空閑idle
? ? - fair： 任何cell不會在HOL停留超過一定時間
- Aim
? ? - a work-conserving新荤， fair policy
? ? - maximum throughput揽趾， minimize input queue latency
? ? - simple to implement in hardware
- 思路：
? ? - 當(dāng)輸入端口發(fā)生競爭contention的時候，會有一些剩下的cells（residue）等待在下一個time slot被調(diào)度苛骨。本文認(rèn)為：盡量把這些residue集中（concentrate on）在盡量少的輸入端口篱瞎，會使得policy表現(xiàn)最好。
? ? - Trade-off between 1）concentration of residue（for high throughput） 痒芝，2）fairness（to prevent starvation） and 3）implementational simplicity
? ? - 通過將組播交換調(diào)度問題mapping到 a variation of the popular block-packing game Tetris俐筋， 可以用更intuitive and geometric 的方式分析各種調(diào)度策略。
? ? 什么意思严衬？
- 結(jié)果——調(diào)度策略
? ? TATRA： extrmely well and in strict in fairness
? ? WBA: a simple weight-based algorithm澄者， 易于實施，fair请琳，和concentrating algorithm相比表現(xiàn)良好(意思是比TATRA好粱挡？那前面的工作有什么意義呢）
（未完待續(xù)）
[2016]Non-blocking frame-based multicast scheduler for IQ switches
- What is “circulation of packets?”？
? ? packet流動俄精，調(diào)整里面排隊隊列情況询筏。
The internal multicast tree was proposed in [5]. For each multicast flow, an internal multicast tree is built. The tree’s root node is the flow’s source port and the other tree nodes are the flow’s destination ports. Multicast packet copies are circulated across the corresponding tree. The circulated copies are treated as unicast packets. However, this solution requires at least the speedup of four.
a simple non-blocking frame-based multicast (NFBM) scheduler that can be used for offline scheduling.
Requirement: 1.multicast switching 2. fan-out splitting allowed. 3. circulation of the packets allowed. 4.fixed-size packet(cell), for variable size packet, perform packet segmentation first.
Assumptions: N x N switch,
frame length L,?
Speedup = 2 (thus two packets can be sent from each input port and each output can receive at most two packets during one time slot.)?Since the speedup of two is used, there are 2L configurations to be scheduled in the L consecutive time slots.
Admissible frame (i.e. no more than L received packets at each of the input ports, and there are at most L packet copies for each of the output ports.)
這篇文章主要就是引入了packet circulation，將調(diào)度過程分為兩個階段竖慧，第一階段packet circulation嫌套，將所有input端口的隊列的一幀中的copies均衡為L 個局冰；第二階段就是將調(diào)度作為unicast來處理，應(yīng)用二分圖上色的數(shù)學(xué)理論證明了最多需要L個configuration就能完成單播過程灌危。 兩個階段各自占L個configuration康二，總共占2L個，也就是說在L個time slot中完成2L次調(diào)度就OK勇蝙，所以speedup=2就能完成基于IQ的任務(wù)沫勿。 復(fù)雜度比較大，speedup=3的算法在實際工作中比較好味混。 文章沒有說失序的問題产雹，顯然是會有失序問題的。
那么自然想到對于CICQ情況下翁锡，既然引入crosspoint蔓挖，能否將speedup降到1？ 另外考慮失序問題馆衔，如何處理瘟判？
梁師兄論文
CICQ結(jié)構(gòu)組播調(diào)度問題分析
1. HoL Blocking隊頭阻塞問題：類似VOQ的思想，克服組播隊頭阻塞需要在每個輸入端口設(shè)置(2^N-1)個虛擬組播隊列角溃，在大規(guī)模交換機中難以實現(xiàn)拷获。目前常采用的方法設(shè)置k個（1<k<<2^N-1)個虛擬組播隊列，可以緩解HOL阻塞但是無法解決减细。
2. 分組入隊問題：設(shè)置的k個虛擬組播隊列不能cover所有的fanout類型匆瓜，那么需要按照一定的規(guī)則讓到達(dá)的cell進入某一個隊列。比如1.給每個隊列設(shè)置標(biāo)志扇出向量未蝌，讓最接近的進入該隊 或者2.Modulo算法驮吱。? 還可以考慮隊列之間的調(diào)整問題，比如上面那篇文章的packet circulation萧吠。
3. 單組播競爭裁決問題： 如果是單播和組播分別設(shè)置隊列進行排隊左冬，就需要在入隊之前考慮判斷是單/組播。 如果是把單播作為組播的特殊情況怎憋，應(yīng)該就不需要考慮該問題又碌。對于此問題，由于單播和組播在目的端口的特性區(qū)別绊袋，在單播比例較高的時候應(yīng)該當(dāng)作不同業(yè)務(wù)類型處理。
4. Work-Conserving逼近問題：工作保持的定義：任意一次調(diào)度中铸鹰，如果輸入端口有去往某個輸出端口的分組癌别，那么在該次調(diào)度的發(fā)生時隙里，一定有分組通過該輸出端口蹋笼。因此展姐，只要輸入調(diào)度后每列交叉緩存不為空躁垛，那么在輸出端口一定有分組可以被調(diào)度離開交換機，交換機則處于work-conserving階段 —— 因此提出在輸入調(diào)度中今盡量使crosspoint中的緩存分組數(shù)目相同圾笨。（ 思考： 這個推理實際上是將a. input port有cell的情況等價成了b. crosspoint有cell教馆。是否等價？? 也許在某個瞬間crosspoint里沒有cell但是輸入端口有cell還沒來得及通過輸入調(diào)度進入這個crosspoint呢擂达？這就是所謂的隊頭阻塞吧土铺。那此時要解決的是輸入調(diào)度中如何把需要的那個cell提前放進來的問題）
5.?. 結(jié)合GEO星載環(huán)境特征，在現(xiàn)有研究中提出CICQ單組播混合調(diào)度交換結(jié)構(gòu)中選擇一種適用于星載環(huán)境的交換結(jié)構(gòu)： 單級板鬓，單組播共享輸入端酒悲敷，競爭相同交叉節(jié)點緩存，多FIFO組播隊列俭令。
算法設(shè)計分析
1. CA部分分配后的組播隊列應(yīng)該盡量滿足：
????1）k個隊列頭分組多樣性好后德，盡量涵蓋所有的N個輸出端口
????2）相同或相似組播分組歸入同一隊列
? ? 3）不同隊列負(fù)載盡量均衡
2. 為了使得交換機work-conserving，輸入調(diào)度盡量使分組數(shù)量最少的列方向交叉緩存有分組進入抄腔。原因：
????1）有利于使得每列交叉緩存不為空->work-conserving
? ? 2）可均衡每列交叉緩存中分組的數(shù)目->后續(xù)時隙少出現(xiàn)為空情況->后續(xù)時隙work-conserving瓢湃。
????為了使CICQ結(jié)構(gòu)中每列crosspoint buffer中cell數(shù)目均衡，輸入調(diào)度中應(yīng)該優(yōu)先考慮分組數(shù)目最少的列交叉緩存對應(yīng)的輸出端口調(diào)度赫蛇，選定輸出端口后（需要選嗎箱季？一個crosspoint不是確定了對應(yīng)的一對input-output嗎？）棍掐，在可去往該輸出端口的所有輸入端口中藏雏，選擇目的端口數(shù)最少的輸入端口傳輸分組，盡量使得交換機work-conserving作煌。
這個分析再理解一下掘殴？如果選怎了輸入端口1，此時有2個頭分組前往1輸出端口粟誓，1個頭分組前往2輸出端口奏寨，那么同一個time slot里，應(yīng)該是一個頭分組前往（1鹰服，1）crosspoint病瞳，一個頭分組前往(1,2)crosspoint，還剩一個1->(1,1)等到下一個time slot調(diào)度悲酷。對于輸入端口2套菜，有兩個2-（2，1）的調(diào)度设易。講道理也可以在這個time slot里調(diào)度啊逗柴。 那么在這個time slot里（1，1）顿肺、（1戏溺，2）渣蜗、（2，1）都有分組進入旷祸，為什么說第二列交叉緩存無分組進入呢耕拷？
3. 可以通過設(shè)置等待時間為權(quán)重來來保證裁決競爭過程的公平性。
4. 到達(dá)時扇出和當(dāng)前輸入隊列扇出的大小能夠反映阻塞程度托享。若某頭分組到達(dá)時扇出大骚烧，當(dāng)前扇出小，則滯留越嚴(yán)重嫌吠。（這是在說允許扇出拆分的情況下嗎止潘？？）
