Hadoop is an open source software based on MapReduce framework. The Hadoop Distributed File System (HDFS) performs well while storing and managing data sets of very large size. However, the performance of HDFS suffers while handling a large number of small files since they put a lot of burden on the NameNode of HDFS both in terms of memory and access time. To overcome these defects, we merge small files into a large file and store the merged file on HDFS. Generally, when small files are merged, variation in the size distribution of files is not taken into consideration. We propose a new algorithm OMSS (Optimized MapFile based Storage of Small files) which merges the small files into a large file based on the Worst fit strategy. The strategy helps in reducing internal fragmentation in data blocks, which in turn leads to fewer data blocks consumed for the same number of small files. Less number of data blocks mean fewer memory overheads at major nodes of Hadoop cluster and hence increased efficiency of data processing. Our experimental results indicate that the time to process data on HDFS containing unprocessed small files reduces significantly to 590s when MapFile is used and it reduces further to 440s when OMSS is used. OMSS as compared to MapFile merging algorithm has a reduction of 34.7% in memory requirements.

A portable healthcard on the patient mobile device can integrate Patient Health Records (PHRs) dispersed on various Hospital Information Systems (HIS) to provide a highly available medical history for correct diagnosis and treatment. In this paper, we present a broad overview of the design issues for the security framework of a novel NFC and Secure Element-based healthcard on a mobile device known as S-MAPLE (Secure Mobility-Assisted PortabLE) healthcard. We provide detailed design for Role-Based Access Control (RBAC) with selective read and write access. Evaluation results on Android-based devices indicate satisfactory performance results for delays due to security overheads.

This paper presents a waist-worn Pedestrian Dead Reckoning (PDR) System that requires minimal end-user calibration. The PDR system is based on an Inertial Measurement Unit (IMU) comprising of a tri-axial accelerometer, a tri-axial magnetometer and a tri-axial gyroscope. We propose a novel heading estimation scheme using a quaternion-based extended Kalman filter (EKF) that estimates magnetic disturbances and corrects for them. Accelerometer measurements are used to detect step events and to estimate step lengths. Experimental results show that a relative distance error of about 3% to 8% can be obtained using our methods.

It is easier to detect a DDoS attack near the victim but it is of little use to do so. Many researchers believe that it would be best to handle DDoS attacks closer to the computers which host these attacks and have propounded various strategies for packet filtering at edge-routers. This paper makes three contributions over earlier work. First, we propose that it is best to track illegitimate packets suspected to cause a DDoS at the source computer itself. Secondly, we come up with a secure and efficient implementation (ADVOS: Anti-DDoS Virtualized Operating System) for packet filtering at the source computer itself. Security dependency on the integrity of the source operating system is removed by using virtualization to isolate the modules providing the protection capabilities. Different models of traffic characterization could possibly be used in curtailing malicious traffic, we justify the effectiveness of symmetry based model at source computers. Thirdly, we demonstrate that such an anti-DDoS operating system using virtualization can be implemented practically and efficiently. In our prototype over native Linux system 2.4% overhead was observed in the attained network throughput. Less than 1% of the total attack traffic generated was allowed to pass through on attack. Finally, we discuss the scalability and deployment issues for ADVOS.

This paper describes an algorithm to control non-adaptive sources in a simple and lightweight fashion that does not maintain per-flow state information. Using experimental results from simulations, we demonstrate that the algorithm outperforms current well-known algorithms for buffer management in providing better protection for TCP flows under varying degrees of attack from non-adaptive flows.

The paper describes an algorithm to control flows from nonadaptive sources in the Internet in a simple and lightweight fashion. The algorithm, called XCHOKe, is an extension to CHOKe and RED. The paper presents experimental results from simulations that demonstrate that the algorithm outperforms current well-known algorithms for buffer management in providing better protection for TCP flows under varying degrees of attack from non-adaptive flows.

We propose k-SACK, a TCP variant that has considerably improved throughput characteristics over lossy links. A k-SACK source does not consider every packet loss as an indication of congestion. It uses the selective acknowledgement option to estimate a parameter lookahead-loss, which is used in congestion detection. Our results demonstrate that k-SACK maintains a steady performance in a non-lossy environment while showing considerable performance improvement over paths spanning lossy links. Throughput gains of more than 90% are observed over links with packet loss rates of the order of 5%. We show that when k-SACK is used over wireline Internet links, it does not harm the existing TCP variants significantly. k-SACK is simple to implement and does not involve any additional overheads.

In networks with mobile nodes, power consumption is an important constraint due to the limited battery power available at the mobile nodes. Reduction of power consumption in mobile devices can be achieved by keeping these devices in a low power (standby) mode during periods of inactivity. This may, however, result in increased end-to-end delays leading to violation of the quality of service (QoS) parameters. We propose medium access control (MAC) scheduling policies for centrally controlled TDD wireless systems. The proposed policies reduce the power consumption of mobile devices by putting them into low power mode intelligently, using probabilistic estimates of inactivity based on the previous traffic arrival pattern. The policies ensure that the QoS parameters such as end-to-end packet delays are not violated.

Bluetooth is an emerging standard low-cost indoor pico-cellular wireless systems. It is a master driven time division duplex (TDD) system. Real time services such as voice are given 64 kbps bandwidth in Bluetooth. However most other wireless networks use compressed voice, which requires much lesser bandwidth, leading to a substantial increase in system capacity. Bandwidth can be further conserved by using voice activity detection (VAD) techniques and variable rate voice codecs. We propose and analyse modifications to be made to Bluetooth for incorporating variable rate coded voice. Current mechanisms in Bluetooth use synchronous channels with fixed slot allocation for voice and a best effort service for data. We propose and study two scheduling strategies which optimise bandwidth consumption by using variable rate coded voice. In the first scheme, adaptive T/sub SCO/ scheduling, we modify the conventional scheduling policy to change the time period of scheduling a voice channel depending upon its activity. In the voice over ACL scheduling, we schedule voice asynchronously like data using a QoS based scheduling scheme with maximum scheduling delay tolerable by packets as the QoS parameter. This scheme can also be used to schedule other multimedia applications with varying QoS requirements. We observe from simulations that the voice over ACL scheme gives more than 115% increase in bandwidth over the currently used scheduling in the presence of two voice connections.

Emerging technologies such as Bluetooth are expected to become a ubiquitous solution for providing short range, low power, low cost, pico-cellular wireless connectivity. Bluetooth is a master driven time division duplex (TDD) system that supports an asynchronous channel for data traffic as well as synchronous channels for voice traffic. Data applications running over Bluetooth such as http, ftp and real audio will need transport layer protocols such as TCP and UDP to send packets over the wireless links. In this paper we study several schemes designed to improve the performance of asynchronous data traffic over a Bluetooth piconet that supports multiple active slaves. We propose and compare a number of segmentation and reassembly policies and MAC scheduling algorithms with a view towards enhancing the performance of transport layer sessions. We investigate the effect of different FEC and ARQ schemes at the baseband level, using a two-state Markov channel model for the Bluetooth RF link. We also study how the presence of circuit-switched voice impacts the performance of data traffic.

Virtual private networks (VPN) and link sharing are cost-effective ways of realizing corporate intranets. Corporate intranets will increasingly have to provide integrated services for voice and multimedia traffic. Although packet scheduling algorithms can be used to implement integrated services in link sharing and virtual private networks, their statistical multiplexing gains are limited. We propose a new scheme called stochastic fair sharing (SFS) to carry out fair link sharing and fair sharing among virtual leased links (VLL). In the link sharing environment, capacities allocated to different classes are adjusted dynamically as sessions arrive (or depart). The SFS admission control algorithm decides which sessions to accept and which to reject depending upon the current utilizations and provisioned capacities of the classes. SFS gives protection to classes with low session arrival rate against classes with high session arrival rates by ensuring them a low blocking probability. In the case of multi-hop VLL, capacity resizing requests are sent in the service providers's network which are admission-controlled using SFS. Our simulations indicate that using SFS, the equivalent capacity of virtual links converge to their max-min fair capacity, with a fairness index of 0.97 in extreme situations. The average signaling load of the protocol was found to be reasonable. The scheme is simple to implement, efficient, and robust. The potential applications of SFS are fair and efficient resource sharing in telecommunication networks, ATM networks, virtual private networks (VPN) and integrated services or differentiated services-based IP networks.

A factor 2 approximation algorithm for the problem of finding a minimum-cost b-balanced cut in planar graphs is presented, for $b \leq {1 \over 3}$. We assume that the vertex weights are given in unary; for the case of binary vertex weights, a pseudoapproximation algorithm is presented. This problem is of considerable practical significance, especially in VLSI design. The natural algorithm for this problem accumulates sparsest cuts iteratively. One of our main ideas is to give a definition of sparsity, called net-sparsity, that reflects precisely the cost of the cuts accumulated by this algorithm. However, this definition is too precise: we believe it is NP-hard to compute a minimum--net-sparsity cut, even in planar graphs. The rest of our machinery is built to work with this definition and still make it computationally feasible. Toward this end, we use several ideas from the works of Rao [ Proceedings, 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 225--237; Proceedings, 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 229--240] and Park and Phillips [ Proceedings, 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 766--775].

We present an efficient algorithm for computing the minimal trellis for a group code over a finite Abelian group, given a generator matrix for the code. We also show how to compute a succinct representation of the minimal trellis for such a code, and present algorithms that use this information to efficiently compute local descriptions of the minimal trellis. This extends the work of Kschischang and Sorokine (1995), who handled the case of linear codes over fields. An important application of our algorithms is to the construction of minimal trellises for lattices. A key step in our work is handling codes over cyclic groups C/sub p//spl alpha/, where p is a prime. Such a code can be viewed as a submodule over the ring Z/sub p//spl alpha/. Because of the presence of zero-divisors in the ring, submodules do not share the useful properties of vector spaces. We get around this difficulty by restricting the notion of linear combination to p-linear combination, and introducing the notion of a p-generator sequence, which enjoys properties similar to that of a generator matrix for a vector space.

We describe the design, implementation, and performance tuning of a transport layer targeted specifically for ATM networks. The layer has been built from scratch to minimize overhead in the critical path and take advantage of ATM adaptation layer 5 functionality. It provides reliable or unreliable data delivery with feedback or leaky-bucket flow control. These services can be combined to create a customized transport service. Our work is novel in that it is the first end-to-end ATM transport service to provide reliable, flow controlled data transfer. We describe the mechanisms and the operating system support needed to provide these services. A detailed performance measurement allows us to determine the bottlenecks in our system and do tune our implementation. With this tuning, we are able to achieve a user-to-user throughput of 55 Mbps between two 66 MHz Intel 80486 personal computers with Fore Systems' HPA-200 EISA-bus host adaptors. The user-to-user latency for small messages is around 720 /spl mu/s. These figures compare favorably with the performance from far more expensive workstations and validate the correctness of our design choices.

We present an efficient algorithm for computing the minimal trellis for a group code over a finite abelian group, given a generator matrix for the code. We also show how to compute a succinct representation of the minimal trellis for such a code, and present algorithms that use this information to compute efficiently local descriptions of the minimal trellis. This extends the work of Kschischang and Sorokine (see ibid., vol.41, no.6, p.1926-37, 1995), who treated the case of linear codes over fields. An important application of our algorithms is to the construction of minimal trellises for lattices. A key step in our work is handling codes over cyclic groups C/sub p//spl alpha/, where p is a prime. Such a code can be viewed as a module over the ring Z/sub p//spl alpha/. Because of the presence of zero divisors in the ring, modules do not share the useful properties of vector spaces. We get around this difficulty by restricting the notion of linear combination to a p-linear combination, and by introducing the notion of a p-generator sequence, which enjoys properties similar to those of a generator matrix for a vector space.

We describe the design, implementation, and performance measurement of a transport layer targeted specifically for asynchronous transfer mode (ATM) networks. The layer has been built from scratch to minimize overhead in the critical path, provide per-virtual circuit quality of service (QoS) guarantees, and take advantage of ATM adaptation layer 5 functionality. It provides reliable and unreliable data delivery with a choice of feedback and leaky-bucket flow control. These services can be combined to create per-virtual-circuit customized transport services. Our work is novel in that it provides high-performance, reliable, flow-controlled transport service using cheap personal computers (PCs). We describe the mechanisms and the operating system support needed to provide these services in detail. An extensive performance measurement allows us to pinpoint and eliminate inefficiencies in our implementation. With this tuning, we are able to achieve a user-to-user throughput of 55 Mb/s between two 66 MHz Intel 80486 personal computers with FORE Systems' HPA-200 EISA-bus host adaptors. The user-to-user latency for small messages is around 720 /spl mu/s. These figures compare favorably with the performance of far more expensive workstations and validate the correctness of our design choices.

When carrying Internet protocol (IP) traffic over an asynchronous transfer mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP datagram. We present a formal statement of the problem and carry out a detailed empirical examination of various holding time policies taking into account the issue of network pricing. We offer solutions for two natural pricing models, the first being a likely pricing model of future ATM networks, while the second is based on characteristics of current networks. For each pricing model, we study a variety of simple nonadaptive policies as well as easy to implement policies that adapt to the characteristics of the IP traffic. We simulate our policies on actual network traffic, and find that policies based on least recently used (LRU) perform well, although the best adaptive policies provide a significant improvement over LRU.>

Two simple approximation algorithms for the minimum k-cut problem are presented. Each algorithm finds a k cut having weight within a factor of $(2 - 2/k)$ of the optimal. One algorithm is particularly efficient—it requires a total of only $n - 1$ maximum flow computations for finding a set of near-optimal k cuts, one for each value of k between 2 and n.

Building on the works of S.B. Rao (1987, 1992) and J.K. Park and C.A. Phillips (1993), we present a factor 2 approximation algorithm for the problem of finding a minimum cost b-balanced cut in planar graphs, for b/spl les/1/3, if the vertex weights are given in unary (using scaling, a psuedo-approximation algorithm is also presented for the case of binary vertex weights). This problem is of considerable practical significance, especially in VLSI design.>

When carrying Internet Protocol (IP) traffic over an asynchronous transfer mode (ATM) network, the ATM adaptation layer must determine how long to hold a virtual circuit opened to carry an IP datagram. The authors present a formal statement of the problem and an empirical study of holding time policies taking network pricing into account. They find that IP traffic shows temporal locality of reference and so least recently used (LRU)-based policies perform well. A system-wide timeout, which is a special case of an LRU policy, is quite effective when the timeout value is chosen correctly. The policies proposed are easy to implement and solve the problem satisfactorily.>

The strong link between matroids and matching is used to extend the ideas that resulted in the design of random NC (RNC) algorithms for matching to obtain RNC algorithms for the matroid union, intersection, and matching problems, and for linearly representable matroids. As a consequence, RNC algorithms for the well-known problems of finding an arborescence and a maximum cardinality set of edge-disjoint spanning trees in a graph are obtained. The key tools used are linear algebra and randomization.

Two simple approximation algorithms are presented for the minimum k-cut problem. Each algorithm finds a k-cut having weight within a factor of (2-2/k) of the optimal. One of the algorithms is particularly efficient, requiring a total of only n-1 maximum flow computations for finding a set of near-optimal k-cuts, one for each value of k between 2 and n.>

The combinatorial structure of visibility in simple orthogonal polygons is studied. It is shown that the visibility graph of a horizontally or vertically convex polygon is a permutation graph. In general, orthogonal polygons can have concavities (dents) with four possible orientations. In the case where the polygon has three dent orientations, it is shown that the visibility graph is weakly triangulated. Since weakly triangulated graphs are perfect, a polynomial algorithm for this polygon covering problem is obtained. Furthermore, the following duality relationship is obtained. The minimum number of orthogonally convex polygons needed to cover an orthogonal polygon P with at most three dent orientations is equal to the maximum number of points of P, no two of which can be contained together in an orthogonally convex covering polygon. Finally, it shown that in the case of orthogonal polygons with all four dent orientations, the above duality relationship fails to hold.

We consider the problem of covering simple orthogonal polygons with star polygons. A star polygon contains a point p, such that for every point q in the star polygon, there is an orthogonally convex polygon containing p and q.

A formal study of three-dimensional topological graph theory is initiated. The problem of deciding whether a graph can be embedded in 3-space so that no collection of vertex-disjoint cycles is topologically linked is considered first. The Robertson-Seymour Theory of Graph Minors is applicable to this problem and guarantees the existence of an O(n/sup 3/) algorithm for the decision problem. However, not even a finite-time decision procedure was known for this problem. A small set of forbidden minors for linkless embeddable graphs is exhibited, and it is shown that any graph with these minors cannot be embedded without linked cycles. It is further established that any graph that does not contain these minors is embeddable without linked cycles. Thus, an O(n/sup 3/) algorithm for the decision problem is demonstrated. It is believed that the proof technique will lead to an algorithm for actually embedding a graph, provided it does not contain the forbidden minors.>