Grid routing apparatus and method

• US 8,379,516 B2
• Filed: 12/24/2009
• Issued: 02/19/2013
• 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: Barkai, Sharon, Noy, Ariel, Kaempfer, Gideon, Sidi, Ron
• Primary Examiner(s): RIYAMI, ABDULLAH A
• Application Number:
  US12/647,145
• Publication Number:
  US 20110158082A1
• Time in Patent Office: 1,153 Days
• Field of Search: 370/216, 370/218, 370/229, 370/230, 370/231, 370/235, 370/254, 370/252, 370/389, 370/392, 370/395.31, 370/258, 370/390, 370/328, 370/422, 370/419, 370/400, 370/401, 709/236, 709/230, 709/223, 709/226, 709/224
• US Class Current: 370/229
• 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 circuits (IUs), mailbox circuits (MUs), and egress circuits (EUs) connected in a structure of succeeding layers, said layered structure being segregated such that circuits in a given layer are connected only to a corresponding subset of mailbox circuits in a succeeding layer, said corresponding subset of mailbox circuits being an incomplete subset of mailbox circuits in said succeeding layer, said segregation excluding packet flows not between said circuits in the given layer and said corresponding subset of mailbox circuits,

wherein said grid router further comprises a hashing circuit 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 the packets arriving at a given circuit in one layer to the circuits only of the corresponding subset in said succeeding layer, to which the circuits of said corresponding subset, flow is allowed by said segregation.

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 a mailbox circuit (MU) collocated with an ingress circuit (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 a mailbox circuit (MU) collocated with a destination egress circuit (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 a mailbox circuit (MU) collocated with a source ingress circuit (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 a mailbox circuit (MU) collocated with a source ingress circuit (IU) of said traffic, said collocated MU further being configurable to forward said traffic to a next one of multi-hops.

11. The grid router of claim 1, wherein external circuits 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 particular circuit in particular layer of said grid router is passed on to a corresponding access point, thereby allowing traffic from a given external circuit to be rerouted to at least one said second access point via said aggregated link, thereby to avoid said failure.

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

13. The grid router of claim 1, wherein the packets are hashed to a primary and a secondary member of a pair of parallel circuits, 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 system comprising grid routers for routing packets,

each of the grid routers comprising ingress circuits (IUs), mailbox circuits (MUs), and egress circuits (EUs) connected in a structure of succeeding layers, said layered structure being segregated such that circuits in a given layer are connected only to a corresponding subset of mailbox circuits in a succeeding layer, said corresponding subset of mailbox circuits being an incomplete subset of mailbox circuits in said succeeding layer, said segregation excluding packet flows not between said circuits in the given layer and said corresponding subset of mailbox circuits,

wherein each of said grid routers further comprises a hashing circuit 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 the packets arriving at a given circuit in one layer to the circuits only of the corresponding subset in said succeeding layer, to which the circuits of said corresponding subset, flow is allowed by said segregation.

15. A network system 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 system 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 system of claim 16, wherein said hashing sub-functions are variants of a single hash function.

18. The network system 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 system 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 system 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 system of claim 14, wherein external circuits are respectively connected via an aggregated link to a first and at least a second access point of said network system, wherein said network system is constructed such that notification of a failure of a particular circuit in particular layer of said network system is passed on to a corresponding access point, thereby allowing traffic from a given external circuit to be rerouted to at least one said second access point via said aggregated link, thereby to avoid said failure.

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

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