Fast lookup and update of current hop limit

• US 9,667,528 B2
• Filed: 03/31/2014
• Issued: 05/30/2017
• Est. Priority Date: 03/31/2014
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Singaravelu, Lenin, Banerjee, Amitabha
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US14/231,677
• Publication Number:
  US 20150281049A1
• Time in Patent Office: 1,156 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:

maintaining a search tree to locate a node that corresponds to a particular transmission control protocol (TCP) connection, the search tree comprising a plurality of nodes, each node pointing to a data structure of a corresponding TCP connection, said node identified by an index derived from a set of identifying information of the corresponding TCP connection;

receiving an updated hop limit value;

updating a copy of a hop limit value that is cached in the data structure pointed to by the located node with the updated hop limit value, the hop limit value being a parameter associated with the TCP connection; and

transmitting a data packet for the particular TCP connection by retrieving said data structure for the particular connection and inserting the updated copy of the hop limit value obtained from the data structure into the data packet.

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

3. 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.

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

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

6. The method of claim 1, further comprising requiring less than log(n) traversals when traversing the search tree to locate the node that corresponds to the particular connection, n being the number of nodes in the search tree.

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

8. The method of claim 1 further comprising deleting a node from the search tree when a corresponding connection is terminated.

9. The method of claim 1, further comprising adding a node to the binary search tree when a corresponding connection is established.

10. The method of claim 1, wherein the search tree is used to locate a node that corresponds to the particular connection based on the index, and the set of identifying information is a five-tuple identifier of the particular connection.

11. A communications device comprising:

a set of processors;

a transmitter for assembling packets for transmission for a transmission control protocol (TCP) connection, the assembling of a packet for the TCP connection comprising retrieving a data structure for the TCP connection, said data structure 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 a current hop limit value;

receiving an updated hop limit value

a hop limit update module controller for;

receiving an updated hop limit value; and

updating the copy of the current hop limit value embedded in the data structure of the TCP connection with the updated hot limit value, the current hop limit value being a parameter associated with the TCP connection.

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

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

14. The communications device of claim 13, wherein the search tree of a communications interface is used for locating and updating a copy of a hop limit value of the communications interface.

15. The communications device of claim 13, 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 12, wherein the search tree is an Adelson-Velskii and Landis (A VL) binary search tree.

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

transmitting a packet for a TCP connection associated with a corresponding connection data structure, said connection data structure identified by an index derived from a set of identifying information of the TCP connection, said connection data structure comprising a copy of a hop limit value of the communications interface, the hop limit value being a parameter associated with the TCP connection, the transmitting of the packet for the TCP connection comprising retrieving the connection data structure;

receiving an updated hop limit value for the communications interface; and

updating the copy of the hot limit value in the connection data structure of the TCP connection to the received updated hop limit value.

18. The method of claim 17, wherein the updating of the copy of the hop limit value comprises using a search tree to locate the copy of the hop limit value.

19. The method of claim 18, wherein the search tree comprises a plurality of nodes, each node pointing to the copy of the hop limit value.

20. The method of claim 17, wherein the copy of the hop limit value limits a number of hops the transmitted packet can have before reaching its destination.