一种网络仿真实验床映射问题的启发式算法

Heuristic Algorithm for Mapping Problem of Network Emulation Testbed

提出了一种求解网络仿真实验床映射问题的启发式算法.该算法的思想是:为尽量少地占用仿真实验床的网络资源,应尽可能地将实验者要求的逻辑拓扑中连接紧密的结点映射到同一台交换机上.为此,将仿真实验床的物理拓扑以交换机为单位分成若干子图,之后在实验者要求的逻辑拓扑上进行迭代,每次迭代按边和权值选取结点进行子图划分,最终得到的划分图即为逻辑拓扑到仿真实验床物理拓扑的映射结果.实验结果表明,该算法能在较短的时间内求得近优解,并且当结点个数增大时,算法的求解时间远少于遗传算法.

A heuristic algorithm for mapping problem of the network emulation testbed was presented. The idea of the algorithm is as follows. The tightly connected nodes of the graph of logictopology required by experimenter are mapped possibly to the same single switch in order to occupy as less network resources of emulation testbed as possible. Thereby, the physical topology of the emulation testbed is partitioned into several sub-graphs in a switch unit, and then the iteration is carried out on the logic-topology required by the experimenter, at each iteration the subgraphs is partitioned into the nodes selected by edge and weight value. The resulting partitioned graph corresponds to the mapping result which maps the logic-topology into the physical topology of the emulation testbed. Experiment result shows that the heuristic algorithm can find near-optimal solutions in shorter time, and the runtime is far less than genetic algorithm when increasing the number of nodes.