Path controls apparatus and table updating method

• US 7,822,034 B2
• Filed: 11/29/2006
• Issued: 10/26/2010
• Est. Priority Date: 07/31/2006
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Okagawa, Hiroshi
• Primary Examiner(s): Patel; Jayanti K
• Assistant Examiner(s): Houshmand; Hooman
• Application Number:
  US11/605,356
• Publication Number:
  US 20080025311A1
• Time in Patent Office: 1,427 Days
• Field of Search: None
• 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 for each entry including a plurality of generation bits indicating a plurality of generations, wherein one of the generation bits for an entry corresponds to a time elapsed since the entry was updated and is set as an indicator bit for the 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 an indicator bit located at a position indicating a longest time elapsed in a bit string that is obtained by coupling the generation bits for all entries by the generations, and selects an entry corresponding to the detected indicator bit as an overwriting target entry to be overwritten; and

an updating unit that registers 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 in the management table in the storage unit, and changes a position of the indicator bit in the generation-management bit strings of the selected overwriting target entry to a generation bit of a generation indicating a shortest time elapsed.

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 to a generation bit of a generation indicating a shortest time elapsed, when the entry is determined to be the entry to which the correspondence relation can be registered by the determining unit.

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 generation bit of a 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 detects the indicator bit after masking the generation bits of a generation indicating a shortest time elapsed from among the bit string obtained by coupling the generation bits.

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

10. 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 for each entry including a plurality of generation bits indicating a plurality of generations, wherein one of the generation bits for an entry corresponds to a time elapsed since the entry was updated and is set as an indicator bit for the entry;

detecting, when it is determined that there is no entry to which the correspondence relation can be registered at the determining, an indicator bit located at a position indicating a longest time elapsed in a bit string that is obtained by coupling the generation bits for all entries by the generations;

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

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 in the management table; and

changing a position of the indicator bit in the generation-management bit strings of the selected overwriting target entry to a generation bit of a generation indicating a shortest time elapsed.

11. The table updating method according to claim 10, 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.

12. The table updating method according to claim 11, 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.

13. The table updating method according to claim 12, wherein the updating includes changing a position of the indicator bit in the generation-management bit strings of the entry to a generation bit of a generation indicating a shortest time elapsed, when the entry 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 10, 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.

15. The table updating method according to claim 14, 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.

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

the updating includes

setting a generation bit of a 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.

17. The table updating method according to claim 10, wherein the selecting includes detecting the indicator bit after masking the generation bits of a generation indicating a shortest time elapsed from among the bit string obtained by coupling the generation bits.

18. The table updating method according to claim 17, wherein the selecting includes performing a masking of a generation bit that has been previously detected as the indicator bit in the generation bits of the generation indicating the shortest time elapsed.