Back to results
US 8,264,973 B2Granted
Method and system for timestep stochastic simulation for networks
AssigneeUniversity of Maryland
InventorsArunchandar Vasan, Ajjampur Udaya Shankar
Life of this patent
Estimating the term…
Abstract
A method and system for analytically simulating the state of a 802.11 WLAN network having a plurality of stations at discreet timesteps, including analytically generating a plurality of sample paths of a network state, including obtaining probability distribution values for aspects of the network. The probability distributions may be precomputed and stored in a cache to be accessed during a simulation of a network.
Claims17
A method for evaluating via a processor the performance of a network comprising a plurality of stations, the method comprising:
- establishing a timestep value;
- analytically generating a plurality of sample paths of a network state, wherein each of the states is simulated at a discrete timestep and wherein each discrete timestep is separated by the established timestep value;
- probabilistically determining at least one Media Access Control (MAC) state characteristic of a station at a timestep t+δ, δ being the timestep value, based on the MAC state characteristic at time t;
- for each station in the network, obtaining a probability distribution of an individual instantaneous goodput at each timestep given the station's MAC state at the start of the timestep;
- dependently sampling the individual instantaneous goodput at each timestep from the obtained probability distribution;
- and
- outputting network performance information based on the generated sample paths;
- wherein sampling the individual instantaneous goodput at each timestep from the obtained probability distribution further includes:
- applying a randomized algorithm that enforces a negative correlation constraint among any subset of a plurality of stations in the network;
- correlating the individual instantaneous goodput at each timestep such that the sum of the individual instantaneous goodputs for the plurality of stations in the network equals the determined instantaneous aggregate goodput for the network;
- ordering the plurality of stations according to a random permutation;
- and
- sampling a station's marginal distribution based in part on the sum of all goodputs allocated to it in a prior timestep and an aggregate goodput constraint.
10 more elements
A system for evaluating the performance of a network having α stations, the system comprising:
- means for establishing a timestep value;
- means for analytically generating a plurality of sample paths of a network state, wherein each of the states is simulated at a discrete timestep and wherein each discrete timestep is separated by the established timestep value, wherein the means for analytically generating a plurality of sample paths of a network state includes:
- means for probabilistically determining at least one Media Access Control (MAC) state characteristic of a station at a timestep t+δ, δ being the timestep value, based on the MAC state characteristic at time t;
- means for obtaining the probability distribution of the instantaneous aggregate goodput for each station in the network at each timestep given the station's MAC state at the start of the timestep;
- means for sampling the instantaneous aggregate goodput at each timestep from the obtained probability distribution;
- for each station in the network, means for obtaining the probability distribution of an individual instantaneous goodput given the station's MAC state at the start of the timestep;
- means for dependently sampling the individual instantaneous goodput at each timestep from the obtained probability distribution means for obtaining the probability distribution of the MAC state of each station at an adjacent timestep based on the MAC state and goodput at the previous timestep;
- and
- means for sampling the MAC state of each station at the adjacent timestep from the obtained probability distribution;
- and
- means for outputting network performance information based on the generated sample paths;
- wherein the means for sampling the individual instantaneous goodput at each timestep from the obtained probability distribution includes:
- means for applying a randomized algorithm that enforces a negative correlation constraint among any subset of a plurality of stations in the network;
- means for correlating the individual instantaneous goodput at each timestep such that the sum of the individual instantaneous goodputs for the plurality of stations in the network equals the determined instantaneous aggregate goodput for the network;
- means for ordering the plurality of stations according to a random permutation;
- and
- means for sampling a station's marginal distribution based in part on the sum of all goodputs allocated to it in a prior timestep and an aggregate goodput constraint.
14 more elements
A system for evaluating the performance of a network having α stations, the system comprising:
- a processor;
- a user interface functioning via the processor;
- and
- a repository accessible by the processor;
- wherein
- the user interface is configured to receive a timestep value;
- and
- the processor is configured to analytically generate a plurality of sample paths of a network state, wherein each of the states is simulated at a discrete timestep and wherein each discrete timestep is separated by an established timestep value, wherein analytically generating the plurality of sample paths of a network state includes:
- determining a per-station collision probability;
- probabilistically determining at least one Media Access Control (MAC) state characteristic of a station at a timestep t+δ, δ being the timestep value, based on the MAC state characteristic at time t;
- for each station in the network, obtaining a probability distribution of an individual instantaneous goodput at each timestep given the station's MAC state at the start of the timestep;
- obtaining a probability distributions at each timestep Pr[S(t+α)|S(t)] and Pr[N(t))|S(t)], where t is time, S(t) is the state of the network at time t, and N(t) is the goodput of the network at time t;
- and
- obtaining the state of the network from the probability distributions;
- and
- wherein the user interface is configured to output network performance information based on the generated sample paths;
- wherein analytically generating the plurality of sample paths of the network state further comprises:
- sampling the individual instantaneous goodput at each timestep from the obtained probability distribution further including:
- applying a randomized algorithm that enforces a negative correlation constraint among any subset of a plurality of stations in the network;
- correlating the individual instantaneous goodput at each timestep such that the sum of the individual instantaneous goodputs for the plurality of stations in the network equals the determined instantaneous aggregate goodput for the network;
- ordering the plurality of stations according to a random permutation;
- and
- sampling a station's marginal distribution based in part on the sum of all goodputs allocated to it in a prior timestep and an aggregate goodput constraint.
20 more elements
Dependencies are inferred from the claim text.