A processor-sharing model for input-buffered ATM-switches in a correlated traffic environment

We present a model to analyze the performance of a class of input-buffered ATM-switches when the offered traffic is correlated. The correlation not only pertains to the arrival instants of consecutive cells, but to their destinations too, and is modeled by a message train-arrival process. The switches under consideration use a pure random resolution scheme for the output-port contention. This contention is modeled through the well-known virtual-queue concept. For correlated traffic, the random scheme results in a discrete-time processor-sharing discipline inside these virtual queues. The analysis of this discipline presented here is based on generating functions and yields straightforward algorithms to calculate various measures of interest, as illustrated by numerical examples. The main conclusion drawn is that under realistic circumstances—no exact prior knowledge of the extent of the correlation—the random resolution scheme can provide a fair compromise between design complexity, robustness and performance.     

Insensitive Traffic Models for Communication Networks

We present a survey of traffic models for communication networks whose key performance indicators like blocking probability and mean delay are independent of all traffic characteristics beyond the traffic intensity. This insensitivity property, which follows from that of the underlying queuing networks, is key to the derivation of simple and robust engineering rules like the Erlang formula in telephone networks.

Feedback invariant discipline and insensitivity in closed queueing networks

Motivated by control theory concepts, we investigate a closed queueing network by adding a feedback path to each node. A feedback invariant service discipline is introduced. This approach differs from the conventional queueing theory approach and provides a new criteria and an intuitive explanation for the insensitivity property in a closed queueing network.     

Decomposing the queue length distribution of processor-sharing models into queue lengths of permanent customer queues

We obtain a decomposition result for the steady state queue length distribution in egalitarian processor-sharing (PS) models. In particular, for multi-class egalitarian PS queues, we show that the marginal queue length distribution for each class equals the queue length distribution of an equivalent single class PS model with a random number of permanent customers. Similarly, the mean sojourn time (conditioned on the initial service requirement) for each class can be obtained by conditioning on the number of permanent customers. The decomposition result implies linear relations between the marginal queue length probabilities, which also hold for other PS models such as the egalitarian PS models with state-dependent system capacity that only depends on the total number of customers in the system. Based on the exact decomposition result for egalitarian PS queues, we propose a similar decomposition for discriminatory processor-sharing (DPS) models, and numerically show that the approximation is accurate for moderate differences in service weights.     

Analysis of join-the-shortest-queue routing for web server farms

Join the Shortest Queue (JSQ) is a popular routing policy for server farms. However, until now all analysis of JSQ has been limited to First-Come-First-Serve (FCFS) server farms, whereas it is known that web server farms are better modeled as Processor Sharing (PS) server farms. We provide the first approximate analysis of JSQ in the PS server farm model for general job-size distributions, obtaining the distribution of queue length at each queue. To do this, we approximate the queue length of each queue in the server farm by a one-dimensional Markov chain, in a novel fashion. We also discover some interesting insensitivity properties of PS server farms with JSQ routing, and discuss the near-optimality of JSQ.     

Ad Hoc网络中基于延迟的多径路由协议的研究

Ad Hoc网络的频繁变化和节点的移动使得单路径协议的性能受到很大限制.由于多径路由具有稳定和网络资源利用率高的特性,它比原来的单径路由更适合于无线多跳网络.基于跨层设计的思想,提出一种按需多径路由算法QAOMDV.该算法通过节点最短队列长度,把网络层、MAC层和物理层协同起来.在与原有的路由协议的性能进行全面比较的基础上,用NS2仿真工具对改进的算法进行了性能分析和评价,结果表明该改进协议在性能上优于原有路由协议.     

基于链路稳定性加权的车载自组网按需路由协议

车载自组网由于网络拓扑变化快,带宽有限,易导致通信链路不稳定.传统基于跳数判据的按需路由协议主要考虑协议的时延性能,忽略了路由的稳定性.路由的不稳定会带来频繁的路由发现过程,增大网络开销,降低路由协议性能.针对车载自组织网,对经典按需路由协议AODV进行改进,兼顾考虑路由的稳定性和时延,提出了一种由链路有效时间、队列饱和度和跳数组成的综合判据,实现了一种基于链路稳定性加权的路由协议.在路由发现过程中,路由发现包携带途经每一跳的综合判据值或权重之和,以权重之和最小的路径作为路由.仿真结果表明,提出的路由协议在投递率、时延和网络开销方面均优于AODV.尤其是路由发现频率仅为AODV的70％左右,说明路由稳定性远优于AODV.     

A new computational algorithm for retrial queues to cellular mobile systems with guard channels

Retrial queueing models have been applied to evaluate the impact of new and handover calls on the call control mechanisms of cellular mobile networks. The fact that the retrial rate depends on the number of retried calls waiting in the system leads to an analytically intractable model. Therefore, approximation procedures should be used to compute the performability of the system. However, there exists a numerical problem concerning a recursive algorithm to compute the stationary probabilities for retrial queues modeling guard channels. Namely, the consideration of guard channels leads to calculations with negative terms in the recursive algorithm. Negative terms and extremely small values involved in the computation are the main causes for a numerical instability in the recursive algorithm.     

Self-stabilizing smoothing and balancing networks

A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced. Prior work on smoothing networks always assumed that such networks were properly initialized. In a real distributed system, however, network switches may be rebooted or replaced dynamically, and it may not be practical to determine the correct initial state for the new switch. Prior analyses do not work under these new assumptions. This paper makes the following contributions. First, we show that some well-known 1-smoothing networks, known as counting networks, when started in an arbitrary initial state (perhaps chosen by an adversary), remain remarkably smooth, degrading from 1-smooth to (log n)-smooth, where n is the number of input/output wires. For the networks that we consider, we show that the above (log n) bound for the smoothness is tight. Our second contribution is to show how any balancing network can be made self-stabilizing with the addition of local stabilization actions and state, which restore the network back to a “legal state” even if it starts out in an illegal state. A preliminary version of this work appeared in the Proceedings of The 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island, USA.     

Bandwidth-constrained queries in sensor networks

Sensor networks consist of battery-powered wireless devices that are required to operate unattended for long periods of time. Thus, reducing energy drain is of utmost importance when designing algorithms and applications for such networks. Aggregate queries are often used by monitoring applications to assess the status of the network and detect abnormal behavior. Since radio transmission often constitutes the biggest factor of energy drain in a node, in this paper we propose novel algorithms for the evaluation of bandwidth- constrained queries over sensor networks. The goal of our techniques is, given a target bandwidth utilization factor, to program the sensor nodes in a way that seeks to maximize the accuracy of the produced query results at the monitoring node, while always providing strong error guarantees to the monitoring application. This is a distinct difference of our framework from previous techniques that only provide probabilistic guarantees on the accuracy of the query result. Our algorithms are equally applicable when the nodes have ample power resources, but bandwidth consumption needs to be minimized, for instance in densely distributed networks, to ensure proper operation of the nodes. Our experiments with real sensor data show that bandwidth-constrained queries can substantially reduce the number of messages in the network while providing very tight error bounds on the query result.     

Distributed election in complete networks

An improved version of Afek and Gafni's synchronous algorithm for distributed election in complete networks is given and anO(n) expected message complexity is shown. M.Y. Chan received her Ph.D. in 1988 from the University of Hong Kong, and her M.S. and B.A. degrees in computer science from the University of California, San Diego in 1980 and 1981, respectively. She is currently an Assistant Professor at the University of Texas at Dallas. Francis Y.L. Chin (S71-M76-SM85) received the B.Sc. degree in engineering science from the University of Toronto, Toronto, Canada, in 1972, and the M.S., M.A., and Ph.D. degrees in electrical engineering and computer science from Princeton University, New Jersey, in 1974, 1975, and 1976, respectively. Since 1975, he has taught at the University of Maryland, Baltimore Country, University of California, San Diego, University of Alberta, and Chinese University of Hong Kong. He is currently Head of the Department of Computer Science, University of Hong Kong. He has served as a program co-chairman of the 1988 International Conference on Computer Processing of Chinese and Oriental Languages (Toronto) and the International Computer Science Conference '88 (Hong Kong). His current research interests include algorithm design and analysis, parallel and distributed computing.     

Distributed decision propagation in mobile-agent proximity networks

This paper develops a distributed algorithm for decision/awareness propagation in mobile-agent networks. A time-dependent proximity network topology is adopted to represent a mobile-agent scenario. The agent-interaction policy formulated here is inspired from the recently developed language-measure theory. Analytical results related to convergence of statistical moments of agent states are derived and then validated by numerical simulation. The results show that a single (user-defined) parameter in the agent interaction policy can be identified to control the trade-off between Propagation Radius (i.e. how far a decision spreads from its source) and Localisation Gradient (i.e. the extent to which the spatial variations may affect localisation of the source) as well as the temporal convergence properties.

     

Using zero configuration technology for IP addressing in optical networks

Host configuration in optical networks is usually done by hand. In this paper we propose to use zero configuration techniques, including self-assigned IP addresses and multicast DNS to do this automatically. The proposed technology is designed for small networks without central control, and can be applied to optical private networks as long as there is no router in between the end-hosts.     

Congestion control algorithm in large-delay uncertain networks

Based on Smith-fuzzy controller, a new active queue management （AQM） algorithm adaptable to the large-delay uncertain networks is presented. It can compensate the negative impact on the queue stability caused by the large delay, and it also maintains strong robustness under the condition of dynamic network fluid. Its stability is proven through Lyapunov method. Simulation results demonstrated that this method enables the queue length to converge at a preset value quickly and keeps the queue oscillation small, the simulation results also show that the scheme is very robust to disturbance under various network conditions and large delay and, in particular, the algorithm proposed outperforms the conventional PI control and fuzzy control when the network parameters and network delay change.     

Dynamic control of service rates in queuing networks

A method for dynamic control of service rates in closed exponential queuing networks is proposed. The performance of queuing networks with the service-rate control is analyzed, and the main steady-state network characteristics are computed using an analytic approximation. A simple example of a queuing network with controlled service rates is considered as an illustration. The efficiency of the service-rate control is confirmed by Monte Carlo simulations, which, as a by-product, also show acceptable accuracy of our analytical approximations.     

Queues in DOCSIS cable modem networks

In this paper we determine the optimal fraction c^*$c^{*}$ of the uplink channel capacity that should be dedicated to the contention channel in a DOCSIS cable network in order to minimize its mean response time. For this purpose, we have developed an open queueing network with a non-standard form of blocking consisting of tens to hundreds of nodes. The network contains several types of customers that enter the network at various points according to a Markovian arrival process with marked customers. One of the main building blocks of the model exists in capturing the behavior of the conflict resolution algorithm by means of a single processor sharing queue. To assess the performance characteristics of this open queueing network we rely on an advanced decomposition technique that is specifically designed to deal with the Markovian nature of the arrival pattern. Several simulations are run to confirm the accuracy of the decomposition technique. We also explore the impact of a variety of systems parameters, e.g., the number of cable modems, the initial backoff window size, the correlation structure of the arrival process, the mean packet sizes, etc., on the optimal fraction c^*$c^{*}$.     

Meta-searches in peer-to-peer networks

We propose a method for carrying out enhanced collaborative searches, called meta-searches, in peer-to-peer networks. In addition to performing regular searches, our method supports searches based on other network users’ previous searches on the same or similar topic. In essence, when a user performs a search, s/he will receive not only the usual result set, but also information on other users’ previous results, as well as relevancy information (such as how many times a resource that appeared in the result set was successfully downloaded). The core components of meta-search are query relevancy calculation, query matching algorithms, and relevancy file format. In this paper we discuss the underlying concepts and principles, and describe the component design in detail. Meta-search provides a way of benefiting from other users’ successful searches without any additional effort, thus potentially improving the efficiency and experience of a search.     

Online social networks in economics

This paper describes how economists study social networks. While economists borrow from other fields like sociology or computer science, their approach of modeling of social networks is distinguished by the emphasis on the role of choices under constraints. Economists investigate how socioeconomic background and economic incentives affect the structure and composition of social networks. The characteristics of social networks are important for economic outcomes like the matching of workers to jobs and educational attainment. I review the theoretical and empirical literature that investigates these relationships and discuss possible implications of new, Internet based, forms of social interactions.     

Resource placement in Cartesian product of networks

The utilization of the limited resources of a multiprocessor or multicomputer system is a primary performance issue which is crucial for the design of many scheduling algorithms. While many of the existing parallel machines benefit from a regular product network topology, almost none of the previous resource placement techniques have come to recognize and exploit this inherent regularity. This paper introduces several novel algorithms for deriving resource placement schemes in product networks based on the assumption of perfect resource placement in their underling basic graphs. Our techniques use known schemes for the basic networks as their building blocks for deploying the resource placement scheme in the product network. This seriously cuts down the expenses required for deploying and rescaling the network. In particular, we propose some efficient algorithms for adjacency placement in a product of k$k$ heterogeneous graphs. Furthermore, we extend our approach and present algorithms for distant resource placement in product networks.