Back to results
US 7,733,888 B2Granted
Pointer allocation by prime numbers
AssigneeAlcatel-Lucent USA Inc.
InventorsGregory S. Mathews, Sanjay Jain, Jorge Alejandro Aguilar, Avinash Mani
Life of this patent
Estimating the term…
Abstract
A prime number based pointer allocation technique. A packet-forwarding system incorporating the technique stores cells of a packet in packet memory, according to allocated pointers that have a fixed correspondence to locations in the packet memory. Each packet input interface of an ingress module has a memory parameter counter that is incremented by a different prime number each time a memory pointer is allocated to that input interface. The memory parameter counter includes a memory interface portion and a memory bank portion that correspond to the memory interfaces and memory banks of a packet memory with which the memory pointers are associated.
Claims16
A method for configuring a system to assign pointers to packets, comprising:
- configuring a pointer memory of an ingress module of a traffic forwarding system to contain a linked list of available pointers with a head and a tail and a list of unavailable pointers;
- sorting available pointers by memory interface parameters and memory bank parameters associated with said packet memory;
- providing a plurality of pointer buffer fields in a memory pointers buffer, where said pointer buffer fields comprises a plurality of sub-buffers, wherein each sorted pointer is placed into one of the sub-buffers corresponding to a memory parameter of said sorted pointer comprising a memory interface parameter and a memory bank parameter;
- associating respective prime number values with said plurality of pointer buffer fields, wherein said respective prime number values are unique;
- and
- configuring a plurality of input interfaces to:
- obtain a pointer of said packet memory from a sub-buffer of said plurality of pointer buffers fields in accordance with a memory parameter field of a prime number memory parameter increment engine configured as a counter and comprising two values as a memory parameter field sequence, where a first value is contained in a memory interface field register and a second value is contained in a memory bank field register;
- store a received packet in a packet memory in accordance with said pointer;
- and
- increment said counter by adding a unique prime number to said two values of said counter to yield a new memory parameter field sequence.
7 more elements
A method for forwarding packets, comprising:
- assigning a first pointer from an available pool of pointers to a first cell in accordance with a first memory parameter field of a prime number memory parameter increment engine, wherein the prime number memory parameter increment engine is located within an ingress module of a traffic forwarding system;
- moving said first pointer in a pointer memory from a linked list of available pointers with a head and a tail to a list of unavailable pointers;
- storing the first cell in memory according to said first pointer;
- incrementing said first memory parameter field by a first prime number;
- and
- moving said first pointer in said pointer memory from said list of unavailable pointers to said linked list of available pointers, wherein said first pointer is enqueued at said tail.
3 more elements
A packet based-traffic forwarding system that allocates pointers to memory blocks, comprising:
- packet memory;
- pointer memory configured to contain a linked list of available pointers with a head and a tail and a list of unavailable pointers;
- a sorting buffer configured to receive and to sort available pointers of said list of available pointers in accordance with memory parameters, wherein said memory parameters include memory interface parameters and memory bank parameters associated with said packet memory;
- a pointer buffer configured to contain the sorted pointers, where said pointer buffer comprises a plurality of sub-buffers, wherein each sorted pointer is placed into one of said sub-buffers corresponding to a memory parameter of said sorted pointer comprising a memory interface parameter and a memory bank parameter;
- one or more input interfaces configured to receive cells for storage in said packet memory, said one or more input interfaces including:
- a prime number memory parameter increment engine configured to increment a memory parameter counter by a prime number, said prime number memory parameter increment engine comprising
- a prime increment field register containing the value of a unique prime number,
- a memory parameter field configured as said counter and comprising two values as a memory parameter field sequence, where a first value is contained in a memory interface field register and a second value is contained in a memory bank field register, and
- an increment engine configured to increment said counter by adding said unique prime number to said two values of said counter to yield a new memory parameter field sequence with each increment;
- a pointer acquisition engine configured to select and remove pointers from a sub- buffer, to receive the selected pointers, and to associate the received pointers with said cells, where each said selection is made in accordance with said new memory parameter field of said prime number memory parameter increment engine;
- and
- an output interface configured to forward said cells from said packet memory and return said associated pointers to said linked list of available pointers, wherein said associated pointers are enqueued at said tail.
9 more elements
Dependencies are inferred from the claim text.