Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2007-12-25
2007-12-25
Pham, Chi (Department: 2616)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C709S225000, C726S022000
Reexamination Certificate
active
10261299
ABSTRACT:
The present invention is a methodology to prioritize packets based on the conditional probability that given the values of attributes carried by packet, the packet is a legitimate one. We will call this the conditional legitimate probability of a packet from here onward. The conditional probability of each packet is evaluated based on Bayesian estimation technique. This is accomplished by comparing the attributes carried by an incoming packet against the “nominal” distribution of attributes of legitimate packet stream. Since an exact prioritization of packets based on their conditional legitimate probability would require offline, multiple-pass operations, e.g. sorting, we take the following alternative approach to realize an online, one-pass selectively dropping scheme. In particular, we maintain the cumulative distribution function (CDF) of the conditional legitimate probability of all incoming packets and apply a threshold-based selective dropping mechanism according to the conditional probability value computed for each incoming packet. To speed-up the computation of the conditional legitimate probability for each incoming packet, we may, as an alternative, use the logarithmic version of the equation to implement the Bayesian estimation process. Other features of the invention include: providing means to guarantee minimum throughput of particular (pre-configured) type(s) of packets; providing a. Filtering Mechanism to suppress the noise during estimation/maintenance of nominal attributes distribution; applying state-of-the-art efficient algorithm/data-structures for quantile and histogram building/updates; using the proven, industrial-strength load-shedding algorithms as a submodule in the overload control algorithm; and being amenable to practical implementation to support online, one-pass processing on high-speed communication links.
REFERENCES:
patent: 6301668 (2001-10-01), Gleichauf et al.
patent: 6484203 (2002-11-01), Porras et al.
patent: 6499107 (2002-12-01), Gleichauf et al.
patent: 2005/0111307 (2005-05-01), Saaski et al.
J. Kaufmann, “A New Traffic Overload Control for the Autoplex Series II Cell—Work Project No. 170211-2200”, Technical Memorandum, Bell Labs. Lucent Technologies, Feb. 25, 1999.
G. S. Manku et al., “Approximate Medians and Other Qauntiles in One Pass And With Limited Memory”,Proc. of SIGMOD'98, Seattle, WA., U.S.A., 1998.
G. S. Manku et al., “Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of large Datasets”,Proc. of SIGMOD'99, Philadelphia, PA., U.S.A. , 1999.
G. S. Manku, “Approximate Frequency Counts Over Data Streams”,Proc. of the 28thVLDB Conference, Hong Kong, China, Aug. 2002.
M. Greenwald et al., “Space-Efficient Online Computation of Quantile Summaries”,Proc. of the 2001 ACM SIGMOD Intl. Conference on Management of Data, Santa Barbara, CA., May 2001, pp. 58-66.
R. M. Karp et al., “A Simple Algorithm for Finding Frequent Elements in Streams and Bags”, manuscript available from: http://www.cs.berkeley.edu/˜christos/icebergs.ps.
Jaeyeon Jung et al., “Flash Crowds and Denial of Service Attacks: Characterization and Implications for CDNs and Web Sites”,Proc. of WWW2002, May 2002, Honolulu Hawaii, U.S.A.
P. Domingos et al., “Mining High-Speed Data Streams”,Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining, 2000, Boston, MA, ACM Press, pp. 71-80.
G. Hulten et al., “Mining Time-Changing Data Streams”,Proceedings of the Seventh International Conference on Knowledge Discovery and Data Mining, San Francisco, CA: 2001: ACM Press, pp. 97-106.
Tingfang Ji, “Adaptive Nonlinear Suppression of Non-Gaussian Interface” preprint, 2002.
M. Datar et al., “Maintaining Stream Statistics Over Sliding Windows”,Proc. of Thirteenth Annual ACM-SIAM Symposium On Discrete Algorithms(SODA'02) 2002.
B. Babcock et al., “Sliding Window Computations Over Data Streams”, Technical Report, Department of Computer Science, Standord University, Apr. 2002.
Fei Chen et al., “Incremental Quantile Estimation For Massive Tracking”,Proc. of the Sixth International Conference in Knowledge Discovery and Data Mining, 2000.
Anna C. Gilbert et al., “How To Summarize The Universe: Dynamic Maintainance of Quantiles”,Proc. of the 28thVLDB Conference, Hong Kong, China, Aug. 2002.
Lau Wing Cheong
Zhang Yinglu
Hodulik Matthew J.
Hyun Soon D.
Lucent Technologies - Inc.
Pham Chi
LandOfFree
Apparatus and method for an overload control procedure... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for an overload control procedure..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for an overload control procedure... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3881369