Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1998-12-21
2002-09-17
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S392000, C370S408000, C709S242000
Reexamination Certificate
active
06452908
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a route searching circuit for determining an apparatus to which a packet should be transferred, based on a destination address which specifies a transmission destination of the packet. Also, the present invention relates to a communication apparatus such as a router which uses the route searching circuit.
2. Description of the Related Art
A route searching circuit determines a network address which is defined based on an address such as an IP address on the internet and a mask length.
As an apparatus for relaying a packet data between networks or local area networks (LANs) connected to each other, an apparatus such as a bridge and a router is well known. In an Open Systems Interconnection (OSI) reference model which is defined by the International Organization for Standard (ISO), the bridge performs the connection in a data link layer, especially, a media access sub-layer. The router performs the connection in a network layer which is the upper layer of the data link layer.
A communication control apparatus which is called the bridge or the router needs to determine which apparatus the reception packet received through the network should be next transmitted to, based on a route table data which is previously provided for the communication control apparatus.
In this determination processing, it is generally determined based on the address stored in an address field of a reception packet data that the reception packet data should be transmitted to which apparatus.
The address used in an LAN will be described below simply.
As the address used on the LAN, there are known the address such as a MAC address in an ethernet network and an ATM address in an ATM network which is physically peculiar to the apparatus, a network number of a network to which the apparatus is connected, and a network address indicating a number of the apparatus on the network.
The data transmitted on the LAN generally contains network addresses of a transmission destination and transmission origin in the network layer. As the internet work address, for example, an IP address of 32 bits in the TCP/IP protocol is well known. In the following explanation, the IP address is used.
A router refers to a destination IP address of the received packet to determine that the router should next transmit the packet to which router or terminal. In this determining process, it is first determined which network address the destination IP address of the received packet belongs to. Then, a physical address of the transmission destination corresponding to the network address is determined. The network address is determined based on the IP address and the mask length. The mask length is the data that a predetermined number of bits of the IP address from the most significant bit are significant.
FIG. 1
shows an example of the network address. Referring to
FIG. 1
, because the mask length is “16”, it can be found that the upper 16 bits of the IP address of “800A0000” is valid as the network address. When the mask length is “16”, the mask address of “FFFF0000” that each of the upper 16 bits is “1” and each of the lower 16 bits is “0” is defined.
When a result of logical product of the above mask address and the destination IP address of the received packet is coincident with the IP address of “800A0000”, the destination IP address is coincident with the network address. For example, when the destination IP address is “800A40C8”, the logical product of the destination IP address of “800A40C8” and the mask data of “FFFF0000” is calculated. As a result, the address of “800A0000” is obtained. This is coincident with the IP address of “800A0000”. Thus, the destination IP address is coincident with the network address.
In a conventional example, the correspondence of the destination IP address and the network address could be simply solved under the concept of “class”. More specifically, when each of the upper bits of the IP address is “0”, the IP address belongs to a class A and the mask length is 8 bits. When the upper bit of the IP address is “10”, the IP address belongs to a class B and the mask length is 16 bits. When the IP address is “100”, the IP address belongs to a class C and the mask length is 24 bits.
At present, the concept of the class is demolished through the spread of subnets and Classless Internet Domain Routing (CIDR). Thus, the network address can not be simply determined from the destination IP address. It takes a long processing time for the determination of the network address. Also, in the network which adopts CIDR, there is a case where one or more network addresses in the route table are coincident with the destination IP address. In this case, the route data of the network address with the longest mask length must be adopted.
However, in a conventional router apparatus of the Internet, the route solution processing for determining based on the destination IP address that a packet should be transmitted to which apparatus is realized by software.
As described above, in a conventional communication control apparatus such as a bridge and a router, there is a problem that it takes a very long processing time for the solution of the route data for packet transfer in the network which has a lot of route data. Especially, in the packet transfer in the network in which there are one or more network addresses matching to an address, the algorithm to solve the network address becomes complicated. Therefore, the determination of the route data takes more time. For these reasons, the throughput of the packet transfer processing decreases in the packet transfer apparatus. This is because a specific route data corresponding to the destination address is searched from a lot of route data by the software.
In addition to the above conventional examples, a routing system is described in Japanese Laid Open Patent Application (JP-A-Heisei 2-206237). In the routing system, a connection apparatus includes an address table for a sub-tree. When a communication frame is received, the address table is referred to. When a destination address is exist in the address table, the communication frame is transferred to a link corresponding to the destination address.
Also, an address comparing system is described in Japanese Laid Open Patent Application (JP-A-Heisei 4-352534). In the address comparing system, an address common section Acom of terminal addresses Al to An set for a plurality of terminal equipments
1
-
1
to
1
-n is stored in an address register
2
. A portion of a terminal address of a reception address RA corresponding to the address common section Acom is compared with the value of the address register
2
. More specifically, a control register
4
is provided to have mask bits in which presence or non-presence of address comparison is set in units of bits. The address register
2
value and the reception address RA are compared by a comparing section
3
based on the mask bits of the control register
4
.
Also, a communication network system is described in Japanese Laid Open Patent Application (JP-A-Heisei 6-62029). In the communication network system, a distribution tree is generated based on tree addresses by a tree leader. A tree address correlation is generated using a network identifier and a node identifier, and a list of connected nodes is generated for every member of the multicast tree set.
Also, a LAN connecting apparatus is described in Japanese Laid Open Patent Application (JP-A-Heisei 7-254912). In the LAN connecting apparatus, an IP header
4
is detected from a reception communication packet
5
, and a destination IP address is detected from the IP header
4
. An output port number and the destination target IP address corresponding to the IP address are searched from the routing table
11
a
storing target IP addresses and an output port number for designating a transmission destination LAN for every IP address.
Also, a memory is described in Japanese Laid Open Patent Application (JP-A-Heisei 7-143156). In the memory, a
Nishihara Motoo
Yamada Kenshin
Foley & Lardner
Ho Duc
Hsu Alpus H.
NEC Corporation
LandOfFree
Route searching circuit and communication apparatus using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route searching circuit and communication apparatus using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route searching circuit and communication apparatus using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2910132