HIERARCHICAL SHORTEST PATH FIRST NETWORK ROUTING PROTOCOL

• US 20100128638A1
• Filed: 11/19/2009
• Published: 05/27/2010
• Est. Priority Date: 11/20/2008
• Status: Abandoned Application

• Current Assignee: SAP AG (SAP SE)
• Original Assignee: SAP AG (SAP SE)
• Inventors: Zajakins, Vadims, Navas, Julio
• Application Number:
  US12/622,391
• Publication Number:
  US 20100128638A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A hierarchical shortest path first (HSPF) protocol, routers of a network are grouped in areas, and routing and client subscription information are distributed through all levels of the network hierarchy in the same way. Each level of the hierarchy identifies its connections with its peers that have the same level of hierarchy, and represents areas outside its own as individual nodes. The number of levels of hierarchy is not limited to any particular number, and each level performs the same operations to share routing information and generate routes for data. Distribution of link-state and client subscription information begins at the router level, and continues up the levels of the hierarchy until distributed through the network.

Claims

1. A method comprising:

discovering links at routers of a distributed network, where the routers are logically, hierarchically grouped in areas, where the links include links to peer neighbor routers for which a direct connection exists, and which are in the same area, and links to routers in other areas;

distributing link-state information from each router to peer neighbor routers, where each router updates local link-state information to represent the links of its peer neighbor routers;

distributing link-state information between areas to peer neighbor areas that exist at a same level of hierarchy, where each router in the areas updates local link-state information to represent links of the peer neighbor areas, where each area outside of a router'"'"'s area is represented as a node within the router'"'"'s local link-state information; and

storing link-state information at each router to be used to determine routing paths for data distribution through the distributed network.

2. The method of claim 1, wherein the areas comprise one of separate companies, departments of an enterprise, or business organizations, and routers are logically grouped based on company, department, or business organization, respectively.

3. The method of claim 1, wherein the areas comprise separate geographic locations, and logically group routers based on geography.

4. The method of claim 1, wherein the routers are nodes in an eventing network.

5. The method of claim 4, wherein the eventing network parses queries into component parts and routes each component part in accordance with the routing paths toward a data source to satisfy a query.

6. The method of claim 1, wherein distributing link-state information between areas further comprises:

selecting a router to represent each area to other areas based on a node identifier of the routers within the areas.

7. The method of claim 6, wherein selecting the router based on the node identifier further comprises:

selecting the router based on which router has a smallest node identifier within the area.

8. The method of claim 6, wherein distributing link-state information between areas further comprises:

a router not selected to represent the area waiting for the selected router to distribute the link-state information for the area; and

the router not selected to represent the area distributing the link-state information to other areas if the selected router fails to distribute the link-state information within a period of time.

9. The method of claim 1, further comprising:

subscribing a client as a data target at a router;

distributing client subscription information from the router to peer neighbor routers, where each router stores client subscription information to represent the client subscriptions of its peer neighbor routers; and

distributing client subscription information between areas to peer neighbor areas that exist at a same level of hierarchy, where each router in the area stores client subscription information to represent the client subscriptions of its peer neighbor areas.

10. The method of claim 1, further comprising:

subscribing a client as a data source at a router;

distributing client subscription information from the router to peer neighbor routers, where each router stores client subscription information to represent the client subscriptions of its peer neighbor routers; and

distributing client subscription information between areas to peer neighbor areas that exist at a same level of hierarchy, where each router in the area stores client subscription information to represent the client subscriptions of its peer neighbor areas.

11. A computer readable storage medium having content stored thereon to provide instructions, which when executed, cause a processor to perform operations, including:

discovering links from a router to all routers directly connected to the router in a network having routers hierarchically grouped in areas, including discovering links to peer neighbor routers for which a direct connection exists, and which are in the same area, and links to routers in different areas;

generating local link-state information at the router to indicate the discovered links;

distributing the local link-state information from the router to the peer neighbor routers;

receiving link-state information for peer neighbor routers and areas;

updating the local link-state information to indicate links of the peer neighbors and areas, including representing the areas as individual nodes; and

generating routing paths based on the link-state information.

12. The computer readable storage medium of claim 11, wherein the areas comprise one or more of separate companies, geography, business organizations, departments, industry groups, business partners, or a combination of these.

13. The computer readable storage medium of claim 11, wherein the content to provide instructions for distributing link-state information between areas further comprises content to provide instructions for

selecting a router to represent each area to other areas based on a node identifier of the routers within the areas.

14. The computer readable storage medium of claim 11, further comprising content to provide instructions for

detecting that a directly connected router is unavailable;

updating the local link-state information to reflect the unavailable router;

distributing the updated local link-state information; and

generating updated routing paths based on the updated link-state information.

15. The computer readable storage medium of claim 14, wherein the content to provide instructions for detecting that the router is unavailable further comprises content to provide instructions for

determining that the directly connected router has not sent data or a heartbeat message within a threshold amount of time.

16. The computer readable storage medium of claim 11, wherein the content to provide instructions for distributing the local link-state information comprises content to provide instructions for

flooding the network with link-state information to multiple peer neighbor routers.

17. The computer readable storage medium of claim 16, wherein the content to provide instructions for flooding the network with link-state information comprises content to provide instructions for

sending the link-state information to all neighbor nodes in the network.

18. A router in a distributed network, comprising:

network ports to connect the router to the network, the router to send communications over the ports to the other routers;

a memory device to store a link-state database to store link-state information for the router, the link-state information including information indicating links from the router to peer neighbor routers for which a direct connection exists and which are in the same area, and links to routers in other areas, and link-state information for the peer neighbor routers, including information about links external to the area, where other areas are represented as individual nodes; and

a hierarchical shortest path first (HSPF) network stack to access the link-state database and calculate routing information based on the link-state information, to send the communications over the ports to other locations in the network, wherein calculating the routing information is performed the same for each hierarchical level of the network based on knowledge of peer nodes for the hierarchical level as indicated in the link-state information.

19. The router of claim 18, wherein the areas comprise one or more of separate companies, geography, business organizations, departments, industry groups, business partners, or a combination of these.

20. The router of claim 18, wherein the HSPF network stack is to further:

determine if the router is to be selected to represent the area of which the router is a part to other areas based on a node identifier of the router, and node identifiers of other routers within the area.