Detecting interfering packet streams in packet networks
View Patent ↗A method for estimating the network-layer topology of a telecommunications network is described. In particular, the illustrative embodiment of the present invention estimates the existence and connectivity of nodes in the topology based on the detection of network-wide end-to-end path intersections. This is based on the assumption that pairs of streams of packets that share a common node will interfere and that the interference can be detected in the received streams. In general, this interference is manifested as jitter. By transmitting streams on each pair of end-to-end paths in the network, and detecting interference (or a lack of interference) a matrix of path intersections for the network can be created. Using logic and supposition, the topology of the network can be estimated using the matrix of path intersections. Once the estimate of the topology is complete, the maintenance and operation of the network can proceed based on the topology.
1. A method comprising:
receiving, by a first node n 1 in a packet network, a first stream of packets;
generating, by the first node n 1 , a jitter pattern based on the first stream of packets, wherein the jitter pattern comprises one or more temporally-shifted packets, and wherein generating the jitter pattern comprises:
(1) identifying the one or more temporally-shifted packets in the first stream of packets,
(2) grouping the one or more temporally-shifted packets that are within E seconds of one another into m groups, wherein m is a positive integer and E is a real number, and
(3) computing the m−1 inter-group intervals to generate the jitter pattern;
comparing, by the first node n 1 , the jitter pattern to a temporal pattern; and
transmitting a packet in the packet network to transit at least one of:
(a) a second node n 2 and not transit a third node n 3 when the jitter pattern corresponds to the temporal pattern; and
(b) the third node n 3 and not transit the second node n 2 when the jitter pattern fails to correspond to the temporal pattern.
2. The method of claim 1 wherein the temporal pattern comprises k bursts at k−1 inter-burst intervals; and
wherein comparing the jitter pattern to the temporal pattern comprises comparing m to k; and
wherein k is a positive integer.
3. The method of claim 1 wherein the temporal pattern comprises k bursts at k−1 inter-burst intervals; and
wherein comparing the jitter pattern to the temporal pattern comprises comparing the m−1 inter-group intervals to the k−1 inter-burst intervals;
wherein k is a positive integer.
4. The method of claim 1 wherein the temporal pattern is periodic.
5. The method of claim 1 wherein the temporal pattern is aperiodic.
6. A method comprising:
receiving a first stream of packets from a packet network;
analyzing the first stream of packets, wherein analyzing the first stream of packets comprises:
(a) identifying one or more temporally-shifted packets in the first stream of packets,
(b) grouping the one or more temporally-shifted packets that are within E seconds of one another into m groups, and
(c) computing the m−1 inter-group intervals to generate a jitter pattern;
comparing m to an expected value of k; and
transmitting a packet in the packet network to:
(a) transit a first node n 1 and not transit a second node n 2 when m ε {k−Δ, . . . ,k , . . . , k−Δ}; and
(b) transit the second node n 2 and not transit the first node n 1 when m ∉ 0 {k−Δ, . . . ,k , . . . , k−Δ};
wherein k and m are positive integers, E is a real number, and Δ is an integer.
7. The method of claim 6 wherein k is the number of bursts in a temporal pattern that comprises k−1 inter-burst intervals; and
wherein the first stream of packets comprises m groups of temporally-shifted packets at m−1 inter-group intervals; and
further comprising:
comparing the k−1 inter-burst intervals to the m−1 inter-group intervals.
8. The method of claim 6 wherein the m−1 inter-group intervals are equal.
9. The method of claim 6 wherein the m−1 inter-group intervals are not all equal.
10. A method comprising:
receiving a first stream of packets from a packet network;
identifying a plurality of temporally-shifted packets in the first stream of packets by calculating a temporal shift z i for each packet i in the first stream of packets, wherein z i =(tr i −tr (i−1) ) −(ts i −ts (i−1) ), and wherein:
(a) z i is a real number,
(b) i is a positive integer,
(c) ts i and tr i are times in which each packet i is transmitted by a first node n 1 and received b a second node n 2 respectively,
(d) ts (i−1) and tr (i−1) are times in which each (i−1) packet is transmitted by the first node n 1 and received by the second node n 2 , respectively;
grouping based on the temporal shift z i calculated for each packet i, the temporally-shifted packets in the first stream of packets that are within E seconds of one another into m groups;
comparing m to an expected value of k; and
transmitting a packet in the packet network to:
(a) transit a third node n 3 and not transit a fourth node n 4 when m ε {k−Δ, . . . ,k , . . . , k+Δ}; and
(b) transit the fourth node n 4 and not transit the third node n 3 when m ∉ {k−Δ, . . . ,k , . . . , k+Δ};
wherein k and m are positive integers, Δ is an integer, and E is a real number.
11. The method of claim 10 wherein k is the number of bursts in a temporal pattern that comprises k−1 inter-burst intervals; and
wherein the first stream of packets comprises m groups of temporally-shifted packets at m−1 inter-group intervals; and
further comprising:
comparing the k−1 inter-burst intervals to the m−1 inter-group intervals.
12. The method of claim 10 wherein the m−1 inter-group intervals are equal.
13. The method of claim 10 wherein the m−1 inter-group intervals are not all equal.