Granted Patent B2

US 7,796,587 · App. 11/361,970 · Granted Sep 14, 2010

Assignee: Hyperchip Inc.

Abstract

Claims (47)

1. A method of processing a plurality of sets of routing information received from corresponding ones of a plurality of neighbor nodes connectable to a router, the router having a plurality of memory units accessible via separate paths, the method comprising:

said router creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information;

said router accessing the plurality of memory units via the separate paths; and

said router storing the plurality of non-identical routing information subsets created from a given one of said received sets of routing information in respective ones of the plurality of memory units,

wherein said at least one of the received sets of routing information is a plurality of the received sets of routing information, and

wherein at least one of the plurality of non-identical routing information subsets created from the given one of said received sets of routing information comprises a portion that is not present in any of the other ones of the non-identical routing information subsets created from the given one of said received sets of routing information.

2. A method of processing a plurality of sets of routing information received from corresponding ones of a plurality of neighbor nodes connectable to a router, the router having a plurality of memory units accessible via separate paths, the method comprising:

said router creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information;

said router accessing the plurality of memory units via the separate paths; and

said router storing the plurality of non-identical routing information subsets created from a given one of said received sets of routing information in respective ones of the plurality of memory units,

wherein said at least one of the received sets of routing information is a plurality of the received sets of routing information, and

wherein each of the received sets of routing information includes a respective set of routes and wherein said creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information includes creating a respective plurality of non-identical subsets of routes from the set of routes in each of the at least one of the received sets of routing information,

further comprising: for each of the memory units, creating a forwarding sub-table associated with said memory unit from all routing information subsets stored in said memory unit

further comprising: creating a complete forwarding table from the forwarding sub-tables stored in the plurality of memory units

wherein no given memory unit of said plurality of memory units contains all routes from which said complete forwarding table is built.

3. A method as claimed in claim 2 , wherein each route has a specificity, and wherein each plurality of non-identical subsets of routes is created on the basis of the specificity of each route in the set of routes in a respective one of the received sets of routing information.

4. A method of processing a plurality of sets of routing information received from corresponding ones of a plurality of neighbor nodes connectable to a router, the router having a plurality of memory units accessible via separate paths, the method comprising:

said router creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information;

said router accessing the plurality of memory units via the separate paths; and

said router storing the plurality of non-identical routing information subsets created from a given one of said received sets of routing information in respective ones of the plurality of memory units,

wherein said at least one of the received sets of routing information is a plurality of the received sets of routing information, and

further comprising: for each of the memory units and for each of the neighbor nodes, creating a partial output routing information base, associated with said memory unit and said neighbor node, from all routing information subsets stored in said memory unit.

5. A method as claimed in claim 4 , further comprising: for each neighbor node, creating a complete output routing information base, associated with said neighbor node, from all partial output routing information bases associated with said neighbor node.

6. A method as claimed in claim 5 , further comprising: advertising to at least one neighbor node other than said neighbor node the complete output routing information base associated with said neighbor node.

7. A method of processing a plurality of sets of routing information received from corresponding ones of a plurality of neighbor nodes connectable to a router, the router having a plurality of memory units accessible via separate paths, the method comprising:

said router creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information;

said router accessing the plurality of memory units via the separate paths; and

said router storing the plurality of non-identical routing information subsets created from a given one of said received sets of routing information in respective ones of the plurality of memory units,

wherein said at least one of the received sets of routing information is a plurality of the received sets of routing information, and

wherein each of the received sets of routing information includes a respective set of prefixes and associated attributes and wherein creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information includes creating a respective plurality of non-identical subsets of prefixes and associated attributes from the set of prefixes and associated attributes in each of at least one of the received sets of routing information.

8. A method of processing a plurality of sets of routing information received from corresponding ones of a plurality of neighbor nodes connectable to a router, the router having a plurality of memory units accessible via separate paths, the method comprising:

said router creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information;

said router accessing the plurality of memory units via the separate paths; and

said router storing the plurality of non-identical routing information subsets created from a given one of said received sets of routing information in respective ones of the plurality of memory units,

wherein said at least one of the received sets of routing information is a plurality of the received sets of routing information, and

further comprising: identifying a set of at least two available memory units among the plurality of memory units; wherein creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information includes creating as many non-identical routing information subsets from a certain one of said received sets of routing information as there are memory units in said set of available memory units.

9. A method as claimed in claim 8 , further comprising: identifying a new set of at least two available memory units among the plurality of memory units; creating as many non-identical routing information subsets from a particular one of said received sets of routing information as there are memory units in said new set of available memory units.

10. A method as claimed in claim 8 , further comprising: identifying a change in the number of memory units in said set of at least two available memory units; and

modifying the number of non-identical routing information subsets created from a given one of said received sets of routing information to match the changed number of available memory units.

11. A method as claimed in claim 8 , wherein: said at least one of the received sets of routing information is a plurality of the received sets of routing information; for each given received set of routing information in said plurality of the received sets of routing information, the same function is used to create the respective plurality of non-identical routing information subsets from said given received set of routing information; each of the received sets of routing information includes a respective set of prefixes and associated attributes; creating a respective plurality of non-identical routing information subsets from each of at least one of the received sets of routing information includes creating a respective plurality of non-identical subsets of prefixes and associated attributes from the set of prefixes and associated attributes in each of at least one of the received sets of routing information; and for each received set of routing information in said plurality of the received sets of routing information, the subsets containing any given prefix are stored in the same memory units as the corresponding subsets of the other received sets of routing information from said plurality of the received sets of routing information that contain the same given prefix.

12. A method as claimed in claim 11 , further comprising: identifying a change in the number of memory units in said set of at least two available memory units; modifying the number of non-identical routing information subsets created from a given one of said received sets of routing information to match the changed number of available memory units;

wherein each non-identical routing information subset has a respective number of routes and wherein said modifying the number of non-identical routing information subsets comprises:

responsive to a decrease in said number of available memory units, combining the corresponding subsets of the two or more memory units that have the smallest numbers of routes.

13. A method as claimed in claim 11 , further comprising: identifying a change in the number of memory units in said set of at least two available memory units; modifying the number of non-identical routing information subsets created from a given one of said received sets of routing information to match the changed number of available memory units;

wherein each non-identical routing information subset has a respective number of routes and wherein said modifying the number of non-identical routing information subsets comprises:

responsive to an increase in said number of available memory units, splitting the subsets associated with the one or more memory units that have the largest numbers of routes.

14. A method of distributing routing information among a plurality of memory units, the routing information pertaining to a plurality of routes, each of the routes having a prefix with a respective length, the method comprising: a router associating each of said routes with a respective subset of said plurality of memory units on a basis of the prefix of that route, the number of memory units in the subset of said plurality of memory units that is associated with a given one of said routes being inversely related to the length of that route's prefix; and causing the routing information pertaining to each of said routes to be stored in each of the at least one of the memory units associated with that route; wherein the routing information pertaining to at least one of said routes is not stored in all of said plurality of memory units.

Assignments (8)

Continuity (1)