Dynamically detecting topology and egress nodes in communication networks

• US 7,318,105 B1
• Filed: 03/11/2003
• Issued: 01/08/2008
• Est. Priority Date: 03/11/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Original Assignee: BBN Technologies Corporation (Rtx Corporation)
• Inventors: Cousins, David Bruce, Bongiovanni, Kevin Paul
• Primary Examiner(s): Walsh, John B.
• Application Number:
  US10/385,782
• Time in Patent Office: 1,764 Days
• Field of Search: None
• US Class Current: 709/238
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A method of determining routing information among nodes [210] in a network [200] may include obtaining a set of times of arrival [410] and corresponding source nodes [420] for chunks of data in the network [200] and assigning weights to a set of chunks of data [520-550] based on respective times between the set of chunks of data [520-550] and one chunk of data [510]. A set of routing information [600/800] among the nodes in the network [200] may be updated based on the assigned weights.

Claims

1. A method of determining topology of a network, comprising:

obtaining a data set including times of arrival, durations, and source nodes for chunks of data in the network;

identifying most recent chunks of data arriving from source nodes other than a source node of interest in which arrival times of the most recent chunks occur before a chunk arrival time associated with the source node of interest;

calculating weights for the other source nodes based on time differences between the chunk arrival time associated with the source node of interest and the most recent chunks of data;

updating a probability matrix based on the weights for the other source nodes;

repeating the identifying, calculating, and updating for other times of arrival and associated source nodes of interest in the data set;

determining the topology of the network from the probability matrix; and

outputting the topology of the network.

2. The method of claim 1, wherein the network is a wireless network.

3. The method of claim 1, wherein the identifying includes:

determining one most recent chunk of data for each of the other source nodes.

4. The method of claim 1, wherein the calculating includes:

determining the time differences based on ending times of the most recent chunks of data.

5. The method of claim 4, wherein the ending times are determined from respective times of arrival and durations of the most recent chunks of data.

6. The method of claim 1, wherein the calculating includes:

calculating the weights using a function of time whose value generally decreases with increasing time.

7. The method of claim 6, wherein the function is a monotonically decreasing function of time.

8. The method of claim 1, wherein the updating includes:

normalizing the weights to obtain a set of probabilities for the other source nodes.

9. The method of claim 1, wherein the determining includes:

applying a threshold function to the probability matrix.

10. The method of claim 1, further comprising:

finding egress nodes in the network from the probability matrix.

11. A method of determining routing information among nodes in a network, comprising:

obtaining a set of times of arrival and corresponding source nodes for chunks of data in the network;

determining intervening times between one chunk of data from one node and recently arriving chunks of data from other nodes;

generating routing probabilities between the one node and the other nodes using the intervening times; and

outputting the routing probabilities.

12. The method of claim 11, wherein the determining includes:

determining the intervening times between the one chunk of data and one most recent chunk of data for each of the other nodes.

13. The method of claim 11, wherein the obtaining includes:

obtaining durations of the chunks of data in the network.

14. The method of claim 13, wherein the determining includes:

calculating the intervening times based on the times of arrival and the durations of the most recent other chunks of data from the other nodes.

15. The method of claim 11, wherein the generating includes:

assigning weights to respective other nodes, the weights varying inversely to respective intervening times associated with the respective other nodes.

16. The method of claim 15, wherein the weights decrease exponentially with increasing intervening time.

17. The method of claim 11, wherein the generating further includes:

normalizing the assigned weights to generate the routing probabilities.

18. A method of determining routing information among nodes in a network, comprising:

obtaining times of arrival and corresponding source nodes for chunks of data in the network;

assigning weights to a set of chunks of data based on respective time differences between the set of chunks of data and one chunk of data;

updating a set of estimated routing information among the nodes in the network based on the assigned weights; and

outputting the updated estimated routing information.

19. The method of claim 18, wherein the respective times are measured from ends of respective chunks of data in the set and a time of arrival of the one chunk of data.

20. The method of claim 18, further comprising:

choosing a new chunk of data as the one chunk of data; and

repeating the assigning weights and updating a set of routing information for the new chunk of data.

21. A computer-readable medium that stores instructions executed by one or more processors to perform a method for determining routing information among nodes in a network, comprising:

instructions for obtaining a set of times of arrival and corresponding source nodes for chunks of data in the network;

instructions for assigning weights to a set of chunks of data based on respective time differences between the set of chunks of data and one chunk of data; and

instructions for updating a set of routing information among the nodes in the network based on the assigned weights.