Method for routing optical signals with diversity requirements

A method of determining a route for transmitting a signal through a network, the method comprising:

• obtaining network data, including link type data, spare capacity data, vendor data, and common mileage data;
• obtaining demand data, including origination node data, termination node data, and diversity requirement data;
• storing the network data and the demand data;
• processing the demand data using a shortest path routing method to obtain an initial route;
• updating the network data by decreasing the spare capacity data in accordance with the initial route;
• computing an initial cost based on the initial route;
• updating the network data by increasing the spare capacity data in accordance with deleting the initial route;
• re-processing the demand data using a constrained diverse shortest path routing method until a stop criterion is satisfied and obtaining a final route;
• computing a final cost based on the final route;
• and
• outputting the final route and the final cost,
• wherein the initial cost and the final cost are based on one or more of a diversity cost, a capacity overload cost and a routing cost and computed as Total_Cost(R) as follows:
• Total—Cost(R)=Div—Cost(R)+Overload—Cost(R)+Routing—Cost(R).

A method of determining routes for transmitting signals through a network, the method comprising:

• obtaining a plurality of demands T, each demand Ti having diversity requirements Di;
• processing each demand Ti consecutively using a shortest path routing method to obtain a corresponding initial route Ri which satisfy the diversity requirements Di if network parameters permit;
• updating the network parameters based upon the initial routes R;
• computing an initial cost solution based on the initial routes R;
• re-processing each demand Ti using a constrained diverse shortest path method to obtain a corresponding final route Ri′ until a stop criterion is satisfied;
• computing a final cost solution based on the final routes R′;
• and
• outputting the final routes R′ and the final cost solution,
• wherein the constrained diverse shortest path method includes:
• creating an initial partial path pn having parameters node(pn), cost(pn), violation_set(pn) and parent(pn) wherein
• node(pn) is set equal to Ai,
• cost(pn) is set equal to zero,
• violation_set(pn) is set equal to null, and
• parent(pn) is set equal to riull;
• storing initial partial path pn in memory;
• initializing a value Heap that indicates whether there is an established pathway to Zi;
• and
• determining whether the established pathway is compliant with an optical transponder constraint, if Heap is equal to null.

A method of determining routes for transmitting signals through a network, the method comprising:

• obtaining a plurality of demands T, each demand Ti having diversity requirements Di;
• processing each demand Ti consecutively using a shortest path routing method to obtain a corresponding initial route Ri which satisfy the diversity requirements Di if network parameters permit;
• updating the network parameters based upon the initial routes R;
• computing an initial cost solution based on the initial routes R;
• re-processing each demand Ti using a constrained diverse shortest path method to obtain a corresponding final route Ri′ until a stop criterion is satisfied;
• computing a final cost solution based on the final routes R′;
• and
• outputting the final routes R′ and the final cost solution,
• wherein the constrained diverse shortest path method includes:
• creating a partial path pn having parameters node(pn), cost(pn), violation_set(pn) and parent(pn) wherein
• node(pn) is set equal to a termination node of a previous partial path pre-pn,
• cost(n) is equal to a current total cost of the partial path pn,
• violation_set(pn) is a collection of violated diversity requirements of the partial path pn and
• parent(n) is the previous partial path pre-pn.

A method of determining routes for transmitting signals through a network, the method comprising:

• obtaining a plurality of demands T, each demand Ti having diversity requirements Di;
• processing each demand Ti consecutively using a shortest path routing method to obtain a corresponding initial route Ri which satisfy the diversity requirements Di if network parameters permit;
• updating the network parameters based upon the initial routes R;
• computing an initial cost solution based on the initial routes R;
• re-processing each demand Ti using a constrained diverse shortest path method to obtain a corresponding final route Ri′ until a stop criterion is satisfied;
• computing a final cost solution based on the final routes R′;
• and
• outputting the final routes R′ and the final cost solution,
• wherein the constrained diverse shortest path method includes:
• selecting a partial path pni, having parameters node(pni), cost(pni), violation_set(pni) and parent(pni) from one or more partial paths, where cost(pni) is minimal in comparison to costs associated with other partial paths, when a Heap value is not equal to null;
• and
• equating partial path pni with a route Ai-Zi if node(pni) is equal to Zi.

A method of determining routes for transmitting signals through a network, the method comprising:

• obtaining a plurality of demands T, each demand Ti having diversity requirements Di;
• processing each demand Ti consecutively using a shortest path routing method to obtain a corresponding initial route Ri which satisfy the diversity requirements Di if network parameters permit;
• updating the network parameters based upon the initial routes R;
• computing an initial cost solution based on the initial routes R;
• re-processing each demand Ti using a constrained diverse shortest path method to obtain a corresponding final route Ri′ until a stop criterion is satisfied;
• computing a final cost solution based on the final routes R′;
• and
• outputting the final routes R′ and the final cost solution,
• wherein the constrained diverse shortest path method includes:
• selecting a partial path pni, having parameters node(pni), cost(pni), violation_set(pni) and parent(pni) from one or more partial paths, where cost(pni) is minimal in comparison to costs associated with other partial paths, when a Heap value is not equal to null;
• if node(pni) is not equal to a termination node Zi, identifying a link adjacent to node(pni);
• creating a new partial path pni′ from node(pni) to the identified link;
• determining if the new partial path pni′ satisfies an optical transponder constraint;
• and
• updating the Heap value with the new partial path pni′ if the new partial path pni′ does satisfy the optical transponder constraint.