Scheduling algorithms for input queued switches using local search technique

	Scheduling algorithms for input queued switches using local search technique
	Zheng, YF ; He, SM ; Sun, ST ; Gao, W
	2005
发表期刊	NETWORKING - ICN 2005, PT 1
ISSN	0302-9743
卷号	3420 页码:865-872
摘要	Input Queued switches have been very well studied in the recent past. The Maximum Weight Matching (MWM) algorithm is known to deliver 100% throughput under any admissible traffic. However, MWM is not practical for its high computational complexity O(N(3)). In this paper, we study a class of approximations to MWM from the point of view of local search. Firstly, we propose a greedy scheduling algorithm called GSA. It has the following features: (a) It is very simple to compute the weight of a neighbor matching. GSA only needs to compute the weight of two swapped edges instead of the weight of all the edges. (b) The computational complexity of GSA is 0(c_max), where c_max denotes the maximum number of iterations. Hence we can adjust the value of c_max to achieve low computational complexity. Secondly, we observe that: (a) Local search is well suitable for parallel computing. (b) Each line card of high performance router has at least one processor. Based on the two important observations, we develop the second algorithm PGSA. Compared with GSA, PGSA significantly reduce the number of iterations. Simulation results show that PGSA with three iterations outperforms algorithms in [1] under different switch sizes.
收录类别	SCI
语种	英语
WOS研究方向	Computer Science ; Telecommunications
WOS类目	Computer Science, Theory & Methods ; Telecommunications
WOS记录号	WOS:000229070600102
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/10142
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zheng, YF
作者单位	1.Chinese Acad Sci, Comp Technol Inst, Beijing 100080, Peoples R China 2.Chinese Acad Sci, Grad Sch, Beijing 100039, Peoples R China
推荐引用方式 GB/T 7714	Zheng, YF,He, SM,Sun, ST,et al. Scheduling algorithms for input queued switches using local search technique[J]. NETWORKING - ICN 2005, PT 1,2005,3420:865-872.
APA	Zheng, YF,He, SM,Sun, ST,&Gao, W.(2005).Scheduling algorithms for input queued switches using local search technique.NETWORKING - ICN 2005, PT 1,3420,865-872.
MLA	Zheng, YF,et al."Scheduling algorithms for input queued switches using local search technique".NETWORKING - ICN 2005, PT 1 3420(2005):865-872.