GRID ROUTING APPARATUS AND METHOD

• US 20110158082A1
• Filed: 12/24/2009
• Published: 06/30/2011
• Est. Priority Date: 12/24/2009
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Contextream Ltd.
• Inventors: Kaempfer, Gideon, Barkai, Sharon, Noy, Ariel, Sidi, Ron
• Granted Patent: US 8,379,516 B2
• Time in Patent Office: Days
• US Class Current: 370/216
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A grid router for routing packets and a network containing the same. The router comprises ingress units (IE), mailbox units (MU), and egress units (EU) connected in a structure of succeeding layers, said layered structure being segregated such that units in a given layer are connected only to a subset of units in a succeeding layer, wherein said grid router comprises a hashing unit for using a hashing function to direct incoming packets through said layers, and wherein said hashing function is configured to reinforce said segregation by directing packets arriving at a given unit in one layer only to units of a corresponding subset in said succeeding layer.

Claims

1. A grid router for routing packets, the router comprising ingress units (IE), mailbox units (MU), and egress units (EU) connected in a structure of succeeding layers, said layered structure being segregated such that units in a given layer are connected only to a subset of units in a succeeding layer, said subset being an incomplete subset of said succeeding layer, wherein said grid router comprises a hashing unit for using a hashing function to direct incoming packets through said layers, and wherein said hashing function is configured to reinforce said segregation by directing packets arriving at a given unit in one layer only to units of a corresponding subset in said succeeding layer.

2. The grid router of claim 1, wherein said hashing function is a uniform function pointing to location tables, said location tables being specific to respective subsets.

3. The grid router of claim 1, wherein said hashing function comprises a plurality of hashing sub-functions, each sub-function being specific to a given subset.

4. The grid router of claim 3, wherein said hashing sub-functions are variants of a single hash function.

5. The grid router of claim 1, wherein said hashing function is a single hash function and is fed a key that is offset by an identifier implying a given subset.

6. The grid router of claim 1, wherein said hashing function comprises grouped sub-functions, each grouped sub-function being set with a bias for a physically closest unit of a respective subset.

7. The grid router of claim 1, wherein for multicast traffic, selection of a subset comprises forwarding to an MU collocated with the IU receiving said multicast traffic.

8. The grid router of claim 1, wherein for traffic flowing upstream towards an application service source, selection of a subset comprises forwarding said traffic to an MU collocated with the destination EU of said traffic.

9. The grid router of claim 1, wherein for traffic flowing downstream from an application service source, selection of a subset comprises forwarding said traffic to an MU collocated with the source IU of said traffic.

10. The grid router of claim 1, wherein for traffic requiring multi-hop forwarding, selection of a subset comprises forwarding said traffic to an MU collocated with the source IU of said traffic, said collocated MU further being configurable to forward said traffic to a next one of said multi-hops.

11. The grid router of claim 1, wherein external units are respectively connected via an aggregated link to a first and at least a second access point of said grid router, wherein said grid router is constructed such that notification of a failure of a unit in one layer of said grid router is passed on to a corresponding access point, thereby allowing traffic from a given external unit to be rerouted to at least one second access point via said aggregated link, thereby to avoid said failure.

12. The grid router of claim 11, wherein said access points are ingress units, said unit in one layer to which said failure notification relates is a mailbox unit, and said notification of failure causes shutting down of said corresponding access point interface, thereby to cause traffic to be rerouted to another ingress point participating in said aggregated link.

13. The grid router of claim 1, wherein packets are hashed to a primary and a secondary member of a pair of parallel units, such that in the event of failure of said primary member, a respective packet is routed to said secondary member, thereby avoiding said failure.

14. A network comprising grid routers for routing packets, the grid routers comprising ingress units (IE), mailbox units (MU), and egress units (EU) connected in a structure of succeeding layers, said layered structure being segregated such that units in a given layer are connected only to a subset of units in a succeeding layer, said subset being an incomplete subset of units in said succeeding layer, wherein said grid router comprises a hashing unit for using a hashing function to direct incoming packets through said layers, and wherein said hashing function is configured to reinforce said segregation by directing packets arriving at a given unit in one layer only to units of a corresponding subset in said succeeding layer.

15. The network of claim 14, wherein said hashing function is a uniform function pointing to location tables, said location tables being specific to respective subsets.

16. The network of claim 14, wherein said hashing function comprises a plurality of hashing sub-functions, each sub-function being specific to a given subset.

17. The network router of claim 16, wherein said hashing sub-functions are variants of a single hash function.

18. The network of claim 14, wherein said hashing function is a single hash function and is fed a key that is offset by an identifier implying a given subset.

19. The network of claim 14, wherein said hashing function comprises grouped sub-functions, each grouped sub-function being set with a bias for a physically closest unit of a respective subset.

20. The network of claim 14, being one member of the group comprising, a broadband access network, a PON based broadband access network, a wireless access network and an IMS network.

21. The network of claim 14, wherein external units are respectively connected via an aggregated link to a first and at least a second access point of said network, wherein said network is constructed such that notification of a failure of a unit in one layer of said network is passed on to a corresponding access point, thereby allowing traffic from a given external unit to be rerouted to at least one second access point via said aggregated link, thereby to avoid said failure.

22. The network of claim 21, wherein said access points are ingress units, said unit in one layer to which said failure notification relates is a mailbox unit, and said notification of failure causes shutting down of said corresponding access point interface, thereby to cause traffic to be rerouted to another ingress point participating in said aggregated link.

23. The network of claim 14, wherein packets are hashed to a primary and a secondary member of a pair of parallel units, such that in the event of failure of said primary member, a respective packet is routed to said secondary member, thereby avoiding said failure.