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 flows are known and a fixed frame size is applicable. We present a frame-based decomposition method for computing offline a recurring schedule that can guarantee the specified flow 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是对交换机可见的还是不可见的？

• 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 flow control in integrated service networks: the single-node case,” IEEE/ACM Trans. Networking, 1993.)
  • 相当于BvN分成两部分，第一部分是将traffic矩阵分解成多个permutation矩阵，再用PGP来调度。
  • 最开始的BvN是针对的单播的，对于组播的改进在：[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 Traffic 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.
     关于拆分后没有走掉的部分的处理：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 offline scheduler with more flexibility in resolving conflicts. 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).

符号定义

• General Case：

  
  DEF of Flow

DEF of Conflict graph

• Integer Flow Rate：

  
  Def of Interger confilict graph

No-Splitting Case

• 将flow rate 大于1的圈分成多个flow rate为1的圈：

  
  Def of Unit conflict graph

Once the unit conflict graph is derived, the offline 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 flow is shown as a pair (𝑖,𝑗), a multicast flow 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 conflict graph shown can be colored using 𝐾 = 4 colors, for example as follows:

FIG1: Config1

If the number of switch configurations (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