JP3581238B2 - Real-time packet tracking method and packet matching device - Google Patents

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a network for transmitting packets, and more particularly, to a packet tracking method.
[0002]
[Prior art]
In a network (called a user network) for transmitting information (packets), as shown in FIG. 12, probes (packet probe devices 100) for probing packets flowing on the network via a packet transfer device 101 are provided at a plurality of points. Put. Each probe 100 copies a packet from the network and takes in the packet data. Further, each probe sends a large amount of captured packet data to the monitoring server 102 as a continuous stream through a user network or a dedicated network. Further, on the monitoring server 102, the same packet is searched for in real time from continuous data sent from a plurality of points, and packet tracking is performed. The operation of searching for the same packet is called packet matching.
[0003]
Conventionally, in order to perform packet matching, as shown in FIG. 13, packet data copied by a probe 100 is temporarily stored on a monitoring server 102, and after a certain period of time, packet matching is performed using the same packet selection device 103. Was performed repeatedly. Therefore, the same packet selecting device 103 can perform the packet matching only by comparing the packet data stored on the monitoring server 102 regardless of the execution time.
[0004]
[Problems to be solved by the invention]
The conventional technique has the following problems with respect to matching in real time.
[0005]
・ Since processing is not performed in real time, continuous monitoring over a certain period of time is impossible.
[0006]
-Since the search is performed by matching the packet data, it takes a long time for the matching process.
[0007]
-When the capacity of the search table is small, an efficient registration method for the search table is required.
[0008]
-Even if a search table is used, a long search key may increase the reference time of the search table.
[0009]
-When the input rates for the two inputs are different, the amounts registered in the search table are different. If the search table is very small, packets from one side of the input may not be registered in the search table, and packet matching may not be performed properly.
[0010]
-The function to output the packet that failed to search may not work in real time.
-To perform packet matching, prepare a small finite table, fetch packet stream fragments into that table, search for equal packets based on search keys, and always update the table at short intervals Is required. By the way, if the arrival time of the packet is different or a certain time is required, if this time is longer than the time for updating the table, the packet to be subjected to packet matching is not taken in all tables, Matching does not work properly.
[0011]
An object of the present invention is to provide a real-time packet tracking method and a packet matching device capable of real-time packet matching.
[0012]
[Means for Solving the Problems]
According to the real-time packet tracking method of the present invention, for each packet of each packet stream, a search key is created by extracting a part of the data of the packet. It checks whether the packet has been sent, and if so, outputs those packet pairs and outputs to another output port a packet to which no packet with the same search key is sent even after waiting for a certain period of time.
[0013]
The packet matching device according to the present invention includes a masking unit that extracts a part of the data of a packet and creates a search key for each packet of each packet stream, A matching means that checks whether the packet has already been sent, and if so, outputs those packet pairs and outputs to another output port a packet to which no packet with the same search key is sent even after waiting for a certain period of time Have.
[0014]
Therefore, by using this apparatus on a monitoring server, packet tracking can be performed in real time from continuous data transmitted from a plurality of points.
[0015]
When using the packet matching device, the matching means uses a hash, so that packet matching can be performed in real time.
[0016]
If the hash is used when the amount of the search table cannot be obtained, the possibility of occurrence of collision at the time of registration in the table increases, and the matching speed may be affected. In such a case, by registering in a table using a Patricia tree, packet matching can be performed in real time. If the search key is long, there is a high possibility that a collision will occur at the time of registration in the table, and the matching speed may be affected. In such a case, by registering in a table using a Patricia tree, packet matching can be performed in real time.
[0017]
In the matching means, by creating a search database using a Patricia tree for the input port, when both input rates are different depending on time, a packet to be subjected to packet matching with the search table is reliably registered in the table. It becomes possible to do.
[0018]
In the matching means, using one table on one side and three tables on the other side using a hash or Patricia tree at two input ports, if the input rate on one side is very large, On the other hand, a packet to be subjected to packet matching can be reliably registered in the table.
[0019]
Since the matching means holds, in addition to the search database, an array consisting of a search key and an attribute indicating whether the search was successful or unsuccessful, it is very costly to delete packet data from the search table. In such a case, it becomes possible to operate the function of outputting a packet whose search has failed in real time.
[0020]
If the matching means succeeds in the search using the search key, the data is deleted from the search table, and if it is very costly to delete the entire search table at once, a packet that failed to be searched is output. The function can be operated in real time.
[0021]
When a data string composed of a pair of a packet and a time stamp is given, the matching unit compares the time stamp with respect to the matched packet, that is, by calculating a difference or the like, the packet is sent in a stream form. It is possible to examine the time difference between the same two pieces of packet data and the fluctuation of the time difference.
[0022]
Changing the number of search tables means that the number of data registered in the search tables in a certain period of time is increased. In order to perform accurate packet matching, all packets to be matched need to be registered in a finite search table. For this reason, a stream synchronization device is incorporated, but even if this device is used, if the search tables are updated one after another within the generation interval of the SIQV header, all the packets to be matched may not be registered in the search table. is there. For this reason, the problem is solved by increasing the size of the search table corresponding to both inputs (one input in some cases) (claims 5 and 6).
[0023]
When performing a search table update, it is necessary to output data remaining in the search table as a result of the matching failure (that is, data in which an equal key was not found). Therefore, unless the search table is cleared, old packet data always remains, and the data is always output as data for which matching has failed. In order to avoid such an error, a method of deleting all packet data from the search table and a method of referring to information on packet data registered in the search table can be considered. The choice is a trade-off.
[0024]
By providing a stream synchronizer, when the delay fluctuation or delay difference from each probe to the monitoring server is large, the delay error is minimized, the packets to be packet-matched are taken in all tables, and packet matching is performed normally. Will be able to be done.
[0025]
BEST MODE FOR CARRYING OUT THE INVENTION
Next, embodiments of the present invention will be described with reference to the drawings.
[0026]
According to the real-time packet tracking method of the present invention, a packet data stream sent from a packet probe device is directly received, packet matching is performed in real time, and data that has succeeded in packet matching and data that has failed are output.
[0027]
In order to realize this, as shown in FIG. 1, the present embodiment has a stream synchronization device 30 and a packet matching device 10.
[0028]
"Packet matching device 10" (claims 2, 3, 4, 5, 6, 7, 8): A device that executes the packet matching method is called a packet matching device. As shown in FIG. 2, the present apparatus has four input (IA, IB, MA, MB) and three output (OM, OIA, OIB) data ports. In this device, the matched packets of the data streams input to the input ports IA and IB are output to the data port OM. Regarding the unmatched packet, the input from the input port IA is output to the output port OIA, and the input from the input port IB is output to the output port OIB. The data ports MA and MB are used as mask input terminals for enabling packet matching by referring to a part of the packet.
[0029]
As shown in FIG. 3, the packet matching device 10 includes a masking mechanism 11, a matching mechanism 12, and a time stamp processing mechanism 13. Each mechanism is described below. The time stamp processing mechanism 13 is operable when individual data in the data stream is given as a set of a time stamp and packet data, and is a mechanism provided when time stamp processing is required.
[0030]
"Masking mechanism 11" (Claim 2): In packet matching, it is necessary to refer to a part that is not rewritten in the packet data area in order to find an equal packet. For this reason, a mechanism for cutting out a part of the packet data is called a masking mechanism.
[0031]
FIG. 5 shows an operation example of the masking mechanism 11 using an IP packet as an example. Here, “1” is set as don't care. A packet (input data) A is at the head of the input data stream to the IA, and a packet B is at the head of the input data stream to the IB. The MA mask is shown as mask A and the MB mask is shown as mask B. At this time, the masking mechanism 11 creates mask data with reference to each mask, and passes this data to the matching mechanism 12. The packet data is also passed to the matching mechanism 12.
[0032]
"Matching mechanism 12" (claims 2, 3, 4, 5, 6, 7, 8): The matching mechanism 12 includes an input / output module 21 and a table management module 22, as shown in FIG. The mechanism 12 has a function of searching for the same packet by referring to a search table using masked data as a key.
[0033]
Hereinafter, HIA indicates a search table formed by a hash table (or Patricia tree) corresponding to an input port on the IA side. HIA (key) indicates data retrieved by the key. When HIA (key) → (a, b, c) is expressed, it indicates that the data pointed by the key is a data set of a, b, and c. Further, each data is expressed as HIA (key): a, HIA (key): b, HIA (key): c. Here, HIA (key): A indicates that the data is A searched by HIA (key).
[0034]
The input / output module 21 (Claim 2): Here, the input / output module IA will be described as an example. The input from the input port IB operates similarly by exchanging IA and IB in the following text.
[0035]
1. The first packet data a of the data stream input to the input port IA and the key of a are acquired.
[0036]
2. Assuming that an attribute indicating that the data is input data from the input port IA is IA, data consisting of (a, key, IA) is sent to the table management module 22.
[0037]
3. When A returns from the table management module 22,
If A = NULL,
Return to 1. At this time, the operation is performed by exchanging IA and IB.
[0038]
When A = b (= packet data of HIB (key)) returns,
When not passing through the time stamp processing mechanism 13, a (or b) is output. When passing through the time stamp processing mechanism 13, (a, b) is passed to the time stamp processing mechanism 13.
[0039]
Return to 1. At this time, the operation is performed by exchanging IA and IB.
[0040]
Table management module 22 (Claims 2, 3, 4, 5, 6, 7, and 8): Here, an example in which a hash is used for a search table will be described, but the same processing can be performed when a Patricia tree is used. is there.
[0041]
Table management module 22 (Claims 2, 3, 4, 5, and 7): The table management module 22 manages the search table HIA1 for the input port IA for each input terminal to the packet matching apparatus 10, and stores the search table HIA1 in the input port IB. The corresponding search table HIB1 is managed. Further, for input ports IA and IB, DIA and DIB each having a key array are provided. Each data registered in the search tables HIA1 and HIB1 is composed of a set of HIA1 (key) → (packet data, Mbit).
[0042]
Mbit indicates the attribute of the packet corresponding to the key. The initial value of Mbit is off. When a packet corresponding to the key is found, Mbit is turned on. Therefore, by referring to the Mbit, it is possible to know whether or not a packet corresponding to the key has been found.
[0043]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the IA side or IB side.
[0044]
A search operation when attr = IA is described. Note that when attr = IB, the operation is such that A and B are interchanged.
[0045]
Search the search table HIB1 based on the key.
[0046]
-When data is obtained from the search table HIB1:
* HIB1 (key): When Mbit == Off:
1. “HIB1 (key): packet data” is output to TOUT.
2. HIB1 (key): Mbit = ON.
[0047]
HIB1 (key): When Mbit == ON, outputs NULL to TOUT.
[0048]
-When data cannot be obtained from the search table HIB1:
1. Output NULL to TOUT.
[0049]
2. Data consisting of (packet data, Mbit = off) is stored in HIA1 (key).
[0050]
3. Save the key in DIA1.
[0051]
Next, the table management module 22 manages the search tables HIA1 and HIB1 and the arrays DIA and DIB. This function, as an initial operation, secures the areas of the search tables HIA1 and HIB1 and the arrays DIA and DIB, reads the deletion condition T, and sets tIA = 0 and tIB = 0. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Although the operation on the input port IA side is described below, the operation on the input port IB side is the same if A and B are exchanged.
[0052]
When tIA = T:
1. The keys are sequentially referred to from the array DIA, and when HIA1 (key): Mbit == off, “HIA1 (key): packet data” is output to the OIA.
[0053]
2. Clear the contents of the search table HIA1 and the array DIA1.
[0054]
3. It is assumed that tIA = 0.
[0055]
When tIA <T:
1. This function does not work.
[0056]
Table management module 22 (claims 2, 3, 4, and 8): The table management module 22 manages the search table HIA1 corresponding to the input port IA, and manages the search table HIB1 corresponding to the input port IB. The individual data registered in the search table is HIA (key) → (packet data), and is composed of only packet data.
[0057]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the input port IA side or input port IB side.
[0058]
A search operation when attr = IA is described. Note that when attr = IB, the operation is such that A and B are interchanged.
[0059]
Search the search table HIB1 based on the key.
[0060]
-When data is obtained from the search table HIB1:
1. “HIB1 (key): packet data” is output to TOUT.
2. "HIB1 (key): packet data" is deleted from HIB1.
[0061]
-When data cannot be obtained from the search table HIB1:
1. Output NULL to TOUT.
[0062]
2. (Packet data) is stored in HIA1 (key).
[0063]
Next, the table management module 22 manages the search tables HIA1 and HIB1. As an initial operation, this function reads the deletion condition T after securing the areas of the search tables HIA1 and HIB1, and sets tIA = 0 and tIB = 0. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Although the operation on the input port IA side is described below, the operation on the input port IB side is the same if A and B are exchanged.
[0064]
When tIA = T:
1. If packet data exists in the search table HIA1, the data is output to the OIA.
[0065]
2. Clear the contents of the search table HIA1.
[0066]
3. It is assumed that tIA = 0.
[0067]
When tIA <T:
1. This function does not work.
[0068]
Table management module 22 (Claims 2, 3, 4, 5, and 7): The table management module 22 manages the search tables HIA1 and HIA2 corresponding to the input port IA for each input terminal to the packet matching device 10, The search tables HIB1 and HIB2 corresponding to the input port IB are managed. Also, for the input ports IA and IB, there are arrays DIA1, DIA2, DIB1, and DIB2 consisting of keys, respectively. Each data registered in the search table is a set of HIAn (key) → (packet data, Mbit), where n = 1 and 2.
[0069]
Mbit indicates the attribute of the packet corresponding to the key. The initial value of Mbit is off. When a packet corresponding to the key is found, Mbit is turned on. Therefore, by referring to the Mbit, it is possible to know whether or not a packet corresponding to the key has been found.
[0070]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the IA side or IB side.
[0071]
A search operation when attr = IA is described. Note that when attr = IB, the operation is such that A and B are interchanged.
[0072]
Search for HIBn (n = 1, 2) based on the key.
[0073]
-When data can be obtained from HIBm (m: arbitrary n):
* HIBm (key): When Mbit == Off:
1. “HIBm (key) packet data” is output to the OM.
[0074]
2. HIBm (key): Mbit = ON.
[0075]
* HIBm (key): When Mbit == ON, outputs NULL to TOUT.
[0076]
When data cannot be obtained from HIBm (m: arbitrary n):
1. Output NULL to TOUT.
[0077]
2. Data consisting of (packet data, Mbit = off) is stored in HIA1 (key).
[0078]
3. Save the key in DIA1.
[0079]
Next, the table management module 22 manages the search tables HIA1, HIA2, HIB1, HIB2 and the arrays DIA1, DIA2, DIB1, DIB2. In this function, as an initial operation, HA0, HA1, HB0, HB1, DA0, DA1, DB0, and DB1 are secured as areas, and then read as a deletion condition T and a is set to a value satisfying a <T, and tIA = 0 , TIB = T−a: initial state 1 (or tIA = Ta, tIB = 0: initial state 2), and hia = 0, hib = 0. Also, HIA1 → HA0, HIA2 → HA1, HIB1 → HB0, HIB2 → HB1, DIA1 → DA0, DIA2 → DA1, DIB1 → DB0, DIB2 → DB1. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Hereinafter, the operation on the IA side will be described, but the operation on the IB side is the same if A and B are exchanged.
[0080]
When tIA = T:
-Part 1-1
1. The keys are sequentially referred to from DIA2, and if HIA2 (key): Mbit == off, “HIA2 (key): bucket data” is output to OIA.
[0081]
2. HA2 → HAhia, and DIA2 → DAhia.
[0082]
3. hia = 1-hia, and HIA1 → HAhia, DIA1 → DAhia.
[0083]
4. Clear the contents of HIA1 and DIA1.
[0084]
5. It is assumed that tIA = 0.
[0085]
-Part 1-2
1. HIA2 → HAhia, and DIA2 → DAhia.
[0086]
2. hia = 1-hia, and HIA1 → HAhia, DIA1 → DAhia.
[0087]
3. The keys are sequentially referred to from DIA1, and if HIA1 (key): Mbit == OFF, “HIA1 (key): packet data” is output to OIA.
[0088]
4. Clear HIA1 and DIA1.
[0089]
5. It is assumed that tIA = 0.
[0090]
-Part 2
1. The keys are sequentially referred to from DIA2, and if HIA2 (key): Mbit == OFF, "HIA2 (key): packet data" is output to OIA.
[0091]
2. Clear the contents of HIA2 and DIA2.
[0092]
3. HIA2 → HAhia, and DIA2 → DAhia.
[0093]
4. hia = 1-hia.
[0094]
5. HIA1 → HAhia, and DIA1 → DAhia.
[0095]
6. It is assumed that tIA = 0.
[0096]
-Part 3-1
1. The keys are sequentially referred to from DIA2, and if HIA2 (key): Mbit == OFF, “HIA2 (key): packet data” is output to OIA.
[0097]
2. HIA2 → HAhia, and DIA2 → DAhia.
[0098]
3. cia = 1-hia, and clears HAhia and DAhia.
[0099]
4. HIA1 → HAhia, DIA1 → DAhia.
[0100]
5. It is assumed that tIA = 0.
[0101]
-Part 3-2
1. HIA2 → DAhia and DIA2 → DAhia.
[0102]
2. hia = 1-hia.
[0103]
3. The keys are sequentially referred to from DAhia, and if HAhia: Mbit == OFF, “HAhia (key): packet data” is output to the OLA.
[0104]
4. Clear HAhia and DAhia.
[0105]
5. HIA1 → HAhia, DIA1 → DAhia.
[0106]
6. It is assumed that tIA = 0.
[0107]
When tIA <T:
1. This function does not work.
[0108]
Table management module 22 (claims 2, 3, 4, 5, and 8): The table management module 22 manages the search tables HIA1 and HIA2 corresponding to the input port IA, and searches the search tables HIB1 and HIB1 corresponding to the input port IB. Manages HIB2. The individual data registered in the search table is HIAn (key) → (packet data), where n = 1 and 2, and is composed of only packet data.
[0109]
The input to the table management module 22 is given from the input module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the input port IA side or input port IB side.
[0110]
A search operation when attr = IA is described. Note that when attr = IB, the operation is such that A and B are interchanged.
[0111]
Search for HIBn (n = 1, 2) based on the key.
[0112]
-When data can be obtained from HIBm (m: arbitrary n):
1. “HIBm (key): packet data” is output to TOUT.
[0113]
2. "HIBm (key): packet data" from HIBm (key)
Remove.
[0114]
When data cannot be obtained from HIBm (m: arbitrary n):
1. Output NULL to TOUT.
[0115]
2. (Packet data) is stored in HIA1 (key).
[0116]
Next, the table management module 22 manages the search tables HIA1, HIA2, HIB1, and HIB2. In this function, as an initial operation, after allocating the areas of the search tables HA0, HA1, HB0, and HB1, the deletion condition T is read, and when a is set to a <T, tIA = 0 and tIB = Ta: The initial state 1 (or tIA = Ta, tIB = 0: initial state 2) is set, and hia = 0 and hib = 0. Also, HIA1 → HA0, HIA2 → HA1, HIB1 → HB0, HIB2 → HIB1. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Although the operation on the input port IA side is described below, the operation on the input port IB side is the same if A and B are exchanged.
[0117]
When tIA = T:
-Part 1-1
1. If packet data exists in the search table HIA2, it outputs it to the OIA.
[0118]
2. It is assumed that the search table is HIA2 → HAhia.
[0119]
3. HIA = 1-HIA, and HIA1 → HAHIA.
[0120]
4. Clear the contents of the search table HIA1.
[0121]
5. It is assumed that tIA = 0.
[0122]
-Part 1-2
1. It is assumed that the search table is HIA2 → HAhia.
[0123]
2. HIA = 1-HIA, and HIA1 → HAHIA.
[0124]
3. If there is packet data in the search table HIA1, it outputs it to the OIA.
[0125]
4. Clear the contents of the search table HIA1.
[0126]
5. It is assumed that tIA = 0.
[0127]
-Part 2
1. If the search table HIA2 packet data exists, it outputs it to the OIA.
[0128]
2. Clear the contents of the search table HIA2.
[0129]
3. It is assumed that the search table is HIA2 → HAhia.
[0130]
4. HIA = 1-HIA, and HIA1 → HAHIA.
[0131]
5. It is assumed that tIA = 0.
[0132]
-Part 3-1
1. It is assumed that the search table is HIA2 → HAhia.
[0133]
2. hia = 1-hia.
[0134]
3. If there is packet data in HAhia, it outputs it to OIA.
[0135]
4. Clear HAhia.
[0136]
5. It is assumed that the search table is HIA1 → HAhia.
[0137]
6. It is assumed that tIA = 0.
[0138]
-Part 3-2
1. If packet data exists in the search table HIA2, it outputs it to the OIA.
[0139]
2. It is assumed that the search table is HIA2 → HAhia.
[0140]
3. HAhia is cleared by setting the search table hia = 1-hia.
4. It is assumed that the search table is HIA1 → HAhia.
[0141]
5. It is assumed that tIA = 0.
[0142]
When tIA <T:
1. This function does not work.
[0143]
Table management module 22: Part 2 (Claims 2, 3, 4, 5, and 7): The table management module 22 stores search tables HIA1 and HIA2 corresponding to the input port IA for each input terminal to the packet matching apparatus 10. It manages the search tables HIB1 and HIB2 corresponding to the input port IB. Also, for the input ports IA and IB, there are arrays DIA1, DIA2, DIB1, and DIB2 consisting of keys, respectively. Each data registered in the search table is a set of HIAn (key) → (packet data, Mbit), where n = 1 and 2.
[0144]
Mbit indicates the attribute of the packet corresponding to the key. The initial value of Mbit is off. When a packet corresponding to the key is found, Mbit is turned on. Therefore, by referring to the Mbit, it is possible to know whether or not a packet corresponding to the key has been found.
[0145]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the IA side or IB side.
[0146]
A search operation when attr = IA is described. Note that when attr = IB, the operation is such that A and B are interchanged.
[0147]
Search for HIBn (n = 1, 2) based on the key.
[0148]
-When data can be obtained from HIBm (m: arbitrary n):
HIBm (key): When Mbit == Off:
1. “HIBm (key): packet data” is output to TOUT.
[0149]
2. HIBm (key): Mbit = ON.
[0150]
If HIBm (key): == ON, NULL is output to TOUT.
[0151]
When data cannot be obtained from HIBm (m: arbitrary n):
1. Output NULL to TOUT.
[0152]
2. The data consisting of (packet data, Mbit: = ON) is stored in HIA1 (key).
[0153]
3. Save the key in DIA1. For 1 see the next paragraph.
[0154]
Next, the table management module 22 manages the search tables HIA1, HIA2, HIB1, HIB2 and the arrays DIA1, DIA2, DIB1, DIB2. This function reads the deletion condition T and the condition t (t <= T / 2) after securing areas of the search tables HA0, HA1, HB0, HB1, arrays DA0, DA1, DB0, DB1 as an initial operation. It is assumed that tIA = tIB = 0. It is assumed that hia = 0 and hib = 0. HIA1 → HA0, HIA2 → HA1, HIB1 → HB0, HIB2 → HB1, DIA1 → DA0, DIA2 → DA1, DIB1 → DB0, DIB2 → DB1. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Hereinafter, the operation on the IA side will be described. However, the operation on the IB side is the same when A and B are exchanged.
[0155]
・ Part 1
If -tIA <t:
1.1 = hia + 1.
[0156]
-T ≦ tIA <T:
1.1 = values of both 1 and 2.
[0157]
When −tIA = T:
1. The keys are sequentially referred to from DAhia, and if HAhia (key): Mbit == off, “HAhia (key): packet data” is output to OIA.
[0158]
2. Clear the contents of HAhia and DAhia.
[0159]
3. hia = 1-hia.
[0160]
4. It is assumed that tIA = 0.
[0161]
・ Part 2
If -tIA <t:
1.1 = 1.
[0162]
If -t <= tIA <T:
1.1 = values of both 1 and 2.
[0163]
When −tIA = T:
* Part 2-1-1
1. The keys are sequentially referred to from DIA2, and when HIA2 (key): Mbit == off, “HIA2 (key): packet data” is
Output to OIA.
[0164]
2. HIA2 → HAhia, and DIA2 → DAhia.
[0165]
3. hia = 1-hia, and HIA1 → HAhia, DIA1 → DAhia.
[0166]
4. Clear the contents of HIA1 and DIA1.
[0167]
5. It is assumed that tIA = 0.
[0168]
* Part 2-1-2
1. HIA2 → HAhia, and DIA2 → DAhia.
[0169]
2. hia = 1-hia, and HIA1 → HAhia, DIA1 → DAhia.
[0170]
3. The keys are sequentially referred to from DIA1, and if HIA1 (key): Mbit == OFF, “HIA1 (key): packet data” is output to OIA.
[0171]
4. Clear HIA1 and DIA1.
[0172]
5. It is assumed that tIA = 0.
[0173]
* Part 2-2
1. The keys are sequentially referred to from DIA2, and if HIA2 (key): Mbit == OFF, "HIA2 (key): packet data" is output to OIA.
[0174]
2. Clear the contents of HIA2 and DIA2.
[0175]
3. HIA2 → HAhia, and DIA2 → DAhia.
[0176]
4. hia = 1-hia.
[0177]
5. HIA1 → DIhia, and DIA1 → DAhia.
[0178]
6. It is assumed that tIA = 0.
[0179]
* Part 2-3-1
1. The keys are sequentially referred to from DIA2, and if HIA2 (key): Mbit == OFF, "HIA2 (key): packet data" is output to OIA.
[0180]
2. HIA2 → HAhia, and DIA2 → DAhia.
[0181]
3. cia = 1-hia, and clears HAhia and DAhia.
4. HIA1 → HAhia, DIA1 → DAhia.
[0182]
5. It is assumed that tIA = 0.
[0183]
* Part 2-3-2
1. HIA2 → DIhia, and DIA2 → DAhia.
[0184]
2. hia = 1-hia.
3. The key is sequentially referred to from DAhia, and if HAhia: Mbit == off, “HAhia (key): packet data” is output to OIA.
4. Clear HAhia and DAhia.
5. HIA1 → HAhia, DIA1 → DAhia.
6. It is assumed that tIA = 0.
Table management module 22 (Claims 2, 3, 4, 5, and 8): The table management module 22 manages the search tables HIA1 and HIA2 corresponding to the input port IA, and searches the search tables HIB1 and HIB1 corresponding to the input port IB. Manages HIB2. The individual data registered in the search table is HIAn (key) → (packet data), where n = 1 and 2, and is composed of only packet data.
[0185]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). “key” indicates a search key, “data” indicates packet data, and “utter” indicates whether data is input from the IA side or IB side.
[0186]
A search operation when attr = IA is described. Note that when attr = IB, the operation is such that A and B are interchanged.
[0187]
Search for HIBn (n = 1, 2) based on the key.
[0188]
-When data can be obtained from HIBm (m: arbitrary n):
1. “HIBm (key) packet data” is output to TOUT.
[0189]
2. “HIBm (key): packet data” is deleted from HIBm (key).
[0190]
When data cannot be obtained from HIBm (m: arbitrary n):
1. Output NULL to TOUT.
[0191]
2. Data consisting of (packet data, Mbit = off) is stored in HIA1 (key). For 1 see the next paragraph.
[0192]
Next, the table management module 22 manages the search tables HIA1, HIA2, HIB1, and HIB2. This function, as an initial operation, secures areas HA0, HA1, HB0, and HB1, and then reads a deletion condition T and a condition t (t <= T / 2), and sets tIA = tIB = 0. It is assumed that hia = 0 and hib = 0. Further, the order is HIA1 → HA0, HIA2 → HA1, HIB1 → HB0, HIB2 → HB1. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Hereinafter, the operation on the input port IA side will be described, but the operation on the input port IB side is the same if A and B are exchanged.
[0193]
・ Part 1
If -tI <t
1.1 = hia + 1.
[0194]
If -t <= tIA <T:
1.1 = hia + 1,2-hia.
[0195]
When −tIA = T:
1. If there is packet data in HAhia, it outputs it to OIA.
[0196]
2. Clear the contents of HAhia.
[0197]
3. hia = 1-hia.
[0198]
4. It is assumed that tIA = 0.
[0199]
・ Part 2
If -tIA <t
1.1 = 1.
[0200]
If -t <= tIA <T:
1.1 = 1,2.
[0201]
When −tIA = T:
* Part 2-1-1
1. If packet data exists in the search table HIA2, it outputs it to the OIA.
[0202]
2. It is assumed that the search table is HIA2 → HAhia.
[0203]
3. The search table hia is set to 1-hia, and HIA1 → HAhia.
[0204]
4. Clear the contents of the search table HIA1.
[0205]
5. It is assumed that tIA = 0.
[0206]
* Part 2-1-2
1. It is assumed that the search table is HIA2 → HAhia.
[0207]
2. hia = 1-hia, and HIA1 → HAhia.
[0208]
3. If packet data exists in search table HIA1, it is
To the OIA.
[0209]
4. Clear the search table HIA1 and the array DIA1.
[0210]
5. It is assumed that tIA = 0.
[0211]
* Part 2-2
1. If there is packet data in the search table HIA2,
To the OIA.
[0212]
2. Clear the contents of the search table HIA2.
[0213]
3. It is assumed that the search table is HIA2 → HAhia.
[0214]
4. hia = 1-hia.
[0215]
5. It is assumed that the search table is HIA1 → HAhia.
[0216]
6. It is assumed that tIA = 0.
[0217]
* Part 2-3-1
1. If packet data exists in the search table HIA2, it outputs it to the OIA.
[0218]
2. It is assumed that the search table is HIA2 → HAhia.
[0219]
3. cia = 1-hia to clear HAhia.
[0220]
4. It is assumed that the search table is HIA1 → HAhia.
[0221]
5. It is assumed that tIA = 0.
[0222]
* Part 2-3-2
1. It is assumed that the search table is HIA2 → HAhia.
[0223]
2. hia = 1-hia.
[0224]
3. If there is packet data in HAhia, it outputs it to OIA.
[0225]
4. Clear HAhia.
[0226]
5. It is assumed that the search table is HIA1 → HAhia.
[0227]
6. It is assumed that tIA = 0.
[0228]
Table management module 22 (Claims 2, 3, 4, 6.7): The table management module 22 manages the search table HIA1 corresponding to the input port IA for each input terminal to the packet matching device 10, and stores the input port IB Are managed in the search tables HIB1, HIB2, HIB3 corresponding to. Further, for the input ports IA and IB, there are arrays DIA1, DIB1, DIB2, and DIB3 composed of keys, respectively. Each data registered in the search table is composed of a set of (packet data, Mbit).
[0229]
Mbit indicates the attribute of the packet corresponding to the key. The initial value of Mbit is off. When a packet corresponding to the key is found, Mbit is turned on. Therefore, by referring to the Mbit, it is possible to know whether or not a packet corresponding to the key has been found.
[0230]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the IA side or IB side.
[0231]
A search operation when attr = IA is described. n is an integer such that n = 1, 2, 3,. When attr = IB, n = 1 and the operation is such that A and B are interchanged.
[0232]
Search for HIBn based on the key (if n> 1, check for all n).
[0233]
-When data can be obtained from HIBm (m: arbitrary n):
* HIBm (key): When Mbit == Off:
1. “HIBm (key): packet data” is output to TOUT.
[0234]
2. HIBm (key): Mbit = ON.
[0235]
* HIBm (key): When Mbit == ON, outputs NULL to TOUT.
[0236]
When data cannot be obtained from HIBm (m = any n):
1. Output NULL to TOUT.
[0237]
2. Data consisting of (bucket data, Mbit = off) is stored in HIA1 (key).
[0238]
3. Save the key in DIA1.
[0239]
Next, the table management module 22 manages the search tables HIA1, HIB1, HIB2, HIB3 and the arrays DIA, DIB1, DIB2, DIB3. This function, as an initial operation, secures the areas of the search tables HIA1, HB0, HB1, HB2, arrays DIA, DB0, DB1, DB2, reads the deletion condition T, and reads tIA = 0. It is assumed that tIB = 0. Also, HIB1 → HB0, HIB2 → HB1, HIB3 → HB2, and DIB1 → DB0, DIB2 → DB1, DIB3 → DB2. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Note that hib starts with 0, and this value is a 2-bit counter (when incremented, continues as 0, 1, 2, 0, 1, 2,...).
[0240]
When tIA = T:
1. The keys are sequentially referred to from DIA1, and if HIA1 (key): Mbit == off, “HIB3 (key): packet data” is output to OIA.
[0241]
2. Clear the contents of HIA1 and DIA1.
[0242]
3. It is assumed that tIA = 0.
[0243]
When tIA <T:
1. This function does not work.
[0244]
-When tIB = T:
-Part 1-1
1. The keys are sequentially referred to from DIN3, and when HIB3 (key): Mbit = off, “HIB3 (key): packet data” is output to the OIA.
[0245]
2. If a = hib + 1, then HIB2 → HBhib, HIB3 → HBa, and DIB2 → HBhib, DIB3 → DBa.
[0246]
3. hib = hib-1, HIB0 → HBhib, DIB0 → DBhib.
[0247]
4. Clear the contents of HIB0 and DIB0.
[0248]
5. It is assumed that tIB = 0.
[0249]
-Part 1-2
1. If a = hib + 1, then HIB2 → HBhib, HIB3 → HBa, and DIB2 → HBhib, DIB3 → DBa.
[0250]
2. hib = hib-1, HIB0 → HBhib, DIB0 → DBhib.
[0251]
3. The keys are sequentially referred to from DIB0, and when HIB0 (key): Mbit = off, “HIB0 (key): packet data” is output to the OIA.
[0252]
4. Clear the contents of HIB0 and DIB0.
[0253]
5. It is assumed that tIB = 0.
[0254]
-Part 2
1. The keys are sequentially referred to from DIB3, and if HIB3 (key): Mbit = off, “HIB3 (key): packet data” is output to OIA.
[0255]
2. Clear the contents of HIB3 and DIB3.
[0256]
3. If a = hib + 1, then HIB2 → HBhib, HIB3 → HBa, and DIB2 → DBhib, DIB3 → DBa.
[0257]
4. hib = hib-1, HIB0 → HBhib, DIB0 → DBhib.
[0258]
5. It is assumed that tIB = 0.
[0259]
-Part 3-1
1. The keys are sequentially referred to from DIB3, and if HIB3 (key): Mbit = off, “HIB3 (key): packet data” is output to OIA.
[0260]
2. If a = hib + 1, then HIB2 → HBhib, HIB3 → HBa, and DIB2 → DBhib, DIB3 → DBa.
[0261]
3. hib = hib-1, HBhib and DAhib are cleared.
[0262]
4. HIB0 → HBhib, DIB0 → DBhib.
[0263]
5. It is assumed that tIB = 0.
[0264]
-Part 3-2
1. If a = hib + 1, then HIB2 → HBhib, HIB3 → HBa, and DIB2 → DBhib, DIB3 → DBa.
2. hib = hib-1.
[0265]
3. The keys are sequentially referred to from the DBhib, and when HBhib (key): Mbit = off, “HBhib (key): packet data” is output to the OIA.
[0266]
4. Clear HBhib and DAhib.
[0267]
5. HIB0 → HBhib, DIB0 → DBhib.
[0268]
6. It is assumed that tIB = 0.
[0269]
When tIB <T:
1. This function does not work.
[0270]
Table management module 22 (Claims 2, 3, 4, 6, and 8): The table management module 22 manages the search table HIA1 corresponding to the input port IA, and searches the search tables HIB1, HIB2, and HIB2 corresponding to the input port IB. Manages HIB3. Each piece of data registered in the search table is packet data, and is composed of only packet data.
[0271]
The input to the table management module 22 is given from the input / output module 21 through TIN, and is constituted by a set of (key, data, attr). key indicates a search key, data indicates packet data, and attr indicates whether data is input from the IA side or IB side.
[0272]
A search operation when attr = IA is described. When attr = IB, n = 1 and the operation is such that A and B are interchanged.
[0273]
Search for HIBn based on key (if n> 1, check for all n)
-When data can be obtained from HIBm (m: arbitrary n):
1. HIBm (key): Outputs packet data to TOUT.
[0274]
2. HIBm (key): deletes packet data from HIBm (key).
[0275]
When data cannot be obtained from HIBm (m: arbitrary n):
1. Output NULL to TOUT.
[0276]
2. (Packet data) is stored in HIA1 (key).
[0277]
Next, the table management module 22 manages the search tables HIA1, HIB1, HIB2, and HIB3. In this function, as an initial operation, after the areas of the search tables HIA1, HB0, HB1, and HB2 are secured, the deletion condition T is read, and tIA = 0 and tIB = 0. Also, HIB1 → HB0, HIB2 → HB1, HIB3 → HB2. Here, tIA and tIB indicate a timer (or a counter = the number of packets). Then, it operates as follows. Note that hib starts with 0, and this value is a 2-bit counter (when incremented, continues as 0, 1, 2, 0, 1, 2,...).
[0278]
When tIA = T:
1. If packet data exists in HIA1, it outputs it to OIA.
[0279]
2. Clear the contents of HIA1.
[0280]
3. It is assumed that tIA = 0.
[0281]
When tIA <T:
1. This function does not work.
[0282]
-When tIB = T:
-Part 1-1
1. If there is packet data in HIB3, it outputs it to OIB.
[0283]
2. If HIB2 → HBhib, a = hib + 1, then HIB3 → HBa.
[0284]
3. hib = hib-1, and HIB0 → HBhib.
[0285]
4. Clear the contents of HIB0.
[0286]
5. It is assumed that tIB = 0.
[0287]
-Part 1-2
1. If HIB2 → HBhib, a = hib + 1, then HIB3 → HBa.
[0288]
2. hib = hib-1, and HIB0 → HBhib.
[0289]
3. If there is packet data in HIB0, it outputs it to OIB.
[0290]
4. Clear the contents of HIB0.
[0291]
5. It is assumed that tIB = 0.
[0292]
-Part 2
1. If there is packet data in HIB3, it outputs it to OIB.
[0293]
2. Clear the contents of HIB3.
[0294]
3. If HIB2 → HIBhib, a = hib + 1, then HIB3 → HBa.
[0295]
4. hib = hib-1.
[0296]
5. It is assumed that tIB = 0.
[0297]
-Part 3-1
1. If there is packet data in HIB3, it outputs it to OIB.
[0298]
2. If HIB2 → HBhib, a = hib + 1, then HIB3 → HBa.
[0299]
3. hib = hib-1, HBhib and DAhib are cleared.
[0300]
4. HIB0 → HBhib.
[0301]
5. It is assumed that tIB = 0.
[0302]
-Part 3-2
1. If HIB2 → HBhib, a = hib1, then HIB3 → HBa.
[0303]
2. hib = hib-1.
[0304]
3. If the packet data exists in the HBhib, it outputs it to the OIB.
[0305]
4. Clear HBhib.
[0306]
5. HIB0 → HBhib.
[0307]
6. It is assumed that tIB = 0.
[0308]
When tIB <T:
1. This function does not work.
[0309]
"Time stamp processing mechanism 13" (Claim 9): It is assumed that a packet data stream composed of a pair (a, b) is transmitted from the input / output module 21 of the matching mechanism 12. Further, a has a time stamp Ta and data a such as (Ta, a), and b has a time stamp Tb and data b such as (Tb, b). In this case, when (a, b) is given as an input, data consisting of a set of (Ta, Tb, a) (or (Ta, Tb, b)) is output as a packet data stream.
[0310]
Stream synchronizer 30 (Claim 10): The stream synchronizer 30 includes a firing mechanism 31 and an SIQV header reproducing mechanism 32, as shown in FIG. In order to perform synchronization control using this apparatus, it is necessary that a packet including a sequence number is periodically inserted when a packet is copied by a probe and the data is sent to a monitoring server as stream data. . This is temporarily called an SIQV header.
[0311]
The SIQV header is generated at regular intervals by the packet probe device, and the sequence number is incremented each time the SIQV header is created. The stream synchronizer 30 performs synchronization in units of streams divided by SIQV headers having the same sequence number, thereby enabling synchronous execution control for absorbing errors in the packet data stream collection time.
[0312]
FIG. 7 shows the basic operation of the firing mechanism 31 included in the stream synchronization device 30. As shown in FIG. 7, firing occurs when SIQV headers having the same sequence numbers are available on both sides of the input. Thereafter, data after the SIQV header is read as needed. If the SIQV header appears only on one side of the input, the input side is locked and data reading is stopped. Performing the execution in units of streams divided by the SIQV header has an advantage that the maximum amount of each link buffer can be calculated.
[0313]
FIG. 8 shows an operation example in which the firing mechanism 31 controls execution in the following manner.
[0314]
-When there is a synchronization packet only at the beginning of one side input
(FIGS. 8 (1), (3), (6)): Wait for a synchronization packet to arrive at the other input.
[0315]
When synchronous packets having the same sequence number as the head of both inputs are prepared (FIGS. 8 (2) and 8 (4)): The synchronous packets are removed, the subsequent data stream is read, and sent to the search table. This is called firing. At this time, the sequence number of the synchronization packet is stored in a variable called Sequence register.
[0316]
When there is a synchronization packet having a different sequence number at the beginning of both inputs (FIG. 8 (5)): The data stream following the synchronization packet having the smaller sequence number is read into the subsequent data stream after removing the synchronization packet. , Send to search table.
[0317]
When there is a synchronous packet having a sequence number smaller than the value of Sequence register: remove the synchronous packet, read the subsequent data stream, and send it to the search table.
[0318]
Note that the stream synchronizer 30 has an SIQV header playback mechanism 32. The SIQV header reproducing mechanism 32 is a mechanism for reproducing the synchronization packet removed by the firing mechanism 31. This mechanism generates a synchronization packet when the firing is performed by the firing mechanism 31 and outputs it to all output ports. At this time, the sequence number of the fired synchronization packet is set as the sequence number of the synchronization packet newly generated by the present mechanism. If the firing is not performed, the packet stream output from the search table is output.
[0319]
FIG. 9 illustrates a quality monitoring network and a monitored network. The monitored network is composed of a host 40, a router 41, and a test packet generating host 42, and these are IP-connected using Ethernet and frame relay. The quality monitoring network includes a packet probe device 43 and a monitoring station 44 (monitoring server), and these are IP-connected using Ethernet or ISDN. Furthermore, the clock of the packet probe device 43 is synchronized using the ISDN, and the clock of the packet probe device 43 and the monitoring station 44 are very accurately synchronized.
[0320]
The packet probe device 43 has a probe interface for probing Ethernet and frame relay of the monitored network (O in the figure). This probe monitors IP packets flowing through the Ethernet and frame relay of the monitored network. The probed result is sent to the monitoring station 44, where real-time packet tracking is performed.
[0321]
An analysis program (Harumoto Fukuda, Satoshi Ono, Naohisa Takahashi, used in a monitoring server (Data Collection Server) in a network quality monitoring network as shown in FIG. 9, "Design and Realization of an Internet QoS Visualizer" IEICE Transactions on Multimedia An example is the use of mpf nodes in the Special Issue on Network / Service Quality, Jul., 1997). The SIQV header required for synchronizing the packet data stream is inserted into the packet data stream by the packet collection device, and is changed to the SIQV header format at the Pin node.
[0322]
The mpf is configured as illustrated in FIG. It is assumed that the analysis program is given as FIG. The data stream delimited by the SIQV header generated at Pin arrives at the input of mpf. The firing mechanism 31 of the stream synchronizer 30 performs firing control according to the sequence number of the SIQV header, and data is taken in. Further, the packet matching device 10 performs a matching process. The data processed in this manner is output to a total of three output destinations: unmatch, unmatch, and match. The SIQV header is provided by the SIQV header reproducing mechanism 32 and output from the mpf.
[0323]
When a packet is copied by the probe, it is conceivable to send a data stream to the monitoring server with a time stamp added. The input to the mpf is a stream composed of a set of packet data and a time stamp indicating time, such as (t, p). In this case, if the input is (t1, p) or (t2, p) by the time stamp processing mechanism 13, the matched data is output as (t1, t2, p). The time difference is calculated by comparing t1 and t2.
[0324]
As described above, by performing the processing of the mpf node in real time, the fluctuation such as the one-way delay can be calculated in real time. Further, by manipulating the time stamp of the data output in this manner, packet tracking in real time, that is, the operation of the packet on the network can be observed.
[0325]
【The invention's effect】
Claim 1, 3 : By using the present invention on a monitoring server, packet tracking can be performed in real time from continuous data transmitted from a plurality of points. Further, by applying the present invention to a packet network and performing packet tracking in real time, it is possible to grasp quality fluctuations in real time. By using the packet matching device that realizes the second aspect, it is possible to select the same packet data from packet data sent in a stream and perform packet matching in real time.
[0326]
Claim 4 : When using a packet matching apparatus, hashing is used in a matching mechanism, so that packet matching can be performed in real time.
[0327]
Claim 5 : By registering input data in a search table using a Patricia tree, real-time packet matching becomes possible.
[0328]
Claim 6 A: When both input rates differ with time, it is possible to reliably register a packet to be subjected to packet matching in a search table.
[0329]
Claim 7 A: When the input rate on one side is very high, it is possible to reliably register a packet to be subjected to packet matching in the search table.
[0330]
Claim 8 : When it is very costly to delete packet data from the search table, it becomes possible to operate a function of outputting a packet whose search failed in real time.
[0331]
Claim 9 : When it is very costly to delete the entire search table, it becomes possible to operate the function of outputting a packet whose search failed in real time.
[0332]
Claim 2, 10 : By calculating a difference or the like, it is possible to check the time difference of the same packet data and the fluctuation of the time difference between two packet data transmitted in a stream.
[0333]
Claim 11 : Claim if delay fluctuation or delay difference from each probe to the monitoring server is large 4 ~ 9 The delay error is minimized, the packet to be packet-matched is fetched into all tables, and the packet matching can be performed normally without modifying the invention. Further, when considering the network configuration from each probe to the monitoring server, it is not necessary to consider the transfer delay of the data stream.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating a real-time packet tracking method of the present invention.
FIG. 2 is a diagram showing input / output ports of a packet matching device.
FIG. 3 is a configuration diagram of a packet matching device.
FIG. 4 is a configuration diagram of a matching mechanism 12.
FIG. 5 is a diagram showing an example of execution of masking.
FIG. 6 is a configuration diagram of a stream synchronization device.
FIG. 7 is a diagram illustrating an example of a method of synchronizing a packet data stream.
FIG. 8 is a diagram showing a sequence number and early control.
FIG. 9 is a diagram showing a network quality management network.
FIG. 10 is a configuration diagram of an mpf node.
FIG. 11 is a diagram showing an analysis program.
FIG. 12 is a diagram showing a packet network and a probe.
FIG. 13 is a diagram showing a conventional packet tracking method.
[Explanation of symbols]
10. Packet matching device
11 Masking mechanism
12 Matching mechanism
13 Timestamp mechanism
21 I / O module
22 Table management module
30 Stream synchronizer
31 Ignition mechanism
32 SIQV header playback mechanism
40 hosts
41 router
42 Host for test packet generation
43 Packet Probe Device
44 monitoring station

Claims (12)

In a system for receiving two packet streams in which packets of data are continuously transmitted, for each packet of each packet stream, a part of the packet data is extracted to create a search key. It checks whether packets with the same search key have already been sent for the two packet streams, and if so, outputs a pair of those packets. A real-time packet tracking method that outputs incoming packets to another output port. The real-time packet tracking method according to claim 1, wherein synchronization of both data is performed so that matching is correctly performed for given data. 2. Description of the Related Art In a system for receiving two packet streams in which packets of data are continuously transmitted, a search key is created by extracting a part of the packet data for each packet in each packet stream. Masking means and, for the two packet streams, check if packets with the same search key have already been sent, and if so, output those packet pairs and wait for a certain period of time to find a packet with the same search key. A packet matching device having matching means for outputting a packet that has not been sent to another output port. 4. The packet matching apparatus according to claim 3 , wherein the matching unit creates a search database for the input port using a hash table. 4. The apparatus according to claim 3 , wherein the matching unit creates a search database for the input port using a Patricia tree. It said matching means for the two input ports, device according to claim 4 or 5, wherein utilizes two tables individually. It said matching means, the two input ports, using a hash or Patricia tree, one on one side and the other three apparatus according to any one of claims 3 to 6, using a table. The apparatus according to any one of claims 4 to 7 , wherein the matching unit holds, in addition to the search database, an array including a set of a search key and an attribute indicating whether the search has succeeded or failed. It said matching means, upon a successful search by the search key, apparatus according to any one of claims 4 to delete data from the lookup table 7. 4. The apparatus according to claim 3 , wherein said matching means has a function of comparing the time stamps of the matched packets when a data string composed of a set of a packet and a time stamp is given. The packet matching device according to claim 3, further comprising a stream synchronization device that synchronizes the data provided to the two input ports so that the two data are synchronized correctly . The stream synchronizer includes a firing means for removing synchronization packet performs control to capture the stream data is a continuous packet sequence to the retrieval table, the header reproducing means for reproducing a synchronized packet that has been removed by the ignition means, wherein Item 12. The packet matching device according to Item 11 .

Images