报告题目：Routing Paths in Software Defined Networks
In this talk, we will introduce a bandwidth-delay-hop constrained routing problem in large-scaled software deﬁned networks. A number of demands, each of which speciﬁes a source vertex and a sink vertex, are required to route in a given network. We are asked to select a subset of demands, for each of which assign a routing path without violating the hop and delay constraints, while assuring that the bandwidth occupied on each edge is not beyond its capacity. The goal is to maximize the throughput of the selected demands. We develop an efﬁcient heuristic algorithm for the problem, which consists of three main steps, namely, computing feasible paths for each demand, sorting the demands with some priority rules, selecting a path for each demand. The algorithm is tested with networks of actual sizes and topologies, generated by the Huawei Technologies Company. In the experiments, our algorithm achieves more than 90% of the total bandwidth of the given demands within 10 seconds. From the theoretical aspect, we show a very special case is already hard to approximate.
张国川，浙江大学计算机科学与技术学院教授。主要从事与计算机科学、管理科学密切相关的组合优化问题的算法分析与设计。在装箱、排序、在线算法领域完成了若干杰出的研究工作。2001年获得德国洪堡研究奖学金。现任国际刊物《Parallel Computing》、《Asia-Pacific Journal of Operational Research》 编委；中国运筹学会数学规划分会副理事长；Asian Association for Algorithms and Computation创始成员。