Systems and methods for multi-layer traffic grooming

1. A method comprising:

constructing an auxiliary graph for a network comprising a plurality of network elements, the network elements having an Internet Protocol layer, a lower layer, and a wavelength layer, the auxiliary graph including a plurality of directed edges, the plurality of directed edges indicative of connectivity of components of the plurality of network elements; and

for a selected demand of the network:

deleting directed edges from the auxiliary graph whose available bandwidth is lower than the required bandwidth of the demand;

finding a path for the demand on the auxiliary graph via remaining directed edges;

deleting at least one directed edge of the auxiliary graph on the wavelength layer along the path;

adding lower layer lightpath edges to the auxiliary graph for a lower layer lightpath for the path; and

converting lower layer lightpaths to Internet Protocol lightpaths if a conversion condition is satisfied.

2. A method according to claim 1 , further comprising assigning weights to each directed edge of the auxiliary graph.

3. A method according to claim 2 , wherein finding a path for the demand on the auxiliary graph via remaining directed edges comprises finding a path based on the weights.

4. A method according to claim 1 , further comprising updating available bandwidth on each directed edge on the auxiliary graph associated with a lightpath based on lightpath configuration for the demand.

5. A method according to claim 1 , further comprising:

adding back deleted edges of the auxiliary graph; and

selecting a second demand; and

for the second selected demand:

deleting directed edges from the auxiliary graph whose available bandwidth is lower than the required bandwidth of the second demand;

finding a second path for the second demand on the auxiliary graph via remaining directed edges;

deleting at least one directed edge of the auxiliary graph on the wavelength layer along the second path;

adding lower layer lightpath edges to the auxiliary graph for a lower layer lightpath for the second path; and

converting lower layer lightpaths to Internet Protocol lightpaths if a conversion condition is satisfied.

6. A method according to claim 5 , further comprising determining a total cost for lightpath configurations for the demand and the second demand.

7. A method according to claim 6 , further comprising:

changing the weights for the directed edges;

repeating the deleting, finding, adding, and converting steps for each of the demand and the second demand based on the changed weights;

determining a second total cost for lightpath configurations for the demand and the second demand based on the changed weights; and

selecting a configuration for the network based on a comparison of the total cost to the second total cost.

8. A network element comprising:

an Internet Protocol layer having plurality of Internet Protocol layer access modules;

a lower layer having a plurality of lower layer access modules;

a wavelength layer supporting communication via a plurality of wavelength division multiplexed wavelengths;

logic for constructing an auxiliary graph for a network comprising the network element and at least one second network element, the auxiliary graph including a plurality of directed edges, the plurality of directed edges indicative of connectivity of components of the network element and the at least one second network element;

logic for selecting a demand of the network;

logic for deleting directed edges from the auxiliary graph whose available bandwidth is lower than the required bandwidth of the demand;

logic for finding a path for the demand on the auxiliary graph via remaining directed edges;

logic for deleting at least one directed edge of the auxiliary graph on the wavelength layer along the path;

logic for adding lower layer lightpath edges to the auxiliary graph for a lower layer lightpath for the path; and

logic for converting lower layer lightpaths to Internet Protocol lightpaths if a conversion condition is satisfied.

9. A network element according to claim 8 , further comprising logic for assigning weights to each directed edge of the auxiliary graph.

10. A network element according to claim 9 , wherein the logic for finding a path for the demand on the auxiliary graph via remaining directed edges comprises logic for finding a path based on the weights.

11. A network element according to claim 8 , further comprising logic for updating available bandwidth on each directed edge on the auxiliary graph associated with a lightpath based on lightpath configuration for the demand.

12. A network element according to claim 8 , further comprising:

logic for adding back deleted edges of the auxiliary graph;

logic for selecting a second demand;

logic for deleting directed edges from the auxiliary graph whose available bandwidth is lower than the required bandwidth of the second demand;

logic for finding a second path for the second demand on the auxiliary graph via remaining directed edges;

logic for deleting at least one directed edge of the auxiliary graph on the wavelength layer along the second path;

logic for adding lower layer lightpath edges to the auxiliary graph for a lower layer lightpath for the second path; and

logic for converting lower layer lightpaths to Internet Protocol lightpaths if a conversion condition is satisfied.

13. A network element according to claim 12 , further comprising logic for determining a total cost for lightpath configurations for the demand and the second demand.

14. A network element according to claim 13 , further comprising:

logic for changing the weights for the directed edges;

logic for determining a second total cost for lightpath configurations for the demand and the second demand based on the changed weights; and

logic for selecting a configuration for the network based on a comparison of the total cost to the second total cost.

15. A system comprising:

logic constructing an auxiliary graph for a network comprising a plurality of network elements, the network elements having an Internet Protocol layer, a lower layer, and a wavelength layer, the auxiliary graph including a plurality of directed edges, the plurality of directed edges indicative of connectivity of components of the plurality of network elements;

logic for selecting a demand of the network;

logic for deleting directed edges from the auxiliary graph whose available bandwidth is lower than the required bandwidth of the demand;

logic for finding a path for the demand on the auxiliary graph via remaining directed edges;

logic for deleting at least one directed edge of the auxiliary graph on the wavelength layer along the path;

logic for adding lower layer lightpath edges to the auxiliary graph for a lower layer lightpath for the path; and

logic for converting lower layer lightpaths to Internet Protocol lightpaths if a conversion condition is satisfied.

16. A system according to claim 15 , further comprising logic for assigning weights to each directed edge of the auxiliary graph.

17. A system according to claim 16 , wherein the logic for finding a path for the demand on the auxiliary graph via remaining directed edges comprises logic for finding a path based on the weights.

18. A system according to claim 15 , further comprising logic for updating available bandwidth on each directed edge on the auxiliary graph associated with a lightpath based on lightpath configuration for the demand.

19. A system according to claim 15 , further comprising:

logic for adding back deleted edges of the auxiliary graph;

logic for selecting a second demand;

logic for deleting directed edges from the auxiliary graph whose available bandwidth is lower than the required bandwidth of the second demand;

logic for finding a second path for the second demand on the auxiliary graph via remaining directed edges;

logic for deleting at least one directed edge of the auxiliary graph on the wavelength layer along the second path;

logic for adding lower layer lightpath edges to the auxiliary graph for a lower layer lightpath for the second path; and

logic for converting lower layer lightpaths to Internet Protocol lightpaths if a conversion condition is satisfied.

20. A system according to claim 19 , further comprising logic for determining a total cost for lightpath configurations for the demand and the second demand.

21. A network element according to claim 20 , further comprising:

logic for changing the weights for the directed edges;

logic for determining a second total cost for lightpath configurations for the demand and the second demand based on the changed weights; and

logic for selecting a configuration for the network based on a comparison of the total cost to the second total cost.