Neighbor lookup operations in a network node

Patent metadata

Field	Value
Publication number	US-9270636-B2
Application number	US-201414246160-A
Country	US
Kind code	B2
Filing date	Apr 7, 2014
Priority date	Apr 7, 2014
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

Abstract

A network node maintains a neighbor data structure in the form of a hash table containing multiple buckets for storing mapping entries, with each entry specifying a local address corresponding to a global address. The table is based on a hash function that generates a corresponding hash value for each global address. Each bucket is associated with a unique hash value and is implemented as a corresponding balanced tree containing a corresponding set of nodes, with each node storing a corresponding mapping entry. Upon receiving a lookup request containing a first global address, the node determines a first bucket by applying the hash function to the first global address, and then traverses a first tree corresponding to the first bucket to find a first entry having a global address equaling the first global address. Concurrent non-blocking access is permitted to various portions of the tree during changes in the tree.

First claim

What is claimed is:

1. A method performed in a network node, said method comprising:
maintaining a neighbor data structure for storing mapping entries, each mapping entry specifying a local address corresponding to a global address, said neighbor data structure being in the form of a hash table containing a plurality of buckets,
said hash table being based on a hash function that generates a corresponding hash value for each global address, wherein each bucket is associated with a unique hash value,
wherein each bucket of said plurality of buckets is implemented as a corresponding balanced tree of a plurality of balanced trees, each balanced tree containing a corresponding set of nodes, with each node storing a corresponding mapping entry,
wherein, upon applying of said hash function, corresponding global address of mapping entries in each balanced tree generates the unique hash value associated with the bucket;
receiving a lookup request containing a first global address;
determining a first bucket of said plurality of buckets by applying said hash function to said first global address; and
traversing a first balanced tree corresponding to said first bucket to find a first mapping entry having a global address equaling said first global address.

2. The method of claim 1 , wherein said first global address is an address of a next network node to which a packet is to be forwarded, said method further comprising:
examining said first mapping entry to identify a local address; and
forwarding said packet to said next network node on a local network using said local address.

3. The method of claim 2 , wherein said network node is a router, said next network node is an end system, wherein said first global address is a destination global address of said end system.

4. The method of claim 2 , wherein said network node is a first end system, said next network node is a second end system, wherein said first global address is a destination global address of said second end system.

5. The method of claim 1 , further comprising:
forming a second mapping entry containing a second global address and a second local address;
hashing said second global address to a first hash value using said hash function, said first hash value equaling the hash value associated with said first bucket; and
adding said second mapping entry as a second node to said first balanced tree corresponding to said first bucket.

6. The method of claim 5 , wherein said adding comprises:
determining whether said first hash value for said second global address causes a collision in said hash table,
wherein said adding adds said second node as a root of said first balanced tree if said collision is not determined, and adds said second node below said root otherwise.

7. The method of claim 6 , wherein said adding said second node below said root comprises:
identifying a parent node to which said second node is to be added as a child according to an order required by said first balanced tree;
checking whether inclusion of said second node as said child of said parent node would cause imbalance in said first balanced tree; and
if said imbalance is caused, changing the topology of said first balanced tree, with the addition of said second node to ensure that the resulting tree is again balanced.

8. The method of claim 5 , further comprising:
receiving a second request to change a mapping entry in a third node of said first balanced tree and a third request to lookup said mapping entry in said third node, wherein said second request and said third request are respectively processed by a first execution entity and a second executing entity executing concurrently in said network node; and
permitting non-blocking access to said third node to both of said first execution entity and said second execution entity, thereby enabling the change of said mapping entry and said lookup to be performed concurrently.

9. A non-transitory machine readable medium storing one or more sequences of instructions for enabling a network node to perform neighbor lookup operations, wherein execution of said one or more instructions by one or more processors contained in said network node enables said network node to perform the actions of:
maintaining a neighbor data structure for storing mapping entries, each mapping entry specifying a local address corresponding to a global address, said neighbor data structure being in the form of a hash table containing a plurality of buckets,
said hash table being based on a hash function that generates a corresponding hash value for each global address, wherein each bucket is associated with a unique hash value,
wherein each bucket of said plurality of buckets is implemented as a corresponding balanced tree of a plurality of balanced trees, each balanced tree containing a corresponding set of nodes, with each node storing a corresponding mapping entry,
wherein, upon applying of said hash function, corresponding global address of mapping entries in each balanced tree generates the unique hash value associated with the bucket;
receiving a lookup request containing a first global address;
determining a first bucket of said plurality of buckets by applying said hash function to said first global address; and
traversing a first balanced tree corresponding to said first bucket to find a first mapping entry having a global address equaling said first global address.

10. The non-transitory machine readable medium of claim 9 , wherein said first global address is an address of a next network node to which a packet is to be forwarded, further comprising one or more instructions for:
examining said first mapping entry to identify a local address; and
forwarding said packet to said next network node on a local network using said local address.

11. The non-transitory machine readable medium of claim 10 , wherein said network node is a router, said next network node is an end system, wherein said first global address is a destination global address of said end system.

12. The non-transitory machine readable medium of claim 10 , wherein said network node is a first end system, said next network node is a second end system, wherein said first global address is a destination global address of said second end system.

13. The non-transitory machine readable medium of claim 9 , further comprising one or more instructions for:
forming a second mapping entry containing a second global address and a second local address;
hashing said second global address to a first hash value using said hash function, said first hash value equaling the hash value associated with said first bucket; and
adding said second mapping entry as a second node to said first balanced tree corresponding to said first bucket.

14. The non-transitory machine readable medium of claim 13 , wherein said adding comprises:
determining whether said first hash value for said second global address causes a collision in said hash table,
wherein said adding adds said second node as a root of said first balanced tree if said collision is not determined, and adds said second node below said root otherwise.

15. The non-transitory machine readable medium of claim 14 , wherein said adding said second node below said root comprises:
identifying a parent node to which said second node is to be added as a child according to an order required by said first balanced tree;
checking whether inclusion of said second node as said child of said parent node would cause imbalance in said first balanced tree; and
if said imbalance is caused, changing the topology of said first balanced

Assignees

• Oracle Int Corp

Inventors

• Narasimhamurthy Giridhar
• Gosukonda Bharadwaj Raghavendra

Classifications

• H04L61/2046

  Electricity · mapped topic

• H04W28/12

  using signalling between network elements · CPC title

• H04L61/255 Primary

  Maintenance or indexing of mapping tables · CPC title

• H04L45/7453 Primary

  using hashing · CPC title

• H04L2101/622

  Layer-2 addresses, e.g. medium access control [MAC] addresses · CPC title