計(jì)劃
1.Michael Tartre and Bill Lin. Frame-Based Multicast Switching. 2010
2. 師兄論文
實(shí)施情況
本周做的工作：
? ? 1. 讀了師兄論文中的機(jī)制分析的部分，梁師兄部分比較好理解，袁師兄用數(shù)學(xué)語言描述，理解難度比較大。
? ? 2. 復(fù)習(xí)了讀懂論文需要的一些數(shù)學(xué)知識(shí)如線性代數(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 可能會(huì)有新的理解。
? ? 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é)果文件怎么看。 爭(zhēng)取下周能確定方案并仿真。
袁師兄論文
- 結(jié)構(gòu)配置：N個(gè)單播隊(duì)列，k個(gè)組播隊(duì)列
- Work-conserving： 任一時(shí)隙中存在去往某個(gè)輸出端口的分組，則該時(shí)隙必有分組離開該輸出端口。
- 由HOL阻塞引起的非work-conserving問題：在調(diào)度過程中，屬于同一組播隊(duì)列的分組扇出不完全一致，若組播隊(duì)列中的后續(xù)分組中存在使交換機(jī)滿足work-conserving狀態(tài)的扇出去向，二頭分組不存在，則發(fā)生了頭分組阻塞。
- 由于考慮整個(gè)組播隊(duì)列中全部后續(xù)分組的扇出過于復(fù)雜，本文算法只考慮頭分組對(duì)次分組的阻塞影響（ 思考： 那我們可以多考慮幾個(gè)后面的分組作為改進(jìn)？）
對(duì)防止頭分組阻塞的機(jī)制分析（幾個(gè)定理）見紙上，有些許問題，整理下問師兄。
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 由三個(gè)變量定義， 源 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在同一個(gè)valid switch configuration中不能共存。在圖中，每個(gè)flow代表一個(gè)vertex， 如果兩個(gè)flow間有沖突，則兩個(gè)vertex間會(huì)有一條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， 幀長(zhǎng)為 T。 則內(nèi)部需要的加速比speedup為 K/T .
總結(jié)：
?本文很不錯(cuò)！詳細(xì)介紹了將frame-based的調(diào)度過程轉(zhuǎn)換成graph coloring問題的一種思路和過程，之后就可以用graphing coloring的算法來解決這個(gè)問題。比如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 可能會(huì)有新的理解。
初步設(shè)計(jì)思路：?
入隊(duì)階段： 使用Module算法，實(shí)現(xiàn)簡(jiǎn)單，速度快；因?yàn)楹竺孢€會(huì)在幀內(nèi)調(diào)整分組順序，沒有必要在入隊(duì)的時(shí)候大費(fèi)周折。這樣的話似乎RR更好？
輸入調(diào)度階段：
? ? - 基于幀的調(diào)度? 幀長(zhǎng) N = 三個(gè)值對(duì)比效果
? ? - 梳理frame-based算法
輸出調(diào)度階段：從非空交叉緩存中，依據(jù)權(quán)重選取分組調(diào)度出交換機(jī)。權(quán)重設(shè)立依據(jù)：緩解頭分組阻塞。 具體？ EDF? or 等待時(shí)間？? ?那只要盡量使crossbuffer中均衡似乎就行了。
業(yè)務(wù)類型： 均勻伯努利、非均勻伯努利、均勻ON-OFF,非均勻ON-OFF
歸一化負(fù)載：0.9, 0.95, 0.99
指標(biāo)：平均時(shí)延/時(shí)隙，通過率??
對(duì)比算法：MF-MRSF, LCNS， OQ
（這些仿真平臺(tái)都能直接計(jì)算得到）
一個(gè)突然想到的關(guān)于輸入調(diào)度的想法：
如果設(shè)置N個(gè)隊(duì)列，按照扇出數(shù)量進(jìn)入不同隊(duì)列，那么不同隊(duì)列的扇出數(shù)量是有互補(bǔ)關(guān)系的，比如扇出(N-1）的隊(duì)列頭分組，就可以找一個(gè)扇出為1的隊(duì)列中的分組結(jié)合進(jìn)行調(diào)度，即使找不到，那也是這個(gè)time slot里扇出最多的選擇。也就是說，每一個(gè)time slot中?
????STEP1:從分組扇出最大的隊(duì)列Q(0<Q<N+1)開始考慮，選取其頭分組?
????STEP2：從扇出為(N-Q)<Q的隊(duì)列開始考慮，從前往后找隊(duì)列中能與其互補(bǔ)的分組.IF能找到，分為一組，在同一個(gè)time slot里調(diào)度， ELSE? NEXT? STEP
????STEP3：以(N-Q-1）,（N-Q-2），，2,1的順序考慮，在隊(duì)列中找能兼容的分組，直到扇出為1（單播）的隊(duì)列都找不到，則這個(gè)time slot 只能調(diào)度Q的頭分組。 注意，在執(zhí)行的過程中，找到的概率其實(shí)是逐漸增大的，要找到合起來扇出為N的扇出比較難，但是找到合起來扇出為Q+1其實(shí)很容易。? 這里有個(gè)選擇，假設(shè)N=16， Q= 10，現(xiàn)在找到了一個(gè)扇出為4的分組結(jié)合，那此時(shí)一個(gè)時(shí)隙的扇出已經(jīng)14很高了，是否還要從fanout=2和1的隊(duì)列面找合適的？
分析：
?1.復(fù)雜度。最壞情況就是每次都找不到互補(bǔ)的，與幀長(zhǎng)F和端口數(shù)N有關(guān)，幾乎都是平方關(guān)系。(F^2 * N^2)?
2.并沒有考慮crossbuffer的情況，和研究思路不同。研究思路是緩解頭分組阻塞，那最核心的應(yīng)該是考慮crossbuffer為空的情況，盡量調(diào)度那些扇出為空buffer 的分組
3.也沒考慮等待時(shí)間，會(huì)有餓死情況。
問題： 優(yōu)先級(jí)、突發(fā)性考慮嗎？如何簡(jiǎn)化近似？
