New York University

Future Wei Technologies, Inc.

H Jonathan Chao

Yang Xu

Kang Xi

Nabi Sertac Artan

Sertac Artan

Wu Chou

Shivendra S Panwar

Min Luo

Yanming Shen

Junjie Zhang

Rihua Wei

Kuan-yin Chen

Collisions and/or congestion at output ports of switches can be relieved by: (a) receiving a packet; (b) extracting destination information from the packet; (c) looking up, using the extracted destination information, an output port; (d) determining whether to redirect the packet based on a congestion level of a buffer of the output port; (f) when determining to redirect the packet, (1) dispatching the packet to a dedicated reservoir port of the switch, wherein the reservoir port enforces a queue discipline, (2) receiving, by a reservoir, the redirected packet, (3) temporarily buffering, in an internal queue of the reservoir, the redirected packet, and (4) sending the temporarily buffered packet back to the switch. Otherwise, the packet is dispatched to the output port of the switch. Packets sent back to the switch are paced to relieve collisions and congestion at the switch output port.

Methods and apparatus for alleviating congestion at a switch, such as a shallow buffered switch

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.

Controlling the reactive caching of wildcard rules for packet processing, such as flow processing in software-defined networks

A controller having an application optimally routing traffic to balance fluctuating traffic loads in a SDN network. A processor is configured to control the data plane to establish routing through the plurality of routers, wherein the processor is configured to establish hybrid routing comprising both explicit routing and destination-based routing. The processor utilizes a set of traffic matrices representing the fluctuating traffic load over time. A destination-based multi-path routing algorithm is configured to improve load balancing of the traffic load based on the set of representative traffic matrices. The destination based routing is calculated based on linear programming. The processor comprises a traffic categorization algorithm configured to identify a set of key flows, wherein the processor is configured to explicitly route the set of key flows. The processor is configured such that the set of key flows consume a small fraction of a ternary content-addressable memory (TCAM), and such that the set of key flows provide a routing decision for a large portion of the traffic load.

Apparatus for hybrid routing in SDN networks to avoid congestion and achieve good load balancing under fluctuating traffic load

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.

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

The problem of providing an efficient physical implementation of a (first) classifier defined by a first rule set, at least a part of which first classifier having a sparse distribution in Boolean space, is solved by (1) converting the first classifier, having a corresponding Boolean space, into a second classifier, wherein the second classifier has a corresponding Boolean space which is not semantically equivalent to the Boolean space corresponding to the first classifier, and wherein the second classifier is defined by a second set of rules which is smaller than the first set of rules defining the first classifier; and (2) defining a bit string transformation which transforms a first bit string into a second bit string, wherein applying the first bit string to the first classifier is equivalent to applying the second bit string to the second classifier. In at least some example embodiments, the first bit string includes packet header information. In at least some example embodiments, the second classifier is implemented on a TCAM. In at least some example embodiments, the bit string transformation is implemented on an FPGA.

Finding nonequivalent classifiers to reduce ternary content addressable memory (TCAM) usage

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.

Generating a tunable finite automaton for regular expression matching

Using a tunable finite automaton for regular expression matching

Regrouping non-derministic finite automaton active states to minimize distinct subsets

Hybrid security architecture (HSA) provides a platform for middlebox traversal in the network. The HSA decouples the middlebox control from network forwarding. More specifically, such embodiments may receive a data packet having a packet header including an Ethernet header identifying source and destination addresses in the network. A traffic type of the data packet is determined. Then, layer-2 forwarding information, which encodes a set of non-forwarding network service provider middleboxes in the network to be traversed by the data packet, is determined based on the traffic type. The layer-2 forwarding information is inserted into the Ethernet header and the data packet is forwarded into the network. The data packet will then traverse, according to the layer-2 forwarding information, a sequence of the middleboxes in the network, wherein at least one non-forwarding network service will be provided by each of the middleboxes to the data packet in a sequence.

Dynamically provisioning middleboxes

Load balancing is performed in a network using flow-based routing. For example, upon detection of a big flow, one or more alternative paths from a source host to a destination host in the network may be discovered by probing the network and generating, for each of the one or more alternative paths, an association of the packet header information of the big flow to an alternative path discovered using results of probing the network. Upon congestion in a path currently being used by the big flow, an alternative path that is not congested is selected from the one or more discovered alternative paths. The packet header information of the big flow is altered using the generated association of the packet header information to the selected alternative path such that the big flow will be transmitted using the selected alternative path.

Balancing load in a network, such as a data center network, using flow based routing

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.

Detecting whether an arbitrary-length bit string input matches one of a plurality of known arbitrary-length bit strings using a hierarchical data structure

Encoding non-derministic finite automation states efficiently in a manner that permits simple and fast union operations

A representation of a new rule, defined as a set of a new transition(s), is inserted into a perfect hash table which includes previously placed transitions to generate an updated perfect hash table. This may be done by, for each new transition: (a) hashing the new transition; and (b) if there is no conflict, inserting the hashed new transition into the table. If, however, the hashed new transition conflicts with any of the previously placed transitions, either (A) any transitions of the state associated with the conflicting transition are removed from the table, the hashed new transition is placed into the table, and the removed transitions are re-placed into the table, or (B) any previously placed transitions of the state associated with the new transition are removed, and the transitions of the state associated with the new transition are re-placed into the table.

Updating a perfect hash data structure, such as a multi-dimensional perfect hash data structure, used for high-speed string matching

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.

Internet protocol fast reroute for shared risk link group failure recovery

Generating and using a high-speed, scalable and easily updateable data structures 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.

Generating a log-log hash-based 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 strings

Growing community of inventors

Holmdel, NJ, United States of America

H Jonathan Chao