Monitor, system and method for monitoring performance of a scheduler

• US 7,092,360 B2
• Filed: 12/28/2001
• Issued: 08/15/2006
• 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: Hristov, Boris, Saint-Hilaire, Roxan
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HAMANN, JORDAN J
• Application Number:
  US10/028,286
• Publication Number:
  US 20030125907A1
• Time in Patent Office: 1,691 Days
• Field of Search: None
• US Class Current: 370/241
• 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;

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; and

wherein said scheduler controls the departure of data from a plurality of queues, and said element comprises;

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.

2. A monitor as claimed in claim 1, 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.

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

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

5. A monitor as claimed in claim 4, 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.

6. A monitor as claimed in claim 4, 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.

7. A monitor as claimed in claim 4, 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.

8. A monitor as claimed in claim 7, 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.

9. A monitor as claimed in claim 4, 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.

10. A monitor as claimed in claim 1, 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.

11. A monitor as claimed in claim 1, 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.

12. A monitor as claimed in claim 1, wherein said detection means is detecting 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 detecting the status of said element after said operation causing a data cell to be output, and wherein said comparison means is comparing the status of said element with the expected status of said element after said operation.

13. A monitor as claimed in claim 1, wherein said detection means is detecting 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 detecting the state of said first element after the next cell is output, and said comparison means is comparing the detected state with said expected state and output the result of the comparison.

14. A monitor as claimed in claim 13, 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.

15. A monitor as claimed in claim 13, 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.

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

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

18. 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 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 element, and comparison means for comparing the detected parameter with said expected parameter and for outputting the result of the comparison;

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.

19. A monitor as claimed in claim 18, 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.

20. A monitor as claimed in claim 19, 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.

21. 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 states for that element and for outputting the result of said comparison;

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.

22. A monitor as claimed in claim 21, wherein said scheduler is selecting 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.

23. A monitor as claimed in claim 22, wherein said detector is detecting the status of said selector over a predetermined period of time and said comparison means is comparing the number of times said selector selects a group of queues over said predetermined period with an expected value.

24. 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 for at least one of:

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

25. A system as claimed in claim 24, 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.

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

wherein said scheduler comprises a computer generated model; and

wherein said scheduler is controlling the departure of data from a plurality of queues, and said element comprises;

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.

27. A method as claimed in claim 26, 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.

28. A method as claimed in claim 26, 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.

29. A method as claimed in claim 26, 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.

30. A method as claimed in claim 29, wherein said scheduler is controlling 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.

31. A method as claimed in claim 30, 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.

32. A method as claimed in claim 30, 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.

33. A method as claimed in claim 29, 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.

34. A method as claimed in claim 29, 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.

35. A method as claimed in claim 29, 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.

36. A method as claimed in claim 29, 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.

37. A method as claimed in claim 36, 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.

38. A method as claimed in claim 37, 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.

39. A method as claimed in claim 29, 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.

40. A method as claimed in claim 39, 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.

41. A method as claimed in claim 29, 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.

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

43. A method as claimed in claim 26, 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 26, wherein said computer generated model comprises a file containing a functional description of said element.

45. A method as claimed in claim 26, 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 26, 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.

49. A method as claimed in claim 26, 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.