Method and apparatus for characterizing network traffic

[0002] All or part of the present application claims the benefit, under 35 U. S. C. §119(e), of a U. S. Provisional Application No. 60/073,175 filed on Jan. 30, 1998 and entitled NETWORK TRAFFIC CHARACTERIZATION USING TOKEN BUCKET MODEL.

[0003] 1. Field of the Invention

[0004] The present invention relates to Internet Quality of Service (QoS) technology. More particularly, the present invention pertains to a method and apparatus for characterizing required network resources during transmission of network traffic.

[0005] 2. Related Art

[0006] Real-time media such as video and audio are often delivered over a network such as the Internet to enhance the contents of a wide variety of data. Appropriate network resource reservation and management is crucial both for the timely delivery of the traffic corresponding to these real-time media and to ensure efficient use of limited network resources. A number of methods have been proposed by organizations, such as the Internet Engineering Task Force (IETF), to provide a QoS guarantee for real-time traffic. The most prominent method for providing QoS is Resource Reservation Protocol (RSVP) (Braden, R., Zhang, L., Berson, S., Herzog, S., and Jamin, S., “RSVP—Version 1 Functional Specification”, September 1997). RSVP employs a parameter known as the traffic specification (TSpec) to reserve network resources for transmitting the real-time traffic. TSpec is based on the token bucket model and is a standard parameter for characterizing a pattern. Specifically, TSpec is based on several values including the value r which is related to the average bandwidth (e. g., bytes per second) of the traffic and the value b which is an indication of how “bursty” the traffic is (e. g., fluctuations in bandwidth above and below the value for r).

[0007] RSVP requires the end-hosts to submit a request for the reservation of network resources. The network responds to the host by confirming whether or not the requested network resources have been successfully reserved. To accurately request the network resources required to deliver the real-time traffic pattern, the host must first characterize the traffic. For audio/video application developers and Internet users, pre-specifying traffic characteristics for each codec (coder/decoder) is a difficult task. The characteristics for well known audio/video codecs, such as H. 261 (International Telecommunication Union—Telecommunications Standardization Sector (ITU-T), March, 1993), and H. 263 (ITU-T, Dec. 5, 1995) can be roughly estimated. However, network traffic is highly dependent on such variables as the frame rate, the resolution, and the scene complexity. Additionally, silence suppression or interframe coding techniques, may result in varying bit rates.

[0008] In some systems, such as those with WinSock2 (Windows® Socket Version 2; an add on feature of Windows® 95 Operating System and installed in Windows® NT Operating System, Version 4 and later and Windows® 98 Operating System (Microsoft Corporation, Redmond, Wash.)), TSpec templates for a few well known codecs are accessible. This situation creates many disadvantages which result in an additional burden on the user and an inefficient use of network resources. First, using one template per codec regardless of the frame rate and scene complexity leads to inaccuracies. Second, the user application is required to take steps to determine and transmit appropriate TSpec values, while the TSpec information is often not easily accessible to the user application. Finally, when the user application is unable to access TSpec information, a trial and error method is often employed.

[0009] In a manual describing a software program using a so-called token bucket model written by C. Partridge and M. Garrett (1994), a method is described for computing token bucket parameters. For a given r, the system uses a linear pass through the pattern data to determine a large enough b value. However, the algorithm employed ignores the fact that credit growth in the token bucket model may be cut off and does not always give the optimal value for b.

[0010] Accordingly, there is a need for a method and apparatus which will automatically and accurately characterize a given traffic pattern while delivering the traffic over a network.

[0011] According to an embodiment of the present invention, a method for characterizing network traffic is provided. First, a traffic pattern for said network traffic is recorded at a source device. Then, at least one value characterizing the network traffic is generated.

[0012] FIG. 1 is a block diagram of an apparatus for determining traffic characteristics according to an embodiment of the present invention.

[0013] FIG. 2 shows the apparatus of FIG. 1 included within a computer for determining token bucket based traffic characteristics according to an embodiment of the present invention.

[0014] FIG. 3 shows a no-delay TB (token bucket) curve for an example of a traffic pattern.

[0015] FIG. 4 shows queuing TB curves for the traffic pattern of FIG. 3.

[0016] A simplified block diagram of an apparatus according to an embodiment of the present invention is shown in FIG. 1. In this embodiment, functional blocks are shown which can be implemented as a set of instructions residing in a storage medium (e. g., using the C/C++ programming language) executed by a processor or as individual hardware components. A service provider (e. g., an application controlling a source device such as a coder/decoder or codec) generates information to be sent out onto a network 8 (not shown in FIG. 1) to be received by one or more devices coupled to network 8. A collector 1 may be provided that receives and records a network traffic pattern output of the source device (not shown in FIG. 1) to assist in characterizing the traffic of the information being sent to the network. In this embodiment, collector 1 collects packet length and corresponding packet arrival time information. An engine 2 is provided coupled to an output of collector 1. In this embodiment, engine 2 generates at least one value that characterizes the network traffic being output by the source device. A reporting mechanism 3 may be provided to receive the value characterizing the network traffic pattern and report the value to the network (e. g., to set up a reserved bandwidth for the transmission of data from the source device) via an RSVP service provider 4.

[0017] FIG. 2 shows an example of the apparatus of FIG. 1 included within a host device 5 (e. g. a computer including a Pentium® II Processor (Intel Corporation, Santa Clara, Calif.)). Host device 5 includes an application 11 controlling a number of service providers such as a source device (e. g. a H. 263 codec signal generator) and an RSVP service provider 4. The service providers control the transmission of packets via a network layer to line 7 and network 8. In this embodiment, network 8 is the Internet. The service providers also provide network traffic pattern data to an input of collector 1. As used herein, the term “coupled” refers to both direct and indirect coupling of components. In this embodiment, collector 1 records the packet length and time (e. g., the time the packet is sent from the application to the service provider (source device)) for one or more packets and transmits these values to engine 2. In this example using the RSVP token bucket model, engine 2 uses the packet length and time values from the collector 1 to compute values to characterize the network traffic being generated by the traffic source such as the optimal values for r and b described above as well as values for the peak rate (p) and the maximum packet size (M). In this embodiment, RSVP reporting engine 3 receives these four values from engine 2 as well as the value for the minimal policing size (m) which is configured by the user. In this token bucket example, reporting mechanism 3 can generate the TSpec values based on the values it receives from engine 2 and the user. Reporting mechanism 3 can report the TSpec values to RSVP service provider 4 which transmits the TSpec values to the network in a known manner as defined in the RSVP specification.

[0018] The method and apparatus of this embodiment of the present invention will now be further explained in the context of RSVP and the token bucket model; however, the present invention is intended for use with other network traffic pattern characterization models. A token bucket is a non-negative credit counter which accumulates credits at a constant rate (r) until the credit counter reaches an upper bound (b). The traffic includes a series of packets. The packets can be of varying length and are typically separated by varying time intervals. A packet of data will be immediately transmitted upon arrival at the source device if the packet size in bytes is less than or equal to the number of credits present in the token bucket. In this case, the packet size is subtracted from the credit count. If the byte size of the arriving packet exceeds the number of the credits present in the token bucket, the packet will be either dropped or queued until more credits accumulate in the bucket. When the flow is idle or running at a low rate, the token count will continue to replenish credits at the rate r until the credit count reaches the upper bound b and in that case the credit growth will be suspended until the arrival of the next packet. The token bucket model characterizes a traffic pattern in terms of the parameters r and b. Once a traffic pattern is characterized by the parameters r and b, reservation of an appropriate amount of network resources can be requested. While there are a number of r and b values which ensure that all arriving packets in the traffic will be transmitted without delay upon their arrival, an optimal (r, b) pair will minimize certain prescribed cost functions such as (r+b).

[0019] The token bucket model can be extended by adding a queue. The queue is used to store the incoming stream of data packets at the source device until enough credits accumulate in the token bucket. With a queue, the traffic pattern can be suitably changed so that the token bucket model for the post-queuing traffic pattern is more stationary than the strict no-delay model described above. A token bucket with a queue is able to accommodate a wider variety of traffic patterns. Queuing also avoids dramatically increasing the size and rate of the token bucket when the traffic pattern flow becomes bursty. When the parameters of a given token bucket are not large enough to satisfy the no-delay requirement for a given traffic pattern, a challenge exists in determining the minimal size of the queue (q) which will ensure that the traffic flow after queuing can be modeled by that token bucket. The present invention can be adapted to characterize a given traffic pattern in terms of optimal token bucket parameters (r and b) both with and without the addition of a queue.

[0020] According to an embodiment of the present invention, collector 1 records the network traffic pattern generated by the traffic source. The traffic includes a series of packets and the traffic pattern can be described by the notation PΔ{(p_i, t_i)|1≦i≦n}, where p_irepresents the length of the i-th packet and t_irepresents the arrival time of the i-th packet at the service provider. Collector 1 transmits the traffic pattern (P) to engine 2. Engine 2 employs an algorithm to characterize the traffic pattern (P) by determining the corresponding optimal token bucket rate (r) and the corresponding optimal token bucket size (b).

[0021] In one example of an algorithm, the first step entails determining the range of the traffic pattern's token bucket rate using the following relationships: $r_{\min }=\underset{1\le k\le n}{\max }\frac{\sum _{i=1}^k{p}_i-c_0}{t_k-t_0}$ $r_{\max }=\underset{2\le k\le n}{\max }\left\{\frac{p_1-c_0}{t_1-t_0},\frac{p_k}{t_k-t_{k-1}}\right\}$

[0022] where r_minis defined as the lower bound for r, k is an index, c₀is the initial token count existing in the token bucket at t₀, and r_maxis defined as the upper bound for r. If the token bucket is initially full, r_maxis set equal to the peak rate for the traffic pattern and the relationships for determining r_minand r_maxare as follows: $r_{\min }=\frac{\sum _{k=1}^n{p}_k}{t_n-t_0}$ $r_{\max }=p=\underset{1\le k\le n}{\max }\frac{p_k}{t_k-t_{k-1}}$

[0023] Once the range of the token bucket rate for the traffic pattern is determined, the algorithm uses the following relationships to determine the range of the token bucket size: $b_{\min }=\underset{1\le k\le n}{\max }\left(p_k,c_0\right)$ $b_{\max }\left(r\right)=\underset{1\le i\le n}{\max }{c}_k\left(r\right)$

[0024] where b_minis a lower bound for b, b_maxis an upper bound for b, and c_k(r) is given by the following expression: $c_k\left(r\right)=c_0+r\left(t_k-t_0\right)-\sum _{i=1}^{k-1}{p}_i$

[0025] Within the range of the four values determined above, there are a number of token bucket parameter pairs (r and b) which characterize the traffic pattern and satisfy the no-delay requirement. The relationship between these (r, b) pairs, within the range of the above four determined values, can be illustrated graphically by plotting a no-delay TB curve. A best example of a mathematical expression describing the no-delay TB curve is: $b_{\mathrm{opt}}\left(r\right)=\underset{1\le u\le v\le n}{\max }\left(\sum _{i=u}^v{p}_i-r\left(t_v-t_u\right)\right)$

[0026] A best example of an algorithm for determining the values of the above mathematical expression is:

[0027] d₁=b₁=p₁

[0028] d_k=max(d_k−1+(p_k−rΔ_k), p_k), k>1

[0029] b_k=max(b_k−1,d_k),k>1

[0030] where d_kis an auxiliary variable and b_ngives the value for b_opt(r). This algorithm is useful in determining the no-delay TB curve when there is no queue. FIG. 3 illustrates an example of a no-delay TB curve; the token bucket size (in bytes) is along the vertical axis and the token bucket rate (in bytes/second) is along the horizontal axis. The curve in FIG. 3 was determined using the above algorithm for traffic which represents a clip from the movie “True Lies. ” This clip contains 1,664 packets and 1,989,862 bytes. The average rate is r_min=20,539 bytes/second and the peak rate is r_max=1,652,500 bytes/second.

[0031] The optimal token bucket rate and optimal token bucket size are determined from the no-delay TB curve. An optimal token bucket rate and token bucket size would be to minimize r+b. While r+b is a typical cost function to be minimized, different cost functions may be used in other situations. Experimentation has determined that one of the best methods for determining the optimal token bucket rate (r_opt) entails the following steps: 1) determine the difference between r_minand r_max, 2) calculate 5% of the determined difference between r_minand r_max, 3) add this 5% value to r_minto calculate r_opt. Once r_optis determined, the corresponding optimum token bucket size, b_optcan be determined from the no-delay TB curve.

[0032] A second example of an algorithm for determining the no-delay TB curve uses a binary search to determine the minimal b in its range such that the number of credits in the token bucket is greater than the byte size of each packet in the traffic pattern (c_k(r,b)≧p_kfor all k). This algorithm does not use the explicit solution for the optimal token bucket size and is illustrated below in psuedo code:

[0033] Input parameters:

[0034] Traffic pattern: P={(p_i, t_i)|i=1,2, . . . , n}

[0035] where p_iand t_iare the i-th packet's length and arrival time, respectively.

[0036] Queue size: q

[0037] Output parameters:

[0038] Token bucket rate: r

[0039] Token bucket size: b

[0040] Internal Variables

[0041] Number of bytes backlogged immediately prior to t_k: g(k)

[0042] Maximal number of bytes backlogged: g

[0043] Number of tokens in the bucket immediately prior to t_k: c(k)

[0044] Number of packets sent out so far until t_k: I(K)

[0045] Algorithm:

[0046] 1. Compute c(k) and I(k) inductively where

[0047] I(k) is set to the largest index k′, k′<k, such that c(k−1)+r(t_k−t_k−1)−(p_I(k−1)+1+ . . . +p_k′)≧0;

[0048] c(K) is set to min(c(k−1)+r(t_k−t_k−1)−(p_I(k−1)+1+ . . . +p_I(k)), b); with

[0049] c(1)=b;

[0050] I(1)=0;

[0051] 2. Compute g(k) based on c(k) and I(k)

[0052] g(k)=0, If I(K)=k−1 and c(k)≧p_k, p_I(k)+1+ . . . +p_k,, otherwise;

[0053] g=max g(k);

[0054] 3. Compute the following:

[0055] MeanRate=(p₁+p₂+ . . . p_n)/t_n;

[0056] PeakRate=max(p_k/(t_k−t_k−1));

[0057] bLower=max p_k;

[0058] bUpper=p₁+p₂+ . . . p_n;

[0059] 4. For any r between MeanRate and PeakRate, do a binary search for the minimal b in the range of bLower and bUpper such that g is less than or equal to q.

[0060] This second algorithm can be adapted to determine the TB curve when a queue is available.

[0061] FIG. 4 illustrates a series of 10 queuing TB curves with various queue sizes. The curves were determined by applying the second algorithm to the previously described “True Lies” clip. The queuing TB curve parameterized by q=0 coincides with the no-delay TB curve in FIG. 3. As illustrated in FIG. 4, the greater the capacity of the queue, the lower the queuing TB curve on the (r, b) plane. The lower queuing TB curves require the reservation of fewer network resources. Thus, systems with more resources invested in memory capacity available for a queue reserve less resources on the network.

[0062] As described above, engine 2 also determines the peak rate (p), and the maximum packet size (M) along with an optimal token bucket rate (r) and token bucket size (b). These four parameters, when combined with the user defined minimal policing size (m) as known in the art are defined as the TSpec value for a traffic pattern. TSpec characterizes the traffic and is used to request the reservation of the network resources which will be required for the timely and efficient transmission of the traffic over the network. The TSpec values can be generated by reporting mechanism 3 with the r_opt, b_opt, M, and p values from engine 2 and the m value from the user. Reporting mechanism 3 transmits a trigger signal to RSVP service provider 4, which then transmits the TSpec parameters, known in the art as the PATH message, over the network to the intended recipient(s) of the network traffic. A reserve message (RSVE), generated by each intended recipient, is transmitted back to the host. As known in the art, the RSVE message from the network indicates whether or not the requested network resources have been reserved.

[0063] Engine 2 can periodically determine new optimal token bucket rate and optimal token bucket size values which can be selectively reported to the network. These new values can be compared to the previous values, so that if the new and the previous values are within a predetermined range of each other, the new values are not transmitted to the network. If the new values are outside the predetermined range, the new optimal values (and thus new TSpec) will be transmitted to the network to request resource reservation.

[0064] The present invention may characterize network traffic dynamically and in a manner transparent to the user application. In one embodiment, for the first few seconds of transmission from the host, the data is transmitted on a best efforts basis. Best efforts means the traffic employs whatever network resources are available between the host and the recipient without reservation. Once the present invention has sampled the outgoing traffic pattern and characterized the network traffic in the manner described above, appropriate network resources are reserved for transmitting further traffic to the network. Thus, the risk of over-subscribing or failing to reserve enough network resources to provide the necessary QoS can be eliminated.

[0065] Although several embodiments are specifically illustrated and described herein, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.