In this paper, we describe our experiences and lessons learned from building a general-purpose in-memory key-value middleware, called HydraDB. HydraDB synthesizes a collection of state-of-the-art techniques, including continuous fault-tolerance, Remote Direct Memory Access (RDMA), as well as awareness for multicore systems, etc, to deliver a high-throughput, low-latency access service in a reliable manner for cluster computing applications.

This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our solution achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide explicit necessary and sufficient conditions on the parameters to guarantee synchronization. We then study the effect of noisy measurements (jitter) and frequency drift (wander) on the offsets and synchronization frequency, and further optimize the parameter values to minimize their variance. Our study reveals a few insights, for example, we show that our algorithm can converge even in the presence of timing loops and noise, provided that there is a well-defined leader. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme as it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. The results are supported by experiments running on a cluster of IBM BladeCenter servers with Linux.

Recently, many in-memory key-value stores have started using a High-Performance network protocol, Remote Direct Memory Access (RDMA), to provision ultra-low latency access services. Among various solutions, previous studies have recognized that leveraging RDMA Read to optimize GET operations and continuing using message passing for other requests can offer tremendous performance improvement while avoiding read-write races. However, although such a design can utilize the power of RDMA when there is sufficient memory space, it has also raised new challenges on the cache management that do not exist in traditional key-value stores. First, RDMA Read deprives servers of the awareness of the read operations. Therefore, how to track popular items and make replacement decisions at the server side becomes a critical issue. Second, without the access knowledge from the clients, new approaches are needed for servers to efficiently and reliably reclaim the resources. Lastly, the remote pointers hold by clients to conduct RDMA are highly susceptible to the evictions made by remote servers. Thus, any replacement algorithm that solely considers the server-side hit ratio is insufficient and can cause severe underutilization of RDMA.

In order to improve the performance of MapReduce, we design DynMR. It addresses the following problems that persist in the existing implementations: 1) difficulty in selecting optimal performance parameters for a single job in a fixed, dedicated environment, and lack of capability to configure parameters that can perform optimally in a dynamic, multi-job cluster; 2) long job execution resulting from a task long-tail effect, often caused by ReduceTask data skew or heterogeneous computing nodes; 3) inefficient use of hardware resources, since ReduceTasks bundle several functional phases together and may idle during certain phases.

This paper examines synchronization of computer clocks connected via a data network and proposes a skewless algorithm to synchronize them. Unlike existing solutions, which either estimate and compensate the frequency difference (skew) among clocks or introduce offset corrections that can generate jitter and possibly even backward jumps, our algorithm achieves synchronization without these problems. We first analyze the convergence property of the algorithm and provide necessary and sufficient conditions on the parameters to guarantee synchronization. We then implement our solution on a cluster of IBM BladeCenter servers running Linux and study its performance. In particular, both analytically and experimentally, we show that our algorithm can converge in the presence of timing loops. This marks a clear contrast with current standards such as NTP and PTP, where timing loops are specifically avoided. Furthermore, timing loops can even be beneficial in our scheme. For example, it is demonstrated that highly connected subnetworks can collectively outperform individual clients when the time source has large jitter. It is also experimentally demonstrated that our algorithm outperforms other well-established software-based solutions such as the NTPv4 and IBM Coordinated Cluster Time (IBM CCT).

Improving data locality for MapReduce jobs is critical for the performance of large-scale Hadoop clusters, embodying the principle of moving computation close to data for big data platforms. Scheduling tasks in the vicinity of stored data can significantly diminish network traffic, which is crucial for system stability and efficiency. Though the issue on data locality has been investigated extensively for MapTasks, most of the existing schedulers ignore data locality for ReduceTasks when fetching the intermediate data, causing performance degradation. This problem of reducing the fetching cost for ReduceTasks has been identified recently. However, the proposed solutions are exclusively based on a greedy approach, relying on the intuition to place ReduceTasks to the slots that are closest to the majority of the already generated intermediate data. The consequence is that, in presence of job arrivals and departures, assigning the ReduceTasks of the current job to the nodes with the lowest fetching cost can prevent a subsequent job with even better match of data locality from being launched on the already taken slots. To this end, we formulate a stochastic optimization framework to improve the data locality for ReduceTasks, with the optimal placement policy exhibiting a threshold-based structure. In order to ease the implementation, we further propose a receding horizon control policy based on the optimal solution under restricted conditions. The improved performance is further validated through simulation experiments and real performance tests on our testbed.

Schedulers are critical in enhancing the performance of MapReduce/Hadoop in presence of multiple jobs with different characteristics and performance goals. Though current schedulers for Hadoop are quite successful, they still have room for improvement: map tasks (MapTasks) and reduce tasks (ReduceTasks) are not jointly optimized, albeit there is a strong dependence between them. This can cause job starvation and unfavorable data locality. In this paper, we design and implement a resource-aware scheduler for Hadoop. It couples the progresses of MapTasks and ReduceTasks, utilizing Wait Scheduling for ReduceTasks and Random Peeking Scheduling for MapTasks to jointly optimize the task placement. This mitigates the starvation problem and improves the overall data locality. Our extensive experiments demonstrate significant improvements in job response times.

False sharing is a major class of performance bugs in parallel applications. Detecting false sharing is difficult as it does not change the program semantics. We introduce an efficient and effective approach for detecting false sharing based on machine learning.

Current schedulers of MapReduce/Hadoop are quite successful in providing good performance. However improving spaces still exist: map and reduce tasks are not jointly optimized for scheduling, albeit there is a strong dependence between them. This can cause job starvation and bad data locality. We design a resource-aware scheduler for Hadoop, which couples the progresses of mappers and reducers, and jointly optimize the placements for both of them. This mitigates the starvation problem and improves the overall data locality. Our experiments demonstrate improvements to job response times by up to an order of magnitude.

For MapReduce/Hadoop, map and reduce phases exhibit fundamentally distinguishing characteristics. Additionally, these two phases admit complicated and tight dependency on each other, causing the repeatedly observed starvation problem with the widely used Fair Scheduler. To mitigate this problem, we design Coupling Scheduler, which, among other new features, jointly schedules map and reduce tasks by coupling their progresses, different from existing ones that treat them separately. This design is based on the intuition that allocating excess resources to reduce tasks without balancing with the map task progress of the same job is likely to result in resource underutilization since a job is deemed done only when both phases complete. In order to analytically understand the performance of this design, we propose a model that captures the fundamental scheduling characteristics for MapReduce. Specifically, the map phase is modeled by a processor sharing queue, and the reduce phase by a “sticky processor sharing” queue. Along with the important dependence between these two types of tasks, we show that, for a class of jobs with regularly varying map service times, the job processing time distribution under Coupling Scheduler can be one order better than Fair Scheduler. These theoretical results are validated through simulations and the improved performance is further illustrated through real experiments on our testbed.

The rapid deployment of cloud computing promises network users with elastic, abundant, and on-demand cloud services. The pay-as-you-go model allows users to be charged only for services they use. Current purchasing designs, however, are still primitive with significant constraints. Spot Instance, the first deployed auction-style pricing model of Amazon EC2, fails to enforce fair competition among users in facing of resource scarcity and may thus lead to untruthful bidding and unfair resource allocation. Dishonest users are able to abuse the system and obtain (at least) short-term advantages by deliberately setting large maximum price bids while being charged only at lower Spot Prices. Meanwhile, this may also prevent the demands of honest users from being satisfied due to resource scarcity. Furthermore, Spot Instance is inefficient and may not adequately meet users' overall demands because it limits users to bid for each computing instance individually instead of multiple different instances at a time. In this paper, we formulate and investigate the problem of cloud resource pricing. We propose a suite of computationally efficient and truthful auction-style pricing mechanisms, which enable users to fairly compete for resources and cloud providers to increase their overall revenue. We analytically show that the proposed algorithms can achieve truthfulness without collusion or (t, p)-truthfulness tolerating a collusion group of size t with probability at least p. We also show that the two proposed algorithms have polynomial complexities O(nm + n2) and O(nm), respectively, when n users compete for m different computing instances with multiple units. Extensive simulations show that, in a competitive cloud resource market, the proposed mechanisms can increase the revenue of cloud providers, especially when allocating relatively limited computing resources to a potentially large number of cloud users.

MapReduce/Hadoop production clusters exhibit heavy-tailed characteristics for job processing times. These phenomena are resultant of the workload features and the adopted scheduling algorithms. Analytically understanding the delays under different schedulers for MapReduce can facilitate the design and deployment of large Hadoop clusters. The map and reduce tasks of a MapReduce job have fundamental difference and tight dependence between them, complicating the analysis. This also leads to an interesting starvation problem with the widely used Fair Scheduler due to its greedy approach to launching reduce tasks. To address this issue, we design and implement Coupling Scheduler, which gradually launches reduce tasks depending on map task progresses. Real experiments demonstrate improvements to job response times by up to an order of magnitude.

SUMMARY Even though Java is the de facto programming language for enterprise applications, there exist only a limited number of Java‐based benchmarks to understand the performance on emerging multicore systems. To bridge this gap, this paper presents a report generation benchmark that is developed on top of Open Source Apache Geronimo's DayTrader benchmark. Report generation and rendering is at the heart of many enterprise business analytics and business intelligence software products, and it is used by many enterprise applications. We evaluate the performance scalability of this benchmark on a state‐of‐the‐art Power7 multicore system with 8 Power7 cores and 32 hardware threads. The benchmark throughput scales linearly up to eight hardware threads, but beyond that point, the throughput falls sharply. Significant locking in the Java class libraries for non‐shared objects results in this performance drop. Splitting the locks on these shared classes results in near linear scaling from eight to 32 threads and improved the throughput by 80%. We also show that the Linux operating system load balancing could result in a degraded application performance in hardware multithreaded systems and simultaneous‐multithreads‐aware task scheduling results in uniform core‐resource utilization as well as improved application performance. Copyright © 2011 John Wiley & Sons, Ltd.

Network operators are continuously confronted with malicious events, such as port scans, denial-of-service attacks, and spreading of worms. Due to the detrimental effects caused by these anomalies, it is critical to detect them promptly and effectively. There have been numerous softwares, algorithms, or rules developed to conduct anomaly detection over traffic data. However, each of them only has limited descriptions of the anomalies, and thus suffers from high false positive/false negative rates. In contrast, the combination of multiple atomic detectors can provide a more powerful anomaly capturing capability when the base detectors complement each other. In this paper, we propose to infer a discriminative model by reaching consensus among multiple atomic anomaly detectors in an unsupervised manner when there are very few or even no known anomalous events for training. The proposed algorithm produces a perevent based non-trivial weighted combination of the atomic detectors by iteratively maximizing the probabilistic consensus among the output of the base detectors applied to different traffic records. The resulting model is different and not obtainable using Bayesian model averaging or weighted voting. Through experimental results on three network anomaly detection datasets, we show that the combined detector improves over the base detectors by 10% to 20% in accuracy.

Recent advances in virtualization technology have made it a common practice to consolidate virtual machines(VMs) into a fewer number of servers. An efficient consolidation scheme requires that VMs are packed tightly, yet receive resources commensurate with their demands. However, measurements from production data centers show that the network bandwidth demands of VMs are dynamic, making it difficult to characterize the demands by a fixed value and to apply traditional consolidation schemes. In this work, we formulate the VM consolidation into a Stochastic Bin Packing problem and propose an online packing algorithm by which the number of servers required is within (1+∈)(√2+1) of the optimum for any ∈ >; 0. The result can be improved to within (√2+1) of the optimum in a special case. In addition, we use numerical experiments to evaluate the proposed consolidation algorithm and observe 30% server reduction compared to several benchmark algorithms.

The scalability of modern data centers has become a practical concern and has attracted significant attention in recent years. In contrast to existing solutions that require changes in the network architecture and the routing protocols, this paper proposes using traffic-aware virtual machine (VM) placement to improve the network scalability. By optimizing the placement of VMs on host machines, traffic patterns among VMs can be better aligned with the communication distance between them, e.g. VMs with large mutual bandwidth usage are assigned to host machines in close proximity. We formulate the VM placement as an optimization problem and prove its hardness. We design a two-tier approximate algorithm that efficiently solves the VM placement problem for very large problem sizes. Given the significant difference in the traffic patterns seen in current data centers and the structural differences of the recently proposed data center architectures, we further conduct a comparative analysis on the impact of the traffic patterns and the network architectures on the potential performance gain of traffic-aware VM placement. We use traffic traces collected from production data centers to evaluate our proposed VM placement algorithm, and we show a significant performance improvement compared to existing general methods that do not take advantage of traffic patterns and data center network characteristics.

Today's networked systems are extensively instrumented for collecting a wealth of monitoring data. In this paper, we propose a framework called System-wide Similarity Query (S2Q) to support a new type of similarity queries on monitoring data for managing complex networked systems. The similarity queries are defined on a novel data model that captures system states, and the implementation includes a streaming algorithm for online state-modeling computation and a companion graph-based indexing technique for fast retrieval of historical system states. S2Q simplifies many systems management tasks through a simple and intuitive query interface available to operators, and two applications are evaluated in the paper: (i) fast diagnosis of repeated failures in enterprise IT systems, and (ii) automated application traffic profiling on computer networks. For the first application, the diagnosis accuracy can reach 95% on a multi-tier web service testbed. For the second application, major network applications were automatically identified in the traffic logs from a large campus wireless network.

"Alice has a piece of valuable information which she is willing to sell to anyone who is interested in; she is too busy and wants to ask Bob, a professional broker, to sell that information for her; but Alice is in a dilemma where she cannot trust Bob with that information but Bob cannot help her find her customers without knowing that information." In this paper, we propose a security mechanism called information foiling to address new confidentiality problems arising in pub/sub overlay services [1]. Information foiling extends Rivest's "Chaffing and Winnowing" [2], and its basic idea is to carefully generate a set of fake messages to hide an authentic message. Information foiling requires no modification inside the broker network so that the routing/filtering capabilities of broker nodes remains intact. We formally present the information foiling mechanism in the context of publish/subscribe overlay services, and discuss its applicability in other Internet applications. For publish/subscribe applications, we propose a suite of optimal schemes for fake message generation in different scenarios. Real-world data are used in our evaluation to demonstrate the effectiveness of the proposed schemes.

In this paper we measured and analyzed the workload on Yahoo! Video, the 2nd largest U.S. video sharing site, to understand its nature and the impact on online video data center design. We discovered interesting statistical properties on both static and temporal dimensions of the workload; they include file duration and popularity distributions, arrival rate dynamics and predictability, and workload stationarity and burstiness. Complemented with queueing-theoretic techniques, we extended our understanding on the measurement data with a virtual data center design assuming the same workload as measured, which reveals results regarding the impact of workload arrival distribution, service level agreements (SLAs) and workload scheduling schemes on the design and operations of such large-scale video distribution systems.

The behavior of network entities, such as flows, sessions, hosts, and users, can often be described by communication event sequences in the time domain. For the purpose of many network measurement and monitoring tasks, it is desirable to have an accurate yet information-compact profiling of the behavior of massive event sequences. This paper proposes a new method to achieve this goal. On a given set of event sequences, the proposed method automatically learns a mixture model which fully captures the sequence behavior including both event pattern and duration between events. The learned mixture model is information-compact as it classifies sequences into a set of behavior templates, each of which is described by a Markov Chain. The model parameters are estimated in an iterative procedure which is developed from the Expectation Maximization algorithm. Two network management applications are proposed based on the method: a visualization tool for network administrators to conduct exploratory traffic analysis, and an efficient anomaly detection mechanism. In the evaluation, we validate the method accuracy as well as the usefulness of the two applications by using three networking datasets with different types: TCP packet traces, VoIP calls, and syslog traces in wireless networks.

In this paper we measured and analyzed the workload on Yahoo! Video, the 2nd largest U.S. video sharing site, to understand its nature and the impact on online video data center design. We discovered interesting statistical properties on both static and temporal dimensions of the workload including file duration and popularity distributions, arrival rate dynamics and predictability, and workload stationarity and burstiness. Complemented with queueing-theoretic techniques, we further extended our understanding on the measurement data with a virtual design on the workload and capacity management components of a data center assuming the same workload as measured, which reveals key results regarding the impact of Service Level Agreements (SLAs) and workload scheduling schemes on the design and operations of such large-scale video distribution systems.

Service hosting platforms typically run a large number of third-party applications that are composed of multiple communicating components distributed on a dynamic set of hosting servers. Understanding the real-time behaviors of these applications and the intricate interactions/dependency relationships among these application components is very important to service management tasks such as load balancing, capacity planning, performance debugging and fault diagnosis. In this paper, we present the scalable real-time application monitoring and diagnosis (SRAMD) tool, for applications consisting of "black box" components: software without source code available, and usually without desired logging instrumentation. SRAMD runs at application layer and requires no modification to existing applications, middleware, or messages. For each application component collocated at its hosting server, a SRAMD monitor traces the component's packet-level traffic unobtrusively, summarizes its local resource utilization and performance (e.g. response time) online, performs interactive queries (e.g. per- request resource utilization) to locate possible bottlenecks on- demand, and discovers inter-component dependence relationships statistically. The SRAMD controller simply aggregates reports from distributed monitors to construct real-time application topologies with rich runtime information. We have developed mechanisms to decentralize the computation overhead and minimize the communication cost in the monitoring and diagnosis process, and two schemes to discover application component dependency relationships in different scenarios. The SRAMD tool offers an alternative to server logs and message-level traces for service monitoring and performance diagnosis.

SMS has been arguably the most popular wireless data service for cellular networks. Due to its ubiquitous availability and universal support by mobile handsets and cellular carriers, it is also being considered for emergency notification and other mission-critical applications. Despite its increased popularity, the reliability of SMS service in real-world operational networks has received little study so far. In this work, we investigate the reliability of SMS by analyzing traces collected from a nationwide cellular network over a period of three weeks. Although the SMS service incorporates a number of reliability mechanisms such as delivery acknowledgement and multiple retries, our study shows that its reliability is not as good as we expected. For example the message delivery failure ratio is as high as 5.1% during normal operation conditions. We also analyze the performance of the service under stressful conditions, and in particular during a "flash-crowd" event that occurred in New Year's Eve of 2005. Two important factors that adversely affect reliability of SMS are also examined: bulk message delivery that may induce network-wide congestion, and the topological structure of the social network formed by SMS users, which may facilitate quick propagation of viruses or other malware.

In modern cellular networks, the channel quality is dynamic among users and also over time. The time-granularity for such dynamics is significantly diverse - either slow or fast compared to packet transmission time. Because of these issues most existing scheduling policies can not work consistently well. In this work, we propose a scheduling policy with performance relatively insensitive to the time-granularity of the dynamics of channel quality. Our policy is self-adaptive to the scale of channel variations by using an ensemble of proposed algorithms. The proposed scheduling policy is proved to have a worst-case performance bound in the existence of both slow and fast time-varying channels. Simulation results confirm that the policy better tolerates channel variations than other popular schemes such as EDF and the Greedy algorithm.

In third-generation (3G) wireless data networks, providing service to low data-rate users is required for maintaining fairness, but at the cost of reducing the cell's aggregate throughput. In this paper, we propose the unified cellular and ad hoc network (UCAN) architecture for enhancing cell throughput while maintaining fairness. In UCAN, a mobile client has both 3G interface and IEEE 802.11 -based peer-to-peer links. The 3G base station forwards packets for destination clients with poor channel quality to proxy clients with better channel quality. The proxy clients then use an ad hoc network composed of other mobile clients and IEEE 802.11 wireless links to forward the packets to the appropriate destinations, thereby improving cell throughput. We refine the 3G base station scheduling algorithm so that the throughput gains are distributed in proportion to users' average channel rates, thereby maintaining fairness. With the UCAN architecture in place, we propose novel greedy and on-demand protocols for proxy discovery and ad hoc routing that explicitly leverage the existence of the 3G infrastructure to reduce complexity and improve reliability. We further propose secure crediting mechanisms to motivate users that are not actively receiving to participate in relaying packets for others. Through both analysis and extensive simulations with HDR and IEEE 802.11b, we show that the UCAN architecture can increase individual user's throughput by more than 100 percent and the aggregate throughput of the HDR downlink by up to 50 percent.

In recent years, cellular networks have experienced an astronomical increase in the use of Short Message Service (SMS), making it a popular communication means for inter-personal as well as content provider-to-person usage. Yet little is known about the traffic and message user behavior in real SMS systems. In this paper, we present a measurement study of SMS based on traces collected from a nationwide cellular carrier during a three-week period. We characterize message traffic at both the message level and the conversation thread level. We also examine the "store-and-forward" mechanism of SMS and present initial measurements on how messages are actually delivered.

We introduce a medium access control protocol for ad hoc networks. The new protocol, which we call ORMA (opportunistic reservation multiple access) is aimed at providing both high throughput and bounded channel access delays, which are critical for supporting integrated voice and data services over ad hoc networks. In ORMA, the channel is divided into a random access section and a scheduled access section. The first is used to exchange neighborhood information, the latter is used for data transmissions over time slots organized in frames, with each time slot being accessed through reservations or probabilistic elections. To attain high throughput, nodes access data slots based on a fair election in which they win with a certain probability. To attain bounded channel access delays, nodes reserve time slots by using a novel opportunistic reservation. The performance of ORMA is studied by both analysis and simulations. It is also compared against the performance of schemes based entirely on probabilistic or fixed conflict-free slot assignment

Protecting the network layer from malicious attacks is an important yet challenging security issue in mobile ad hoc networks. In this paper, we describe SCAN, a unified network-layer security solution for such networks that protects both routing and data forwarding operations through the same reactive approach. SCAN does not apply any cryptographic primitives on the routing messages. Instead, it protects the network by detecting and reacting to the malicious nodes. In SCAN, local neighboring nodes collaboratively monitor each other and sustain each other, while no single node is superior to the others. SCAN also adopts a novel credit strategy to decrease its overhead as time evolves. In essence, SCAN exploits localized collaboration and information cross-validation to protect the network in a self-organized manner. Through both analysis and simulation results, we demonstrate the effectiveness of SCAN even in a highly mobile and hostile environment.

Several studies have recently been performed on wireless university campus networks, corporate and public networks. Yet little is known about the flow-level characterization in such networks. In this paper, we statistically characterize both static flows and roaming flows in a large campus wireless network using a recently-collected trace. For static flows, we take a two-tier approach to characterizing the flow arrivals, which results a Weibull regression model. We further discover that the static flow arrivals in spatial proximity show strong similarity. As for roaming flows, they can also be well characterized statistically.We explain the results by user behaviors and application demands, and further cross-validate the modeling results by three other traces. Finally, we use two examples to illustrate how to apply our models for performance evaluation in the wireless context.

Transport protocol design for supporting multimedia streaming in mobile ad hoc networks is challenging because of unique issues, including mobility-induced disconnection, reconnection, and high out-of-order delivery ratios; channel errors and network congestion. In this paper, we describe the design and implementation of a transmission control protocol (TCP)-friendly transport protocol for ad hoc networks. Our key design novelty is to perform multimetric joint identification for packet and connection behaviors based on end-to-end measurements. Our NS-2 simulations show significant performance improvement over wired TCP friendly congestion control and TCP with explicit-link-failure-notification support in ad hoc networks.

This work seeks a better understanding of the relations between the better network service provided by QoS-oriented wireless packet scheduling and the actual benefits perceived by the multimedia applications that use them. Through extensive simulations driven by real (multimedia and wireless channel error) traces, we observe that in general, there is a performance gap between application perceived QoS and network QoS provided by the wireless fair packet scheduler. This gap tends to increase further as the channel error rate aggravates. The exact distribution of channel errors greatly affects the multimedia application performance, but its impact on network QoS is much smaller. We then present the solution, which is based on idealized weighted fair queuing (IWFQ) to further improve three popular multimedia applications' performance.

Transport protocol design for mobile ad hoc networks is challenging because of unique issues, including mobility-induced disconnection, reconnection, and high out-of-order delivery ratios; channel errors; and network congestion. We describe the design and implementation of a TCP-friendly transport protocol for ad hoc networks. Our key design novelty is to perform multi-metric joint identification for packet and connection behaviors based on end-to-end measurements. Our testbed measurements and ns-2 simulations show a significant performance improvement over standard TCP in ad hoc networks.

Several recent studies have indicated that TCP performance degrades significantly in mobile ad hoc networks. This paper examines how badly TCP may perform in such networks and provides a quantitative characterization of this performance gap. Previous approaches typically made comparisons by ignoring the inherent dynamics such as mobility, channel error and shared-channel contention. Our work provides a realistic, achievable TCP throughput upper bound, and may serve as a benchmark for future TCP modifications in ad hoc networks. Our simulation findings indicate that node mobility, especially mobility-induced network disconnection and reconnection events, has the most significant impact on TCP performance. TCP NewReno merely achieves about 10% of a reference TCPs throughput in such cases. As mobility increases, the relative throughput drop ranges from almost 0% in the static case to 1000% in a highly mobile scenario (mobility speed is 20 m/sec). In contrast, congestion and mild channel error (say, 1%) have less visible effect on TCP (with less than 10% performance drop compared with the reference TCP).

Inspired by Zhang's work on flexible calibration technique, a new easy technique for calibrating a camera based on circular points is proposed. The proposed technique only requires the camera to observe a newly designed planar calibration pattern (referred to as the model plane hereinafter) which includes a circle and a pencil of lines passing through the circle's center, at a few (at least three) different unknown orientations, then all the five intrinsic parameters can be determined linearly. The main advantage of our new technique is that it needs to know neither any metric measurement on the model plane, nor the correspondences between points on the model plane and image ones, hence the whole calibration process becomes extremely simple. The proposed technique is particularly useful for those people who are not familiar with computer vision. Experiments with simulated data as well as with real images show that our new technique is robust and accurate. (C) 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.