<Emphasis Type="BoldItalic">LAMA/CA</Emphasis>: A Load-Adaptive MAC Protocol for Short Packets

An efficient Media Access Control (MAC) protocol for wireless Internet access is developed in this study. The proposed access protocol exploits the fact that very often the Internet access messages, such as HTTP download requests, are based on short packets. In addition, whenever the user is able to access to multiple overlapping base stations (e.g., in WiMAX access networks, or in 3GPP cellular networks), the proposed protocol enables the user to select the least loaded base station. Consequently, the user gets a better quality of service, while load balancing is achieved by preferring links that are less loaded over congested links. The key idea is to adjust the access probability to the load on the local link, and to use a different access protocol for short messages. Delay insensitive and long messages are transmitted using a Request To Send (RTS) and Clear To Send (CTS) mechanism, in a similar way to IEEE 802.11, over hops that are able to support this protocol type, while short and delay-sensitive messages are transmitted using another method, that offers a reduced call delivery delay, as well as better channel utilization. Whenever the message length drops below a certain threshold (evaluated in this study), the overhead of transmitting an RTS and CTS messages becomes too large. The analysis in this study shows that this threshold is load-dependent. Whenever the message length drops below this load-dependent threshold, this study proposes to use a protocol which is more efficient for short messages transmissions, such as HTTP download requests, Short Message Service (SMS) messages, and signaling messages. The proposed MAC protocol is especially suitable for 3G and beyond cellular networks. Whenever there are number of channels that can be possibly used to deliver a message, it enables to select the least loaded channel among several channels.     

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs

This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set (FES) problem. In the {FVS} (resp. FES) problem, one is given a directed graph with weights (each of which is at least one) on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-hard problems and have many applications. We also consider a generalization of these problems: subset-fvs and subset-fes, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset consists of all the cycles that go through a distinguished input subset of vertices and edges, denoted by X . This generalization is also NP-hard even when |X|=2 . We present approximation algorithms for the subset-fvs and subset-fes problems. The first algorithm we present achieves an approximation factor of O(log ² |X|) . The second algorithm achieves an approximation factor of O(min{log τ ^* log log τ ^* , log n log log n)} , where τ ^* is the value of the optimum fractional solution of the problem at hand, and n is the number of vertices in the graph. We also define a multicut problem in a special type of directed networks which we call circular networks, and show that the subset-fes and subset-fvs problems are equivalent to this multicut problem. Another contribution of our paper is a combinatorial algorithm that computes a (1+ɛ) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution. Received May 31, 1995; revised June 11, 1996, and October 9, 1996.     

Flow in planar graphs with vertex capacities

Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintainplanarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).A preliminary version of this paper appeared in theProceedings of the First Integer Programming and Combinatorial Optimization Conference, Waterloo, Canada, May 1990, pp. 367–383. Samir Khuller is currently supported by NSF Grant CCR-8906949. Part of this research was done while he was visiting the IBM Thomas J. Watson Research Center and was supported by an IBM Graduate Fellowship at Cornell University. Joseph Naor's work was supported by Contract ONR N00014-88-K-0166 while he was a post-doctoral fellow in the Department of Computer Science at Stanford University.     

Hierarchical image representation for compression,filtering and normalization

Applications of pyramid data structure to image compression and image filtering are described. The compression scheme fits visual perception models, and filtering is computationally faster than filtering in the frequency domain. Image normalization is also possible.     

Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees

Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider’s POPs (points of presence). This collection of paths thus forms a “confluent” tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion. In this paper we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. In particular, we design fully polynomial-time approximate schemes (FPTAS) for different variants of this problem on trees. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.