Broadcom Corporation

Nick Horgan

Daniel L Rosenband

Dominic Li

Kathryn Russell

Disclosed method, system and computer readable storage medium embodiments for providing hardware-efficient universal hashing functions include performing a first hash function on a received input key or a bit sequence derived from the received input key to generate a hashed input key, selecting a plurality of input key portions from the hashed input key, accessing, a respective permutation table for each of the input key portions from a group of permutation tables to generate a permuted key portion, and combining at least the generated permuted key portions to form a hash value.

Method and system for a hardware-efficient universal hash function

Methods, systems, and computer program products are provided for efficient packet replication. In an embodiment, a packet is stored as a linked list of at least one page. Replicating the packet comprises creating a new header page and linking it to the first page of the linked list. Each replica packet may be transmitted independently and concurrently. In an embodiment where packets are stored in queues, each replica packet may be dequeued for transmission independently and concurrently. After all references to a page have been transmitted (or dequeued), the page may be freed.

Efficient packet replication

A method for classifying an incoming packet. The method includes maintaining a database associated with patterns of fields, where the fields can be network addresses. The database can be developed by mapping each pattern to a unique numeric identifier. The number of unique numeric identifiers is equal to the number of patterns, and the size of each unique numeric identifier is substantially smaller than the field of each pattern. The database can be further developed by determining a range of one or more of the unique numeric identifiers to be associated with each pattern. The range for each pattern can be bounded by a minimum unique numeric identifier and a maximum unique numeric identifier. The method also includes using a field of the incoming packet to determine an associated identifier for that field, where the associated identifier is equal to one of the unique numeric identifiers. The associated identifier can then be matched with one or more of the ranges for the patterns, and the method can then determine how to process the incoming packet.

Growing community of inventors

Waltham, MA, United States of America

Nick Horgan