Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-02-29
2004-03-02
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S471000, C370S475000
Reexamination Certificate
active
06700889
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an apparatus that can quickly determine if multiple numbers are respectively contained in multiple numeric ranges. More particularly, the present invention relates to an apparatus that can quickly classify data packets transmitted over a digital communication network at high speeds by quickly determining if data values contained in the data packets are respectively contained in certain data ranges. Furthermore, the present invention relates to a method employed by the apparatus.
BACKGROUND OF THE INVENTION
In many applications, classifying a group of numbers by determining whether or not the group of numbers falls within a specific group of numerical ranges is extremely useful. For example, in a digital communication network (e.g. the internet, wide area network (“WAN”), local area network (“LAN”), etc.), data packets are transmitted over the network between a source computer (e.g. a router, server, etc.) and a destination computer (e.g. a router, server, etc.). Each of the data packets typically includes a header that contains information identifying the type of data contained in the data packet, the source from which the data packet was transmitted, the intended destination of the data packet, etc.
FIG. 1
illustrates an example of a data packet header HDR that comprises a source internet protocol (“IP”) address field
2
, a destination IP address field
4
, a protocol field
6
, a source port field
8
, and a destination port field
10
. The source IP address field
2
contains a 32-bit source IP address that identifies the computer transmitting the data packet. The destination IP address field
4
contains a 32-bit destination address that identifies the intended destination of the data packet. The protocol field
6
contains eight bits of protocol data that identify the data format and/or the transmission format of the data contained in the data packet. The source port field
8
includes 16 bits of data that identify the computer port that physically outputs the data packet, and the destination port field
10
contains 16 bits of data that represent the computer port that is supposed to input the data packet.
When data packets are transmitted over the network from the source computer to the destination computer, they are input by various routers, firewalls, and other network components. Such components may be included in the destination computer and/or may be contained in an intermediate computer that processes the data as it is being transmitted from the source computer to the destination computer. Before processing the data packet, a network component must “classify” the data packet according to various characteristics of the data packet and/or the data contained in the packet. Then, the network component processes the data packet based on its classification.
A data packet is usually classified by evaluating the information contained in the data packet header. For example, if the data packet contains the header HDR shown in
FIG. 1
, a network component may classify the data packet as a first type of data packet if the source IP address falls within a first range of source IP addresses, the destination IP address falls within a first range of destination IP addresses, the protocol data falls within a first range of protocol data values, the source port data falls within a first range of source port data values, and the destination port data falls within a first range of destination port data values. On the other hand, the internet component may classify the data packet as a second type of data packet if the source IP address, destination IP address, protocol data, source port data, and destination port data respectively fall within a second range of source IP addresses, a second range of destination IP addresses, a second range of protocol data values, a second range of source port data values, and a second range of destination port data values. Each group of data value ranges by which a data packet is classified may be considered to be a “rule”. Thus, in the example above, the data packet is classified as a first type of data packet if it satisfies a first rule and is classified as a second type of data packet if it satisfies a second rule.
After the data packet is classified, the network component is able to determine how handle or process the data. For instance, based on the classification of the data packet, the network component may output the data packet via a particular transmission path so that it quickly reaches the intended destination computer, may determine that the data packet is authorized to be received and further processed by the internet component, may prevent the packet from being forwarded on the network, may process the data contained in the data packet in a particular manner, etc. Accordingly, the network component acts as a filter that classifies incoming data packets according to various rules based on the specific data values contained in the data packet headers and then processes the data packets based on their classification.
Since the network component must classify each and every data packet that it receives, it should ideally classify the data packets at a speed that equals at least the speed at which the data packets are received. By classifying the data packets as quickly as they are received, data packets do not become “bottlenecked” at the input of the internet component, and the overall operational speed of the network is not degraded.
Currently, high speed Sonet and Ethernet networks are capable of transmitting data at speeds of one gigabit per second and are widely implemented in LANs and WANs. Furthermore, fiber optic networks capable of transmitting data at speeds of ten gigabits per second are expected to be developed soon. Moreover, interconnects that can transmit data at 40 gigabits per second are currently being tested and will additionally increase the overall speed at which data travels over the LANs and WANs. In light of the present and foreseeable transmission speeds of data networks, network components must be able to classify and filter data packets at extraordinary speeds. For example, on a high speed Sonet network that is capable of transmitting ten gigabits per second, data packets can be transmitted at a rate of 30 million packets per second, and on a full duplex line, data packets can be transmitted at about 60 million packets per second.
As described above, network components classify each incoming data packet by evaluating its header and selecting a rule from among multiple rules that corresponds to the data in the header. Furthermore, a typical component uses hundreds of rules to classify data packets. Thus, in order to properly classify the incoming data packets without creating a bottleneck at the input of the network component, the component must determine which rule of the hundreds of rules corresponds to each of the incoming data packets and must make such determination at a very high speed. Furthermore, as the number of network users and the number of different services available on the network increase, the number of rules that will need to be evaluated by standard network components is expected to grow to ten thousand or more in the near future. As a result, the network components will need to classify data packets according to an extremely large number of rules at incredible speeds.
One proposal for designing network components to classify data packets is to combine dedicated hardware and conventional central processing units (“CPUs”). However, such a design requires hundreds of CPUs that are each capable of executing more than one billion instructions per second. Furthermore, as the number of rules that need to be evaluated and the speed at which the rules must be evaluated increase, designing a network component in the proposed manner will be impractical because the speed of the CPUs will be too slow and the overall cost of the network component will become extremely expensive.
Also, some network components suggest using a combination of dedicated
Hyun Soon-Dong
Nguyen Chau
P-Cube Ltd.
LandOfFree
High speed apparatus and method for classifying a data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed apparatus and method for classifying a data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed apparatus and method for classifying a data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3208901