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.     

A constrained optimization perspective on actor–critic algorithms and application to network routing

We propose a novel actor–critic algorithm with guaranteed convergence to an optimal policy for a discounted reward Markov decision process. The actor incorporates a descent direction that is motivated by the solution of a certain non-linear optimization problem. We also discuss an extension to incorporate function approximation and demonstrate the practicality of our algorithms on a network routing application.     

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.     

Routing policy of stochastic-flow networks under time threshold and budget constraint

The quickest path problem is to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. More specifically, the capacity of each arc in the network is assumed to be deterministic. 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 as stochastic-flow network. Hence, the minimum transmission time is not a fixed number. The purpose of this paper is to provide a decision procedure for a stochastic-flow network under the time and budget constraints. We try to evaluate the probability that d units of data can be sent through the network under both time threshold and budget according to the routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. An efficient algorithm is proposed to derive the optimal routing policy with highest system reliability. The sensitive analysis can be conducted to improve the most important component which increases the system reliability most significantly.     

一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题,设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息,可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网,从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明,文中提出的算法求得的连通支配集小,能较好地应用于一般网络以及移动自组网络中。     

A scalable method for DCLC problem using hierarchical MDP model

It is well known that the delay-constrained least-cost (DCLC) routing problem is NP-complete, hence various heuristic methods have been proposed for this problem. However, these heuristic methods have poor scalability as the network scale increases. In this paper we propose a new method based on the Markov Decision Process (MDP) theory and the hierarchical routing scheme to address the scalability issue of the DCLC routing problem. We construct a new two-level hierarchy MDP model and apply an infinite-horizon discounted cost model to the upper level for the end-to-end inter-domain link selection. Since the infinite-horizon discounted cost model is independent of network scale, the scalability problem is resolved. With the proposed model, we further give the algorithm of solving the optimal policy to obtain the DCLC routing. Simulation results show that the proposed method improves the scalability significantly.     

基于动态策略的校园网络高速访问的设计与实现

通过分析校园网多出口环境下与公网实现高速互访所需解决的问题,研究使用动态DNS、策略路由、NAT等关键技术实现不同的源/目的地址的数据包经由最佳路径策略所选择的出口发送/接收,以及在公网及CERNET访问校内域名时DNS动态解析出属于各自网内的IP地址,提出了应用于多出口校园网环境下与公网高速互访的实际方案,实现了校园网对外网提供高速网络服务,以及访问外网路由最优化.     

Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks

Unbalanced energy consumption is an inherent problem in wireless sensor networks characterized by multihop routing and many-to-one traffic pattern, and this uneven energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of maximizing network lifetime through balancing energy consumption for uniformly deployed data-gathering sensor networks. We formulate the energy consumption balancing problem as an optimal transmitting data distribution problem by combining the ideas of corona-based network division and mixed-routing strategy together with data aggregation. We first propose a localized zone-based routing scheme that guarantees balanced energy consumption among nodes within each corona. We then design an offline centralized algorithm with time complexity O(n) (n is the number of coronas) to solve the transmitting data distribution problem aimed at balancing energy consumption among nodes in different coronas. The approach for computing the optimal number of coronas in terms of maximizing network lifetime is also presented. Based on the mathematical model, an energy-balanced data gathering (EBDG) protocol is designed and the solution for extending EBDG to large-scale data-gathering sensor networks is also presented. Simulation results demonstrate that EBDG significantly outperforms conventional multihop transmission schemes, direct transmission schemes, and cluster-head rotation schemes in terms of network lifetime.     

Power and delay optimisation in multi-hop wireless networks

In this paper, we study the optimisation problem of transmission power and delay in a multi-hop wireless network consisting of multiple nodes. The goal is to determine the optimal policy of transmission rates at various buffer and channel states in order to minimise the power consumption and the queueing delay of the whole network. With the assumptions of interference-free links and independently and identically distributed (i.i.d.) channel states, we formulate this problem using a semi-open Jackson network model for data transmission and a Markov model for channel states transition. We derive a difference equation of the system performance under any two different policies. The necessary and sufficient condition of optimal policy is obtained. We also prove that the system performance is monotonic with respect to (w.r.t.) the transmission rate and the optimal transmission rate can be either maximal or minimal. That is, the ‘bang-bang’ control is an optimal control. This optimality structure greatly reduces the problem complexity. Furthermore, we develop an iterative algorithm to find the optimal solution. Finally, we conduct the simulation experiments to demonstrate the effectiveness of our approach. We hope our work can shed some insights on solving this complicated optimisation problem.     

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.     

面向编码机会路由的无线Mesh 网络广播信道接入

编码机会路由是有损无线Mesh网络中提供高吞吐量和高可靠性传输的理想方案.该路由机制建立在无线广播的多用户分集优势和随机网络编码的纠删特性之上,为广播MAC的设计引入了新的机会和挑战.基于最优停止理论,研究面向编码机会路由的机会广播信道接入问题,提出一种在接入延迟和信道交付能力之间加以折衷,以获得最优的平均有效速率的方法,并在IEEE 802.11 DCF协议基础上设计实现面向NCOR的广播MAC协议O-BCast.仿真结果表明,该协议显著提高了编码机会路由的端到端吞吐量,具有网络负载自适应的良好特性.     

基于梯度转播的井下WSNs分簇路由协议

针对无线传感器网络煤矿安全监测系统对数据传输可靠性和能量均衡性的需求,提出了一种适用于煤矿井下的基于梯度转播的井下分簇路由协议（G-LEACH）。通过分析煤矿井下特殊的环境特点,针对井下巷道空间特点提出了相应的网络节点部署模型,同时在网络中部署了移动的传感器节点,在此基础上实现了基于梯度转播的可靠分簇路由算法。该算法引入候选簇首机制,通过感知节点的剩余能量、转播因子以及距离因素进行分簇,采用混合路由转发模型并结合梯度信息来决定关键节点。仿真结果表明,G-LEACH具有更高的均衡性和可靠性,更适用于井下复杂环境中安全数据的监测。     

Groupcast routing with the possibility of choosing a channel transmission method

Consideration was given to the following statement of the problem of groupcast routing in the wireless multihop network: in the class of tree-like routes, it is required to determine a minimal-cost route calculated with account for the transmission method used by the MAC protocol. If this method takes advantage of the broadcast nature of the wireless medium, then the number of attempts of transmission made by a route retransmitter and their cost depend on the retransmitter neighbor nodes on the route. This peculiarity makes the considered groupcast routing problem sufficiently distinct from the classical Steiner tree problem. The sensitivity of the route cost to the transmission methods used was analyzed. Also a number of the groupcast routing algorithms were proposed which allow for the structure of the transmission methods and enable one to reduce the cost of routes.     

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.     

Optimal transmission schemes for parallel and fading Gaussian broadcast channels with an energy harvesting rechargeable transmitter

We consider an energy harvesting transmitter sending messages to two users over parallel and fading Gaussian broadcast channels. Energy required for communication arrives (is harvested) at the transmitter and a finite-capacity battery stores it before being consumed for transmission. Under off-line knowledge of energy arrival and channel fading variations, we obtain the trade-off between the performances of the users by characterizing the maximum departure region in a given interval. We first analyze the transmission with an energy harvesting transmitter over parallel broadcast channels. We show that the optimal total transmit power policy that achieves the boundary of the maximum departure region is the same as the optimal policy for the non-fading broadcast channel, which does not depend on the priorities of the users, and therefore is the same as the optimal policy for the non-fading scalar single-user channel. The optimal total transmit power can be found by a directional water-filling algorithm. The optimal splitting of the power among the parallel channels is performed in each epoch separately. Next, we consider fading broadcast channels and obtain the transmission policies that achieve the boundary of the maximum departure region. The optimal total transmit power allocation policy is found using a specific directional water-filling algorithm for fading broadcast channels. The optimal power allocation depends on the priorities of the users unlike in the case of parallel broadcast channels. Finally, we provide numerical illustrations of the optimal policies and maximum departure regions for both parallel and fading broadcast channels.     

Information delivery through broadcasting in satellite communication networks

Satellite broadcast is an important candidate for large-scale multimedia information distribution due to the inherent wide-range multicasting capability of satellites and the asymmetry of satellite communications (high bandwidth downlink, limited bandwidth uplink) that matches nicely the information flow asymmetry in multimedia applications. We consider a data broadcasting model that is encountered in most asymmetric satellite communication environments. The problem of scheduling the data broadcast such that average response time experienced by the users is low is considered. In a push-based system, where the users cannot place requests directly to the server and the broadcast schedule should be determined based solely on the access probabilities, we formulate a deterministic dynamic optimization problem, the solution of which provides the optimal broadcast schedule. Properties of the optimal solution are obtained and then we propose a suboptimal dynamic policy which achieves average response time close to the lower bound. In a pull-based system where the users may place requests about information items directly to the server, the scheduling can be based on the number of pending requests for each item. Suboptimal policies with good performance are obtained in this case as well. If a user has local memory, it can alleviate its access latency by selectively prefetching the items from the broadcast and storing them in the memory. A good memory management strategy can substantially reduce the user's access latency. An optimal memory management policy is identified, that minimizes the expected aggregate latency. Memory update strategies with limited look-ahead are presented as implementable approximations of the optimal policy as well. We also consider the problem of joint broadcast scheduling and user's cache management and propos a joint optimization scheme which can achieve the performance up to 40% better than the existing non-joint approach.     

A Novel Gradient Boosted Energy Optimization Model (GBEOM) for MANET

Mobile Ad Hoc Network (MANET) is an infrastructure-less network that is comprised of a set of nodes that move randomly. In MANET, the overall performance is improved through multipath multicast routing to achieve the quality of service (quality of service). In this, different nodes are involved in the information data collection and transmission to the destination nodes in the network. The different nodes are combined and presented to achieve energy-efficient data transmission and classification of the nodes. The route identification and routing are established based on the data broadcast by the network nodes. In transmitting the data packet, evaluating the data delivery ratio is necessary to achieve optimal data transmission in the network. Furthermore, energy consumption and overhead are considered essential factors for the effective data transmission rate and better data delivery rate. In this paper, a Gradient-Based Energy Optimization model (GBEOM) for the route in MANET is proposed to achieve an improved data delivery rate. Initially, the Weighted Multi-objective Cluster-based Spider Monkey Load Balancing (WMC-SMLB) technique is utilized for obtaining energy efficiency and load balancing routing. The WMC algorithm is applied to perform an efficient node clustering process from the considered mobile nodes in MANET. Load balancing efficiency is improved with a higher data delivery ratio and minimum routing overhead based on the residual energy and bandwidth estimation. Next, the Gradient Boosted Multinomial ID3 Classification algorithm is applied to improve the performance of multipath multicast routing in MANET with minimal energy consumption and higher load balancing efficiency. The proposed GBEOM exhibits ∼4% improved performance in MANET routing.     

基于局部邻居节点和链路权值的改进AODV路由协议

在节点高速移动的Ad Hoc网络环境中,广播风暴对网络性能的影响尤为重要,且网络拓扑结构的频繁变化极易导致路由中断.传统的AODV路由协议在路由发现阶段直接使用广播转发RREQ（路由请求分组）机制,容易导致广播风暴降低网络性能;同时,协议选择跳数最少的路径作为路由,没有考虑到节点的快速移动导致路由频繁失效,因此无法适应节点高速移动的网络环境.针对上面存在的问题,提出一种对AODV进行改进的协议.该协议在路由发起过程中,基于局部邻居节点数量计算动态转发概率;选择路由时,利用跨层思想,结合网络节点移动速度提出链路权值,依据链路权值选择路由路径.NS2仿真结果表明：该改进协议提高了数据包的投递率,缩短了端到端的传输时延,能够更好地适应节点高速移动的网络环境.     

Routing Strategies Under Demand Uncertainty

In this paper, we study network routing and traffic controls under demand uncertainty. Specifically, we examine the strategy of using a deterministic parameter in an optimization setting (a strategy employed in the literature) to represent the demand uncertainty, where traffic flows are modeled using the cell transmission model (CTM). For a special class of networks, for which instances have been previously analyzed in the literature, we provide an optimal policy (i.e., a policy whose solution is optimal for any realization of the demand). Using this optimal policy we show the problems inherent using a deterministic parameter to represent uncertainty. We then show that, for other types of networks, for which optimal policies do not exist, simple heuristics can outperform the use of optimization with a deterministic parameter that represents the demand uncertainty.     

Dynamic broadcasting in parallel computing

We consider the problem where broadcast requests are dynamically generated at random time instants at each node of a multiprocessor network. In particular, in our model packets arrive at each node of a network according to a Poisson process, and each packet has to be broadcast to all the other nodes. We propose an on-line, distributed routing scheme to execute the broadcasts in this dynamic environment. Our scheme consists of repeated execution of a partial multinode broadcast task, which is a static communication task where any M⩽N arbitrary nodes of an N-processor network broadcast a packet to all the other nodes. The dynamic broadcasting scheme that we propose can be used in any topology, regular or not, for which partial multinode broadcast algorithms with certain properties can be found. We derive such an algorithm and we analyze the corresponding dynamic broadcasting scheme for the hypercube network. We show that its stability region tends to the maximum possible as the number of nodes of the hypercube tends to infinity. Furthermore, for any fixed load in the stability region, the average delay is of the order of the diameter of the hypercube. Our analysis does not use any approximating assumptions