| Fast simulated annealing for traffic matrix estimation -> Monitor Keywords |
|
|
 
Fast simulated annealing for traffic matrix estimationRelated Patent Categories: Multiplex Communications, Network Configuration Determination, Using A Particular Learning Algorithm Or TechniqueFast simulated annealing for traffic matrix estimation description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20070140148, Fast simulated annealing for traffic matrix estimation. Brief Patent Description - Full Patent Description - Patent Application Claims
RELATED APPLICATION [0001] This application is related to U.S. Ser. No. 10/962,488 filed Oct. 13, 2004. The contents of U.S. Ser. No. 10/962,488 are incorporated herein by reference. FIELD OF THE INVENTION [0002] The present invention relates to systems and methods for estimating the performance of communication networks and more particularly to performance estimations using a fast, simulated annealing for traffic matrix estimation (FastSATME) technique. BACKGROUND OF THE INVENTION [0003] Spurred by technological advances, the telecommunications industry has experienced tremendous growth over the last decade. The advances in processing power of desktop computers and the decrease in application response times have fostered corresponding improvements in network infrastructure. The new bandwidth consuming applications support the network traffic growth and the rapid changes in equipment utilization confront the network providers with the issue of whether the network has adequate capacity to support current and future traffic requirements. [0004] In any traffic and/or network engineering task, more knowledge about the network can only be beneficial. Specific applications require, for example, knowledge of how much traffic goes from a site A to a site B, how much traffic does a particular customer send from site A to B, where is the hot spot in the network, or how much capacity needs to be added and where. Information about network behaviour under specific conditions is also useful. For example, a network provider may optimize network performance based on the knowledge of how much traffic has to be moved if a link fails, what happens if traffic between two points is moved from one link to another, whether most traffic originating in a sub-network (autonomous system, country, or company) is staying in that sub-network or not, etc. This knowledge is used generally for routing path calculations, load balancing, etc. [0005] Network engineering tools were designed for handling the issues created by the increases in traffic demands or changes in the existing demands and determining the necessary expansion or modification to the network to support the projected traffic. These tools generally aid in revising network designs and routing schemes to avoid traffic bottlenecks, and enable differential pricing of services, etc. However, all these tools require knowledge of traffic statistics, and more specifically of the real time, source-destination traffic demands. [0006] A way of keeping statistics for a packet based network is to look at each packet and to record its source and destination addresses. However, this method requires huge tables for recording this information. Furthermore, if what is desired is a source to destination traffic matrix for a subset of the network, then the ingress into the subset and the egress from the subset will not be available without looking at the source and destination addresses and then determining the path the packet would take as indicated by the routing information. This would not be feasible for large networks and large numbers of packets. [0007] It is also known to organize the traffic statistics into a"traffic matrix". A traffic matrix is typically expressed as the total bytes of data or the total number of packets or connections between all of the source-destination pairs of nodes. While current routers are able to measure the counts for the incoming and outgoing traffic at each interface (incoming and outgoing links), it is generally impossible to derive the traffic matrix from the link counts with mathematical certainty. The best that can be done is to make a probabilistic inference concerning the traffic matrix from the observed link traffic. [0008] AT&T has proposed a scheme which derives traffic matrices from the available measurements of link loads, by combining two known models, namely the gravity model with the tomographic model. The gravity model assumes that the traffic between the sites is proportional to the traffic at each site on a per peer basis (as opposed to a per router basis) for the outbound traffic, and that there is no systematic difference between the traffic in different locations. The tomographic model applies link constraints based on models. The combination of these models (tomo-gravity) reduces the problem size for large networks and provides more accurate results that the gravity and tomographic models separately. [0009] However, the tomo-gravity method does not allow for easy specification of arbitrary constraints, such as knowing that if one link has twice the speed of another, it probably has roughly twice the traffic. Also, this method is based on assuming that the traffic follows the `gravity` model, which can not be assumed in practice. [0010] The prior art techniques described above, such as monitoring all packets as well as the gravity and tomographic approaches including the tomo-gravity approach, are not satisfactory for large traffic volumes and rely on unrealistic assumptions, respectively. On the other hand, it is essential to provide tools and techniques for traffic engineering in modern communication networks, particularly for estimating traffic patterns (characteristics), e.g. traffic volumes, hotspots, effects of failures, etc. [0011] In the aforementioned U.S. application Ser. No. 10/962,488a simulated annealing traffic matrix estimation (SATME) technique is described and illustrated. The SATME method and system estimates source-to-destination traffic matrices using a simulated annealing algorithm, the traffic matrix estimation being represented as a probability distribution over the set of all possible matrices that satisfy a set of given constraints. The constraints explicitly encode information that the user knows about the network traffic as components of an objective function (a fitness function), that is then minimized using simulated annealing. With the method according to U.S. Ser. No. 10/962,488, arbitrary constraints of any form can be included, and the case where there are no feasible solutions can be diagnosed by the objective function not converging to zero. [0012] Although the SATME technique represents an improvement over the aforementioned prior art its main disadvantage is the speed of the algorithm. It is potentially too slow for real-time traffic engineering, taking on the order of hours to perform a traffic matrix estimation for a network of 100 nodes, for example. SUMMARY OF THE INVENTION [0013] It is an object of the invention to provide tools and techniques for traffic engineering that alleviate totally or in part the drawbacks of the prior art tools and techniques. [0014] In particular, it is an object of the invention to estimate source-to-destination traffic matrices using a fast simulated annealing algorithm, the traffic matrix estimation being represented as a probability distribution. [0015] The present invention relies on the SATME technique to arrive at a preliminary estimation which is performed in an initial step while subsequent steps perform incremental estimates based on the estimate of the previous step. [0016] Accordingly, the invention provides a method for estimating a traffic matrix for a communication network based on measured link counts, comprising the steps of; a) establishing a fitness function for the respective network; b) generating a starting source to destination (SD) traffic matrix and calculating a starting value of the fitness function for the starting SD traffic matrix; c) modifying the starting matrix to obtain a randomly modified SD traffic matrix and calculating an updated value of the fitness function for the randomly modified SD traffic matrix; d) selecting the SD traffic matrix corresponding to the less of the starting value and the updated value as a temporary SD traffic matrix; e) changing the temporary SD traffic matrix using a simulated annealing algorithm, until the fitness function of the temporary SD traffic matrix satisfies constraints to a given tolerance; f) selecting the temporary SD traffic matrix estimated in step e) as a potential SD traffic matrix; and g) repeating steps b) to e) in subsequent time steps wherein the potential SD matrix of step f) is the starting SD matrix. [0017] The invention also provides a system for estimating a traffic matrix for a communication network. The system comprises: a source to destination (SD) traffic matrix generator for generating a starting SD traffic matrix based on network configuration data and on link counts collected for each link of the network; a random number generator for randomly altering the starting SD traffic matrix to obtain a randomly modified SD traffic matrix SD traffic matrix; a fitness function calculating unit for determining a starting fitness function and an updated fitness function for said respective SD traffic matrices and selecting the SD traffic matrix corresponding to the less of the starting value and the current value as a temporary SD traffic matrix; and a simulated annealing (SA) algorithm processor for changing the temporary SD traffic matrix until the fitness function of the temporary SD traffic matrix satisfies constraints to a given tolerance, and selecting the SD traffic matrix corresponding to the minimum as a potential SD traffic matrix wherein the potential SD traffic matrix is sent back to the traffic matrix generator for use in generating the new starting SD matrix for a subsequent time step. [0018] Advantageously, the invention requires no assumptions about the traffic, i.e. it allows the user to specify prior information about the network and traffic flows in a simple manner. [0019] Furthermore, the invention provides not just a point estimate of each element, but rather a probability distribution over all possibilities, so that the variation of the possibilities and the correlations between traffic on different links can be assessed. BRIEF DESCRIPTION OF THE DRAWINGS Continue reading about Fast simulated annealing for traffic matrix estimation... Full patent description for Fast simulated annealing for traffic matrix estimation Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Fast simulated annealing for traffic matrix estimation patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Fast simulated annealing for traffic matrix estimation or other areas of interest. ### Previous Patent Application: System, method and apparatus for authentication of nodes in an ad hoc network Next Patent Application: Method and apparatus for optimizing convergecast operations in a wireless sensor network Industry Class: Multiplex communications ### FreshPatents.com Support Thank you for viewing the Fast simulated annealing for traffic matrix estimation patent info. IP-related news and info Results in 0.12683 seconds Other interesting Feshpatents.com categories: Accenture , Agouron Pharmaceuticals , Amgen , AT&T , Bausch & Lomb , Callaway Golf 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
