Multi-resolution tree for longest match address lookups
First Claim
Patent Images
1. A method for forwarding packets, comprising the steps of:
- a) receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by;
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
f) repeating steps b) to e) until there is no pointer associated with said index;
retrieving the decision value associated with said longest prefix; and
forwarding said packet in according with said decision value.
4 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for forwarding packets in a network is described. A routing table is constructed using p-structures. An address for a packet is received. The address is matched with a longest prefix stored in the routing table. A decision value associated with the longest prefix is retrieved. The packet is forwarded in accordance with the decision value.
102 Citations
55 Claims
-
1. A method for forwarding packets, comprising the steps of:
-
a) receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by;
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
f) repeating steps b) to e) until there is no pointer associated with said index;
retrieving the decision value associated with said longest prefix; and
forwarding said packet in according with said decision value. - View Dependent Claims (2)
storing said address in a register;
retrieving a mask associated with said current partition member;
masking said address with said partition mask; and
shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
3. A method for constructing a routing table, comprising the steps of:
-
receiving a prefix and a decision value associated with said prefix, wherein said prefix is a bit sequence for a binary number and inserting said decision value into all entries of at least one p-structure indexed by the set {circumflex over (B)}a;
={λ
ε
N;
λ
<
2a{circumflex over ( )}λ
≧
0}, where B, b, a and β
are positive integers, and wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet defining the decision value, and the second part containing a pointer to another p-structure.
-
-
4. A method for constructing a routing table, comprising the steps of:
-
a) setting a current partition member to a first partition member, and a bit counter to a bit size for said first partition member;
b) receiving a prefix and a decision value associated with said prefix, said prefix comprising an address and a masklength;
c) translating said address into an index for said current partition member, and a subaddress of said masklength;
d) comparing said masklength to said bit counter to form a comparison;
e) inserting said decision value for all entries in a p-structure corresponding to said subaddress, and all bit combinations for bits more significant than the bits for subaddress and less significant for said bit size for the current partition member in accordance with said comparison;
f) setting said current partition member to a next partition member in accordance with said comparison;
g) incrementing said bit counter by adding a bit size for said next partition member to said bit counter; and
h) repeating steps c) to g) until there are no more partition members or bit counter becomes greater than the masklength. - View Dependent Claims (5, 6)
storing said address in a register;
retrieving a mask associated with said current partition member;
masking said address with said partition mask; and
shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
6. The method of claim 4, wherein said step of translating said address into a subaddress of said masklength comprises the steps of:
-
storing said address in a register;
retrieving a mask associated with said prefix;
masking said address with said mask; and
shifting said masked address to the right in accordance with a shift value associated with said prefix.
-
-
7. A method for updating a routing table comprised of p-structures utilized by a forwarding device, comprising the steps of:
-
building a maintenance routing table having a m-structure corresponding to each p-structure for the routing table, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure;
receiving an instruction to update said maintenance routing table by performing one of a group comprising adding, deleting and modifying a prefix;
updating said maintenance routing table in accordance with said instruction; and
replicating said maintenance routing table to said routing table used by the forwarding device. - View Dependent Claims (8, 9, 10)
-
-
11. A method for forwarding packets, comprising the steps of:
-
constructing a routing table utilizing p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure;
receiving an address for a packet;
matching said address with a longest prefix stored in said routing table by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at;
retrieving the decision value from the last p-structure associated with said longest prefix; and
forwarding said packet in accordance with said decision value.
-
-
12. An apparatus for forwarding packets, comprising:
-
means for receiving an address for a packet;
means for matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure, said matching means comprising;
a) means for initializing a current partition member to a first partition member;
b) means for translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) means for storing a decision value associated with said index;
d) means for determining whether a pointer is associated with said index;
e) means for setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
g) means for utilizing means b) to e) until there is no pointer associated with said index;
means for retrieving a decision value associated with said longest prefix; and
means for forwarding said packet in accordance with said decision value. - View Dependent Claims (13)
means for storing said address in a register;
means for retrieving a mask associated with said current partition member;
means for masking said address with said partition mask; and
means for shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
14. An apparatus for constructing a routing table, comprising:
-
means for receiving a prefix and a decision value associated with said prefix, wherein said prefix is defined as a bit sequence for a binary number and means for inserting said decision value into all entries of at least one p-structure indexed by the set {circumflex over (B)}a;
={λ
ε
N;
λ
<
2a{circumflex over ( )}λ
≧
0}, where B, b, a and β
are positive integers, and wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet defining the decision value, and the second part containing a pointer to another p-structure.
-
-
15. An apparatus for constructing a routing table, comprising:
-
a) means for setting a current partition member to a first partition member, and a bit counter to a bit size for said first partition member;
b) means for receiving a prefix and a decision value associated with said prefix, said prefix comprising an address and a masklength;
c) means for translating said address into an index for said current partition member, and a subaddress of said masklength;
d) means for comparing said masklength to said bit counter to form a comparison;
e) means for inserting said decision value for all entries in a p-structure corresponding to said subaddress, and all bit combinations for bits more significant than the bits for subaddress and less significant for said bit size for the current partition member in accordance with said comparison;
f) means for setting said current partition member to a next partition member in accordance with said comparison;
g) means for incrementing said bit counter by adding a bit size for said next partition member to said bit counter; and
h) means for utilizing means c) to g) until there are no more partition members or bit counter becomes greater than the masklength. - View Dependent Claims (16, 17)
means for storing said address in a register;
means for retrieving a mask associated with said current partition member;
means for masking said address with said partition mask; and
means for shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
17. The apparatus of claim 15, wherein said means for translating said address into a subaddress of said masklength comprises:
-
means for storing said address in a register;
means for retrieving a mask associated with said prefix;
means for masking said address with said mask; and
means for shifting said masked address to the right in accordance with a shift value associated with said prefix.
-
-
18. An apparatus for updating a routing table comprised of p-structures utilized by a forwarding device, comprising:
-
means for building a maintenance routing table having a m-structure corresponding to each p-structure for the routing table, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure;
means for receiving an instruction to update said maintenance routing table by performing one of a group comprising adding, deleting and modifying a prefix;
means for updating said maintenance routing table in accordance with said instruction; and
means for replicating said maintenance routing table to said routing table used by the forwarding device. - View Dependent Claims (19, 20, 21)
-
-
22. An apparatus for forwarding packets, comprising:
-
means for constructing a routing table utilizing p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure;
means for receiving an address for a packet;
means for matching said address with a longest prefix stored in said routing table by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at;
means for retrieving the decision value from the last p-structure associated with said longest prefix; and
means for forwarding said packet in accordance with said decision value.
-
-
23. A computer for forwarding packets, comprising:
-
a memory containing a forwarding decision program having functions for matching an address for a packet with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at, and forwarding said packet using the decision value from the last p-structure associated with said prefix; and
a processor for executing the forwarding decision program.
-
-
24. A computer for forwarding packets, comprising:
-
a memory containing a routing table constructing program having functions for constructing a routing table using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure with at least three p-structures linked together by pointers; and
a processor for executing the routing table constructing program.
-
-
25. A computer readable medium whose contents cause a computer system to forward a packet, the computer system having a forwarding decision program with functions for forwarding, by performing the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by;
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
f) repeating steps b) to e) until there is no pointer associated with said index;
retrieving a decision value associated with said longest prefix; and
forwarding said packet in accordance with said decision value. - View Dependent Claims (26)
storing said address in a register;
retrieving a mask associated with said current partition member;
masking said address with said partition mask; and
shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
27. A computer readable medium whose contents cause a computer system to construct a routing table, the computer system having a routing table constructing program with functions for constructing, by performing the steps of:
-
a) setting a current partition member to a first partition member, and a bit counter to a bit size for said first partition member;
b) receiving a prefix and a decision value associated with said prefix, said prefix comprising an address and a masklength;
c) translating said address into an index for said current partition member, and a subaddress of said masklength;
d) comparing said masklength to said bit counter to form a comparison;
e) inserting said decision value for all entries in a p-structure corresponding to said subaddress, and all bit combinations for bits more significant than the bits for subaddress and less significant for said bit size for the current partition member in accordance with said comparison;
f) setting said current partition member to a next partition member in accordance with said comparison;
g) incrementing said bit counter by adding a bit size for said next partition member to said bit counter;
h) repeating steps c) to g) until there are no more partition members or bit counter becomes greater than the masklength. - View Dependent Claims (28, 29)
storing said address in a register;
retrieving a mask associated with said current partition member;
masking said address with said partition mask; and
shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
29. The computer readable medium of claim 27, wherein said step of translating said address into a subaddress of said masklength comprises the steps of:
-
storing said address in a register;
retrieving a mask associated with said prefix;
masking said address with said mask; and
shifting said masked address to the right in accordance with a shift value associated with said prefix.
-
-
30. A method for locating a decision value, comprising the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by;
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
f) repeating steps b) to e) until there is no pointer associated with said index; and
retrieving the decision value associated with said longest prefix. - View Dependent Claims (31)
storing said address in a register;
retrieving a mask associated with said current partition member;
masking said address with said partition mask; and
shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
32. An apparatus for locating a decision value, comprising the steps of:
-
means for receiving an address for a packet;
means for matching said address with a longest prefix stored in a table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure, said matching means comprising;
a) means for initializing a current partition member to a first partition member;
b) means for translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) means for storing a decision value associated with said index;
d) means for determining whether a pointer is associated with said index;
e) means for setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
f) means for utilizing means b) to e) until there is no pointer associated with said index; and
means for retrieving the decision value associated with said longest prefix. - View Dependent Claims (33)
means for storing said address in a register;
means for retrieving a mask associated with said current partition member;
means for masking said address with said partition mask; and
means for shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
34. A computer readable medium whose contents cause a computer system to locate a decision value in a routing table, the computer system having a forwarding decision program with functions for locating, by performing the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by;
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index;
f) repeating steps b) to e) until there is no pointer associated with said index; and
retrieving the decision value associated with said longest prefix. - View Dependent Claims (35)
storing said address in a register;
retrieving a mask associated with said current partition member;
masking said address with said partition mask; and
shifting said masked address to the right in accordance with a shift value associated with said current partition member.
-
-
36. A computer for locating a decision value, comprising:
-
a memory containing a forwarding decision program having functions for matching an address for a packet with a longest prefix stored in a table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at, and locating the decision value from the last p-structure associated with said prefix; and
a processor for executing the forwarding decision program.
-
-
37. A look up device, comprising:
-
a processor;
a memory coupled to said processor, said memory containing a table of prefixes and decision values organized into p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure; and
a forwarding decision module coupled to said processor and said memory, said forwarding decision module matching said address with a longest prefix stored in said table by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at and locating the decision value from the last p-structure associated with said prefix.
-
-
38. A routing table constructing device, comprising:
-
a processor;
a memory coupled to said processor;
a routing table constructing module coupled to said processor and said memory, said routing table constructing module constructing a table of prefixes and decision values organized into p-structures and storing said table into said memory, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure. - View Dependent Claims (39)
-
-
40. A computer for locating a decision value, comprising:
-
a cache memory containing a table comprised of prefixes and decision values organized as a p-structure tree, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure, with a holding value used to mark decision points for that portion of said tree that does not fit within said cache memory;
a memory containing a forwarding decision program having functions for matching an address for a packet with a longest prefix stored in said table by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at and locating the decision value from the last p-structure associated with said prefix; and
a processor for executing the forwarding decision program.
-
-
41. A look up device, comprising:
-
a plurality of processors;
a memory coupled to each processor, with each memory containing part of a table of prefixes and decision values organized into p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure; and
a forwarding decision module coupled to said processors and each of said memory, said forwarding decision module utilizing said processors in parallel to match said address with a longest prefix stored in said table by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at and locating the decision value from the last p-structure associated with said prefix. - View Dependent Claims (42, 43)
-
-
44. A method for forwarding packets, comprising the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at;
retrieving the decision value from the last p-structure associated with said longest prefix; and
forwarding said packet in according with said decision value. - View Dependent Claims (45)
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index; and
f) repeating steps b) to e) until there is no pointer associated with said index.
-
-
46. An apparatus for forwarding packets, comprising:
-
means for receiving an address for a packet;
means for matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at;
means for retrieving the decision value from the last p-structure associated with said longest prefix; and
means for forwarding said packet in accordance with said decision value. - View Dependent Claims (47)
a) means for initializing a current partition member to a first partition member;
b) means for translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) means for storing a decision value associated with said index;
d) means for determining whether a pointer is associated with said index;
e) means for setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index; and
f) means for utilizing means b) to e) until there is no pointer associated with said index.
-
-
48. A computer readable medium whose contents cause a computer system to forward a packet, the computer system having a forwarding decision program with functions for forwarding, by performing the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at;
retrieving the decision value from the last p-structure associated with said longest prefix; and
forwarding said packet in accordance with said decision value. - View Dependent Claims (49)
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index; and
f) repeating steps b) to e) until there is no pointer associated with said index.
-
-
50. A method for locating a decision value, comprising the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at; and
retrieving the decision value from the last p-structure associated with said longest prefix. - View Dependent Claims (51)
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index; and
f) repeating steps b) to e) until there is no pointer associated with said index.
-
-
52. An apparatus for locating a decision value, comprising the steps of:
-
means for receiving an address for a packet;
means for matching said address with a longest prefix stored in a table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at; and
means for retrieving the decision value from the last p-structure associated with said longest prefix. - View Dependent Claims (53)
a) means for initializing a current partition member to a first partition member;
b) means for translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) means for storing a decision value associated with said index;
d) means for determining whether a pointer is associated with said index;
e) means for setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index; and
f) means for utilizing means b) to e) until there is no pointer associated with said index.
-
-
54. A computer readable medium whose contents cause a computer system to locate a decision value in a routing table, the computer system having a forwarding decision program with functions for locating, by performing the steps of:
-
receiving an address for a packet;
matching said address with a longest prefix stored in a routing table constructed using p-structures, wherein each p-structure is represented as an array having a first part and a second part, the first part containing forwarding information for the packet called a decision value, and the second part containing a pointer to another p-structure by identifying an associated first p-structure and receiving each subsequent p-structure that a pointer of a previous p-structure points to until a last p-structure having a decision value but no pointer is arrived at; and
retrieving the decision value from the last p-structure associated with said longest prefix. - View Dependent Claims (55)
a) initializing a current partition member to a first partition member;
b) translating said address into a p-structure index utilizing partition information stored for said current partition member;
c) storing a decision value associated with said index;
d) determining whether a pointer is associated with said index;
e) setting said current partition member to a next partition member associated with said pointer if there is a pointer associated with said index; and
f) repeating steps b) to e) until there is no pointer associated with said index.
-
Specification