Multicolor routing in the undirected hypercube

An undirected routing problem is a pair (G,R) where G is an undirected graph and R is an undirected multigraph such that V(G)=V(R). A solution to an undirected routing problem (G,R) is a collection P of undirected paths of G (possibly containing multiple occurrences of the same path) such that edges of R are in one-to-one correspondence with the paths of P, with the path corresponding to edge {u,v} connecting u and v. We say that a collection of paths P is k-colorable if each path of P can be colored by one of the k colors so that the paths of the same color are edge-disjoint (each edge of G appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let Q_n denote the n-dimensional hypercube, for arbitrary n1. We show that a routing problem (Q_n,R) always admits a 4d-colorable solution where d is the maximum vertex degree of R. This improves over the 16d/2-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pp. 567–576]. Since, for any positive d, there is a multigraph R of degree d such that any solution to (Q_n,R) requires at least d colors, our result is tight up to a factor of four. In fact, when d=1, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.     

基于最小化平均分组跳的波长路由环网逻辑拓扑设计

本文提出了用混合整数线性规则（ＭＩＬＰ）进行波长路由环网的逻辑拓扑设计。对于给定的通信流量矩阵,其目标函数是最小经平均分组跳。以双向环网为例,对于不同网络结构参数的情况,进行了计算分析并给出了数值结果。对双向环网和单向环网的网络性能进行了比较分析。     

全扫描设计中多扫描链的构造

本文在交迭测试体系 的基础上提出了一种多扫描链的区间构造法,对于确定的测试向量集能够显著地减少测试应用时间.该构造方法根据规定的扫描链数,通过求解线性规划问题的方法确定扫描寄存器在扫描链上的优化的分布区间,从而构造多扫描链,最后根据对多扫描链进行连线复杂度的定性分析,求得连线复杂度最低的多扫描链的最优构造.     

局部搜索最小路径费用算法

本文在MPH(Minimum Path Cost Heuristic)的基础上,改进了端节点的加入过程,得到了两种改进的MPH算法:局部搜索最小路径费用算法LSMPH(Locally Searching MPH)和简化的LSMPH:最短端节点最小路径费用算法STMPH(Shortest Terminal MPH).在随机网络模型的基础上,我们进一步进行了仿真.仿真结果表明,LSMPH以相对较小的费用增加换取更快的计算速度.如果要求更快的速度,可以采用STMPH.     

多光纤波分复用网动态路由和波长分配算法

本文研究了多光纤波分复用光互连网的动态路由和波长分配问题,提出了基于分层图模型的两种动态路由算法,LG-1和LG-2.这两种算法将路由和波长分配问题转换为如何在分层图中支持尽可能多的光路.这使得设计者可以同时考虑路由和波长分配子问题,从而取得了更好的效果.计算机仿真表明基于分层图的算法大大优于传统的固定路由和动态路由算法.     

ATM自愈网的一种恢复调度策略

网络生存性是ATM网络中亟待解决的问题.本文在深入分析ATM中故障恢复机制的基础上,指出在恢复过程中存在着恢复调度问题.针对各种服务对恢复时限的不同要求,提出了一种优先级恢复调度策略,P_-RS策略.经模拟分析显示,该策略可以提高网络的有效恢复率,增强了网络的生存性.     

一个2D-Mesh上的完全自适应路由器设计

路由器在大规模并行处理机系统(MPP)中,对互连网络通信性能和系统性能发挥起着关键作用.本文根据所提出的完全自适应路由思想——基于通道方向的完全自适应路由,设计了一个2D-Mesh上完全自适应路由算法.进一步,采用了一种新的高速网络互连技术——源同步技术,最终设计、实现了一个高效、简洁的完全自适应路由器,并在Xilinx XACT的CAD工具上进行了模拟验证.     

一种加强型Route-over和Mesh-under路由策略

6LoWPAN标准将下一代互联网协议IPv6与IEEE 802.15.4标准联系起来,使得在低速无线个人区域网络(LoWPAN)上进行基于IPv6的数据传输成为可能.6LoWPAN规定了2种路由方式,如果路由策略在适配层称作Mesh-under,如果路由策略在网络层,称作Route-over.在这2种策略的基础上提出了这两者相应的加强型改进策略,并通过实验分析了原始2种策略与加强型的2种策略性能上的比较.实验证明加强型策略较原始策略在网络传输与时延方面拥有更好的表现.     

基于分布式选择探测算法的服务路由机制

当前网络中间件服务部署方式僵化单一，难以支持未来多样化的网络服务需求.针对此问题，本文从可重构信息通信基础网络中引入元服务的思想，提出一种支持在控制层进行定制编排以及在数据面按需部署的服务路由机制.该机制将服务路径构建问题建模为多约束最优化问题，并针对性设计了分布式选择探测算法，通过对探针的分布式选择处理进行最优服务路径的构建.仿真结果表明，相较于现有算法，本文提出的服务路由机制在付出较小探测开销的情况下，有效提高了路径服务质量以及服务请求成功率.     

A stochastic evolution algorithm based 2D VLSI global router

In this work we present a global router that uses the features of the Stochastic Evolution (StocE) algorithm to perform the rip-up and re-route (R&R) process. The unique features of the proposed global router are its simple design and ability to produce good results. It has two main components: (i) maze routing with framing (MRF) that act as a means of routing the nets; and (ii) a StocE algorithm that controls the R&R process and adjusts the parameters of the MRF method. This work shows that the StocE algorithm can perform the net selection in the R&R process and also adjust the parameter values of the MRF method in order to successfully solve 2D global routing problems. The performance of the proposed global router on the ISPD98 and ISPD2008 benchmarks was found to be better than some of the existing global routers.