Discrete particle swarm optimization algorithms for two variants of the static data segment location problem

We consider the static data segment location problem in information networks. This problem was introduced by Sen et al. (Comput Oper Res, 62:282–295 2015). We consider the problem of optimally locating large volumes of digital content that is accessed via a distributed network. A database is pre-partitioned into multiple segments and the problem is one of placing these segments at servers located in different regions. We need to jointly consider four specific subproblems: (1) the problem of locating servers in the network, (2) the problem of allocating specific data segments to each of the servers, (3) the problem of assigning users to the servers based on their query patterns, and, (4) routing queries through the network. We consider two variants of this problem depending on the topology of the network through which the servers are connected: a mesh topology and a tree topology. In this paper, we develop a solution approach based on a discrete particle swarm optimization approach. We demonstrate the superiority of our approach by comparing its performance against solutions to benchmark instances obtained previously using a simulated annealing approach (Networks, 68(1):4–22 2016b).     

Aggregation method experimentation for large-scale network location problems

We present demand point aggregation procedures for the p-median and p-center network location models. A coarse aggregation structure is initially obtained by partitioning the demand points according to a grid imposed over the demand region. A “row-column’’ aggregation algorithm is used to determine the spacing of rows and columns of the grid to exploit the problem structure. A second step involves locating aggregate demand points on the subnetworks induced by the cells of the grid partitioning. The aggregate demand point set so obtained then defines an approximating location model; alternatively, it may initialize an iterative network location–allocation procedure to find the aggregate demand points. We have tested our procedures on data sets based on maps from the TIGER/Line database of the United States Census Bureau, and report on our computational experience.     

Secure dynamic fragment and replica allocation in large-scale distributed file systems

We present a distributed algorithm for file allocation that guarantees high assurance, availability, and scalability in a large distributed file system. The algorithm can use replication and fragmentation schemes to allocate the files over multiple servers. The file confidentiality and integrity are preserved, even in the presence of a successful attack that compromises a subset of the file servers. The algorithm is adaptive in the sense that it changes the file allocation as the read-write patterns and the location of the clients in the network change. We formally prove that, assuming read-write patterns are stable, the algorithm converges toward an optimal file allocation, where optimality is defined as maximizing the file assurance.     

A neural networks algorithm for data path synthesis

This paper presents a deterministic parallel algorithm to solve the data path allocation problem in high-level synthesis. The algorithm is driven by a motion equation that determines the neurons firing conditions based on the modified Hopfield neural network model of computation. The method formulates the allocation problem using the clique partitioning problem, an NP-complete problem, and handles multicycle functional units as well as structural pipelining. The algorithm has a running time complexity of O(1) for a circuit with n operations and c shared resources. A sequential simulator was implemented on a Linux Pentium PC under X-Windows. Several benchmark examples have been implemented and favorable design comparisons to other synthesis systems are reported.     

Resource allocation optimization for quantitative service differentiation on server clusters

The goal of service differentiation is to provide different service quality levels to meet changing system configuration and resource availability and to satisfy different requirements and expectations of applications and users. In this paper, we investigate the problem of quantitative service differentiation on cluster-based delay-sensitive servers. The goal is to support a system-wide service quality optimization with respect to resource allocation on a computer system while provisioning proportionality fairness to clients. We first propose and promote a square-root proportional differentiation model. Interestingly, both popular delay factors, queueing delay and slowdown, are reciprocally proportional to the allocated resource usage. We formulate the problem of quantitative service differentiation as a generalized resource allocation optimization towards the minimization of system delay, defined as the sum of weighted delay of client requests. We prove that the optimization-based resource allocation scheme essentially provides square-root proportional service differentiation to clients. We then study the problem of service differentiation provisioning from an important relative performance metric, slowdown. We give a closed-form expression of the expected slowdown of a popular heavy-tailed workload model with respect to resource allocation on a server cluster. We design a two-tier resource management framework, which integrates a dispatcher-based node partitioning scheme and a server-based adaptive process allocation scheme. We evaluate the resource allocation framework with different models via extensive simulations. Results show that the square-root proportional model provides service differentiation at a minimum cost of system delay. The two-tier resource allocation framework can provide fine-grained and predictable service differentiation on cluster-based servers.     

Efficient solution of a class of location–allocation problems with stochastic demand and congestion

We consider a class of location–allocation problems with immobile servers, stochastic demand and congestion that arises in several planning contexts: location of emergency medical clinics; preventive healthcare centers; refuse collection and disposal centers; stores and service centers; bank branches and automated banking machines; internet mirror sites; web service providers (servers); and distribution centers in supply chains. The problem seeks to simultaneously locate service facilities, equip them with appropriate capacities, and allocate user demand to these facilities such that the total cost, which consists of the fixed cost of opening facilities with sufficient capacities, the access cost of users׳ travel to facilities, and the queuing delay cost, is minimized. Under Poisson user demand arrivals and general service time distributions, the problem is set up as a network of independent M/G/1 queues, whose locations, capacities and service zones need to be determined. The resulting mathematical model is a non-linear integer program. Using simple transformation and piecewise linear approximation, the model is linearized and solved to ϵ-optimality using a constraint generation method. Computational results are presented for instances up to 400 users, 25 potential service facilities, and 5 capacity levels with different coefficients of variation of service times and average queueing delay costs per customer. The results indicate that the proposed solution method is efficient in solving a wide range of problem instances.     

Negotiation on Data Allocation in Multi-Agent Environments

In this paper, we consider the problem of data allocation in environments of self-motivated servers, where information servers respond to queries from users. New data items arrive frequently and have to be allocated in the distributed system. The servers have no common interests, and each server is concerned with the exact location of each of the data items. There is also no central controller. We suggest using a negotiation framework which takes into account the passage of time during the negotiation process itself. Using this negotiation mechanism, the servers have simple and stable negotiation strategies that result in efficient agreements without delays. We provide heuristics for finding the details of the strategies which depend on the specific settings of the environment and which cannot be provided to the agents in advance. We demonstrate the quality of the heuristics, using simulations. We consider situations characterized by complete, as well as incomplete, information and prove that our methods yield better results than the static allocation policy currently used for data allocation for servers in distributed systems.     

Designing a distributed database on a local area network: a methodology and decision support system

Local area networks (LANs) are important for an enterprise to hold a competitive edge. Many companies have therefore converted terminal-based computing systems to LAN-based distributed data processing systems. This paper proposes a design methodology for distributed databases connected by a LAN. Two primary objectives of the methodology are: (i) to allocate data files and workload among heterogeneous servers; and (ii) to determine the number of servers to satisfy the response time required for processing each transaction. The file and workload allocation decision is formulated as a nonlinear zero–one integer programming problem. This problem is proven to be NP-complete. A heuristic is developed to solve this problem effectively. A decision support system is implemented and an example is solved to illustrate the practical usefulness of the system.     

通过V-GridFTP提高数据访问性能

数据网格需要文件传输服务(FTP)。但是,目前数据网格中使用的FTP服务具有存储内容独立的局限性,这一局限性造成了诸如数据定位困难、服务器之间负荷不均衡等问题。该文提出了V-GridFTP的概念,将原本内容独立的物理服务器联结起来协同工作,在信息服务的协助下,通过数据分区、复制以及GridFTP等技术,实现了资源分布动态自适应调整,为用户提供高性能、高可用性、高可靠性的FTP服务。这里开发了一个原型系统。测试显示系统运行良好。     

I/O-efficient join dependency testing,Loomis–Whitney join,and triangle enumeration

We revisit two fundamental problems in database theory. The join-dependency (JD) testing problem is to determine whether a given JD holds on a relation r. We prove that the problem is NP-hard even if the JD involves only relations each of which has only two attributes. The JD-existence testing problem is to determine if there exists any non-trivial JD satisfied by r. We present an I/O-efficient algorithm in the external memory model, which in fact settles the closely related Loomis–Whitney enumeration problem. As a side product, we solve the triangle enumeration problem with the optimal I/O-complexity, improving a recent result of Pagh and Silvestri in PODS'14.     

Strategies for peer-to-peer downloading

An advantage of peer-to-peer applications is that files can be shared without concentrated load on file servers. This note proposes deterministic techniques for splitting a files into segments so that, for certain restricted cases of arrival and server rates, users may copy files from one another without fetching the data from file servers.     

Faster Algorithms for Stable Allocation Problems

We consider a high-multiplicity generalization of the classical stable matching problem known as the stable allocation problem, introduced by Baïou and Balinski in 2002. By leveraging new structural properties and sophisticated data structures, we show how to solve this problem in O(mlog?n) time on a bipartite instance with n vertices and m edges, improving the best known running time of O(mn). Building on this algorithm, we provide an algorithm for the non-bipartite stable allocation problem running in O(mlog?n) time with high probability. Finally, we give a polynomial-time algorithm for solving the “optimal” variant of the bipartite stable allocation problem, as well as a 2-approximation algorithm for the NP-hard “optimal” variant of the non-bipartite stable allocation problem.     

基于Web的跨平台分布式多线程文件服务器设计

分析了以往分布式文件服务器的不足,提出了一种以J2EE技术为核心的基于Web的跨平台分布多线程文件服务器的设计方案,该分布式文件服务器由一个集中控制单元和多个本地文件服务器组成,集中控制单元以数据库的地文件逻辑信息进行集中式管理,文件的物理信息则上位于Web不同节点上的本地文件服务器分布式地管理,本地文件服务器支持多线程文件操作和Windows,Unix,Linux等多种操作系统的文件系统。     

Flexible bandwidth assignment with application to optical networks

We introduce two scheduling problems, the flexible bandwidth allocation problem (\(\textsc {FBAP}\)) and the flexible storage allocation problem (\(\textsc {FSAP}\)). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In \(\textsc {FBAP}\), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in \(\textsc {FSAP}\) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore \(\text {NP-hard}\). Our main results are a 3-approximation algorithm for \(\textsc {FBAP}\) and a \((3+\epsilon )\)-approximation algorithm for \(\textsc {FSAP}\), for any fixed \(\epsilon >0 \). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a \((2+\epsilon )\)-approximation algorithm for \(\textsc {SAP}\), for any fixed \(\epsilon >0 \), thus improving the best known ratio of \(\frac{2e-1}{e-1} + \epsilon \). Our study is motivated also by critical resource allocation problems arising in all-optical networks.     

Distributed computer system design: An interactive procedure

This paper presents an overview of an interactive system for the design of a distributed computer system. The system helps the designer in finding the optimal combination of processors of varying power to be located at various nodes of the system. It also helps in finding the optimal allocation of data files or databases. The system allows the designer to trade-off between the conflicting objectives: low investment and operating cost and high availability of data. Reasonable relative weights are assigned to each data file, and design objectives can be assigned priorities. A value added network such as TELENET is assumed for data communication. Also, multiple copies of the data file or database may exist in the system to achieve higher data availability and better response time.     

Artificial immune network-based anti-collision algorithm for dense RFID readers

Radio frequency identification (RFID) is faced with reader-to-reader collision problem when multiple readers are deployed densely. In scheduling-based methods, the reader-to-reader collision problem can be often mitigated from the viewpoint of optimized resource allocation to readers, which aims at maximizing the total effective interrogation area of an RFID reader network. This paper formulates a reader-to-reader anti-collision model with respect to physical positions, time slots, frequency channels and transmitting power, and thus proposes an artificial immune network with hybrid encoding for resource allocation (AINetHE-RA) to solve this model. In AINetHE-RA, a candidate antibody consists of a location segment, a channel segment and a power segment, where time slots are hidden in the last two segments. According to their respective properties, the location segment and the power segment are encoded by using real number; while the channel segment is encoded by integer number. This is the hybrid encoding format in essence. Correspondingly, in the mutation operator, different mutation strategies are designed for three segments, respectively, which make AINetHE-RA solve this reader-to-reader anti-collision model efficiently. In simulation experiments, the effects of such parameters as time slots, frequency channels, power values and locations are first investigated, and the total effective interrogation area and the number of identified tags are evaluated for the single and multiple density tag distribution. Especially, as an industrial example of non-uniform random tag distribution, the simple sectionalized warehouse management is considered to evaluate the performance of AINetHE-RA. The simulation results demonstrate that the proposed AINetHE-RA algorithm is effective and efficient in mitigating the reader-to-reader collision problem in dense RFID networks and outperforms such methods as GA-RA, PSO-GA and opt-aiNet-RA in finding the optimal resource allocation schemes.     

Load balanced and optimal disk allocation strategy for partial match queries on multidimensional files

A multidimensional file is one whose data are characterized by several attributes, each specified in a given domain. A partial match query on a multidimensional file extracts all data whose attributes match the values of one or more attributes specified in the query. The disk allocation problem of a multidimensional file F on a database system with multiple disks accessible in parallel is the problem of distributing F among the disks such that the data qualifying for each partial match query are distributed as evenly as possible among the disks of the system. We propose an optimal solution to this problem for multidimensional files with pairwise prime domains based on a large and flexible class of maximum distance separable codes, namely, the redundant residue codes. We also introduce a new family of residue codes, called the redundant nonpairwise prime residue codes, to deal with files whose attribute domains are nonpairwise prime.     

Peer Assisted Video Streaming With Supply-Demand-Based Cache Optimization

In this paper, we consider a hybrid P2P video on-demand architecture that utilizes both the server and the peer resources for efficient transmission of popular videos. In our system architecture, each peer dedicates some cache space to store a particular segment of a video file as well as some of its upload bandwidth to serve the cached segment to other peers. Peers join the system and issue a streaming request to a control server. Control server directs the peers to streaming servers or to other peers who have the desired video segments. Control server also decides which peer should cache which video segment. Our main contribution in this paper is to determine the proper caching strategies at peers such that we minimize the average load on the streaming servers.      

An optimized approach for storing and accessing small files on cloud storage

Hadoop distributed file system (HDFS) is widely adopted to support Internet services. Unfortunately, native HDFS does not perform well for large numbers but small size files, which has attracted significant attention. This paper firstly analyzes and points out the reasons of small file problem of HDFS: (1) large numbers of small files impose heavy burden on NameNode of HDFS; (2) correlations between small files are not considered for data placement; and (3) no optimization mechanism, such as prefetching, is provided to improve I/O performance. Secondly, in the context of HDFS, the clear cut-off point between large and small files is determined through experimentation, which helps determine ‘how small is small’. Thirdly, according to file correlation features, files are classified into three types: structurally-related files, logically-related files, and independent files. Finally, based on the above three steps, an optimized approach is designed to improve the storage and access efficiencies of small files on HDFS. File merging and prefetching scheme is applied for structurally-related small files, while file grouping and prefetching scheme is used for managing logically-related small files. Experimental results demonstrate that the proposed schemes effectively improve the storage and access efficiencies of small files, compared with native HDFS and a Hadoop file archiving facility.