Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-11-21
2004-09-07
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395520, C370S401000
Reexamination Certificate
active
06788683
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a technique of controlling the flow of data such as IP packets on the Internet.
Recently, without being restricted to the best-effort-type service, the quality of services (QoS) including transmission delay, variations in delay, minimum guaranteed speed, or peak speed has been importantly concerned even when information on voice, images and so on are transferred in real time under the traffic control on the Internet.
The content of QoS to be required depends on the IP traffic. For example, requirements for transmission delay are not strict in the case of the best-effort-type traffic. In contrast, in the case of image information, strict requirements are required for transfer delay or variations in delay in order to avoid interruption of images.
In order to realize an optimum quality of services (QoS) for each IP (Internet Protocol) traffic, the IETF (Internet Engineering Task Force) is studying to standardize the specifications—Intserv (integrated services) and Diffserv (differentiated services)—. In the Intserv specification, QoS is guaranteed by reserving an end to end range using RSVP (resource reservation protocol). In the Diffserv specification, in order to realize QoS on, particularly, the backbone network, priority information is added to each IP packet so that the traffic flowing on the backbone is controlled.
Moreover, since QoS can be guaranteed for each connection in the asynchronous transfer mode (ATM), the approach of mapping QoS of an IP packet on the ATM connection is taken as means of providing QoS of an IP packet in the ATM.
In order to guarantee QoS through the mapping, a data flow (hereinafter referred to as “flow”) being formed of a sequence of IP packet groups is identified so that QoS is set in accordance with the identified flow.
The flow is identified for each data based on various data combinations. The data combination is formed by selecting all fields or a specific field only of fields within the header of an IP packet according to a difference of the flow type or the presence or absence of a specific transmission source or transmission destination.
In other words, fields including “TOS (type of services)” within the header of an IP packet, “PROTOCOL” of an IP packet defining a network layer protocol, “source address (SA)” being a source address, “destination address (DA)” being a destination address, and “source port (SPORT)” or “destination port (DPORT)” of TCP (transmission control protocol) header or UDP (user datagram protocol) header defining a transport layer protocol are handled as flow identification objects.
A selective combination of specific fields of those fields, for example, a combination of “SA” and “DA”, a combination of “SPORT” and “DPORT”, or a combination of “SA”, “DA”, “SPORT”, “DPORT” and “PROTOCOL”, becomes an actual object for flow identification.
As described above, there are a great number of fields to be selected for flow identification. Data of each field is represented in plural bits—16 bits or 32 bits—. For that reason, the number of bits for the retrieval key is increased for flow identification. As a result, outputting the flow identification result with the retrieval table largely widens the bit width of the retrieval key for the retrieval table.
The various combinations of fields for actual identification of fields require complicated identification rules for flow identification. Conventionally, in order to deal with such requirements, the flow identification is performed by software.
However, it is difficult to implement high speed flow identification in the software processing. An increasing number of heavy traffics to be handled occur a bottleneck in processing, thus resulting in congestion in a network. For that reason, an application range for the flow identification by software is limited to small size networks such as LANs (local area networks) or to areas with a relatively small number of traffics such as access systems of WANs (wide area networks).
In near future, the traffic of an IP packet is expected to increase explosively. For that reason, it is considered that even small size networks such as LANs or access systems in WANs will require the system that can deal with a large volume of traffics.
The ATM has the advantage of performing traffic control by hardware every logical link, so that the type of services (QoS) can be ensured without occurring a process bottleneck even on high-speed broadband networks. However, the high-speed technique in a hardware level has not been yet established even in the ATM to map the flow of an IP packet to an ATM logical link compatible QoS. For that reason, the intervention of software is needed to the QoS mapping and a high-speed flow identification process has been not realized.
Recently, content-addressable memory (CAM) has been used in the field of address retrieval in the network system devices. The content-addressable memory determines a memory location through label association and indicates it with the content, not address. The content-addressable memory can retrieve data on the retrieval data table at high speed. Since the capacity of a content-addressable memory depends on only the number of entries, the content-addressable memory can retrieve data with large data bit width at high speed, without an increase of the capacity.
However, the content-addressable memory can perform only the exact matching retrieval. In order to configure a retrieval table for flow identification with the content-addressable memory, it is required to register entries in which combinations of all fields to be selectable for flow identification correspond to all flow identification results. In this case, an enormous number of registration entries lead to a expanded retrieval table. The enormous number of registration entries takes much time for retrieval, thus making it difficult to implement a high-speed process for flow identification. For example, where the total number of bits of each field in a header is 128 bits, it is necessary to register entries of 128th power of 2. This is not realistic. Therefore, it has been difficult to configure the flow retrieval table with content-addressable memory.
SUMMARY OF THE INVENTION
The present invention is made to overcome the above-mentioned problems. An object of the present invention is to provide a flow identification technique that can implement a flow identification process at high speed.
The present inventor of this application noticed that the field of a header for actual flow identification is usually a part of the entire field. The present inventor has come to the idea that the number of entries of the retrieval table will be able to be decreased by masking a field based on an input logical link number of received data and extracting the field only for actual flow identification. As a result, a content-addressable memory (CAM) can be used, thus speeding the flow identification process.
According to the present invention, the flow identification device comprises a retrieval flag table for storing an input logical link number of received data and a retrieval flag in a corresponding relationship, the retrieval flag setting a field to be retrieved among fields in a header of a received IP (internet protocol) packet terminating the received data, and for outputting a retrieval flag corresponding to an input logical link number extracted from the received data; a mask section for masking each field in a header of the received IP packet with the retrieval flag and creating a post-mask retrieval key; and a flow retrieval table configured of a content-addressable memory, for storing the post-mask retrieval key and a flow identification result in a corresponding relationship and outputting a flow identification result corresponding to a post-mask retrieval key output from the retrieval flag table.
As described above, in the flow identification device of the present invention, a retrieval flag table is provided that sets a retrieval flag indicating a field for flow retrieval among fiel
Ikeda Hiroshi
Suzuki Yuichi
LandOfFree
Flow identifying device, flow processing device, flow... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Flow identifying device, flow processing device, flow..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flow identifying device, flow processing device, flow... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3234201