专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US10129181B2 Controlling the reactive caching of wildcard rules for packet processing, such as flow processing in software-defined networks 有权
公开(公告)号：US10129181B2
公开(公告)日：2018-11-13
申请号：US14461372
申请日：2014-08-16
申请人： Yang Xu , H. Jonathan Chao
发明人： Yang Xu , H. Jonathan Chao
IPC分类号： H04L12/931 , H04L12/851 , H04L12/947 , H04L12/715 , H04L12/819
摘要： Software-Defined Networking (“SDN”) enables flexible flow control by caching policy rules at OpenFlow switches. Compared with exact-match rule caching, wildcard rule caching can better preserve the flow table space at switches. However, one of the challenges for wildcard rule caching is the dependency between rules, which is generated by caching wildcard rules overlapped in field space with different priorities. Failure to handle the rule dependency may lead to wrong matching decisions for newly arrived flows, or may introduce high storage overhead in flow table memory. A wildcard rule caching system, which may be used for SDN partitions the field space into logical structures called buckets, and caches buckets along with all the associated wildcard rules. Doing so resolves rule dependency while using control network bandwidth efficiently. Further, controller processing load and flow setup latency are reduced.

2. 发明授权

US09455996B2 Generating progressively a perfect hash data structure, such as a multi-dimensional perfect hash data structure, and using the generated data structure for high-speed string matching 有权
标题翻译：逐渐生成完美的散列数据结构，如多维完美散列数据结构，并使用生成的数据结构进行高速字符串匹配
公开(公告)号：US09455996B2
公开(公告)日：2016-09-27
申请号：US13409947
申请日：2012-03-01
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F17/30 , H04L29/06 , G06F21/55
CPC分类号： H04L63/1416 , G06F17/30946 , G06F17/30949 , G06F17/30958 , G06F17/30985 , G06F21/55 , H04L63/0245
摘要： A multi-dimensional perfect hash table construction technique is based on which the well-known AC automaton, and can be implemented by very compact perfect hash tables. The technique may place transitions, each from a source state to a destination state, of an automaton into a hash table to generate a perfect hash table by: (a) dividing the transitions into multiple independent sets according to their respective source states; (b) ordering the sets of transitions based on the number of transitions belonging to the set, thereby defining an order of the sets from largest to smallest; and (c) constructing a perfect hash table by, for each of the sets of transitions, in the order from largest to smallest, hashing the transitions of the set into the hashing table to generate a perfect hashing table.
摘要翻译：一种多维完美的散列表构建技术是基于众所周知的AC自动机，可以通过非常紧凑的完美散列表来实现。该技术可以将自动机的每个从源状态到目的地状态的转换放置到散列表中，以通过以下方式产生完美的散列表：（a）根据它们各自的源状态将转换分为多个独立集合; （b）基于属于集合的转移次数来排序转换集合，由此定义从最大到最小的集合的顺序; 并且（c）通过按照从最大到最小的顺序对于每个转换集合构建完美散列表，将集合的转换散列到散列表中以生成完美散列表。

3. 发明授权

US08264955B2 Internet protocol fast reroute for shared risk link group failure recovery 有权
标题翻译： Internet协议快速重新路由共享风险链路组故障恢复
公开(公告)号：US08264955B2
公开(公告)日：2012-09-11
申请号：US12483912
申请日：2009-06-12
申请人： H. Jonathan Chao , Kang Xi
发明人： H. Jonathan Chao , Kang Xi
IPC分类号： G01R31/08 , G06F11/00 , G08C15/00 , H04J1/16 , H04J3/14 , H04L1/00 , H04L12/26
CPC分类号： H04L41/0893 , H04L41/0668 , H04L41/12
摘要： A scheme to achieve fast recovery from SRLG failures in the IP layer is described. An exemplary scheme, called multi-section shortest path first (“MSSPF”), builds on the idea of IP Fast Reroute (“IPFRR”), guarantees 100% recovery of SRLG failures and causes no dead loops. Given a source node, a destination node, and a shared risk group failure on a next hop from the source node to the destination node, failure recovery information may be determined by (1) accepting a graph representing network topology information including the source node and the destination node, (2) determining a node which is able to reach the destination node using a route which does not include the source node, wherein a path from the source node to the determined node is not affected by the shared risk group failure, and (3) storing, in association with the shared risk group failure, both (i) a network address associated with the determined node and (ii) an alternative output port of the source node using the shortest path from the source node to the determined node.
摘要翻译：描述了实现IP层中SRLG故障快速恢复的方案。基于IP快速重路由（“IPFRR”）的思想，建立了一个称为多节段最短路径（“MSSPF”）的示范方案，保证了SRLG故障的100％恢复，并且不会导致死循环。给定来自源节点到目的地节点的下一跳的源节点，目的地节点和共享风险组故障，故障恢复信息可以通过以下方式来确定：（1）接受表示包括源节点和目的地节点，（2）使用不包括源节点的路由来确定能够到达目的地节点的节点，其中从源节点到确定的节点的路径不受共享风险组故障的影响，和（3）与共享风险组故障相关联地存储（i）与所确定的节点相关联的网络地址和（ii）使用从源节点到确定的最短路径的源节点的备选输出端口节点。

4. 发明授权

US07805460B2 Generating a hierarchical data structure associated with a plurality of known arbitrary-length bit strings used for detecting whether an arbitrary-length bit string input matches one of a plurality of known arbitrary-length bit string 有权
标题翻译：生成与用于检测任意长度位串输入是否匹配多个已知任意长度位串中的一个的多个已知任意长度位串相关联的分层数据结构
公开(公告)号：US07805460B2
公开(公告)日：2010-09-28
申请号：US11978216
申请日：2007-10-26
申请人： Nabi Sertac Artan , H. Jonathan Chao
发明人： Nabi Sertac Artan , H. Jonathan Chao
IPC分类号： G06F7/00 , G06F17/00
CPC分类号： H04L63/1416 , G06F21/564
摘要： Generating and using a high-speed, scalable, and easily updateable data structure are described. The proposed data structure provides minimal perfect hashing functionality while intrinsically supporting low-cost set-membership queries. In other words, in some embodiments, it provides at most one match candidate in a set of known arbitrary-length bit strings that is used to match the query.
摘要翻译：描述生成和使用高速，可扩展和易于更新的数据结构。提出的数据结构提供最小的完美散列功能，同时本质上支持低成本集成员查询。换句话说，在一些实施例中，它在用于匹配查询的一组已知的任意长度位串中提供至多一个匹配候选。

5. 发明授权

US08938454B2 Using a tunable finite automaton for regular expression matching 有权
标题翻译：使用可调谐有限自动机进行正则表达式匹配
公开(公告)号：US08938454B2
公开(公告)日：2015-01-20
申请号：US13648438
申请日：2012-10-10
申请人： H. Jonathan Chao , Yang Xu
发明人： H. Jonathan Chao , Yang Xu
IPC分类号： G06F7/00 , G06F17/30
CPC分类号： G06F17/30985
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

6. 发明申请

US20140101157A1 ENCODING NON-DERMINISTIC FINITE AUTOMATON STATES EFFICIENTLY IN A MANNER THAT PERMITS SIMPLE AND FAST UNION OPERATIONS 有权
标题翻译：在简单和快速的联合运行的人手中有效地编码非限制性有机自动机
公开(公告)号：US20140101157A1
公开(公告)日：2014-04-10
申请号：US13648452
申请日：2012-10-10
申请人： H. Jonathan CHAO , Yang XU
发明人： H. Jonathan CHAO , Yang XU
IPC分类号： G06F17/30
CPC分类号： H04L43/028 , H04L63/1416
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

7. 发明申请

US20140101155A1 GENERATING A TUNABLE FINITE AUTOMATON FOR REGULAR EXPRESSION MATCHING 有权
标题翻译：生成用于常规表达匹配的有限自动调节器（TUNNABLE FINITE AUTOMATON FOR REGULAR EXPRESSION MATCHING）
公开(公告)号：US20140101155A1
公开(公告)日：2014-04-10
申请号：US13648432
申请日：2012-10-10
申请人： H. Jonathan CHAO , Yang Xu
发明人： H. Jonathan CHAO , Yang Xu
IPC分类号： G06F17/30
CPC分类号： H04L41/16 , H04L43/028
摘要： Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significant reductions in the number of states and memory space.
摘要翻译：确定性有限自动机（DFA）和非确定性有限自动机（NFAs）是网络入侵检测系统（NIDS）中使用的两种典型自动机。虽然它们都执行正则表达式匹配，但它们具有非常不同的性能和内存使用属性。 DFA提供快速和确定性的匹配性能，但遭受着名的国家爆炸问题。 NFAs是紧凑的，但它们的匹配性能是不可预测的，没有最坏的情况保证。描述了称为可调谐有限自动机（TFA）的正则表达式的新自动机表示。 TFAs解决了DFA的状态爆炸问题和NFAs不可预测的性能问题。与仅具有一个活动状态的DFA不同，TFA允许多个并发活动状态。因此，TFA跟踪匹配状态所需的状态总数远远小于DFA所要求的状态总数。与NFA不同，TFA保证并行活动状态的数量受绑定因子b的约束，根据应用速度和存储的需要，可以在构建TFA期间进行调整。 TFA可以显着减少状态和记忆空间的数量。

8. 发明申请

US20120206279A1 DETECTING WHETHER AN ARBITRARY-LENGTH BIT STRING INPUT MATCHES ONE OF A PLURALITY OF KNOWN ARBITRARY-LENGTH BIT STRINGS USING A HIERARCHICAL DATA STRUCTURE 有权
标题翻译：检测无论是长度字符串输入匹配使用分层数据结构的多个已知的仲裁长度位串中的一个
公开(公告)号：US20120206279A1
公开(公告)日：2012-08-16
申请号：US13451877
申请日：2012-04-20
申请人： Nabi Sertac ARTAN , H. Jonathan Chao
发明人： Nabi Sertac ARTAN , H. Jonathan Chao
IPC分类号： H03M7/00
CPC分类号： G06F21/564 , G06F17/30949
摘要： Generating and using a high-speed, scalable, and easily updateable data structure are described. The proposed data structure provides minimal perfect hashing functionality while intrinsically supporting low-cost set-membership queries. In other words, in some embodiments, it provides at most one match candidate in a set of known arbitrary-length bit strings that is used to match the query.
摘要翻译：描述生成和使用高速，可扩展和易于更新的数据结构。提出的数据结构提供最小的完美散列功能，同时本质上支持低成本集成员查询。换句话说，在一些实施例中，它在用于匹配查询的一组已知的任意长度位串中提供至多一个匹配候选。

9. 发明申请

US20100194608A1 GENERATING A BOUNDARY HASH-BASED HIERARCHICAL DATA STRUCTURE ASSOCIATED WITH A PLURALITY OF KNOWN ARBITRARY-LENGTH BIT STRINGS AND USING THE GENERATED HIERARCHICAL DATA STRUCTURE FOR DETECTING WHETHER AN ARBITRARY-LENGTH BIT STRING INPUT MATCHES ONE OF A PLURALITY OF KNOWN ARBITRARY-LENGTH BIT STRINGS 有权
标题翻译：产生与多个已知仲裁长度位串相关联的基于边界的基于HASH的分层数据结构，并使用生成的分层数据结构来检测无论是长度比特字符串输入匹配多个已知仲裁长度位串中的一个
公开(公告)号：US20100194608A1
公开(公告)日：2010-08-05
申请号：US12366503
申请日：2009-02-05
申请人： Sertac ARTAN , H. Jonathan CHAO
发明人： Sertac ARTAN , H. Jonathan CHAO
IPC分类号： H03M7/00
CPC分类号： G06F17/30985 , H04L9/0643 , H04L2209/60
摘要： A high-speed, space-efficient, scalable and easily updateable data boundary hash-based structure is generated and used. The proposed boundary hash-based data structure provides minimal perfect hashing functionality while intrinsically supporting low-cost set-membership queries. In other words, in some embodiments, it provides at most one match candidate in a set of known arbitrary-length bit strings that is used to match the query.
摘要翻译：生成并使用高速，空间高效，可扩展和易于更新的数据边界基于散列的结构。所提出的基于边界散列的数据结构提供了最小的完美散列功能，同时本质上支持低成本集成员查询。换句话说，在一些实施例中，它在用于匹配查询的一组已知的任意长度位串中提供至多一个匹配候选。

10. 发明授权

US07415020B2 Packet classification apparatus and method using field level tries 失效
标题翻译：数据包分类设备和方法使用字段级别尝试
公开(公告)号：US07415020B2
公开(公告)日：2008-08-19
申请号：US10787298
申请日：2004-02-27
申请人： Jinoo Joung , Woo-jong Park , Guansong Zhang , H. Jonathan Chao
发明人： Jinoo Joung , Woo-jong Park , Guansong Zhang , H. Jonathan Chao
IPC分类号： H04L12/28
CPC分类号： H04L45/742 , H04L45/02 , H04L47/32 , Y10S707/99933 , Y10S707/99942 , Y10S707/99943
摘要： A packet classification apparatus and method using field level tries includes a main processing part for generating and maintaining the field level tries, which organize a multi-field packet by field in a hierarchical structure for classifications; and classification engines, each of which is provided with a first classification part for performing queries and updates and processing a prefix lookup represented by an IP source/destination address lookup, and a second classification part for proceeding with classifications by corresponding field based on a result of the first classification part in order to process a range lookup belonging to the result. Accordingly, tries in the unit of a field are developed so that packet classifications for high-speed networking with excellent query performance are secured, and wherein approximately a half-million classifier rules can be processed.
摘要翻译：使用场级尝试的分组分类装置和方法包括用于生成和维护场级尝试的主处理部分，其以用于分类的分级结构逐场地组织多字段; 和分类引擎，每个分类引擎具有用于执行查询和更新并处理由IP源/目的地地址查找表示的前缀查找的第一分类部分和用于基于结果对应的字段进行分类的第二分类部分的第一分类部分，以处理属于结果的范围查找。因此，开发出领域单元的尝试，从而确保了用于具有优异查询性能的高速网络的分组分类，并且其中可以处理大约50万分类器规则。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式