Querying a traffic forwarding table

• US 9,531,598 B2
• Filed: 04/17/2014
• Issued: 12/27/2016
• 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,835
• Publication Number:
  US 20140314086A1
• Time in Patent Office: 985 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• 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/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

Computer implemented methods include querying a traffic forwarding table at a device in a computer network, the traffic forwarding table having entries which are accessible using a key. The methods further include identifying a forwarding address for use in querying the traffic forwarding table, where the forwarding address constitutes only part of a key and where a remaining part of the key is an embedded index in the traffic forwarding table. The methods additionally include combining the forwarding address with a plurality of embedded indices of the traffic forwarding table to generate a set of keys for querying the traffic forwarding table; and generating a query message for the forwarding table using at least one of the set of keys.

Claims

1. A computer implemented method of querying a traffic forwarding table at a device in a computer network, the traffic forwarding table having entries which are accessible using a key, the method comprising at a monitor computer connected to the computer network:

identifying a forwarding address for use in querying the traffic forwarding table, wherein the forwarding address constitutes only part of a key and wherein a remaining part of the key is an embedded index in the traffic forwarding table;

combining the forwarding address with a plurality of embedded indices of the traffic forwarding table to generate a set of keys for querying the traffic forwarding table;

generating a first query message for the forwarding table using at least one of said set of keys;

transmitting the first query message from the monitor computer to the device via the computer network;

receiving a result message from the device, the result message containing a next hop address and an egress port identifier, said egress port identifier being equal to zero;

generating a second query message using at least one of a new set of keys, wherein the new set of keys is generated by combining the next hop address with the plurality of embedded indices; and

transmitting the second query message to the device.

2. A method according to claim 1, wherein the step of combining the forwarding address comprises logically combining a bit sequence representing the forwarding address with a bit sequence representing each embedded index of the plurality of embedded indices.

3. A method according to claim 1, wherein the key(s) which are used in the first or second query message generated for the device are selected from the set of keys by selecting only the unique keys from the set of keys, wherein the number of keys in the set of keys is greater than the number of keys that are selected.

4. A method according to claim 1, wherein the forwarding table is a routing table and each index in the routing table is a net mask.

5. A method according to claim 4, wherein the forwarding table is for a layer 3 routing device.

6. A method according to claim 1, wherein the embedded index is an interface index of an ARP table in a forwarding device.

7. A method according to claim 1, wherein the first or second query message contains a plurality of query keys for querying the table in parallel.

8. A method according to claim 4, wherein each key also comprises an egress port identifier of the device.

9. A method according to claim 8, wherein the result message returned from the traffic forwarding table comprises an egress port identifier, and wherein the egress port identifier returned in the result message is compared with the egress port identifier in the key to determine if there is a match.

10. A computer configured to implement a method querying a traffic forwarding table, the computer comprising:

a processor; and

a memory, the memory holding a computer program which, when executed by the processor, carries out the steps of claim 1.

11. A non-transitory computer program product in the form of a computer program which, when executed by computer, implements the method of claim 1.