The Internet of Things(IoT)and cloud technologies have encouraged massive data storage at central repositories.Software-defined networks(SDN)support the processing of data and restrict the transmission of duplicate va...The Internet of Things(IoT)and cloud technologies have encouraged massive data storage at central repositories.Software-defined networks(SDN)support the processing of data and restrict the transmission of duplicate values.It is necessary to use a data de-duplication mechanism to reduce communication costs and storage overhead.Existing State of the art schemes suffer from computational overhead due to deterministic or random tree-based tags generation which further increases as the file size grows.This paper presents an efficient file-level de-duplication scheme(EFDS)where the cost of creating tags is reduced by employing a hash table with key-value pair for each block of the file.Further,an algorithm for hash table-based duplicate block identification and storage(HDBIS)is presented based on fingerprints that maintain a linked list of similar duplicate blocks on the same index.Hash tables normally have a consistent time complexity for lookup,generating,and deleting stored data regardless of the input size.The experiential results show that the proposed EFDS scheme performs better compared to its counterparts.展开更多
Towards line speed and accurateness on-line content popularity monitoring on Content Centric Networking(CCN) routers, we propose a three-stage scheme based on Bloom filters and hash tables for differentiated traffic. ...Towards line speed and accurateness on-line content popularity monitoring on Content Centric Networking(CCN) routers, we propose a three-stage scheme based on Bloom filters and hash tables for differentiated traffic. At the first stage, we decide whether to deliver the content to the next stage depending on traffic types. The second stage consisting of Standard Bloom filters(SBF) and Counting Bloom filters(CBF) identifies the popular content. Meanwhile, a scalable sliding time window based monitoring scheme for different traffic types is proposed to implement frequent and real-time updates by the change of popularities. Hash tables according with sliding window are used to record the popularity at the third stage. Simulation results reveal that this method reaches a 40 Gbps processing speed at lower error probability with less memory, and it is more sensitive to the change of popularity. Additionally, the architecture which can be implemented in CCN router is flexible and scalable.展开更多
In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and Lakshman and Stiliadis p...In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and Lakshman and Stiliadis proposing a 2-dimensional classification algorithm (LS algorithm). The core of algorithm consists of two parts: structure the non-collision hash function, which is constructed mainly based on destination/source port and protocol type field so that the hash function can avoid space explosion problem; introduce jumping table Trie-tree based LS algorithm in order to reduce time complexity. The test results show that the classification rate of NHJTTT algorithm is up to 1 million packets per second and the maximum memory consumed is 9 MB for 10 000 rules. Key words IP classification - lookup algorithm - trie-tree - non-collision hash - jumping table CLC number TN 393.06 Foundation item: Supported by the Chongqing of Posts and Telecommunications Younger Teacher Fundation (A2003-03).Biography: SHANG Feng-jun (1972-), male, Ph.D. candidate, lecture, research direction: the smart instrument and network.展开更多
A distributed processing system (DPS) contains many autonomous nodes, which contribute their own computing power. DPS is considered a unified logical structure, operating in a distributed manner;the processing tasks a...A distributed processing system (DPS) contains many autonomous nodes, which contribute their own computing power. DPS is considered a unified logical structure, operating in a distributed manner;the processing tasks are divided into fragments and assigned to various nodes for processing. That type of operation requires and involves a great deal of communication. We propose to use the decentralized approach, based on a distributed hash table, to reduce the communication overhead and remove the server unit, thus avoiding having a single point of failure in the system. This paper proposes a mathematical model and algorithms that are implemented in a dedicated experimental system. Using the decentralized approach, this study demonstrates the efficient operation of a decentralized system which results in a reduced energy emission.展开更多
目前,华容道算法是基于广度优先或深度优先搜索策略的改进,时间复杂为O(V+E)。为了提高效率,文章利用排列组合算法找到所有开局,再用广度优先算法找到开局的最优解,将所有开局及对应最优解保存在文件中。执行算法时最快可以以O(1)的时...目前,华容道算法是基于广度优先或深度优先搜索策略的改进,时间复杂为O(V+E)。为了提高效率,文章利用排列组合算法找到所有开局,再用广度优先算法找到开局的最优解,将所有开局及对应最优解保存在文件中。执行算法时最快可以以O(1)的时间复杂度找到最优解。理论分析和实验结果都表明,基于h as h表的求解华容道的算法能明显提高算法效率。展开更多
基金supported in part by Hankuk University of Foreign Studies’Research Fund for 2023 and in part by the National Research Foundation of Korea(NRF)grant funded by the Ministry of Science and ICT Korea No.2021R1F1A1045933.
文摘The Internet of Things(IoT)and cloud technologies have encouraged massive data storage at central repositories.Software-defined networks(SDN)support the processing of data and restrict the transmission of duplicate values.It is necessary to use a data de-duplication mechanism to reduce communication costs and storage overhead.Existing State of the art schemes suffer from computational overhead due to deterministic or random tree-based tags generation which further increases as the file size grows.This paper presents an efficient file-level de-duplication scheme(EFDS)where the cost of creating tags is reduced by employing a hash table with key-value pair for each block of the file.Further,an algorithm for hash table-based duplicate block identification and storage(HDBIS)is presented based on fingerprints that maintain a linked list of similar duplicate blocks on the same index.Hash tables normally have a consistent time complexity for lookup,generating,and deleting stored data regardless of the input size.The experiential results show that the proposed EFDS scheme performs better compared to its counterparts.
基金supported by the Foundation for Innovative Research Groups of the National Natural Science Foundation of China (Grant No.61521003)the National Basic Research Program of China (2012CB315901, 2013CB329104)+1 种基金the National Natural Science Foundation of China (Grant No. 61372121, 61309019, 61309020)the National HighTech Research & Development Program of China (Grant No. 2015AA016102, 2013AA013505)
文摘Towards line speed and accurateness on-line content popularity monitoring on Content Centric Networking(CCN) routers, we propose a three-stage scheme based on Bloom filters and hash tables for differentiated traffic. At the first stage, we decide whether to deliver the content to the next stage depending on traffic types. The second stage consisting of Standard Bloom filters(SBF) and Counting Bloom filters(CBF) identifies the popular content. Meanwhile, a scalable sliding time window based monitoring scheme for different traffic types is proposed to implement frequent and real-time updates by the change of popularities. Hash tables according with sliding window are used to record the popularity at the third stage. Simulation results reveal that this method reaches a 40 Gbps processing speed at lower error probability with less memory, and it is more sensitive to the change of popularity. Additionally, the architecture which can be implemented in CCN router is flexible and scalable.
文摘In order to classify packet, we propose a novel IP classification based the non-collision hash and jumping table trie-tree (NHJTTT) algorithm, which is based on noncollision hash Trie-tree and Lakshman and Stiliadis proposing a 2-dimensional classification algorithm (LS algorithm). The core of algorithm consists of two parts: structure the non-collision hash function, which is constructed mainly based on destination/source port and protocol type field so that the hash function can avoid space explosion problem; introduce jumping table Trie-tree based LS algorithm in order to reduce time complexity. The test results show that the classification rate of NHJTTT algorithm is up to 1 million packets per second and the maximum memory consumed is 9 MB for 10 000 rules. Key words IP classification - lookup algorithm - trie-tree - non-collision hash - jumping table CLC number TN 393.06 Foundation item: Supported by the Chongqing of Posts and Telecommunications Younger Teacher Fundation (A2003-03).Biography: SHANG Feng-jun (1972-), male, Ph.D. candidate, lecture, research direction: the smart instrument and network.
文摘A distributed processing system (DPS) contains many autonomous nodes, which contribute their own computing power. DPS is considered a unified logical structure, operating in a distributed manner;the processing tasks are divided into fragments and assigned to various nodes for processing. That type of operation requires and involves a great deal of communication. We propose to use the decentralized approach, based on a distributed hash table, to reduce the communication overhead and remove the server unit, thus avoiding having a single point of failure in the system. This paper proposes a mathematical model and algorithms that are implemented in a dedicated experimental system. Using the decentralized approach, this study demonstrates the efficient operation of a decentralized system which results in a reduced energy emission.
文摘目前,华容道算法是基于广度优先或深度优先搜索策略的改进,时间复杂为O(V+E)。为了提高效率,文章利用排列组合算法找到所有开局,再用广度优先算法找到开局的最优解,将所有开局及对应最优解保存在文件中。执行算法时最快可以以O(1)的时间复杂度找到最优解。理论分析和实验结果都表明,基于h as h表的求解华容道的算法能明显提高算法效率。
