Apparatus and method for monitoring data flow at a node on a network

Device and method for monitoring data flow at network node

<u><b>Background of the invention</b></u>

<u><b>1. Technical Field of Invention</b></u>

The invention relates to the field of digital communication, in particular to a system and method for exchanging data packets at a switching node used in a digital data network and monitoring data flow at the switching node.

<u><b>2. Narration of related skills</b></u>

The development of digital networks has facilitated the transfer of information, including data and programs in digital computer systems and many other forms of devices. Various forms of the Internet are constantly evolving and are achieved through different ways of transmitting information. In modern networks, information is transmitted through meshes in switching nodes that are interconnected by various forms of communication links. This form of mesh connection permits to provide several paths to the network from one computer system or other device to another computer or other device.

The information transmitted from a source device to a destination device is usually transmitted in the form of fixed or variable-length data packets, where each data packet is usually exchanged by a switching node on a communication link. Received and sent to another communication link to cause the data packet to be transmitted to the destination device or another switching node through a path to the destination device. Typically, each packet contains address information, which includes the source address to identify the device that generated the packet and the destination address to identify the specific device that will receive the packet.

Typically, a switching node includes one or more input ports, where each input port is connected to a communication link on the network to receive data packets, and one or more output ports, where each output port is connected to the network A communication link on the way to send a packet. Generally, each node also includes a switching structure that couples data packets from the eighth port to the output for transmission.

Typically, a network service provider maintains and operates one or more switching nodes, which can pass data packets from an input communication link through an exchange structure to an output communication link. These providers charge customers who pass data through network nodes. Generally, these fees are related to the maximum data rate at which customers can pass data through the nodes.

Each link on a node is usually assigned at least one "class of service", which is about the maximum permitted data rate provided to customers using the link, which is based on the fees paid by the customer to the supplier. In many cases, each link can be assigned multiple "levels of service" to a single user or multiple users.

What ISPs are interested in is how to monitor or monitor data traffic at each link to determine whether the customer's use of their assigned links is within the limits specified by the contract. When the use of the data rate exceeds the contract limit, the data packet can be identified and marked "out of contract". In many cases, it is extremely important to carefully monitor the traffic flow on each link in each service level. It is also important to identify data packets that are related to a particular data packet that may exceed the contract level. needs. For example, if a particular data packet slightly exceeds the contract, the data packet must be marked. In addition, in some cases where links are overused, it is necessary to mark data packets in this way.

In some systems, the degree to which a packet exceeds the associated contract data rate is used to prioritize packet abandonment. Packets that only slightly exceed the contract data rate are assigned a relatively low "discardeligibility value", while packets that significantly exceed the maximum data rate are assigned a higher discontinuation value. Therefore, if a particular packet must be discarded, those with a higher revocation value are more likely to be relinquished than those with a lower revocation value.

Several methods have been used to monitor data streams in multiple connections with multiple service levels. One commonly used method is called the "leaky bucket" method. In this method, the memory or temporary storage location, often referred to as a "bucket", is assigned to each of a plurality of links and a class of service. Each storage location or storage maintains a certain number of data units for its designated links and service levels. A data unit can be a byte of data or a group of data units. data bytes), where each data packet sends multiple data tuples. For each packet, a preset critical number of data units is generated and stored, which is related to the maximum permissible data rate of the connection and service level. When a data packet is received, the number of data units (bytes) will be added to the current value or number in the packet, and the updated value will be compared with the threshold value. If the updated value exceeds the threshold, the input packet will be marked with a mark that exceeds the threshold. Because the data rate to be monitored is not the total amount of data received, the value or number stored in each storage is periodically reduced by a predetermined amount of data, which is related to the maximum permitted data rate and Time period is related. This reduction is often referred to as a "storage leak." By leaking the storage at a correct preset rate, it can be determined that when the number of data units in the storage exceeds a preset threshold, its maximum permitted data rate has been exceeded.

In order to identify short bursts of large amounts of data exceeding the maximum permissible data rate, each reservoir must be leaked, and comparisons with critical values performed as often as possible. These short spleen bursts may be missed where the reservoir has not been leaked or frequently inspected. In a relatively small system with a small number of reservoirs, the system can quickly cycle through each reservoir so that short bursts of large amounts of data can be identified as exceeding contract limits. In this system, the reservoir has the form of a memory location, and its leaks and inspections are performed in the system software. However, the system expands as the number of connections and service levels increases, and at the same time, the leakage and inspection cycle for each reservoir becomes longer. Therefore, the maintenance of the reservoir cannot be performed frequently, and the chance of identifying short bursts of large amounts of data is reduced. As a result, the data rate monitoring of such a system becomes less accurate.

<u><b>Summary of invention</b></u>

The present invention is a device and method for monitoring or monitoring data flow at a network node, wherein the node causes data to be transmitted on at least one link having at least one service level. The data is transmitted in the form of data packets, and each data packet includes at least one data unit. For each of at least one selected link and service level, a count value in an updatable value counter is stored in the storage device according to a maximum permitted data rate related to the selected link and service level. The rate of decision increases. After the data packet is received, the number of data units in the data packet is counted. An adjusted updatable value is calculated by adjusting the updatable value based on the count value when the data packet is received and the number of data units in the data packet. The updatable value of the adjustment is compared to a preset threshold value related to the selected link and service level. The data packets are marked according to whether the adjusted updateable value exceeds the preset maximum data rate determined by the threshold value.

In a specific embodiment, the adjusted updateable value is calculated by calculating the difference between the updateable value and the count value when the data packet is received. Then, the calculated difference value can be added to the data sheet set number in the received data packet to calculate the updated value of the adjustment. In a specific embodiment, the adjusted updateable value is used to update the updateable value, for example, by adding the adjusted updateable value to the number of data units in the received data packet, and storing the obtained sum value. Back to the storage device as the updated value.

In a specific embodiment, each link may include multiple service levels, and each service level has a unique maximum permitted data rate. Therefore, the storage device may include multiple individual storage areas. For example, the storage device may be a semiconductor memory, such as a static random access memory (SRAM), which has multiple addressable locations. Then, the storage device stores the plurality of updateable values to provide to any one of the plurality of links and / or the plurality of service levels.

In a specific embodiment, each data packet is related to a discard eligibility value, which sets a priority order for discarding data packets. In general, if it is determined that a specific packet must be discarded due to excessive data traffic or data congestion, a packet designated with a higher discard value will be easily discarded. Therefore, in the present invention, the data packet can be marked according to whether it causes the threshold value to be exceeded by changing the abolition appointment value of the data packet. In other words, if a certain packet causes the threshold to be exceeded, its abolition appointment value will increase, so that the priority of abolishing the packet is advanced.

In a specific embodiment of the present invention, a connection and a service level may be assigned multiple preset thresholds, so that the abolition of the appointment value may be set to one of multiple corresponding levels, depending on the threshold being exceeded. . In a specific embodiment, an additional storage device is provided to allow multiple levels of monitoring so that multiple revocation appointments can be specified. Where a second storage device is provided, a second updateable value associated with the selected link and service level is stored in the second storage device. A second adjusted updateable value is calculated based on the count value when the data packet is received and the number of data units in the data packet. The updatable value of the second adjustment is compared with a second preset threshold value related to the selected link and service level, wherein the second preset threshold value is selected to determine the value of the abolition of the packet. A second level. The input data packet is marked according to whether the adjusted updateable value exceeds the maximum allowable data rate determined by the second preset threshold. In a specific embodiment, if the data packet is found to cause the first preset threshold to be exceeded, the data packet is analyzed according to the second and other levels.

Therefore, in the present invention, a single counter is effectively used to reduce the values stored in all the reservoirs at the same time. This single counter can be used in counter derivation circuitry to derive the count value provided to any number of links and any number of packets in the service class. In the present invention, a processing stage storage (which can be implemented by a semiconductor static random access memory (SRAM)), a counter, and a counter derivation circuit can be implemented in hardware. Therefore, the periodic round-robin diminishing or "leakage" that occurred in previous leaky storage systems can be eliminated. The storage value can be reduced and thoroughly inspected at very short intervals, making short Large bursts within a time period can be identified. Such a result is far more accurate in monitoring than the results of previous techniques. Since the monitoring method proposed by the present invention has high accuracy, it can be applied In very large systems with numerous connections and service levels.

The present invention can be applied to various networks that need to monitor data traffic on a network link. For example, the present invention can be implemented in a switching node, such as "System and Method for Switching Packages in a Network" in US Patent Application Serial No. 09 / 108,771 filed by Schwartz et al. On July 2, 1998. As disclosed in this article and assigned to the same trustee of the present invention. Its application is for reference of the present invention.

<u><b>Detailed description of the preferred embodiment</b></u>

FIG. 1 illustrates a computer network 10 including a plurality of switching nodes. nodes) 11 (1) to 11 (N), usually with the reference number 11 table, to transmit data representing the signals between several devices, as shown in Figure 1, these devices usually refer to a wide area network (WAN) The packet source / destination devices in 12 (1) to 12 (M) are usually listed in reference numeral 12. As a skilled artist, these packet source / destination devices 12 include a specific device, such as a computer system or other device, which stores, generates, processes, or uses digital data, and a local area network (LAN) composed of such devices. ), And even Wide Area Networks (WAN). Each packet source / destination device 12 is connected to the entire communication link. It is usually connected to a switching node 11 by referring to the reference numeral 13 to facilitate the transmission of its incoming data or its output. Reception of information. The switching nodes 11 are connected to each other through a communication link. The communication link is usually shown by the reference numeral 13 to facilitate the transmission of information between the switching nodes 11. The communication link can use any convenient information transmission medium, including, for example, cables that carry electronic signals and optical fiber links that carry optical signals. Each link is preferably bidirectional, allowing the switching nodes 11 to transmit and receive signals between each other, and to connect customer-oriented equipment 12 in the same link; according to the media type selected for the individual communication link 13, Multimedia can be provided to pass signals in opposite directions to provide a two-way link.

Data in the network 10 is transmitted in the form of packets. Generally, a packet includes a header portion and a data portion. The header section includes information to assist in sending packets in the network, and has specific information according to a specific packet routing protocol used to send packets in the network. In the connection with the network 10, any well-known packet transmission protocol may be used; in a specific embodiment, the Internet Protocol (IP) is used by the user. In any case, the header usually includes address information, which includes a means to identify a particular source device 12 (m_S) Source address, where the source device 12 (m_D) Generates the packet and the destination address, which identifies the specific destination device 12 (m_D)By. In the Internet Protocol (IP), packets may have various lengths, and the header usually includes length information to identify the length of the packet. Typically, the packet length is identified as the number of bytes or the number of byte groups, where a set of byte groups includes a predetermined number of set bytes. The header usually includes other information, for example, it includes protocol identification information used to identify a specific protocol, and the protocol is used to define the structure of the packet. The data part includes the data payload of the packet. In addition, as part of the data or other parts, the packet can also include error detection information, which can be used to determine whether an error occurred while transmitting the packet.

In the production of the intended device 12 (M_D), The source device 12 (m_S) Sends the packet to the switching node 11 (n) to which it is connected. The switching node will use the destination address in the packet to identify a route that connects a destination address and a communication link 13, where the communication link 13 is connected to the switching node, and on the switching node, the The packet is forwarded to the destination device 12 (M_D) If switching node 11 (n) is connected to destination device 12 (M_D), Or relay to the device 12 (m_D) Another switching node 11 (n ') (n n') on the path. If the switching node can identify the path of the received packet, it will forward the packet on the communication link identified by the path. Any switching node 11 (n) receiving a packet will perform a similar operation. If all switching nodes have individual paths to the destination address, the final packet will reach the destination device 12 (M_D)。

FIG. 2 includes a schematic block diagram of a specific embodiment of a switching node 11 according to the present invention. Node 11 is roughly composed of multiple input terminal modules 20 (1), 20 (2) ... 20 (N), which is usually shown by the reference numeral 20, and the corresponding output terminal modules 21 (1), 21 (2) ... 21 (N), usually listed by reference number 21. The input terminal module 20 and the output terminal module 21 are connected to the processing circuit and the switching structure 24, and the control data is transferred from the input terminal module 20 to the output terminal module 21. Generally speaking, each input module 20 (N) can include one or more input terminals 22 (N) (1) to 22 (N) (M), which are individually connected to multiple communication links. 13 (N) (1) to 13 (N) (M). Similarly, each output module 21 (N) may include one or more output terminals 23 (N) (1) to 23 (N) (M), which are individually connected to multiple communication links 13 (N) (1) to 13 (N) (M). The data received on each link 13 (N) (M) is transmitted from the corresponding input module 20 (N) to the appropriate output module 21 (N) through the processing circuit and switching structure 24. And further output to the appropriate link 13 (N) (M) network.

Each link 13 can be assigned one or more service levels and one or more customers using the link. The data stream starting from each link can be monitored by the data monitoring or data monitoring circuit 26 of the present invention. Generally, in the present invention, each input module 20 (1), 20 (2) ... 20 (N) includes a corresponding monitoring circuit 26 (1), 26 (2) ... 26 ( N). It is worth noting that the monitoring circuit 26 does not need to be installed in the input module 20. On the other hand, the monitoring circuit 26 may be installed in the processing circuit and switching structure 24 and / or the output module 21. It is worth noting that the above-mentioned network node configuration is only used to illustrate the application of the present invention to a node structure including an input / output terminal module for supporting multiple links, wherein the multiple links can be processed by Circuits are connected to the switching structure. I will understand that the present invention can be used with other node structures, including but not limited to node structures that do not include input / output end modules and / or processing circuits and switching structures, and nodes that support a single input / output connection.

FIG. 3 includes a schematic block diagram of a specific embodiment of the monitoring circuit 26 of the present invention. As shown in FIG. 3, the data packet is received by the monitoring circuit 26 on the line 27, and processed by the packet processing circuit 28 and output to the line 31.

FIG. 4 includes a schematic diagram illustrating a part of a field included in the data packet 36. The packet 36 includes a header portion 38 and a data portion 40. A typical header includes a discardeligibility field and a packet length field. The revocation appointment message group includes a revocation appointment value, which sets the priority of the revocation packet, and the packet length value is the number of data sheets in the data portion 40 in the data packet 36. Typically, the data unit is a byte, so that the packet length value is the number of bytes in the data portion 40. In other systems, the packet length is the number of byte groups. For example, in a particular system, bytes are packed in thirty-two (32) groups, and the packet length value is 32. For example, in such a system, a packet length value of 32 corresponds to 32 groups of 32 bits, that is, 1,024 (1024) bits of data.

The packet processing circuit 28 receives a packet 36 and reads the discarded appointment value and the packet length value in the packet. These start values are transmitted to the comparison circuit 35. The comparison circuit 35 performs a comparison process described in detail below to determine whether a packet causes the maximum permitted data rate of the identified link and service level to be exceeded. In the preferred embodiment, the comparison circuit 35 adjusts the packet discarding value according to whether a preset threshold value assigned to the link and service level is exceeded. After that, the processor 30 reassembles the packet with the new revocation value and transfers it from the monitoring circuit 26 on the line 31.

The comparison circuit 35 includes a circuit for determining whether a packet causes the maximum permitted data rate of the connection and service level to be exceeded. In the illustration of this specific embodiment, the comparison circuit 35 can also define the rate at which the data rate is exceeded and specify a revocation value according to the level.

In the specific embodiment shown in FIG. 3, three processing levels are used to compare the three preset thresholds with the number of data units, that is, bytes or groups, which are linked to a specific service level Recipients. These three processing levels allow the level beyond which four thresholds are exceeded. Therefore, this system permits four possible settings for the abolition of appointment values related to the inspected packets.

In this embodiment, the comparison circuit 35 includes a first-level processor 50, a second-level processor 52, and a third-level processor 54. Each of the three processors 50, 52, and 54 is individually connected to a memory 56, 58, and 60, which are all implemented by a static random access memory (SRAM) in this embodiment. . Each memory is assigned a memory location or location group to the link and service level being monitored. These locations or location groups, ie "storages", maintain an updateable value that can be updated when a data packet is received. Each memory 56, 58, and 60 also stores a preset threshold value for each link and service level, which is compared with the corresponding updateable value when a new data packet is received.

In a specific embodiment of the present invention, the first-level processor 50 uses the memory value stored in the first memory 56 and a corresponding threshold value to perform the first comparison step. If the threshold is exceeded, the discarding appointment value of the packet is incremented and the comparison processing is advanced to the second-level processor 52. The second-level processor 52 uses the memory value stored in the second memory 58 and its corresponding threshold value to perform the second comparison step. If the threshold is exceeded, the discarding appointment value of the packet is incremented and the comparison processing is advanced to the third-level processor 54. If the threshold value of the second level is not exceeded, the revocation value of the second level can be stored back with the data packet by the processor 30 of the packet processing circuit, and the packet with the updated revocation value can be removed from the monitoring circuit 26 Send it out. If necessary, a third-level processor 54 may be used to perform the comparison to increase the packet revocation value. At any level, if the critical value is not exceeded, the revocation appointment value can be stored back with the data packet by the processor 30, and the packet with the renewed revocation appointment value can be transmitted from the monitoring circuit 26.

As shown in FIG. 3, the packet processing circuit 28 also includes a counter 32 and a count value deriving circuit 34. In a specific embodiment, the counter is a free-running counter, which is incremented at a predetermined rate. The derivation circuit 34 can be used to derive a count value, which is incremented at any predetermined rate. Therefore, the various counts generated can be used by the comparison circuit 35, which will be described in detail below, to determine whether data packets received at various links and various service levels cause the maximum permitted data rate to be exceeded. It is worth noting that, looking at the whole description, the mentioned counter value is not necessarily the value stored in the actual counter. This value may be one of the values generated by the derivation circuit 34. It is also worth noting that, with or without a derivation circuit, multiple counters can be used instead of using a single counter and derivation circuit.

FIG. 5 is a schematic flowchart of a specific embodiment of a data flow monitoring method according to the present invention. The data flow monitoring method of the present invention will be discussed in detail below with the assistance of FIG. 3 and FIG. 5. As shown in step 100, the packet processing circuit 28 waits to receive a packet. When the packet is received, at step 102, the link index L defining the link where the received packet is located, and the service level of the link are read out. The packet is also analyzed to read the packet length value and the discarded appointment value of the input packet. This information is then transmitted to the first-level processor 50. First determine whether the current revocation appointment value is equal to the S-level revocation appointment value. If not, the processor of this level does not process the packet, and the flow proceeds to the next step 106. If the revocation appointment value of the received packet is at an appropriate level of this level, the link index L and the service level are used to access the appropriate memory location in the associated static random access memory (SRAM), ie "Body", which is the first memory 56 at the first level.

The maximum permitted memory value (critical value) M and the current memory content B are read from the static random access memory (SRAM) in step 108. In step 110, the difference between the current storage content B and the count value C is calculated, that is, D = BC. The calculation of this difference effectively reduces or "leaks" the inspected packets. If the difference D is less than zero, then D is set to zero. In step 112, the obtained difference value is then added to the number of data bytes or the number of data byte groups contained in the input packet. This effectively calculates a new adjusted bank content value E. In step 114, this adjustment value E is compared with the threshold value of the reservoir. If the adjustment value E exceeds the storage threshold MI, then in step 116, the value of the abolishment of the packet will also increase. Subsequently, in a specific embodiment, the content value of the bank at this level is updated by adding the count value and the difference (D) in step 118, and the obtained sum value is stored back to the static random access memory. The volume (SRAM) 56 is used as the new storage value B related to the connection index L of the received packet and the service level, that is, B = D + C. In another specific embodiment, the content of the storage body is updated by adding as many data units as possible to the content of the storage body within a range not exceeding a critical value, that is, B = M. Thereafter, in step 120, the process continues to the next level, in this example, the second level, where the comparison process determines whether the input packet causes the second level threshold M to be exceeded. Referring to step 114 again, if the adjusted storage value does not exceed the critical value M, in step 122, the content of the storage is updated by adding the count value C to the value E and storing it back to the storage The position is taken as the new value B of the contents of the bank, that is, B = E + C. Subsequently, in step 124, the packet processing circuit 28 generates a packet by using the current revocation appointment value. The packet is then forwarded to a packet processing circuit 28 on line 31. The process then returns to the starting point for processing of newly received packets.

This processing flow is executed at each level as the abolition appointment value increases at each level when the threshold M is exceeded. The final packet is reassembled by the new revocation value changed by the monitoring circuit of the present invention. If none of the thresholds are exceeded, the revocation appointment value of the packet remains unchanged.

At any time, due to the finite bit size of the counter, the counting derivation circuit, and the storage location, the difference between the storage value and the count value will cause an underflow due to the time of the last storage update. Or wrap-around. In the present invention, this problem is overcome by using a "scrubbing" method, where zero-length packets are introduced into the system periodically to bring the underflow packets back to the effective Within range. These zero-length packets are used to reset each packet, and thus are encoded according to a specific link index L and service level, which are the same as the encoding method of the actual packet.

In the method shown in FIG. 5, when a zero-length packet is received, its connection index L and service level are read out. These values are used to restore the critical value M and the current reservoir content B. Because in the case of underflow, the count value C will exceed the bank value B, first calculate the difference of D = BC, and set the D value to zero. Next, calculate E = D + PL (packet length) = 0. When compared with the threshold value M, it is determined that the threshold value M has not been exceeded. Then calculate the new stored value B = E + C = 0 + C = C, which effectively sets the new stored value B to the count value C. Therefore, using a zero-length packet, the contents of the bank are set to the current count value, which effectively adjusts the bank. In the case of "scrubbing" operation, there is no case where the reservoir underflow occurs, and the content B of the reservoir remains unchanged.

Therefore, according to the above description of the present invention, the counter 32 and the derivation circuit 34 can make all the processing levels and all the banks available in a very small time frame. In fact, in the time frame defined by the receipt and transfer of data packets, the storage can be updated and checked at the same time. This is a major improvement over the conventional round-robin approach to leaky reservoir treatment. Therefore, the threshold M can be set to a very low level to accurately monitor the data stream. In fact, by the above method, the threshold M can be set to a low level, so that a single data packet with sufficient information exceeding the permission limit can be marked as exceeding the contract. In practical applications, such a critical value will not be used because the burst of any data is prevented from being forwarded. In fact, due to the flexibility of the method of the present invention, the threshold M can be set to allow the burst data to be tolerated at a predetermined level. Therefore, the huge flexibility of controlling the flow on the link provides a very accurate and correct monitoring and monitoring method.

In a real network environment, a data packet may include a very large amount of data. For example, it is not common to send more than a thousand bits of data in a packet. In some common systems and communication protocols, in order to accommodate a large amount of data and reduce the complexity involved in processing a large amount of data, the amount of data is quantized so that it is processed as a group of bytes. For example, in one particular method, the data is quantized into groups of thirty-two bytes. Therefore, the packet length value of a data packet that usually exists in the form of bytes is processed to have a number of units of thirty-two bytes. Typically, this involves eliminating the five least significant bits (LSBs) of the packet length string. In conventional systems, this is accomplished through the use of a rounding function. If the five least significant bits (LSB) of the packet length string represent one from zero₁₀To 15₁₀, The new processing value representing the number of units with thirty-two bytes is rounded down. If the five least significant bits (LSB) of the packet length string represent a value from 16₁₀To 31₁₀, The new processing value representing the number of units with thirty-two bytes is rounded up.

In actual systems, some packet lengths are more commonly used than others. Therefore, the five least significant bits (LSBs) of the packet length string of the received packet are not evenly allocated to 0.₁₀To 31₁₀between. Such an uneven distribution may cause significant errors when using the pick-up function that is used conventionally. In the present invention, the value of the five least significant bits (LSB) is between 0 and a randomly generated value.₁₀To 31₁₀Compare the numbers. If the value of the five least significant bits (LSB) of the packet length string is greater than or equal to the randomly generated critical value, the number of units with thirty-two bytes will be rounded up. The value of the five least significant bits (LSB) of the string is less than the randomly generated threshold. The number of units with thirty-two bytes will be rounded down. This results in a more evenly allocated Input function that eliminates errors during processing.

FIG. 6 includes schematic functional block diagrams of specific embodiments of the data stream monitoring device and method of the present invention. As shown in FIG. 6, in block 200, the difference D between the current storage content B and the count value C is calculated, that is, D = BC. The difference D is transmitted to a comparison block 202, which determines whether the difference D is less than zero. If the difference D is less than zero, the MUX 204 is controlled by the selection line (indicated by "x) to be excluded from the comparison block 202, and the zero value is used as the output. Otherwise, the difference D will be output by the MUX 204.

The packet length value of the input packet is added to the difference D in an addition block 206 to generate a sum value, that is, E = D + PL (packet length). The difference D is also transmitted to the input of a second MUX 208. The sum generated in block 206 is applied to the second input of MUX 208. The sum value is also applied to a second comparison block 210, which determines whether the sum value is less than or equal to a preset critical value M. The output of the second comparison block 210 is a logic signal. When the sum value calculated in block 206 is less than or equal to the critical value M, it is active (high level), and when the sum value exceeds the critical value M, it is Inactive (low level). This logic value is applied to one of the first inputs of the logic AND gate block 212 and is also applied to an inverting circuit 214. The inversion value is applied to a second AND gate block 216. A first input. The second input terminal of the second AND gate block 216 is generated from a comparison block 218, which judges whether the current S value is equal to the current processing level S value, where the S value is the discarding appointment value for identifying the packet By. If so, and it is determined that the critical value M is exceeded in block 210, the logic AND gate 216 will output an active signal to the MUX The selection line of 220 causes the N value of the next level to be output as a new S value. In other words, the process continues to the next level. The N value is a hard-coded value with an index of the next level in the pipeline.

The result of the comparison performed at block 218 is also input to the logic AND gate (AND) block 212. If the current hierarchy is correct and the threshold has not been exceeded, the logic and gate (AND) block 212 applies an active signal to MUX208 The selection line of the s, so that the sum calculated in block 206, that is, E = D + PL (packet length), is output to an adder block 222. The output of adder block 22 training winter MUX 208 is added to the count value C And store it back as an updated storage content value B, that is, B = E + C.

If one level is incorrect, that is, if the comparison block 218 has an inactive output, or the critical value M is exceeded in block 210, the selection line (marked with "y") of MUX 208 will be logically AND gated (AND ) The block 212 is driven to a low level so that the difference D = BC is transmitted to the adder block 222. As a result, the count value is added back to the difference D, so that the content value B of the bank remains unchanged.

As described above, the "scrubbing" operation that can avoid the problems caused by round-robin can be implemented as a periodic dummy packet with an arbitrary and unused packet length value, and S is It is set to binary 11 and L is set to a value that is incremented from the current count value for each scrub operation. Then, if the reservoir starts to underflow, this S value will cause each pipeline level to reset its reservoir to the count value.

In a specific embodiment of the present invention, the actual processing time can be reduced by calculating an exact value before the processing proceeds to the adder block 222, where the content value B of the bank is modified in the adder block. Table 1 lists the values that can be calculated by the data path logic shown in Figure 6.

<img file="TW453073B_D0001.tif" />

It is worth noting that only the B value must be read and written in a single level, and all other values (including M) can be processed before the B-correction level in block 222 shown in Figure 6 Calculate beforehand. Therefore, calculations can be performed in a substage to reduce calculation time. In a specific embodiment, calculations can be performed in two substages. FIG. 7A is a schematic block diagram of the first level, referred to herein as "sub-level A, and FIG. 7B is a schematic block diagram of the second level, referred to herein as "sub-level B.

As shown in FIG. 7A, the adder block 250 calculates the sum of C + PL (packet length value). The inversion block 252 inverts the critical value M, and the sum of the inverted M value and the packet length value is added by the adder block 254. Comparator block 256 determines whether PL-M-1 is less than zero. The value of C is changed in adder block 258, and the value calculated by adder block 254 is added to adder block 260 to -C. The S value is set to the hierarchy number in block 262. These numerical values of the sub-level A shown in FIG. 7A are applied to the sub-level B shown in FIG. 7B.

As shown in FIG. 7B, the values B, B + PL, C, and C + PL are applied to the input terminal of the MUX 264, which outputs the selected input as the updated bank content value B. The selection lines x and y of MUX 264 are generated as described below. The sum of B and -C is calculated in adder block 266, and the sum is compared with zero in comparator circuit 268. The logic output of the comparator circuit 268 is treated as a selection line x for input to the MUX 264. Since the value calculated in the adder block 266 is less than zero, the selection line x is the active one. If the value calculated in the adder block 266 is greater than or equal to zero, then the selection line x is inactive. The value of the selection line x is also applied to the selection line of the MUX 270. If the selection line is active, a logic value with a relationship of PL-M-1 &lt;0 is transmitted to the output of the MUX 270. If the selection line is inactive, a logic value having a relationship of B-C + PL-M-1 &lt;0 will be transmitted to the output of the MUX 270. The logical value having the relationship of B-C + PL-M-1 &lt;0 is generated by adding the adder block 274 and the comparator block 276.

The output of MUX 270 is applied to a logic AND gate 272 with an S value. The output of the logic AND gate 272 is used as the selection line y of the MUX 264. The output of MUX 270 can also be changed by the inverting circuit 278. The inverted value output from the inverter circuit 278 is applied to the logic AND gate (AND) 280 along with the S value. The output of the logic AND gate (282) serves as a selection line for the MUX 282. The MUX 282 selects S or N to output an updated value that becomes the variable S.

The illustrations and descriptions of the present invention are described above in the preferred embodiments, and are only used to help understand the implementation of the present invention. They are not intended to limit the spirit of the present invention. Those skilled in the art will understand the spirit of the present invention. Without departing from the spirit of the present invention, when some modifications and equivalent changes can be made, the scope of patent protection shall depend on the scope of the attached patent application and its equivalent fields.

<p>10 Computer Network 11 Switch Node</p><p>12 Packet Source / Destination Device 13 Communication Link</p><p>20 Input module 21 Output module</p><p>twenty two Input 23 Output</p><p>twenty four Processing Circuits and Switching Structures 26 Monitoring Circuits</p><p>27 Line 28 packet processing circuit</p><p>30 Processor 31 lines</p><p>32 Counter 34 derivation circuit</p><p>35 Compare circuit 36 data packet</p><p>38 Header section 40 Information section</p><p>50 First-level processor 52 Second-level processor</p><p>54 Third-level processor 56 memory</p><p>58 Memory 60 Memory</p><p>200 Box 202 Compare Box</p><p>204 MUX 206 Add Block</p><p>208 MUX 210 comparison block</p><p>212 Logic and gate block 214 reverse circuit</p><p>216 And gate block 218 comparison block</p><p>220 Block 222 Adder Block</p><p>250 Adder Block 252 Reverse Block</p><p>254 Adder block 256 Comparator block</p><p>258 Adder Block 260 Adder Block</p><p>262 Block 264 MUX</p><p>266 Adder Block 268 Comparator Circuit</p><p>270 MUX 272 logic AND gate</p><p>274 Adder Block 276 Comparator Block</p><p>278 Reverse circuit 280 logic and gate</p><p>282 MUX</p>

The above objects, features, and advantages of the present invention are described below with reference to the accompanying drawings.

The detailed description of the preferred embodiments will be made clearer. Yu Bu

Identical reference numbers in the same drawings denote the same parts

Of course, it is drawn to scale, and its emphasis lies on the principle diagram of the present invention.

FIG. 1 includes a schematic diagram of a computer network including a plurality of switching nodes in the present invention.

Figure 2 contains a schematic block diagram of a switching node of the present invention.

FIG. 3 includes a schematic block diagram of a data flow monitoring circuit according to a specific embodiment of the present invention.

FIG. 4 includes a schematic diagram of a data packet that can be processed according to the method provided by the present invention.

FIG. 5 includes a schematic flowchart of a specific embodiment of a data flow monitoring method according to the present invention.

FIG. 6 includes schematic functional block diagrams of specific embodiments of the data stream monitoring device and method of the present invention.

FIG. 7A includes a schematic block diagram of a first embodiment of the first calculation sub-level of the present invention.

FIG. 7B includes a schematic block diagram of a specific embodiment of the second calculation sub-level of the present invention.