Interface split routing for finer-grained traffic engineering

Legacy IP routing restricts the efficacy of traffic engineering solutions. This restriction stems from the constraint that traffic at a node must be uniformly split across all next-hop nodes corresponding to equal cost shortest path to a destination. Proposals that alleviate this constraint either completely overhaul legacy IP routing, or introduce complex control and/or forwarding plane components. This additional complexity departs from the elegant simplicity of legacy routing protocols where statically optimized link weights embed all traffic engineering semantics.

We present Interface Split Routing (ISR), which retains the basic forwarding and control mechanism of legacy IP routing. Furthermore, a set of link weights embed all traffic engineering semantics in ISR. However, ISR makes possible finer-grained traffic engineering by configuring independent sets of next-hops to a destination at each incoming interface. This lends itself well to modern router architectures where each incoming interface has its own forwarding table. Consequently, at the aggregated node level, traffic to a particular destination may be non-uniformly distributed across next-hop nodes. Hence, ISR allows additional flexibility in routing traffic as compared to default IP routing while retaining its simplicity. We conduct simulation studies on representative ISP topologies to compare ISR with traditional link-weight-optimized routing. ISR reduces the difference between optimal routing and weight-optimized routing by 50%.     

机会网络自私节点的Bertrand博弈与激励机制研究

在真实的网络环境中,很多节点可能是自私的,它们不愿意牺牲自己的资源为其他节点转发消息。针对这种情况,提出一种基于博弈论的激励机制,可以激励节点与其他节点相互合作。该机制为二阶段激励,激励节点接收消息以协助其他节点转发,同时激励节点转发更多的消息。把源节点与中继节点之间的竞争与合作模型化为Bertrand（伯特兰德）博弈,定义了源节点和中继节点的效用函数。求解了源节点的最佳定价策略和中继节点最佳的转发计划,验证了源节点与中继节点之间存在唯一的纳什均衡。模拟仿真结果表明提出的激励机制能够鼓励自私节点参与合作,能提高路由算法的传递率,同时降低了消息传递延迟。与基于声誉的激励机制相比,所提激励机制能使消息传递成功率提高31.4%、平均时延降低9.7%。     

移动Ad Hoc网络通信量相关干扰感知路由协议

干扰严重影响移动Ad hoc网络的网络吞吐量、能量消耗、网络寿命等性能.在已有基于邻居数目和分布位置的干扰模型基础上,进一步考虑各邻居上的通信量情况,提出通信量干扰模型.并在该干扰模型的基础上,提出一个通信量相关干扰感知路由TIR(traffic load-based interference-aware routing)协议.TIR通过在源节点和目的节点之间选择干扰最小的路径来降低数据包在转发过程中可能受到的干扰.模拟实验结果表明,所提出的通信量干扰模型符合移动Ad hoc网络的特性,通信量相关干扰感知路由协议对网络寿命、通信延迟及吞吐量等网络性能有明显改善.     

无线多媒体传感网络中基于方向角度的路由空洞优化算法

TPGF作为无线多媒体传感网络(WMSN)的一种纯地理位置路由贪婪算法,其核心是在邻居节点集中选择距离目的节点最近的节点作为下一跳节点(下一跳节点可以比本节点距离目的节点要远),同时进行编号进而精简优化来解决空洞问题并满足服务质量(QoS)的需求。针对选取下一跳时距离比自己距离目的节点更远这一策略,提出DATF算法,引入角度变量来进行优化处理,目的是在遇到路由空洞时,更加合理地选择回跳的节点,而不只是单纯地考虑距离因素。仿真结果表明,DATF算法在能量利用率和端到端时延上较TPGF均有改善,在解决空洞问题上也有显著效果。     

基于信任机制的机会网络安全路由决策方法

提出一种基于信任机制的机会网络安全路由决策方法TOR,该方法在节点中引入信任向量的数据结构,记录节点携带消息能力的信任度.采用层状硬币模型和数字签名机制,在消息传递过程中将节点签名的转发证据动态捆绑到消息包上,依靠消息携带方式实现证据链的采集.周期性地将具有签名和时间戳的信任向量表通过洪泛方式反馈到网络中,在每个节点,迭代形成一个由多维行向量集组成的只读可信路由表TRT,作为选择下一跳节点和副本分割策略的决策依据.在节点相遇时,选择信任度比自身大的作为下一跳转发节点,消息沿着信任梯度递增的方向传递.实验结果表明：与现有路由算法相比,TOR算法能够有效抑制恶意节点和自私节点的破坏行为,且具有较高的消息传递成功率和较低的消息转发平均时延,对缓存空间和计算能力要求较低.     

无线传感器网络中基于协作的包转发研究

运用博弈论的观点和方法来解决传感器网络中的包转发问题．为传感器网络建立了包转发模型，分析了节点参与包转发会话所获得的帕累托最优效用．提出了基于帕累托最优效用的包转发算法POUPF，并证明了该算法能够建立纳什均衡以保证每个节点都获得帕累托最优效用．仿真结果表明：POUPF能够有效促进节点自发合作，确保了每个节点获得帕累托最优效用；任何偏离POUPF节点的包转发行为都会导致所有节点效用的下降．     

基于水压的水下传感网络的选播路由协议

在水下传感网络中,由于传感节点的移动以及节点带宽和能量受限,设计从移动节点至声纳浮标的有效选播路由协议存在挑战.为此,提出一种基于水压的水下传感网络的选播路由HPAR(Hydraulic-Pressure-based Anycast Routing)协议.HPAR协议通过水压决策路由,并依据数据包权重,择优选择下一跳转发节点.当传感节点需要传输数据包时,HPAR协议就利用数据包优先权值ADV(ADVancement)构建候选转发集,再利用归一化的权值NADV(Normalized ADVance)评估候选转发集内节点成为下一跳节点的"适度性",然后,将候选转发集划分不同的簇,使得簇内的节点均在彼此的通信范围内,再计算每个簇的期望权值EPA(Expected Packet Advanced),具有最大EPA的簇成为下一跳转发簇,最后,再利用定时器抑制冗余数据包数,并优化定时参数.仿真结果表明,提出的HPAR协议有效地提高数据包传输率、降低冗余数据包数.     

Torus网络中基于标志位的容错路由

针对Torus结构的多处理机系统中容错路由的问题,提出标志位概念,给出一个基于标志位的容错路由算法。存储于Torus网络中各节点的标志位记录系统中的故障信息,用于判定消息的源节点和目的节点之间是否存在最优通路。标志位的赋值可以通过与邻节点间的信息交换完成。     

Power-aware localized routing in wireless networks

A cost aware metric for wireless networks based on remaining battery power at nodes was proposed for shortest-cost routing algorithms, assuming constant transmission power. Power-aware metrics, where transmission power depends on distance between nodes and corresponding shortest power algorithms were also proposed. We define a power-cost metric based on the combination of both node's lifetime and distance-based power metrics. We investigate some properties of power adjusted transmissions and show that, if additional nodes can be placed at desired locations between two nodes at distance d, the transmission power can be made linear in d as opposed to d^α dependence for α ⩾ 2. This provides basis for power, cost, and power-cost localized routing algorithms where nodes make routing decisions solely on the basis, of location of their neighbors and destination. The power-aware routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. The cost-aware routing algorithm is aimed at extending the battery's worst-case lifetime at each node. The combined power-cost localized routing algorithm attempts to minimize the total power needed and to avoid nodes with a short battery's remaining lifetime. We prove that the proposed localized power, cost, and power-cost efficient routing algorithms are loop-free and show their efficiency by experiments     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

一种面向机会网络路由的最优停止决策方法

投递延迟是机会网络的一个重要指标,给定节点缓存和消息副本数目限制,如何选择合适的节点复制消息成为一个关键问题.提出一种基于最优停止理论的路由决策方法（OSDR）.OSDR 将每个时隙上所遇节点和目标节点的平均相遇时间看做一个随机变量,根据该随机变量的统计特性得到一个停止观察、复制消息的规则,该规则呈现简单的阈值结构,即当某个时隙上所遇节点和目标节点的平均相遇时间小于给定阈值时即复制消息. OSDR 可以在较小的相遇间隔和等待成本之间进行折衷,实现数学期望意义上的最小消息投递延迟.介绍了OSDR 的网络模型、最优停止规则的存在性证明过程以及计算方法.模拟实验结果表明,OSDR 相对其他方法,在投递成功率、投递延迟等方面具有明显优势.     

Road Pricing Design Based on Game Theory and Multi-agent Consensus

Consensus theory and noncooperative game theory respectively deal with cooperative and noncooperative interactions among multiple players/agents. They provide a natural framework for road pricing design, since each motorist may myopically optimize his or her own utility as a function of road price and collectively communicate with his or her friends and neighbors on traffic situation at the same time. This paper considers the road pricing design by using game theory and consensus theory. For the case where a system supervisor broadcasts information on the overall system to each agent, we present a variant of standard fictitious play called average strategy fictitious play (ASFP) for large-scale repeated congestion games. Only a weighted running average of all other players' actions is assumed to be available to each player. The ASFP reduces the burden of both information gathering and information processing for each player. Compared to the joint strategy fictitious play (JSFP) studied in the literature, the updating process of utility functions for each player is avoided. We prove that there exists at least one pure strategy Nash equilibrium for the congestion game under investigation, and the players' actions generated by the ASFP with inertia (players' reluctance to change their previous actions) converge to a Nash equilibrium almost surely. For the case without broadcasting, a consensus protocol is introduced for individual agents to estimate the percentage of players choosing each resource, and the convergence property of players' action profile is still ensured. The results are applied to road pricing design to achieve socially local optimal trip timing. Simulation results are provided based on the real traffic data for the Singapore case study.      

拍卖博弈模型在无线传感器网络路由中的应用研究

为了提高无线传感器网络数据转发的可靠性及能量利用率,本文基于拍卖博弈建立了拍卖路由博弈模型,并提出一种进行转发节点选择的价格路由博弈算法.在算法中潜在的转发节点为了从发送节点获得虚拟货币而相互竞争,发送节点根据各个转发节点的标价选择最佳转发节点.实验仿真表明拍卖路由博弈模型的合理、有效,提出的价格路由博弈算法能够降低节点的能量消耗,延长网络的生命周期.     

Routing into Two Parallel Links: Game-Theoretic Distributed Algorithms

We study a class of noncooperative networks where N users send traffic to a destination node over two links with given capacities in such a way that a Nash equilibrium is achieved. Under a linear cost structure for the individual users, we obtain several dynamic policy adjustment schemes for the online computation of the Nash equilibrium and study their local convergence properties. These policy adjustment schemes require minimum information on the part of each user regarding the cost–utility functions of the others.     

一种基于稳定簇的混合路由协议CBHRP

移动算组网是一种没有有线基础结构支持的移动网络,具有带宽有限和拓扑结构易变的特点。这些特点使得设计一个合适的路由协议具有一定的挑战性。该文针对移动自组网提出了一种基于稳定簇结构、按需路由和预先路由混合、支持单播和组播通信的路由协议CBHRP。CBHRP具有路由控制开销小、主机移动对拓扑结构改变的影响小、通信的初始延迟低和应用范围广的特点。     

基于层级的水下传感器网络自适应地理路由协议

针对水下传感器网络(UWSN)需要专门的路由协议满足适应性、鲁棒性、高能效和能量均衡等要求, 提出了基于层级的UWSN自适应地理路由协议LB-AGR, 不同流量采用不同路由决策, 根据节点层级、剩余能量、节点密度和位置信息, 为候选下一跳节点计算复合转发因子, 从而确定最佳路由, 并将上行流量单播传送, 减少了碰撞和能耗。仿真表明, LB-AGR在降低能耗、缩短端到端延时的同时, 延长了网络生存期。     

Fine two-phase routing over shortest paths with traffic matrix

This paper presents an IP finely-distributed load-balanced routing scheme based on two-phase routing over shortest paths, where the traffic matrix is given. It is called the fine two-phase routing (F-TPR) scheme. F-TPR more finely distributes traffic from a source node to intermediate nodes than the original TPR. F-TPR determines the distribution ratios to intermediate nodes for each source–destination node pair independently. To determine an optimum set of distribution ratios, a linear programming (LP) formulation is derived. We compare the F-TPR scheme against the TPR scheme and the sophisticated traffic engineering (TE) scheme of Multi-Protocol Label Switching (MPLS-TE). Numerical results show that F-TPR greatly reduces the network congestion ratio compared to TPR. In addition, F-TPR provides almost the same network congestion ratios as MPLS-TE, the difference is surprisingly less than 0.1% for the various network topologies examined. In addition, considering the practical implementation of F-TPR for routers, we also investigate the case that traffic from a source node to a destination node is not allowed to be split over multiple routes. The non-split problem is formulated as an integer linear programming (ILP) problem. As it is difficult to solve the ILP problem within practical time, two heuristic algorithms are presented: Largest Traffic Demand First (LTDF) and a Random Selection (RS). The applicability of LTDF and RS are presented in terms of network size. We find that non-split F-TPR also matches the routing performance of MPLS-TE within an error of 1%, when network size is large enough.     

MRABM:一种新的基于mesh结构的多径路由算法

针对移动AdHoc网络提出了一种新的基于mesh结构的多径路由算法MRABM(MultipathRoutingAlgorithmBasedonMeshStructure),该算法采用目的节点建立和更新mesh结构的机制。该算法不仅为每个源节点、中间节点提供了到目的节点最优路径,而且为每个节点建立了到目的节点的多条路径。当节点移动造成链路断开时,该算法能避开断开的链路,迅速沿其它路径转发数据,不需要路由修复和路由重建过程,从而降低了丢包率和端到端的延时。对大流量数据的传输,该算法能有效利用网络资源,减少网络拥塞。因此该算法能很好地适应网络拓扑结构的动态变化。     

基于能量优化的认知无线电网络组播路由协议

针对认知无线电网络节点动态频谱分配的特点,利用静态博弈方法,根据次用户占用频谱越宽所造成干扰越大,建立基于价格惩罚机制的古诺模型解决频谱分配问题,通过求解纳什均衡,频谱利用率达到最优。根据最小增量按需驱动思想建立了节约能量的组播树,提出基于能量优化的适用于认知无线电网络的按需组播路由协议。     

A decentralized mechanism for improving the functional robustness of distribution networks

Most real-world distribution systems can be modeled as distribution networks, where a commodity can flow from source nodes to sink nodes through junction nodes. One of the fundamental characteristics of distribution networks is the functional robustness, which reflects the ability of maintaining its function in the face of internal or external disruptions. In view of the fact that most distribution networks do not have any centralized control mechanisms, we consider the problem of how to improve the functional robustness in a decentralized way. To achieve this goal, we study two important problems: 1) how to formally measure the functional robustness, and 2) how to improve the functional robustness of a network based on the local interaction of its nodes. First, we derive a utility function in terms of network entropy to characterize the functional robustness of a distribution network. Second, we propose a decentralized network pricing mechanism, where each node need only communicate with its distribution neighbors by sending a "price" signal to its upstream neighbors and receiving "price" signals from its downstream neighbors. By doing so, each node can determine its outflows by maximizing its own payoff function. Our mathematical analysis shows that the decentralized pricing mechanism can produce results equivalent to those of an ideal centralized maximization with complete information. Finally, to demonstrate the properties of our mechanism, we carry out a case study on the U.S. natural gas distribution network. The results validate the convergence and effectiveness of our mechanism when comparing it with an existing algorithm.