A design algorithm for reconfigurable ATM networks

In this paper, we study the reconfiguration capability in ATM networks and its ability to reduce ATM cell losses. Digital cross-connect systems have been used in traditional reconfigurable networks to concatenate channels to avoid store- and-forward delays. We propose an implementation of the reconfiguration capability in ATM networks that restricts the transmission of cells of an O-D pair to particular channels in each physical link in a simple path from origin to destination. With this proposed implementation, digital cross-connect systems are not needed. We formulate the problem of jointly determining logical networks and the routing assignments on the logical network of a reconfigurable ATM network as a nonlinear mixed integer programming problem. We prove that the joint problem with the integrality constraints relaxed can be simplified to a convex programming problem. This provides a method to compute a lower bound on the minimum cell losses for the original problem. An algorithm is developed to solve the nonlinear mixed integer programming problem. In the computational experiments, the proposed algorithm determined a good feasible solution in a few minutes of CPU time on SUN SPARCsystem 400. In the experiments, the reconfiguration capability decreased the total cell losses by up to 80%. Problem parameters that affect the effectiveness of the reconfiguration capability in reducing ATM cell losses are identified.Supported by NSF Grants NCR 90-16348 and NCR 92-23148.     

An ATM Switch Capacity Allocation Problem

In this paper, we consider a capacity allocation problem arising in the context of deploying asynchronous transfer mode (ATM) networks. Given types of ATM switches, the problem is to find an optimal allocation of capacity such that the total cost of installed switch modules is minimized, while satisfying all traffic demands. We formulate the problem as an integer programming model, which can be conceptualized as a generalized bin packing problem with capacity constraints. We then develop a surrogate constraint technique of the formulation for enhancing the representation of the model. Guided by the tight lower bound of the surrogate relaxation, we devise an effective tabu search heuristic that provides good quality solutions with guaranteed optimality. We present promising computational results that show the viability of the proposed heuristic and lower bounding methods, and that provide insights into implementation for configuring ATM switch in practice.     

Distributed network computing over local ATM networks

Communication between processors has long been the bottleneck of distributed network computing. However, recent progress in switch-based high-speed local area networks (LANs) may be changing this situation. Asynchronous transfer mode (ATM) is one of the most widely-accepted and emerging high-speed network standards which can potentially satisfy the communication needs of distributed network computing. We investigate distributed network computing over local ATM networks. We first study the performance characteristics involving end-to-end communication in an environment that includes several types of workstations interconnected via a Fore Systems' ASX-100 ATM switch. We then compare the communication performance of four different application programming interfaces (APIs). The four APIs were Fore Systems' ATM API, the BSD socket programming interface, Sun's remote procedure call (RPC), and the parallel virtual machine (PVM) message passing library. Each API represents distributed programming at a different communication protocol layer. We evaluated two popular distributed applications, parallel matrix multiplication and parallel partial differential equations, over the local ATM network. The experimental results show that network computing is promising over local ATM networks, provided that the higher level protocols, device drivers, and network interfaces are improved     

On the planning of the S-PVC overlay in ATM networks

We tackle the planning problem of the soft-permanent virtual connections (S-PVCs) in asynchronous transfer mode (ATM) networks. The private network-to-network interface (PNNI) routing standard is used to route these connections. The planning problem consists of determining the PNNI link metrics and the capacity to reserve on each ATM link that ensure the successful rerouting of the S-PVCs for all failure scenarios of interest to the network planner. A mathematical programming model is proposed and a tabu search heuristic in order to find "good" solutions. Finally numerical results are presented and analyzed     

Locating internet gateways to minimize nonlinear congestion costs

We investigate the impact of the locations of the gateways on the performance of the internet. We consider the problem of determining (i) the routing assignments for the intranet and internet traffic and (ii) the number of gateways and their locations to interconnect existing data networks to minimize a linear combination of the average internet and intranet packet delays subject to a cost constraint on the amount to be spent to establish the gateways. This joint routing and topological design problem is important in the design of internets and should be solved before networks are actually interconnected. This problem is formulated as a nonlinear combinatorial optimization problem. When the gateway locations are fixed, the resulting routing problem is not a convex programming problem. This is unexpected since the routing problem in datagram networks is usually formulated as a convex program. We develop an algorithm based upon Lagrangian relaxation to solve this problem. In the computational experiments, the algorithm was shown to be effective in interconnecting (i) two WANs and (ii) two grid networks. The experiments also showed that the algorithm finds better feasible solutions than an exchange heuristic     

Restoration strategies and spare capacity requirements inself-healing ATM networks

This paper studies the capacity and flow assignment problem arising in the design of self-healing asynchronous transfer mode (ATM) networks using the virtual path concept. The problem is formulated here as a linear programming problem which is solved using standard methods. The objective is to minimize the spare capacity cost for the given restoration requirement. The spare cost depends on the restoration strategies used in the network. We compare several restoration strategies quantitatively in terms of spare cost, notably: global versus failure-oriented reconfiguration, path versus link restoration, and state-dependent versus state-independent restoration. The advantages and disadvantages of various restoration strategies are also highlighted. Such comparisons provide useful guidance for real network design. Further, a new heuristic algorithm based on the minimum cost route concept is developed for the design of large self-healing ATM networks using path restoration. Numerical results illustrate that the heuristic algorithm is efficient and gives near-optimal solutions for the spare capacity allocation and flow assignment for tested examples     

训练支持向量机的极大熵方法

支持向量机是基于统计学习理论的结构风险最小化原理提出来的一种新的学习算法,它把模式识别问题建模为一个简单约束的高维二次规划问题。利用Lagrangian对偶方法,把求解二次规划等价为求解低维的无约束不可微优化问题。提出极小化一个严格凸的熵函数来处理不可微问题,得到原二次规划的扰动问题的最优解。数据仿真结果表明该算法在低存储需求下有效提高了大数据量问题的训练学习速度。     

A Parallel Optimization Approach to ATM Network Survivability

This paper describes a new model for routing in survivable ATM networks and a new parallel projection algorithm for solving the corresponding optimization problem. The proposed algorithm has application in general linear programming (LP). Numerical results for medium size networks are presented and discussed.     

The end-to-end rate control in multiple-hop wireless networks: Cross-layer formulation and optimal allocation

In this paper, we study the theoretical problem of the end-to-end rate assignment for multi-hop wireless networks. Specifically, we consider the problem of joint congestion control, random access and power control design with multi-hop transmissions and interference-limited link rates. In order to address both the end-to-end throughput maximization and energy efficiency, we formulate this problem into a cross-layer design problem under a realistic interference-based communication model, which captures the attainable link capacity in practice. There are primarily three challenges in this design: 1) how to formulate the cross-layer design; 2) how to solve the non- convex and non-separable problem efficiently; more importantly 3) under a reasonably complexity, how to design a distributed algorithm that can realize this formulation while maintaining the architectural modularity among different layers. First, we propose a novel method that can convert a non- convex and non-separable programming into an equivalent convex programming problem. The problem is solved by a dual decomposition technique. We show that the resulting algorithm can be practically realized. We then design a distributed algorithm that jointly considers random access and power control to adapt for the transport layer congestion status. Simulation results confirm that the proposed algorithm can achieve close to the global optimum within reasonable convergence times.     

基于PNNI递阶拓扑结构的VP网络规划

ＡＴＭ网络中的ＶＰ层网络规划在大规模网络情形下求解会发生困难,文章借鉴了ＰＮＮＩ网络递阶结构,设计了一种分级规划方法,有效地解决了大规模ＡＴＭ网络ＶＰ层规划问题,并用进化规划对规划问题进行了求解。文中给出了数值算例。     

基于进化规划的ATM网络优化路由算法

根据ATM网络承载业务的特性，提出了以最小化全网平均信元丢失率为目标函数，以途经交换节点数目为约束的优化路由准则，并应用进化规划方法求解此优化问题。     

异构无线网络干扰效率最大顽健资源分配算法

针对能效提升、宏用户干扰减小的问题,该文研究了基于干扰效率最大的异构无线网络顽健资源分配算法.首先,考虑宏用户干扰约束、微蜂窝用户速率需求约束和最大发射功率约束,将资源优化问题建模为多变量非线性规划问题.其次,考虑有界信道不确定性模型,利用Dinkelbach辅助变量方法和连续凸近似方法结合对数变换方法,将原分式规划顽健资源分配问题转换为等价的确定性凸优化问题,并利用拉格朗日对偶算法获得解析解.理论分析了计算复杂度和参数不确定性对性能的影响.仿真结果表明该算法具有较好的干扰效率和鲁棒性.     

Cross-Layer Design for End-to-End Throughput and Fairness Enhancement in Multi-Channel Wireless Mesh Networks

In this paper, we study joint rate control, routing and scheduling in multi-channel wireless mesh networks (WMNs), which are traditionally known as transport layer, network layer and MAC layer issues respectively. Our objective is to find a rate allocation along with a flow allocation and a transmission schedule for a set of end-to-end communication sessions such that the network throughput is maximized, which is formally defined as the maximum throughput rate allocation (MRA) problem. As simple throughput maximization may result in a severe bias on rate allocation, we take account of fairness based on a simplified max-min fairness model and the proportional fairness models. We define the max-min guaranteed maximum throughput rate allocation (MMRA) problem and proportional fair rate allocation (PRA) problem. We present efficient linear programming (LP) and convex programming (CP) based schemes to solve these problems. Numerical results show that proportional fair rate allocation schemes achieves a good tradeoff between throughput and fairness.     

The IEEE P1520 standards initiative for programmable networkinterfaces

This article discusses the need for standard software interfaces for programming of networks, specifically for service and signaling control, through programming interfaces. The objective is to enable the development of open signaling, control, and management applications as well as higher-level multimedia services on networks. The scope of this effort includes ATM switches, circuit switches, IP routers, and hybrid switches such as those that provide for fast switching of IP packets over an ATM backbone. The basic ideas represented herein are in the process of development as a standard for application programming interfaces for networks under IEEE Standards Project IEEE P1520     

Preplanned rerouting optimization and dynamic path rerouting for ATM VP restoration

The survivability for ATM based B‐ISDN has become an important challenge for telecommunication network planners and engineers. In this paper, we consider multiple grades of reliability concept and a multilayer survivable network architecture for survivable ATM networks. We address two complementary ATM VP restoration schemes in this paper. First, we propose preplanned rerouting models and algorithms based on combinatorial optimization to prepare efficient backup VP configuration. We test two formulations and algorithms for this problem. Efficient column generation technique to solve linear programming relaxation and strong valid inequalities incorporating the branch‐and‐bound scheme are suitable to solve the problem to optimality within small time limits. Second, we propose a new dynamic VP path restoration scheme to restore nonprotected VPs by the preplanned rerouting. Our protocol has shown the advantage in restoration effectiveness comparing a well‐known protocol in computational simulation. We, finally, address the relationships between the suggested models of this paper and the expected results of our ongoing project. This revised version was published online in August 2006 with corrections to the Cover Date.     

ATM网络的链路平衡配流策略

本文提出了一种全新的流量分配策略－－链路平衡配流策略,它把平衡思想引入配流过程,利用需求与阻抗的平衡,达到网络流量的最佳分配。本文详细介绍了链路平衡配流策略的概念,还介绍了本策略的数学模型。本文的工作为配流问题的研究提供了一种新思想,新方法。     

Charging for ATM services

Advances in analog and digital telecommunications technology have provided us with a wide range of telecommunications networks since the invention of the analog telephony network by Bell in 1876, such as wireless and wired CATV networks, local, metropolitan, and wide area networks, and the Internet; and a range of protocols to go with these networks, such as Internet Protocol or ATM. Charging for services delivered across these networks has always been an issue of major concern to providers and users of telecommunications services. The ability to charge accurately and efficiently for a service is directly related to the potential quality, value, flexibility, and customer care available to the customer, and, equally important, provides a means of survival, growth, and profitability to the provider. ATM is becoming a significant carrier of telecommunications services because its technology can accommodate a wide variety of services such as multimedia on demand, voice services, or videoconferencing, demanded by today's rapidly changing market. While there are many schemes in use for the charging of mobile and fixed telephony, the area of Internet charging and, in particular, ATM charging is relatively uncharted to date. In this article we address the challenge of developing methods of charging for ATM services, and show solutions in the form of technical and commercial recommendations and a practical implementation of these recommendations     

Task offloading under deterministic demand for vehicular edge computing

In vehicular edge computing (VEC) networks, the rapid expansion of intelligent transportation and the corresponding enormous numbers of tasks bring stringent requirements on timely task offloading. However, many tasks typically appear within a short period rather than arriving simultaneously, which makes it difficult to realize effective and efficient resource scheduling. In addition, some key information about tasks could be learned due to the regular data collection and uploading processes of sensors, which may contribute to developing effective offloading strategies. Thus, in this paper, we propose a model that considers the deterministic demand of multiple tasks. It is possible to generate effective resource reservations or early preparation decisions in offloading strategies if some feature information of the deterministic demand can be obtained in advance. We formulate our scenario as a 0-1 programming problem to minimize the average delay of tasks and transform it into a convex form. Finally, we proposed an efficient optimal offloading algorithm that uses the interior point method. Simulation results demonstrate that the proposed algorithm has great advantages in optimizing offloading utility.     

Satellite ATM networks: a survey

Satellite ATM networks have significant advantages over terrestrial ATM networks. Satellites provide unique advantages such as remote coverage with rapid deployment, distance insensitivity, bandwidth on demand, immunity to terrestrial disasters, and offering broadband links. Satellite ATM networks will play an important role in the rapidly evolving information infrastructure. However, there are several obstacles which need to be overcome so that satellite ATM networks can operate in full service. The objective of this survey is to present the state of the art in satellite ATM networks and to point out open research problems. We explain the satellite ATM network architecture and cover the requirements and technical barriers for seamless integration of ATM and satellite networks. We describe the feasibility of the existing ATM cell transport methods, and deal with conventional and new satellite link access methods, and some error control schemes for the satellite environment. We then describe the problems of the proposed traffic and congestion control schemes, followed by the error performance of the Transmission Control Protocol (TCP) and Service-Specific Connection-Oriented Protocol (SSCOP) for the satellite ATM network. We present basic requirements and a possible architecture for local area-metropolitan area network (LAN-MAN) interconnection using satellite ATM and then discuss the requirements for multimedia services in satellite ATM networks     

分布式认知无线网络中的频谱接入凸规划算法

针对分布式认知无线网络中所可能存在的多频道隐终端问题,以及分布式协调方法(DCF)在随机冲突下性能下降的问题,该文以最优化网络的效用值为目标,将各个认知节点的接入概率作为求解对象,在分布式认知无线网络中建立了一个通用的凸规划模型。同时,基于凸规划算法,提出了一种分布式的信道接入 (DSAC) 算法对目标问题进行求解,从而决定认知网络中每个节点以及每条链路的接入概率。仿真结果表明,DSAC算法能够在较少的迭代次数内实现收敛;与普通的DCF方法相比,DSAC算法可以有效地提高网络中同时传输的链路个数,提高了频谱利用率以及网络吞吐量。