Summarized application profiling and quick network profiling

• US 6,381,628 B1
• Filed: 11/20/1998
• Issued: 04/30/2002
• Est. Priority Date: 10/02/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hunt, Galen C.
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US09/197,211
• Time in Patent Office: 1,257 Days
• Field of Search: 709/200, 709/201, 709/220, 709/223, 709/224, 709/303
• US Class Current: 709/201
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 9/465 Distributed object oriented systems remote method invocation [RMI] G06F9/548
• CPC Class Codes: H04L 41/0233 Object-oriented techniques, for representation of network management data, e.g. common object request broker architecture [CORBA]
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

An automatic distributed partitioning system (ADPS) profiles a computer network using short term sampling to estimate minimum network latency and maximum network bandwidth. The ADPS profiles an application program to produce an application profile that summarizes inter-unit communication within the application program. Summarization of the application profile reduces overhead during profiling of the application program. The application profile is network independent, but by combining it with information in the network profile, the ADPS produces a model of the behavior of the application program on the computer network. Quick estimation of network characteristics facilitates the ADPS repartitioning the application to adjust to a different computer network or a changed computer network.

Claims

1. A method for partitioning and distributing plural units of an application program through a computer network based upon an application profile and a network profile, wherein the computer network comprises a first computer and a second computer connected by a network connection, the method comprising:

profiling a computer network to produce a network profile, wherein the network profile comprises estimates of characteristics of the computer network, and wherein the estimates comprise application program independent values;

profiling an application program to produce an application profile, wherein the application profile comprises a summary of communication between plural units of the application program, and wherein the summary comprises a network-independent description;

determining a distribution plan for the plural units of the application program in the computer network based upon the network profile and the application profile, wherein the application profile complements the network profile to produce a model of the behavior of the application program on the computer network; and

executing the application program, wherein plural units of the application program are distributed in the computer network according to the distribution plan.

2. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

3. The method of claim 1 wherein the application profile comprises a summary structure, wherein a first unit and a second unit communicate through plural messages, and wherein for the first and second unit pair the summary structure stores a size value for each message sent between the first and second units.

4. The method of claim 1 wherein the application profile comprises a summary structure, wherein a first unit and a second unit communicate through plural messages, wherein for the first and second unit pair the summary structure comprises plural message buckets, wherein each message bucket has a size range, wherein a message bucket stores a size value for a message that falls within the size range of the message bucket, and wherein the size ranges of the plural message buckets form a contiguous series.

5. The method of claim 4 wherein the size ranges of the plural message buckets are spaced at increasing intervals along the contiguous series, whereby a first message bucket stores size values for the smallest messages and has the smallest size range, and whereby a last bucket stores size values for the largest messages and has the largest size range.

6. The method of claim 4 wherein the step of profiling an application program comprises:

determining from the network profile a set of discontinuities of a function relating network latency to network bandwidth;

creating the plural message buckets based upon the set of discontinuities; and

classifying communication between the plural units of the application program based upon the message buckets.

7. The method of claim 4 wherein the computer network has an associated set of message buckets, the method further comprising:

receiving from a user an identifier of the computer network;

finding for the computer network an associated set of message buckets; and

organizing the summary structure based upon the set of message buckets.

8. The method of claim 4 wherein testing of plural computer networks determines a set of message buckets for messages sent over an unknown computer network.

9. The method of claim 1 wherein the step of profiling a computer network comprises:

for each of n samples, where n is the number of samples in a short term sample set,

noting a start time in a first computer;

sending a message from the first computer to a second computer over the network connection;

receiving a message response from the second computer;

noting a finish time in the first computer;

calculating a latency value based upon the start time and the finish time;

noting the latency value for the sample; and

from the short term sample set, determining a minimum latency value for the computer network.

10. A computer-readable medium having computer-executable instructions for performing the method of claim 9.

11. The method of claim 9 wherein the message comprises an empty data frame, wherein a protocol stack in the first computer wraps the message with protocol information, and wherein the first computer transmits the wrapped message as one or more packets over the network connection.

12. The method of claim 9 wherein the step of profiling a computer network further comprises:

for each of m samples, where m is the number of samples in a second short term sample set,

noting a start time in the first computer;

sending a long message from the first computer to the second computer over the network connection, wherein the long message has a fixed size larger than the size of a message sent for one of the n samples;

receiving a long message response from the second computer;

noting a finish time in the first computer;

calculating a latency value based upon the start time and the finish time;

noting the latency value for the sample;

from the first and second short term sample sets, determining a maximum bandwidth value for the computer network.

13. A computer-readable medium having computer-executable instructions for performing the method of claim 12.

14. The method of claim 12 wherein the long message comprises a k byte data frame, wherein a protocol stack in the first computer wraps the long message with protocol information, and wherein the first computer transmits the wrapped long message as one or more packets over the network connection.

15. The method of claim 12 wherein the step of determining a maximum bandwidth value comprises:

determining a second minimum latency value, wherein the second minimum latency value is the minimum latency for a sample in the second short term sample set;

calculating a difference between the second minimum latency value and the minimum latency value from the first short term sample set;

calculating a maximum latency value by dividing the size of the long message by the difference.

16. The method of claim 12 wherein m<

5.

17. The method of claim 12 wherein the long message response comprises a k byte data frame, wherein a protocol stack in the second computer wraps the long message response with protocol information, and wherein the second computer transmits the wrapped long message response as one or more packets over the network connection.

18. The method of claim 12 wherein the long message response comprises an empty data frame, wherein a protocol stack in the second computer wraps the long message response with protocol information, and wherein the second computer transmits the wrapped long message response as one or more packets over the network connection.

19. The method of claim 9 wherein n<

5.

20. The method of claim 1, the profiling of an application program further comprising:

noting a first unit of the application program;

noting a second unit of the application program;

summarizing a series of plural messages sent between the first and second units based upon the number of messages and the sizes of the messages; and

producing an application profile.

21. A computer-readable medium having computer-executable instructions for performing the method of claim 20.

22. The method of claim 20 wherein a summary structure for the first and second unit pair stores a size value for each message sent between the first and second units.

23. The method of claim 22 wherein the summarizing comprises:

calculating the total number of messages;

for each of n samples, where n is less than the total number of messages, noting the size value of a message sent between the first and second units; and

calculating an average size value for the messages sent between the first and second units based on the n samples.

24. The method of claim 22 wherein the summarizing comprises:

sorting the stored size values;

for each of m size ranges,

calculating the number of messages in the size range;

for each of n samples, where n is less than the number of messages in the size range, noting the size value of a message sent between the first and second units; and

calculating an average size value for the messages of the size range based upon the n samples.

25. The method of claim 20 wherein a summary structure for the first and second unit pair comprises plural message buckets, wherein each message bucket has a size range, wherein a message bucket stores a size value for a message that falls within the size range of the message bucket, wherein the size ranges of the plural message buckets form a contiguous series, wherein the size ranges of the plural message buckets are equally spaced along the contiguous series up to a size limit, wherein a lower limit of a size range for a last message bucket is the size limit, and wherein the size range for the last message bucket lacks an upper limit.

26. The method of claim 25 wherein the size ranges of the plural message buckets are spaced at exponentially increasing intervals along the contiguous series up to a size limit, whereby a first message bucket stores size values for the smallest messages and has the smallest size range, whereby a last message bucket stores size values for the largest messages and has the largest size range, wherein a lower limit of the size range for the last message bucket is the size limit, and wherein the size range for the last message bucket lacks an upper limit.

27. The method of claim 20 wherein the summarizing a series of plural messages comprises:

for each message sent between the first unit and the second unit,

detecting the message;

measuring the size of the message; and

classifying the message according to the measured size.

28. The method of claim 20 wherein the summarizing a series of plural messages comprises:

for each message sent between the first unit and the second unit,

detecting the message;

recording the size of the message in a series;

for the series,

measuring the size of each message in the series of plural messages; and

classifying each message according to the measured size.