Method and system for predicting communication delays of detailed application workloads
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/50
G06F-009/44
G06F-009/45
G06F-013/10
G06G-007/62
출원번호
US-0632522
(2000-08-04)
§371/§102 date
20020816
(20020816)
발명자
/ 주소
Papaefstathiou, Efstathios
출원인 / 주소
Microsoft Corporation
대리인 / 주소
Leydig Voit &
인용정보
피인용 횟수 :
45인용 특허 :
3
초록▼
The disclosed method is a hybrid model containing statistical model information as well as steps for simulating the main stages that change the state of the communication network traffic. As such, the evaluation time is orders of magnitude quicker than traditional methods, while providing prediction
The disclosed method is a hybrid model containing statistical model information as well as steps for simulating the main stages that change the state of the communication network traffic. As such, the evaluation time is orders of magnitude quicker than traditional methods, while providing predictions, which are of reasonable accuracy. The characteristics of different networks can be easily incorporated into the model, and thus the model can be used in a variety of situations. The output of the model is the expected delay of a set of communications, which can be further, expanded into a suitable trace format and visualized for further investigation. In evaluation tests, the disclosed method and system provides predictions which are more accurate than simple regression models while requiring seconds of CPU processing time.
대표청구항▼
1. A method for generating a delay model in a networked system under a defined workload, the method comprising:generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the active message; creating a conte
1. A method for generating a delay model in a networked system under a defined workload, the method comprising:generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the active message; creating a contention structure created by summing together routing structure elements for active message events; first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message. 2. The method of claim 1 further comprising:rendering a set of delay values corresponding to a set of active events; and identifying an event horizon corresponding to a simulated time duration before an event state change. 3. The method of claim 2 further comprising:advancing a simulation clock based upon the event horizon; and third calculating completed portions of each one of the set of active events based upon the event horizon. 4. The method of claim 3 wherein the event state change corresponds to a message event state change, and further comprising the steps of:fourth calculating an updated contention structure in accordance with the message event state change and a present set of active message events after the advancing step; rendering a new set of delay values corresponding to the present set of active events in accordance with the updated contention structure and remaining portions of the present set of active events; and determining a next event horizon in accordance with the new set of delay values. 5. The method of claim 2 wherein the event state change corresponds to a completed active event, and further comprising the step of recording within an output trace record an entry corresponding to the completed active event.6. The method of claim 1 wherein the routing structure comprises an array.7. The method of claim 1 wherein the contention structure comprises an array.8. The method of claim 1 further comprising generating a statistical summary of completed events based upon simulated time durations.9. The method of claim 1 further comprising the step of processing an input trace sequence to render a set of events including the first active message.10. The method of claim 9 wherein the input trace sequence is rendered by a translator of a workload definition.11. A computer system including executable program code for generating a delay model in a networked system under a defined workload, the computer system comprising:an input stage that receives a workload description and renders event sequences corresponding to the workload description; and an evaluation stage that receives the event sequences and renders timing information representing execution of the event sequences in a distributed processing network configuration, the evaluation stage comprising executable program instructions for: generating for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the first active message; creating a contention structure created by summing together routing structure elements for active message events; first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the first active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message. 12. The computer system of claim 11 wherein the evaluation stage further comprises executable program instructions for:rendering a set of delay values corresponding to a set of active events; and identifying an event horizon corresponding to a simulated time duration before an event state change. 13. The computer system of claim 12 wherein the evaluation stage further comprises executable program instructions for:advancing a simulation clock based upon the event horizon; and third calculating completed portions of each one of the set of active events based upon the event horizon. 14. The computer system of claim 13 wherein the event state change corresponds to a message event state change, and the evaluation stage further comprises executable program instructions for:fourth calculating an updated contention structure in accordance with the message event state change and a present set of active message events after the advancing step; rendering a new set of delay values corresponding to the present set of active events in accordance with the updated contention structure and remaining portions of the present set of active events; and determining a next event horizon in accordance with the new set of delay values. 15. The computer system of claim 12 wherein the event state change corresponds to a completed active event, and the evaluation stage further comprises executable program instructions for recording within an output trace record an entry corresponding to the completed active event.16. The computer system of claim 11 wherein the routing structure comprises an array.17. The computer system of claim 11 wherein the contention structure comprises an array.18. The computer system of claim 11 further comprising a post output stage for receiving data corresponding to the timing information rendered by the evaluation stage, and generating a statistical summary of completed events based upon simulated time durations.19. The computer system of claim 11 wherein the input stage comprises executable code facilitating processing an input trace sequence to render a set of events including the first active message.20. The computer system of claim 19 wherein the input trace sequence is rendered by a translator of a workload definition.21. A computer-readable medium having computer executable instructions for performing a set of steps to generate a delay model in a networked system under a defined workload, the steps including:generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the first active message; creating a contention structure created by summing together routing structure elements for active message events; first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the first active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message. 22. The computer-readable medium of claim 21 further comprising computer executable instructions for performing the steps of:rendering a set of delay values corresponding to a set of active events; and identifying an event horizon corresponding to a simulated time duration before an event state change. 23. The computer-readable medium of claim 22 further comprising computer executable instructions for performing the steps of:advancing a simulation clock based upon the event horizon; and third calculating completed portions of each one of the set of active events based upon the event horizon. 24. The computer-readable medium of claim 23 further comprising computer executable instructions for performing the steps of:fourth calculating an updated contention structure in accordance with the message event state change and a present set of active message events after the advancing step; rendering a new set of delay values corresponding to the present set of active events in accordance with the updated contention structure and remaining portions of the present set of active events; and determining a next event horizon in accordance with the new set of delay values. 25. The computer-readable medium of claim 22 wherein the event state change corresponds to a completed active event, and further comprising executable instructions for performing the step of recording within an output trace record an entry corresponding to the completed active event.26. The computer-readable medium of claim 21 wherein the routing structure comprises an array.27. The computer-readable medium of claim 21 wherein the contention structure comprises an array.28. The computer-readable medium of claim 21 further comprising executable instructions for performing the step of generating a statistical summary of completed events based upon simulated time durations.29. The computer-readable medium of claim 21 further comprising computer executable instructions for performing the step of processing an input trace sequence to render a set of events including the first active message.30. The computer-readable medium of claim 29 wherein the input trace sequence is rendered by a translator of a workload definition.31. A computer system including executable program code for generating a delay model in a networked system under a defined workload, the computer system comprising:an input stage that receives a workload description and renders event sequences corresponding to the workload description; and an evaluation stage that receives the event sequences and renders timing information representing execution of the event sequences in a distributed processing network configuration, the evaluation stage comprising: a routing structure generator for generating, for a first active message, a routing structure based upon a network configuration and a source network node and destination network node of the first active message; a contention structure generator for creating a contention structure by summing together routing structure elements for active message events; a bandwidth availability calculator for first calculating, for the first active message, an available bandwidth for use by the message at a path between network nodes utilized by the first active message, the available bandwidth being a function of a level of contention between the first active message and at least a second active message on the path, the level of contention being determined in accordance with the contention structure and the routing structure for the first active message; and a delay calculator for second calculating, for the first active message, based upon the available bandwidth, a modeled communication delay to communicate at least a portion of the first active message.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (3)
Corson, Mathew Scott; Park, Vincent Douglas, Adaptive routing method for a dynamic network.
Jackson, David B., Canceling and locking personal reservation if the workload associated with personal reservation exceeds window of time allocated within a resource reservation.
Duan, Ning; Ghoting, Amol; Natarajan, Ramesh, Isolating resources between tenants in a software-as-a-service system using the estimated costs of service requests.
Devarakonda, Murthy V.; Rajamani, Nithya; Srivatsa, Mudhakar, Method and apparatus for performance and policy analysis in distributed computing systems.
Horvitz, Eric J.; Apacible, Johnson T., Methods and interfaces for probing and understanding behaviors of alerting and filtering systems based on models and simulation from logs.
Tantawi, Asser Nasreldin, System for dynamic performance modeling of computer application services using a serial parallel queueing network (SPQN) modeler.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.