Configuration of overloaded servers with dynamic routing

We consider overload of servers in a network with dynamic routing of messages. The system consists of k servers and ℓ independent Poisson input flows. Messages from each flow are directed to m servers, and each message is directed to a server that is the least loaded at the moment of its arrival. In such a system, configuration of overloaded servers depends on the intensity of input flows. A similar effect was considered in [1] for a system with another geometry.     

一个新的(t,N-2)弹性的Mix Net

Mix net是实现匿名通信、电子投票选举、电子支付以及电子投标的有力工具．该文建立了(t，N-2)Mix net模型，利用Shamir门限方案、E1Gamal公钥体制、零知识证明等密码技术设计了一个基于这个模型的Mix net协议．该协议将同一密文组让不同的两个服务器组进行盲化解密示证和比较，从而使得该协议具有(t-1，N-2)^AA弹性及秘密性、正确性和可验证性等优点，同时通信量和计算量方面也少于已知的基于E1Gamal公钥体制的可验证Mix net协议．     

A model of periodic acknowledgement

We study a problem abstracted from modeling a multicast protocol. In our model, messages generated by a single source are simultaneously forwarded to a set of receivers where they are independently processed. We assume a state-dependent message arrival rate and memoryless service time distributions. The receivers may process messages at different average rates. Messages processed by all receivers are periodically acknowledged and cleared from the system. Due to finite buffer space, the total number of non-acknowledged messages in the system is limited. Our focus in this paper is on the number of messages cleared at acknowledgement time.

The problem under consideration bears resemblance to a fork/join process with heterogeneous servers, used in the study of multiprocessing computer systems. Our model includes the additional features of finite buffer space and delayed periodic departure of completed jobs. Even without these features, the resulting type of queuing model has no known closed-form solution in the general case of more than two servers. Because the arrival processes to the servers are correlated, the model is difficult to decompose. We propose a relatively simple decomposition technique and a fixed-point iteration scheme. In our approach, we consider each receiver (server) in isolation, and we account for the influence of other receivers through the probability that a given number of messages can be cleared at acknowledgement time. We derive elementary differential equations for the number of messages processed by a receiver. These equations involve the conditional probability of the number of messages not yet processed given the number of messages waiting to be cleared. We compute an approximate solution using the conditional probability obtained from a model with exponentially distributed acknowledgement periods. Our numerical results for the average number of messages cleared at acknowledgment time are typically within a few percent of simulation midpoints.     

过载服务器的性能研究

针对服务器过载时的性能对Linux的相关源代码进行了分析.用排队论分析了内核的收包过程,得出了关于服务器在过载时性能的几个结论.基于上述分析提出并在Linux上实现了提高服务器在过载时性能的方法.实验证明这些方法能有效防止活锁现象,极大地提高服务器在高负载情况下的性能.     

An auto-responsive honeypot architecture for dynamic resource allocation and QoS adaptation in DDoS attacked networks

Distributed Denial of Service (DDoS) attacks generate flooding traffic from multiple sources towards selected nodes. Diluted low rate attacks lead to graceful degradation while concentrated high rate attacks leave the network functionally unstable. Previous approaches to such attacks have reached to a level where survivable systems effort to mitigate the effects of these attacks. However, even with such reactive mitigation approaches in place, network under DDoS attack becomes unstable and legitimate users in the network suffer in terms of increased response times and frequent network failures. Moreover, the Internet is dynamic in nature and the topic of automated responses to attacks has not received much attention.In this paper, we propose a proactive approach to DDoS in form of integrated auto-responsive framework that aims to restrict attack flow reach target and maintain stable network functionality even under attacked network. It combines detection and characterization with attack isolation and mitigation to recover networks from DDoS attacks. As first line of defense, our method uses high level specifications of entropy variations for legitimate interactions between clients and servers. The network generates optimized entropic detectors that monitor the behavior of flows to identify significant deviations. As the second line of defense, malicious flows are identified and directed to isolated zone of honeypots where they cannot cause any further damage to the network and legitimate flows are directed to a randomly selected server from pool of replicated servers. This approach leads the attacker to believe that they are succeeding in their attack, whereas in reality they are simply wasting time and resources.Service replication and attack isolation alone are not sufficient to mitigate the attacks. Limited network resources must be judiciously used when an attack is underway. Further, as third line of defense, we propose a Dynamic Honeypot Engine (DHE) modeled as a part of Honeypot Controller (HC) module that triggers the automatic generation of adequate nodes to service client requests and required number of honeypots that interact with attackers in contained manner. This load balancing in the network makes it attack tolerant. Legitimate clients, depending upon their trust levels built according to their monitored statistics, can track the actual servers for certain time period. Attack flows reaching honeypots are logged by Honeypot Data Repository (HDR). Most severe flows are punished by starting honeypot back propagation sessions and filtering them at the source as the last line of defense. The data collected on honeypots are used to isolate and filter present attack, if any and as an insight into future attack trends. The judicious mixture and self organization of servers and honeypots at different time intervals also guaranties promised QoS.We present the exhaustive parametric dependencies at various phases of attack and their regulation in real time to make the service network DDoS attack tolerant and insensitive to attack load. Results show that this auto-responsive network has the potential to maintain stable network functionality and guaranteed QoS even under attacks. It can be fine tuned according to the dynamically changing network conditions. We validate the effectiveness of the approach with analytical modeling on Internet type topology and simulation in ns-2 on a Linux platform.     

A multi-layer client–server queueing network model with non-hierarchical synchronous and asynchronous messages

We analyze a multi-layered queueing network that models a client–server system where clients and servers communicate via synchronous and asynchronous messages. The servers are organized in groups such that they form a multi-layered structure. The messaging pattern is non-hierarchical, i.e., a client can send a message to a server belonging to any layer, and a server from a layer-i may issue messages to a server belonging to any higher layer, j>i. The queueing network is analyzed approximately using a decomposition algorithm. Numerical tests show that the approximation algorithm has a good accuracy.     

A calculus for stochastic QoS analysis

The issue of Quality of Service (QoS) performance analysis in packet-switched networks has drawn a lot of attention in the networking community. There is a lot of work including an elegant theory under the name of network calculus, which focuses on analysis of deterministic worst case QoS performance bounds. In the meantime, researchers have studied stochastic QoS performance for specific schedulers. However, most previous works on deterministic QoS analysis or stochastic QoS analysis have only considered a server that provides deterministic service, i.e. deterministically bounded rate service. Few have considered the behavior of a stochastic server that provides input flows with variable rate service, for example wireless links. In this paper, we propose a stochastic network calculus to analyze the end-to-end stochastic QoS performance of a system with stochastically bounded input traffic over a series of deterministic and stochastic servers. We also prove that a server serving an aggregate of flows can be regarded as a stochastic server for individual flows within the aggregate. Based on this, the proposed framework is further applied to analyze per-flow stochastic QoS performance under aggregate scheduling.     

Routing Internet traffic in heterogeneous mesh networks: Analysis and algorithms

In practical wireless mesh networks (WMNs), gateways are subject to hard capacity limits on the aggregate number of flows (in terms of bit rate) that they can support. Thus, if traffic is routed in the mesh network without considering those constraints, as well as the traffic distribution, some gateways or intermediate mesh routers may rapidly get overloaded, and the network resources can be unevenly utilized. To address this problem, in this paper we firstly develop a multi-class queuing network model to analyze feasible throughput allocations, as well as average end-to-end delay, in heterogeneous WMNs. Guided by our analysis, we design a Capacity-Aware Route Selection algorithm (CARS), which allocates network paths to downstream and upstream Internet flows so as to ensure a more balanced utilization of wireless network resources and gateways’ fixed connections. Through simulations in a number of different network scenarios we show that the CARS scheme significantly outperforms conventional shortest path routing, as well as an alternative routing method that distributes the traffic load on the gateway nodes to minimize its variance.     

Large-scale indexing of spatial data in distributed repositories: the SD-Rtree

We propose a scalable distributed data structure (SDDS) called SD-Rtree. We intend our structure for point, window and kNN queries over large spatial datasets distributed on clusters of interconnected servers. The structure balances the storage and processing load over the available resources, and aims at minimizing the size of the cluster. SD-Rtree generalizes the well-known Rtree structure. It uses a distributed balanced binary tree that scales with insertions to potentially any number of storage servers through splits of the overloaded ones. A user/application manipulates the structure from a client node. The client addresses the tree through its image that can be possibly outdated due to later split. This may generate addressing errors, solved by the forwarding among the servers. Specific messages towards the clients incrementally correct the outdated images. We present the building of an SD-Rtree through insertions, focusing on the split and rotation algorithms. We follow with the query algorithms. We describe then a flexible allocation protocol which allows to cope with a temporary shortage of storage resources through data storage balancing. Experiments show additional aspects of SD-Rtree and compare its behavior with a distributed quadtree. The results justify our various design choices and the overall utility of the structure.     

A multilayer client-server queueing network model with synchronous and asynchronous messages

We analyze a multilayered queueing network that models a client-server system where clients and servers communicate via synchronous and asynchronous messages. The servers are organized in groups such that they form a multilayered hierarchical structure. The queueing network is approximately analyzed using a decomposition algorithm. Numerical tests show that the approximation algorithm has a good accuracy.     

QoS Driven Parallelization of Resources to Reduce File Download Delay

In this paper, we propose a novel approach for reducing the download time of large files over the Internet. Our approach, known as Parallelized File Transport Protocol (P-FTP), proposes simultaneous downloads of disjoint file portions from multiple file servers. P-FTP server selects file servers for the requesting client on the basis of a variety of QoS parameters, such as available bandwidth and server utilization. The sensitivity analysis of our file server selection technique shows that it performs significantly better than random selection. During the file transfer, P-FTP client monitors the file transfer flows to detect slow servers and congested links and adjusts the file distributions accordingly. P-FTP is evaluated with simulations and real-world implementation. The results show at least 50 percent reduction in download time when compared to the traditional file-transfer approach. Moreover, we have also carried out a simulation-based study to investigate the issues related to large scale deployment of our approach on the Internet. Our results demonstrate that a large number of P-FTP users has no adverse effect on the performance perceived by non-P-FTP users. In addition, the file servers and network are not significantly affected by large scale deployment of P-FTP.     

Virtual network transport protocols for Myrinet

Bringing direct and protected network multiprogramming into mainstream cluster computing requires innovations in three key areas: application programming interfaces, network virtualization systems, and lightweight communication protocols for high-speed interconnects. The AM-II API extends traditional active messages with support for client-server computing and facilitates the construction of parallel clients and distributed servers. Our virtual network segment driver enables a large number of arbitrary sequential and parallel applications to access network interface resources directly in a concurrent but fully protected manner. The NIC-to-NIC communication protocols provide reliable and at-most-once message delivery between communication endpoints. The NIC-to-NIC protocols perform well as the number of endpoints and the number of hosts in the cluster are scaled. The flexibility afforded by the underlying protocols enables a diverse set of timely research efforts. Other Berkeley researchers are actively using this system to investigate implicit techniques for the coscheduling of communicating processes, an essential part of high-performance communications in multiprogrammed clusters of uni- and multiprocessor servers. Other researchers are extending the active message protocols described here for clusters of symmetric multiprocessors, using so-called multiprotocol techniques and multiple network interfaces per machine     

Pagerank Computation and Keyword Search on Distributed Systems and P2P Networks

This paper presents a fully distributed computation for Google's pagerank algorithm. The computation is based on solution of the matrix equation defining pageranks by a distributed implementation of asynchronous iteration. Pageranks for the documents stored on a web server or on a host in a peer-to-peer network are computed in place and stored with the documents. The matrix is never assembled and no crawls of the web are required. Continuously accurate pageranks are enabled by incremental computation of pageranks for documents as they are inserted onto a network storage host and incremental recomputation of pageranks when documents are deleted. Intrahost and intradomain dominance of document link structure is naturally exploited by the distributed asynchronous iteration algorithm.Three implementations: (i) a simulation which was previously reported, (ii) an implementation of the algorithm in a peer-to-peer computational system and (iii) an embedding of the computation in web servers, are described. Application of the three implementations to three different workloads, two constructed following power law network models for link distributions and one derived from the Government document database are reported. Convergence for computation of a complete set of pageranks is rapid: 1% accuracy in 10 or fewer messages per document. Incremental computation of pageranks resulting from addition or deletion of documents also converges rapidly, usually requiring 10 or fewer messages per document.Coupling locally stored pageranks with the documents in a peer-to-peer network dramatically diminishes the volume of data which must be transmitted to satisfy keyword searches in peer-to-peer networks.The web server implementation shows that the distributed algorithm can be used to enable web servers to compute pageranks for the documents they store and thus potentially enable effective keyword searches for the documents stored on the web servers of intranets by utilizing unused processing power of the web servers.     

Load sharing in distributed multimedia-on-demand systems

Service providers have begun to offer multimedia-on-demand services to residential estates by installing isolated, small-scale multimedia servers at individual estates. Such an arrangement allows the service providers to operate without relying on a highspeed, large-capacity metropolitan area network, which is still not available in many countries. Unfortunately, installing isolated servers can incur very high server costs, as each server requires spare bandwidth to cope with fluctuations in user demand. The authors explore the feasibility of linking up several small multimedia servers to a (limited-capacity) network, and allowing servers with idle retrieval bandwidth to help out servers that are temporarily overloaded; the goal is to minimize the waiting time for service to begin. We identify four characteristics of load sharing in a distributed multimedia system that differentiate it from load balancing in a conventional distributed system. We then introduce a GWQ load sharing algorithm that fits and exploits these characteristics; it puts all servers' pending requests in a global queue, from which a server with idle capacity obtains additional jobs. The performance of the algorithm is captured by an analytical model, which we validate through simulations. Both the analytical and simulation models show that the algorithm vastly reduces wait times at the servers. The analytical model also provides guidelines for capacity planning. Finally, we propose an enhanced GWQ+L algorithm that allows a server to reclaim active local requests that are being serviced remotely. Simulation experiments indicate that the scheduling decisions of GWQ+L are optimal, i.e., it enables the distributed servers to approximate the performance of a large centralized server     

An open exponential queuing network with limited waiting spaces and losses: A method of approximate analysis

Open exponential queuing networks are considered where each node in a network represents several exponential servers with a joint waiting space (a buffer) of limited capacity. A customer arriving to a node with fully occupied buffer is lost. An assumption is made that the input flow to each node formed as a mixture of the external Poisson flow and the flows coming from other nodes is a Poisson flow. Under this assumption, a method of computing network parameters is presented which is based on solving iteratively a system of nonlinear equations for the unknown nodal flow rates. A method based on Markov chain techniques is presented to find the approximate value of the average conditional sojourn time in the network for customers which completed their service process in the network and for customers which were lost eventually. It is demonstrated for two types of a network (a complete 5-node graph and a 5-node tandem-type system) that the network parameters obtained by the derived analytic method are close to those obtained by the Monte Carlo simulation method.     

SIP自动测试工具的设计实现

SIP测试工具已成为测试SIP服务器健壮性不可缺少的手段,而现有的健壮性测试工具并不能很好的模拟实际网络中服务器遇到大量并发畸形消息的情况.针对这个问题,设计并实现一种新型测试工具,可以模拟大量并发非法消息来测试SIP服务器健壮性.该工具通过发送大量非法SIP消息引起SIP服务器软件的崩溃并给出原因,以便促进服务器健壮性的发展.实验结果表明,新工具可以完全自动对任意SIP服务器进行健壮性测试.     

An integrated congestion control mechanism for optimized performance using two-step rate controller in optical burst switching networks

Optical burst switching (OBS) is a promising solution to implement the optical internet backbone. However, the lack of adequate congestion-control mechanisms may result in high burst loss. Schemes such as fiber delay line (FDL), wavelength conversion, and deflection routing to reduce burst collision are unable to prevent the network congestion effectively. To address this problem, we propose and investigate a global solution, called Integrated Congestion-Control Mechanism (ICCM), for OBS networks. ICCM, which combines congestion avoidance with recovery mechanism, restricts the amount of burst flows entering the network according to the feedback information from core routers to edge routers to prevent network congestion. Also, a flow-policing scheme is proposed to intentionally drop the overloaded traffic with a certain probability at a core router to support fairness among flows. Moreover, the transmission rate of each flow is controlled to achieve optimized performance such as maximizing throughput or minimizing loss probability using two-step rate controller at the edge router. Simulation results show that ICCM effectively eliminates congestion within the network and that, when combined with a flow-policing mechanism, the fairness for competing flows can be supported while maintaining effective network performance.     

Analysis of an open non-Markovian GI — (GI | ∞) K queueing network with high-rate renewal arrival process

We analyze an open non-Markovian queueing network with high-rate renewal arrival process, Markovian routing, arbitrary service policy, and unlimited number of servers at nodes. We obtain mean values for the number of busy servers at nodes of the queueing network in question. We show that, under an infinitely increasing arrival rate, the multivariate distribution of the number of busy servers at network nodes can be approximated by a multivariate normal distribution; we find parameters of this distribution.     

非结构P2P网络受限搜索机制

降低搜索过程中产生的大量网络开销,是非结构P2P 网络重点研究内容之一.泛洪算法和随机查找算法简单且易于实现,但其在搜索过程中产生的大量冗余消息是造成大量网络开销的主要原因.针对这一问题,提出一种受限搜索机制(restricted forward search algorithm,简称RFSA),定义了搜索路径和冗余搜索路径,引入本地消息索引缓存机制,通过节点对消息的受限接收,消除节点对消息的重复接收与转发;利用搜索过程中携带的实时搜索路径信息,选择未出现在搜索路径中的邻居节点对消息进行转发,消除冗余搜索路径的产生.从理论上分析了RFSA 所产生的消息数目和网络开销.模拟实验分别从网络开销、查询点击率、搜索覆盖率和产生的冗余消息数目等方面对受限机制下和非受限机制下的泛洪算法和随机查找算法进行了对比分析,结果表明,在搜索覆盖率和查询点击率基本相同的情况下,受限机制下的泛洪算法和随机查找算法能够减少大量冗余消息的产生,降低了网络开销.     

一种面向分布式虚拟环境的分层迭代负载平衡算法

为了支持大规模用户共享虚拟环境,多服务器结构被应用到分布式虚拟环境系统中,每个服务器负责虚拟环境的一个区域划分.由于用户不可预知的移动和交互,可能会导致某些服务器负载过重.现有的负载平衡算法注重于将负载在服务器间重分配,但引入开销过大,影响系统交互性能.提出一种分层迭代的动态负载平衡算法,以过载区域为中心,分层地选择周围有限数量的区域作为调整目标,将过载部分由内向外迭代地扩散到各层,多次迭代达到负载平衡状态.针对倾斜和聚簇两种典型用户分布的虚拟环境,对算法进行验证并与现有的3种负载平衡算法进行比较.结果表明,该算法可以快速、有效地调整负载并引入较少的开销.