Monitor, system and method for monitoring performance of a scheduler

• US 20030125907A1
• Filed: 12/28/2001
• Published: 07/03/2003
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Tropic Networks, Inc. (Nokia Corporation)
• Inventors: Saint-Hilaire, Roxan, Hristov, Boris
• Granted Patent: US 7,092,360 B2
• Time in Patent Office: Days
• US Class Current: 702/186
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/88 Monitoring involving counting

Abstract

A monitor for monitoring the operation of a scheduler for controlling the departure of data cells is provided, comprising a detector for detecting the state of an internal element of the scheduler during a test, and determining means for determining whether the scheduler is operating as intended based on the detected state of the internal element.

Claims

1. A monitor for monitoring the operation of a scheduler for controlling the departure of data cells, comprising detection means for detecting a state of an element of said scheduler, comparing means for comparing the detected state with a predetermined state for said element and for outputting the result of the comparison.

2. A monitor as claimed in claim 1, wherein said scheduler is adapted to control the departure of data from a plurality of queues, and said element comprises any one of:

an element for recording whether a queue is empty or occupied, an element for recording the number of data cells contained in a queue, an element identifying a queue from which data is to be output, and an element identifying a group of queues from which data is to be output.

3. A monitor as claimed in claim 2, wherein said element for identifying a queue from which data is to be output comprises one of a current pointer for identifying a queue from which data is to be output, and a next pointer for identifying a queue from which data is to be output after data is output from the queue identified by said current pointer.

4. A monitor as claimed in claim 1, further comprising monitoring means for monitoring a parameter relating to the operation of said scheduler, and determining means for determining an expected state for said element based on said monitored parameter.

5. A monitor as claimed in claim 4, wherein said scheduler is adapted to control the departure of data cells from a plurality of queues, and said element comprises any one of:

an element for recording whether a queue is empty or occupied, an element for recording the number of data cells contained in a queue, an element identifying a queue from which a data cell is to be output, and an element identifying a group of queues from which a cell is to be output.

6. A monitor as claimed in claim 5, wherein said element for identifying a queue from which a cell is to be output, comprises one of:

a current pointer for identifying a queue from which a cell is to be output, and a next pointer identifying a queue from which a cell is to be output after a cell is output from the queue identified by said current pointer.

7. A monitor as claimed in claim 5, wherein said parameter comprises one of:

information contained in a cell supplied for storage in a queue identifying the queue in which the cell is to be stored, and information contained in a cell output by said scheduler identifying a queue for storing the cell.

8. A monitor as claimed in claim 4, wherein said parameter comprises a state of a second element of said scheduler.

9. A monitor as claimed in claim 8, wherein said element comprises an element for identifying a queue from which a cell is to be output, and said parameter comprises one of:

the state of an element recording whether is queue is empty or occupied, the state of an element recording the number of cells contained in a queue, and an element indicating a group of queues from which a cell is to be output.

10. A monitor as claimed in claim 8, wherein said element comprises an element for recording whether a queue is empty or occupied, and said parameter comprises the status of an element recording the number of cells contained in a queue.

11. A monitor as claimed in claim 8, wherein said element comprises an element for recording whether a queue is empty or occupied, and said parameter comprises the status of a second element for recording whether the same queue is empty or occupied.

12. A monitor as claimed in claim 11, wherein said first element comprises a register for recording whether said is empty or occupied, and said second element comprises a counter for recording the number of data cells stored in said queue.

13. A monitor as claimed in claim 8, wherein said element comprises one of:

an element for recording whether a queue is empty or occupied, and an element for recording the number of cells contained in a queue, and said parameter comprises the status of an element identifying a group of queues from which a cell is to be output.

14. A monitor as claimed in claim 1, wherein said scheduler comprises a computer generated model, and said monitor includes means for requesting said scheduler model to pass the status of said element to said monitor.

15. A monitor as claimed in claim 1, wherein said detection means is adapted to detect the status of said element before an operation causing a cell to be output, and said monitor further comprises prediction means for determining an expected status for said element after an operation causing a data cell to be output and wherein said detection means is further adapted to detect the status of said element after said operation causing a data cell to be output, and wherein said comparison means is adapted to compare the status of said element with the expected status of said element after said operation.

16. A monitor as claimed in claim 1, wherein said detection means is adapted to detect the state of a second element prior to a next cell being output by said scheduler, and wherein said monitor further comprises prediction means for determining an expected state of said first element after the next cell readout by said scheduler and wherein said detection means is adapted to detect the state of said first element after the next cell is output, and said comparison means is adapted to compare the detected state with said expected state and output the result of the comparison.

17. A monitor as claimed in claim 16, wherein said second element comprises a current pointer which identifies a queue from which a data cell is to be readout and said first element comprises any one of:

an element recording whether a queue is empty or occupied, an element recording the number of cells in a queue, a next pointer identifying the next queue from which a data cell is to be output after the next cell output, and an element identifying a group of queues from which a cell is to be output.

18. A monitor as claimed in claim 16, wherein said second element comprises a next pointer identifying a queue from which a cell is to be output by said scheduler after the next cell output and said first element comprises any one of:

a current pointer identifying a queue from which the next cell is to be readout, an element recording whether a queue is empty or occupied, an element recording the number of cells contained in a queue and an element identifying a group of queues from which a cell is to be readout.

24. A monitor as claimed in claim 1, wherein said scheduler comprises a buffer having a plurality of queues for storing data cells, and a next pointer for identifying a queue from which a next cell is to be output, and wherein said first element comprises a current pointer which identifies a queue from which a data cell is to be read out, and said monitor is arranged to detect the position of said current pointer after a data cell has been read from the queue identified by said current pointer and to compare said position with the position of said next pointer.

25. A monitor as claimed in claim 1, wherein said scheduler comprises first and second elements and said monitor is adapted to monitor the state of at least one of said first and second elements at a plurality of different times and to compare the state of the element at said different times with an expected state at each of said plurality of different times.

28. A monitor as claimed in claim 11, wherein said detector is arranged to detect the status of said selector over a predetermined period of time and said comparison means is adapted to compare the number of times said selector selects a group of queues over said predetermined period with an expected value.

19. A monitor for monitoring the operation of a scheduler for controlling the departure of data cells, comprising detection means for detecting a state of a first element of said scheduler and a parameter relating to the operation of said scheduler, determining means for determining an expected value of said parameter based on the detected state of said first element, and comparison means for comparing the detected parameter with said expected parameter and for outputting the result of the comparison.

20. A monitor as claimed in claim 19, wherein said parameter comprises one of:

information contained in a cell supplied for storage in a queue identifying the queue in which the cell is to be stored, and information contained in a cell output by said scheduler identifying a queue for storing the cell.

21. A monitor as claimed in claim 20, wherein said element comprises any one of:

an element for recording whether a queue is empty of occupied, an element for recording the number of data cells contained in a queue, an element identifying a queue, an element identifying a queue from which a data cell is to be output, and an element identifying a group of queues from which a data cell is to be output.

22. A computer generated model of a scheduler for controlling the departure of data cells, the scheduler having a plurality of simulated circuit elements and an instruction associated with at least one circuit element for causing the status of the element to be transferred externally of the simulated scheduler for detection.

23. A computer generated model as claimed in claim 22, wherein said element comprises any one of:

an element for recording whether a queue is empty or occupied, an element for recording the number of data cells contained in a queue, an element identifying a queue from which data is to be output, and an element identifying a group of queues from which data is to be output.

26. A monitor for monitoring a scheduler for controlling the departure of data cells from a plurality of queues, comprising means for detecting the state of an element of said scheduler at a plurality of different times and comparing the detected states with expected stares for that element and for outputting the result of said comparison.

27. A monitor as claimed in claim 26, wherein said scheduler is adapted to select queues for cell departure from a plurality of different groups of queues, and said element comprises a selector for selecting a group of queues from said plurality of groups and whose status indicates the selected group.

29. A system for monitoring operation of a scheduler for controlling the departure of data cells from a plurality of queues, comprising a generator for generating test cells and means for placing said test cells in said queues, each test cell containing the identity of the queue in which the cell is placed, and a monitor having means for detecting the state of at least one element of said scheduler whose state depends on which queue is selected by said scheduler for outputting a test cell and means for detecting from each test cell input to and/or output by said scheduler, the identity of the queue in which contained in said test cell, and comparison means adapted to at least one of:

compare the detected element status with an expected status for said element based on the detected queue identity and compare the detected queue identity, with an expected queue identity based on the detected status of said element.

30. A system as claimed in claim 29, wherein said element comprises one of a pointer identifying the queue from which a data cell is to be output and an element for recording whether a queue is empty or occupied.

31. A method of monitoring operation of a scheduler, comprising supplying said scheduler with data, monitoring the state of an element of said scheduler, comparing the monitored state with an expected state for said element, and outputting the result of the comparison.

32. A method as claimed in claim 31, wherein said scheduler is adapted to control the departure of data from a plurality of queues, and said element comprises any one of:

an element for recording whether a queue is empty or occupied, an element for recording the quantity of data contained in a queue, an element identifying a queue from which data is to be output, and an element identifying a group of queues from which data is to be output.

33. A method as claimed in claim 32, wherein said element for identifying a queue from which data is to be output comprises one of a current pointer for identifying a queue from which data is to be output, and a next pointer identifying a queue from which data is to be output after a data cell is output from the queue identified by said current pointer.

34. A method as claimed in claim 31, further comprising monitoring a parameter relating to the operation of said scheduler, and determining an expected state for said element based on said monitored parameter.

35. A method as claimed in claim 31, further comprising monitoring a parameter relating to the operation of said scheduler, determining an expected value for said parameter based on the state of said element, comparing the monitored value of said parameter with the expected value of said parameter and outputting the result of the comparison.

36. A method as claimed in claim 34, wherein said scheduler is adapted to control the departure of data cells from a plurality of queues, and said element comprises any one of:

an element for recording whether a queue is empty or occupied, an element for recording the number of cells contained in a queue, an element identifying a queue from which a data cell is to be output, and an element identifying a group of queues from which a cell is to be output.

37. A method as claimed in claim 36, wherein said element for identifying a queue from which a cell is to be output comprises one of a current pointer for identifying a queue from which a cell is to be output, and a next pointer identifying a queue from which a cell is to be output after a cell is output from the queue identified by said current pointer.

38. A method as claimed in claim 36, wherein said parameter comprises one of:

information contained in a cell supplied for storage in a queue identifying the queue in which the cell is to be stored, and information contained in a cell output from said scheduler identifying a queue for storing the cell.

39. A method as claimed in claim 34, wherein said element comprises an element for identifying a queue from which a cell is to be output, and said parameter comprises one of:

the status of an element recording whether a queue is empty or occupied, the state of an element recording the number of cells contained in a queue, and an element indicating a group of queues from which a cell is to be output.

40. A method as claimed in claim 34, wherein said element comprises an element for recording whether a queue is empty or occupied and said parameter comprises the state of an element recording the number of cells contained in a queue.

41. A method as claimed in claim 34, wherein said element comprises one of:

an element for recording whether a queue is empty or occupied, and an element for recording the number of cells contained in a queue, and said parameter comprises the state of an element identifying a group of queues from which a cell is to be output.

42. A method as claimed in claim 31, wherein said scheduler comprises a computer generated model.

43. A method as claimed in claim 42, wherein the step of monitoring the state of an element comprises calling an instruction associated with said scheduler model to pass the state of said element to said monitor.

44. A method as claimed in claim 42, wherein said computer generated model comprises a file containing a functional description of said element.

45. A method as claimed in claim 42, wherein said computer generated model is described in a programming language from which the scheduler can be synthesized.

46. A method as claimed in claim 45, wherein said scheduler model is generated using a hardware description programming language.

47. A method as claimed in claim 46, wherein said programming language comprises one of Verilog and VDHL.

48. A method as claimed in claim 34, further comprising monitoring the state of one or more elements of said scheduler and comparing the state of the or each further element with an expected state for the or each further element.

49. A method as claimed in claim 48, further comprising determining an expected state for the or each further element based on at least one of the monitored and the expected state of said first element.

50. A method as claimed in claim 49, wherein said one or more further elements is/are selected from the group consisting of:

an element for recording whether a queue is empty or occupied, an element for recording the number of cells contained in a queue, an element identifying a queue from which a cell is to be output, and an element identifying a group of queues from which a cell is to be output.

51. A method as claimed in claim 34, further comprising monitoring one or more further parameters relating to the operation of said scheduler and comparing the monitored value of the or each further parameter with an expected value for the or each parameter.

52. A method as claimed in claim 51, further comprising determining the expected value of the or each further parameter based on at least one of the monitored value and the expected value of the first parameter.

53. A method as claimed in claim 31, further comprising determining the expected state for said element based on at least one previous state of said element or on at least one previous state of another element or parameter relating to the operation of said scheduler.

54. A method as claimed in claim 31, further comprising monitoring the state of said element at a plurality of successive times and comparing the sequence of monitored states with a sequence of expected states for said element.

55. A method as claimed in claim 34, comprising monitoring said parameter at a plurality of successive times and comparing the sequence of monitored states of said parameter with a sequence of expected states for said parameter.

56. A method as claimed in claim 55, wherein each parameter comprises information contained in a data cell output by said scheduler identifying a queue for storing said cell.

57. A method of monitoring operation of a scheduler for controlling the departure of data cells, comprising supplying said scheduler with data cells, monitoring the status of an element of said scheduler, monitoring the value of a parameter relating to the operation of said scheduler, determining an expected value for said parameter based on the detected state of said element, and comparing the detected value of said parameter with said expected value, and outputting the result of the comparison.

58. A method of fabricating a scheduler for controlling the departure of data, comprising creating a computer model of a scheduler, generating test cells for testing the performance of said scheduler, monitoring the operation of said computer model including monitoring a state of at least one element of said model, determining whether said model is operating as required based on the monitored state of said at least one element, modifying said model if said model is not operating as required, and synthesizing said scheduler in hardware based on the tested computer generated model.

59. A scheduler fabricated according to the method of claim 58.