Browsing by Author "Chou, Cheng-Fu"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item On a Graph-theoretic Approach to Scheduling Large-scale Data Transfers(2002-04-04) Cheng, William C.; Chou, Cheng-Fu; Golubchik, Leana; Khuller, Samir; Wan, Yungchun (Justin)In this paper we consider the problem of moving a large amount of data from several different hosts to a single destination in a wide-area network. Often, due to congestion conditions, the choice of paths by the network may be poor. By choosing an indirect route at the application level, we may be able to obtain substantially higher performance in moving data through the network. We formulate this data transfer (collection) problem as a network flow problem. We show that by using a min-cost flow algorithm on an appropriately defined time-expanded (network) graph, we can obtain a data transfer schedule. We show that such schedules can be an order of magnitude better than schedules obtained by transferring data directly from each host to the destination. In fact, this holds, even though we make no assumptions about knowledge of the topology of the network or the capacity available on individual links of the network. We simply use end-to-end type information and compute a schedule for transferring the data. Finally, we also study the shortcomings of this approach in terms of the gap between the network flow formulation and data transfers in a wide-area network. Also UMIACS-TR-2002-04Item Performance of Batch-based Digital Signatures(2002-04-04) Cheng, William C.; Chou, Cheng-Fu; Golubchik, LeanaA Digital Signature is an important type of authentication in a public-key (or asymmetric) cryptographic system, and it is in wide use. The performance of an Internet server computing digital signatures online is limited by the high cost of modular arithmetic. One simple way to improve the performance of the server is to reduce the number of computed digital signatures by combining a set of documents into a batch in a smart way and signing each batch only once. This reduces the demand on the CPU but requires extra information to be sent to clients. In this paper, we investigate performance of online digital signature batching schemes and show that significant computational benefits can be obtained from batching without significant increases in the amount of additional information that needs to be sent to the clients. We also give a semi-Markov model of a batch-based digital signature server and its approximate solution. We validate the solutions of the analytical model through both emulation and simulation. Also UMIACS-TR-2002-03Item A Performance Study of a Large-scale Data Collection Problem(2002-08-01) Chou, Cheng-Fu; Wan, Yung-Chun (Justin); Cheng, William C.; Golubchik, Leana; Khuller, SamirIn this paper, we consider the problem of moving a large amount of data from several source hosts to a destination host over a wide-area network, i.e., a large-scale data collection problem. This problem is important since improvements in data collection times in many applications such as wide-area upload applications, high-performance computing applications and data mining applications are crucial to performance of those applications. Existing approaches to the large-scale research are transferring data either directly, i.e., direct methods, or using ``best''-path type of application-level re-routing techniques, which we refer as non-coordinated methods. However, we believe that in the case of large-scale data collection applications, it is important to *coordinate* data transfers from multiple sources. More specifically, our coordinated method would take into consideration the transfer demands of all source hosts and then schedule all data transfers in parallel by using all possible existing paths between the source hosts and the destination host. We present a performance and robustness study of different data collection methods. Our results showed that coordinated methods can perform significantly better than non-coordinated and direct methods under various degrees and types of network congestion. Moreover, we also showed that coordinated methods are more robust than non-coordinated methods under inaccuracies in network condition information. Therefore, we believe that coordinated methods are a promising approach to large-scale data collection problems. Also UMIACS-TR-2002-62