Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-06-02
2004-08-31
Lee, Andy (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S252000
Reexamination Certificate
active
06785240
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods of traffic measurement in packetized communication networks. More particularly, the invention relates to methods for inferring the amount of data passing between particular origin-destination node pairs, from undifferentiated measurements made at network routers.
ART BACKGROUND
FIG. 1A
shows a simple, illustrative network for packetized communication. One example of such a network is a local area network (LAN) of computers. In the network illustrated, router
10
is directly connected to edge nodes
15
.
1
-
15
.
4
via respective links
20
.
1
-
20
.
4
, and each of the edge nodes is connected to a respective group of hosts or users
25
.
1
-
25
.
4
. The router directs traffic in the network by forwarding packets between nodes according to a routing scheme. Edge nodes, i.e., nodes directly connected to the router, are origin or destination nodes for such traffic. Each node pair between which traffic is being forwarded is denominated an origin-destination (OD) pair. It should be noted that although a single router is shown in the figure, the direction of traffic may alternatively be carried out by multiple routers, by one or more switches, by a combination of routers and switches, or by yet other devices that forward packet traffic.
The set of traffic counts, typically expressed as total bytes of data or total number of packets or connections, between all of the OD pairs is referred to as the traffic matrix. Knowledge of the traffic matrix is valuable to network operators for, e.g., revising network designs and routing schemes to avoid traffic bottlenecks, and for differential pricing of service.
Router
10
will typically have a respective interface
30
.
1
-
30
.
4
associated with each of links
20
.
1
-
20
.
4
. As shown in the figure, each of links
20
.
1
-
20
.
4
carries traffic bidirectionally, and each interface should be regarded as functionally subdivided into respective portions for handling incoming and outgoing traffic.
Generally, the router is able to measure the counts of incoming and outgoing traffic at each interface. We refer to these traffic measurements as the link counts. For example, link counts are readily obtainable via the Simple Network Management Protocol (SNMP), which is implemented in almost all commercial routers. That is, through the SNMP protocol, counts of incoming bytes received from each link interface and counts of outgoing bytes sent on each link interface can be obtained by polling at, e.g., regular five-minute intervals
Unfortunately, the incoming link counts are typically aggregated over all possible destination nodes, and the outgoing link counts are likewise aggregated over all possible origination nodes. Consequently, it is generally impossible to derive the traffic matrix from the link counts with mathematical certainty. The difficulty is further compounded in networks having more than one router or switch.
The best that can be done is to make a probabilistic inference concerning the traffic matrix from the observed link counts. Such an inference relies upon two elements: (i) the recognition that a set of linear equations relates the observed link counts to the unknown OD counts, and (ii) the adoption of a statistical model to describe how the values of the link counts are probabilistically distributed. Given these two elements, it is possible, through the application of conditional probabilities, to estimate the set of OD counts that are most likely in view of the link counts that have been measured.
Simple implementations of such an approach have been described, for example, in Y. Vardi, “Network tomography: Estimating source-destination traffic intensities from link data,”
J. Amer. Statistical Assoc
. (1996), C. Tebaldi et al., “Bayesian inference on network traffic using link count data,”
J. Amer. Statistical Assoc
. (1998), and R. J. Vanderbei et al., “An EM approach to OD matrix estimation,”
Technical Report SOR
94-04, Princeton University (1994). However, there is a need for further improvements in the accuracy of the resulting estimates of the traffic matrix, particularly when the traffic data are evolving in time, or when the assumption of a Poisson relation between the means and variances of the statisitical model, adopted in earlier work, is not realistic.
SUMMARY OF THE INVENTION
We have developed an improved method for estimating the OD counts from the link counts. Our method is the first to include an explicit treatment of data as a time series having a past and a future. Our method takes explicit account of past data when forming a current estimate of the OD counts. As a consequence, behavior that evolves in time is described by our method with greater accuracy. A further advantage of our method is that the estimated OD counts evolve with improved smoothness.
According to our method, a statistical model is assumed for the distribution of the OD counts. In an exemplary embodiment, the model is multivariate, iid, and normal. A normal distribution is parametrized by a mean value for each of the variables and a variance matrix. However, in our exemplary embodiment, the variance is assumed to be a function of the means, so the only independent parameters are the means and a scale factor that helps to define the variance.
An exact enumeration of the OD counts cannot be derived directly from the link counts. However, given the measured link counts and a statistical model, it is possible to construct a likelihood that describes how likely the observed counts are, depending on given values of the independent parameters of the statistical model.
Those skilled in the art of Bayesian analysis, and more particularly in applications of the well-known EM algorithm, will appreciate that a function known as the Q function expresses the expected value of such a likelihood function. The value that the Q function takes is conditioned on the observed set of link counts, and it is also conditioned on a current estimate of the independent parameters of the statistical model. In application of the EM algorithm, the estimate of the independent parameters is refined through a series of iterations in which the Q function corresponding to a current estimate of the independent parameters is maximized to yield an updated parameter estimate.
Each of the iterations carried out in application of the EM algorithm is typically applied to the same set of data as the previous iterations. As the parameter estimate continues to improve through these iterations, the value of the likelihood function increases toward a maximum.
In contrast to methods of the prior art, our method permits further refinement of the parameter estimates. This is achieved, as above, by performing a series of iterations that drive a function toward a maximum value. However, the function is now a penalized likelihood function that depends not only on a current time window of observed link counts, but also on a prior distribution of the parameters themselves, based on link counts observed in previous time windows.
According to one embodiment of the invention, an initial estimate of the model parameters is obtained from the EM algorithm using only the sequence of link counts measured in a given time window. Then, in a subsequent stage (which may also apply the EM algorithm, or a different algorithm), a series of iterations is carried out to drive a penalized likelihood function toward a maximum value. This penalized likelihood function depends on both of: the link counts measured in the given time window, and a prior distribution of the independent parameters of the statistical model, as obtained from one or more earlier time windows.
The OD counts are then estimated as a conditional expectation depending on the measured link counts, the statistical model using the refined parameter evaluation, and the routing scheme of the network.
REFERENCES:
patent: 6061331 (2000-05-01), Conway et al.
patent: 6173325 (2001-01-01), Kukreja
patent: 6178448 (2001-01-01), Gray et al.
patent: 6229815 (2001-05-01), Huang et al.
patent: 6347
Cao Jin
Davis R. Drew
Wiel Scott Alan Vander
Yu Bin
Finston Martin I.
Lee Andy
Lucent Technologies - Inc.
LandOfFree
Method for estimating the traffic matrix of a communication... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for estimating the traffic matrix of a communication..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for estimating the traffic matrix of a communication... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335576