Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algori...Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.展开更多
A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2...A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.展开更多
Many applications do not fit well with the traditional best effort packet delivery policy of the Internet. These include applications such as Internet telephony and video conferencing which require voice and bulky gra...Many applications do not fit well with the traditional best effort packet delivery policy of the Internet. These include applications such as Internet telephony and video conferencing which require voice and bulky graphical images transfer. Therefore, the policies of assigning traffic to various service classes and providing service as per the service level agreement of the user with the network provider came into existence. Multi-protocol Label Switching is the backbone of fast switching technology that helps the network service providers to implement these policies. It provides Quality of service oriented reserved paths from the source to the destination for the user’s traffic. Selection of these paths is a cumbersome task, especially when the traffic forecast is totally unknown. Furthermore, nodes and link failures in the Internet worsen the situation. This paper addresses the issue of selecting Label Switched Paths (LSPs) for various traffic demands in the network so that the resultant network has the characteristics like high failure resistance, low LSP demand blocking probability, low impact from the node or link failure, load balancing and low over-all resource utilization. By extensive simulations, the proposed cost function has been compared with the various cost functions mentioned in the literature and it was found to score over them in major aspects.展开更多
The (2,1)-total labeling number of a graph is the width of the smallest range of integers that suffices to label the vertices and the edges of such that no two adjacent vertices have the same label, no two adjacent ed...The (2,1)-total labeling number of a graph is the width of the smallest range of integers that suffices to label the vertices and the edges of such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper, we studied the upper bound of of Sn+1∨Pm and展开更多
In conventional shared risk link group （SRLG）-diverse path selection （CSPS） algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection meth...In conventional shared risk link group （SRLG）-diverse path selection （CSPS） algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection method is the sarne as the algorithms without SRLG constraint. A problem of CSPS algorithm is that, after a primary path is selected, the success probability to select an SRLG-diverse backup path for it is low. If SRLG is taken into account when computing the primary path, then the probability to successfully select an SRLG-diverse backup path will be much increased. Based on this idea, an active SRLG-diverse path selection （ASPS） algorithm is proposed. To actively avoid selecting those SRLG links, when computing the primary path, a link that share risk with more links is assigned a larger link cost. To improve the resource utilization ratio, it is permitted that the bandwidth resources are shared among backup paths. What is more, differentiated reliability （DiR） requirements of different customers are considered in ASPS algorithm. The simulation results show that, compared with CSPS algorithm, ASPS algorithm not only increases successful protection probability but also improves resource utilization ratio.展开更多
A multiobjective quality of service (QoS) routing algorithm was proposed and used as the QoS-aware path selection approach in differentiated services and multi-protocol label switching (DiffServ-MPLS) networks. It sim...A multiobjective quality of service (QoS) routing algorithm was proposed and used as the QoS-aware path selection approach in differentiated services and multi-protocol label switching (DiffServ-MPLS) networks. It simultaneously optimizes multiple QoS objectives by a genetic algorithm in conjunction with concept of Pareto dominance. The simulation demonstrates that the proposed algorithm is capable of discovering a set of QoS-based near optimal paths within in a few iterations. In addition, the simulation results also show the scalability of the algorithm with increasing number of network nodes.展开更多
基金Supported by the National Natural Science Foundation of China (60573089)the Teaching and Research Award Program for Out-standing Young Teachers in Post-Secondary Institutions by the Ministry of Education, China (706016)
文摘Holistic twig query processing techniques based on region encoding have been developed to minimize the intermediate results, namely, those root-to-leaf path matches that are not in the final twig results. These algorithms have to scan all the streams of tags in query patterns. However, useless path matches cannot be completely avoided. TJFast which is based on the labeling scheme of Extended Dewey has been proposed to avoid useless intermediate results, and it only needs to access the labels of the leaf query nodes. However, it don＇t concern about the characteristics of elements with the same parent, and it has to merge join all the intermediate results which are evaluated during the first phrase. We propose a new labeling scheme to compress the XML elements which have the same characteristic. Based on the compressed path-labeled streams, a new novel holistic twig query algorithm named CPJoin is designed. Finally, implementation results are provided to show that CPJoin has good performance on both real and synthetic data.
基金Supported in part by the NNSF of China(10301010,60673048)Science and Technology Commission of Shanghai Municipality(04JC14031).
文摘A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.
文摘Many applications do not fit well with the traditional best effort packet delivery policy of the Internet. These include applications such as Internet telephony and video conferencing which require voice and bulky graphical images transfer. Therefore, the policies of assigning traffic to various service classes and providing service as per the service level agreement of the user with the network provider came into existence. Multi-protocol Label Switching is the backbone of fast switching technology that helps the network service providers to implement these policies. It provides Quality of service oriented reserved paths from the source to the destination for the user’s traffic. Selection of these paths is a cumbersome task, especially when the traffic forecast is totally unknown. Furthermore, nodes and link failures in the Internet worsen the situation. This paper addresses the issue of selecting Label Switched Paths (LSPs) for various traffic demands in the network so that the resultant network has the characteristics like high failure resistance, low LSP demand blocking probability, low impact from the node or link failure, load balancing and low over-all resource utilization. By extensive simulations, the proposed cost function has been compared with the various cost functions mentioned in the literature and it was found to score over them in major aspects.
文摘The (2,1)-total labeling number of a graph is the width of the smallest range of integers that suffices to label the vertices and the edges of such that no two adjacent vertices have the same label, no two adjacent edges have the same label and the difference between the labels of a vertex and its incident edges is at least 2. In this paper, we studied the upper bound of of Sn+1∨Pm and
基金supported by the National Natural Science Foundation of China (60673142)Applied Basic ResearchProject of Sichuan Province (2006J13-067).
文摘In conventional shared risk link group （SRLG）-diverse path selection （CSPS） algorithm in survivable GMPLS networks, SRLG is taken into account when selecting the backup paths, while the primary path selection method is the sarne as the algorithms without SRLG constraint. A problem of CSPS algorithm is that, after a primary path is selected, the success probability to select an SRLG-diverse backup path for it is low. If SRLG is taken into account when computing the primary path, then the probability to successfully select an SRLG-diverse backup path will be much increased. Based on this idea, an active SRLG-diverse path selection （ASPS） algorithm is proposed. To actively avoid selecting those SRLG links, when computing the primary path, a link that share risk with more links is assigned a larger link cost. To improve the resource utilization ratio, it is permitted that the bandwidth resources are shared among backup paths. What is more, differentiated reliability （DiR） requirements of different customers are considered in ASPS algorithm. The simulation results show that, compared with CSPS algorithm, ASPS algorithm not only increases successful protection probability but also improves resource utilization ratio.
文摘A multiobjective quality of service (QoS) routing algorithm was proposed and used as the QoS-aware path selection approach in differentiated services and multi-protocol label switching (DiffServ-MPLS) networks. It simultaneously optimizes multiple QoS objectives by a genetic algorithm in conjunction with concept of Pareto dominance. The simulation demonstrates that the proposed algorithm is capable of discovering a set of QoS-based near optimal paths within in a few iterations. In addition, the simulation results also show the scalability of the algorithm with increasing number of network nodes.
