Traffic adaptive WDM networks: a study of reconfiguration issues

This paper studies the issues arising in the reconfiguration phase of broadcast optical networks. Although the ability to dynamically optimize the network under changing traffic conditions has been recognized as one of the key features of multi-wavelength optical networks, this is the first in-depth study of the tradeoffs involved in carrying out the reconfiguration process. We develop and compare reconfiguration policies to determine when to reconfigure the network, and we present an approach to carry out the network transition by describing a class of strategies that determine how to retune the optical transceivers. We identify the degree of load balancing and the number of retunings as two important, albeit conflicting, objectives in the design of reconfiguration policies, naturally leading to a formulation of the problem as a Markovian decision process. Consequently, we develop a systematic and flexible framework in which to view and contrast reconfiguration policies. We show how an appropriate selection of reward and cost functions can be used to achieve the desired balance among various performance criteria of interest. We conduct a comprehensive evaluation of reconfiguration policies and retuning strategies and demonstrate the benefits of reconfiguration through both analytical and simulation results. The result of our work is a set of practical techniques for managing the network transition phase that can be directly applied to networks of large size. Although our work is in the context of broadcast networks, the results can be applied to any wavelength-division multiplexing network where it is necessary to multiplex traffic from a large user population into a number of wavelengths     

Optimal Resource Allocation and Fairness Control in All-Optical WDM Networks

This paper investigates the problem of optimal wavelength allocation and fairness control in all-optical wavelength-division-multiplexing networks. A fundamental network topology, consisting of a two-hop path network, is studied for three classes of traffic. Each class corresponds to a source-destination pair. For each class, call interarrival and holding times are exponentially distributed. The objective is to determine a wavelength allocation policy in order to maximize the weighted sum of users of all classes (i.e., class-based utilization). This method is able to provide differentiated services and fairness management in the network. The problem can be formulated as a Markov decision process (MDP) to compute the optimal allocation policy. The policy iteration algorithm is employed to numerically compute the optimal allocation policy. It has been analytically and numerically shown that the optimal policy has the form of a monotonic nondecreasing switching curve for each class. Since the implementation of an MDP-based allocation scheme is practically infeasible for realistic networks, we develop approximations and derive a heuristic algorithm for ring networks. Simulation results compare the performance of the optimal policy and the heuristic algorithm, with those of complete sharing and complete partitioning policies.     

Optimal Adaptive Modulation and Coding with Switching Costs

We present an optimal adaptive modulation and coding policy that minimizes the transmission latency and modulation/coding switching cost across a finite-state Markovian fading channel. We formulate the optimal tradeoff between transmission latency and modulation/coding switching cost as a discounted infinite horizon Markov Decision Problem (MDP). By exploiting special structures of the formulated MDP and under certain sufficient conditions, we show that optimal modulation and coding selection policies are monotone in the state variables. These monotone optimal policies are computationally inexpensive to implement and are scalable in terms of channel and switching cost parameters. Numerical results confirm the monotonicity and threshold-based structure of the optimal Modulation and Coding Scheme (MCS) selection policies under the proposed sufficient conditions.     

Optimal and Structured Call Admission Control Policies for Resource-Sharing Systems

Many communication and networking systems can be modeled as resource-sharing systems with multiple classes of calls. Call admission control (CAC) is an essential component of such systems. Markov decision process (MDP) tools can be applied to analyze and compute the optimal CAC policy that optimizes certain performance metrics of the system. But for most practical systems, it is prohibitively difficult to compute the optimal CAC policy using any MDP algorithm because of the "curse of dimensionality". We are, therefore, motivated to consider two families of structured CAC policies: reservation and threshold policies. These policies are easy to implement and have good performance in practice. However, since the number of structured policies grows exponentially with the number of call classes and the capacity of the system, finding the optimal structured policy is a complex unsolved problem. In this paper, we develop fast and efficient search algorithms to determine the parameters of the structured policies. We prove the convergence of the algorithms. Through extensive numerical experiments, we show that the search algorithms converge quickly and work for systems with large capacity and many call classes. In addition, the returned structured policies have optimal or near-optimal performance, and outperform those structured policies with parameters chosen based on simple heuristics     

A Markov Decision Process based flow assignment framework for heterogeneous network access

We consider a scenario where devices with multiple networking capabilities access networks with heterogeneous characteristics. In such a setting, we address the problem of efficient utilization of multiple access networks by devices via optimal assignment of traffic flows with given utilities to different networks. We develop and analyze a device middleware functionality that monitors network characteristics and employs a Markov Decision Process (MDP) based control scheme that in conjunction with stochastic characterization of the available bit rate and delay of the networks generates an optimal policy for allocation of flows to different networks. The optimal policy maximizes, under available bit rate and delay constraints on the access networks, a discounted reward which is a function of the flow utilities. The flow assignment policy is periodically updated and is consulted by the flows to dynamically perform network selection during their lifetimes. We perform measurement tests to collect traces of available bit rate and delay characteristics on Ethernet and WLAN networks on a work day in a corporate work environment. We implement our flow assignment framework in ns-2 and simulate the system performance for a set of elastic video-like flows using the collected traces. We demonstrate that the MDP based flow assignment policy leads to significant enhancement in the QoS provisioning (higher rate allocation, lower packet delays and packet loss rates) for the flows and better access network utilization, as compared to policies that allocate flows to different networks using greedy approaches or heuristics like average available bit rate on the networks.     

基于节点控制的空间信息网拓扑重构算法

空间信息网是一种融合陆海空天信息系统的新型自组织网络,成为研究热点.针对网络特点和应用需求,提出一种预防和恢复相结合的拓扑重构策略,通过检测拓扑关键点触发预防性重构,通过拓扑故障触发恢复性重构,重构时在一定范围内选择冗余节点,该节点在虚拟力的导向下自主地移动剑待维护区域,并以修复区域的局部拓扑通信代价最小为目标,进行拓...     

Reconfiguration Decision Making Based on Ant Colony Optimization in Cognitive Radio Network

Facing to the challenges of dynamic adaptation capabilities in the time-varying environment of cognitive radio networks (CRN), reconfiguration capabilities are introduced to flexibly and dynamically adapt to changing wireless environment and service requirement. As one of the essential characteristics for CRN, the cognitive reconfiguration can meet the user requirements, realize interoperability between heterogeneous networks, make full use of radio resources and adapt to the time-varying environment to achieve the end-to-end requirements. However, the reconfiguration implementation is still challenging due to its need for complex environment cognition and multi-objects optimization. In this direction, ant colony optimization(ACO) technique, as an intelligent technology to solve the complex issues, is introduced to the appropriate model of the reconfiguration decision making process to achieve the adaption alternatives. The aim of this paper is to present a generic cognitive reconfiguration framework including indispensable function entities for autonomous reconfiguration decision making with regard to the multiple and complex objectives. Moreover, three kinds of reconfiguration approaches, which are parameters reconfiguration, radio resource reconfiguration and heterogeneous access reconfiguration, are proposed. Finally, numerous results prove the effective performance improvements of ACO based reconfiguration solution in CRN.     

Information Theoretic Approach to Traffic Adaptive WDM Networks

WDM networks adapt to the changes in traffic by reconfiguring the virtual topology. Though reconfiguration is done with the objective of utilizing resources efficiently, the resulting disruption in traffic is a cause for concern. Hence, policies are formed to decide on the time (i.e., when) to trigger reconfiguration and the new virtual topology that is most beneficial to the network. We present a simple, general and flexible framework, based on the two conflicting objectives of efficient resource utilization and minimizing traffic disruption, to evaluate reconfiguration policies. Instead of re-determining the reconfiguration policy whenever the traffic changes, we present Incremental Clustering Algorithm (ICA) to pre-plan the reconfiguration policy for a fully predictable finite sequence of traffic matrices. Since full predictability of such a sequence is not possible in practice, we learn the traffic sequences in order to probabilistically predict the future ones. From an information theoretic point of view, we quantify the predictability of traffic sequences and the number of times the reconfiguration policy is re-determined for any WDM network. To optimally predict the future traffic sequences and to incur optimal cost in the re-determination of the reconfiguration policy, we propose Universal Reconfiguration Management System (URMS). A Prediction-based Incremental Clustering Algorithm (PICA) that extends ICA is used by URMS to predict the reconfiguration policy. Within URMS, the probabilities are assigned to the traffic sequences by the prediction schemes of LZ78. We performed extensive simulations to study the effectiveness and efficiency of URMS when compared to the fully predictable and totally unpredictable models. The performance of URMS improves with learning and nearly achieves the performance of a fully predictable model.     

Optimized bandwidth allocation with fairness and service differentiation in multimedia wireless networks

In this article we present an optimal Markov Decision‐based Call Admission Control (MD‐CAC) policy for the multimedia services that characterize the next generation of wireless cellular networks. A Markov decision process (MDP) is used to represent the CAC policy. The MD‐CAC is formulated as a linear programming problem with the objectives of maximizing the system utilization while ensuring class differentiation and providing quantitative fairness guarantees among different classes of users. Through simulation, we show that the MD‐CAC policy potentially achieves the optimal decisions. Hence our proposed MD‐CAC policy satisfies its design goals in terms of call‐class‐differentiation, fairness and system utilization. Copyright © 2006 John Wiley & Sons, Ltd.     

Opportunistic Fair Scheduling in Wireless Networks: An Approximate Dynamic Programming Approach

We consider the problem of temporal fair scheduling of queued data transmissions in wireless heterogeneous networks. We deal with both the throughput maximization problem and the delay minimization problem. Taking fairness constraints and the data arrival queues into consideration, we formulate the transmission scheduling problem as a Markov decision process (MDP) with fairness constraints. We study two categories of fairness constraints, namely temporal fairness and utilitarian fairness. We consider two criteria: infinite horizon expected total discounted reward and expected average reward. Applying the dynamic programming approach, we derive and prove explicit optimality equations for the above constrained MDPs, and give corresponding optimal fair scheduling policies based on those equations. A practical stochastic-approximation-type algorithm is applied to calculate the control parameters online in the policies. Furthermore, we develop a novel approximation method—temporal fair rollout—to achieve a tractable computation. Numerical results show that the proposed scheme achieves significant performance improvement for both throughput maximization and delay minimization problems compared with other existing schemes.     

Characterization, testing and reconfiguration of faults in mesh networks

Achieving fault-tolerance through incorporation of redundancy and reconfiguration is quite common. The distribution of faults can have several impacts on the effectiveness of any reconfiguration scheme; in fact, patterns of faults occurring at strategic locations may render an entire VLSI system unusable regardless of its component redundancy and its reconfiguration capabilities. Such fault patterns are called catastrophic fault patterns (CFPs). In this paper, we characterize catastrophic fault patterns in mesh networks when the links are bidirectional or unidirectional. We determine the minimum number of faults required for a fault pattern to be catastrophic. We consider the problem of testing whether a fault pattern is catastrophic. When a fault pattern is not catastrophic we study the problem of finding optimal reconfiguration strategies, where optimality is with respect to either the number of processing elements in the reconfigured network (the reconfiguration is optimal if such a number is maximized) or the number of bypass links to activate in order to reconfigure the array (the reconfiguration is optimal if such a number is minimized). The problem of finding a reconfiguration strategy that is optimal with respect to the size of the reconfigured network is NP-complete, when the links are bidirectional, while it can be solved in polynomial time, when the links are unidirectional. Considering optimality with respect to the number of bypass links to activate, we provide algorithms which efficiently find an optimal reconfiguration.     

A component-based policy-neutral architecture for kernel-level access control

Protection should fundamentally be flexible for devices roaming in Beyond 3G networks. In this federation of heterogeneous access networks, each sub-network comes with its own security requirements, policies, and protocols. Foundational element of device security, the embedded OS itself, should become adaptable to make it possible to tune its protection mechanisms to the current security context, notably to support multiple authorization policies. We show how flexibility can be applied to the kernel authorization architecture by adopting a component-based OS design, the component serving as single abstraction for reconfiguration and security. We present a policy-neutral access control architecture called CRACKER (Component-based Reconfigurable Access Control for KERnels) for component-based operating systems. CRACKER supports a wide range of authorization policies, and permits policy reconfiguration, in the same or in different security models. Specified in the Fractal component model, and implemented in the Think OS, CRACKER illustrates how flexible kernel authorization can be realized while maintaining acceptable system performance.     

Optimal power and retransmission control policies for random access systems

We consider in this study dynamic control policies for slotted Aloha random access systems. New performance bounds are derived when random access is combined with power control for system optimization, and we establish the existence of optimal control approaches for such systems. We analyze throughput and delay when the number of backlogged users is known, where we can explicitly obtain optimal policies and analyze their corresponding performance using Markov Decision Process (MDP) theory with average cost criterion. For the realistic unknown-backlog case, we establish the existence of optimal backlog-minimizing policies for the same range of arrival rates as the ideal known-backlog case by using the theory of MDPs with Borel state space and unbounded costs. We also propose suboptimal control policies with performance close to the optimal without sacrificing stability. These policies perform substantially better than existing "Certainty Equivalence" controllers.     

Call admission control for capacity-varying networks

Many networks, such as Non-Geostationary Orbit Satellite (NGOS) networks and networks providing multi-priority service using advance reservations, have capacities which vary over time for some or all types of calls carried on these networks. For connection-oriented networks, Call Admission Control (CAC) policies which only use current capacity information may lead to excessive and intolerable dropping of admitted calls whenever the network capacity decreases. Thus, novel CAC policies are required for these networks. Three such CAC policies are discussed, two for calls with exponentially distributed call holding times and one for calls whose holding time distributions have Increasing Failure Rate (IFR) functions. The Admission Limit Curve (ALC) is discussed and shown to be a constraint limiting the conditions under which any causal CAC policy may admit calls and still meet call dropping guarantees on an individual call basis. We demonstrate how these CAC policies and ALC represent progressive steps in developing optimal CAC policies for calls with exponentially distributed call holding times, and extend this process to the more general case of calls with IFR call holding times.     

Paging and Registration in Cellular Networks: Jointly Optimal Policies and an Iterative Algorithm

This paper explores optimization of paging and registration policies in cellular networks. Motion is modeled as a discrete-time Markov process, and minimization of the discounted, infinite-horizon average cost is addressed. The structure of jointly optimal paging and registration policies is investigated through the use of dynamic programming for partially observed Markov processes. It is shown that there exist policies with a certain simple form that are jointly optimal. An iterative algorithm for policies with the simple form is proposed and investigated. The algorithm alternates between paging policy optimization, and registration policy optimization. It finds a pair of individually optimal policies. Majorization theory and Riesz's rearrangement inequality are used to show that jointly optimal paging and registration policies are given for symmetric or Gaussian random walk models by the nearest-location-first paging policy and distance threshold registration policies.     

An efficient topology reconfiguration algorithm for high speed connection-oriented LANs

This paper deals with the design and performance issues of a protocol, proposed for dynamic topology reconfiguration in high-speed connection-oriented local area networks (LANs). A distributed reconfiguration algorithm is introduced where each network node maintains the minimum-hop-tree connectivity information, corresponding to all the physically reachable network interfaces within the local subnetwork. An incremental and adaptive tree-maintenance strategy is designed for keeping a reconfiguration process isolated from the unaffected parts of the network. A call-by-call routing algorithm, working on top of this reconfiguration protocol, is also proposed with multiple heuristics for optimizing the end-to-end connection hop-count and network load distribution. Simulation results illustrating the correctness and performance of these protocols are included in this paper. Issues regarding a prototype implementation of the presented protocols are also discussed. © 1997 John Wiley & Sons, Ltd.     

An analytical approach to the dynamic topology problem

Currently, it is possible to modify (say, hourly) the topology of a data communications network by adding or deleting network links and/or by increasing or decreasing bandwidth on existing links in response to changing traffic loads and/or projected network conditions. The intent of this paper is to study a Markov decision process (MDP) model of the dynamic topology problem (DTP), the problem of activating and/or deleting links, as a function of the current traffic in the network and of the most recent network topology design. We present a decomposition of this model and structural results for the decomposition. The decomposition and structural results enhance the tractability of procedures for determining optimal link control policies. A numerical example is used to illustrate these results.Research supported by ARO Contract No. DAAG-29-85-K0089, NSF Grant No. ECS-8708183, and DCA Contract No. DCA 100-89-C-0031.     

MDP-based lightpath establishment for service differentiation in all-optical WDM networks with wavelength conversion capability

In this paper, we propose a service differentiation method for lightpath establishment in all-optical WDM networks. The proposed method derives the optimal lightpath establishment policy for each serve class based on a Markov Decision Process (MDP). The optimal policy considered here is to provide service differentiation for lightpath establishment and to utilize wavelengths effectively. Here, we focus on two cases for wavelength conversion capability; full-range wavelength conversion and limited-range wavelength conversion. For full-range wavelength conversion, the number of lightpaths for each class is considered as a state of MDP. On the other hand, for limited-range wavelength conversion, the service class of lightpath that has been established with each output wavelength is considered as the state. Based on these states, we derive the optimal policy for lightpath establishment. In both cases, we evaluate the performance of the proposed method with simulation. In numerical examples, we show that our proposed method can provide service differentiation and use wavelengths effectively regardless of wavelength conversion capability.     

Optimal Mode Selection Policies in Cognitive Radio Networks with RF Energy Harvesting

Applying energy harvesting technology in cognitive radio networks (CRNs) leads to a tradeoff between the time allocated for spectrum sensing followed by spectrum accessing and that for energy harvesting. This tradeoff can be formulated as a mode selection problem for the secondary users. In this paper, we consider a CRN working in the time-slotted manner. The secondary users powered by radio frequency energy harvesting can perform overlay transmission or cooperate with the primary users. To maximize the long-term throughput of the secondary network, we propose two optimal mode selection policies by formulating this problem under a partially observable Markov decision process framework. Numerical simulations show that both of our proposed policies achieve more throughput than the overlay-only policy. Finally, we also evaluate the effect of the cooperative threshold and the energy harvesting process on the optimal policies.