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是对交换机可见的还是不可见的？

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 $O(N^2)$ for $N \times N$ 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.)
- 相当于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 Trafﬁc Theory for Integrated Broadband Networks. Boston, MA: Kluwer Academic Publishers, 1990. )

$\text{[math]}$

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.

$\text{[math]}$

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 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).

符号定义

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 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.

$\dots$