ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 February 2008, Volume 45 Issue 2
Contagion Worm Propagation Simulation and Analysis
Wang Yuewu, Jing Jiwu, Xiang Ji, and Liu Qi
2008, 45(2):  207-216. 
Asbtract ( 315 )   HTML ( 0)   PDF (602KB) ( 388 )  
Related Articles | Metrics
Although active worms have great spread speed, they usually stir anomalous traffic pattern during targets discovery, which make them easy to be detected. Thus, worm authors turn to increasing the stealth of worms to make them propagate more effectively. Contagion worm is a typical paradigm of stealth worms. It takes advantage of the normal Internet operation traffic to propagate through the Internet, thus it can spread faster than the traditional passive worm, and evinces almost no peculiar communication patterns. Because of its spread speed and stealth, Contagion worm is becoming an immediately security threat on Internet. In order to get insight into Contagion worm propagation, it is necessary to construct a suitable simulation model. Unfortunately, all existing simulation models are constructed for active worms, and can't dynamically simulate the network traffic that is necessary for Contagion worm simulation. Here, a dynamic operation traffic simulation model is presented to adapt for Contagion worm simulation. Through selective abstraction, the scalable bottleneck of packet level worm simulation is broken and a complete Contagion worm simulation system is implemented based on the general network simulator. A series of analyses experiments are conducted by this simulation system to analyze the Contagion worm propagation. Simulation results indicate that the simulation method is very effective in Contagion worm study.
A Connectible-Cell Based Topology Control Algorithm for Wireless Sensor Networks
Jin Xin, Xiong Yan, Li Min, and Yue Lihua
2008, 45(2):  217-226. 
Asbtract ( 266 )   HTML ( 0)   PDF (541KB) ( 347 )  
Related Articles | Metrics
In wireless sensor networks topology control (TC), cell based TC algorithms have been recognized as a type of methods which could conserve nodes' energy and extend network lifetime. However, they require too many backbone nodes and can't guarantee connectivity. By investigating the limitations of these algorithms, a 1-con method is proposed: when a cell head is connected into the current backbone, all cells that could be reached by this head will be connected to the topology structure through it, and then the new backbone expands itself recursively in this way. By leveraging the 1-con method, a connectible-cell based topology control algorithm (CCTC) is designed. It could be theoretically proved that 1) CCTC could guarantee the network connectivity; and 2) In every round, CCTC needs fewer active nodes than other algorithms do. The computing complexity of CCTC is linear; and the storage space and the message amount are bounded by constant magnitude. Simulation results also validate that CCTC provides impressive energy conservation and longer network lifetime with decent robustness and limited control overheads.
Identification of BitTorrent Traffic for High Speed Network Using Packet Sampling and Application Signatures
Guo Zhenbin and Qiu Zhengding
2008, 45(2):  227-236. 
Asbtract ( 345 )   HTML ( 0)   PDF (514KB) ( 506 )  
Related Articles | Metrics
It is very difficult to identify peer-to-peer (P2P) traffic in high speed network environment because well-known port numbers are no longer reliable and application signatures are not efficient enough. In this paper, a BitTorrent traffic identification method for high speed network using packet sampling and application signatures is presented. Models of false negatives and false positives are developed to analyze the effects of packet sampling probability and application signatures probability on accuracy. The method is implemented with Snort by developing a flow state differentiating preprocessor. The experiment results show that the efficiency and accuracy of the method are exciting and the method can be applied to high speed network. The low limit of processing efficiency is over 800 Mbps on a personal computer hardware platform. Assuming that the method is applied to processing packets, the false negatives rate is about 0.6% with 0.5 sampling probability, about 5.9% with 0.1 sampling probability, and about 10.5% with 0.05 sampling probability. Assuming that the method is applied to analyzing flows, the false negatives rate is about 0.06% with 0.5 sampling probability, about 0.33% with 0.1 sampling probability, and about 1.1% with 0.05 sampling probability. The method shows excellent false positives with no packet falsely identified. The experiment results also show that the false negatives and false positives models are very accurate.
An Algorithm for Detecting Filters Conflicts Based on the Intersection of Bit Vectors
Li Lin and Lu Xianliang
2008, 45(2):  237-245. 
Asbtract ( 509 )   HTML ( 1)   PDF (448KB) ( 569 )  
Related Articles | Metrics
Detection of conflicts among filters is an important issue for packet classification and network security. On the one hand, to reduce the time spent on packet classification, a certain algorithm for detecting filters conflicts should be applied to find out all conflicting filters during the preprocessing phase and the update phase. On the other hand, because of the complexity of firewall filters, when firewall administrators add a filter, the newly added filter may conflict with the existing ones. This may lead to security vulnerabilities. Thus a certain algorithm for detecting filters conflicts should also be applied to find out all the existing filters conflicting with the new filter. Several algorithms for detecting conflicts have already been proposed but most of them are of poor performance or set restrictions on filters. Presented in this paper is an algorithm named DBBV for detecting filters conflicts, which is based on ASBV. Similar to ASBV, DBBV employs a divide-and-conquer method and bit vectors. Different from ASBV, DBBV needs only to calculate the intersection of bit vectors once in the course of every dimensional processing, while ASBV needs to compute the union of bit vectors many times. Also, DBBV does not set any restrictions on filters, while ASBV limits every field of filters to be a prefix. Experiments show that the performance of DBBV is better than that of ASBV.
Cost Optimization Heuristics for Grid Workflows Scheduling Based on Serial Reduction
Yuan Yingchun, Li Xiaoping, and Wang Qian,
2008, 45(2):  246-253. 
Asbtract ( 347 )   HTML ( 0)   PDF (470KB) ( 450 )  
Related Articles | Metrics
Workflow scheduling which guarantees the anticipated QoS (quality of service) is a fundamental and complexity problem in computational grids. In this paper, the scheduling of workflows represented by directed acyclic graph (DAG) with the objective of cost minimization is considered. In general, the optimization problem is NP-hard. Two new heuristics, FSRD (forward serial reduction with deadline) and BSRD (backward serial reduction with deadline) are proposed. According to the property of serial activities, a new concept called series reduction (SR) is defined. The time window for each serial reduction group is recalculated based on leveling algorithms. A dynamic programming method is presented for implementing the cost minimization of each serial reduction group. By integrating the local optimization strategy with two leveling algorithms (DBL and DTL), BSRD and FSRD are investigated. The two heuristics take into account comprehensive serial and parallel properties of DAG, and improve the cost optimization strategies adopted by leveling algorithms. Experimental results show that BSRD and FSRD can considerably improve the average performance of corresponding leveling heuristics. For pipeline workflows, BSRD (FSRD) can achieve the optimal solutions but require a little more computational time. For hybrid workflows, BSRD can save 8.77% average cost of DBL and FSRD can save 6.00% average cost of DTL. Moreover, BSRD outperforms FSRD. As well, the impact of serial reduction ratio on two heuristics is analyzed.
A Novel Framework for Miscellaneous Data Gathering in Wireless Sensor Networks
Xu Jianbo, and Li Renfa
2008, 45(2):  254-260. 
Asbtract ( 313 )   HTML ( 0)   PDF (405KB) ( 492 )  
Related Articles | Metrics
The number of sensor nodes in wireless sensor networks are numerous and single node is extraordinarily limited in resource. The first aim of designing routing data gathering protocol of wireless sensor networks is to reduce the overall energy dissipated in the network and to maximize the network lifetime. The author analyzed and compared several typical existing data gathering protocols, based on the actual application needs, design a new data gathering protocol—miscellaneous data gathering protocol based on node clustering in wireless sensor networks(MDGP). MDGP is a differentiated service data gathering protocol based on in-network data aggregation. It is suitable for mine large-scale security detection applications. In this paper, a new algorithm for cluster head election is proposed, which can balance the load and reduce the number of cluster head. The data aggregation tree, a multiple-source single-sink communication paradigm, is employed for abstracting the packet flow. A real-time scenario where the data gathering must be performed within a specified latency constraint is also considered. The simulation results show that MDGP provides longer lifetime than the current important protocol and achieves its design goal.
A Dynamic Knowledge-Based Task Scheduling Algorithm in Simulation Grid Environment
Wu Lei and Du Zhihui
2008, 45(2):  261-268. 
Asbtract ( 304 )   HTML ( 0)   PDF (413KB) ( 405 )  
Related Articles | Metrics
Simulation grid is a specific grid which is based on general grid technology and oriented towards simulation. At present, researches on simulation grid are still at the fledgling stage. Simulation resources as well as federates in HLA-based distributed simulation are statically bound now. Introduction of grid technology makes the dynamic allocation of the simulation resources come to reality. However,there is little relevant literature discussing task scheduling in simulation grid now. Therefore, it's a new research field of high practical value. Simulation grid provides a flexible and powerful simulation platform to execute large-scale simulation applications. The focus here is on the task scheduling in simulation grid environment. In this paper, a new task scheduling model in simulation grid is built firstly, and a novel knowledge-based dynamic task scheduling algorithm KMO is proposed for scheduling N independent tasks with the different length onto a simulation gird with M resources whose computing power varies over time. In this algorithm, the results of several scheduling are collected and refined to form knowledge, which is then used in pretreatment stage in the algorithm. Finally, the experiment result shows that KMO is better than the traditional task scheduling algorithms in simulation grid environment.
DPVoD: P2P Based Video-on-Demand Architecture
Wu Ai, Liu Xinsong, Fu Qingyun, and Liu Kejian
2008, 45(2):  269-277. 
Asbtract ( 604 )   HTML ( 3)   PDF (452KB) ( 343 )  
Related Articles | Metrics
Scalability and reliability are essential to VoD. A P2P based VoD architecture (DPVoD) is proposed in this paper, which can support large-scale and reliable VoD services in the Internet. DPVoD is based on application-layer multicast, every user uses assignable-size buffer to cache the most recent video received, and provides services for later comers, and all users who share the same streaming are grouped in a multicast tree. Based on the extent of the overlap of streaming data among multicast trees, three kinds of neighbor relationships are defined. A tree may collaborately work with its neighbor trees in operations such as user joining, load balancing and fault tolerant controlling. To improve the performance of DPVoD, several mechanisms are put forward, including an efficient distributed state control protocol to exchange user state imformation efficiently, the parent selection strategy to increase the capacity of the system, and a reliable failure recovery mechanism. The problem of tail snowslide is defined for the first time. The analysis indicates that it may have a strong impact on the quality of service of VoD, and the corresponding solution is also presented. Performance analyses are carried out in theory, and the simulation results show that the proposed architecture outperforms similar systems in a number of important performance metrics such as the server stress, reliability, service ability and so on.
Research on an Algorithm for Approximate Quantile Computation over Data Streams
Yang Bei, and Huang Houkuan
2008, 45(2):  287-292. 
Asbtract ( 635 )   HTML ( 0)   PDF (347KB) ( 1531 )  
Related Articles | Metrics
Data stream is a new data model that has attracted attentions in numerous applications such as traffic monitoring, telephone records management, sensor networks, stock-market analysis, Web click streams, etc. The importance of quantile estimation of data streams has been highlighted by more and more researchers in recent years. Due to the characteristics of continuity and boundlessness of streaming data, it is unfeasible to memorize the entire information of data streams and thus difficult to get the exact answer to the query on streaming data. In this paper, a novel synopsis data structure—Nord_Histogram for storing streaming data summary is designed to get a balance between the memory cost and the query accuracy, and a one-pass online approximate algorithm for quantile computation is presented. The algorithm implements the approximate quantile queries over data stream with the time and space requirements being linear with the number of the buckets, which has no business with the length of data streams, and therefore has great scalability. This method has very good performance on data with uniform distribution. The correlation between the computation accuracy and main memory requirement is also analyzed. Experimental results show that the algorithm brings about quite small relative errors and works well over data streams.
Using Pattern and Linguistic Features to Improve Reading Comprehension Performance
Du Yongping, Huang Xuanjing, and Wu Lide
2008, 45(2):  293-299. 
Asbtract ( 354 )   HTML ( 2)   PDF (397KB) ( 393 )  
Related Articles | Metrics
A reading comprehension (RC) system aims to understand a single document (i.e. story or passage) in order to be able to automatically answer questions about it. RC resembles the ad hoc question answering (QA) task that aims to extract an answer from a collection of documents when posed with a question. However, since RC focuses only on a single document, the system needs to draw upon external knowledge sources to achieve deep analysis of passage sentences for answer sentence extraction. Proposed in this paper is an approach towards RC that attempts to utilize external knowledge to improve performance, including (i) automatic acquisition of Web-based answer patterns and its application in answer sentence matching; (ii) linguistic feature matching; (iii)lexical semantic relation inference, and (iv)context assistance. This approach gives improved RC performances for both the Remedia and ChungHwa corpora, attaining HumSent accuracies of 45% and 69% respectively. In particular, performance analysis based on Remedia shows that relative performances of 24.1% is due to the application of Web-derived answer patterns and a further 11.1% is due to linguistic feature matching. Pairwise t-tests are also conducted and the result shows that the performance improvements due to Web-derived answer patterns, linguistic feature matching and lexical semantic relation inference technique are statistically significant.
Mapping Between Relational Database Schemas and Ontologies: The State of the Art
Qu Yuzhong, Hu Wei, Zheng Dongdong, and Zhong Xinyu
2008, 45(2):  300-309. 
Asbtract ( 511 )   HTML ( 0)   PDF (488KB) ( 567 )  
Related Articles | Metrics
Ontologies proliferate with the growth of the semantic Web. To date, however, most of the data on the Web are still stored in relational databases. Therefore, it is important to establish interoperability between relational databases and ontologies for creating a Web of data. An effective way to achieve such interoperability is to discover mappings between relational database schemas and ontologies. In this paper, some definitions in terms of mapping between a relational database schema and an ontology are firstly presented, and two major difficulties are analyzed from the standpoints of model construction and concrete application context. Then, a large number of popular existing solutions are surveyed according to three different facets, i.e., the approaches of model transformation (e.g., transforming ontologies to relational database schemas, transforming relational database schemas to ontologies, or transforming both relational database schemas and ontologies to medium models), the scopes of mapping strategies (e.g., automatization, and number of relational database schemas and ontologies), and the expressions of mapping results (e.g., simple correspondences, or semantic mappings). In addition, six representative mapping tools are introduced and compared with each other based on the three different facets mentioned above, and their unique features are highlighted in details. Finally, some remaining challenges are discussed, and some future research directions are also pointed out.
An Approximate k-Closest Pair Query Algorithm Based on Z Curve
Xu Hongbo and Hao Zhongxiao,
2008, 45(2):  310-317. 
Asbtract ( 483 )   HTML ( 0)   PDF (540KB) ( 461 )  
Related Articles | Metrics
The k-closest pairs query is one of the important operations of spatial database. The k-self-closest pair query algorithm based on R*-tree (k-self-CPQ) and brute-force method could achieve better performance in low-dimensional space, but their performances suffer greatly in high-dimensional space, so the reduction of the dimensionality is the key to the problem. Space-filling curve has been extensively used as a mapping scheme from high-dimensional space into linear space, and imposes a linear order of points in the space. It is like a thread that goes through all the points in the space. Hilbert curve, Gray curve, and Z curve are three important space-filling curves. The mapping of Z curve could apply to high-dimensional space easily. Based on Z curve, a method of the reduction of the dimensionality, a notion of minimum grid, and an approximate k-closest pair algorithm under the L_t-metric (t=1,…,∞) are presented. It uses multiple shifted copies (ZL-set) of the data point sorted according to their position along Z curve. Using the length of minimum grid, it optimizes the procedure of scanning ZL-set. The algorithm is efficient and simple to implement. Experimental results, obtained by using real and synthetic data sets in high-dimensional space, indicate that its performance is better than that of the k-self-CPQ and brute-force methods, and the quality of approximate k-closest pair is better than that of theoretical analysis.
Property Sequence Chart: Formal Syntax and Semantic
Zhang Pengcheng, Zhou Yu, Li Bixin, and Xu Baowen
2008, 45(2):  318-328. 
Asbtract ( 436 )   HTML ( 1)   PDF (649KB) ( 422 )  
Related Articles | Metrics
Temporal logics are extensively used to reason about correctness of concurrent system in scenario-based software engineering. Formal verification techniques such as model checking can automatically check the consistence between the system and the properties. These properties are usually represented by linear temporal logics. Unfortunately, the inherent complication of linear temporal logic formulas makes model checking difficult to apply widely in industry practice. Property sequence chart is a scenarios-based visual language, which can solve this problem; it not only has the ability of powerful expression and simplicity, but also can tackle the defaults of currently used notations in industry such as UML 2.0 sequence diagrams and message sequence charts and, in academy, such as live sequence chart. In order to describe PSC clearly and make it used widely, this paper gives the formal syntax and formal semantic. The basic semantic of basic property sequence chart based on Büchi automaton is first given and then the semantic of how to get more complex property sequence chart with Par, Loop, Simulat operators is put forward. Semantic of how to compose two property sequence charts into a more complex one is also given. Finally, some examples are studied and its future applications in model checking are discussed.
Research on Unified Object Model Supporting HLA-Based Simulation and Parallel Rendering
Wang Zonghui, Xiong Hua, Jiang Xiaohong, and Shi Jiaoying
2008, 45(2):  329-336. 
Asbtract ( 323 )   HTML ( 0)   PDF (476KB) ( 389 )  
Related Articles | Metrics
With the development of computer hardware, network, and software technology, and also with the development of social requirements, distributed interactive simulation applications which involve massive complex scene and large quantity of simulation entity objects put high demand on simulation object management capability and scene rendering ability. There are two problems in the existing HLA-based distributed interactive simulation applications. One is the fact that the timeliness of scene simulations with massive complex scene are bad. The other is that the management of simulation entity object and the management of rendering object are separate. In order to solve the above problems, a unified object model consisting of heterogenous scene graph tree, action list and universal access interface, is presented, realizing the efficient organization and unified management of simulation entity object and rendering object. The unified object model builds a bridge for high efficient data exchange between HLA-based simulation platform and parallel rendering platform, reducing the development workload of integration between them, and supporting the real-time rendering of massive complex scene and large quantity of simulation entity object to help to enhance the timeliness of scene simulation. The unified object model is a common method for HLA-based simulation platform and parallel rendering platform. Finally, an experimental demo with analysis is given.
Research on Real-Time Realizing PGA Algorithm in FPGA
Hao Zhiquan, Wang Zhensong, and Liu Bo,
2008, 45(2):  342-347. 
Asbtract ( 559 )   HTML ( 0)   PDF (364KB) ( 529 )  
Related Articles | Metrics
Synthetic aperture radar (SAR) image has some common features such as huge data volume, relative complex algorithm, etc. Realizing SAR image algorithm is worthy of being studied in the domain of EHPC (embedded high performance computing). FPGA is used as a high efficient and low cost solution in EHPC for its high performance and reconfigurable ability. A new phase gradient autofocus (PGA) algorithm for real time case is proposed, which can achieve convergence focusing quality with less iteration and fewer computation loads than the classic PGA algorithm. The principle of how to map the improved algorithm to FPGA architecture is discussed. Some key computing components abstracted from the algorithm, such as CORDIC processor, complex vector correlator and prominent scatter filter are also discussed. The motivation and aim of this work is to develop a numerically efficient, accurate and robust Doppler rate estimator with reasonable architecture in FPGA, which can be used in a high-throughput-rate processor for future onboard imaging system. Because logic resources are effectively used, constraints on volume, weight, and power are easier to meet without sacrifice of losing real-time performance. Experiment result indicates that the improved algorithm reduces iteration times and the precision can satisfy the imaging system.
A Rollback Recovery Algorithm Based on Causal Message Logging in Mobile Environment
Zhang Zhan, Zuo Decheng, Ci Yiwei, and Yang Xiaozong
2008, 45(2):  348-357. 
Asbtract ( 416 )   HTML ( 0)   PDF (553KB) ( 474 )  
Related Articles | Metrics
Due to the unreliable mobile hosts and the fragile network connection, it is significant to research on the fault tolerance of the mobile systems. Asynchronous rollback and recovery is suitable for the mobile hosts which move across cells and disconnect from the wireless networks from time to time. The existent rollback and recovery algorithms in the mobile computing environment can not completely implement consistent asynchronous recovery. A novel rollback recovery algorithm suitable to mobile environment based on causal message logging is presented. This algorithm takes advantage of antecedence graph to trace the message dependency of mobile hosts. Simultaneously, the storage of uncoordinated checkpoint, volatile sender-based message log and antecedence graph information is carried out on the mobile support station in order that the mobile hosts can gain a transparent fault tolerant service. This algorithm can tolerate multi-failures of mobile hosts when the mobile support station fails, and completely eliminate the effect of dependence among the mobile hosts. By means of formalization, the consistency of the system is proven. The simulation result shows that compared with the optimistic and pessimistic message logging, the causal message logging algorithm has the minimized rollback cost and communication, and storage cost in the failure free phase is enormously reduced.
Error-Correcting Techniques for High-Performance Processors
Wang Zhen, Jiang Jianhui, and Yuan Chunxin
2008, 45(2):  358-366. 
Asbtract ( 303 )   HTML ( 0)   PDF (444KB) ( 484 )  
Related Articles | Metrics
The downscaling of feature size of CMOS technology results in faster transistors and lower supply voltages. This trend contributes to the overall performance improvement of integrated circuits, but it also brings more challenges to the reliability of complex circuits like microprocessors. Accordingly, the fault-tolerance design of high-performance processors becomes more and more important. Till now much work has been done for error detection and correction in processors. Some novel fault tolerant microprocessor architectures are proposed recently, such as the simultaneously and redundantly threaded processors with recovery architecture. In this paper, a comprehensive survey on conventional and up-to-date error correction techniques for high-performance processors is given. A novel taxonomy is presented, by which the fault tolerant techniques for processors are categorized into clock-level error recovery, instruction-level error recovery, thread-level error recovery and reconfiguration. Many microarchitecture schemes, prototype systems and industrial products are analyzed and detailed fault tolerant strategies and schedule algorithms are compared. It is shown that for modern processors characterized by chip multiprocessor and/or simultaneous multithreading, the reliability is mostly improved by the fault-tolerance techniques based on inherent replicated hardware resources that are designed for improving performance.
A Method of Statistics-Based Cache Leakage Power Estimation
Zhou Hongwei, Zhang Chengyi, and Zhang Minxuan
2008, 45(2):  367-374. 
Asbtract ( 273 )   HTML ( 1)   PDF (445KB) ( 357 )  
Related Articles | Metrics
Leakage power has become one of the main restrictions on microprocessor design with the decrease of the transistor's dimension, supply voltage and threshold voltage. Two important techniques to reduce leakage power in caches are sleep cache and drowsy cache in which the cache lines unused recently can be put into low-power mode. A cache leakage power estimation method based on statistics (SB_CLPE) is provided in this paper for sleep cache or drowsy cache and a cache architecture using SB_CLPE is designed which can estimate cache leakage power in real time during the execution of programs. According to the statistics of access intervals for all cache lines, the SB_CLPE can estimate the cache leakage power with different decay interval and get the optimum decay interval which can make the leakage power lowest. For sleep cache, the average variation between the leakage power estimated by SB_CLPE and the leakage power from the HotLeakage power simulator is only 3.16%. The optimum decay intervals estimated by SB_CLPE are almost identical with the real optimum decay intervals from HotLeakage. The cache architecture using SB_CLPE can be used for estimating the optimum decay interval in sleep cache or drowsy cache. By adjusting the decay interval dynamically when programs executes, the best power saving result can be achieved.
Algorithms of Reconfigurable Resource Management and Hardware Task Placement
Li Tao and Yang Yulu
2008, 45(2):  375-382. 
Asbtract ( 278 )   HTML ( 0)   PDF (497KB) ( 559 )  
Related Articles | Metrics
Reconfigurable computing system has the flexibility of traditional CPU and the speed of ASIC approximately. Based on the ability of partially dynamic reconfiguration, the tasks can be dynamically reconfigured on the reconfigurable hardware at runtime. Some hardware tasks can run at the same time with the execution of the reconfiguration process of other tasks. To some extent, the runtime reconfiguration overhead can be hidden and the system performance can be improved. Reconfigurable computing has become one of the most important computing methods. With the improvement of the size and integration, such as FPGA, more and more tasks can run and/or resident on the reconfigurable hardware concurrently. In order to utilize the reconfigurable hardware efficiently, the reconfigurable resource management and hardware task placement are very important. A task-top based keep all maximal empty rectangles (TT-KAMER) algorithm is presented in this paper. Maximal empty rectangles can efficiently represent all the empty reconfigurable resources on the reconfigurable hardware. Based on the TT-KAMER algorithm, hardware task placement can also be implemented by the first fit algorithm and the heuristic best fit algorithm. The results indicate that the algorithms can implement resource allocation and on-line task placement efficiently, and high reconfigurable resource utilization can be obtained.