A call admission control for service differentiation and fairness management in WDM grooming networks

We investigate a call admission control (CAC) mechanism for providing fairness control and service differentiation in a WDM network with grooming capabilities. A WDM grooming network can handle different classes of traffic streams which differ in their bandwidth requirements. We assume that for each class, call interarrival and holding times are exponentially distributed. Using a Markov Decision Process approach, an optimal CAC policy is derived for providing fairness in the network. The Policy Iteration algorithm is used to numerically compute the optimal policy. Furthermore, we propose a heuristic decomposition algorithm with lower computational complexity and good performance. Simulation results compare the performance of our proposed policy with those of Complete Sharing and Complete Partitioning policies. Comparisons show that our proposed policy provides the best performance in most cases. Although this approach is motivated by WDM networks, it may be deployed to determine the optimal resource allocation in many problems in wireless and wired telecommunications systems.     

Optimal scheduling of coordinated multipoint transmissions in cellular networks

In this paper, we study the optimal scheduling problem in coordinated multipoint (CoMP) transmission–based cellular networks. We consider joint transmission and coordinated scheduling together in CoMP transmission–based cellular networks and develop an optimization framework to compute the optimal max‐min throughput and the optimal scheduling of the transmissions to the users. The optimization problem is found to be a complex linear program with number of variables in for a cellular network of N users and K cells. We solve the optimization problem for several network instances using an optimization tool. The numerical results show that the optimal CoMP transmission provides a significant throughput gain over a traditional transmission. We find that in optimal scheduling the fraction time of coordinated scheduling is higher than that of joint transmission. To solve the optimization problem without any optimization tool, we propose a heuristic algorithm. The performance of the heuristic algorithm is evaluated and found to be provided throughput around 97% of the optimal throughput. Further, we extend the optimization framework to study joint scheduling and power allocation (JSPA) problem in CoMP transmission–based cellular networks. We numerically solve the JSPA problem for the network instances and demonstrate that the optimal power allocation at the base stations is not binary for a significant fraction of time of scheduling. However, the gain in max‐min throughput by the optimal JSPA technique over the optimal scheduling technique is not significant.     

Link scheduling with power control for throughput enhancement in multihop wireless networks

Joint scheduling and power control schemes have previously been proposed to reduce power dissipation in wireless ad hoc networks. However, instead of power consumption, throughput is a more important performance concern for some emerging multihop wireless networks, such as wireless mesh networks. This paper examines joint link scheduling and power control with the objective of throughput improvement. The MAximum THroughput link Scheduling with Power Control (MATH-SPC) problem is first formulated and then a mixed integer linear programming (MILP) formulation is presented to provide optimal solutions. However, simply maximizing the throughput may lead to a severe bias on bandwidth allocation among links. To achieve a good tradeoff between throughput and fairness, a new parameter called the demand satisfaction factor (DSF) to characterize the fairness of bandwidth allocation and formulate the MAximum Throughput fAir link Scheduling with Power Control (MATA-SPC) problem is defined. An MILP formulation and an effective polynomial-time heuristic algorithm, namely, the serial linear programming rounding (SLPR) heuristic, to solve the MATA-SPC problem are also presented. Numerical results show that bandwidth can be fairly allocated among all links/flows by solving the MILP formulation or by using the heuristic algorithm at the cost of a minor reduction of network throughput. In addition, extensions to end-to-end throughput and fairness and multiradio wireless multihop networks are discussed.     

An algorithm for optimal assignment of a wavelength in a tree topology and its application in WDM networks

In this paper, we present a polynomial time algorithm that gives an optimal solution to the routing and wavelength assignment (RWA) problem in a tree topology. One of the major design issues in wavelength-division multiplexed networks is the assignment of the limited number of wavelengths among network stations so that greater capacity can be achieved. The problem of RWA is known to be NP-hard problem. Many researchers have tackled the problem of RWA with a number of efficient heuristic algorithms. This paper presents an algorithm that optimally assigns a single wavelength to maximize one-hop traffic in a tree topology. The algorithm uses dynamic programming and is shown to be optimal with a time complexity of O(N/sup 4/). We also propose a heuristic scheme to use our optimal algorithm for wavelength assignment in a general graph. The heuristic works on the tree subgraphs of a given graph and the remaining spare wavelengths can be assigned with an existing RWA policy.     

Proportional-fair energy-efficient radio resource allocation for OFDMA smallcell networks

This paper investigates the energy-efficient radio resource allocation problem of the uplink smallcell networks. Different from the existing literatures which focus on improving the energy efficiency (EE) or providing fairness measured by data rates, this paper aims to provide fairness guarantee in terms of EE and achieve EE-based proportional fairness among all users in smallcell networks. Specifically, EE-based global proportional fairness utility optimization problem is formulated, taking into account each user’s quality of service, and the cross-tier interference limitation to ensure the macrocell transmission. Instead of dealing with the problem in forms of sum of logarithms directly, the problem is transformed into a form of sum of ratios firstly. Then, a two-step scheme which solves the subchannel and power allocation separately is adopted, and the corresponding subchannel allocation algorithm and power allocation algorithm are devised, respectively. The subchannel allocation algorithm is heuristic, but can achieve close-to-optimal performance with much lower complexity. The power allocation scheme is optimal, and is derived based on a novel method which can solve the sum of ratios problems efficiently. Numerical results verify the effectiveness of the proposed algorithms, especially the capability of EE fairness provisioning. Specifically, it is suggested that the proposed algorithms can improve the fairness level among smallcell users by 150–400 % compared to the existing algorithms.     

一种基于多小区OFDMA系统用户公平性约束的分布式资源分配算法

针对多小区OFDMA系统下行链路,研究了用户公平性约束下的资源分配问题,提出了一种多基站协作的迭代优化的分布式资源分配算法。每个小区根据干扰状况及用户公平性,迭代地进行子载波和功率的资源优化;而每次迭代中,根据用户公平性准则分配子载波,并将非凸的小区功率优化问题转化为其下界的凸问题,通过一个分布式算法来求解。通过仿真验证了算法的有效性;仿真结果表明,与传统网络的固定功率分配的情形相比,所提算法保证了用户之间的公平性并显著提高了系统吞吐量。     

Efficient routing and wavelength assignment for multicast in WDMnetworks

The next generation multimedia applications such as video conferencing and HDTV have raised tremendous challenges on the network design, both in bandwidth and service. As wavelength-division-multiplexing (WDM) networks have emerged as a promising candidate for future networks with large bandwidth, supporting efficient multicast in WDM networks becomes eminent. Different from the IP layer, the cost of multicast at the WDM layer involves not only bandwidth (wavelength) cost, but also wavelength conversion cost and light splitting cost. It is well known that the optimal multicast problem in WDM networks is NP-hard. In this paper, we develop an efficient approximation algorithm consisting of two separate but integrated steps: multicast routing and wavelength assignment. We prove that the problem of optimal wavelength assignment on a multicast tree is not NP-hard; in fact, an optimal wavelength assignment algorithm with complexity of O(NW) is presented. Simulation results have revealed that the optimal wavelength assignment beats greedy algorithms by a large margin in networks using many wavelengths on each link such as dense wavelength-division-multiplexing (DWDM) networks. Our proposed heuristic multicast routing algorithm takes into account both the cost of using wavelength on links and the cost of wavelength conversion. The resulting multicast tree is derived from the optimal lightpaths used for unicast     

Provisioning algorithms for WDM optical networks

This paper concerns connection provisioning for optical networks employing wavelength division multiplexing. A heuristic algorithm is developed and numerically studied for routing and wavelength assignment of a set of static connection requests. The algorithm runs much faster than the optimum solution of this problem. An adaptation of the algorithm is proposed to design restorable networks which can handle a specified set of failures. The proposed algorithm is based on taking all failures into consideration simultaneously, and performs better than developing independent designs for each failure     

WDM网络中基于均衡策略的波长分配算法

对WDM光网络中的波长分配问题进行了研究,采用波长均衡分配的思路解决瓶颈容量对网络性能的影响,并给出了一种启发式算法--最大剩余瓶颈容量算法(Maximum Bottleneck Capacity,MaxBC).该算法把负载引起的波长损失均衡地分布在网络中,使得链路的信道容量受到的影响更小.通过仿真比较了MaxBC与MaxSum、RCL算法在网络拥塞概率等网络性能上的优劣.     

Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks

Multihop infrastructure wireless mesh networks offer increased reliability, coverage, and reduced equipment costs over their single-hop counterpart, wireless local area networks. Equipping wireless routers with multiple radios further improves the capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing is essential for throughput optimization of mesh clients. Efficient channel assignment schemes can greatly relieve the interference effect of close-by transmissions; effective routing schemes can alleviate potential congestion on any gateways to the Internet, thereby improving per-client throughput. Unlike previous heuristic approaches, we mathematically formulate the joint channel assignment and routing problem, taking into account the interference constraints, the number of channels in the network, and the number of radios available at each mesh router. We then use this formulation to develop a solution for our problem that optimizes the overall network throughput subject to fairness constraints on allocation of scarce wireless capacity among mobile clients. We show that the performance of our algorithms is within a constant factor of that of any optimal algorithm for the joint channel assignment and routing problem. Our evaluation demonstrates that our algorithm can effectively exploit the increased number of channels and radios, and it performs much better than the theoretical worst case bounds     

Fairness Guaranteed Cooperative Resource Allocation in Femtocell Networks

User-deployed low-power femtocell access points (FAPs) can provide better indoor coverage and higher data rates than conventional cellular networks. However, a major problem in this uncoordinated frequency reuse scenario is the inter-cell interference. In this paper, we propose a graph based distributed algorithm called fairness guaranteed cooperative resource allocation (FGCRA) to manage interference among femtocells. Since the optimal resource allocation is a NP-hard problem, which is difficult to get global optimization in femtocell networks, our proposed FGCRA algorithm provides sub-optimal resource allocation via cooperation among interfering neighbors. First, we propose a specific fairness factor obtained from two-hop interference relations, to determine the lower bound amount of subchannels that each FAP can use and guarantee the fairness among femtocells. Second, we propose scalable rules for distributed resource allocation and the solution to avoid the conflicts among interfering neighbors. Simulation results show that our proposed FGCRA significantly enhances both average user throughput and cell edge user throughput, and provides better fairness.     

An efficient and generic downlink resource allocation procedure for pre‐5G networks

This paper addresses the downlink resource allocation problem in pre‐5G (LTE‐B) networks. At each time slot, the problem is to share the radio resources between users in order to maximize a given objective function. We expressed this problem considering the LTE standard constraints, which are rarely considered in the literature. Mainly, for any given user, the base station is constrained to transmit with a single modulation and coding scheme. We show that this problem is non‐deterministic polynomial‐time hard, and therefore, we propose a generic approximation algorithm that covers a large variety of objectives. This algorithm is composed of three routines that enable an effective resource sharing procedure. The first routine computes a solution for a relaxation of our main problem, while the second routine selects the most suitable modulation and coding scheme for each user. Finally, the last routine effectively distributes the unallocated resources. For the max rate policy, simulation results show that our algorithm outperforms other existing algorithms in terms of capacity and remains close to the optimal. Under the proportional fairness policy, our solution also provides a very good fairness while maintaining a near‐optimal capacity. Copyright © 2016 John Wiley & Sons, Ltd.     

OFDMA系统基于QoS保证和最大最小公平性准则下的动态资源分配

正交频分多址(OFDMA)技术以其更高的频谱效率和抗多径衰落特性成为高速无线通信网络的候选标准。兼顾效率和公平性是OFDMA系统资源分配亟待解决的问题。本文研究了OFDMA系统中的无线资源分配问题,既要保证QoS用户的最小速率要求,同时“尽力而为”用户之间必须满足最小速率最大化公平性(max-min fairness)准则;该资源分配问题可以表述为一个系统总功率约束下的子载波分配和功率控制的混合离散型优化模型,这是难解的NP-hard问题,穷举搜索的代价是极其巨大的。针对该非凸模型,本文设计一个拉格朗日松弛的优化算法,该算法中采用修正的椭球算法求解对偶问题。算法具有多项式时间复杂度,且与子载波数目呈线性增长关系。仿真结果表明,该算法能近似最优地满足用户QoS及最大最小公平性要求。      

Efficient algorithms for scheduling multiple bulk data transfers in inter‐datacenter networks

Bulk data transfers, such as backups and propagation of bulky updates, account for a large portion of the inter‐datacenter traffic. These bulk transfers consume massive bandwidth and further increase the operational cost of datacenters. The advent of store‐and‐forward transfer mode offers the opportunity for cloud provider companies to transfer bulk data by utilizing dynamic leftover bandwidth resources. In this paper, we study the multiple bulk data transfers scheduling problem in inter‐datacenter networks with dynamic link capacities. To improve the network utilization while guaranteeing fairness among requests, we employ the max–min fairness and aim at computing the lexicographically maximized solution. Leveraging the time‐expanded technique, the problem in dynamic networks is formulated as a static multi‐flow model. Then, we devise an optimal algorithm to solve it simultaneously from routing assignments and bandwidth allocation. To further reduce the computational cost, we propose to select an appropriate number of disjoint paths for each request. Extensive simulations are conducted on a real datacenter topology and prove that (i) benefiting from max–min fairness, the network utilization is significantly improved while honoring each individual performance; (ii) a small number of disjoint paths per request are sufficient to obtain the near optimal allocation within practical execution time. Copyright © 2013 John Wiley & Sons, Ltd.     

Resource allocation for real-time traffic in unreliable wireless cellular networks

Providing reliable transmission for real-time traffic in wireless cellular networks is a great challenge due to the unreliable wireless links. This paper concentrates on the resource allocation problem aiming to improve the real-time throughput. First, the resource allocation problem is formulated as a Markov Decision Process and thus the optimal resource allocation policy could be obtained by adopting the value iteration algorithm. Considering the high time complexity of the optimal algorithm, we further propose an approximate algorithm which decomposes the resource allocation problem into two subproblems, namely link scheduling problem and packet scheduling problem. By this method, the unreliable wireless links are only constrained in the link scheduling problem, and we can focus on the real-time requirement of traffic in packet scheduling problem. For the link scheduling problem, we propose the maxRel algorithm to maximize the long-term network reliability, and we theoretically prove that the maxRel algorithm is optimal in scenarios with dynamic link reliabilities. The Least Laxity First algorithm is adopted for the packet scheduling problem. Extensive simulation results show that the proposed approximate resource allocation algorithm makes remarkable improvement in terms of time complexity, packet loss rate and delay.     

Downlink resource allocation in multi-carrier systems: frequency-selective vs. equal power allocation

This paper revisits equal power allocation from the viewpoint of asymptotic network utility maximization (NUM) problem in multi-carrier systems. It is a well-known fact that the equal power allocation is near optimal to the sum capacity maximization problem in high SNR (Signal-to-Noise Ratio) regime, i.e., optimal water-filling approximates to equal power allocation in that case. Due to this property together with its simplicity, the equal power allocation has been adopted in several researches, but its performance in other problems has not been clearly understood. We evaluate the suitability of equal power allocation in NUM problem which turns into various resource sharing policies according to utility functions. Namely, our conclusion is that in frequency selective channels, the equal power allocation is near optimal for efficiency-oriented resource sharing policy, but when fairness is emphasized, its performance is severely degraded and thus frequency-selective power allocation is necessary. For this, we develop a suboptimal subcarrier and frequency-selective power allocation algorithm for asymptotic NUM problem using the gradient-based scheduling theory and compare the performance of equal power allocation and the developed algorithm. Extensive simulation results are presented to verify our arguments.     

Heuristic and Hybrid Methods for Solving Optimal Multiple Multicast Problem on WDM Ring Network

The Optimal Multiple Multicast Problem (OMMP) on wavelength division multiplexing (WDM) ring networks without wavelength conversion is considered in this paper. When the physical network and the set of multicast requests are given, OMMP is the problem that selects a suitable path (or paths) and wavelength (or wavelengths) among the many possible choices for each multicast request such that not any pair of paths using the same wavelength pass through the same link. In this paper, a formulation of OMMP is given; this problem is NP-hard since the famous RWA problem which has been proved NP-hard is a special case of OMMP. In this paper, the OMMP is divided into two subproblems: path routing and wavelength assignment subproblems. For each subproblem, two heuristic algorithms are proposed to solve it. Moreover, a hybrid method which combines heuristic and simulated annealing algorithm is proposed to find the near optimal solution. Experimental results indicate that these algorithms are efficient.     

Resource allocation with proportional rate fairness in orthogonal frequency division multiple access relay networks

We address the problem of subchannel and transmission power allocation in orthogonal frequency division multiple access relay networks with an aim to maximize the sum rate and maintain proportional rate fairness among users. Because the formulated problem is a mixed‐integer nonlinear optimization problem with an extremely high computational complexity, we propose a low‐complexity suboptimal algorithm, which is a two‐step separated subchannel and power allocation algorithm. In the first step, subchannels are allocated to each user, whereas in the second step, the optimal power allocation is carried out on the basis of the given subchannel allocation and the nonlinear interval Gauss–Seidel method. Simulation results have demonstrated that the proposed algorithm can achieve a good trade‐off between the efficiency and the fairness compared with two other existing relevant algorithms. In particular, the proposed algorithm can always achieve 100% fairness under various conditions. Copyright © 2012 John Wiley & Sons, Ltd.     

Preferred Link Based Distributed Adaptive Routing in Wavelength Routed Optical Network

As the WDM technology matures and the demand for bandwidth increases, dynamic provisioning of lightpaths at the WDM layer becomes an important and challenging problem. In this paper, we consider the problem of dynamic routing and wavelength assignment in wavelength-routed optical networks. The conventional approach to this problem is to select a route from a set of candidate routes, which has a common wavelength available on all the links of the route. In this paper, we propose a distributed algorithm which selects a route based on the state of the network (called preferred link approach). In this approach, a route is selected link by link based on a preference value given to each of the links. We propose three different heuristic functions for calculating the preference of the links, depending on the cost and congestion on the links. We evaluate our routing algorithm in terms of call acceptance ratio, cost of the path, hop length, and call setup time. Our experimental results suggest that our algorithm not only out performs the existing methods with respect to average call acceptance ratio, but, also improves the fairness among different hop connections, which is an important result in the case of WDM optical networks.