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

• US 20030147386A1
• Filed: 02/01/2002
• Published: 08/07/2003
• 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, Zhang, XinYan, Liu, Jiangchuan
• Granted Patent: US 7,194,002 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• 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

2. The infrastructure of claim 1, 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.

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.

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

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 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.

18. The method of claim 16, 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.

19. The method of claim 18, 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.

20. The method of claim 19, 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.

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

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.

22. The method of claim 21, 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.

23. The method of claim 21, 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 SYN packets to the remote host; and

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

24. The method of claim 23, 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.

25. The method of claim 23, 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.

26. The method of claim 23, wherein the step of analyzing 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 paclet, and a fifth and a sixth RST packet is not less than a time dispersion between a third and a fourth RST packet.

27. The method of claim 16, wherein the step of forming at least one measurement group comprises the step of merging a small measurement group into a nearby measurement group.

28. The method of claim 16, wherein the step of forming at least one measurement group comprises the step of disbanding a small measurement group so that the hosts therein may join a nearby measurement group.

29. In a large scale network having a first plurality of hosts organized into a second plurality of measurement groups, each measurement group having a group leader belonging to a first multicast group for inter-group communications between group leaders of the second plurality of measurement groups, and to a second multicast group for intra-group communications between hosts within the group leader'"'"'s measurement group, a method of searching for a nearby measurement group to join, comprising the steps of:

joining the first multicast group;

multicasting a request message having a large time to live;

when a reply is received from a nearby measurement group within a predetermined latency,

leaving the first multicast group, and

joining the nearby measurement group.

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.

5. The infrastructure of claim 1, 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 host'"'"'s measurement group.

6. The infrastructure of claim 5, 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.

7. The infrastructure of claim 1, wherein a host sends a packet train to a remote host to determine the network performance thereto, the packet train including two small SYN packets followed by two large SYN packets followed by two small SYN packets.

8. The infrastructure of claim 7, wherein the host receives a response packet train of RST packets from the remote host, the host discarding the response packet train when the RST packets are reordered relative to the SYN packets.

9. The infrastructure of claim 7, wherein the host receives a response packet train of six 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.

10. The infrastructure of claim 1, 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.

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

12. The infrastructure of claim 11, 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.

13. The infrastructure of claim 12, 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.

14. The infrastructure of claim 11, 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.

15. The infrastructure of claim 1, wherein a small measurement group will merge with a nearby measurement group to increase efficiency determining network performance through shared network performance information.

30. The method of claim 29, wherein the step of joining the nearby measurement group comprises the steps of:

joining the second multicast group of the nearby measurement group;

multicasting host information on the second multicast group; and

receiving replies from other hosts in the nearby measurement group on the second multicast group.

31. The method of claim 29, further comprising the steps of forming a new measurement group when no reply is received from a nearby measurement group with the predetermined latency, and assuming a role of group leader for the new measurement group.

32. The method of claim 29, further comprising the steps of:

receiving a first reply from a first nearby measurement group within the predetermined latency;

receiving a second reply from a second nearby measurement group; and

determining a closer of the first and the second nearby measurement groups; and

joining the closer of the first and the second nearby measurement groups.

32-1. The method of claim 29, further comprising the steps of:

receiving a first reply from a first nearby measurement group within the predetermined latency;

receiving a second reply from a second nearby measurement group; and

determining a closer of the first and the second nearby measurement groups; and

joining the closer of the first and the second nearby measurement groups.

33. In a large scale network having at least a first measurement group having a first group leader and a second measurement group, a method of changing group membership of a host in the first measurement group, comprising the steps of:

receiving a message from a new group leader of the second measurement group; and

joining the second measurement group when the new group leader is nearer than the first group leader.

3. The infrastructure of claim 1, 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.

4. The infrastructure of claim 3, 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.

34. The method of claim 33, wherein the step of joining the second measurement group when the new group leader is nearer than the first group leader comprises the steps of:

calculating a first distance estimate to the first group leader of the first measurement group;

calculating a second distance estimate to the new group leader of the second measurement group; and

joining the second measurement group when the second distance estimate to the new group leader of the second measurement group is less than the first distance estimate to the first group leader of the first measurement group.

35. The method of claim 33, wherein the step of joining the second measurement group when the new group leader is nearer than the first group leader comprises the steps of:

calculating a first distance estimate to the first group leader of the first measurement group;

33-2. In a large scale network having at least a first measurement group having a first group leader and a second measurement group, a method of changing group membership of a host in the first measurement group, comprising the steps of:

receiving a message from a new group leader of the second measurement group; and

joining the second measurement group when the new group leader is nearer than the first group leader.

34-3. The method of claim 33, wherein the step of joining the second measurement group when the new group leader is nearer than the first group leader comprises the steps of:

calculating a first distance estimate to the first group leader of the first measurement group;

calculating a second distance estimate to the new group leader of the second measurement group; and

joining the second measurement group when the second distance estimate to the new group leader of the second measurement group is less than the first distance estimate to the first group leader of the first measurement group.

35-4. The method of claim 33, wherein the step of joining the second measurement group when the new group leader is nearer than the first group leader comprises the steps of:

calculating a first distance estimate to the first group leader of the first measurement group;

receiving a second distance estimate between the first group leader and the new group leader; and

joining the second measurement group when the second distance estimate between the first group leader and the new group leader is less than or equal to twice the first distance estimate to the first group leader of the first measurement group.

36. 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;

determining by one host in the 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.

37. The method of claim 36, 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.

38. The method of claim 36, 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 SYN packets to the remote host; and

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

39. The method of claim 38, 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.

40. The method of claim 38, 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.

41. The method of claim 38, wherein the step of analyzing 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.

42. In a large scale network having a first plurality of hosts distributed therethrough, at least some of which are nearby one another and are organized into a measurement group, the hosts within the measurement group sharing network performance information, a method of determining by a host within the measurement group network performance to a host remotely located from the measurement group, comprising the steps of:

determining if the network performance to the remote host has been actively calculated by the host previously;

determining if the network performance to the remote host has been actively calculated by another host in the measurement group and shared within the measurement group; and

estimating the network performance to the remote host based on available network performance information actively calculated by the host previously and shared from another host with the measurement group.

43. The method of claim 42, wherein the step of estimating includes the step of weighting the available network performance information.

44. The method of claim 43, wherein the step of weighting includes the step of weighting based on distance to the host in the measurement group who shared the network performance.

45. The method of claim 43, wherein the step of weighting includes the step of weighting based on a time that the network performance was determined.

46. The method of claim 42 wherein a second measurement group is located nearby the measurement group, further comprising the step of determining if the network performance to the remote host has been actively calculated by another host in the nearby measurement group and shared with the measurement group when there is no available network performance information actively calculated by the host previously and no available network performance information shared from another host with the measurement group, and wherein the step of estimating comprises the step of estimating the network performance to the remote host based on available network performance information shared from the nearby measurement group.

47. The method of claim 46, wherein there is no available network performance information shared from the nearby measurement group, further comprising the steps of:

transmitting a packet train of SYN packets to the remote host;

analyzing a return packet train of RST packets from the remote host to determine the network performance to the remote host; and

sharing the network performance with the other hosts in the measurement group.

48. The method of claim 47, 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.

49. The method of claim 47, 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.

50. The method of claim 47, wherein the step of analyzing 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.