Two regularized estimators that avoid the pathologies associated with variance estimation are disclosed. The regularized variance estimator adds a contribution to estimated variance representing the likely error, and hence ameliorates the pathologies of estimating small variances while at the same time allowing more reliable estimates to be balanced in the convex combination estimator. The bounded variance estimator employs an upper bound to the variance which avoids estimation pathologies when sampling probabilities are very small.

Traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths or trajectories followed by packets between any ingress and egress point of the domain. A method of sampling packet trajectories in a packet switching network allows the direct inference of traffic flows through a measurement domain by observing the trajectories of a subset of all packets traversing the network. A method which assumes that the measurement domain does not change comprises the steps of selecting packets for sampling in accordance with a sampling function of the packet content and generating a practically unique label for each sampled packet. The method does not rely on routing state, its implementation cost is small, and the measurement reporting traffic is modest and can be controlled precisely. Using the same hash function will yield the same sample set of packets in the entire domain, and enables us to reconstruct packet trajectories. An alternate embodiment which assumes no constraints and that the measurement domain may change comprises the steps of applying a sampling function and altering an invariant bit position as a signaling flag in each packet selected for sampling.

An efficient streaming method and apparatus for detecting hierarchical heavy hitters from massive data streams is disclosed. In one embodiment, the method enables near real time detection of anomaly behavior in networks.

The present invention provides apparatus for sampling data flows in a data network in order to estimate a total data volume in the network. Sampling the data flows in the data network reduces the network resources that must be expended by the network to support the associated activity. The present invention enables the service provider of the data network to control sampled volumes in relation to the desired accuracy. The control can be either static or can be dynamic for cases in which the data volumes are changing as a function of time.

A method and apparatus for the estimation of traffic matrices in a network are disclosed. Mechanisms are disclosed for measuring traffic volume from a plurality of ingress points to a plurality of egress points in a large scanl network, such as an IP backbone network. The traffic matrix is advantageously inferred from widely available link load measurements such as SNMP data.

The invention provides apparatus and methods for a Virtual Private Network (VPN) in a network that offers a simple user interface for efficient utilization of network resources. The VPN is defined for a specified set of endpoints each of which is associated with a single hose. A hose provides access to the VPN through an access point which may be a node of the network, for example. The hose is a single interface to the VPN for communication to all other endpoints of the VPN. The VPN achieves network resource allocation efficiency by exploiting resource sharing possibilities via multiplexing routing paths between endpoints and dynamic resource allocation techniques that permit real time resource allocation resizing. When a VPN is established with a VPN service provider, the routing paths between the endpoints of the VPN is optimized for multiplexing opportunities so that resource allocations between nodes along routing paths within the IP network is reduced to a minimum.

The present invention provides a method and apparatus for sampling data flows in a data network in order to estimate a total data volume in the network. Sampling the data flows In the data network reduces the network resources that must be expended by the network to support the associated activity. The present Invention enables the service provider of the data network to control sampled volumes in relation to the desired accuracy. The control can be either static or can be dynamic for cases in which the data volumes are changing as a function of time

The invention provides apparatus and methods for a Virtual Private Network (VPN) in a network that offers a simple user interface for efficient utilization of network resources. The VPN is defined for a specified set of endpoints each of which is associated with a single hose. A hose provides access to the VPN through an access point which may be a node of the network, for example. The hose is a single interface to the VPN for communication to all other endpoints of the VPN. The VPN achieves network resource allocation efficiency by exploiting resource sharing possibilities via multiplexing routing paths between endpoints and dynamic resource allocation techniques that permit real time resource allocation resizing. When a VPN is established with a VPN service provider, the routing paths between the endpoints of the VPN is optimized for multiplexing opportunities so that resource allocations between nodes along routing paths within the IP network is reduced to a minimum.

Traffic measurement should make it possible to obtain the spatial flow of traffic through the domain, i.e., the paths or trajectories followed by packets between any ingress and egress point of the domain. A method of sampling packet trajectories in a packet switching network allows the direct inference of traffic flows through a measurement domain by observing the trajectories of a subset of all packets traversing the network. A method which assumes that the measurement domain does not change comprises the steps of selecting packets for sampling in accordance with a sampling function of the packet content and generating a practically unique label for each sampled packet. The method does not rely on routing state, its implementation cost is small, and the measurement reporting traffic is modest and can be controlled precisely. Using the same hash function will yield the same sample set of packets in the entire domain, and enables us to reconstruct packet trajectories. An alternate embodiment which assumes no constraints and that the measurement domain may change comprises the steps of applying a sampling function and altering an invariant bit position as a signaling flag in each packet selected for sampling.

Apparatus for routing packets in a communication network comprises a plurality of per-connection queues, each queue established for receiving packets from a respective source and temporarily storing received packets before routing to a particular destination; a weighted fair-queuing scheduler for servicing packets from each of the plurality of per-connection queues at guaranteed pre-allocated rates; a sensing device for sensing a presence or absence of packets in queues, the absence of packets in queues indicating availability of excess bandwidth; and, a state dependent scheduler for redistributing excess bandwidth upon sensing of queues absent packets, the state dependent scheduler servicing those queues in accordance with a state variable corresponding to a performance property of the queues, wherein delay and isolation properties for routing packets of respective queues in weighted fair-queuing is preserved.

A method and apparatus provide a smoothing and rate adaptation algorithm to facilitate the flow of video data, maintaining video quality while avoiding potentially harmful buffering delays. The invention uses a smoothing interval to determine a rate to request for allocation. The invention also adapts the encoding rate in relation to a target delay for a source buffer.