An O(log N)Parallel Scheduling Algorithm for Input-Queued Switches

摘要：

　　This paper explores the application of a new algebraic method of edge coloring,called complex coloring,to the scheduling problems of input queued switches.The proposed distributed parallel scheduling algorithms possess two important features: optimality and rearrangeability.The optimality ensures that the algorithm always returns a proper coloring with the minimum number of required colors,and the rearrangeability allows partially re-coloring the existing connection patterns if the underlying graph only changes slightly.The running time of the frame based on-line algorithm is on the order of O(log2N)per frame,and the amortized time complexity,the time to compute a matching per timeslot,is only O(logN).The scheduling algorithm is highly robust in the face of traffic fluctuations.Since the higher the variable density,the higher the efficiency of variable elimination process.Therefore,the complex coloring provides a natural adaptive solution to non-uniform input traffic patterns.The frame based on-line algorithm for packet switching can achieve nearly 100%throughput,while the off-line algorithm for circuit switching always achieves 100%throughput.

关键词： Packet switching Scheudling Edge coloring Complex coloring

作者: Lingkang Wang Tong Ye Tony T.Lee Weisheng Hu

作者单位: Shanghai Jiao Tong University,Shanghai,200240,China Chinese University of Hong Kong(Shenzhen),Shenzhen,518000,China

会议类型: 国际会议

会议名称: The 12th International Conference on Queueing Theory and Network Applications(第十二届排序理论与网络应用国际会议)(QTNA 2017)

会议地点: 河北秦皇岛

会议语种:英文

页码: 114-117

在线出版日期: 2017-08-21（万方平台首次上网日期，不代表论文的发表时间）