Riverstone Networks, Inc.

Lucent Technologies Inc.

Balakrishnan Ramakrishnan

Marc A Schaub

Kumar B Mehta

Distributing packets from an input link to multiple output links involves categorizing each incoming packet, selecting a mapping algorithm based on the packet category, and using the selected mapping algorithm for each packet to determine an output link for the respective packet. If packets are from a category that requires the order of the packets to be maintained, then the selected mapping algorithm causes packets from the same set of packets to be distributed to the same output link. If packets are from a category that does not require the order of the packets to be maintained, then the selected mapping algorithm can cause packets to be distributed more evenly among the multiple output links. Hashing can be used to distribute in-order packets from the same set to the same output link. Load balancing and round-robin distribution can be used to distribute out-of-order packets more evenly across the output links.

Flexible application of mapping algorithms within a packet distributor

A pool of integers is managed by dividing the pool of integers into groups and initializing, in memory, doubly linked lists related to the groups on an as needed basis in response to requests to allocate integers. If an initialized group of integers no longer includes any allocated integers, the doubly linked list related to the group is deleted from memory. Memory locations of the group-specific doubly linked lists are identified by a hash table that includes a unique hash table pointer for each one of the groups. Each element of the doubly linked list includes a next pointer for identifying a next element and a previous pointer for identifying a previous element. A specific free integer can be allocated in an order of one, O(1), operation by indexing into the linked list and utilizing the next and previous pointers of the linked list element to remove the linked list element from the linked list.

Method, system, and computer program product for managing a re-usable resource with linked list groups

Managing a reusable resource, such as a pool of integers, involves a doubly linked list of elements that represents free integers in an integer pool. Each element of the doubly linked list includes a next pointer for identifying a next element and a previous pointer for identifying a previous element. A specific free integer can be allocated from the integer pool in an order of one, O(1), operation by indexing into the linked list and then utilizing the next and previous pointers of the linked list element to remove the linked list element from the linked list. The desired element is removed by adjusting the next pointer of the previous element and the previous pointer of the next linked list element. A non-specific free integer can be allocated from the integer pool in an O(1) operation through a head element that identifies a next free integer in the linked list.

Method, system, and computer program product for managing a re-usable resource

Updating a content addressable memory (CAM) involves identifying a new entry that is to be added to the CAM, identifying a free location in the CAM that is the fewest number of prefix levels away from the prefix level of the new entry, moving an existing CAM entry into the free location to create a newly freed location that is a fewer number of prefix levels away from the prefix level of the new entry, repeating the move process until a free location is created at the desired prefix level of the new entry, and then adding the new entry into the newly freed location. The specific algorithm for moving entries to free a location in the desired prefix level is a function of whether the prefix level of the first free location is above or below the prefix level of the new entry.

Growing community of inventors

Sunnyvale, CA, United States of America

Balakrishnan Ramakrishnan