Methods and apparatus to model end-to-end class of service policies in networks

1. A method to generate a class of service model, comprising:

electronically generating a ruleset based on a class of service configuration associated with a router;

electronically generating a flat representation of the ruleset, wherein generating the flat representation comprises generating a binary decision diagram representative of the ruleset;

electronically generating a class of service model by composing the flat representation into a composed ruleset, wherein composing the flat representation comprises transforming the binary decision diagram, wherein the binary decision diagram is a first binary decision diagram and transforming the first binary decision diagram comprises using existential quantification to remove a binary decision diagram variable from the binary decision diagram, generating a second binary decision diagram using the removed binary decision diagram variable, and performing a set-union on the first and second binary decision diagrams to generated a transformed binary decision diagram; and

storing the class of service model in a computer-readable memory.

2. A method as defined in claim 1 , further comprising generating a recursive representation of the ruleset.

3. A method as defined in claim 1 , wherein the class of service configuration comprises a configuration file, the router providing a plurality of classes of service based on the configuration file.

4. A method as defined in claim 1 , further comprising using the stored class of service model to do at least one of: output a flow treatment, identify a shadowed policy in the class of service model, identify a departure from a class of service configuration pattern, and electronically generate a class of service map of a virtual private network.

5. A method as defined in claim 1 , wherein generating the flat representation further comprises set-intersecting a first binary decision diagram representative of a flowset with a second binary decision diagram representative of a router policy of the router.

6. A computer readable storage disk comprising machine readable instructions which, when executed, cause a machine to at least:

generate a ruleset based on a class of service configuration associated with a router;

generate a flat representation of the ruleset, wherein generating the flat representation comprises generating a binary decision diagram representative of the ruleset;

generate a class of service model by composing the flat representation into a composed ruleset, wherein composing the flat representation comprises transforming the binary decision diagram, wherein the binary decision diagram is a first binary decision diagram, and transforming the first binary decision diagram comprises using existential quantification to remove a binary decision diagram variable from binary decision diagram, generating a second binary decision diagram using the removed binary decision diagram variable, and performing a set-union on the first and second binary decision diagrams to generated a transformed binary decision diagram; and

store the class of service model in a computer-readable memory.

7. A computer readable storage disk as defined in claim 6 , wherein the class of service configuration comprises a configuration file, the router providing a plurality of classes of service based on the configuration file.

8. A computer readable storage disk as defined in claim 7 , wherein the instructions further cause the machine to use the stored class of service model to do at least one of: output a flow treatment, identify a shadowed policy in the class of service model, identify a departure from a class of service configuration pattern, and electronically generate a class of service map of a virtual private network.

9. A computer readable storage disk as defined in claim 6 , wherein generating the flat representation further comprises set-intersecting a first binary decision diagram representative of a flowset with a second binary decision diagram representative of a router policy.

10. An apparatus, comprising:

a processor; and

a memory having computer readable instructions stored thereon which, when executed, cause the processor to perform operations comprising:

generating a ruleset based on a class of service configuration associated with a router;

generating a flat representation of the ruleset;

generating a class of service model by composing the flat representation into a composed ruleset, wherein composing the flat representation comprises transforming the binary decision diagram, wherein the binary decision diagram is a first binary decision diagram, and transforming the first binary decision diagram comprises using existential quantification to remove a binary decision diagram variable from binary decision diagram, generating a second binary decision diagram using the removed binary decision diagram variable, and performing a set-union on the first and second binary decision diagrams to generated a transformed binary decision diagram; and

storing the class of service model in the memory.

11. An apparatus as defined in claim 10 , wherein generating the flat representation further comprises set-intersecting a first binary decision diagram representative of a flowset with a second binary decision diagram representative of a router policy.

12. An apparatus as defined in claim 10 , wherein the instructions further cause the processor to generate a recursive representation of the ruleset.

13. An apparatus as defined in claim 10 , wherein the class of service configuration comprises a configuration file, the router providing a plurality of classes of service based on the configuration file.

14. An apparatus as defined in claim 10 , wherein the instructions further cause the processor to use the stored class of service model to do at least one of: output a flow treatment, identify a shadowed policy in the class of service model, identify a departure from a class of service configuration pattern, and electronically generate a class of service map of a virtual private network.