US 7,460,538 B2 · Communication control apparatus and method for searching an internet protocol address

Abstract

A communication control apparatus includes search information associated with a tree structure. A mask prefix is associated with at least one entry, each entry including information on the mask length of a mask prefix associated therewith and a sort key. Each entry is assigned to a node in the tree structure according to a sorting order. Each node is linked to a different node at the next lower hierarchy via a branch based on the entry of the node. A destination address of the packet received is first extracted, and a search target node specified by a search control for an entry having information on the best matched prefix of the extracted address is then searched for. After completion of the node-by-node search process, a transfer route is determined for the packet received based on the longest prefix amongst the most appropriate prefixes of all the current search target nodes.

Claims19

Dependent claims

A communication control apparatus, comprising:

a storage device for storing search information to determine a subsequent transfer route for a packet received by way of its destination address;
and
a route search device to search for a transfer route for said packet received based on said search information, wherein said search information is associated with a tree structure, each node in said tree structure having at least one entry, a mask prefix associated with said at least one entry, wherein each entry includes information on the number of bits of said mask prefix associated therewith, and a sort key, and wherein the number of bits of said sort key is set to be greater than or equal to a longest mask length amongst the mask lengths of all said mask prefixes;
a bit string divided into an upper side bit string field and a lower side bit string field, wherein the upper side bit string field of each of said sort keys is to match said mask prefix associated with an entry having said sort key wherein entries are assigned to predetermined nodes of said tree structure based on a sort order of their sort keys;
each node having an entry list in which multiple entries included therein are sorted based on their sort keys;
and each node except leaf nodes are linked via each branch to relate each entry in the entry list of said node to each node at the next lower hierarchy.

3 more elements

A communication control apparatus comprising:

a storage device for storing search information to determine a next transfer route for a packet received by way of its destination address;
and
a route search device to search for a transfer route for the packet received based on said search information, wherein said search information is comprised of a first and second information field, wherein said first and second information fields are based on a predetermined integer u, to define respective bit numbers of a mask prefix arranged in descending order from the most significant bit (MSB) to the least significant bit (LSB), a short and a long mask prefix consisting of at most u bits and a mask prefix consisting of at least (u+1) bits, referred to as a short mask prefix and a long mask prefix, respectively;
an upper side mask prefix field from the first bit to the uth bit and a lower side mask prefix field from the (u+1)th bit to the last bit of said mask prefix, said long mask prefix having the same upper side mask prefix field forming a mask prefix group and said first information field includes information related to the short mask prefix and the upper side mask prefix field,
said first information field is stored in a table, said table including:
a) u-bit entries with sort keys different from one another;
b) entries in each table that include first and second table entries;
c) all the bits from the first to the wth bit (where w≦u is an integer) of the sort key of the first table entry that are identical to the short mask prefix associated with the first table entry;
and d) all the bits of the sort key of the second table entry that are identical to the upper side mask prefix field associated with the second table entry;
said second information field includes information related to the lower side mask prefix field, said second information field is stored in at least one tree structure, each tree structure is associated with each mask prefix group, and where a link is established to the tree structure from an entry having a sort key equal to the upper side mask prefix field of a long mask prefix belonging to the associated mask prefix group and included in said table, each node in each tree structure has at least one entry, the lower side mask prefix field of each long mask prefix is associated with at least one entry, each entry in the tree structure includes information on the number of bits of the lower side mask prefix field associated therewith, and a sort key;
and wherein
the number of bits of an entry in the tree structure is set to be greater than or equal to the longest lower side mask prefix field amongst the lower side mask prefix field mask lengths of all the lower side mask prefix fields;
the upper side bit string field of each sort key is set to match the lower side mask prefix field associated with an entry having said sort key;
entries are assigned to predetermined nodes of said tree structure based on a sort order of their sort keys;
each node having an entry list in which multiple entries included therein are sorted based on their sort keys;
each node except leaf nodes being linked via each branch related to each entry in the entry list of the node to each node at the next lower hierarchy;
said route search device comprising:
means for extracting the destination address of a packet received from the packet received;
a table route search device, wherein a bit string field from the first to the uth bits and abit string field of (u+1)th bit and subsequent bits, said table route search device searching for a transfer route for the packet received related to the currently extracted destination address by comparing each entry in the table with the first extracted address field;
a tree structure route search device searching for a transfer route for the packet received based on the currently extracted destination address by comparing each entry in the tree structure with the second extracted address field;
a controller for controlling said table route search device and said tree structure route search device;
and
means for determining the transfer route for the packet received related to the currently extracted destination address based on search results of said table route search device and said tree structure route search device;
said table route search device comprising:
means for searching for an entry having a sort key matching the upper side bit string field of the first extracted address field as a matching entry;
and
means for notifying said controller of the linked tree structure if a link from the appropriate entry retrieved by said search means to a predetermined tree structure is set,
said tree structure route search device comprising:
inside-node matching entry search means for searching each search target node of said tree structure for an entry having information on the lower side mask prefix field that matches the upper side bit string field of the second extracted address field in the search target node as a matching entry to determine if there is only one matching entry, the only one entry to become the inside-node matching entry and determine if there are multiple matching entries, an entry having information on the lower side mask prefix field with the longest bit length amongst the matching entries to become the inside-node matching entry;
search control means for specifying a search target node to said inside-node matching entry search means, the search control means selecting a link based on a comparison of the sort key of each entry in each of said search target node with the second extracted address field to determine a node related to the selected link to be the next search target node and determining that the node-by-node search process is terminated if said link does not exist;
and a lower side mask prefix field determining means for determining the lower side mask prefix field with the longest bit length amongst the lower side mask prefix field corresponding to multiple inside-node matching entries related to the second extracted address field after the node-by-node search process is terminated;
said controller comprising:
first directing means for directing the table route search means to execute a search process for the currently extracted destination address which has been extracted by said address extracting means prior to directing said tree structure route search means;
second directing means for directing said tree structure route search means to execute a search process related to the currently extracted destination address by specifying the search target tree structure notified by said notification means, when notified by said notification means of said table route search means;
and
final determination means for determining a transfer route for the packet received based on its currently extracted destination address utilizing the short mask prefix related to the appropriate entry retrieved by said search means of said table route search means, if said second directing means does not direct said tree structure route search means to execute a search process;
and determining if said second directing means directs said tree structure route search means to execute said search process, a long mask prefix which is based on the upper side mask prefix field related to an entry in the link-source table in the tree structure, which was determined to be the search target tree structure by said tree structure route search means, and the lower side mask prefix field determined by said lower side mask prefix field determining means of said tree structure route search means to be a transfer route for the packet received related to the currently extracted destination address.

34 more elements

A communication control method for storing search information to determine the next transfer route for a packet received based on its destination address, and searching for a transfer route for the packet received based on said search information, wherein

said search information is associated with a tree structure;
each node in the tree structure having at least one entry;
each mask prefix being associated with at least one entry;
each entry including information on the number of bits of a mask prefix associated therewith, and a sort key;
the number of bits of the sort key being set to be greater than or equal to the longest mask length amongst the mask lengths of all the mask prefixes;
the upper side bit string field of each sort key being set to match the mask prefix associated with the entry having the sort key;
entries being assigned to predetermined nodes of said tree structure based on the sort order of the sort keys;
and each node having an entry list in which multiple entries included therein are sorted based on their sort keys;
each node except leaf nodes being linked by a branch related to each entry in the entry list of the node to each node at the next lower hierarchy;
the communication control method comprising the steps of:
extracting a destination address of a packet received from the packet received based on its destination address;
searching for each search target node of an entry having information on a mask prefix that matches the upper side bit string field of the extracted address in the search target node, as a matching entry to determine if there is only one matching entry, the only one matching entry to become the inside-node matching entry, and to determine if there are multiple matching entries, an entry having information on a mask prefix with the longest mask length amongst the matching entries to become the inside-node matching entry;
determining a search target node at said inside-node matching entry search step, the search control step selecting a link based on a comparison of the sort key of each entry in each search target node with the extracted address to determine the node related to the selected link to be the next search target node and determining that the node-by-node search process is terminated if a link does not exist;
and
determining a transfer route for the packet received based on its extracting address, said determination being based on a mask prefix with the longest mask length amongst the mask prefixes associated with multiple inside-node matching entries related to the extracted address, after the node-by-node search process is terminated.

12 more elements

A communication control method for storing search information to determine the next transfer route for a packet received from its destination address, and searching for a transfer route for the packet received based on said search information, wherein

said search information is comprised of a first and a second information field;
a predetermined integer u and respective bit numbers of a mask prefix arranged in the order from the MSB to the LSB;
a mask prefix with at most u bits and a mask prefix with at least u+1 bits, referred to a short mask prefix and a long mask prefix, respectively;
a field from the first to the uth bits and a field from the (u+1)th to the last bit of the long mask prefix referred to the upper side mask prefix field and the lower side mask prefix field, respectively;
long mask prefixes having the same upper side mask prefix field to form a mask prefix group;
said first information field including information related to a short mask prefix and the upper side mask prefix field;
said first information field being stored in a table;
said table including u-bit entries with sort keys different from one another;
the entries included in each table consisting of a first and a second table entries;
all the bit values from the first to the wth (where w<u is an integer) of the sort key of the first table entry that are identical to the short mask prefix associated with the first table entry;
and all the bits of the sort key of the second table entry that are identical to the upper side mask prefix field associated with the second table entry;
said second information field including information related to the lower side mask prefix;
said second information field being stored in at least one tree structure;
each tree structure is associated with each mask prefix group, and a link established to the tree structure from an entry having a sort key equal to the upper side mask prefix field of a long mask prefix belonging to the associated mask prefix group and included in said table;
each node in each tree structure has at least one entry;
the lower side mask prefix field of each long mask prefix is associated with at least one entry;
each entry in the tree structure includes information on the number of bits of the lower side mask prefix field associated therewith, and a sort key;
the number of bits of an entry in the tree structure is set to be greater than or equal to the longest lower side mask prefix field mask length amongst the lower side mask prefix field mask lengths of all the lower side mask prefix fields;
the upper side bit string field of each sort key is set to match the lower side mask prefix field associated with an entry having the sort key;
entries are assigned to predetermined nodes of said tree structure based on the sort order of their sort keys;
each node has an entry list in which multiple entries included therein are sorted based on their sort keys;
each node except leaf nodes are linked via each branch that are related to each entry in the entry list of the node to each node at the next lower hierarchy;
the communication control method comprising the steps of:
extracting a destination address of a packet received from the packet received;
searching for a transfer route for the packet received from its currently extracted destination address based on a comparison of each entry in the table with the first extracted address field wherein a bit string field from the first to the uth bit and a bit string field of (u+1)th bits and subsequent bits are referred to as a first and a second extracted address field, respectively;
searching for a transfer route for the packet received from its currently extracted destination address based on a comparison of each entry in the tree structure with the second extracted address field;
controlling said table route search step and said tree structure route search step;
and
determining a transfer route for the packet received from its currently extracted destination address based on search results of said table route search step and said tree structure route search step;
said table route search step comprising the steps of:
searching for an entry having a sort key matching the upper side bit string field of the first extracted address field as a matching entry;
and
notifying said control step to that effect and the linked tree structure if a link from the appropriate entry retrieved at said search step to a predetermined tree structure is set;
said tree structure route search step further comprising the steps of:
searching each search target node of said tree structure for an entry having information on the lower side mask prefix field that matches the upper side bit string field of the second extracted address field in the search target node, as a matching entry to determine if there is only one matching entry, the only one matching entry to become the inside-node matching entry and determine if there are multiple matching entries, an entry having information on the lower side mask prefix field with the longest bit length amongst the matching entries to become the inside-node matching entry;
determining a search target node at said inside-node matching entry search step, the search control step selecting a link based on comparison of the sort key of each entry in each search target node with the second extracted address field to determine a node related to the selected link to be the next search target node and determining that the node-by-node search process is terminated if a link does not exist;
and
determining the lower side mask prefix field with the longest bit length among the lower side mask prefix field corresponding to multiple inside-node matching entries related to the second extracted address field, after the node-by-node search process is terminated;
said control step further comprising the steps of:
a first directing step for executing a search process at the table transfer search step for the currently extracted destination address which has been extracted at said address extracting step, prior to execution of a search process at said tree structure route search step;
a second directing step for directing said tree structure route search step to execute a search process related to the currently extracted destination address by specifying the search target tree structure notified by said notification step when notified by said notification step of said table route search step;
and
determining a transfer route for the packet received related to the currently extracted destination address, based on the short mask prefix related to the appropriate entry retrieved at the search step of said table route search step if execution of a search process at said tree structure route search step has not been directed at said second directing step;
and
determining a long mask prefix based on the upper side mask prefix field related to an entry in the link-source table in the tree structure determined to be a search target tree structure by said tree structure route search step and the lower side mask prefix field determined by said lower side mask prefix field determining step of said tree structure route search step to be a transfer route for the packet received related to the currently extracted destination address if execution of a search process at the tree structure route search step has been directed at said second directing step.

42 more elements

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing a communication control method for storing search information to determine the next transfer route for a packet received based on its destination address, and searching for a transfer route for the packet received based on said search information, wherein said search information is associated with a tree structure;

each node in the tree structure having at least one entry;
each mask prefix being associated with at least one entry;
each entry including information on the number of bits of a mask prefix associated therewith, and a sort key;
the number of bits of the sort key being set to be greater than or equal to the longest mask length amongst the mask lengths of all the mask prefixes;
an upper side bit string field of each sort key being set to match the mask prefix associated with the entry having the sort key;
entries being assigned to predetermined nodes of said tree structure based on the sort order of the sort keys;
and each node having an entry list in which multiple entries included therein are sorted based on their sort keys;
each node except leaf nodes being linked by a branch related to each entry in the entry list of the node to each node at the next lower hierarchy;
said communication control method comprising the steps of:
extracting a destination address of a packet received from the packet received based on its destination address;
searching for each search target node of an entry having information on a mask prefix that matches the upper side bit string field of the extracted address in the search target node, as a matching entry to determine if there is only one matching entry, the only one matching entry to become an inside-node matching entry, and to determine if there are multiple matching entries, an entry having information on a mask prefix with the longest mask length amongst the matching entries to become the inside-node matching entry;
determining a search target node at said inside-node matching entry search step, the search control step selecting a link based on a comparison of the sort key of each entry in each search target node with the extracted address to determine the node related to the selected link to be the next search target node and determining that the node-by-node search process is terminated if a link does not exist;
and
determining a transfer route for the packet received based on its extracting address, said determination being based on a mask prefix with the longest mask length amongst the mask prefixes associated with multiple inside-node matching entries related to the extracted address, a after node-by-node search process is terminated.

11 more elements

Dependencies are inferred from the claim text.

Communication control apparatus and method for searching an internet protocol address

Life of this patent

Communication control apparatus and method for searching an internet protocol address

Life of this patent

Abstract

Claims19