Peer-to-peer based network performance measurement and analysis system and method for large scale networks

• US 7,194,002 B2
• Filed: 02/01/2002
• Issued: 03/20/2007
• Est. Priority Date: 02/01/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Qian, Zhu, Wenwu, Liu, Jiangchuan, Zhang, XinYan
• Primary Examiner(s): To; Doris H.
• Assistant Examiner(s): Hoang; Thai
• Application Number:
  US10/061,481
• Publication Number:
  US 20030147386A1
• Time in Patent Office: 1,873 Days
• Field of Search: 370254-258, 370400-410, 370/422, 370424-425, 709208-211, 709/249, 709223-224
• US Class Current: 370/400
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/12 Network monitoring probes

Abstract

A network performance (e.g., latency and bandwidth) measurement infrastructure for large scale networks based on self-organized probing groups of devices. Each group of devices has a lead device that measures network characteristics, and then shares the measurement information with other devices. This grouping method reduces the amount of network bandwidth needed for adequate measurements, while still providing necessary information to individual devices. The system utilizes a novel multicast-based algorithm that is adopted for both intra-group and inter-group performance measurement. The measurement groups (MeGroups) are dynamic and self-forming, and use a set of heuristic algorithms to optimize the dynamic groupings.

Claims

1. A network performance measurement infrastructure for large scale networks having a number of hosts dispersed throughout the network, comprising a plurality of measurement groups self organized from nearby hosts, each measurement group containing a group leader, each group leader joining a first multicast group to share inter-group network performance information between measurement groups, each group leader further forming a second multicast group within its measurement group to share intra-group network performance information within that measurement group;

wherein a given measurement group will merge with a nearby measurement group to increase efficiency when determining network performance through shared network performance information.

2. The infrastructure of claim 1, wherein the measurement groups dynamically reform as hosts enter and leave the network, or the network conditions vary.

3. The infrastructure of claim 2, wherein the group leader of a dynamically reformed measurement group is a host who is located at approximately the logical center of the dynamically reformed measurement group.

4. The infrastructure of claim 3, wherein hosts in a measurement group leave that measurement group to join the dynamically reformed measurement group when the group leader of the dynamically reformed measurement group is closer to the host than its current group leader.

5. The infrastructure of claim 2, wherein the group leader of the measurement group before the measurement group dynamically reformed calculates the distance between all hosts within measurement group after the dynamic reformation, the group leader thereafter requesting a host at a logical center of the measurement group after the dynamic reformation to assume a role of group leader.

6. A network performance measurement infrastructure for large scale networks having a number of hosts dispersed throughout the network, comprising a plurality of measurement groups self organized from nearby hosts, each measurement group containing a group leader, each group leader joining a first multicast group to share inter-group network performance information between measurement groups, each group leader further forming a second multicast group within its measurement group to share intra-group network performance information within that measurement group;

wherein each host shares within its respective measurement group any network performance information that it has relative to remote hosts, and wherein hosts within each measurement group utilize the network performance information shared within its respective measurement group to estimate network performance to the remote hosts without actively measuring the network performance.

7. The infrastructure of claim 6, wherein one host within a measurement group initiates an intra-group performance measurement by multicasting a packet to the second multicast group, each host within the group responding by multicasting a response to the packet to the second multicast group, thereafter the one host calculating the round trip time (RTT) performance between itself and all other hosts within its measurement group.

8. The infrastructure of claim 7, wherein the hosts within the measurement group further multicast information relating to the packet received from the one host and to the responses received from each host from the second multicast group, the hosts thereafter calculating the RTT performance between any two hosts within their measurement group.

9. A network performance measurement infrastructure for large scale networks having a number of hosts dispersed throughout the network, comprising a plurality of measurement groups self organized from nearby hosts, each measurement group containing a group leader, each group leader joining a first multicast group to share inter-group network performance information between measurement groups, each group leader further forming a second multicast group within its measurement group to share intra-group network performance information within that measurement group;

wherein each group leader shares any network performance information that it has relative to remote hosts with group leaders of nearby measurement groups, and wherein hosts within each measurement group utilize the network performance information shared from nearby measurement groups to estimate network performance to the remote hosts without actively measuring the network performance when no such network performance information is available from another host within that hostts measurement group.

10. The infrastructure of claim 9, wherein a host actively measures the network performance to a remote host when no such network performance information is shared from within the measurement group and from nearby measurement groups.

11. A network performance measurement infrastructure for large scale networks having a number of hosts dispersed throughout the network, comprising a plurality of measurement groups self organized from nearby hosts, each measurement group containing a group leader, each group leader joining a first multicast group to share inter-group network performance information between measurement groups, each group leader further forming a second multicast group within its measurement group to share intra-group network performance information within that measurement group;

wherein a host sends a packet train to a remote host to determine the network performance thereto, the packet train including two small synchronize (SYN) packets followed by two large SYN packets followed by two small SYN packets.

12. The infrastructure of claim 11, wherein the host receives a response packet train of reset (RST) packets from the remote host, the host discarding the response packet train when the RST packets are reordered relative to the SYN packets.

13. The infrastructure of claim 11, wherein the host receives a response packet train of six reset (RST) packets from the remote host, the host discarding the response packet train when a time dispersion between third and fourth RST packets is shorter than time dispersions between first and second, and fifth and sixth packets.

14. A network performance measurement infrastructure for large scale networks having a number of hosts dispersed throughout the network, comprising a plurality of measurement groups self organized from nearby hosts, each measurement group containing a group leader, each group leader joining a first multicast group to share inter-group network performance information between measurement groups, each group leader further forming a second multicast group within its measurement group to share intra-group network performance information within that measurement group;

wherein a host weights network performance information inversely based on a distance between itself and another host from which the network performance information is shared.

15. A method of determining network performance for a large scale network having a plurality of hosts distributed throughout the network, comprising the steps of:

forming at least one measurement group from nearby hosts;

within each of the at least one measurement groups, multicasting by one host a packet to other hosts in its associated measurement group to determine intra-group network performance;

multicasting by the other hosts in the measurement group to the hosts in that measurement group a response to the packet;

calculating by the one host the round trip time (RTT) performance between itself and all other hosts within that measurement group;

multicasting by the other hosts within the at least one measurement group information relating to the packet received from the one host and relating to the is responses received from each of the other hosts; and

calculating, by each of the other hosts, the RTT performance between any two hosts within their measurement group.

16. A method of determining network performance for a large scale network having a plurality of hosts distributed throughout the network, comprising the steps of:

forming at least one measurement group from nearby hosts;

within each of the at least one measurement groups, multicasting by one host a packet to other hosts in its associated measurement group to determine intra-group network performance;

multicasting by the other hosts in the measurement group to the hosts in that measurement group a response to the packet;

calculating by the one host the round trip time (RTT) performance between itself and all other hosts within that measurement group;

wherein the step of forming at least one measurement group comprises the steps of;

joining a first multicast group;

sending a request message to the first multicast group, the request message having a large time to live (TTL);

forming a new measurement group when no response is received within a predetermined latency;

assuming a role of leader of the new measurement group; and

forming a second multicast group for intra-group communication.

17. The method of claim 16, further comprising the steps of:

receiving a multicast request message from a new host;

responding to the request message;

receiving new host information multicast from the new host on the second multicast group; and

replying to the new host on the second multicast group.

18. The method of claim 17, further comprising the steps of:

calculating, by the group leader, a distance between each host the measurement group;

determining which host in the measurement group is the logical center of the measurement group; and

requesting that the host which is the logical center of the measurement group assume the role of group leader.

19. A method of determining network performance for a large scale network having a plurality of hosts distributed throughout the network, comprising the steps of:

forming at least one measurement group from nearby hosts;

within each of the at least one measurement groups, multicasting by one host a packet to other hosts in its associated measurement group to determine intra-group network performance;

multicasting by the other hosts in the measurement group to the hosts in that measurement group a response to the packet;

calculating by the one host the round trip time (RTT) performance between itself and all other hosts within that measurement group;

determining by one host in a measurement group network performance between itself and a remote host; and

multicasting the network performance to the other hosts in its associated measurement group for use by the other hosts in the measurement group to estimate the network performance to the remote host without actively communicating with the remote host.

20. The method of claim 19, further comprising the step of multicasting to group leaders of nearby measurement groups the network performance to the remote host for use by the nearby measurement groups to estimate the network performance to the remote host without actively communicating with the remote host.

21. The method of claim 19, wherein the step of determining by one a host in a measurement group network performance between itself and a remote host comprises the steps of:

transmitting a packet train of synchronize (SYN) packets to the remote host; and

analyzing a return packet train of reset (RST) packets from the remote host.

22. The method of claim 21, wherein the step of transmitting comprises the step of transmitting a packet train of six SYN packets including two small SYN packets followed by two large SYN packets followed by two small SYN packets.

23. The method of claim 21, wherein the step of analyzing comprises the steps of analyzing an ordering of the RST packets, and discarding the RST packet train when the RST packets have been reordered relative to the SYN packets.

24. The method of claim 21, wherein the step of analyzing is comprises the steps of analyzing time dispersion between RST packets, and discarding the RST packet train when at least one of the time dispersions between a first and a second RST packet, and a fifth and a sixth RST packet is not less than a time dispersion between a third and a fourth RST packet.

25. A method of determining network performance for a large scale network having a plurality of hosts distributed throughout the network, comprising the steps of:

forming at least one measurement group from nearby hosts;

within each of the at least one measurement groups, multicasting by one host a packet to other hosts in its associated measurement group to determine intra-group network performance;

multicasting by the other hosts in the measurement group to the hosts in that measurement group a response to the packet;

calculating by the one host the round trip time (RTT) performance between itself and all other hosts within that measurement group;

wherein the step of forming at least one measurement group comprises the step of merging a given measurement group into a nearby measurement group.

26. A method of determining network performance for a large scale network having a plurality of hosts distributed throughout the network, comprising the steps of:

forming at least one measurement group from nearby hosts;

within each of the at least one measurement groups, multicasting by one host a packet to other hosts in its associated measurement group to determine intra-group network performance;

multicasting by the other hosts in the measurement group to the hosts in that measurement group a response to the packet;

calculating by the one host the round trip time (RTT) performance between itself and all other hosts within that measurement group;

wherein the step of forming at least one measurement group comprises the step of disbanding a given measurement group so that the hosts therein may join a nearby measurement group.