Michael Tartre and Bill Lin
IEEE COMMUNICATIONS LETTERS, VOL. 14, NO. 3, MARCH 2010
Abstract — This letter considers the multicast scheduling problem for the case where the average rates of ?ows are known and a ?xed frame size is applicable. We present a frame-based decomposition method for computing of?ine a recurring schedule that can guarantee the speci?ed ?ow rates with minimum internal speedup if any. We consider both the no-splitting case, where a multicast cell must be transferred to all its destinations in a single time slot and the fanout-splitting case, where a multicast cell may take multiple time slots to transfer to all its destinations, transferring only to a subset of its destinations each time.
Index Terms — Multicast switching, high-performance switches, rate guarantees.

Introduction

• Switch scheduling for crossbbar switches
• Online scheduling problem extensively syudied, exsiting algorithms too complex to implement at high speeds/not capable of providing delay gurantees.
• Offline scheduling is an attractive option when the traffic profile is known a priori and static
  我的研究中traffic demand是對(duì)交換機(jī)可見的還是不可見的？

• Birkhoff-Von Neumann(BvN) by Chang: one such offline scheduling which guarantees 100% throughput and determines delay of any known admissible traffic
  • Decompose any admissible traffic matrix into a convex combination of permutation matrices that correspond to switch configurations
  • permmutation metrices for switch - substantial online memory when N is large
  • not completely : PGPS (Packetized Generalized Process Sharing) algorithm to schedule online the generated permutation matrices, non-trivial impllement
    （PGP IN [2] A. K. Parekh and R. G. Gallager, “A generalized processor sharing approach to ?ow control in integrated service networks: the single-node case,” IEEE/ACM Trans. Networking, 1993.)
  • 相當(dāng)于BvN分成兩部分，第一部分是將traffic矩陣分解成多個(gè)permutation矩陣，再用PGP來調(diào)度。
  • 最開始的BvN是針對(duì)的單播的，對(duì)于組播的改進(jìn)在：[4] J. K. Sundararajan, S. Deb, and M. Medard, “Extending the Birkhoff-von Neumann switching strategy for multicast—on the use of optical
    splitting in switches,” IEEE J. Sel. Areas Commun., 2007.

問題： 這里的online和offline具體含義是什么？

• For Integer flow rates, frame-based offlline scheduling methods have been proposed.
  • Decompose any integer rate matrix into T permutation matrices( T is an interger frame size corresponding to the largest row or column sum of interfer flow rate)
  • Frame-based decomposition approached offer several advantage over BvN approach: 1)Worst-case online memory requirment is much less when T is much less than N^2. 2) no need for PGPs
    (This approach in [3] J. Hui, Switching and Traf?c Theory for Integrated Broadband Networks. Boston, MA: Kluwer Academic Publishers, 1990. )

This paper: proposes a new frame-based scheduling method that provides support for multicast switching. To the author's knowledgem previous frame-based offline scheduling methods didnot consider multicast switching.

Frame-based offline Multicast Scheduling

• Formulated as a graph coloring problem

• Two modes:

  1. No-splitting:A multicast cell must be transferred to all its destinations in a single time slot.
  2. Fan-out splitting: A multicast cell may take multiple time slots to transfer to all its destinations, ransferring only to a subset of its destinations each time.
     關(guān)于拆分后沒有走掉的部分的處理：In the fanout-splitting case, a multicast cell remains queued until it has been transferred to all its destinations. The fanout-splitting case provides the of?ine scheduler with more ?exibility in resolving con?icts. To support partial service, we assume the multicast virtual output queueing model with requeueing described in [6], which is also assumed in [4], [5]. 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).

符號(hào)定義

• General Case：

  
  
  DEF of Flow

DEF of Conflict graph

• Integer Flow Rate：

  
  
  Def of Interger confilict graph

No-Splitting Case

• 將flow rate 大于1的圈分成多個(gè)flow rate為1的圈：

  
  
  Def of Unit conflict graph

Once the unit con?ict graph is derived, the of?ine multicast scheduling problem is reduced to the classical graph coloring problem [7].

FIG1 Process for NO-splitting+cell-splitting Case: SEE Config 1 and 2

A unicast ?ow is shown as a pair (??,??), a multicast ?ow is shown in the form of ??:[??, ??, . . .], and the rates are shown in bold. i: input port j:output port

Continuing with the example shown in Figure 1(c), the unit con?ict graph shown can be colored using ?? = 4 colors, for example as follows:

FIG1: Config1

If the number of switch con?gurations (colors) equals to the frame size, ?? = ?? , then no internal speedup is required. Otherwise, an internal speedup of ??/?? is required to schedule the cell arrivals in ?? time slots.

Fanout-Splitting case

FIG1: Config2

FIG2. Process for Fanout-splitting Case

FIG2 Config