text:
This work discloses a unicast, end-to-end network performance measurement process which is capable of determining internal network losses, delays, and probability mass functions for these characteristics. The process is based on using groups of closely-spaced communications packets to determine the information necessary for inferring the performance characteristics of communications links internal to the network. Computationally efficient estimation algorithms are provided.
1. A method that includes:
sending a set of unicast communications packets from a source through the network, wherein the set of unicast communications packets includes multiple groups of communications packets, wherein the group are separated by at least a predetermined minimum time, wherein the communications packets within the groups are separated by no more than a predetermined maximum time, and wherein the predetermined maximum time is substantially less than the predetermined minimum time;
receiving from each of multiple receivers receipt information indicating those communications packets which have been successfully received by that receiver; and
determining a performance characteristic for each of multiple communications links in the network from the receipt information.
2. The method of
3. The method of
4. The method of
5. The method of
6. The method of
7. The method of
8. The method of
computing a conditional packet success rate of packets in the groups for the multiple communications links as part of maximizing a complete data likelihood function to determine the performance characteristic.
9. The method of
10. The method of
11. The method of
12. A method of determining network performance, wherein the method includes:
sending multiple sets of closely-spaced communications packets from a source through the network to multiple receivers, wherein the packets travel through a set of communications links characterizable as a tree having intermediate nodes between the source and the multiple receivers;
receiving from each of the multiple receivers receipt information indicating those communications packets which have been successfully received by that receiver;
determining a performance characteristic for each of the communications from the receipt information; and wherein the multiple sets are transmitted in a manner that avoids correlation of performance conditions.
13. The method of
14. A source computer configured to execute network performance determination software, wherein the software comprises:
a topology component configured to determine a tree structure of network communications paths from the source computer to multiple receivers;
a probe component configured to create a first log to track a set of unicast communications packets transmitted from the source computer to the multiple receivers;
a gathering component configured to create a second log to track end-to-end measurement information received from the multiple receivers regarding those communications packets which have been successfully received by the multiple receivers; and
an estimation component configured to process the first and second logs to determine a performance characteristic for each communications link identified in the tree structure.
15. The computer of
16. The computer of
17. The computer of
The present application relates to Provisional U.S. Patent Application No. 60/232,775, filed Sep. 15, 2000, and entitled "Unicast Network Tomography Process" by R. Nowak and M. Coates. This provisional is hereby incorporated by reference in its entirety.
Not applicable.
1. Field of the Invention
This invention generally relates to systems and methods for characterizing the performance of computer networks. More specifically, this invention relates to a process that provides loss and delay analysis of internal network links using only measurements "at the edge" of the network.
2. Description of the Related Art
Network performance information can be extremely useful, but for most applications it is important that the information be localized. Knowing how portions or individual components of the network are performing is more valuable than generating a global measure of performance. In particular, the ability to identify the performance of localized portions of the network would be useful for a number of increasingly important networking tasks, including Quality of Service (QOS) verification, maintenance, and content delivery optimization.
Quality of Service Verification
It is now common for Internet service providers to offer a variety of service levels to customers. Service level agreements specify performance criteria that the network provider guarantees to satisfy. Such criteria can include the amount of bandwidth made available to the customer and bounds on the maximum delay (which is important for Internet telephony and streaming applications). However, when a customer communicates via the Internet often a significant portion of the network connection is not under the direct control and responsibility of the service provider. If the customer experiences poor performance, it is difficult to determine whether it is due to the service provider's portion of the connection or the Internet at large. The only way to separate these effects and verify service is to assemble network performance information that is localized to the service provider's network. Unfortunately, directly measuring local network performance is very expensive for service providers. Furthermore, no existing techniques allow customers or third-parties to independently collect such information. It would be desirable to provide a method for an independent party to verify the service level without the cooperation of the provider and to provide a cost-effective means by which the service provider can track the performance of their system.
Maintenance and Provisioning
Maintenance of a network is a major portion of the effort involved in owning and operating a network. When the performance of a network is poor, it can be very difficult to isolate the cause of the problem. Sometimes a router is performing sub-optimally; on other occasions, too much network traffic is directed along one path while other paths remain idle. Furthermore, as networks grow in complexity it is often the case that network owners may not be aware of all components in their system, and consequently methods for mapping the topology of a network are critical. It would be desirable to have a way to determine the topology and connectivity of the network, to localize poor performance to individual network components, to rapidly identified faulty components, to optimize routing decisions, and to perhaps even indicate where additional network resources are required. The overall benefit is that maintenance overhead would be significantly reduced.
Content Delivery
Delivery of high-bandwidth content such as video poses a challenging resource-allocation problem. The source of the content must attempt to optimize the quality of content received by all users while minimizing the total network bandwidth that the content distribution consumes. Optimal bandwidth allocation accounts for the local loss-rates and delays in the network connecting the source and users. It would be desirable to have a system that can estimate local network performance and that can inform the content source of the loss rates and delays experienced at individual routers in the network.
Detection of network intrusion or misuse is extremely challenging. Most techniques are in their infancy, but it appears clear that many intrusions can be detected by the abnormal traffic patterns they generate. For example, rapid increases in the correlation of delay behavior in local network neighborhoods can be indicative of denial-of-service attacks. By conducting on-line monitoring of delay and loss behavior, rapid determination of the source of the attack becomes a much more feasible task. A system that can localize pathological network performance to individual components or subnetworks could aid in the early warning and detection of attacks and intrusions.
A system and method that determines network topology and localized performance measurements would preferably be based on "edge" measurements. Edge measurements are measurements made at the source and receivers, i.e. at the "edge" of the communications network. Conducting direct measurements at internal network points to acquire localized information is an expensive and in many cases an impractical task. Because internal routers operate at such high speeds and carry so much traffic, internal measurement demands special-purpose hardware devices dedicated to the collection of the traffic statistics. As the size of the analyzed network increases, the number of measurement devices grows exponentially. The installation and maintenance of these devices are extremely time-consuming and costly exercises. Moreover, organizing the transmission of the statistics that these devices record to a central processor is complicated, and the transmission of statistics consumes additional network resources.
Whilst measurement throughout a network is infeasible, measurement at the edge of the network is a much more tractable and low-cost task. There are far fewer sites at which measurement must be made, and perhaps more importantly, the measurement can often be performed in software. Techniques that rely only on edge-based measurement would allow independent performance monitoring to be performed, because measurement at the edge of the network does not require cooperation from the owner of the network.
In large-scale networks, end-systems cannot rely on the network itself to cooperate in characterizing its own behavior. This has prompted several groups to investigate methods for inferring internal network behavior based on end-to-end network measurements: the so-called network tomography problem. See R. Caceres, N. Duffield, J. Horowitz, and D. Towsley, "Multicast-based inference of network-internal loss characteristics," IEEE Trans. Info. Theory, vol. 45, November 1999, pp. 2462-80; C. Tebaldi and M. West, "Bayesian inference on network traffic using link count data," J. Amer. Stat. Assoc., June 1998, pp. 557-76; S. Vander Wiel, J. Cao, D. Davis, and B. Yu, "Time-varying network tomography: router link data," in Proc, Symposium on the Interface: Computing Science and Statistics, (Schaumburg, Ill.), June 1999; Y. Vardi, "Network tomography: estimating source-destination traffic intensities from link data," J. Amer. Stat. Assoc., 1996, pp. 365-77; "Multicast-based inference of network-internal characteristics (MINC)," gaia.cs.umass.edu/minc; S. Ratnasamy and S. McCanne, "Inference of multicast routing trees and bottleneck bandwidths using end-to-end measurements," in Proceedings of INFOCOM '99, (New York, N.Y.), March. While promising, these methods require special support from the network in terms of either cooperation between hosts, internal network measurements, or multicast capability. Many networks do not currently support multicast due to its scalability limitations (routers need to maintain per group state), and lack of access control. Moreover, multicast-based methods may not provide an accurate characterization of the loss rates for the traffic of interest, because routers treat multicast packets differently than unicast packets.
Accordingly, it would be desirable to provide a network tomography method that does not require special support from the networks and which provides a more accurate characterization of normal network behavior. Such a method would preferably be straightforward to implement and would be scalable.
We have developed an innovative and cost-effective process called Network Tomography Using Groups of Closely Time-Spaced Packets that produces accurate mappings of network structure and performance. It may provide estimates of losses and/or delays at internal routers as indicators of localized network performance. A key advantage of the process is that it can provide probability distributions for the measured performance parameters. This allows for a more complete characterization of the network behavior by indicating the accuracy and reliability of the measurements.
Broadly speaking, our methods have the potential to infer subnetwork and link-level (individual connections between routers in a large network) packet loss rates, delays, and utilization, as well as network topology. This will provide the complete characterization of network behavior that is necessary for maintenance and service provisioning, as well as Quality-of-Service verification. Another key advantage of our approach is that we do not require cooperation from any of the routers in the network; all inferences are based only on measurement cooperation between senders and receivers.
Our approach may advantageously employ end-to-end measurement of single unicast packets and groups of closely-spaced unicast packets. The measurements can be performed actively or passively. In contrast to multicast techniques, unicast network tomography is straightforward to implement on most networks and is scalable. Unicast methods will also provide more accurate estimates of network behavior, since the traffic in most networks is predominantly unicast in nature. The process may include the application of maximum likelihood estimation, probability factorization, missing data techniques, and message passing algorithms to the problem. These individual techniques are combined and applied in a novel way to enable very efficient and scalable estimation algorithms. In fact, the complexity of our loss-estimation algorithms grows linearly with the number of nodes in the network under study.
In the preferred embodiment, the process includes (i) sending a set of unicast communications packets from a source through the network to multiple receivers; (ii) receiving from each of the multiple receivers receipt information indicating those communications packets which have been successfully received by that receiver, and possibly indicating receive times of the packets; and (iii) determining a performance characteristic for each of multiple communications links in the network solely from the receipt information. The set of unicast communications packets preferably includes closely-spaced packet pairs, along with isolated packets. The time separation between isolated packets and pairs is preferably sufficiently large enough to provide approximate statistical independence, while the spacing of the packets in the pair is preferably small enough to provide very high correlation between the packet measurements. In the determination step, the process includes identifying the network topology, introducing variables for missing data (unobserved parameters) at internal network nodes, constructing a state-space data structure (a factor graph), and applying a message passing algorithm to maximize the likelihood function for the desired performance characteristic.
A better understanding of the present invention can be obtained when the following detailed description of the preferred embodiment is considered in conjunction with the following drawings, in which:
While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.
Unicast refers to the standard mode of communication in which each information packet is sent from a source to a specific receiver (in contrast to multicast or broadcast where each packet is sent simultaneously to many receivers). Typically, unicast measurements can be made by ISPs (Internet Service Providers) or individual users, and they require no special-purpose network support. Furthermore, they allow passive measurement methods to take advantage of the wealth of information available in existing network traffic (packet probes are not required).
End-to-end measurements refers to traffic measurements collected at host computers or routers at the periphery of the network. No measurements are made at internal routers or nodes in the network.
Back-to-back packet pairs refer to two closely time-spaced packets sent by the source to the same receiver or to different receivers. The two packets are sent one after the other by the source, possibly destined for different receivers, but sharing a common set of links in their paths.
Passive measurement refers to the use of existing network traffic to make the measurements, i.e. the network traffic is not perturbed by the insertion of extra packets for measurement or acknowledgement.
Active measurement refers to the transmission of special purpose packets over the network and using these packets to make the network performance measurements.
In this paper, we introduce a new methodology for network tomography based on unicast measurement. In contrast to multicast techniques, unicast inference is straightforward to implement on most networks and is scalable. The measurements can be performed actively or passively.
Our approach employs unicast, end-to-end measurement of single packet and back-to-back packet pair losses and/or delays. It uses the collected traffic statistics from edge-based measurements to calculate localized performance information. Our approach reconstructs internal performance and connectivity characteristics by exploiting the correlation between measurements made at different receivers. The algorithm is fast, reliable and cost-effective. It scales to large networks and the accuracy of the results is quantifiable.
Network Tree Structure
Turning now to the figures,
Because it is generally recognized that packet loss occurs, various communications protocols (for example, the Transmission Control Protocol (TCP)) include an acknowledgement mechanism. Generally, a receiver acknowledges the receipt of one or more packets by transmitting a reply packet.
The set of communications paths between the source computer an the receiver computers at any given time will possess a tree structure. The structure of the tree may vary as routing tables change, but these changes occur relatively infrequently.
The tree structure in
Software Architecture
Before describing the problem formulation in detail, we describe the high-level structure of software that implements the Network Tomography process.
Sender software package 402 may include four components that execute periodically. The first component operates to identify the tree topology of the network. The second component generates (for active measurement) or identifies (for passive measurements) packets directed to the receivers. The third component collects the information provided by the acknowledgements from the receiver computers, and the fourth component determines the desired localized network performance measurements from the collected information.
Although the routing tables in the Internet are periodically updated, these changes occur at intervals of several minutes. The measurements made by the software typically occurs on a much shorter timescale, so the topology may be considered static for the duration of the measurements. The topology identification component determines the topology before and after the measurement period to verify that the topology has not changed. In the preferred embodiment, the topology identification is performed using a modified version of "traceroute", a program freely available at ftp.ee.lbl.gov/traceroute.tar.Z. The topology identification component runs this program once for each receiver to determine the path traversed by packets traveling from the source to the receiver. The path information is then combined to identify the branching nodes and the connections therebetween.
In a contemplated embodiment, the topology identification component includes a monitoring module that monitors the branching nodes that have been identified. If the routing tables are updated at a branching node, the topology is quickly redetermined and the measurement methodology updated accordingly.
The probe generation component, if operating in active measurement mode, preferably requests and establishes TCP connections with each of the receivers to ensure that the receivers are ready to receive packets. Then the component sends UDP probes to each of the receivers. This component may rely on user-specified parameters that indicate a list of receivers, the UDP and TCP ports to use, the total number of probes to send, and the minimum gap between successive probes. Probes are spaced so that successive measurements are approximately independent. The necessary minimum time spacing will be system-dependent, but is expected to be in the range between 100 microseconds and 100 milliseconds. The UDP packet(s) that constitute a probe include fields that contain the packet identification numbers, the time at which the packet was sent, and the index number assigned to the destination(s).
In the passive measurement mode, the source already has numerous contemporaneous connections with a number of receivers. The probe generation component selects as many informative measurements as possible from the existing traffic. Preferably, this component first identifies the important packet-pair measurements (which are less common than the isolated packet measurements). It first inspects the sending times of the traffic at the source and decides that two packets form a packet-pair if their time-spacing is less than a threshold δt seconds. This threshold is dependent on the sending rate of the source. Commencing at the start of the measurement period, the component scans forward in time, seeking and identifying the first packet-pair. It then steps forward by a fixed time interval Δt>>δt and begins searching for the next pair. In this way, the pairs included in the analysis are all separated by a reasonable time interval, making the assumption of statistical independence between pairs more realistic. Following the collection of these pairs, the probe generation component identifies any isolated packets that do not violate the time separation requirement. In general, the number of such packets is significantly larger than the number of pairs.
This packet identification scheme is very fast. However, some pairs may be more informative than others, i.e. those pairs having packets going to different receivers ("cross-pairs") are rarer than those with packets going to the same receiver. Accordingly, a variation of the identification technique begins by identifying all cross-pairs and including the maximal set that does not violate the Δt separation requirement. After the set of cross-pairs has been finalized, the "auto-pairs" (pairs with both packets destined for the same receiver) are identified and included, excepting those that violate the Δt time-separation criterion with the pairs already included. Finally, single (isolated) packets are included, again maintaining the Δt time-separation. This variation typically provides more informative statistics from a given set of traffic data, and may reduce the measurement time duration required for accurate loss inferences.
A more aggressive approach to obtain more informative data could involve alternative session servicing strategies at the source. For example, instead of a basic round-robin service strategy, the source could employ a scheme that would enhance the chances of cross-pairs occurrences, without necessarily deviating from current network protocols.
The receiver software 404 may be a light-weight network client that is executed on all receivers during (active) measurement periods. The receiver listens for TCP connections from the source, and once a connection is established, it begins to accept UDP packets from the sender. As each UDP probe is received, it is timestamped with the local system time and then transmitted via a TCP socket back to the source. TCP is used for the acknowledgement of probes in order to guarantee that no losses occur on the reverse path. In this manner, the software isolates forward path loss statistics. The receiver program has been implemented in Java, and ported it to C for Solaris, Linux, and Windows (via winsock). These various implementations allow the receiver software to easily run on many of the different types of hosts that are connected to the Internet.
The source software 402 maintains two separate logs of the experiment: one for the probe transmission statistics, and one for the reception statistics from the receivers. During measurement, the data collection component listens on the TCP connections, generating a file containing information on all the packets that were echoed by the receivers. The performance measurement component compares the two logs and determines the performance statistics therefrom.
Formulation for Loss Measurement
We begin by stipulating link performance measurement(s). Although a variety of performance measurements may be determined using the techniques disclosed herein, we select packet loss rates and packet queuing delays as most indicative of network link performance. Other possible measures include utilization percentages and bandwidth availability.
Throughout this document, when dealing with network packet loss rates we will use "success" probabilities (i.e. probability of non-loss) instead of loss probabilities. This provides a more convenient mathematical parameterization of the problem, and the probability of loss is simply one minus the probability of success.
The basic idea for the inference of internal packet loss rates or delay characteristics is quite straightforward. Suppose two closely time-spaced (back-to-back) packets are transmitted from a sender to two different receivers. The paths to these receivers share a common set of links from the source but later diverge. Because closely time-spaced packets on a link are likely to encounter the same conditions, the probability that one packet successfully traverses the link given that the other packet has successfully traversed the link is near unity. This observation has bee verified experimentally in real networks (See V. Paxson, "End-to-end Internet packet dynamics", IEEE/ACM Trans. Networking, vol. 7, June 1999, pp. 277-92.) and can also be established theoretically under an M/M/1/K queue model. In our experiments, we are able to obtain accurate loss estimates even in cases where the conditional success probabilities are significantly less than one (e.g., conditional success probabilities of 0.9, which are much lower than a typical measurements on the Internet).
If one of the packets is dropped and the other successfully received, then (assuming shared fates on shared links) one can infer that the packet must have been dropped on one of the unshared links. Similarly, the two packets should experience the same delay on shared links in their paths. This enables the resolution of average delays on individual links. In fact, the topology of a network can also be identified from packet pair measurements by studying the covariance between losses and/or delays to different receivers.
Given a collection of packet pair measurements, we can compute maximum likelihood estimates (MLEs) of localized network performance parameters. The MLEs are simply defined as the parameter values that make the observed packet pair measurements most likely, in a statistical sense. We have developed a numerical optimization technique based on the Expectation-Maximization Algorithm, Bayesian Analysis, and Graphical Statistical Models to compute the desired MLEs very efficiently. The computational cost of the algorithm grows linearly in proportion to the number of links in the network (rather than growing exponentially, for example). The linear complexity of the algorithm is beneficial because it guarantees that the entire Network Tomography process is scalable to very large networks.
Loss Model
Beginning with individual packet transmissions, we assume a simple Bernoulli loss model for each link in the network. That is, each of the individual packet transmission events on link i are independent of each other with a success probability of αi. The probability of a lost packet on link i is 1−αi. The loss processes of the separate links are assumed to be independent, so that the probability of success on one link does not affect the probability of success on any other links.
Suppose that the source sends ni packets to receiver i, and that of these, only mi packets are received. The likelihood of this result is
Moving now to closely-spaced packets, we assume a Markovian model of packet loss. that is, the probability of successful transmission of either individual packet on link i is αi=Pr{success}, and the probability of successful transmission of the second packet on link i, given that the first packet successfully traversed link i is
Suppose that the source sends a large number of back-to-back packet pairs in which the first packet is destined for receiver i and the second for receiver j. We assume that the timing between pairs of packets is considerably larger than the timing between two packets in each pair. Let nij denote the number of pairs for which the second packet is successfully received at nodej, and let mij denote the number of pairs for which both the first and second packets are received at their destinations. Furthermore, let S(i,j)=P(i)∩P(j) be the set of links common to both paths to receiver i and receiver j, and let R(i,j)=P(i)−S(i,j) be the set of unshared links in the path of the first packet. For example, if the leftmost two receivers in
To use the likelihood formulas given above, we preferably make an assortment of single packet and back-to-back packet measurements distributed across all of the receivers. (Although single-packet statistics may also be determined from the back-to-back packet measurements, e.g. by ignoring one of the packets in each packet pair, more information can be gathered in a shorter amount of time by also considering single packets.) Accordingly, let us represent the set of collected measurements using
Since M and N are known from measurements, the joint likelihood is a function of the unknown link success probabilities A and Γ. Determining the link success probabilities that maximize the joint likelihood function is known as maximum likelihood estimation. This is denoted
If the desire is primarily to determine the unconditional success probabilities A, then integration can be used to eliminate the "nuisance" parameters:
Due to the coupled, multidimensional nature of these expressions, directly calculating the estimates can be a computationally intensive task. One technique that significantly reduces the required computational effort introduces "unobserved" variables. Properly chosen, these unobserved variables can de-couple the effects of the other variables, thereby simplifying the individual calculations.
To introduce the notion of unobserved data, let us consider the likelihood
Various optimization strategies may be used to maximize the complete data likelihood function. One strategy is to use factor graphs and marginal analysis. This strategy is based on graphical representations of statistical models. Such representations include Bayesian networks and, more generally, factor graphs. Both the parameters of interest and the collected data appear as nodes in the factor graph. Each node associated with a parameter is characterized by a (potentially unknown) probability distribution (this is the marginal likelihood function described above). Links between nodes indicate probabilistic dependencies. By introducing unobserved variables as additional nodes, it is possible to decouple the effects of different success probabilities in the graphical model.
Probability propagation can be used to perform exact inference, provided the graph structure is acyclic. However, this may require high-dimensional summations, leading to a heavy computational burden. In general, exact inference algorithms may scale poorly as the network size increases. Approximate inference strategies may perform somewhat better.
We propose an efficient iterative procedure to estimate the marginal likelihoods of the network loss parameters. The procedure makes use of the (theoretically) most informative measurements first. The procedure first forms estimates of the marginal distributions of the β parameters.
The procedure for estimation of the α parameters follows the same pattern. The leaf parameter marginals are estimated first (using appropriate estimated β marginals) and then these estimated marginals are used to perform inference of α parameters further up the tree. Further details on the use of factor graphs may be found in B. Frey, Graphical Models for Machine Learning and Digital Communication, MIT Press, Cambridge, 1998, which is hereby incorporated by reference.
Expectation Maximization Inference
Another strategy that may be used to maximize the complete data likelihood function is the expectation-maximization (EM) approach. This approach alternates performs two steps: the expectation step estimates the unobserved data using the current values of the probability parameters, and the maximization step calculates updated values of the probability parameters that maximize the complete data likelihood function. The approach begins by making initial guesses for A and Γ (e.g. setting them all to unity). The two steps are then iteratively repeated until A and Γ converge.
In the expectation step, the conditional expected values of the unobserved data from the observed data and current estimates of the success probabilities. Closed-form formulas do not exist for these conditional expected values, but they can be computed algorithmically. Using an efficient algorithm such as an upward-downward probability propagation (or "message passing") algorithm, such as that disclosed in B. Frey, Graphical Models for Machine Learning and Digital Communication, MIT Press, Cambridge, 1998, the expectation step can be computed in O(N) to O(N2) operations (depending on network topology), where N is the total number of nodes in the network.
In the maximization step, both the observed and unobserved data are used to calculate the values of A and Γ that maximize the complete likelihood function. Since the complete data likelihood function factorizes into a product of univariate functions, each parameter can be maximized independently using a closed-form analytic expression. Consequently, computation of this step can be done in O(N) operations.
It can be shown that the original (observed data only) likelihood function is monotonically increased at each iteration of the algorithm, and the algorithm converges to a local maximum of the likelihood function. If convergence is defined to occur when none of the unconditional success rates αk changes by more than 0.001, then convergence typically occurs in a small number of iterations (i.e. 15-50 iterations).
Simulation Results
The network simulation was performed in the following manner. Each link in the network was allowed to assume one of two state values, 0 (representing congestion) and 1 (representing light traffic). At each time instant t, the state of each link was updated according to a Markov process. The transition probability matrix of the process governing the link state was determined by drawing αi from a uniform distribution U[0,1], and then drawing βi from U[αi 1]. The matrix was designed so that if traffic were sent across the link, it would experience a steady-state success probability of αi, and a conditional success probability βi. Packet pair probes were sent to the various receivers in an ordered fashion designed to extract an informative subset of the possible mi,j and ni,j. The times at which the first packets were sent were determined from a Poisson process, such that the inter-arrival times were well-separated. The second packet was sent one time instant later. 1600 packet pairs were sent through the network, with the destinations designed so that there was a uniform distribution across the network of divergence nodes.
The pmfs shown in
In situations where the size of the network limits the ability of the sender software 402 to gather enough information for accurate estimation, a grouping technique may be used to reduce the number of divergence nodes. This is particularly useful if just the performance of the topmost links is of interest.
Process Formulation for Delay Measurement
In addition to packet loss statistics, the packet pair concept can be used to infer communication delays on each of the network links. Suppose two closely time-spaced (back-to-back) packets are sent from the source to two different receivers. The paths to these receivers traverse a common set of links, but at some point the two paths diverge (as the tree branches). The two packets should experience approximately the same delay on each shared link in their path. This facilitates the resolution of the delays on each link.
In the following, we distinguish between a "measurement" period and an "inference" period. The measurement period is the time period over which all measurements are collected. The inference period is some time window within the measurement period; the window duration is dictated by the degree of network stationarity and only the measurements collected in this window are used to perform inference. In order to achieve estimates over the entire measurement period, multiple inferences are performed using different, potentially overlapping inference windows.
The source software 402 collects measurements of the end-to-end delays from source to receivers, and indexes the packet pair measurements by k=1, . . . ,N. For the k-th packet pair measurement, let y1(k) and y2(k) denote the two end-to-end delays measured. The ordering is arbitrary; the delay indices are randomly selected with no dependence the order in which the packets were sent from the source. This aids in dealing with discrepancies between the delays experienced by the two packets on shared links, because the random ordering will cause the averaged discrepancy to be zero.
In characterizing network delays, packet pairs in which either of the packets is lost are preferably discarded. However, it is possible to extend this approach to include losses by allocating an "infinite delay" category for lost packets.
Since we are interested in inferring queuing delay, the first step is to identify the minimum delay (propagation+transmission) on each measurement path. This is estimated as the smallest delay measurement acquired on the path during the measurement period.
Our goal is a nonparametric estimate of the delay distributions on each link. Clearly it is impossible to completely determine an infinite dimensional density function from a finite number of delay measurements, but we require that as the number of delay measurements increases so does the accuracy of our estimation procedure. Thus, we adopt the following procedure. The end-to-end delay measurements are binned, but the number of bins is chosen to be equal to or greater than the number of delay measurements. In practice we choose the number of bins to be the smallest power of two greater than or equal to the number of measurements (facilitating certain processing steps to be described later). We upper bound the maximum delay on any one link by the maximum end-to-end delay along the path(s) that include that link. Let dmax denote this upper bound for a particular link and let K be the smallest power of 2 that is greater than or equal to the number of measurement packets N. The bin width for the link is then set at dmax/K.
This procedure is conservative, in that the estimated dmax may be substantially larger than the true maximum queuing delay. It may be preferable to use previous link-delay estimates or bandwidth estimates from a separate procedure to gauge the maximum delay on any link.
At this stage, each end-to-end measurement has been ascribed a discrete number between 0 and L (K−1), where L is the maximum path length in the network.
There are several assumptions in the framework that are worthy of discussion. Firstly, we assume spatial independence of delay. Delay on neighboring links is generally correlated to a greater or lesser extent depending on the amount of shared traffic. In simulation experiments, correlation of delays has been observed. In the presence of weak correlation, our framework is able to derive good estimates of the delay distributions. As the correlation grows stronger, we see a gradual increase of bias in the estimates. We also assume temporal independence (successive probes across the same link experience independent delays). Temporal dependence was observed in our experiments. The maximum likelihood estimator we employ remains consistent in the presence of temporal dependence, but the convergence rate slows. It does not have a dramatic effect on the performance of the estimator.
We do not necessarily require that clocks at the source and receivers be synchronized, but we do require that the disparity between clocks remain very nearly constant over the measurement period. In this way we can be sure that subtracting the estimated minimum delay does not induce bias in our estimates. A further difficulty lies in clock resolution. Clocks must be able to resolve delay sufficiently accurately that the potential error does not overwhelm the true delay value. Deployment of Global Positioning System (GPS) devices allows these clock difficulties to be avoided, as it provides synchronized measurements to within tenths of microseconds. Alternatively, delay measurements can be made using software clocks that have algorithms for enhanced accuracy. Hereafter, we assume that synchronized measurements are available.
Delay Model
Let pt={pi,0, . . . ,pi,K−1} denote the probabilities of a delay of 0, . . . ,K−1 time units, respectively, on link i. We denote the packet pair measurements y={y1(k),y2(k)|k=1, . . . ,N}.
In general, only a relatively small amount of data can be collected over the period when delay distributions can be assumed approximately stationary. A natural estimate would be the maximum likelihood estimates (MLEs) of p={pi}, the collection of all delay pmfs. However, when using a number of bins that is equal to or larger than the number of measurements, the problem is ill-posed and the MLE tends to overfit to the probe data, producing highly variable estimates that do not accurately reflect the delay distribution of the traffic at large. High variance manifests itself in irregular, noisy-looking estimates. One way to reduce this irregularity is to maximize a penalized likelihood. We replace the maximum (log) likelihood objective function L(p)=log l(y|p) with an objective function of the form:
Under the assumption of spatial independence, the likelihood of each delay measurement {y1(k),y2(k)} is parameterized by a convolution of the pmfs in the path from the source to receiver. With our modeling constraint that packets in a pair experience the same delay on shared links, the likelihood of the two measurements made by the k-th packet pair is:
The presence of convolved link pmfs in the likelihood of each measurement results in an objective function that cannot be maximized analytically. The maximization of the likelihood function requires numerical optimization, and an EM algorithm is an attractive strategy for this purpose. Before giving the details of the algorithm, we briefly review the MMPLE nonparametric density estimation procedure employed in our framework.
Here we briefly outline the MMPLE density estimation procedure developed in E. Kolaczyk and R. Nowak, "A multiresolution analysis for likelihoods: Theory and methods," submitted to Annals of Statistics, 2000. To introduce the idea, we consider a case where the link delays have been directly measured (we will handle the tomographic case using the EM algorithm outlined in the next section). Let zl(k), k=1, . . . ,Ni, denote a set of delay measurements for a particular link i. We assume that these measurements are independent and identically distributed according to a continuous delay density p(t), where without loss of generality we assume that tε[0,1] (for convenience of exposition we take the maximum delay to be unity). Define a discrete pmf via
The MMPLE methodology can be employed in the tomographic delay estimation case by simply adopting the penalized likelihood criterion:
The first step in developing an EM algorithm is to propose a suitable complete data quantity that simplifies the likelihood function. Let zi(k) denote the delay on link i for the packets in the k-th pair. Let zi={zi(k)} and z={zi}. The link delays z are not observed, and hence z is called the unobserved data. Define the complete data x={y, z }. Note that the complete data likelihood may be factorized as follows:
The EM algorithm is an iterative method that uses the complete data likelihood function to maximize the log-likelihood function. By suitable modification, it can maximize a penalized log-likelihood objective function instead. Specifically, the modified EM algorithm alternates between computing the conditional expectation of the complete data log likelihood given the observations y and maximizing the sum of this expectation and the imposed complexity penalty (−pen(p)) with respect to p. Notice that the complete data log likelihood is linear in m:
Let p(r) denote the value of p after the r-th iteration. Then
In the penalized case (penalized likelihood criterion), apply the MMPLE algorithm to the conditional expectation {{circumflex over (m)}i,j (r)}. For unpenalized maximum likelihood estimation, simply substitute {circumflex over (m)}i,j (r) in place of mij in equation (1).
Fast Fourier Transform Based EM Algorithm
The expectation step of the EM algorithm poses the major portion of the computational burden of the optimization task. It can be performed using a message passing (or upward-downward) procedure. Unfortunately, a straightforward implementation of the message passing procedure, has a computational complexity which is O(MK3), where M is the number of links in the tree and K is the number of bins. This may be impractical in our nonparametric setting since K is not fixed, but rather increases in proportion to the number of measurements. In this section, we describe a novel, fast Fourier transform based implementation which is O(MK2 log K), a tremendous reduction in complexity when K is large.
The message passing procedure is based on a factorization of the likelihood function, which can be represented graphically using a factor graph. According to (2), our task for each measurement in the r-th iteration of the EM algorithm is to compute p(r)(zi=j|y1, y2) (we have dropped the measurement index k for clarity). In J. Pearl, "Fusion, propagation, and structuring in belief networks," Artificial Intelligence, vol. 29, pp. 245-57, 1986, an exact probability propagation algorithm is disclosed for inferring the distributions of individual variables in singly-connected graphical models. The basic idea of the algorithm is that each node in the graph propagates its information (a measurement or current pmf estimate in this case) to every other node. Each node then combines all the messages it receives to compute the distribution of its variable.
We illustrate the procedure for a packet pair measurement to receivers 1 and 2 of the network in FIG. 2. For this scenario, the factor graph representation is depicted in FIG. 9. The hollow nodes of the graph represent variables (the link delays {zi} and the cumulative delays {di} at links 0, 1, 2, 4 and 5. The small nodes represent functions—these either indicate functional relationships between variable nodes or carry prior information. In this case, the nodes labeled pi (r) carry the current pmf estimates and nodes cij represent convolution operators. For example, node c1,2 indicates that the accumulated delay pmf at node dl is convolved with the link delay pmf z2 to obtain the accumulated delay pmf at node d2.
The message passing algorithm can be divided into two sections. In the "upward" stage, all information available at the leaves of the tree is passed up the tree towards the root. In the "downward" stage, the information at the root is passed down to the leaves. In this case, the leaf information includes the measurements and the current pmf estimates. The root information is simply the knowledge that d0=0. We use the notation μ(a→b) to represent the message that is passed from node a to node b in the graph; each message takes the form of a pmf. We now provide a brief outline of the messages generated and how they are combined and distributed.
At each variable node zi, the incoming messages are multiplied together to calculate the local distributions for the delay pmf variables. For example, multiplying the two messages flowing into node z1 together gives p(r)(z1=j|y1,y2)=μ(c0,1→z1)(j)�μ(p1 (r)→z1)(j).
It is the summations in steps Up-9 and Down-2 that introduce the complexity of O(K2). We avoid this O(K2) computation by noting that messages involving such summation can be written as a convolutions provided we first time-reverse one of the pmfs involved. By time-reversal, we mean that {tilde over (p)}(r)(zi=j)=p(r)(zi=K−1−j) where {tilde over ( )} denotes time-reversal. For example, we can write:
The K2 factor in the complexity dominates the other terms. However, further computational savings can be introduced by exploiting the additive nature of the Fourier transform. This has the effect of replacing the K2 factor by (K/Mint)2, where Mint is the number of internal nodes in the network. The computational savings can be a substantial.
Measurement of Nonstationary Network Parameters
In this section, we propose a sequential Monte Carlo (SMC) procedure capable of tracking nonstationary network behavior and estimating time-varying, internal delay characteristics. (Topology changes are not addressed by this procedure.) This methodology is based on sequential importance sampling that not only addresses the basic (stationary) network tomography problem, but also directly tackles the more challenging and realistic problem of tracking time-varying network delay behavior. A stochastic model of the network dynamics is provided below. The available observations are a highly non-linear function of the system. As a result, the extended Kalman filter is not suitable for the task. The EM algorithm also assumes the network is stationary and does not account for temporal variations.
We collect measurements of the end-to-end delays from source to receivers, and we index the packet pair measurements by m=1, . . . ,M. For the m-th packet pair measurement, let y1(m) and y2(m) denote the two end-to-end delays measured. The delays are quantized such that the quantized delay on each link falls in the range 0,1, . . . ,K time units.
To describe our observation model, let us first consider the case of a stationary network in which the delay characteristics are not time-varying. Associated with each individual link/router in the network is a probability mass function (pmf) for the queuing delay. Let pl={pi,0, . . . ,pi,K} denote the probabilities of a delay of 0, . . . ,K time units, respectively, on link i. Given the packet pair measurements y≡{y1(m),y2(m)}, we are interested in maximum likelihood estimates (MLEs) of p≡{pi}, the collection of all delay pmfs. The likelihood of each delay measurement is parameterized by a convolution of the pmfs in the path from the source to receiver. The coupling of the pmfs of each link results in a likelihood function that cannot be maximized analytically. The joint likelihood l(y|p) of all measurements is equal to a product of the individual likelihoods. The maximization of the joint likelihood function requires numerical optimization, and the EM algorithm is an attractive strategy for this purpose.
In nonstationary networks, the queuing behavior varies over time, and the notion of a delay distribution is not well defined. Nonetheless, time functions such as the expected delays across each link are very much of interest. To put such notions on firmer ground, we define the time-varying delay distribution of window size R at measurement m as:
We now consider the problem of modeling time-varying delay distributions as defined in (4). We propose a relatively simple parametric family of dynamical distributions to describe the queuing delay distributions of individual network links. The models are sufficiently general to capture a variety of potential network conditions. The models play the role of prior probability distributions in our SMC framework. In that context, the prior is a mixture (or superposition) of a variety of the elementary models (distinguished by different parameter settings). The basic idea is that, although no single model and parameter setting may accurately describe the complex queuing behavior of actual networks, mixtures of many such models with diverse parameter settings may be sufficient to capture the true behavior. In the SMC algorithm, the mixing of the models is a function of the actual network measurements; this is a key strength of the approach which allows us to use previous measurements to improve the MC sampling in subsequent steps of the dynamical estimation procedure. The SMC algorithm is described in the next section. We now propose the parametric family of dynamical models underlying the prior distribution of the algorithm.
The queuing delay experienced by a measurement packet on each link in the network is due to other packets in the queue(s) of the associated router(s). The most elementary model for queuing delay distributions is derived the classical M/M/1/K queue model. This model will serve as a motivation for the building block of our prior (mixture) distribution. In addition to M/M/1/K queuing, we assume a network in which each link is a direct connection between two routers and associate the delay on each link with a dedicated output queue at the router from which it emerges (i.e. each outgoing link has its own dedicated queue). Each of these queues has a buffer size K with Markovian services at rate μ. Coupled with a homogeneous (constant rate λ) Poisson arrival process, this model is the standard M/M/1/K queue model. In extending this to heterogeneous networks (differing service rates and queue sizes), we assume that we make measurements (send packet-pairs) at a rate of C1 μK where C1>1 is a constant. This ensures that there is sufficient time for the queues to relax between measurements, resulting in approximately statistically independent measurements.
Now, in the nonstationary setting, the most simple approach is to adopt a model in which packet arrivals at a given queue are governed by a time-varying (inhomogeneous) Poisson arrival process. We will also assume that the bandwidth B of this process is limited such that
The model described thus far induces delay pmfs at each measurement time of the form
In real networks, however, the delay pmfs can display modes at other points due to the non-Poissonian nature of traffic and due to the fact that each link may include multiple "hidden" routers. To account for such modes we propose the following extension of the M/M/1/K type model. We introduce an additional dynamical (continuous) parameter κl for each link and define the delay pmf as
To summarize, we have proposed a parametric family of dynamical models to describe the queuing delay distributions of network links. All parameters of this model, K, μ, λl, are unknowns in our framework (the SMC algorithm will employ many different settings of parameters to obtain a reasonably dense sampling of the parameter space). The models are sufficiently general to capture a variety of potential network conditions. The prior distribution of our SMC procedure, described next, is a mixture (or superposition) of these basic parametric models. As demonstrated above, such mixtures are capable of representing all possible delay distributions. Moreover, the priors on the dynamics of our framework (random walks) and associated parameters (variances of random walks) are fairly non-informative, ensuring that the SMC procedure is mostly influenced by the data themselves and is not strongly affected by our modeling assumptions.
Sequential Monte Carlo Tracking of Time-Variation: Algorithm Development
We would like to track the internal delay distributions over time. More specifically, based on our measurements we wish to estimate the time-varying delay distribution defined in (4). We will focus on the posterior mean as our estimator. The posterior mean is simply the mean of the posterior density, which is proportional to the likelihood function of measurements multiplied by the prior distribution placed on the delay pmfs. The prior we employ here is a mixture of time-varying pmfs of the form (5). The mixing function is determined by the dynamical structure of each time-varying pmf, as governed by the random walks described in the previous section.
The posterior mean estimate of pij(R,m) can be written as:
The evaluation of this estimator is difficult. It requires an integration over the density p(λl|y1 m), which cannot be solved analytically. We adopt numerical integration techniques. Moreover, we calculate the estimate at each time m. It is important that we form our estimate {circumflex over (p)}i,j(R,m) without redoing all the calculations involved in generating the estimate at time m−1. Otherwise we are not only wasting considerable computations, but we render a real-time implementation of our procedure impractical. These considerations motivate the adoption of a sequential algorithm.
In the dynamic model, the available observations yl:m are a highly non-linear function of the evolving parametersλ0,m. Standard sequential tracking methods such as the Kalman filter are not applicable; our attempts at linearization (e.g., the extended Kalman filter) also result in very poor tracking.
We begin by briefly outlining the Monte Carlo nature of the technique. Because the integral in (9) can not be calculated analytically, we approximate the estimator using Monte Carlo integration. To do this, we must sample from p(λl|y1�m), which itself is not easily accomplished. An alternative approach is to perform "importance" sampling. Let λ0:m denote the trajectories of the traffic intensities on all links over the time interval 0, . . . ,m. The basic idea here is to generate N draws of λ0:m from an importance distribution πm, that has the same support as p(λ0:m|y1:m) but from which we can sample more easily. We wish to sample the entire trajectory λ0�m rather than just λl because the trajectories are highly coupled (evaluating p(λl|y1.m) requires difficult marginalization). Each draw represents an independent sample path of the network's dynamical evolution and thus independently explores part of the sample space. We use these draws (or "particles") to compute the desired Monte Carlo integration as follows. We can re-write the integration as,
Evaluating p(zi(l)=j|y(l),λl (ν)) involves the application of an upward-downward algorithm. This algorithm propagates the knowledge of (1) the zero delay at the source and (2) the delays y(l) at the two receivers throughout the tree, exploiting the independence of the conditional pmfs to calculate marginal distributions at each node.
Sequential Importance Sampling
The Monte Carlo integration approach described above requires us to generate entire trajectories λ0:m at each time m, and then to calculate the associated weight. This is computationally demanding and highly wasteful. At time m, we want to perform the integration without redoing calculations made at time m−1. This is achieved by forming the trajectory λ0:m (ν), without modifying the previous trajectory λ0:m−1 (ν)which is possible if the importance sampling distribution has a Markovian structure. At time 0, we sample from the initial distribution π0(λ0). At time m, we sample from πm(λm|λ0:m−1 (ν),y1:m), and form the time-m particle ν by appending λm (ν) to λ0:m−1 (ν). The weight of particle ν at time m can then also be updated recursively:
The dynamics of the proposed model involve a random walk of log λm. We employ the prior distribution p(λm|λm−1) as the importance function. In this scenario, we merely calculate the likelihood to determine the update in the weights:
Degeneracy is a major issue in the application of sequential importance sampling. The multiplicative update applied to the weight at each time means that some importance weights may quickly tend to zero, and the number of particles contributing to the estimator is greatly reduced. This effect increases the variability of the estimator (compared to the variance one would have with the full N particles contributing). The procedure of "resampling" aims to generate an unweighted approximation of the weighted particle distribution. When performed at time m, the procedure associates with each particle v a number of offspring Nm (ν), such that
This resampling process does introduce some additional computational overhead in the formation of our approximate estimator at time m. Technically, it necessitates calculating the marginal smoothing distributions p(λl|y1:m) for lε{m−R+1, . . . , m}. This can be done using the two-filter formula of G.Kitagawa, "Monte Carlo filter and smoother for nonlinear non-Gaussian state space models," J. Comp. Graph. Statist., 5:1-25, 1996, or a forward filtering-backward smoothing of A. Doucet, et al, "On sequential Monte Carlo sampling methods for Bayesian filtering," Statist. Computing, 10:197-208, 2000, or the backwards simulation procedure of S. J. Godsill, et al, "Monte Carlo smoothing for nonlinear time series," Technical report, Institute of Statistics and Decision Sciences, Duke University, 2000.
In simulations, we observe that if we use the approximation (replacing {tilde over (w)}m (ν) with {tilde over (w)}l (ν):
The packet-pair measurement procedures disclosed herein allow for the accurate determination of performance information including the loss rates and delay characteristics of individual links in the network (a link is the connection between two routers). In addition, this technique may be used to isolate available link bandwidth and link utilization if link capacities are known. (Various other software tools exist for determining link capacities. )
Among the many advantages of this technique is that is readily applied in many frameworks, including those that provide for passive, nonparametric and time-varying performance characterization. In addition, it requires no cooperation from internal routers nor does it require any modification of existing network protocols. The performance characterization is expected to be of great utility to service providers, system administrators, and end users, because it characterizes the conditions experienced by unicast packets, the most commonly used communication packets. Further, the computational overhead and bandwidth overhead required by the disclosed techniques is quite moderate and it scales well with the size of the network.
Numerous variations and modifications will become apparent to those skilled in the art once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.
Patent Citations
Non-Patent Citations
Referenced by
Legal Events
Original Image


text:
Walking really is like medicine. It eases RA pain and strengthens the muscles that support your joints. It can boost your mood, help you sleep better, and make you fit enough to keep doing the things you love to do. It lowers your blood pressure and could even help you live longer.
Use these tips to make walking more fun and part of your daily routine.
Go slowly. If you're out of shape and just getting started, be careful. If a 5-minute walk in the morning and evening is all you can manage, that's fine. At first, walk on a flat surface and avoid hills. Then build up, adding more minutes each session. Pacing yourself is so important when you have RA. If you overdo it by jumping from no walks to hour-long hikes, it could take you weeks to recover.
Have a good pair of shoes. The only crucial expense of walking is a good pair of shoes. If your shoes are worn out, or fit poorly, walking may hurt. And if walking hurts, you won't want to do it anymore. Invest in shoes that offer solid support. Thick treads may lower your risk of falling. Get your feet measured, too -- your size may have changed over the years. Be ready to replace your shoes every 500 miles.
Take breaks. If you aim to walk 30 minutes today, don't do it all at once. Rest along the way. For instance, try walking in a park or at the mall where you know there are plenty of benches. Sit down for a few minutes when you need to.
Walk with a friend. You're more likely to enjoy exercise, and stick to it, if you do it with someone else. Find a walking buddy and make a pledge to walk regularly. Your buddy could be your spouse or a neighbor -- or even your dog. If you know someone else, or something else, is counting on you, you're more likely to keep on track. It can push you to get and out and move when you might otherwise stay on the couch.

subset: commoncrawl


text:
2007 Ultimate
National Title
CFN's 9th Annual Ultimate
College Football Playoff
You want a playoff? You really want
a playoff? Is that what you need to satisfy your need for closure on who
the best team is? Fine, then forget about the regular season, and let's
just have one big playoff.
Once again here's the CFN Ultimate National Title, taking all the teams
and giving them a shot at the crown. This is a war of endurance as much as talent. Unlike
past years when we did it at the end of the season, we're doing it at
the beginning.
With 119 teams, there has to be three
brackets of 30 teams and
one of 29. The "strongest" of the No. 3 seeds, in this case,
UCLA, doesn't have to play a first round game. The higher seed gets the home game up until the semifinals. The seedings
are based on our CFN Preseason Rankings in an attempt to create the
fairest, most entertaining tournament possible. Yes, the geographical directions are names only.
Scroll down for all the seedings.
Miss State
Colorado State


text:
Win a Guitar Autographed by Kellie Pickler!
Here's your chance to win a guitar signed by country star Kellie Pickler! Just head over to our Facebook page to enter the contest.
Here's your chance to win a guitar signed by country star Kellie Pickler! Just head over to our Facebook page to enter the contest.
Over 200,000 followers of Jake Owen's page on Facebook could have gotten an eyeful this afternoon, as the 'Alone With You' singer's account was apparently hacked. Friends and fans hoping to catch a few glimpses from his tour or of his dog Merle instead got pictures of, well … use your imagination.
Whether you love or hate Twitter, the microblogging site has revolutionized online communication and some scientists are even using it to ascertain worldwide mood. Though, what they've found is kind of a bummer.
If you recently lost a slew of Facebook friends, it probably wasn't a glitch. Go back and look at your timeline because the chances are good it's your own fault.
That's what a new study from Nielsen seems to indicate anyway. The group surveyed about 2,000 adults to learn why Facebook users add and remove friends, and the results may surprise you.
After a few months in private trials, Facebook launched its Timeline feature to the masses on Thursday. In a nutshell, it lets you view people's photos and status updates from days long past instead of just showing you what they've done or posted most recently. Basically, it's the Facebook equivalent of being forced to look through your friends' childhood scrapbooks.
Intrigued? Here's what you need to know before taking the plunge.
Was Alec Baldwin striking a blow for the common air traveler when he refused to stop playing Words With Friends on his smart phone while his American Airline flight was awaiting takeoff? While his actions may seem justified to some, almost half of Americans think the cell phone rule should be honored.
Did you know that any message sent to you on Facebook which isn't from a friend or a friend of a friend gets filtered into an "other" subfolder?
Most people don't, and this means you probably have dozens of messages sitting on your Facebook page that you've never looked at before.
White girls. If you are on Facebook, there's a good chance you are friends with a whole bunch of them. Mary (a white girl herself) has been studying the social media habits of her Caucasian sisters, and has published a list of '15 of Things White Girls Love To Do On Facebook' on her blog Fibromy-Awesome.
Frustrations over Facebook's lax privacy policies have risen quite high in recent times, which makes the fact that someone was able to hack the social site and make public some of Mark Zuckerberg's private photos all the more satisfying.
A woman in Ireland is unable to list the name of her hometown on her Facebook profile because it's Effin, Ireland. Not "f***in' Ireland"… Effin, Ireland.
Comedian, radio personality and actor Patrice O'Neal passed away at the age of 41 on Monday night. He suffered a stroke in October and never returned to good health.
If you got rid of some of your Facebook friends on Jimmy Kimmel's 'National Unfriend Day,' you might be depressed or have second thoughts. William Shatner wants you to know that you're going to be OK.
In this clip from 'Jimmy Kimmel Live,' Shatner guides you through the steps on how to recover from the feelings of denial and fears of being alone that come with Facebook "un-friending."


text:
Putting you in control of ...
A comparative guide to bribery and corruption laws in a range of jurisdictions, covering public and private sector offences, corporate liability and extra-territorial application.
Read more
This microsite summarises the main types of employee incentive awards operated by UK companies and the main tax, legal and regulatory implications of operating them in the UK.
Putting you in control of:
Simmons & Simmons navigator is our sector-leading online service, currently covering the following four areas of regulation:
Registration is fast and free
Already registered? Log in here
Forgotten Password
28 May 2015
The TMT Regulatory Roundup provides a monthly summary of key telecoms related regulatory and legislative developments across the UK and the EU.
An ACM policy paper provides insight into its strategy and enforcement priorities with regard to vertical agreements between suppliers and buyers.
The much anticipated judgment in Mercuria Energy Trading v Citibank, regarding repo transactions over metal in Qingdao and Penglai, was recently delivered.
19 Dec 2013
In a welcome move, HM Treasury has announced that it will amend its AIFM Regulations to allow transitional AIFMs to submit their application for authorisation to the FCA up to 22 July 2014.
14 Nov 2014
Borsa Italiana has launched a new segment dedicated to trading of UCITS funds which will offer an alternative way for managers to make products available to investors in Italy.
13 Jul 2012
The EU Short Selling Regulation was published in the Official Journal on 24 March 2012 and came into force the day after. It introduces a pan European disclosure regime for net short positions in EEA listed shares and sovereign debt, as well as a ban on naked physical short sales of EEA listed shares and sovereign debt, and a ban on credit default swap positions in EEA sovereign debt which, broadly speaking, do not serve to hedge exposure to the underlying debt (so called naked CDS positions). The Regulation came into force on 25 March 2012, and its provisions will apply from 01 November 2012.
20 May 2015
Simmons & Simmons partner Richard Dyton talks to colleague Mia Showell-Woodsmith about best practice for dealing with dispute resolutions clauses.
15 May 2015
Simmons & Simmons partner Julian Taylor talks to fellow colleague Rebecca Lally about changes to employment law in England and Wales in April 2015.
13 May 2015
Simmons & Simmons associate Steffen Nguyen-Quang talks to fellow associate Sarah Paul about managing sickness in Germany.
© Simmons & Simmons LLP 2015. All rights reserved. Registered in England & Wales Registered Number OC352713
elexica Limited, CityPoint, One Ropemaker Street, London EC2Y 9SS T: +44 20 7628 2020


text:
Pagani Will End Zonda Production With 764 Passione
Like Us On Facebook
Like Us On Facebook
This information comes from a Teamspeed user, while GTSpirit is reporting that the car will get a manual gearbox. Zonda production will come to an end since the AMG engineers are not available anymore. This final car will be motivated by a V12 AMG M120 7.3-liter engine that produces 760 hp (566 kW), which is 20 hp (15 kW) more than the Zonda R and 90 hp (67 kW) more than the Zonda Cinque.


text:
Mum's Blast at Batman Film
AN ANTI-KNIFE campaigner today blasted the new Batman movie claiming it glamorised sadistic violence.
Barbara Dunne, 61, whose son Robert was murdered with a samurai sword in a Middlesbrough street, claimed The Dark Knight would send the wrong message to youngsters. And she vowed to contact the film's producers to complain about the glorification of blades.
The movie features bad-guy character the Joker – played by the late Heath Ledger – who is obsessed with knives.
Mrs Dunne, a Middlesbrough councillor, said The Dark Knight's 12A rating meant young children would be able to watch it if accompanied by an adult.
Mrs Dunne said: "I think the makers should have done research about how high knife crime is in other countries.
"We here are fighting knife crime and they release a movie like that. Kids are impressionable and imaginative. Films like that, along with video games, are re-enacted in a child's mind and in imaginary play. However, these days the kids use the weapons to re- enact with – they have a hard time separating the imaginary from reality."
Mrs Dunne's son Robert, 31, a father-of-one, bled to death in West Lane, Middlesbrough, after a samurai sword was plunged into his back.
Since then Robert's mum, of Stainsby Road, Whinney Banks, Middlesbrough, has campaigned tirelessly against the use of knives in today's society.
She said: "I feel that this movie will give an 'it's OK to carry a knife, it's OK to use a knife, you won't get punished', when we have been fighting for the opposite. Plus what value for human life does it portray? None. The critics might applaud it but what impression will it have on our kids?"
Mrs Dunne is to write to the film's producers to highlight her concerns.
She said: "I'm going to write to them and ask if they did any research into the knife crime going on in the UK. Did they not know there have been 21 stabbings since Christmas? Did they not stop and think that kids are very imaginative and could play act it out?"
(c) 2008 Evening Gazette – Middlesbrough. Provided by ProQuest Information and Learning. All rights Reserved.


text:
Gear Question
I have seen this harness with 2 different...
I have seen this harness with 2 different types of attachment point. One is just webbing, and the other is like the one shown above. Which one is the newer model?
Angus Bohanon
Backcountry carries the latest models of everything. The older ones are on SteepAndCheap or in the Outlet.
The new one is pictured here, but buyer beware! I'm a US citizen working as a canyon guide in New Zealand, and I went through a great deal of trouble to get this harness to me. Upon opening the box, I found that backcountry.com had sent me the old webbing loop model! It will now cost me more money than the harness is worth to send it back for the new model. I'm now what you call SOL. Don't let Backcountry.com mislead you too! Buy somewhere else!!
View More Details on Petzl Canyon Harness - Men's


text:
Bobcats awaken and advance | VIDEO
Refugio roars back against Schulenburg in second half
SAN ANTONIO - Corpus Christi-area teams are indeed going to remember the Alamodome after this weekend.
Refugio High School's top-ranked Bobcats provided the latest bit of come-from-behind drama Saturday night in the Region IV-2A Division II championship game.
Following the lead of their cohorts from Calallen 24 hours previously, Refugio exploded after halftime, blasting for 21 points in the first six-plus minutes of the third quarter.
Behind Terrence Smith's four-touchdown, 254-yard performance, the Bobcats continued their lethal quick strikes for 35 second-half points and a 42-28 victory over the No. 7 Shorthorns.
The 13-0 Bobcats advance to the state semifinals
for the second consecutive season and will face No. 2 Lexington. The 13-0 and District 12-2A champion Eagles posted their fifth shutout of the season, blanking third-ranked New London West Rusk 24-0 for the Region II championship Friday night in Hewitt. The semi is tentatively scheduled for the Berry Center in Cypress outside of Houston, although the game may be switched to the Alamodome. The Shorthorns' season ends at 12-1.
After a lackluster opening 24 minutes, Refugio struck and struck quickly, piling up 319 second-half yards, 260 rushing. It was a near carbon copy of the way Calallen rallied to beat Boerne 51-31 the night before in the Region IV-4A Division II title game. Four of Refugio's scoring drives lasted a total of five plays.
Draigon Silvas' 59-yard scoring pass on a halfback pass to Shiloh Whetsel kick-started the rally. After a three-and-out, Whetsel then returned the ensuing punt 54 yards, setting up Smith's game-tying 11-yard run. Four-plus minutes later after another three-and-out by Schulenburg, Refugio rolled 81 yards in eight plays to take its first lead of the night on Aaron Perez's 9-yard quarterback keeper.
The Shorthorns weren't finished. They regained possession after a questionable spot when Silvas was ruled short of the first down, giving the Shorthorns the ball on their 35. Kyle Bludau, who stinged Refugio for 291 passing yards, directed the 10-play drive that ended with Brandon Strickland's 2-yard run.
Back again came the Bobcats, who trailed at halftime (21-7) for the first time this season. They rolled 59 yards in five plays, capped by Smith's 15-yard run with 6 minutes, 3 seconds to play. After Marcus Thompson's interception of Bludau, Smith blasted 62 yards for his final score of the night, a 62-yarder at the 2:51 mark.
Bludau, Schulenburg's do-everything player, directed the final scoring drive of the night with his 19-yard pass to Ryan Havrda with 30 seconds to play.
Refugio's Justin Padilla recovered the ensuing onsides kick to preserve the win.
To say it was a ragged half for Refugio would be accurate. Numbers-wise, it appeared the Bobcats were able to move the ball on the ground. It was a deceiving 124 yards, though, considering Smith's 60-yard scoring run tied the game at 7.
Other than that, the Bobcats managed 68 yards on four possessions with two turnovers. Of more import, both of those Refugio miscues led to Schulenburg touchdowns.
Schulenburg, meanwhile, converted seven of nine on third-down conversions in the first half and had the ball for 17:54. The Shorthorns featured Bludau at nearly every turn in churning out a modest 202 yards of offense. Despite getting knocked around twice under center, he also took a hit late in the first half. He was able to walk off on his own and returned, nearly leading a fourth scoring drive after Refugio turned over the ball on downs. But a 12-yard sack of Bludau by Sean Dukes - the Refugio junior barely avoided an excessive celebrating penalty afterward - and a fourth-down incompletion left the Shorthorns with a 21-7 lead.
The Shorthorns cruised on their first possession, driving 80 yards for a 7-0 lead. They didn't need any third-down conversions in the seven-play drive. Bludau completed all four of his passes for 73 yards, with the final 37 going to Jacob Langhamer on a post pattern.
Refugio came back to tie the game two plays later when Smith busted through three tackles to complete the 60-yard run.
Both teams traded turnovers, with Malcom Franklin picking off Bludau. But the interception by Nolan Besetzny off Perez gave Schulenburg the ball at its 32 with 32 seconds to play in the first quarter. Three minutes and two third-down conversions later, Besetzny made a brilliant leaping catch of Bludau's pass for a 21-yard scoring play.
Bludau recovered Whetsel's fumble two scrimmage plays later at Schulenburg's 49. this time, the Shorthorns mainly stuck to the ground, picking up all but 11 yards on rushes to their third TD of the half. They also converted three third downs, with Bludau picking up the final one when he scored from the 1 on third-and-goal. His third PAT gave Schulenburg the 21-7 lead.
S — Jacob Langhamer 37 pass from Kyle Bludau (K. Bludau kick)
R — Terrence Smith 60 run (Cristian Padron kick)
S — Nolan Besetzny 21 pass from K. Bludau (K. Bludau kick)
S — K. Bludau 1 run (K. Bludau kick)
R — Shiloh Whetsel 59 pass from Draigon Silvas (Padron kick)
R — T. Smith 11 run (Padron kick)
R — Aaron Perez 9 run (Padron kick)
S — Brandon Strickland 2 run (K. Bludau kick)
R — T. Smith 15 run (Padron kick)
R — T. Smith 62 run (Padron kick)
S — Ryan Havrda 19 pass from K. Bludau (K. Bludau kick)
Schulenburg Refugio
First downs 26 18
Rushes-yards 38-106 37-384
Passes 22-46-2 3-6-1
Yards Passing 291 63
Punts 1-23.0 4-42.0
Fumbles-lost 0-0 1-1
Penalties-yards 2-25 7-81
RUSHING — Schulenburg, Strickland 16-75, K. Bludau 19-27, Langhamer 3-4. Refugio, T. Smith 16-254, Whetsel 8-65, Silvas 9-51, Cory Brown 1-7, A. Perez 2-12.
PASSING — Schulenburg, Bludau 22-46-2-291. Refugio, A. Perez 2-5-1-4, Silvas 1-1-0-59.
RECEIVING — Schulenburg, Logan Zabeda 3-37, Besetzny 4-54, Langhamer 7-107, Havrda 6-67. Refugio, T. Smith 1-(minus-2), Brown 1-6, Whetsel 1-59.
Subscribe to the Caller-Times
Need Help? Call us at 1-800-566-8098.
Monday-Friday: 5am-8pm / Saturday: 7am-12pm / Sunday: 6am-1pm


text:
China HGS Reports the Completion of Two Municipal Road Construction Projects
HANZHONG, China, March 24, 2014 /PRNewswire/ — China HGS Real Estate Inc. (NASDAQ: HGSH) ("China HGS" or the "Company"), a leading regional real estate developer headquartered in Hanzhong City, Shaanxi Province, China, today announced that the Hanzhong government accepted the delivery of the two municipal roads that were constructed by the Company on March 21, 2014.
In June 2012, the Company was approved by the Hanzhong local government to construct two municipal roads, namely Mingzhu Road West and Liuhou Road. The related construction was completed and the Hanzhong government performed its quality inspections and accepted these two roads on March 21, 2014. The final construction price for these two roads is approximately $3.16 million (RMB19, 483,589), which was approved by the Hanzhong Ministry of Finance.
Mr. Xiaojun Zhu, China HGS's Chairman and Chief Executive Officer, said, "We are proud that our team was selected for these two important municipal road construction projects as part of the Hanzhong City Urban Redevelopment Program. We successfully completed these projects on a timely basis. It is a new milestone for the Company, demonstrating our commitment to expand our business to the future of Hanzhong City."
Forward-looking Statements:
This press release contains certain statements that may include 'forward-looking statements'. All statements other than statements of historical fact included herein are 'forward-looking statements'. These forward looking statements are often identified by the use of forward-looking terminology such as 'believes,' 'expects' or similar expressions, involve known and unknown risks and uncertainties. Although the Company believes that the expectations reflected in these forward-looking statements are reasonable, they do involve assumptions, risks and uncertainties, and these expectations may prove to be incorrect. You should not place undue reliance on these forward-looking statements, which speak only as of the date of this press release. The Company's actual results could differ materially from those anticipated in these forward-looking statements as a result of a variety of factors, including those discussed in the Company's periodic reports that are filed with the Securities and Exchange Commission and available on its website http://www.sec.gov. All forward-looking statements attributable to the Company or persons acting on its behalf are expressly qualified in their entirety by these factors. Other than as required under the securities laws, the Company does not assume a duty to update these forward-looking statements.
About China HGS Real Estate, Inc.
China HGS Real Estate, Inc. (NASDAQ: HGSH), founded in 1995 and headquartered in Hanzhong City, Shaanxi Province, is a leading real estate developer in the region and holds the national grade I real estate qualification. The Company focuses on the development of high-rise, sub-high-rise residential buildings and multi-building apartment complexes in China's Tier 3 and Tier 4 cities and counties with rapidly growing populations driven by increased urbanization. The Company provides affordable housing with popular and modern designs to meet the needs of multiple buyer groups. The Company's development activity spans a range of services, including land acquisition, project planning, design management, construction management, sales and marketing, and property management. For further information about China HGS, please go to www.chinahgs.com.
Company contact:
Randy Xiong
President of Capital Market
China Phone: (86) 091-62622612
Email: firstname.lastname@example.com
SOURCE China HGS Real Estate Inc.


text:
Excellent addition to my hamburger hash
I make a hamburger hash with sliced potatoes, and these are great in the hash. When I buy regular potatoes, I usually end up throwing some of them in the trash because they go bad. No waste to these. FYI, here is my recipe for the hash - quick and good. Brown 1 lb. hamburger in a large skillet. Stir in 3 Tbls. flour. Add about 4 cups of water. Add 1 Tbl. onion powder, salt and pepper to taste. Add 3 large handfuls of potato slices that have been previously rehydrated. Stir occasionally and simmer until potato slices are tender and the mixture is to the consistency you prefer. Enjoy!
I Enjoy these
I enjoy these. Simple, yet filling and so many ways to cook them. Spice 'em the way you like 'em!
Good Value
Nice addition to storage.Can't beat the price.
Quality Product @ Great Price!
A great deal for a quality product! Just try to dehydrate your own vegetables and see how much time it takes and how costly it would be to fill a #10 can. One comes out way ahead purchasing freeze dried produce for the cost and diversity of uses. Easy to use, no worries about spoilage, is a great product for daily use or long time storage.
great taste, great value
These are great. They are cheap and taste as good as you want them to, just spice them however you like. These are a lot easier than dehydrating your own potatoes too.
Tastes great and amazing useful
This product is so amazing and can be used so many different ways and used with cheesey sauce makes great fast cheese potatoes and you don't have to go to the store and purchase potatoes at high prices.
potato slices
Great value. Great price. The whole family loved these.
Staple Product
If you're family is anything like mine, then it's meat and potatoes. And then more, meat and potatoes. The potato slices from the Ready Store is a quality product. I recently used it in a "meal in a jar" to make scalloped potatoes. The dish came out very well and the potatoes were as tender as I could have hoped for. This is a staple product that everyone should have in their stockpile. I highly recommend it.
I wasn't sure what to use these for at first, but have found they bulk up soups nicely. Easy to make crockpot casseroles with these on hand!
Important to have in kit.
This is great to have in your kit. You can add it to stews, hamburger, chicken or make has browns out of them. These are potatoes so they could be a tiny bit more affordable but you get them in a long lasting package that you don't need to worry about for years.


text:
The future of computing is constantly changing but as what can we look forward to at home, at work or on the road? PC Advisor investigates.
Print from anywhere
Forget about running home to print out your photos or ordering prints online. The next generation of mobile devices will come with their own built-in printers.
Zink 'zero ink¡' Imaging (click here for zink.com) is a spin-off from Polaroid that has been working on a new way of making photo paper. Zink paper has a crystal substrate sandwiched between its layers that colourises as it passes through a slim-profile printer. The printers themselves are so small that you can slip one in your pocket. They can easily be built into cameras, laptops or other devices.
In 2008, Zink plans to partner with a major camera vendor to release the first pocket-sized digital camera with a built-in printer. This early model will produce 2x3in photos. At the same time, the company will begin selling a handheld printer (costing in the region of £50) for cameraphones; it'll print adhesive-backed photos that may well grace many schoolchildren's folders and pencil cases. Two or three years after that, the technology may be integrated into laptops and other mobile devices.
Zero Ink prints your snaps on paper directly from a mobile phone or digital camera
Great graphics inside
'Integrated graphics' has long been synonymous with 'sluggish graphics¡'. Soon the phrase will have a whole new meaning, thanks to new computers with powerful graphics hardware built in.
AMD's (click here for AMD.com) acquisition of ATI brought the company's rivalry with Intel (Intel.com) - which already made its own basic graphics chips - to a new level. Since then, the two competitors have each worked to bridge the gap between central processing units (CPUs) and graphics processing units (GPUs).
Building graphics-processing functionality directly into a CPU eliminates the delay you'd otherwise experience as data passes between the CPU and GPU across the system bus. Such combined CPU/GPUs will feature DirectX 10.0 support and acceleration for Blu-ray Disc and HD DVD, while consuming substantially less power, requiring less space on the motherboard and performing significantly better than most of today's discrete graphics cards.
Intel plans to put its graphics-integrated Nehalem processors into production in 2008, beginning with a line of server chips. AMD intends to release its integrated Puma laptop platform around the same time. In 2009, Intel will bring its graphics-integrated chips to desktops and notebooks, while AMD's Puma should reach desktops in 2010.
Flexible screens
flexible screens can be bent into any shape and used anywhere
The smaller and more powerful devices become, the harder they are to use. Tiny screens just don't cut it when you want to do real work. But if your phone or PDA came with a large rollout display, you could work in comfort without sacrificing portability. That's where flexible polymers come in.
Display manufacturers make traditional LCD screens by sandwiching liquid crystals between layers of glass and then zapping them with electricity. Replacing that glass with plastic makes things more malleable.
Initially developed by E Ink (eink.com, click here) and Philips (philips.com), electronic paper compresses organic light-emitting diode (or Oled) crystals between very thin layers of polymer, allowing for tremendous flexibility.
Unlike conventional LCD screens, such ultra-thin displays are completely shatterproof, and can even be rolled up into tight spools. The result is a widescreen monitor that you can carry in your pocket and use anywhere. Better still, such screens will be cheaper and easier to manufacture than today's flat panels - they'll simply be printed directly on to sheets of plastic.
The first flexible displays are already here - they're just not that flexible yet. E Ink's electronic paper can be found in such non-flexible products as the Sony Reader (Sony.co.uk) and the Motorola Motofone F3 (motorola.co.uk).
The first rollable displays, created in the labs at Philips spin-off Polymer Vision (polymervision.com), will reach the market in 2008 - a mobile phone from Telecom Italia will carry the world's first Polymer Vision roll-up display. Currently under wraps, the phone is expected to offer a 5in, 320x40 pixel, monochrome rollable display. By 2010, Polymer Vision expects to market larger colour displays with much higher resolution.
NEXT PAGE: pocket presentations > >


text:
They had been set up to track wildlife movement in one of the most densely forested biological hotspots in Maharashtra. Officials in the state forest department were, however, surprised to see animals, albeit the two-legged kind, netted by the camera traps set up in the Tillari area of Sindhudurg's Dodamarg taluka.
In a first-of-its-kind occurrence, camera traps laid near Kendre village to track wildlife secretly photographed a gang of poachers who had allegedly killed a Sambar. Forest officials managed to track down six offenders and nabbed them with an unlicensed gun in their hand.
MK Rao, chief conservator of forests (CCF), Kolhapur range, told dna that the department had set up the cameras to track wild animals. "However, the camouflaged cameras clicked poachers sitting before it. We could identify six people, and they have been arrested," said Rao, adding that this was the first time these traps had helped nab poachers. They are all locals. Officials also recovered Sambar meat and an unlicensed, country-made gun which had been used to kill the deer.
Tillari is on Maharashtra's border with Goa and Karnataka, and boasts thick forest cover teeming with wildlife like leopards, elephants, tigers and gava (Indian bison).
Rao said apart from detecting poachers, these camera traps would help monitor all that happens in the jungle. "The forest department has been monitoring the movement of poachers in the jungles with these cameras, and now we have results. So, deterrence is ensured," added Rao.
A forest department official said earlier this month when an employee had gone to retrieve the cameras set up at a village near Tillari dam, he saw some people running away. They also dropped some Sambar meat that was in their possession. The cameras had captured some of these poachers, one of whom was holding a gun. The accused were arrested after inquiries were made in the nearby villages, and they have confessed to their crime.