A new approach to dynamic bandwidth allocation in Quality of Service networks: Performance and bounds

Efficient dynamic resource provisioning algorithms are necessary to the development and automation of Quality of Service (QoS) networks. The main goal of these algorithms is to offer services that satisfy the QoS requirements of individual users while guaranteeing at the same time an efficient utilization of network resources.In this paper we introduce a new service model that provides per-flow bandwidth guarantees, where users subscribe for a guaranteed rate; moreover, the network periodically individuates unused bandwidth and proposes short-term contracts where extra-bandwidth is allocated and guaranteed exclusively to users who can exploit it to transmit at a rate higher than their subscribed rate.To implement this service model we propose a dynamic provisioning architecture for intra-domain Quality of Service networks. We develop a set of dynamic on-line bandwidth allocation algorithms that take explicitly into account traffic statistics and users’ utility functions to increase users’ benefit and network revenue.Further, we propose a mathematical formulation of the extra-bandwidth allocation problem that maximizes network revenue. The solution of this model allows to obtain an upper bound on the performance achievable by any on-line bandwidth allocation algorithm.We demonstrate through simulation in realistic network scenarios that the proposed dynamic allocation algorithms are superior to static provisioning in providing resource allocation both in terms of total accepted load and network revenue, and they approach, in several network scenarios, the ideal performance provided by the mathematical model.     

Building Manageable Multimedia Network Services

The paper addresses the problem of designing and realizing manageable multimedia network services. We argue that open interface between the service delivery and the service management systems can be defined using design patterns, i.e., generic object models. As an example, we introduce a generic object model that makes instances of a network service accessible to the management system. The model includes a set of cooperating objects that can be customized for particular service and management requirements. By applying this model to the design of mcast, an ATM multicast service, we enable the management system to monitor and control mcast sessions. To validate our approach, we have implemented mcast and the management functions on two different platforms: (1) on a high-performance emulation platform, which allows us to study the system's dynamic behavior and scaling properties in various scenarios; (2) on a broadband testbed, on which network services can be fully implemented, including the transport between multimedia devices. We outline a specific technique that allows us to run the same code, without changes, on both platforms.     

An adaptive congestion control mechanism for intelligent broadband networks

The provision of novel multimedia services in broadband networks through intelligent network (IN) technology is a promising solution that guarantees fast deployment of new services and minimum changes to already operating networks. In this architecture, the broadband service control point (B-SCP) is the main actor in the processing of complex IN service requests. This centralized approach which is reflected in the multiplicity of tasks undertaken by the B-SCP in a broadband IN architecture, can easily lead to network performance degradation. Therefore, the presence of a congestion control mechanism operating at the level of calls is considered essential in order to protect the network nodes from overload conditions and to attain high levels of network performance. In this paper, we propose an adaptive congestion control mechanism (ACCM) which is able to guarantee the desirable quality of service under overload conditions. The proposed mechanism gradually reduces the message transmission rate from the source node to the destination node when overflow conditions have been detected, taking as feedback the buffer capacity state of the destination. Results, obtained by simulation show that the proposed ACCM improves the network performance by maximising the number of established calls and reducing the number of rejected calls.     

基于CORBA的分布式宽带智能网及其业务的实现

为了实现分布式业务控制和统一的业务定制,该文将CORBA技术引入智能网,并提出了分布式宽带智能网的体系结构模型。在此基础上讨论了智能网业务的CORBA实现。     

Adaptive load sharing in heterogeneous distributed systems

In this paper, we study the performance characteristics of simple load sharing algorithms for heterogeneous distributed systems. We assume that nonnegligible delays are encountered in transferring jobs from one node to another. We analyze the effects of these delays on the performance of two threshold-based algorithms called Forward and Reverse. We formulate queuing theoretic models for each of the algorithms operating in heterogeneous systems under the assumption that the job arrival process at each node in Poisson and the service times and job transfer times are exponentially distributed. The models are solved using the Matrix-Geometric solution technique. These models are used to study the effects of different parameters and algorithm variations on the mean job response time: e.g., the effects of varying the thresholds, the impact of changing the probe limit, the impact of biasing the probing, and the optimal response times over a large range of loads and delays. Wherever relevant, the results of the models are compared with the M/M/ 1 model, representing no load balancing (hereafter referred to as NLB), and the M/M/K model, which is an achievable lower bound (hereafter referred to as LB).     

Analysis and optimization of service availability in a HA cluster with load-dependent machine availability

Calculations of service availability of a high-availability (HA) cluster are usually based on the assumption of load- independent machine availabilities. In this paper, we study the issues and show how the service availabilities can be calculated under the assumption that machine availabilities are load dependent. We present a Markov chain analysis to derive the steady-state service availabilities of a load-dependent machine availability HA cluster. We show that with a load-dependent machine availability, the attained service availability is now policy dependent. After formulating the problem as a Markov decision process, we proceed to determine the optimal policy to achieve the maximum service availabilities by using the method of policy iteration. Two greedy assignment algorithms are studied: least load and first derivative length (FDL) based, where least load corresponds to some load balancing algorithms. We carry out the analysis and simulations on two cases of load profiles: In the first profile, a single machine has the capacity to host all services in the HA cluster; in the second profile, a single machine does not have enough capacity to host all services. We show that the service availabilities achieved under the first load profile are the same, whereas the service availabilities achieved under the second load profile are different. Since the service availabilities achieved are different in the second load profile, we proceed to investigate how the distribution of service availabilities across the services can be controlled by adjusting the rewards vector.     

Competitive Analysis of Network Load Balancing

This paper presents a theoretical analysis of the Load Balancing Problem (LBP) in a network of processing units. The performance objective is to minimize the makespan, i.e., the time spent to finish all jobs in a network of processing units. Because of the communication delay that results from the network topology, it is impossible to have a strategy which obtains the exact optimum under all load distributions. Instead, we measure the information efficiency of a load balancing policy by the worst case ratio of the solution (for each load distribution) of a load balancing policy to the optimal solution (for the same load distribution) assuming that processors have complete information about the load distribution over the network. This ratio is called the competitive ratio of this strategy [17, 24, 34]. In particular, a policy is calledcompetitiveif this ratio is bounded by a constant. As a first step, we discuss the centralized LBP, where all the processors have complete information of the load distribution over a network. Its solution serves as a benchmark to compare with realistic strategies, both in theoretical analysis, and experimental and simulational studies of distributed algorithms. We show that when jobs have different sizes, even with preemptive scheduling, LBP is NP–complete. When the jobs are of the same size, we give a polynomial algorithm, using network–flow techniques, which extends to approximate solutions for jobs of different sizes. We apply this benchmark solution in order to analyze the competitiveness for three network topologies: completely connected graphs, rings, and hierarchical completek-ary trees. The constant competitive ratio results for complete network and hierarchical completek-ary trees are applied to a study on the issues of network designs suitable for the LBP. We further discuss the problem for general networks with jobs of different sizes for slightly weaker results than those for the constant competitive ratio requirement. Finally, we comment on the related issues of job partitioning over parallel/distributed systems.     

Adaptive QoS Control Based on Benefit Optimization for Video Servers Providing Differentiated Services

We propose and analyze quality of service (QoS) control algorithms for video servers designed to provide differentiated video streaming services. The design concepts are based on resource reservation and benefit optimization so that resources are reserved dynamically and adaptively for different QoS levels in response to the changing workload of the system, with the objective of maximizing the benefit throughput obtainable by the system. We analyze the benefit throughput obtainable by the system for a baseline algorithm for which the QoS levels of admitted users are not changed during the service lifetime and a greedy algorithm that may raise QoS levels of admitted users due to resources being free from departure events. We validate the design of these two QoS control algorithms via a detailed simulation study.     

Enhancing VoIP service for ubiquitous communication in a campus WLAN with partial coverage

The IEEE 802.11 WLAN technology has become the de facto standard for wireless Internet access. The spotty coverage of WLAN access points, however, confines the applicability of many real-time services such as VoIP within the boundary of the WLAN service area. In this paper, we investigate the problem of enhancing VoIP service for ubiquitous communication in a WLAN with spotty service area. We consider a university campus that has an established infrastructure for supporting SIP-based VoIP service through either wired or wireless data networks. The campus WLAN service does not have 100% full coverage, and hence users cannot make untethered VoIP calls anywhere on campus. The goal of this paper is to overcome the limitations of such “dead spots” for motivating the use of campus IP telephony service. To proceed, we start with two approaches called one-hop extension and dual-mode communication. The first approach uses multi-hop relay to extend the WLAN coverage, while the second approach leverages the availability of dual-mode handsets for ubiquitous voice communication. We implement the two approaches, and evaluate their performance in the campus testbed environment. We find that while the two approaches can effectively allow voice communication in WLAN dead spots, they have one common problem as the potential lack of support for voice call continuity that can cause degradation of the speech quality to an active call. We adopt a cross-layer solution based on signal processing algorithms to address the problem, thus achieving seamless voice call continuity while enabling ubiquitous voice communication on campus. Testbed evaluation shows promising results for future research along the proposed direction.     

QoS-aware,access-efficient,and storage-efficient replica placement in grid environments

In this paper, we study the quality-of-service (QoS)-aware replica placement problem in grid environments. Although there has been much work on the replica placement problem in parallel and distributed systems, most of them concern average system performance and have not addressed the important issue of quality of service requirement. In the very few existing work that takes QoS into consideration, a simplified replication model is assumed; therefore, their solution may not be applicable to real systems. In this paper, we propose a more realistic model for replica placement, which consider storage cost, update cost, and access cost of data replication, and also assumes that the capacity of each replica server is bounded. The QoS-aware replica placement is NP-complete even in the simple model. We propose two heuristic algorithms, called greedy remove and greedy add to approximate the optimal solution. Our extensive experiment results demonstrate that both greedy remove and greedy add find a near-optimal solution effectively and efficiently. Our algorithms can also adapt to various parallel and distributed environments.     

Extending TINA with Secure On-Line Accounting Services

Concepts and principles of TINA (Telecommunications Information Networking Architecture) are introduced with the objective of correcting problems of the current centralized service control and service data model in an IN (Intelligent Network). It is becoming increasingly clear that the future sophisticated telecommunication services, e.g., multimedia, and multi-party conferencing, breaking away from the traditional telephony call model will need the solutions for rapid and efficient introduction, deployment, operations, and management.In this paper, we discuss accounting features and requirements, as well as security services in the TINA management context. We will introduce and present an implementation of a model for a security management, based on secure objects, cryptography and certificate distribution. In order to provide secure services, secure objects that have security functionality, such as authentication and access control, have been defined. Secure objects in our model are CORBA objects. The security domain is also called SBS (Security Base Server), provides security services and has an SMIB (Security Management Information Base) that contains security policies, cryptographic algorithms, and other relevant information. A prototype has been implemented and some experimental results are presented.     

Perfect load balancing on the star interconnection network

In this paper, we use the regular distribution method to design a perfect load balancing algorithm for an n-star with a maximum error of 1 and a time complexity of 3n(n+1). This algorithm is based on the novel notion of leader trees. A second algorithm proposed in this paper as an enhancement to our first algorithm and uses an arbitrary spanning tree as the leader tree and has a worst time complexity of 2.25n ²−3n+0.75. We also discuss the issue of dynamically selecting the leader tree and hybrid load balancing algorithms in general. Furthermore, we present a hybrid algorithm for load balancing on the star interconnection network which benefits from a diffusion load balancing preprocessing phase and shows a smaller mean time complexity than our two first algorithms.     

Floating content for probabilistic information sharing

People are increasingly using online social networks for maintaining contact with friends and colleagues irrespective of their physical location. While such services are essential to overcome distances, using infrastructure services for location-based services may not be desirable. In contrast, we design and analyze a fully distributed variant of an ephemeral content sharing service, solely dependent on the mobile devices in the vicinity using principles of opportunistic networking. The result is a best effort service for floating content in which content is created locally, its availability is geographically limited and its lifetime and spreading depends on interested nodes being available. In this paper, we present our system design, algorithms, and protocol specification in detail. A set of real world experiments is then used to assess the achievable transmission rates and transmission ranges in such a system. We validate our previous analytical results and assess the performance of floating content in general and especially of different replication and deletion strategies by means of extensive simulations using a map-based mobility model in downtown Helsinki.     

考虑服务性能的计算机网络级联失效建模

为分析计算机网络中级联失效对服务性能的影响,在考虑初始负载、节点转发速率和路由策略的基础上,建立一种基于负载容量的级联失效模型。定义吞吐量、负载率和服务时延3个评价参数,对级联失效发生前后网络服务性能的变化进行度量。以BA无标度网络为对象进行仿真实验,结果表明,该模型能客观反映级联失效导致网络服务性能急剧下降的现象,对级联失效的预防和控制具有一定指导意义。     

Static and dynamic adaptations for service-based systems

Context

In service-oriented computing (SOC), service providers publish reusable services, and service consumers subscribe them. However, there exist potential problems in reusing services. Mismatch is a problem that occurs when a candidate service does not fully match to the feature expected. Fault is a problem that occurs when an invocation of services results in some abnormality at runtime. Without remedying mismatch problems, services would not be reusable. Without remedying fault problems, service invocations at runtime would result in failures. Static and dynamic adaptations are practical approaches to remedying the problems.

Objective

Our objective is to define a comprehensive framework which includes a design of service adaptation framework (SAF), and design of static and dynamic adapters.

Method

We design the SAF which governs dynamic adaptations, and define a service life-cycle with adaptation-related activities. Based on causal–effect relationships among mismatch, fault, cause, and adapter, we derive mismatches and faults, from which their relevant causes are identified. For the causes, we define six static adapters and five dynamic adapters. We specify instructions for designing static adapters, and provide step-wise algorithms for designing dynamic adapters based on enterprise service bus (ESB). And, we show a proof-of-concept (POC) of implementation to show applicability of the methods.

Results

The paper presents service life-cycle with adaptation-related activities, SAF design, and design of static and dynamic adapters.

Conclusion

Mismatch and fault problems in utilizing services present threats to high reusability of services. Static adaptations can remedy mismatch problems, and dynamic adaptations can remedy fault problems. In this paper, we presented technical insights of service adaption, SAF design, and definitions of static and dynamic adapters. By utilizing the proposed SAF and service adapters, reusability of services can be greatly enhanced.     

A novel memory management scheme for residential gateways

Home gateways must manage services despite limited memory resources. In home gateway models (e.g., OSGi), services are implemented as software bundles (or plug-ins) that can be downloaded from the Internet and executed in the gateway. Services, in gateways, are not independent; they collaborate and complement each other. The problem we are solving is as follow: when the gateway runs out of memory, which service(s) will be stopped or kicked out of memory to start a new service? The problem was initially inspired by the FTTH (Fibre To The Home) trail project in Japan with NTT because of the limited memory in Panasonic set-top-box IP-STB. Note that stopping a given service means that all the services that depend on it will be stopped too. Because of the service dependencies, traditional memory management techniques, such as best fit, first fit, or worst fit, are not suitable. Our goal is to minimize the total number of stopped services while fulfilling the request of the new service. In this paper, we present two algorithms for service replacement and memory management in home gateways. The algorithms take into consideration the dependencies between different services, in addition to the amount of memory occupied by each service. The first one achieves optimal solution in O(n ²) time and O(nh) space, using dynamic programming. However, the optimal solution requires substantial memory and CPU resources. Then we propose a heuristic that compute solutions very close to the optimal but with much less time and space requirements. We carry simulation experiments to evaluate the effectiveness of the proposed techniques and compare them with traditional memory management techniques.     

Internet-based interactive HDTV

Traditional interactive TV systems depend on expensive hardware, proprietary formats, and a closed-loop end-to-end approach, which greatly limits scalability and extensibility of TV services. In this paper, we present the HDControl interactive Internet TV architecture that achieves an open service model and combines high-quality video with flexible user control using two key software real-time algorithms: visual information embedding (VIE) algorithm and resynchronization algorithm. Experimental results in our HDTV testbed have confirmed the feasibility and efficiency of our proposed algorithms.     

Providing End-to-End Quality of Service with Optimal Least Weight Routing in Next-Generation Multiservice High-Speed Networks

Routing algorithms play a critical role in meeting both the stringent quality of service (QoS) requirements of guaranteed services and the certain QoS requirement of assured services over next-generation multiservice high-speed networks. In this paper, we propose the use of optimal least weight routing (OLWR) algorithm for routing QoS flows in high-speed networks. The main principle of our algorithm is that the choice of the most appropriate route is based on a set of parameters (least weight parameters) that estimate and consider the impact that the acceptance and routing decision of a call request belonging to a specific class would have on the network and other classes of service. Effective bandwidth, bandwidth and trunk reservation techniques, along with load balancing and packing trade-off considerations, are also introduced in the proposed routing algorithm. The performance evaluation of our algorithm is achieved via modeling and simulation of multiclass service routing in various network topologies. The performance results demonstrated that OLWR outperforms both the multihop least-loaded routing algorithms and the multihop most-loaded routing algorithms in terms of both revenue and carried load.     

Market segmentation using service levels in data networks

The objective of this paper is to study a communication system based on aM ^(x)/ D/1 queueing system representing a cell-switch network like Asynchronous Transfer Mode (ATM) network. Network structure consists of a single link modeled as a batch arrival markovian queue with non-preemptive head of the line priority service. Network manager (NM) is assumed to be a decision maker at a Management Information System (MIS) department. This paper establishes the incentive compatible pricing which maximizes the net value of the overall corporation, while the delays have to satisfy the Quality of Service (QoS) guarantees. We obtain structural results for the two priority case in the short run. In equilibrium, we find that the network manager maximizes the price spread between the two priority class services. We prove that as the capacity level increases indefinitely, the market is equally divided among the priority classes. In the first part of the paper, we assume that the users do not respond to network manager’s prices. In the second part, we relax this assumption and look at a leader follower game. Users choose their willingness to pay by deciding on how much value they assign to timely transmission of messages after seeing the prices set by the network manager. Our results indicate that unless there is high enough capacity set upex ante, monopoly network provider cannot price discriminate by offering different quality of service via priority classes. This trade-off between ex ante capacity level choice and ex post price discrimination decision is eliminated if the capacity is set high. It is shown in the network literature that best effort services lead to lower quality of service, in general, for a single service. We show that this holds in multiple priority services as well. We prove that when the capacity is also considered as a decision variable, simultaneous capacity and price setting yields the same optimal level with sequential capacity and price choices.