Resource allocation for end-to-end QoS provisioning in a hybrid wireless WCDMA and wireline IP-based DiffServ network

In the future UMTS network, the heterogeneous traffics of multimedia services demand various QoS provisioning. At the same time, the seamlessly conveying of information between mobile users and a hybrid network requires the networking from wireless to wireline domains. However, in both academia and industries, the end-to-end QoS provisioning in the integration of wireline and wireless networks remains a challenge. In this paper, a modeling of a hybrid wireless WCDMA and wireline IP-based DiffServ network is presented to investigate the resource allocation for end-to-end QoS provisioning for multimedia services. In the wireless domain, the mathematical modeling of the cross-layer model including the physical layer, the link layer and the network layer is built. The connection admission control scheme is implemented based on the cross-layer model to determine the amount of resource for different services. In the wireline domain, we define the mapping of QoS classes between UMTS and DiffServ networks according to different QoS requirements. We propose a bandwidth allocation scheme to provide satisfactory packet loss and delay guarantee in DiffServ networks. The final end-to-end admission control scheme combines the resource allocation and admission control in both wireless and wireline domains. The analytical and simulation results show that the proposed resource allocation and admission control schemes work cooperatively in the presented hybrid wireless and wireline networks to guarantee the end-to-end QoS requirements for multimedia services.     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

Resource allocation in state-dependent emergency evacuation networks

Most of the previous studies on the Emergency Evacuation Problem (EEP) assume that the length and widths of the circulation spaces are fixed. This assumption is only true if one is evaluating facilities that are already built. However, when designing the network for the first time, the size of the circulation space is not known to the designer, in fact it is one of several design parameters. After the routes have been established, it seems that the next logical question is to find out whether or not the system circulation spaces are capable of accommodating the traffic for both normal circulation and in an emergency. The problem of designing emergency evacuation networks is very complex and it is only recently that queueing networks are now being used to model this problem. Recent advances include state-dependent queueing network models that incorporate the mean value analysis algorithm to capture the non-linearities in the problem. We extend these models by incorporating the mean value analysis algorithm within Powell's derivative free unconstrained optimization algorithm. The effect of varying circulation widths on throughput will be discussed and a methodology for solving the resource allocation problem is proposed and demonstrated on several examples. The computational experience of the new methodology illustrates its usefulness in network design problems.     

AD HOC网络中的区域划分和资源分配研究

建立了新的Ad Hoc无线网络的区域划分和资源分配模型,讨论了网络覆盖率和抗毁性.通过构造Voronoi图对平面单连通区域的Ad Hoc网络建立区域划分优化模型;定义了网络抗毁性的评价指标连通率,并通过构造Delaunay三角网的最小生成树和蒙特卡罗实验,取得了较好的抗毁仿真结果.最后结合K-均值分簇和罚函数法,得到了近似最优的平面复连通区域的Ad Hoc网络的区域划分和信道安排.     

灾后运输网络中的最短路修复合作博弈

在最短路修复合作博弈中,当灾后运输网络规模较大时,最优成本分摊问题难以直接求解。基于拉格朗日松弛理论,提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈,进而利用两个子博弈的结构特性,可以{高效地}求解出二者的最优成本分摊,将这两个成本分摊相加,可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真,也包含玉树地震灾区的现实模拟,无论数据来源于仿真还是现实,该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。     

Robust resource allocations in temporal networks

Temporal networks describe workflows of time-consuming tasks whose processing order is constrained by precedence relations. In many cases, the durations of the network tasks can be influenced by the assignment of resources. This leads to the problem of selecting an ‘optimal’ resource allocation, where optimality is measured by network characteristics such as the makespan (i.e., the time required to complete all tasks). In this paper we study a robust resource allocation problem where the task durations are uncertain, and the goal is to minimise the worst-case makespan. We show that this problem is generically ${\mathcal{NP}}$ -hard. We then develop convergent bounds on the optimal objective value, as well as feasible allocations whose objective values are bracketed by these bounds. Numerical results provide empirical support for the proposed method.     

Fixed point optimization algorithm and its application to network bandwidth allocation

A convex optimization problem for a strictly convex objective function over the fixed point set of a nonexpansive mapping includes a network bandwidth allocation problem, which is one of the central issues in modern communication networks. We devised an iterative algorithm, called a fixed point optimization algorithm, for solving the convex optimization problem and conducted a convergence analysis on the algorithm. The analysis guarantees that the algorithm, with slowly diminishing step-size sequences, weakly converges to a unique solution to the problem. Moreover, we apply the proposed algorithm to a network bandwidth allocation problem and show its effectiveness.     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

Deadlock free buffer allocation in closed queueing networks

Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.     

Cost sharing of cooperating queues in a Jackson network

We consider networks of queues in which the independent operators of individual queues may cooperate to reduce the amount of waiting. More specifically, we focus on Jackson networks in which the total capacity of the servers can be redistributed over all queues in any desired way. If we associate a cost to waiting that is linear in the queue lengths, it is known from the literature how the operators should share the available service capacity to minimize the long run total cost. This paper deals with the question whether or not (the operators of) the individual queues will indeed cooperate in this way, and if so, how they could share the cost in the new situation such that each operator never pays more than his own cost without cooperation. For the particular case of a tandem network with two or three nodes it is known from previous work that cooperation is indeed beneficial, but for larger tandem networks and for general Jackson networks this question was still open. The main result of this paper gives for any Jackson network an explicit cost allocation that is beneficial for all operators. The approach we use also works for other cost functions, such as the server utilization.     

Resource Allocation with Wobbly Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximisation version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with functions that are not necessarily concave is difficult.In this article, we focus on a large class of problem instances, with objective functions that are close to a concave function or some other smooth function, but with small irregularities in their shape. It is described that these properties are important in many practical situations.The irregularities make it hard or impossible to use known, efficient resource allocation techniques. We show that, for this class of functions the optimal solution can be computed efficiently. We support our claims by experimental evidence. Our experiments show that our algorithm in hard and practically relevant cases runs up to 40–60 times faster than the standard method.     

Iterative Algorithm for Solving Triple-Hierarchical Constrained Optimization Problem

Many practical problems such as signal processing and network resource allocation are formulated as the monotone variational inequality over the fixed point set of a nonexpansive mapping, and iterative algorithms to solve these problems have been proposed. This paper discusses a monotone variational inequality with variational inequality constraint over the fixed point set of a nonexpansive mapping, which is called the triple-hierarchical constrained optimization problem, and presents an iterative algorithm for solving it. Strong convergence of the algorithm to the unique solution of the problem is guaranteed under certain assumptions.     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

Criticality in Resource Constrained Networks

Project managers readily adopted the concept of the critical path as an aid to identifying those activities most worthy of their attention and possible action. However, current project management packages do not offer a useful measure of criticality in resource constrained projects. A revised method of calculating resource constrained float is presented, together with a discussion of its use in project management. While resource constrained criticality appears to be a practical and useful tool in the analysis of project networks, care is needed in its interpretation as any calculation of such float is conditional on the particular resource allocation employed. A number of other measures of an activity's importance in a network are described and compared in an application to an aircraft development. A quantitative comparison of the measures is developed based on a simulation of the process of management identifying the key activities and directing their control efforts. Resource constrained float appears to be a useful single measure of an activity's importance, encapsulating several useful pieces of management information. However, there are some circumstances in which other measures might be preferred.     

On centralized resource utilization and its reallocation by using DEA

The standard DEA model allows different DMU units to set their own priorities for the inputs and outputs that form part of the efficiency assessment. In the case of a centralized organization with many outlets, such as an education authority that is responsible for many schools, it may be more sensible to operate in the most efficient way, but under a common set of priorities for all DMUs. The algorithm that is used to do this, the centralized resource allocation model, does just this. We show that the centralized resource allocation model can be substantially simplified and we interpret the simplifications and show how the model works using real data of Spanish public schools. Apart from finding the best way to reallocate resource among the schools, it is shown that the most desirable operating unit is found to be a by-product of the estimation. This is useful information when planning new schools.     

Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes

A long distance transportation problem was abstracted to a resource flow allocation problem upon a stochastic-flow network with unreliable nodes. The objectives were the probability that transmission was successful and transportation cost. In order to solve constructed model, a multi-objective genetic algorithm was propounded. Tested by examples, the algorithm well solved the flow allocation problem in a stochastic-flow network.     

Generalized loopy 2U: A new algorithm for approximate inference in credal networks

Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.     

A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic environments, job-processing times can be controlled by the allocation of a common resource to jobs. In this paper, we consider the problem of scheduling jobs with arbitrary release dates and due dates on a single machine, where job-processing times are controllable and are modeled by a non-linear convex resource consumption function. The objective is to determine simultaneously an optimal processing permutation as well as an optimal resource allocation, such that no job is completed later than its due date, and the total resource consumption is minimized. The problem is strongly NP\mathcal{NP}-hard. A branch and bound algorithm is presented to solve the problem. The computational experiments show that the algorithm can provide optimal solution for small-sized problems, and near-optimal solution for medium-sized problems in acceptable computing time.     

A generalized DEA model for centralized resource allocation

In this paper, we introduced a new generalized centralized resource allocation model which extends Lozano and Villa’s and Asmild et al.’s models to a more general case. In order to uncover the sources of such total input contraction in the generalized centralized resource allocation model, we applied the structural efficiency to further decompose it into three components: the aggregate technical efficiency, the aggregate allocative efficiency and re-transferable efficiency components. The proposed models are not only flexible enough for the central decision-maker to adjust the inputs and outputs to achieve the total input contraction but also identify the sources of such total input contraction, thereby giving rise to an important interpretation and understanding of the generalized centralized resource allocation model. Finally, an empirical example is used to illustrate the approach.     

多阶段并发的协同物流网络任务-资源集成调配模型

协同物流网络作为动态开放的网络需要整合多种资源,以完成多项并行的物流任务。为此,本文从物流服务集成商的角度,研究了带时间窗和资源约束的任务—资源集成调配问题。通过将物流任务分解为不同阶段,构造多阶段并发的协同物流网络任务—资源集成调配模型,并采用遗传算法对模型进行求解,以从候选资源集合中为任务阶段匹配合适的资源。算例结果表明,该模型能够有效实现N-N的任务-资源集成调配,使得协同物流网络的整体效益达到最优。