Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2000-06-09
2003-12-16
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S392000
Reexamination Certificate
active
06665274
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a path retrieving circuit operated to decide a device to which a packet is to be transferred based on information about a destination address to specify a receiving unit of the packet, a communication control unit such as a router employing the above path retrieving circuit or a like and more particularly to the path retrieving circuit required to solve a problem of conformity between an IP (Internet Protocol) address being used in the Internet and a network address defined by an address and a mask strength and the communication control unit using the above path retrieving circuit.
2. Description of the Related Art
Communication control units such as a bridge or a router used to pass on packet data between two or more networks, for example, between LANs (Local Area Network) are well known. The bridge establishes a connection at a level of a data link layer in a reference model of an OSI (Open Systems Interconnection) designated by ISO (International Organization for Standard). Moreover, the router establishes a connection at a level of a network layer being an upper layer of the data link layer.
Conventionally, path table information is preliminarily set in the communication control unit such as bridges, routers or a like. The communication control unit, when receiving packet data through the network, is operated to judge a place to which the received packet data is to be transferred in accordance with the path table information. In this processing of the judgement, in general, a path table is retrieved based on an address stored in an address field of the received packet data and to which device the received packet data is to be transferred is then judged.
Next, an example of the retrieving using an address employed in the LAN will be explained below briefly.
The address used in the LAN includes an MAC (Medium Access Control) address on an ethernet network, an address specific to a unit such as an ATM (Asynchronous Transfer Mode) device in an ATM network, a network number used among these communication devices, a network address representing a unit number on the network or a like.
The sending and receiving data transmitted at a level of the network layer in the LAN ordinarily includes an internet work address to identify a destination address and source address. An IP address (32 bits) in a TCP/IP (Transmission Control Protocol/Internet Protocol) is well known as the internet work address.
The router is operated, by referencing to a destination IP address of the received packet, to judge to which router or terminal the received packet is to be transmitted in the processing of the judgement, after having judged to which network address the destination IP address of the received packet belongs and to decide a physical address of the destination address corresponding to the network address.
The network address is defined by the IP address and a mask length. The mask length is information showing up to which bit from a high order bit is valid as the network address in the IP address.
An example of the network address is shown in FIG.
30
. In the example in
FIG. 30
, since the mask length is 16 bits, high order 16 bits out of the IP address [800A0000] are valid as the network address. If the mask length is “16”, the mask address is defined as [FFFF0000] with the high order 16 bits representing “1” and with low order 16 bits representing “0”. When a result obtained by ANDing the destination IP address of the received packet and the above mask address conforms to the IP address [600A0000], the destination IP address is judged to have conformed to the network address.
For example, if the destination IP address is [800A40C8], a result obtaining by ANDing the destination IP address [800A40C8] and the mask address [FFFF0000] is [800A0000] . This conforms to the IP address [800A0000]. Therefore, the destination IP address is judged to conform to the network address.
Conventionally, the conformity between the destination IP address and the network address has seen solved simply by using a concept of a “Class”. That is, if the high order bit of the IP address is “0”, the address fits into the “Class A” having its mask length being 8 bits, if the high order bit of the IP address is “10”, the address fits into the “Class B” having its mask length being 16 bits and if the high order bit of the IP address is “100”, the address fits into the “Class C” having its mask length being 24 bits.
However, in recent years, due to a widespread use of subnet or CIDR (Classless Internet Domain Routing), the concept of the “Class” s not used. This does not allow the network address to be simply judged from the IP address, causing much time required to judge the network address.
Moreover, in some networks employing the CIDR, there are cases in which a plurality of network addresses conforming to the destination IP address may exist in the path table. In this case, path information given by the network address having the largest mask length is employed.
As described above, the conventional communication control units including the bridge, router or like have a problem in that, when the packet data is transferred on the network having much path information, much time is required to process the path information.
Especially, in the case of transferring the packet data on the network having a plurality of network addresses matching to a specified destination address, since an algorithm for solving contents of the network address is made complicated and further much time is required to process the path information. This causes a reduction in throughput of packet transferring processing in the packet transferring unit.
In the conventional router used in the Internet, a path deciding processing for determining a device to which the packet data is to be transferred next, based on the destination IP address, is implemented by using software; that is to say, the path information to be retrieved out of much path information is implemented by the software.
Description of the Prior Invention
The inventor of the present invention has disclosed a technology capable of reducing the time required for the path solving processing in Japanese Patent Application No. Hei9-356774. As shown in
FIG. 32
, disclosed technology is excellent in that the path solving processing can be performed at a high speed by implementing the retrieval algorithm composed of a binary tree structure (path tree or RT
0
) using a hardware circuit. Details of the path tree shown in
FIG. 32
are described later.
Hereafter, technology disclosed in the Japanese Patent Application No. Hei9-356774 will be described in detail.
FIG. 31
is a schematic block diagram showing configurations of a conventional communication control unit. As shown in
FIG. 31
, the conventional communication control unit is composed of an input/output device
1
, a path retrieving circuit
2
a
and a path tree storing memory
3
.
The input/output device
1
is a device to perform processing of a received packet, which requests the path retrieving circuit
2
a
to perform path information retrieving and judges a destination address of the received packet based on a result R of path information retrieving (hereinafter maybe referred to as result of retrieving) outputted from the path retrieving circuit
2
a
as a result of the requested retrieval.
The path retrieving circuit
2
a
, when receiving a retrieval requesting signal S and a destination IP address A from the input/output device
1
, is operated to retrieve the path information corresponding to the destination IP address by using the path tree storing memory
3
and then to output a retrieval completion signal E and result R of retrieving to the input/output device
1
.
A path table shown as Table 1 which corresponds to the path tree, as shown in
FIG. 32
, used for determining the place to which the packet is to be transferred is stored in the path tree storin
Cangialosi Salvatore
Foley & Lardner
NEC Corporation
LandOfFree
Communication control unit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communication control unit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication control unit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3109129