Abstract:Software Process Workshop (SPW 2005) was held in Beijing on May 25-27, 2005. This paper introduces the motivation of organizing such a workshop, as well as its theme and paper gathering and review; and summarizes the main content and insights of 11 keynote speeches, 30 regular papers in five sessions of "Process Content", "Process Tools and Metrics", "Process Management", "Process Representation and Analysis", and "Experience Reports", 8 software development support tools demonstration, and the ending panel "Where Are We Now? Where Should We Go Next?".

Abstract:Although design pattern is quite useful in software reuse, there are still many barriers when instantiating the design patterns, such as pattern overlapping, traceability, and difficulties in reusing the pattern code. A role-based approach for design pattern modeling and implementation is proposed. In this approach, roles of pattern are treated as the independent modeling elements and the RoleOf relationship is used to associate a role with an application class. This can improve the reusability of pattern. The meta-model of the RoleOf relationship for pattern instantiation and its semantics are proposed using UML extension mechanism. The stereotypes and tagged values used for identifying pattern information are provided, and it resolves the traceability and overlapping problem in pattern instantiation. The dynamic binding of application and role logic are implemented through the extension to Java language, called Rava. The approach proposed in this paper can effectively solve the problem such as pattern overlapping and traceability during the pattern instantiation, which improves the reusability of pattern logic and guides the software development using design patterns.

Abstract:Statecharts is widely used as a behavioral modeling language for reactive systems for its concise and intuitive expression. It can represent the system behavior at different levels of abstraction, and therefore can represent the result of every refinement step in the process of system modeling. However, it’s beyond its capability to reason about whether the model semantics of the lower level preserves that of the higher level and whether the models they describe satisfy some properties. In this aspect, the formal language XYZ/E can be used complementarily. The XYZ/E is an executable linear temporal logic. It can express both the properties and behavior of systems. In this paper, the semantics of Statecharts is defined inductively using the Basic Transition System, and its temporal semantics is expressed by an XYZ/E formula. The semantics we give is modularly compositional. The semantic preserving of different refinement steps can be guaranteed by the semantic definition directly. Models that Statecharts specify and their properties are represented in the same logic, so the assertion that a model meets its specification is expressed by logical implication.

Abstract:Internetware is built upon the coordination of the heterogeneous, autonomous software entities in the open coordination environment. But it is very difficult to select the honest coordination software entities with dependable quality of services to build the trusted Internetware because of the openness and dynamic of the Internet. Trust relationships among software entities will provide important information about the selections of trusted coordination entities. The trust relationships are always changing along with the co-operations of software entities. However, the existing trust models cannot support the automatic formation and update of the trust relationships among entities, and cannot reflect the dynamic attribute of the trust relationships. This paper presents a trust measurement and evolution model for the Internetware. The model abstracts the process of the trust measurement, transfer and combination rationally and provides a reasonable approach to form and update trust relationships automatically. This model is helpful to solve the problem of the trustworthiness of the Internetware.

Abstract:Following the great improvement in interaction devices and software technologies, lots of novel interaction technologies which are based on Post-WIMP user interface are studied. It is crucial that the designer chooses the interaction component or the interaction technology properly and efficiently to adapt to the various interaction devices and environments in the user interface designing. According to the analysis of the interaction process and the design level of the Post-WIMP user interface, an interaction-Centered Hierarchical Post-WIMP User Interface Model is presented. It is described and analyzed from the aspects of the user, task, device, behaviors and entity in interaction. Moreover, a Post-WIMP user interface auto-generate tool is designed and implemented based on the model, to help the designers to insert those novel interaction technologies into the system flexibly, and to develop and evaluate the prototype quickly and efficiently. Experiments show that, the model can guide the process of user interface design, the implement of prototype, and the evaluation of the result of design.

Abstract:Object-Oriented software design improving technology is an effective means to increase system flexibility for adapting to future requirement variation and expansion. In this paper, a software design improving approach, based on micro-architecture anti-pattern and case based reasoning, is presented to improve software quality and maintainability. In this approach, problematic, inflexible structures and corresponding refactoring alternatives at micro-architecture level are formally defined and described as cases. Their organization and index mechanism in the case base are studied. Following the 4R procedures of CBR, similarity measurement methods on class diagrams, sequence diagrams, OO quality metric factors, and semantic constraints are discussed. Based on the measurement results, some algorithms on identifying anti-patterns instances in a given original design and replacing them by designs with high quality are presented. Furthermore, a supporting system CBDIT is developed to aid this approach.

Abstract:The study of coalgebraic methods, as one of the active areas for theoretical computer science in recent years, is widely used in concurrence computing model, automat theory, and the foundations of object-oriented technology. Through using category theory, this paper investigates the properties of subcoalgebras, especially, the properties of subcoalgebras on Set, the category of sets and functions. This paper shows that all the subcoalgebras on Set are regular. Furthermore, using the correspondence between the cocongruence corelations and the subcoalgebras on Set, a way to construct the co-generated subcoalgebra is given in this paper.

Abstract:The automata-theoretic approach is one of the state-of-the-art model-checking methods, which consists of the following steps: use a Büchi automaton to represent the abstract system model; use an LTL formula to express the properties to be verified; translate the negation of the LTL formula to a Büchi automaton and check whether the intersection of sentences accepted by the two automata is non-empty. One type of methods for translating LTL formulas to Büchi automata has one step for calculating transition-based generalized Büchi automata (TGBA) and another step for translating TGBA to Büchi automata. This paper redefines the product operation of TGBA according to the characteristics of the accepting language of Büchi automata. This leads to the reduction of the number of states that need to be copied and therefore smaller Büchi automata. The experimental results given at the end of this paper demonstrate the advantage of the approach based on test cases with randomly generated formulas.

Abstract:Dynamic analysis of the coupled logistic map redounds to know and predict the characteristics of high-dimension complex nonlinear system. Using the method combining calculation and experiment, the following conclusions are shown: (1) The boundary equation of the first bifurcation of the coupled logistic map in the parameter space is given out. (2) Chaotic patterns of the coupled logistic map may emerge out of double-periodic bifurcation and Hopf bifurcation, respectively. (3) The boundary between periodic and non-periodic regions in the attraction basin of the coupled logistic map is fractal, which indicates the impossibility to predict the moving result of the points in phase plane. (4) The structures of the Mandelbrot-Julia sets are determined by the control parameters, and their boundaries have the fractal characteristic.

Abstract:Sliding window join aggregation continuous queries (J-A queries for short) are often used in data stream applications. The intuitive method for processing these queries is to construct steaming operator tree and execute the tree in pipeline. The space cost of this method is O(α×β) , where α and β are the sizes of two sliding windows respectively. To reduce the requirement of memory, which is the most expensive resource in data stream query processing system, two novel sliding window J-A continuous query processing algorithms IC and TC are presented in this paper, whose space cost are both O(α×β). Theoretical analysis and experimental results show that the algorithms are more effective.

Abstract:This paper investigates the inference problems due to functional dependencies (FD) and multi-valued dependencies (MVD) in a multilevel relational database with element classification schemes. The algorithms presented can greatly improve the data availability. To further deal with the indirect privacy violation, the view-based inference control method is proposed which can eliminate the secure problem brought by multi-view collusions. The theories of splitting views into the view dependency basis are the foundation of future work on the view-based inference control.

Abstract:Data model is a key research field in the community of XML data management. However, the existed works fall short in their ability to model complex data structure of XML database or to support complete operations. This paper proposes a new mapping-based data model. This model aims to give the precisely defined notations for complex data structure and semantics of XML database. Along with the model, this paper also presents an associated algebra formally which includes a set of path expression operations and data modification operations. This model has already adopted in an XML-based information integration system. It shows that this model can give the precise semantics of XML database, and support the XML database applications effectively.

Abstract:This paper targets on parallel XML document partitioning strategies to process XML queries in parallel. To describe the problem of XML data partitioning, a concept, intermediary node, is presented in this paper. By a set of intermediary nodes, an XML data tree can be partitioned into a root-tree and a set of sub-trees. While the root-tree is duplicated over all the nodes, the set of the sub-trees can be evenly partitioned over all the nodes based on the workload of user queries. For the same XML data tree, there are a number of intermediary nodes sets, and different intermediary nodes sets will generate different partitions. It can be evaluated if a partitioning is good based on the workload of user queries. It is obviously an NP hard problem to choose an optimal partitioning. To solve this problem, this paper proposes a set of heuristic rules. Based on the idea described above, this paper designs and implements an XML data partitioning algorithm, WIN, and the extensive experimental results show that its speedup and scaleup performances outperform the existing strategies.

Abstract:Query expansion has long been suggested as a technique for dealing with the fundamental issue of word mismatch in information retrieval and it has gained great success in Web searching. However, processing query expansion is very challenging in hybrid P2P network because a P2P system is a decentralized and dynamic system. First, the LEM query expansion method, which is constructed by analyzing correlation between queries and documents, is presented. And then, the HEM query expansion method is proposed by establishing the correlation between queries and documents terms directly. Next, an efficient search algorithm is constructed based on the query expansion algorithms. It is proved by experiments that the query expansion methods and search algorithms can greatly improve the search efficiency.

Abstract:In wireless sensor networks, observers are interested in spatio-temporal information monitored by sensors. Observers are not interested in sensor itself or massive irrelevant readings from sensors. They often issue spatio-temporal queries such as “Which events did happen in region R from 10:00 to 12:00?”. Since battery supply of sensors is limited, energy-efficient spatio-temporal query processing in sensor networks has become an important research problem. This paper presents a spatio-temporal query processing algorithm based on data-centric storage. The energy consumption of sensors in three storage strategies, namely external storage, local storage and data-centric storage, is analyzed and compared in this paper. The paper also studies the influence of the probability of an event occurring, node density, number of event types, number of queries, temporal window size and spatial area size in spatial-temporal query on energy consumption. Analytical and experimental results show that in most cases the spatio-temporal query processing algorithm proposed in this paper can save more energy than those algorithms based on the external storage and local storage strategies.

Abstract:Typically, online aggregation algorithms on multi-dimensional data need additional auxiliary data for estimation, which make the performance of the storage and maintenance of the data cube worse. This paper presents the PE (progressively estimate) and HPE (hybrid progressively estimate) to progressively estimate the answers for range queries in the QC-Trees. MPE (multiple progressively estimate) is also proposed to simultaneously evaluate batches of range-sum queries. The difference between the algorithms and other online aggregation algorithms on data cubes is that these algorithms do not need any auxiliary information. The idea of this estimation method is to utilize the data stored in the QC-Tree itself. As a result, this algorithm will not deteriorate the performance of the storage and maintenance of the data cubes. Analysis and experimental results show that the algorithms provide an accurate estimation in far less time than the normal algorithms.

Abstract:Multiprotocol Label Switching (MPLS) enables the deployment of Internet traffic engineering to be sim- ple and efficient by using explicit routing of Label Switching Path (LSP). Hence, the LSP routing algorithmbecomes the core and hot topic of traffic engineering. This paper analyzes the key ideas of Minimum InterferenceRouting Algorithm (MIRA) for LSP routing and then surveys the current improved schemes of MIRA. According totheir technical methods, they are classified as reconfirming critical links class, utilizing traffic profile informationclass, adding admission control class, and solving multiple Quality of Service constraints class. After the key idea is analyzed for each class, their typical algorithms are presented and their advantages, suitable environments and shortcomings with a detailed comprehensive comparison are discussed. The end of the paper points out the future research field for the min- imum interference routing problem.

Abstract:Based on the technology of EPFTS (ethernet-like physical frame timeslot switching), this paper introduces a new scheduling algorithm call TWFS (timeslot weighted fair scheduling) which could be implemented in EPFTS nodes to fit the requirement of fast data switching and QoS (quality of service) guarantee in SUPANET (single physical layer user-data platform architecture network). By analyzing merits and shortcomings of the typical scheduling techniques such as iSlip (iteration round-robin match with slip) and BvN-switch (Birkhoff-von neumann switch), TWFS utilizes the same iteration mechanism as iSlip and takes the total reserved timeslots of an I/O port pair as the weight (priority) for data switching, thus overcomes the shortcoming of the slow response to traffic fluctuation of BvN-switch, while keeping the same calculation complexity in iteration to O(log₂N) as with iSlip. Simulation results have shown that TWFS can made an optimal balance among effectiveness、fairness, and complexity and is most suitable for future high-speed EPFTS nodes in SUPANET.

Abstract:“Bottleneck Nodes” are those connecting two or more areas alone with the reason of the deployment. Compared to other nodes, this kind of nodes are more important to the lifetime of the whole network. How to find these nodes is a problem about how to find the minimum cut set in graph theory, and is difficult to implement in a distributed way. In this paper, a new kind of nodes named “quasi-Bottleneck Nodes” which have similar effect on the performance of the wireless sensor network and can be found out much more easily is introduced. Theoretical analysis and extensive simulation show that “quasi-Bottleneck Nodes” have a significant impact on the performance of the whole network (including the speed of energy consumption and packet lost ratio), and a distributed algorithm to find out all the “quasi-Bottleneck Nodes” and two effective solutions to eliminate the bad effect of these nodes are presented.

Abstract:Efficiently monitoring the network flow is important to a variety of network applications. Considering the equation of flow conservation, the problem of efficient monitoring is regarded as the problem of finding out the minimum weak vertex cover set and the minimum weak vertex cover set based on flow partition for a given graph G(V,E) which are all proved NP-Complete. Firstly the constraints of weak vertex cover set are analyzed and the integer programming formulation for it is given. Next an approximation algorithm for the minimum weak vertex cover set problem is constructed and the approximation ratio of 2 by primal-dual method is analyzed. Finally the approximation algorithm for the minimum weak vertex cover set is analyzed based on the maximal flow partition.

Abstract:In file sharing P2P (peer-to-peer) networks, the service availability is seriously affected by peers’ voluntary actions. For example, there are many freeriders and malicious peers in P2P networks. However, the pure P2P networks don’t take the issue of freeriders and malicious peers as the inherent part of the topology design, and all the peers are symmetry in the topology. This paper proposes a reciprocal capacity based adaptive topology protocol for P2P networks, which takes account of the peer’s rational belief of maintaining connections. The simulation and analyses show that the resulting topology is incentive compatible to different types of peers. In addition, compared with the proposed similar scheme, it is also more efficient with less network cost.

Abstract:This paper presents a simple but efficient path capacity model which can reinforce the theoretical foundation of the wireless mobile computing. Based on the exiting node-oriented analytical model, this paper extends the research object from the node to the path, and proposes a path-oriented capacity analytical model with pipeline queue theory. This model can further be used to explore the transmission capacity of the multi-hop wireless networks, such as MANETs and sensor networks. By using the simple capacity computation equation, network applications can adjust their optimum parameters adaptively, and the QoS routing algorithms can be designed more efficiently.

Abstract:Considering the characteristics and location information of nodes in sensor networks, a modified directed transfer model of sensor networks and a new distributed data aggregation model based on “area” are proposed. On the basis of these new models, a novel mixed entropy data compression algorithm based on interval wavelet transforming is proposed for sensor network, according to the characteristics of data in sensor networks and the good performances of wavelet transforming in compression of the data stream. Theoretical analyses and simulation results show that, the above new methods can compress the data stream and reduce the energy costs of nodes in data transferring efficiently for sensor networks. So, it can prolong the lifetime of the whole networks to a greater degree when the above new methods are deployed with those traditional DC (data centric) routing algorithms such as DD (directed diffusion) protocol for sensor networks.

Abstract:Deng, et al. proposed a security-provable mutually authenticated key agreement protocol MAKAP for mobile communication in 2003. This paper demonstrates by mounting an effective attack against MAKAP that the protocol has security flaws. It is vulnerable against unknown key-share attack. This paper investigates the reasons why such flaws exist and proposes an improved protocol version (called MAKAP-I protocol). The MAKAP-I protocol is not only provably secure within the random oracle model but also more efficient and practical in terms of computation and communication cost memory requirement and implementation cost, than the original MAKAP protocol.

Abstract:Providing video on demand service over the Internet in a scalable way is a challenging problem. This paper proposes an architecture for video on demand streaming in peer-to-peer environment, in which each peer node has a fixed-size FIFO buffer to cache the most recent content of the video stream it receives and can provide service to subsequent reached proper peer nodes. It has the following properties: 1) it utilizes a distributed control protocol to support the joining and leaving processes of peer nodes in a scalable way; 2) it considers the issue of integrity of the received program in service recovering process of the interrupted nodes. Performance studies based on simulation are carried out, and the results show that the system architecture outperforms a recently proposed system architecture P2VoD in a number of important performance metrics such as the server’s load, client join rejection probability, network resource usage ratio, program integrity ratio and so on.

Abstract:Evaluating security threat status is very important in network security management and analysis. A quantitative hierarchical threat evaluation model is developed in this paper to evaluate security threat status of a computer network system and the computational method is developed based on the structure of the network and the importance of services and hosts. The evaluation policy from bottom to top and from local to global is adopted in this model. The threat indexes of services, hosts and local networks are calculated by weighting the importance of services and hosts based on attack frequency, severity and network bandwidth consumption, and the security threat status is then evaluated. The experiment results show that this model can provide the intuitive security threat status in three hierarchies: services, hosts and local networks so that system administrators are freed from tedious analysis tasks based on the alarm datasets to have overall security status of the entire system. It is also possible for them to find the security behaviors of the system, to adjust the security strategies and to enhance the performance on system security. This model is valuable for guiding the security engineering practice and developing the tool of security risk evaluation.

Abstract:This paper describes the security protocol verifier SPVT developed by Objective-Caml. In SPVT (security protocol verifying tool), the specification language is the π-like calculus extended with three appendixes, the Dolev-Yao model is described with Horn logic rules, the π-like calculus model of security protocol is transformed into the logic program model by abstract rules, the security properties are verified based on the calculus of the logic program’s fixpoint, and the counter-examples on security properties are constructed from the process of the fixpoint calculus and the process of the property verification. The simplified Needham-Schroeder public-key authentication protocol is used to exemplify the automatic verification process of security protocol with SPVT, and the results show the validity of the verifier.

Abstract:To achieve security in the networks, it is important to be able to encrypt and authenticate messages sent between the users. Keys for encryption and authentication purposes must be agreed upon by the users in the networks. Three new pairwise key agreement protocols based on Weil pairing are proposed in this paper. In those protocols, all the users share common secret information. They may arrange the pairwise key and authenticate each other by fewer messages. The proposed protocols have the security attributes such as known session key security, perfect forward secrecy, no key-compromise impersonation, no unknown key-share and no key control.

Abstract:Large-Capacity media libraries supporting highly simultaneous access are more and more popular. Media libraries based on traditional client/server mode, or pure Grid or P2P can hardly meet the requirements of both high concurrency and reliable service. This paper proposes a new architecture combining Grid and P2P for media library—NeoMedia. It consists of the dedicated and volunteered nodes supported by the system server and forms a virtual media pool of large capacity. Coordinated by the system server, nodes requesting files from the media pool serve each other in the style of P2P, which further enhances the system’s performance. According to access pattern and intensity, the system server automatically adjusts the allocation of resources, adaptively optimizing the system’s overall performance. NeoMedia targets at view-after-downloading, which can efficiently utilize servers’ precious bandwidth and clients’ power. Theoretical analysis demonstrates that NeoMedia is able to support hugely simultaneous requests and provide non-trivial services at the same time with relatively low server-side bandwidth consumption.

Abstract:The mobility management cost of mobility support protocols is studied. Firstly a suitable network model is proposed and the signaling overhead brought to network in order to support MHs’ (mobile host) mobility using various mobility support protocols is analyzed theoretically. On this base, a numerical simulation method is applied to compare the signaling overhead when only using mobile IP with introducing hierarchical mobility and when applying different micro-mobility protocols such as MIP-RR, CIP and HAWAII. The results show that introducing hierarchical mobility decreases the network signaling overhead observably comparing with only using mobile IP. In different micro-mobility protocols, the route maintenance strategy of deleting old routes explicitly brings less signaling overhead than frequently sending refresh messages periodically, and the route update method of sending route update messages to crossover MRA (mobile routing Agent) brings less signaling overhead than sending messages to GW (gateway).

Abstract:The characteristic that nodes can enlist into the network topology freely and independently makes mobile Ad hoc networks (MANET) widely used in various environments such as disaster rescue, battlefield and so on. In MANET, the routing mechanism should adapt rapidly to the frequently changed network topology and in the mean time economize valuable network resources with its best. The Optimized Link State Routing Protocol (OLSR) is an important MANET routing protocol in which the key technique is MultiPoint Relays (MPR). After introducing the OLSR protocol and its MPR technique, the shortcoming of presently used heuristic algorithm in finding the minimum MPR sets is revealed. Then the new algorithm based on genetic algorithm (GA) is presented, and the convergence of the algorithm is proved. A series of 4 genetic algorithms are further developed by adopting different GA strategies and simulated in many topologies that are created randomly. Analysis on simulating results shows that the genetic algorithms are feasible and applicable and the choice of heuristic strategies is advisable and appropriate.

Abstract:The characteristic that nodes can enlist into the network topology freely and independently makes mobile Ad hoc networks (MANET) widely used in various environments such as disaster rescue, battlefield and so on. In MANET, the routing mechanism should adapt rapidly to the frequently changed network topology and in the mean time economize valuable network resources with its best. The Optimized Link State Routing Protocol (OLSR) is an important MANET routing protocol in which the key technique is MultiPoint Relays (MPR). After introducing the OLSR protocol and its MPR technique, the shortcoming of presently used heuristic algorithm in finding the minimum MPR sets is revealed. Then the new algorithm based on genetic algorithm (GA) is presented, and the convergence of the algorithm is proved. A series of 4 genetic algorithms are further developed by adopting different GA strategies and simulated in many topologies that are created randomly. Analysis on simulating results shows that the genetic algorithms are feasible and applicable and the choice of heuristic strategies is advisable and appropriate.