Subjective-cost policy routing

We study a model of path-vector routing in which nodes’ routing policies are based on subjective cost assessments of alternative routes. The routes are constrained by the requirement that all routes to a given destination must be confluent. We show that it is NP-hard to determine whether there is a set of stable routes. We also show that it is NP-hard to find a set of confluent routes that minimizes the total subjective cost; it is hard even to approximate the minimum cost closely. These hardness results hold even for very restricted classes of subjective costs.     

Mechanism design for policy routing

The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an AS’s underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (ie, the sum of all ASes’ utilities for their selected routes). We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities that we call next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted domain. However, we show that, in contrast to earlier work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current Internet. Our contributions include a new complexity measure for Internet algorithms, dynamic stability, which may be useful in other problem domains. Supported in part by ONR grant N00014-01-1-0795 and NSF grantITR-0219018.Supported by ONR grant N00014-01-1-0795 and NSF grant ITR-0219018. Most of this work was done while the author was at Yale University. Supported in part by NSF grants ITR-0121555 and ANI-0207399. This work was supported by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under Grant N00014-01-1-0795. It was presented in preliminary form at the 2004 ACM Symposium on Principles of Distributed Computing [7]. Portions of this work appeared in preliminary form in the second author’s PhD Thesis [16].     

Optimal routing policy of a stochastic-flow network

Under the assumption that each arc’s capacity of the network is deterministic, the quickest path problem is to find a path sending a given amount of data from the source to the sink such that the transmission time is minimized. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not fixed. We try to evaluate the probability that d units of data can be sent through the stochastic-flow network within the time constraint according to a routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. This paper mainly finds the optimal routing policy with highest system reliability. The solution procedure is presented to calculate the system reliability with respect to a routing policy. An efficient algorithm is subsequently proposed to derive the optimal routing policy.     

基于BGP路由策略的仿真建模

针对IP网络上存在的“开环路由”问题,给出了相应的BGP路由策略配置。该配置根据BGP的路由决策进程,结合路由图和访问控制列表的使用,来设置相关的路径属性值,从而对出入自治系统的流量加以控制。给出了具体策略的配置步骤,并用OPNET仿真软件建立模型验证了该策略的有效性。     

策略路由在园区网双出口中的应用

随着网络技术的发展,园区网当中对外访问的流量日益增多,而网络的出口带宽日益成为瓶颈,带宽的解决也不单单是提高速率的问题,如何既提高带宽又能保障出口的安全逐渐成为在中大型园区网中研究的一个热点问题.本文以校园网为场景,论述了双出口的设计以及在实施中采用的相关技术.     

一种基于迷宫算法的有效FPGA布线方法

在本篇论文中,我们介绍了在标准对称阵列（隔离岛状）现场可编程逻辑阵列结构下的一种基于迷宫布线算法的新型有效布线方法,Pathfinder.实验结果显示,相比普通的迷宫布线法,Pathfinder算法在布线时间上减少了90%.     

There is no optimal routing policy for the torus

A routing policy is the method used to select a specific output channel for a message from among a number of acceptable output channels. An optimal routing policy is a policy that maximizes the probability of a message reaching its destination without delays. Optimal routing policies have been proposed for several regular networks, including the mesh and the hypercube. An open problem in interconnection network research has been the identification of an optimal routing policy for the torus. In this paper, we show that there is no optimal routing policy for the torus. Our result is demonstrated by presenting a detailed example in which the best choice of output channel is dependent on the probability of each channel being available. This result settles, in the negative, a conjecture by Wu concerning an optimal routing policy for the torus.     

策略路由和动态DNS在校园网中的应用

提出了应用于多出口中继的校园网环境中流量双向分配控制的解决方案。它综合了策略路由(PBR)、网络地址翻译(NAT)和动态DNS等关键技术，实现不同源／目的网段的数据包由指定的出口进出，合理利用CERNet和ChinaNet的带宽资源，从而达到提高网络速度、降低网络费用的目的。     

随机需求车辆路径问题的价值逼近在线决策

随着高效实时物流的发展,不确定车辆路径问题面临着兼顾决策精度和实时响应能力的新挑战.本文以应用最为广泛的随机需求车辆路径问题为例,研究提出一种有效的在线决策方法.首先,考虑多车辆同时在线,以总旅行成本最小化为目标,建立马尔科夫决策模型,并引入可信度约束和邻域半径减少策略缩小行动空间,提高求解效率.其次,设计强化学习中的...     

策略梯度的超启发算法求解带容量约束车辆路径问题

有容量车辆路径问题是组合优化问题中比较热门的问题, 它属于经典的NP-hard问题并且时间复杂度高.本文提出了一种基于策略梯度的超启发算法, 将强化学习中的确定性策略梯度算法引入到超启发算法的高层策略中的底层算法选择策略, 确定性策略梯度算法采用Actor-Critic框架, 另外为了能够在后续计算和神经网络参数更新中引用历史经验数据, 在确定性策略梯度算法中设计了经验池用于存储状态转移数据. 在超启发算法解的接受准则方面, 文中通过实验对比了3种接受准则的效果, 最终选择了自适应接受准则作为高层策略中解的接受准则. 通过对有容量车辆路径问题标准算例的计算, 并将求解结果与其他算法对比, 验证了所提算法在该问题求解上的有效性和稳定性.     

混洗交换网络中解决路由冲突的一种新策略

路由分批是多级混洗交换网络中解决路由冲突的重要途径,但分批方法的复杂性和分批数量的不确定性影响了路由效率.本文在引入序列分割以及路由编码等概念的基础上,提出了一种新的冲突路由检测方法—分割检测法,该方法在时间效率上明显优于窗口检测法;另外,针对2n1级网络,提出一个与路由策略相关的新猜想,用构造性方法证明了n5时猜想的正确性,并基于猜想提出一种新的路由冲突解决方案,该方案实现了2n1(n5)级网络中所有入线信号不多于两批的路由,较好地解决了信号分批路由时的效率问题.     

基于策略的可控服务发现与动态路由模型

如何改进现有服务发现模型使之适应动态可变的服务运行环境并选择最符合用户需求的Web服务正在引起研究领域关注.提出了一种基于策略的可控服务发现与动态路由模型(P-WSDRM).该模型支持抽象服务、服务实例和服务发现者的属性定义,支持携带属性描述信息的服务发布与发现,引入了策略判定机制,支持服务发现者基于已定义的策略进行服务发现和实例路由.目前已经于Linux平台和目录服务实现了该模型的一个原型系统.     

A new policy to solve routing conflicts in shuffle-exchange networks

Batch routing is an important approach for solving routing conflicts in SE (shuffle-exchange) networks.However,the complexity of batching and the uncertainty of batch size makes this approach impracticable.Based on sequence division and routing coding concepts,we propose a method for detecting routing conflicts in an SE network,known as dividing detection that is more efficient than the method for window detection.In addition,a new conjecture relating to routing policies in SE networks is proposed.This is p...     

具备网络编码感知的能耗友好WSN路由策略

为均衡及降低无线传感器网络(WSN)的路由能耗并最终延长网络的寿命,提出一种具备网络编码感知且能耗敏感的WSN路由策略。该策略通过对WSN环境中存在的网络寿命限制、数据流限制、广播流量限制3个重要因素的分析,对能耗最优路由进行建模,最后归结为对最优化问题的求解获得最佳路径。仿真实验表明该路由策略能够较好地均衡节点的能耗,从整体上显著延长WSN的生存期。     

长链路型输电线路监测系统中WSN路由策略的研究*

为了解决系统漏斗效应,在研究虚拟MIMO路由协议的基础上,提出一种适合输电线路监测系统的基于多簇协作的路由协议方案。该方案采用分簇方式,多簇头之间相互协作,大大减少路由路径上节点个数,简化路由,提高路由效率。仿真结果表明,该策略提高了数据包发送数量,降低了数据时延,显著改善了网络性能。     

Modelling for flexible manufacturing systems and structural properties of optimal work routing policy

We consider flexible manufacturing systems (FMSs) which are composed of a set of workstations linked together with a material handling system (MHS). Each workstation consists of an input buffer, a single machine and an output buffer. The MHS consisting of a single cart routes work among the workstations according to the process paths required by the work. We deal with an optimal control problem in this FMS. We model the FMS as a closed queueing network. In the model, the cart routes the work to the workstations in accordance with a Markov routing with exponentially distributed routing time, and the machines process work with exponentially distributed processing time. An objective is to find a work routing policy that maximizes the total expected reward earned by operating machines. This optimal control problem is formulated as an undiscounted semi-Markov decision process. Structural properties of an optimal policy are analysed. Moreover, a sufficient condition is derived for the optimal policy to be of control limit type. An example is given to illustrate the result.     

基于IPv6的BGP4+路由策略的研究与实现

边界网关协议(border gateway protocol,BGP)用于在自治系统之间交换路由信息,其目的是在自治系统之间选择最好的路由,BGP为了控制路由的传播为路由附带了大量的属性信息,这些属性信息和路由策略结合起来,在自治系统之间选取更好的路由.介绍了边界网关协议的基础上,重点分析了IPv6下BGP4 路由策略的实现.     

分布式校园网路由防火墙安全过滤检测系统研究

该文提出了在当今校园网环境下,从构建安全的分布式校园网边界路由防火墙系统角度出发,研究在边界路由器上采取针对校园网内部网络的报文过滤和针对路由系统本身的安全策略,并在淮阴师范学院校园网中进行了典型应用,实践证明可以达到事半功倍的网络安全目的。