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%.     

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

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

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.     

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

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

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...     

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

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

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

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

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

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

Sensitivity analysis of an optimal routing policy in an ad hoc wireless network

We examine the sensitivity of optimal routing policies in ad hoc wireless networks with respect to estimation errors in channel quality. We consider an ad hoc wireless network where the wireless links from each node to its neighbors are modeled by a probability distribution describing the local broadcast nature of wireless transmissions. These probability distributions are estimated in real-time. We investigate the impact of estimation errors on the performance of a set of proposed routing policies.     

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

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

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

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

A method to evaluate the routing policy with two minimal paths within time threshold

Two attributes, the capacity and the lead time, are involved in the quickest path problem which finds a path with the minimum transmission time. The capacity of each edge is assumed to be deterministic in this problem. However, in many real-life networks such as computer, telecommunication, logistics networks, etc., each edge should be multistate due to failure, maintenance, etc. Such a network is named a multistate network. Hence, the minimum transmission time through a multistate network is not fixed. We evaluate the system reliability that a specified amount of data can be sent through a pair of minimal paths simultaneously within the time threshold. A solution procedure is first proposed to calculate it. In order to boost the system reliability, the network administrator decides the routing policy in advance to indicate the first and the second priority pairs of minimal paths. The second one will be responsible for the transmission duty if the first one fails. According to the routing policy, the system reliability can be subsequently computed. The case to transmit data through more than two minimal paths can be extended easily.     

基于Linux策略路由结合VLAN技术的应用

本文详细介绍了VLAN及策略路由的概念及工作原理,详细介绍在Linux下策略路由及VLAN的实现,根据具体问题并结合实例详细介绍在Linux下如何将二者结合解决实际问题,希望给需要解决此类问题的用户提供借鉴和帮助。