Differential delay constrained routing for virtually-concatenated data traffic

An apparatus for use in routing virtually-concatenated data traffic in a network comprising a plurality of nodes, the apparatus comprising:

• a processor;
• and
• a memory coupled to the processor;
• wherein the processor is operative, for a given traffic demand to be routed from a source node to a destination node in the network, to perform the steps of:
• determining an initial candidate path set satisfying a differential delay constraint by arranging a plurality of paths in order of increasing delay and selecting a particular subset of the plurality of paths as the initial candidate set;
• determining if the initial candidate path set is able to support a bandwidth requirement of the traffic demand;
• if the initial candidate path set is able to support the bandwidth requirement of the traffic demand, utilizing the initial candidate path set to route the traffic demand;
• and
• otherwise repeating the determining steps for one or more additional iterations, with a different candidate path set satisfying the differential delay constraint being selected for a given additional iteration by application of a sliding-window function to the plurality of paths arranged in order of increasing delay, until a different candidate path satisfying the differential delay constraint is determined to support the bandwidth requirement of the traffic demand, and utilizing that candidate path set to route the traffic demand.

An article of manufacture comprising a machine-readable medium storing one or more programs for use in routing virtually-concatenated data traffic in a network comprising a plurality of nodes, the one or more programs when executed in a processor, for a given traffic demand to be routed from a source node to a destination node in the network, performing the steps of:

• determining an initial candidate path set satisfying a differential delay constraint by arranging a plurality of paths in order of increasing delay and selecting a particular subset of the plurality of paths as the initial candidate set;
• determining if the initial candidate path set is able to support a bandwidth requirement of the traffic demand;
• if the initial candidate path set is able to support the bandwidth requirement of the traffic demand, utilizing the initial candidate path set to route the traffic demand;
• and
• otherwise repeating the determining steps for one or more additional iterations, with a different candidate path set satisfying the differential delay constraint being selected for a given additional iteration by application of a sliding-window function to the plurality of paths arranged in order of increasing delay, until a different candidate path satisfying the differential delay constraint is determined to support the bandwidth requirement of the traffic demand, and utilizing that candidate path set to route the traffic demand.