Resource management in LEO satellite networks

To provide truly global coverage needed by increased Personal Communication Services (PCS), a new generation of mobile satellite networks has been proposed. These low Earth orbit (LEO) mobile satellite networks handle multimedia traffic and can be used for non-real-time as well as real-time service to remote areas. Due to the many handoffs, resource management and connection admission control are important tasks for fair bandwidth sharing and QoS guarantees. Because the total link capacity has to be divided among several carriers and given the limited buffer capacity of the ATM switch, resource management is vital. It ensures the ability of the network to provide users with their negotiated QoS while protecting the network and the end-systems from congestion. We introduced a simple connection admission control (CAC) priority policy based on the delay and cell loss requirements for the investigated types of traffic. We took into account the handoff status of the satellite beams involved. Thus, we propose an onboard buffer architecture with separated buffers for new calls and intra-satellite handoff calls. The priority scheme applied is as follows: highest priority is given to CBR, followed by rt-VBR, nrtVBR and ABR.     

An O((log log n)2) time algorithm to compute the convexhull of sorted points on reconfigurable meshes

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size √n×√n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)²) time on a reconfigurable mesh of size √n×√n. With slight modifications, this algorithm can be implemented to run in O((log log n)²) time on a reconfigurable mesh of size √n/loglogn×√n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take Ω(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes