1. A method of evaluating stability of software code for a control system, the method comprising:
receiving a set of initial trajectories;
determining, by a semidefinite programming solver module, one or more candidate Lyapunov functions based on the set of initial trajectories;
performing a plurality of simulations using a model of the control system to create a set of discovered trajectories; and
evaluating the set of discovered trajectories to determine one or more counterexample trajectories that violate one or more Lyapunov conditions, wherein if one or more counterexample trajectories are discovered:
inputting the set of discovered trajectories including the one or more counterexample trajectories into the semidefinite programming solver module; and
determining, by the semidefinite programming solver module, one or more additional candidate Lyapunov functions based on the set of initial trajectories and the set of discovered trajectories.
2. The method of claim 1, further comprising, if no candidate Lyapunov functions are found, indicating instability of the software code.
3. The method of claim 1, further comprising, if no counterexample trajectories are discovered, indicating stability of the software code.
4. The method of claim 1, wherein the set of initial trajectories comprise simulated trajectories andor experimental trajectories.
5. The method of claim 1, further comprising, if no counterexample trajectories are discovered, performing a convex optimization on the set of initial trajectories and the set of discovered trajectories to determine an invariant set of trajectories.
6. The method of claim 5, wherein the convex optimization is provided by the sum-of-squares technique.
7. The method of claim 5, further comprising:
executing the software code in the control system to obtain experimental data; and
comparing the experimental data to the invariant set of trajectories.
8. The method of claim 1, wherein the set of discovered trajectories are evaluated to determine the one or more counterexample trajectories by a non-convex, global optimization process.
9. The method of claim 1, wherein the software code is for one or more vehicle systems.
10. The method of claim 1, further comprising:
executing the software code in the control system to obtain experimental trajectories; and
inputting the experimental trajectories into the semidefinite programming solver module to determine one or more candidate Lyapunov functions.
11. A computer-program product for use with a computing device for evaluating stability of software code for a control system, the computer-program product comprising:
a computer-readable medium storing computer-executable instructions that, when executed by the computing device, cause the computing device to:
receive a set of initial trajectories;
determine one or more candidate Lyapunov functions based on the set of initial trajectories using a semidefinite programming solver module;
perform a plurality of simulations using a model of the control system to create a set of discovered trajectories; and
evaluate the set of discovered trajectories to determine one or more counterexample trajectories that violate one or more Lyapunov conditions, wherein, if one or more counterexample trajectories are discovered, the computer-executable instructions further cause the computing device to:
input the set of discovered trajectories including the one or more counterexample trajectories into the semidefinite programming solver module; and
determine one or more additional candidate Lyapunov functions based on the set of initial trajectories and the set of discovered trajectories.
12. The computer-program product of claim 11, wherein if no candidate Lyapunov functions are found, the computer-executable instructions cause the computing device to indicate instability of the software code.
13. The computer-program product of claim 11, wherein if no counterexample trajectories are discovered, the computer-executable instructions cause the computing device to indicate stability of the software code.
14. The computer-program product of claim 11, wherein the set of initial trajectories comprise simulated trajectories andor experimental trajectories.
15. The computer-program product of claim 11, wherein if no counterexample trajectories are discovered the computer-executable instructions cause the computing device to perform a convex optimization on the set of initial trajectories and the set of discovered trajectories to determine an invariant set of trajectories.
16. The computer-program product of claim 15, wherein the convex optimization is provided by the sum-of-squares technique.
17. The computer-program product of claim 11, wherein the set of discovered trajectories are evaluated to determine the one or more counterexample trajectories by a non-convex, global optimization process.
18. The computer-program product of claim 11, wherein the software code is for one or more vehicle systems.
19. A method of evaluating stability of software code for a control system, the method comprising:
receiving a set of initial trajectories;
determining, by a semidefinite programming solver module, one or more candidate Lyapunov functions based on the set of initial trajectories;
performing a plurality of simulations of the control system to create a set of discovered trajectories; and
evaluating the set of discovered trajectories to determine one or more counterexample trajectories that violate one or more Lyapunov conditions, wherein:
if no candidate Lyapunov functions are found, indicating instability of the software code;
if one or more counterexample trajectories are discovered:
inputting the set of discovered trajectories including the one or more counterexample trajectories into the semidefinite programming solver module; and
determining, by the semidefinite programming solver module, one or more additional candidate Lyapunov functions based on the set of initial trajectories and the set of discovered trajectories; and
if no counterexample trajectories are discovered, performing a convex optimization on the set of initial trajectories and the set of discovered trajectories to determine an invariant set of trajectories.
20. The method of claim 19, wherein the software code is for one or more vehicle systems.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method in a first network device operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, the method comprising:
receiving information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table; and
for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
2. The method of claim 1, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises:
determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
3. The method of claim 2, further comprising:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
4. The method of claim 2, further comprising:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evicting the first entry stored in the shared forwarding table from the first candidate location,
inserting the first entry of the first forwarding table in the first candidate location, and
determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
5. The method of claim 3, further comprising:
prior to determining each candidate location, determining whether a number of attempts at determining the candidate location has reached a predetermined threshold; and
in response to determining the number of attempts has reached the predetermined threshold, discarding an entry for which the candidate location is being determined.
6. A first network device operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, the first network device comprising:
a set of one or more processors; and
a non-transitory machine-readable storage medium containing code, which when executed by the set of one or more processors, cause the first network device to:
receive information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, and
for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
7. The first network device of claim 6, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises the first network device:
determine a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determine whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
8. The first network device of claim 7, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table further comprises the first network device to:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determine a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
9. The first network device of claim 7, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table further comprises the first network device to:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evict the first entry stored in the shared forwarding table from the first candidate location,
insert the first entry of the first forwarding table in the first candidate location, and
determine a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
10. The first network device of claim 8, wherein the non-transitory machine-readable storage medium further contains code, which when executed by the set of one or more processors, cause the first network device to:
prior to determining each candidate location, determine whether a number of attempts at determining the candidate location has reached a predetermined threshold; and
in response to determining the number of attempts has reached the predetermined threshold, discard an entry for which the candidate location is being determined.
11. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor of a first network device operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, cause the first network device to perform operations comprising:
receiving information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table; and
for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
12. The non-transitory computer-readable storage medium of claim 11, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises:
determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
13. The non-transitory computer-readable storage medium of claim 12, further comprising:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
14. The non-transitory computer-readable storage medium of claim 12, further comprising:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evicting the first entry stored in the shared forwarding table from the first candidate location,
inserting the first entry of the first forwarding table in the first candidate location, and
determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
15. The non-transitory computer-readable storage medium of claim 13, further comprising:
prior to determining each candidate location, determining whether a number of attempts at determining the candidate location has reached a predetermined threshold; and
in response to determining the number of attempts has reached the predetermined threshold, discarding an entry for which the candidate location is being determined.
16. A method in a first network device operating in a control plane for distributing precedence information of a plurality of forwarding tables to a second network device operating in a forwarding plane, wherein the precedence information is used by the second network device to maintain a shared forwarding table that implements the plurality of forwarding tables, the method comprising:
sending information associated with a first forwarding table to the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, wherein the information of the first forwarding table causes the second network device to, for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
17. The method of claim 16, wherein the information of the first forwarding table causes the second network device to perform operations comprising:
determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
18. The method of claim 17, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
19. The method of claim 17, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evicting the first entry stored in the shared forwarding table from the first candidate location,
inserting the first entry of the first forwarding table in the first candidate location, and
determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
20. A first network device operating in a control plane for distributing precedence information of a plurality of forwarding tables to a second network device operating in a forwarding plane, wherein the precedence information is used by the second network device to maintain a shared forwarding table that implements the plurality of forwarding tables, the first network device comprising:
a set of one or more processors; and
a non-transitory machine-readable storage medium containing code, which when executed by the set of one or more processors, cause the first network device to:
send information associated with a first forwarding table to the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, wherein the information of the first forwarding table causes the second network device to, for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
21. The first network device of claim 20, wherein the information of the first forwarding table causes the second network device to perform operations comprising:
determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
22. The first network device of claim 21, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
23. The first network device of claim 21, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evicting the first entry stored in the shared forwarding table from the first candidate location,
inserting the first entry of the first forwarding table in the first candidate location, and
determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
24. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor of a first network device operating in a control plane for distributing precedence information of a plurality of forwarding tables to a second network device operating in a forwarding plane, wherein the precedence information is used by the second network device to maintain a shared forwarding table that implements the plurality of forwarding tables, cause the first network device to perform operations comprising:
sending information associated with a first forwarding table to the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, wherein the information of the first forwarding table causes the second network device to, for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
25. The non-transitory computer-readable storage medium of claim 24, wherein the information of the first forwarding table causes the second network device to perform operations comprising:
determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
26. The non-transitory computer-readable storage medium of claim 25, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
27. The non-transitory computer-readable storage medium of claim 25, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evicting the first entry stored in the shared forwarding table from the first candidate location,
inserting the first entry of the first forwarding table in the first candidate location, and
determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
28. A method in a virtual machine operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, the method comprising:
receiving information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table; and
for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.
29. The method of claim 28, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises:
determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and
in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.
30. The method of claim 29, further comprising:
in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.
31. The method of claim 29, further comprising:
in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table:
evicting the first entry stored in the shared forwarding table from the first candidate location,
inserting the first entry of the first forwarding table in the first candidate location, and
determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.
32. The method of claim 30, further comprising:
prior to determining each candidate location, determining whether a number of attempts at determining the candidate location has reached a predetermined threshold; and
in response to determining the number of attempts has reached the predetermined threshold, discarding an entry for which the candidate location is being determined.