Fast lookup and update of current hop limit

• US 10,187,294 B2
• Filed: 05/29/2017
• Issued: 01/22/2019
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Banerjee, Amitabha, Singaravelu, Lenin
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US15/607,670
• Publication Number:
  US 20170331723A1
• Time in Patent Office: 603 Days
• Field of Search: None
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/566 Routing instructions carried by the data packet, e.g. active networks
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

In order to facilitate efficient and scalable lookup of current hop limits of transmitted packets, a communications device embeds hop limit values along with other connection parameters in a connection data structure. To transmit a packet for a particular connection, the communications device retrieves the data structure for the particular connection and applies the hop limit value embedded in the data structure to the packet for transmission. To keep track of the hop limits being embedded in different data structures of different connections, the communications device use a binary search in which each node of the search tree correspond to a different connection. The communications device maintains one such search tree per communications interface.

Claims

1. A method for transmitting packets from a communications device, the method comprising:

traversing a search tree to locate a node that corresponds to a particular transmission control protocol (TCP) connection, wherein the search tree comprises a plurality of nodes, each node pointing to a data structure of a corresponding TCP connection from a plurality of TCP connections;

receiving data for transmission on a first TCP connection from the plurality of TCP connections;

based on the received data, accessing connection parameters of the first TCP connection, the connection parameters comprising a hop limit value that is cached in a first data structure for the TCP connection;

assembling a packet header based on the connection parameters; and

transmitting a data packet over the first TCP connection, the data packet comprising the packet header and the received data.

2. The method of claim 1, wherein assembling the packet header based on the connection parameters comprises inserting the hop limit value into the packet header.

3. The method of claim 1, wherein the first data structure comprises the connection parameters of the first TCP connection, and wherein accessing the connection parameters comprises accessing the first data structure.

4. The method of claim 1, wherein the nodes of the search tree correspond to TCP connections that are established over a particular communications interface.

5. The method of claim 1 further comprising maintaining a plurality of search trees that each correspond to a different communications interface, each search tree used for updating copies of hop limit values cached in data structures of TCP connections that are established over the corresponding communications interface.

6. The method of claim 1, wherein the hop limit value limits a number of hops the transmitted data packet can have before reaching its destination.

7. The method of claim 6, wherein the data packet comprises an IPv6 (Internet Protocol version 6) header, and wherein the hop limit value is inserted into the IPv6 header.

8. The method of claim 1, wherein the data structure is identified by an index derived from a set of identifying information of the first TCP connection, each data structure for the TCP connection embedding a copy of the hop limit value, wherein the search tree is used to locate a node that corresponds to the first TCP connection based on the index, and the set of identifying information is a five-tuple identifier of the particular connection.

9. The method of claim 1, wherein the search tree is an Adelson-Velskii and Landis (AVL) binary search tree.

10. A communications device comprising:

a set of processors; and

a transmitter for assembling packets for transmission for a transmission control protocol (TCP) connection, the assembling of a packet for the TCP connection comprising;

receiving data for transmission on the TCP connection;

based on the received data, accessing connection parameters of the TCP connection, the parameters comprising a hop limit value that is cached in a data structure for the TCP connection;

assembling a packet header based on the accessed connection parameters; and

transmitting a data packet over the TCP connection, the data packet comprising the packet header and the received data.

11. The communications device of claim 10, wherein the data structure is identified by an index derived from a set of identifying information of the TCP connection, each data structure for the TCP connection embedding a copy of the hop limit value.

12. The communications device of claim 10, further comprising a hop limit update controller for:

receiving an updated hop limit value; and

updating the copy of the hop limit value embedded in the data structure of the TCP connection with the updated hot limit value.

13. The communications device of claim 12, wherein the hop limit update controller uses search trees to locate the copy of the current hop limit value.

14. The communications device of claim 13, further comprising a plurality of communications interfaces, each search tree corresponding to a different communications interface.

15. The communications device of claim 14, wherein each node of a search tree of a particular communications interface corresponds to a particular TCP connection that is established over the particular communications interface.

16. The communications device of claim 14, wherein each search tree is an Adelson-Velskii and Landis (AVL) binary search tree.

17. One or more computer-readable storage media comprising computer-executable instructions for assembling packets for transmission for a transmission control protocol (TCP) connection, that when executed by one or more processors, cause the one or more processors to:

receive data for transmission on the TCP connection;

based on the received data, access connection parameters of the TCP connection, the parameters comprising a hop limit value that is cached in a data structure for the TCP connection;

assemble a packet header based on the accessed connection parameters; and

transmit a data packet over the TCP connection, the data packet comprising the packet header and the received data.

18. The one or more computer-readable storage media claim 17, wherein assembling the packet header based on the accessed connection parameters comprises inserting the hop limit value into the packet header.

19. The one or more computer-readable storage media claim 17, wherein the data structure comprises the connection parameters of the TCP connection, and wherein accessing the connection parameters comprises accessing the data structure.

20. The one or more computer-readable storage media claim 17, wherein the data structure is identified by an index derived from a set of identifying information of the TCP connection, each data structure for the TCP connection embedding a copy of the hop limit value.