Identification of paths in a network of mixed routing/switching devices

• US 9,544,217 B2
• Filed: 04/17/2014
• Issued: 01/10/2017
• Est. Priority Date: 04/19/2013
• Status: Active Grant

• Current Assignee: Entuity Ltd. (Park Place Technologies LLC)
• Original Assignee: Entuity Ltd. (Park Place Technologies LLC)
• Inventors: Roper, Jeffrey John
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): JEONG, MOO RYONG
• Application Number:
  US14/255,815
• Publication Number:
  US 20140313937A1
• Time in Patent Office: 999 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• 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 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Computer implemented methods are disclosed that include identifying a next hop from a focus device in a path of interconnected devices including switching and routing devices, wherein a switching device operates according to a switching address protocol and a routing device operates according to a routing address protocol. The methods may include, for a focus device which is configured to receive traffic addressed to a terminal destination and to act as a routing device, dispatching a query message containing a query key based on an identifier for the terminal destination from a management computer to the focus device to identify the next routing address; receiving a result message containing a new routing address; and ascertaining from the new routing address the corresponding switching address, wherein the switching address is usable in a query key for a query directed to a focus device which is a switching device.

Claims

1. A computer implemented method of identifying a next hop from a focus device in a path of interconnected devices including switching devices and routing devices, configured in multiple virtual local area networks (VLANs) wherein the switching devices operate according to a switching address protocol and the routing devices operate according to a routing address protocol, the method implemented at a management computer having a query path to the interconnected devices and comprising:

for the focus device which is one of the routing devices and which is configured to receive traffic addressed to a terminal destination, the traffic comprising packets which each carry a VLAN identifier which identifies which VLAN is used to route the packet, the step of dispatching a query message containing a query key based on a destination identifier for the terminal destination from the management computer to the focus device, the query message causing the focus device to identify and supply a next routing address for a hypothetical packet addressed to the terminal destination;

receiving, from the focus device, a result message containing a new routing address which is the next routing address;

ascertaining from the new routing address a corresponding switching address which is a switching address for switching traffic at one of the switching devices in a direction to the terminal destination; and

using the switching address in a subsequent query key of a subsequent query message directed to said one of the switching devices, wherein the subsequent query message is directed to a forwarding database at said one of the switching devices,

wherein the subsequent query message includes a VLAN identifier for the hypothetical packet, the VLAN identifier identifying the forwarding database to which the subsequent query message is directed and receiving a subsequent result message identifying an egress port of said one of the switching devices from the forwarding database of said one of the switching devices.

2. A method according to claim 1, wherein a next hop device is identified from the egress port received at the management computer.

3. A method according to claim 1, wherein the switching address is ascertained from a mapping table which maps routing addresses to switching addresses.

4. A method according to claim 1, further comprising:

if the focus device hosts the next routing address;

dispatching a third query message to the focus device containing the routing address of a final destination device in the path; and

ascertaining a new next routing address along with a new switch address of this new routing address, and the egress port for messages addressed to this new next routing address.

5. A method according to claim 1, further comprising:

if the focus device does not host the next routing address;

dispatching another subsequent query message to the focus device; and

ascertaining the egress port for messages addressed to the switching address of the next routing address.

6. A method according to claim 1, wherein the focus device is a source device for traffic conveyed over the path and the step of identifying the next routing address comprises dispatching a query to the source device, containing a routing address of the terminal destination in the path, and ascertaining from the response a next routing address identifier.

7. A method according to claim 1, further comprising:

locating a source device for traffic conveyed over the path by directing a query to a focus device expected to be the source device; and

using the switching address to query a switching device connected to the source device.

8. A method according to claim 3, wherein the mapping table is a global mapping table which maps routing addresses to switching addresses for each device.

9. A method according to claim 1, wherein the switching devices are layer 2 devices according to the open systems interconnection model using a medium access control addressing protocol.

10. A method according to claim 1, wherein the routing devices are layer 3 routing device according to the open systems interconnection model using an Internet protocol routing address protocol.

11. A method according to claim 3, wherein the mapping table is an address routing protocol (ARP) table according to the open systems interconnection model.

12. A method according to claim 1, wherein the query message and the subsequent query message are transmitted from the management computer to the focus device over the network.

13. A method according to claim 12, wherein the query message and the subsequent query message take the form of a least one packet addressed to the device which is being queried.

14. A method according to claim 2, wherein the next hop device is identified from the egress port using a network topology and is shared in a path record accessible by the management computer.

15. A management computer for identifying a next hop in a path of interconnected devices, the management computer comprising:

an interface connected to the interconnected devices for transmitting queries and receiving responses;

a processor operable to execute a computer program which carries out the method of claim 1; and

a storage means for storing a network topology.

16. A management computer according to claim 15, comprising storage means for storing a record of identified hop devices as a path record.

17. A non-transitory computer program product which comprises computer readable instructions which when executed by a processor implements the method of claim 1.

18. A computer implemented method of identifying a next hop for a flow of traffic through a focus device in a path of interconnected devices including switching devices and routing devices, wherein the switching devices operate according to a switching address protocol and the routing devices operate according to a routing address protocol, the method implemented at a management computer having a query path to the interconnected devices and comprising:

for the focus device which is one of the routing devices and which is configured to receive traffic addressed to a terminal destination, dispatching a query message containing a query key based on a destination identifier for the terminal destination from the management computer to the focus device, the query message causing the focus device to identify and supply a next routing address for a hypothetical message addressed to the terminal destination;

receiving, from the focus device, a result message containing a new routing address which is the next routing address;

ascertaining from the new routing address a corresponding switching address which is a switching address for switching traffic at one of the switching devices in a direction to the terminal destination;

using the switching address in a subsequent query key for a subsequent query message directed to said one of the switching devices;

directing the subsequent query message to a forwarding database at said one of the switching devices, the subsequent query message causing said one of the switching devices to identify and supply an egress port for the switching address at said one of the switching devices,

wherein the query message and subsequent query message are transmitted from the management computer over the network, while the network is active and there is a flow of traffic between the interconnected devices, wherein the query message and subsequent query message do not constitute the flow of traffic for which the next hop is to be determined.

19. A computer implemented method of identifying a next hop from a focus device in a path of interconnected devices including switching devices and routing devices, wherein a switching device operates according to a switching address protocol and a routing device operates according to a routing address protocol, the method implemented at a management computer having a query path to the interconnected devices and comprising:

for the focus device which is one of the routing devices and which is configured to receive traffic addressed to a terminal destination, the traffic comprising packets which each carry a VLAN identifier which identifies which VLAN is used to route the packet, the step of dispatching a query message containing a query key based on a destination identifier for the terminal destination from the management computer to the focus device, the query message causing the focus device to identify and supply a next routing address for a hypothetical packet addressed to the terminal destination;

receiving, from the focus device, a result message containing a new routing address which is the next routing address;

ascertaining from the new routing address a corresponding switching address which is a switching address for switching traffic at one of the switching devices in a direction to the terminal destination, wherein the switching address is ascertained from a mapping table which maps routing addresses to switching addresses;

using the switching address in a subsequent query key of a subsequent query message directed to said one of the switching devices, wherein the subsequent query message is directed to a forwarding database at said one of the switching devices, the forwarding database identified by the VLAN identifier; and

if the forwarding database at said one of the switching devices does not contain an entry for an egress port for traffic addressed to the terminal destination, querying the mapping table that was used to map the routing address to the switching address, thereby identifying an interface from which the mapping between the routing and switching address was learned.