# US 2006/0078333 A1 · Protocol speed increasing device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0078333 A1
- Document ID: US20060078333A1
- Status: Published application
- Kind: A1
- Application number: 10/531,436
- Filed: 2004-08-18
- Published: 2006-04-13
- Earliest claimed: 2003-08-20
- Assignees: Nippon Telegraph and Telephone Corporation
- Inventors: Masanori Uga; Takashi Kurimoto; Michihiro Aoki
- Web page: https://patentgrep.com/patent/US20060078333A1

## CPC

- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L 45/54: {Organization of routing tables}
- H04L 45/7453: using hashing
- G11C 15/00: Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

A routing table generating unit that generates a routing table describing a next hop to which a packet is to be sent according to a destination address of the packet that is input via an input channel, including a ternary content addressable memory (TCAM); an external memory; a unit that classifies items in information that is received; and a unit that stores an item that uniquely identifies the information among the classified items in the TCAM and stores the rest of the items to the external memory.

## Claims

### Claim 1

A routing table generating unit that generates a routing table describing a next hop to which a packet is to be sent according to a destination address of the packet that is input via an input channel, comprising
a ternary content addressable memory (TCAM);
an external memory;
a unit that classifies items in information that is received; and
a unit that stores an item that uniquely identifies the information among the classified items in the TCAM and stores the rest of the items to the external memory.

### Claim 2 (depends on 1)

The routing table generating unit according to claim 1, further comprising:
a unit that, upon receiving new information, prior to storing the new information, searches the information stored in the TCAM using, as a search key, the item that uniquely identifies the information among the classified items;
a unit that initiates the storing process by the storing unit when the item that uniquely identifies the newly received information and the item that uniquely identifies the information that has been stored in the TCAM do not match in the search; and
a unit that, when the item that uniquely identifies the newly received information and the item that uniquely identifies the information that has been stored in the TCAM match in the search, determines whether the newly received information is older than corresponding information stored in the external memory that corresponds to the item that uniquely identifies the newly received information.

### Claim 3 (depends on 2)

The routing table generating unit according to claim 2, further comprising:
a unit that ignores the newly received information, when it is determined by the comparing unit that the newly received information is as old as or older than the corresponding information stored in the external memory; and
a unit that, when it is determined by the comparing unit that the newly received information is newer than the corresponding information stored in the external memory, updates the corresponding information stored in the external memory with the newly received information.

### Claim 4 (depends on 1)

The routing table generating unit according to claim 1, further comprising a unit that, upon an arrival of an arrived packet, searches for a shortest path using the information stored in the TCAM and the information stored in the external memory based on a destination address of the arrived packet.

### Claim 5 (depends on 4)

The routing table generating unit according to claim 4, further comprising a unit that determines a next hop to which the arrived packet is to be sent based on the search of the shortest path.

### Claim 6

A program used in a routing table generating unit that generates a routing table describing a next hop to which a packet is to be sent according to a destination address of the packet that is input via an input channel, the program, when installed in a computing device, providing the computing device with:
a function that classifies items in information that is received; and
a function that stores an item that uniquely identifies the information among the classified items in a TCAM and stores the rest of the items in an external memory.

### Claim 7 (depends on 6)

The program according to claim 6, further comprises:
a function that, upon receiving new information, prior to storing the new information, searches the information stored in the TCAM using, as a search key, the item that uniquely identifies the information among the classified items;
a function that initiates the storing process by the storing function when the item that uniquely identifies the newly received information and the item that uniquely identifies the information that has been stored in the TCAM do not match in the search; and
a function that, when the item that uniquely identifies the newly received information and the item that uniquely identifies the information that has been stored in the TCAM match in the search, determines whether the newly received information is older than corresponding information stored in the external memory that corresponds to the item that uniquely identifies the newly received information.

### Claim 8 (depends on 7)

The program according to claim 7, further providing:
a function that ignores that newly received information, when it is determined by the comparing function that the newly received information is as old as or older than the corresponding information stored in the external memory; and
a function that, when it is determined by the comparing function that the newly received information is newer than the corresponding information stored in the external memory, updates the corresponding information stored in the external memory with the newly received information.

### Claim 9 (depends on 6)

The program according to claim 6, further providing a function that, upon an arrival of an arrived packet, searches for a shortest path using the information stored in the TCAM and the information stored in the external memory based on a destination address of the arrived packet.

### Claim 10 (depends on 9)

The program according to claim 9, further providing a function that determines a next hop to which the arrived packet is to be sent based on the search of the shortest path.

### Claim 11 (depends on 6)

A recording medium readable from the computing device, which records the program according to claim 6.

### Claim 12

A link state database (LSDB) search unit that is provided in an interface that processes a packet that is input via an input channel, provided in a packet transfer device, comprising:
a unit that collects received information using a control packet of a routing protocol;
a unit that stores at least a portion of items in the received information collected; and
a unit that compares the stored information and information on the at least a portion of item in newly received information collected by the collecting unit to determine whether the newly received information is new or old.

### Claim 13 (depends on 12)

The LSDB search unit according to claim 12, further comprising a unit that, upon an arrival of a newly arrived control packet containing the newly received information, transfers the newly arrived control packet containing the newly received information to a routing device when information on the at least a portion of item in the newly received information is newer than the information stored based on the decision made by the comparing unit, and discards the newly arrived control packet containing the newly received information when the information on the at least a portion of item in the newly received information is as old as or older than the information stored.

### Claim 14 (depends on 13)

The LSDB search unit according to claim 13, further comprising a unit that transfers the information on the at least a portion of item in the control packet that has been transferred to the routing device to an LSDB search unit in another interface when the information on the at least a portion of item in the newly received information is newer than the information stored based on the decision made by the comparing unit.

### Claim 15 (depends on 14)

The LSDB search unit according to claim 14, further comprising:
a unit that, upon an arrival of a newly arrived control packet containing the newly received information, transfers information on at least a portion of item in the newly arrived control packet containing a newly received information to an LSDB search unit in another interface when the information on the at least a portion of item in the newly received information is newer than the information stored based on the decision made by the comparing unit; and
a unit that stores information on at least a portion of item in a control packet that is transferred from another unit.

### Claim 16

A program used in a link state database (LSDB) search unit that is provided in an interface that processes a packet that is input via an input channel, provided in a packet transfer device, the program, when installed in a computing device, providing the computing device with:
a function that collects received information using a control packet of a routing protocol;
a function that stores at least a portion of the received information collected; and
a function that compares the stored information and at least a portion of the newly received information collected by the collecting function to determine whether the received information is new or old.

### Claim 17 (depends on 16)

The program according to claim 16, further providing a function that, upon an arrival of a newly arrived control packet containing the newly received information, transfers the newly arrived control packet containing the newly received information to a routing device when at least a portion of information in the newly received information is newer than the information stored based on the decision made by the comparing function, and discards the newly arrived control packet containing the newly received information when the at least a portion of information in the newly received information is as old as or older than the information stored.

### Claim 18 (depends on 17)

The program according to claim 17, further providing a function that transfers the at least a portion of the information in the control packet that has been transferred to the routing device to an LSDB search unit in another interface when the at least a portion of the information in the newly received information is newer than the information stored based on the decision made by the comparing function.

### Claim 19 (depends on 18)

The program according to claim 18, further comprises:
a function that, upon an arrival of a newly arrived control packet containing the newly received information, transfers information on at least a portion of item in a newly arrived control packet containing the newly received information to an LSDB search unit in another interface when the at least a portion of the information in the newly received information is newer than the information stored based on the decision made by the comparing function; and
a function that stores information on at least a portion of item in a control packet that is transferred from another function.

### Claim 20 (depends on 16)

A recording medium readable from the computing device, which records the program according to claim 16.
