Nomadic Service Assignment

We consider the problem of dynamically assigning application sessions of mobile users or user groups to service points. Such assignments must balance the trade-off between two conflicting goals. On the one hand, we would like to connect a user to the closest server in order to reduce network costs and service latencies. On the other hand, we would like to minimize the number of costly session migrations, or handoffs, between service points. We tackle this problem using two approaches. First, we employ algorithmic online optimization to obtain algorithms whose worst-case performance is within a factor of the optimal. Next, we extend them with opportunistic heuristics that achieve near-optimal practical average performance and scalability. We conduct case studies of two settings where such algorithms are required: wireless mesh networks with mobile users and wide-area groupware applications with or without mobility.     

Congestion control through input rate regulation

An approach to congestion control based on open-loop regulation of the input is investigated. The input rate regulation schemes are studied from the viewpoint of their smoothing and regulating effects on the incoming traffic. The smoothing effect is characterized by the variance of the interdeparture time of the packet departure process from the input rate regulation mechanism. Under the assumption of Poisson arrivals the characteristics of this departure process are explicitly derived in terms of the particular scheme's parameters, and the tradeoff between the smoothness of the departure process and packet waiting time is studied. Results for both finite- and infinite-buffer pool sizes are presented     

Improved fairness algorithms for rings with spatial reuse

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In this paper, we concentrate on a class of such policies that achieves fairness by allocating transmission quotas to nodes. For such policies, we provide mechanisms for improving delays and increasing overall throughput without compromising fairness     

An Anchor Chain Scheme for IP Mobility Management

This work presents a simple mobility scheme for IP-based networks, termed the anchor chain scheme. The scheme combines pointer forwarding and caching methods. Every mobile host (MH) is associated with a chain of anchors that connects it to its home agent. Each anchor defines the location of the MH at a certain degree of accuracy. The accuracy is increased along the chain until the attachment point of the MH is reached. We develop distributed procedures for updating the anchor chain (binding operation) with MH movements and for delivering messages to a MH (delivery operation). In terms of worst case performance, the total cost of the binding operations is O(Move logMove), where Move is the total geographic distance that the MH has traveled since its activation. The total length of the MH's pointer path is linear with the distance between the MH and its home network, and the delivery cost is near optimal. In addition, the anchor chain of a MH is determined dynamically with no need for preliminary definitions of static anchors or regions. Our simulation results show that the anchor chain scheme also yields lower average overheads for both the binding and the delivery operations than other methods that are described in the literature, including the current home approach. We believe that the proposed scheme is scalable, fairly easy to implement and there fore attractive for supporting MHs.     

Optimal buffer sharing

We address the problem of designing optimal buffer management policies in shared memory switches when packets already accepted in the switch can be dropped (pushed-out). Our goal is to maximize the overall throughput, or equivalently to minimize the overall loss probability in the system. For a system with two output ports, we prove that the optimal policy is of push-out with threshold type (POT). The same result holds if the optimality criterion is the weighted sum of the port loss probabilities. For this system, we also give an approximate method for the calculation of the optimal threshold, which we conjecture to be asymptotically correct. For the N-ported system, the optimal policy is not known in general, but we show that for a symmetric system (equal traffic on all ports) it consists of always accepting arrivals when the buffer is not full, and dropping one from the longest queue to accommodate the new arrival when the buffer is full. Numerical results are provided which reveal an interesting and somewhat unexpected phenomenon. While the overall improvement in loss probability of the optimal POT policy over the optimal coordinate-convex policy is not very significant, the loss probability of an individual output port remains approximately constant as the load on the other port varies and the optimal POT policy is applied, a property not shared by the optimal coordinate-convex policy     

Cell versus message level performances in ATM networks

The goal of this paper is to provide some insight into the relations that exist between cell level and message level performance guarantees in the context of ATM networks. Cell level guarantees are typically what the network is capable of providing, while message level guarantees are the ones of interest to users. It is, therefore, important to understand how the two are related, and which factors influence this relation. There are many different performance measures that are of importance, and in this paper we try to touch on the (three) most relevant ones. This includes comparing cell and message loss probabilities, average cell and message delays, and cell and message jitter. Specifically, we show that cell and message loss probabilities can exhibit significant differences, which strongly depend on traffic characteristics such as peak rate and burst size, i.e., for a fixed cell loss probability, the message loss probability can greatly vary when peak rate and burst size change. One reason for this sensitivity, is that message loss depends on what happen toall the cells in a message. For delay and jitter, we also find that peak rate and burst size play a role in determining the relation between cell and message performance. However, this sensitivity is not as acute as with losses since message delay and jitter are typically determined by the performance seen by onlyone cell, the last cell in a message. In the paper, we provide quantitative examples that illustrate the range of behaviors and identify the impact of different parameters.This work was done while at the IBM T.J. Watson Research Center.Part of the work was done while visiting the IBM T.J. Watson Research Center.     

Analysis of packet loss processes in high-speed networks

The packet loss process in a single-server queueing system with a finite buffer capacity is analyzed. The model used addresses the packet loss probabilities for packets within a block of a consecutive sequence of packets. An analytical approach is presented that yields efficient recursions for the computation of the distribution of the number of lost packets within a block of packets of fixed or variable size for several arrival models and several numbers of sessions. Numerical examples are provided to compare the distribution obtained with that obtained using the independence assumption to compute the loss probabilities of packets within a block. The results show that forward error correction schemes become less efficient due to the bursty nature of the packet loss processes; real-time traffic might be more sensitive to network congestion than was previously assumed; and the retransmission probability of ATM messages has been overestimated by the use of the independence assumption     

Synchronizing asynchronous bounded delay networks

An efficient way to synchronize an asynchronous network with a bounded delay message delivery is presented. Two types of synchronization algorithm are presented. Both types require an initializing phase that costs |E| messages (where |E| is the number of links). The first requires an additional bit in every message and increases the time complexity by a factor of 2. The second does not require any additional bits but increases the time complexity by a factor of 3. How to overcome differences in nodal timer rates is explained     

Distributed Store-and-Forward Deadlock Detection and Resolution Algorithms

Distributed algorithms for the detection and resolution of deadlocks in store-and-forward computer communication networks are presented and validated. The algorithms use a fixed amount of storage at each node (that is independent of the size of the network). The detection algorithm is simple but requires network-wide coordination. The resolution algorithm is based on earlier approaches, but uses the network-wide coordination to address certain synchronization problems. When the detection and resolution algorithms are merged, it is guaranteed that packets will arrive at their destinations in finite time.     

Conflict multiplicity estimation and batch resolution algorithms

The standard model of a multiple-access channel with ternary feedback is considered. When packets of a batch of k nodes initially collide, it is assumed that no a priori statistical information about k is available. An algorithm is presented and analyzed that enables the nodes to compute a statistical estimate of k. Combining the estimation procedure with tree algorithms leads to batch-resolution algorithms that resolve conflicts more efficiently than any other reported to date. Both complete-resolution and partial-resolution algorithms are presented