Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1999-02-05
2002-04-30
Lim, Krisna (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S224000, C709S232000, C709S223000, C370S230000, C370S232000, C370S233000, C370S235000
Reexamination Certificate
active
06381649
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of digital communications and more particularly to systems and methods for switching packets of data in a switching node used in a digital data network and for monitoring data flow at the switching node.
BACKGROUND OF THE INVENTION
Digital networks have been developed to facilitate the transfer of information including data and programs among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modem networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnection pattern can allow for a number of paths to be available through the network from each computer system or other device to another computer system or other device.
Information transferred from a source device to a destination device is generally transferred in the form of fixed or variable-length data packets, each of which is in general received by a switching node over a communication link and transmitted over another communication link to facilitate transfer of the packet to the destination device or to another switching node along a path to the destination device. Each packet typically includes address information including a source address that identifies the device that generated the packet and a destination address that identifies the particular device or devices which are to receive the packet.
Typically, a switching node includes one or more input ports, each of which is connected to a communication link on the network to receive data packets, and one or more output ports, each of which is also connected to a communication link on the network to transmit packets. Each node typically also includes a switching fabric that couples data packets from the input ports to the output ports for transmission.
Typically, a network service provider maintains and operates one or more switching nodes which can transfer data packets from input communication links across the switching fabric to output communication links. These providers charge fees to customers who use the links to transfer data across the nodes on the network. Typically, the fees are related to the maximum data rate at which a customer can expect data to be forwarded across the node.
Each link at a node is typically assigned at least one “class of service” which is related to a maximum allowable data rate provided to a customer that uses the link, which in turn is based upon the fee paid by the customer to the provider. In many cases, each link can be assigned multiple classes of service associated with a single user or multiple users.
It is in the interest of service providers to monitor or “police” data traffic on each link to determine whether customers' use of their allocated links is within contractual limits. Where it is determined that the use of the link, i.e., the data rate, exceeds the contractual limit, data packets can be identified and marked as such, i.e., as being “out of contract.” In many cases, it is important to carefully monitor data traffic on each link at each class of service. It is also often desirable to mark data packets with respect to the degree to which a particular packet may be out of contract. For example, if a particular packet is only slightly out of contract, it may be desirable to mark the packet as such. Also, in cases of extreme overuse of the link, it may also be desirable that data packets be so marked.
In some systems, the degree to which a packet exceeds the link contract data rate is used to set a priority for discarding the packet. Packets that only slightly exceed the contract rate are assigned relatively low “discard eligibility” values, while packets that greatly exceed the maximum rate are assigned high discard eligibility values. In the event that it becomes necessary to drop a particular packet, those with higher discard eligibility values are more likely to be dropped than those with lower discard eligibility values.
Several approaches have been employed to monitor data flow rates on multiple links having multiple classes of service. One common approach is referred to as a “leaky bucket” approach. Under this approach, a memory or register storage location, commonly referred to as a “bucket,” is allocated to each link and class of service. Each storage location or bucket maintains a count of a number of data units received for its assigned link and class of service. A data unit can be a byte of data, or a group of data bytes for example, where each data packet transfers multiple bytes of data. For each bucket, a predetermined threshold number of data units, related to the maximum allowable data rate for the associated link and class of service, is generated and stored. As a data packet is received, the number of data units (bytes) is added to the present value or count in the bucket, and the updated value is compared to the threshold. If the updated value exceeds the threshold, then the incoming data packet is marked as exceeding the threshold. Because it is data rates that are being policed rather than the total amount of data received, the value or count stored in each bucket is periodically decremented a predetermined number of data units related to the maximum allowable data rate and the period at which the decrementing takes place. This decrementing is commonly referred to as “leaking” the bucket. By leaking the bucket at the correct predetermined rate, it is ensured that when the number of data units in the bucket exceeds the predetermined threshold, the maximum allowable data rate has been exceeded.
In order to identify short bursts of large amounts of data that exceed the maximum allowable data rate, it is desirable to leak each bucket and perform a threshold comparison as often as possible. Such short bursts can be missed where buckets are not leaked and checked often enough. In relatively small systems, having a relatively small number of buckets, the system can cycle through all of the buckets relatively quickly such that short bursts of large amounts of data can be identified as being out of contract. In such systems, the buckets take the form of memory locations and the leaking and checking is performed in the system software. However, as systems become larger with larger numbers of links and classes of service and, consequently, larger numbers of buckets, the leaking and checking periods for each bucket become longer. Thus, the buckets are not maintained as frequently, and the likelihood of not identifying short large data bursts increases. Thus, the data rate policing in such systems becomes less accurate.
SUMMARY OF THE INVENTION
The present invention is directed to an apparatus and method for monitoring or policing data traffic at a network node which facilitates data transfer on at least one link having at least one class of service. The data are transferred in data packets, and each data packet includes at least one unit of data. For each of at least one selected link and class of service, an updatable value is stored in a storing device. A counter value in a counter is incremented at a rate determined by a maximum allowable data rate associated with the selected link and class of service. A data packet is received and a number of units of data in the data packet is counted. An adjusted updatable value is computed by adjusting the updatable value according to the counter value at the time the data packet was received and the number of units of data in the data packet. The adjusted updatable value is compared to a predetermined threshold associated with the selected link and class of service. The data packet is marked with respect to the allowable data rate based on whether the adjusted updatable value exceeds the predetermined threshold.
In one embodiment, the adjusted updatable value is computed by computing a difference between the updatable value and the counter value when the data pa
Lim Krisna
Mills & Onello LLP
Pluris, Inc.
LandOfFree
Data flow monitoring at a network node using periodically... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data flow monitoring at a network node using periodically..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data flow monitoring at a network node using periodically... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859014