Method and apparatus for storing and retrieving data related to paths of a multi-path, multi-tier network

• US 7,356,612 B2
• Filed: 06/18/2003
• Issued: 04/08/2008
• Est. Priority Date: 06/18/2003
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Rachlin, Elliott H.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US10/465,414
• Publication Number:
  US 20040260833A1
• Time in Patent Office: 1,756 Days
• Field of Search: 709230-235, 370229-235, 370/400
• US Class Current: 709/242
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

An apparatus is provided for storing and retrieving data relating to paths through a network having a plurality of linked nodes and a destination node, each node of the plurality of nodes having a counter operable to transmit counter data when the node is operating properly. The apparatus includes a processor coupled to the destination node, which serves as a source of received counter data, a memory coupled to said processor, and a data link to a destination node of the network. The memory contains at least one data structure adapted to associate data relating to designed paths through the network with data relating to the received counter data. The memory also contains processor instructions executable to store said data relating to the received counter data in the at least one data structure. Methods for searching and updating the apparatus are also provided.

Claims

1. An apparatus for storing and retrieving data related to paths through a network having a plurality of linked nodes and a destination node, each node of the plurality of nodes having a counter operable to transmit counter data when the node is operating properly, the apparatus comprising:

a processor coupled to said destination node, wherein said destination node serves as a source of counter data received at said destination node; and

a memory coupled to said processor, said memory including at least one data structure adapted to associate data relating to designed paths through said network with data relating to said counter data received at said destination node; and

processor instructions residing in said memory executable to store said data relating to said counter data received at said destination node in said at least one data structure, wherein the counter data of each node is uniquely associated with its respective node and relates to the nodes operability.

2. The apparatus of claim 1, wherein each node of said plurality of nodes has at least one data source operable to produce at least one telemetry item comprising a stream of data elements and a process unique identifier (PUI) for said data elements, wherein said data structure comprises a linear hierarchy of indexed tables.

3. The apparatus of claim 2, wherein at least one said table of said linear hierarchy of indexed tables is configured to store data relating to said counter data.

4. The apparatus of claim 3, wherein said linear hierarchy of indexed tables further comprises a linear hierarchy of directly-addressable indexed tables.

5. The apparatus of claim 3, wherein a first table of said linear hierarchy of indexed tables comprises a look-up table indexed by said PUIs organized by group, each group including the PUIs for data streams originating from each respective node, wherein each PUI is associated with:

data relating to said each telemetry item identified by each said PUI; and

an index to a group table.

6. The apparatus of claim 5, wherein said data relating to said each telemetry item comprises a data update rate.

7. The apparatus of claim 6, wherein said data relating to said each telemetry item comprises a data format code.

8. The apparatus of claim 5, wherein said PUI, said data relating to said each telemetry item, and said group index comprise elements in an ordered PUI list.

9. The apparatus of claim 5, wherein a second table of said linear hierarchy of indexed tables comprises said group table, wherein each group table index is associated with:

a first index to a path table

a second index to said path table.

10. The apparatus of claim 9, wherein said first index to said path table and said second index to said path table comprise elements in an ordered group list.

11. The apparatus of claim 10, wherein said ordered group list further comprises a status indicator associated with said group.

12. The apparatus of claim 11, wherein said status indicator associated with said group comprises an updatable indicator.

13. The apparatus of claim 10, wherein said ordered group list further comprises data associated with said node originating said each telemetry item.

14. The apparatus of claim 9, wherein a third table of said linear hierarchy of indexed tables comprises said path table, said first index to said path table and said second index to said path table comprising an inclusive range of path table indexes to designed paths from said node originating said telemetry item to said destination node, wherein each path table index is associated with a first index to a link table and a last index to said link table.

15. The apparatus of claim 14, wherein said first index to said link table and said last index to said link table comprise elements in an ordered path list in said path table.

16. The apparatus of claim 15, wherein said ordered path list further comprises an indicator of a status of said path.

17. The apparatus of claim 14, wherein a fourth table of said linear hierarchy of indexed tables comprises said link table, said first index to said link table and said last index to said link table comprising an inclusive range of link table indexes to a sequence of links in each said path, wherein each index to said link table is associated with an index to a pipe table.

18. The apparatus of claim 17, wherein said index to said pipe table comprises an element in an ordered pipe list in said link table.

19. The apparatus of claim 17, wherein a fifth table of said linear hierarchy of indexed tables comprises said pipe table, said pipe table index associate with a counter PUI and a pipe status indicator in said pipe table.

20. The apparatus of claim 19, wherein said counter PUI and said pipe status indicator comprise elements in an ordered pipe list in said pipe table.

21. The apparatus of claim 20, wherein said pipe list further contains a primary/secondary status PUI and a primary status enumeration value.

22. A method of updating a data structure within which resides data related to designed paths in a multi-tier, multi-path communications network, each said designed path including a plurality of linked nodes in a linear sequence from an originating linked node to a destination node, the method comprising the steps of:

receiving counter data arriving at said destination node, said counter data being generated by counters in each linked node, wherein the counter data is uniquely identified with its associated linked node;

determining if said received counter data is changing; and

associating, based upon said determination, an indicator of node operability with said linked node with which said received counter data is associated.

23. The method of claim 22, wherein the steps of associating said indicator of node operability with said node comprises the steps of:

associating a first indicator of node operability with said node if said associated counter data is changing; and

associating a second indicator of node operability with said node if said counter data is not changing.

24. The method of claim 23, further comprising the steps of:

determining if a particular linked node is in primary status; and

associating said second indicator of node operability with said node if said particular node is in secondary status.

25. The method of claim 22, wherein each said link originating from each said linked node in each said designed path is associated with a pipe status indicator in said data structure, the step of associating said indicator of node operability with said node comprising the step of storing said indicator of node operability as said pipe status indicator.

26. The method of claim 22, wherein said data structure further associates each said unique counter data identifier with a group of data identifiers commonly originating from said uniquely associated each respective linked node and with a group status indicator, the step of associating further comprising the steps of:

finding said group associated with said counter unique counter data identifier in said data structure;

finding said group status indicator associated with said found group; and

storing said indicator of node operability as said found group status indicator.

27. The method of claim 26, wherein data structure further associates each group with said designed paths from each said group to said destination node, each said path associated with a path status indicator, the step of associating further comprising the steps of:

finding at least one said designed path associated with said found group;

finding a path status indicator associated with said at least one found path; and

storing said indicator of node operability as said path status indicator.

28. The method of claim 22, further comprising the step of updating data other than status indicators relating to one of said pipe, path and group.

29. A method of searching an apparatus for storing and retrieving data related to paths through a network having a plurality of linked nodes and a destination node, each node of the plurality of nodes having a counter operable to transmit uniquely identified counter data when the node is transmitting telemetry data by exception as designed, the method comprising the step of looking up a unique counter data identifier in a unique identifier table to find a group table index to data relating to a particular group of data commonly originating from said node transmitting said uniquely identified counter data.

30. The method of claim 29, further comprising the step of looking up said group table index in said group table to find a first path table, a last path index to said path table, and a group status indicator associated with said particular group.

31. The method of claim 30, further comprising the steps of:

determining group status from said group status indicator;

if said group status is inoperable, invalidating said telemetry data originating from said node originating said group and terminating said search;

if said group status is operable, validating said telemetry data originating from said node originating said group and terminating said search; and

if said group status is unknown, continuing said search.

32. The method of claim 31, further comprising the step of looking up designed paths between a first path table index and a second path table index, inclusive, in said path table to find, for each path table index, a first link index to a link table and a last link index to said link table.

33. The method of claim 32, wherein said path table includes, for each designed path, a path status indicator, the method further comprising the steps of:

determining a status for said each designed path based on each respective said path status indicator;

if said path status for each said designed path is inoperable, invalidating said telemetry data originating from said node and terminating said search;

if said path status for at least one said designed path is operable, validating said telemetry data originating from said node originating said each designed path; and

if said path status for each said designed path is unknown, continuing said search.

34. The method of claim 33, wherein the step of continuing said search comprises the step of looking up each link sequence between said first link table index and said last link table index, inclusive, in said link table to find, for each link table index, a pipe table index.

35. The method of claim 34, further comprising the step of looking up each pipe table index in said pipe table to find a pipe status indicator for each said link for each said path from said group originating said uniquely identified counter data.

36. The method of claim 35, further comprising the step of determining if any link sequence has associated pipe status indicators each indicating an operable link.

37. The method of claim 36, further comprising the step of validating said data originating from said node originating said designed path if any sequence has associated pipe status indicators all indicating operable links.

38. The method of claim 29, wherein said unique identifier table associates each unique counter data identifier with particular counter format data, the method further comprising the steps of:

determining from said unique counter format data if said unique counter data has an active format; and

invalidating said telemetry data originating from said node and terminating said search if said counter format data has an inactive format.

39. A program product comprising program instructions embodied on a processor-readable medium for execution by a programmable processor, wherein the program instructions are operable to cause the programmable processor to:

store counter data that is unique to each linked node in a multi-tier/multi-path network in a linear hierarchy of directly-addressable indexed tables;

determine a status indicator of at least one linked node based on its associated counter data that is unique to the linked node; and

associate a unique identifier relating to counter data that is unique to each linked node with the determined status indicator in the linear hierarchy of directly-addressable indexed tables.

40. The program product of claim 39, wherein the program instructions further associates unique identifiers of data streams with associated nodes originating from associated counter data.

41. The program product of claim 40, wherein the program instructions further associates said unique identifier of data streams with associated paths of nodes from a node originating said data stream to a destination node.

42. The program product of claim 41, the program instructions further associates each said path with each said link in each said path.

43. The program product of claim 41, wherein the program instructions further finds possible paths from said node originating said data stream to said destination node in response to said unique identifier of a data stream.