FAST LOOKUP AND UPDATE OF CURRENT HOP LIMIT

• US 20150281049A1
• Filed: 03/31/2014
• Published: 10/01/2015
• 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
• Granted Patent: US 9,667,528 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 connection, wherein the search tree comprises a plurality of nodes, each node pointing to a data structure of a corresponding connection;

updating a copy of a particular parameter that is cached in the data structure pointed to by the located node;

transmitting a data packet for the particular connection by retrieving said data structure for the particular connection and inserting the updated copy of the particular parameter into the data packet.

2. The method of claim 1, wherein the nodes of the search tree correspond to 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, wherein each search tree is for updating copies of the particular parameter cached in data structures of connections that are established over the corresponding communications interface.

4. The method of claim 1, wherein the particular parameter is a current hop limit value that 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, wherein the current hop limit value is inserted into the IPv6 header.

6. The method of claim 1, wherein traversing the search tree to locate the node that corresponds to the particular connection requires less than log(n) traversals, 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 (AVL) 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 traversing the search tree to locate a node that corresponds to the particular connection is based on an index derived from a five-tuple identifier of the particular connection.

11. A communications device comprising:

a transmit module for assembling packets for transmission for a plurality of different connections, wherein assembling a packet for a connection comprises retrieving a data structure for the connection, wherein each data structure for a connection embeds a copy of a current hop limit value; and

a hop limit update module for updating the copies of the current hop limit value that are embedded in the data structures of the plurality of different connections.

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

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

14. The communications device of claim 13, where the search tree of a communications interface is for locating and updating copies of the hop limit of that communications interface.

15. The communications device of claim 13, wherein each node of a search tree of a particular communications interface correspond to a 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 (AVL) binary search tree.

17. A method for transmitting packets from a communications device, the program executable on one or more processing units, the comprising:

transmitting packets for a plurality of different connections over a communications interface, each connection associated with a corresponding connection data structure, each connection data structure comprising a copy of a particular parameter of the communications interface, wherein transmitting a packet for particular connection comprises retrieving the corresponding connection data structure;

receiving a value for the particular parameter of the communications interface; and

updating the copies of the particular parameter in each connection data structure of the plurality of connections to the received value.

18. The method of claim 17, wherein updating the copy of the particular parameter comprises using a search tree to locate copies of the particular parameter.

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

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