1. Birkhoff’s Decomposition Revisited: Sparse Scheduling for High-Speed Circuit Switches
- Author
-
Victor Valls, George Iosifidis, and Leandros Tassiulas
- Subjects
FOS: Computer and information sciences ,Doubly stochastic matrix ,Computer Networks and Communications ,Computer science ,Heuristic (computer science) ,02 engineering and technology ,Permutation matrix ,Topology ,Scheduling algorithms ,Matrix decomposition ,Computer Science - Networking and Internet Architecture ,Matrix (mathematics) ,machine learning algorithms ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Electrical and Electronic Engineering ,Mathematics - Optimization and Control ,Birkhoff decomposition ,Sparse matrix ,Networking and Internet Architecture (cs.NI) ,Circuit switching ,Approximation algorithm ,020206 networking & telecommunications ,Computer Science Applications ,switches ,Optimization and Control (math.OC) ,Software - Abstract
Data centers are increasingly using high-speed circuit switches to cope with the growing demand and reduce operational costs. One of the fundamental tasks of circuit switches is to compute a sparse collection of switching configurations to support a traffic demand matrix. Such a problem has been addressed in the literature with variations of the approach proposed by Birkhoff in 1946 to decompose a doubly stochastic matrix exactly. However, the existing methods are heuristic and do not have theoretical guarantees on how well a collection of switching configurations (i.e., permutations) can approximate a traffic matrix (i.e., a scaled doubly stochastic matrix). In this paper, we revisit Birkhoff’s approach and make three contributions. First, we establish the first theoretical bound on the sparsity of Birkhoff’s algorithm (i.e., the number of switching configurations necessary to approximate a traffic matrix). In particular, we show that by using a subset of the admissible permutation matrices, Birkhoff’s algorithm obtains an ǫ-approximate decomposition with at most O(log(1/ǫ)) permutations. Second, we propose a new algorithm, Birkhoff+, which combines the wealth of Frank-Wolfe with Birkhoff’s approach to obtain sparse decompositions in a fast manner. And third, we evaluate the performance of the proposed algorithm numerically and study how this affects the performance of a circuit switch. Our results show that Birkhoff+ is superior to previous algorithms in terms of throughput, running time, and number of switching configurations.
- Published
- 2021
- Full Text
- View/download PDF