Path control apparatus and table updating method

• US 20080025311A1
• Filed: 11/29/2006
• Published: 01/31/2008
• Est. Priority Date: 07/31/2006
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Okagawa, Hiroshi
• Granted Patent: US 7,822,034 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A receiving unit receives a frame from any one of a plurality of ports. When it is determined that there is no entry to which a correspondence relation for a transmission-source address of the received frame can be registered in a management table, a selecting unit detects an indicator bit located at an oldest generation in a bit string obtained by rearranging generation-management bit strings of all entries of the management table, and selects an entry corresponding to the detected indicator bit as an overwriting target entry. An updating unit registers the correspondence relation to the selected overwriting target entry.

Claims

1. A path control apparatus that controls a communication path by relaying a frame including a transmission-source address and a transmission-destination address, the path control apparatus comprising:

a receiving unit that includes a plurality of ports, and receives the frame from any one of the ports;

a storage unit that stores therein a management table that includes

a correspondence relation between the transmission-source address of the frame and a port through which the frame is received in each entry, and

a generation-management bit string in which an indicator bit is arranged at a position corresponding to a time elapsed since the entry is updated for each entry;

a determining unit that determines whether there is an entry to which the correspondence relation for the transmission-source address of the received frame can be registered;

a selecting unit that, when the determining unit determines that there is no entry to which the correspondence relation can be registered, detects the indicator bit located at a position indicating a longest time elapsed in a bit string obtained by rearranging the generation-management bit strings of all entries according to the time elapsed, and selects an entry corresponding to the detected indicator bit as an overwriting target entry to be overwritten; and

an updating unit that updates the management table in the storage unit by registering the correspondence relation between the transmission-source address of the frame and the port through which the frame is received to the selected overwriting target entry.

2. The path control apparatus according to claim 1, wherein

the determining unit includes a searching unit that searches the transmission-source address of the frame from the management table, and

when there is an entry to which the transmission-source address is registered, the determining unit determines the entry as the entry to which the correspondence relation can be registered.

3. The path control apparatus according to claim 2, wherein the updating unit registers the port through which the frame is received to the entry that is determined to be the entry to which the correspondence relation can be registered by the determining unit.

4. The path control apparatus according to claim 3, wherein the updating unit changes a position of the indicator bit in the generation-management bit strings of the entry that is determined to be the entry to which the correspondence relation can be registered by the determining unit to a bit of generation indicating a shortest time elapsed.

5. The path control apparatus according to claim 1, wherein

the management table holds a vacancy-management bit, which indicates whether an entry is vacant, in association with each entry, and

when there is an entry that is indicated to be a vacant entry by the vacancy-management bit, the determining unit determines the entry as the entry to which the correspondence relation can be registered.

6. The path control apparatus according to claim 5, wherein the updating unit registers the correspondence relation between the transmission-source address of the frame and the port through which the frame is received to the vacant entry that is determined to be the entry to which the correspondence relation can be registered by the determining unit.

7. The path control apparatus according to claim 6, wherein the updating unit sets a bit of generation indicating a shortest time elapsed in the generation-management bit string of the vacant entry, which is determined to be the entry to which the correspondence relation can be registered by the determining unit, as the indicator bit, and changes the vacancy-management bit.

8. The path control apparatus according to claim 1, wherein the selecting unit rearranges the generation-management bit strings of all entries by coupling bits of all entries for each generation having an equal time elapsed.

9. The path control apparatus according to claim 1, wherein the selecting unit detects the indicator bit after masking a bit portion of the generation indicating a shortest time elapsed from among the bit string obtained by rearranging the generation-management bit string.

10. The path control apparatus according to claim 9, wherein the selecting unit performs a masking of hiding a bit corresponding to the indicator bit that has been previously detected in the bit portion of the generation indicating the shortest time elapsed.

11. A table updating method for a path control apparatus that controls a communication path by relaying a frame including a transmission-source address and a transmission-destination address, the table updating method comprising:

receiving the frame from any one of a plurality of ports;

determining whether there is an entry to which a correspondence relation for the transmission-source address of the frame can be registered in a management table that stores the correspondence relation between the transmission-source address of the frame and a port through which the frame is received in each entry, and holds a generation-management bit string in which an indicator bit is arranged at a position corresponding to a time elapsed since the entry is updated for each entry;

detecting, when it is determined that there is no entry to which the correspondence relation can be registered at the determining, the indicator bit located at a position indicating a longest time elapsed in a bit string obtained by rearranging the generation-management bit strings of all entries according to the time elapsed;

selecting an entry corresponding to the detected indicator bit as an overwriting target entry to be overwritten; and

updating the management table by registering the correspondence relation between the transmission-source address of the received frame and the port through which the frame is received to the selected overwriting target entry.

12. The table updating method according to claim 11, wherein

the determining includes searching the transmission-source address of the received frame from the management table, and

when there is an entry to which the transmission-source address is registered, the determining includes determining the entry as the entry to which the correspondence relation can be registered.

13. The table updating method according to claim 12, wherein the updating includes registering the port through which the frame is received to the entry that is determined to be the entry to which the correspondence relation can be registered at the determining.

14. The table updating method according to claim 13, wherein the updating includes changing a position of the indicator bit in the generation-management bit strings of the entry that is determined to be the entry to which the correspondence relation can be registered at the determining to a bit of generation indicating a shortest time elapsed.

15. The table updating method according to claim 11, wherein

the management table holds a vacancy-management bit, which indicates whether an entry is vacant, in association with each entry, and

when there is an entry that is indicated to be a vacant entry by the vacancy-management bit, the determining includes determining the entry as the entry to which the correspondence relation can be registered.

16. The table updating method according to claim 15, wherein the updating includes registering the correspondence relation between the transmission-source address of the received frame and the port through which the frame is received to the vacant entry that is determined to be the entry to which the correspondence relation can be registered at the determining.

17. The table updating method according to claim 16, wherein

the updating includes

setting a bit of generation indicating a shortest time elapsed in the generation-management bit string of the vacant entry, which is determined to be the entry to which the correspondence relation can be registered at the determining, as the indicator bit;

and

changing the vacancy-management bit.

18. The table updating method according to claim 11, wherein the selecting includes rearranging the generation-management bit strings of all entries by coupling bits of all entries for each generation having an equal time elapsed.

19. The table updating method according to claim 11, wherein the selecting includes detecting the indicator bit after masking a bit portion of the generation indicating a shortest time elapsed from among the bit string obtained by rearranging the generation-management bit string.

20. The table updating method according to claim 19, wherein the selecting includes performing a masking of hiding a bit corresponding to the indicator bit that has been previously detected in the bit portion of the generation indicating the shortest time elapsed.