計(jì)劃
1.Michael Tartre and Bill Lin. Frame-Based Multicast Switching. 2010
2. 師兄論文
實(shí)施情況
本周做的工作：
? ? 1. 讀了師兄論文中的機(jī)制分析的部分盹舞，梁師兄部分比較好理解润脸，袁師兄用數(shù)學(xué)語言描述，理解難度比較大。
? ? 2. 復(fù)習(xí)了讀懂論文需要的一些數(shù)學(xué)知識如線性代數(shù)等
? ? 3. frame-based相關(guān)的內(nèi)容。
下周計(jì)劃：
? ? 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的文章毕贼，梳理一下常見的思路和方法，目前已知的是轉(zhuǎn)換為圖上色的問題图筹。
? ? 3. 明確輸入排隊(duì)隊(duì)列的結(jié)構(gòu)（N+K or N帅刀？） 輸入調(diào)度算法（frame-based的算法）
? ? 4.找?guī)熜肿稍儗?shí)驗(yàn)產(chǎn)生的結(jié)果文件怎么看。 爭取下周能確定方案并仿真远剩。
袁師兄論文
- 結(jié)構(gòu)配置：N個單播隊(duì)列扣溺，k個組播隊(duì)列
- Work-conserving： 任一時隙中存在去往某個輸出端口的分組，則該時隙必有分組離開該輸出端口瓜晤。
- 由HOL阻塞引起的非work-conserving問題：在調(diào)度過程中锥余，屬于同一組播隊(duì)列的分組扇出不完全一致，若組播隊(duì)列中的后續(xù)分組中存在使交換機(jī)滿足work-conserving狀態(tài)的扇出去向痢掠，二頭分組不存在驱犹，則發(fā)生了頭分組阻塞嘲恍。
- 由于考慮整個組播隊(duì)列中全部后續(xù)分組的扇出過于復(fù)雜，本文算法只考慮頭分組對次分組的阻塞影響（ 思考： 那我們可以多考慮幾個后面的分組作為改進(jìn)雄驹？）
對防止頭分組阻塞的機(jī)制分析（幾個定理）見紙上佃牛，有些許問題，整理下問師兄医舆。
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).
關(guān)于Flow theory：
? ? - Flow Def： flow P 由三個變量定義， 源 S蔬将， 目的地D爷速， 和flow rate R（R取值為0~1之間實(shí)數(shù)）
? ? - Conflict Graph沖突圖： G = (F,C)? F代表所有flow， C表示Flow之間的沖突霞怀。 如果(g惫东，h)∈C，則說明flow g和 h在同一個valid switch configuration中不能共存毙石。在圖中廉沮，每個flow代表一個vertex， 如果兩個flow間有沖突胁黑，則兩個vertex間會有一條edge废封。 —— 轉(zhuǎn)化為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 數(shù) K丧蘸， 幀長為 T漂洋。 則內(nèi)部需要的加速比speedup為 K/T .
總結(jié)：
?本文很不錯！詳細(xì)介紹了將frame-based的調(diào)度過程轉(zhuǎn)換成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 可能會有新的理解弟孟。
初步設(shè)計(jì)思路：?
入隊(duì)階段： 使用Module算法贝咙，實(shí)現(xiàn)簡單，速度快拂募；因?yàn)楹竺孢€會在幀內(nèi)調(diào)整分組順序庭猩，沒有必要在入隊(duì)的時候大費(fèi)周折。這樣的話似乎RR更好陈症？
輸入調(diào)度階段：
? ? - 基于幀的調(diào)度? 幀長 N = 三個值對比效果
? ? - 梳理frame-based算法
輸出調(diào)度階段：從非空交叉緩存中蔼水，依據(jù)權(quán)重選取分組調(diào)度出交換機(jī)。權(quán)重設(shè)立依據(jù)：緩解頭分組阻塞录肯。 具體趴腋？ EDF? or 等待時間？? ?那只要盡量使crossbuffer中均衡似乎就行了。
業(yè)務(wù)類型： 均勻伯努利优炬、非均勻伯努利颁井、均勻ON-OFF,非均勻ON-OFF
歸一化負(fù)載：0.9, 0.95, 0.99
指標(biāo)：平均時延/時隙，通過率??
對比算法：MF-MRSF, LCNS蠢护， OQ
（這些仿真平臺都能直接計(jì)算得到）
一個突然想到的關(guān)于輸入調(diào)度的想法：
如果設(shè)置N個隊(duì)列雅宾，按照扇出數(shù)量進(jìn)入不同隊(duì)列，那么不同隊(duì)列的扇出數(shù)量是有互補(bǔ)關(guān)系的糊余，比如扇出(N-1）的隊(duì)列頭分組秀又，就可以找一個扇出為1的隊(duì)列中的分組結(jié)合進(jìn)行調(diào)度单寂，即使找不到贬芥，那也是這個time slot里扇出最多的選擇。也就是說宣决，每一個time slot中?
????STEP1:從分組扇出最大的隊(duì)列Q(0<Q<N+1)開始考慮蘸劈，選取其頭分組?
????STEP2：從扇出為(N-Q)<Q的隊(duì)列開始考慮，從前往后找隊(duì)列中能與其互補(bǔ)的分組.IF能找到尊沸，分為一組威沫，在同一個time slot里調(diào)度， ELSE? NEXT? STEP
????STEP3：以(N-Q-1）,（N-Q-2）洼专，棒掠，2,1的順序考慮，在隊(duì)列中找能兼容的分組屁商，直到扇出為1（單播）的隊(duì)列都找不到烟很，則這個time slot 只能調(diào)度Q的頭分組。 注意蜡镶，在執(zhí)行的過程中雾袱，找到的概率其實(shí)是逐漸增大的，要找到合起來扇出為N的扇出比較難官还，但是找到合起來扇出為Q+1其實(shí)很容易芹橡。? 這里有個選擇，假設(shè)N=16望伦， Q= 10林说，現(xiàn)在找到了一個扇出為4的分組結(jié)合，那此時一個時隙的扇出已經(jīng)14很高了屯伞，是否還要從fanout=2和1的隊(duì)列面找合適的腿箩？
分析：
?1.復(fù)雜度。最壞情況就是每次都找不到互補(bǔ)的愕掏，與幀長F和端口數(shù)N有關(guān)度秘，幾乎都是平方關(guān)系。(F^2 * N^2)?
2.并沒有考慮crossbuffer的情況，和研究思路不同剑梳。研究思路是緩解頭分組阻塞唆貌，那最核心的應(yīng)該是考慮crossbuffer為空的情況，盡量調(diào)度那些扇出為空buffer 的分組
3.也沒考慮等待時間垢乙，會有餓死情況锨咙。
問題： 優(yōu)先級、突發(fā)性考慮嗎追逮？如何簡化近似酪刀？
