EXECUTING LOOPS

• US 20150295816A1
• Filed: 12/29/2014
• Published: 10/15/2015
• Est. Priority Date: 04/11/2014
• Status: Active Grant

• Current Assignee: Entuity Ltd. (Park Place Technologies LLC)
• Original Assignee: Entuity Ltd. (Park Place Technologies LLC)
• Inventors: Roper, Jeffrey John
• Granted Patent: US 9,537,760 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A method of executing a loop computer program comprising receiving at an execution unit a set of state variables which define an entry state, wherein one of the state variables defines a sequence of loop options; recording the entry state in a storage unit; in the execution unit, executing a first loop option in the ordered sequence of loop options in the entry state, using as parameters at least one of the other state variables in the set of state variables, wherein executing the first loop option comprises cancelling the first loop option from the ordered sequence, carrying out processing steps using at least one state variable, and determining if any of the state variables have altered as a result of the processing steps, wherein if none of the state variables have altered, entering a next loop iteration with an entry state in which the first loop option is cancelled from the ordered sequence, revealing a new first loop option, and; if at least one of the state variables has altered, reinstating the cancelled first loop option in the ordered sequence and entering a next loop iteration with an entry state defined by the altered state variable (s) and the original ordered sequence, whereby each next loop iteration receives a new entry state.

Claims

1. A method of executing a loop computer program comprising:

receiving at an execution unit a set of state variables which define an entry state, wherein one of the state variables defines a sequence of loop options;

recording the entry state in a storage unit;

in the execution unit, executing a first loop option in the ordered sequence of loop options in the entry state, using as parameters at least one of the other state variables in the set of state variables, wherein executing the first loop option comprises cancelling the first loop option from the ordered sequence, carrying out processing steps using at least one state variable, and determining if any of the state variables have altered as a result of the processing steps, wherein;

if none of the state variables have altered, entering a next loop iteration with an entry state in which the first loop option is cancelled from the ordered sequence, revealing a new first loop option, and;

if at least one of the state variables has altered, reinstating the cancelled first loop option in the ordered sequence and entering a next loop iteration with an entry state defined by the altered state variable (s) and the original ordered sequence,

whereby each next loop iteration receives a new entry state.

2. The method of claim 1, used to identify a path from a source device to a terminal device in a network of interconnected devices.

3. The method of claim 1 implemented at a monitor computer having a query path to the interconnected devices, wherein executing at least some of the loop options generates a path identification query.

4. The method of claim 3, wherein one of the state variables is a focus device to receive the path identification query.

5. The method of claim 3, wherein one of the state variables is a routing address for traffic addressed to a next hop in the path according to a routing protocol, the routing address to be used in the path identification query.

6. The method of claim 3, wherein one of the state variables is a switching address for switching traffic in the direction of the terminal device according to a switching protocol, the switching address to be used in the path identification query.

7. The method of claim 4, wherein one of the state variables is a virtual local area network identifier which is relevant to the path at the location identified by the focus device.

8. The method of claim 1, wherein one of the state variables is a routing network address, wherein one of the options determines if there is a unique interface on the focus device matching the routing network address in the entry state, or each new entry state, and identifies an egress port of the focus device from the unique interface.

9. The method of claim 8, wherein the routing address is set to the routing address of the terminal device.

10. The method of claim 1 wherein one of the state variables is a routing network address and a further one of the state variables is a switching address wherein an option determines if the routing address in the entry state is on the focus device of the entry state and if not uses a mapping table to translate the routing address to a switching address.

11. The method of claim 10, wherein the switching address is used to access a forwarding database to locate an egress port.

12. The method of claim 1 wherein one of the state variables is a routing network address and a further one of the state variables is a switching address an option locates in a mapping table a mapping entry between the routing address and switching address in the entry state (or new entry state), uses the mapping entry to determine from which interface the mapping entry was derived, and thus derives an egress port.

13. The method of claim 5, wherein the option determines the route by iterative query of a routing table at the focus device to generate a candidate routing address.

14. The method of claim 13, which comprises using a mapping table to translate the candidate routing address to a candidate switching address, and comparing the candidate switching address with the switching address in the entry state (or new entry state).

15. The method of claim 8 wherein the egress port is used to locate the next connected device from a network topology.

16. The method of claim 1, wherein a first priming process stores start and stopping points by identifying network locations for each of the source device and terminal device.

17. The method of claim 16, wherein a second priming process sets a routing address and switching address for the entry state of a first loop iteration.

18. The method of claims 16 wherein a second priming process sets a routing address and switching address for the entry state of a first loop iteration and wherein a second priming process sets a routing address and switching address for the entry state of a first loop iteration and wherein a third priming process sets a focus device for the entry state of a first hop iteration as the source device or an access switch for the source device.

19. The method of claim 18, comprising:

obtaining a hint to assist in identifying a virtual local area network in which the focus device is connected.

20. The method of claim 19, wherein obtaining a hint comprises determining an access port for egress of messages from the source device, identifying the name of the access port, and extracting a number from the name of the access port to store as the hint.

21. The method of claim 19, wherein obtaining a hint comprises determining an access port for egress of messages from the source device, identifying explicit VLAN assignments for the port (via SNMP or from an NMS) and if the VLAN assignment is unique, storing the unique VLAN number as the hint.

22. The method of claims 19, wherein one of the state variables is a routing network address, wherein one of the options determines if there is a unique interface on the focus device matching the routing network address in the entry state, or each new entry state, and identifies an egress port of the focus device from the unique interface wherein the egress port and the VLAN hint is used to locate the next connected device from the network topology.

23. A computer implemented method of identifying in a network of interconnected devices a path through the network from a source device to a final destination device, the path comprising a connected sequence of devices, the method comprising using the loop execution method of claim 1 at a monitor computer connected to the network to implement the steps of:

identifying a first device connected to the source device;

transmitting a first query to the first device, the query including a destination identifier and requesting identification of an egress port for messages addressed to the destination identified by the destination identifier when the query is received at the first device;

receiving a result message identifying the egress port and identifying the second device connected to the first device based on a network topology accessible by the monitor computer; and

addressing a next query to the second device and receiving a next result message identifying an egress port from the second device; and

identifying from the network topology a third device connected to the second device, wherein the path is identified to include the first, second and third devices.