Connectivity matrix-based multi-cost routing

Claim 3

The method of claim 1, further including the steps of: determining a multi-cost requirement indicative of the multi-cost of said cost functions required to satisfy a routing request between a pair of nodes; comparing said multi-cost requirement to said summation ordered n-tuples between said pair of nodes; and determining that a path exists for routing between said pair of nodes if said summation ordered n-tuples between said pair of nodes satisfies said multi-cost requirement.

Claim 4

The method according to claim 1, wherein the nodes are interconnected by links; said step of defining cost functions includes defining a cost function which is a Boolean representation of functionality supported by the network between each said pair of nodes; and each n-tuple of said connectivity matrix includes an element indicative of the functionality, in said ordering of functionality, available directly between each said pair of nodes.

Claim 5

The method according to claim 3, wherein said step of prioritizing each of said cost functions includes defining a mask of a desired functionality of a route between a pair of nodes of the network; said step of defining a generally additive operator includes assigning an operator MAND for said Boolean representation defined in terms of said mask of desired functionality of a route; and said step of deriving said shortest path matrix includes deriving said summation n-tuples such that each summation n-tuple includes an element indicative of the fulfillment of said desired functionality available over said shortest path between each said pair of nodes.

Claim 6

The method of claim 1, wherein said step of deriving a shortest path matrix includes the step of taking the generally additive sum of said cost functions over a shortest path between each pair of nodes using Floyd's Algorithm.

Claim 7

The method of claim 1, wherein said step of deriving a shortest path matrix includes the step of taking the generally additive sum of said cost functions over a shortest path between each pair of nodes using Dijkstra's Algorithm.

Claim 8

The method of claim 1, further including the steps of: determining a multi-cost requirement indicative of the multi-cost required to satisfy a routing request between a pair of nodes; determining at least one primary path and any secondary paths between said pair of nodes which are used to satisfy said multi-cost requirement.

Claim 9

The method of claim 7, wherein said step of determining at least one primary path and any secondary paths includes the steps of: defining said pair of nodes to include a source node and a destination node; determining each adjacent node in the network directly connect to said source node; defining a source-isolated connectivity matrix including ordered n-tuples representing the multi-cost directly between each pair of nodes in the network excluding said source node; deriving a criterion cost as a shortest path between each said adjacent node and said destination node with respect to said composite multi-cost function by applying said composite multi-cost function to said source-isolated connectivity matrix using said generally additive operator and said ordering; deriving a composite constraint cost as a shortest path between each adjacent node and said destination node with respect to each individual cost function by applying each individual cost function to said source-isolated connectivity matrix using said generally additive operator and said ordering of said individual cost function; defining link least-criterion-costs between said source node and said destination node, each being the generally additive sum of said cost functions of each respective link from said source node to a respective one of said adjacent nodes and said criterion cost from said respective one of said adjacent nodes to said destination node; defining link composite-constraint-costs between said source node and said destination node, each being the generally additive sum of said cost functions of each said respective link from said source node to said respective one of said adjacent nodes and said composite constraint cost from said respective one of said adjacent nodes to said destination node; ordering said link least-criterion-costs; defining said at least one primary path as a route between said source node and said destination node having said link least-criterion-costs with the smallest multicost; and defining said secondary paths as the remaining routes between said source node and said destination node.

Claim 10

The method according to claim 8, wherein each said secondary path is prioritized in inverse order with respect to the multi-cost of said link least-criterion-costs associated with each said secondary path.

Claim 11

The method according to claim 8, wherein said step of ordering said link least-criterion-costs includes determining said order by comparing associated link composite-constraint-costs if said link least-criterion-costs for two paths are the same.

Claim 12

The method according to claim 8, further including the step of comparing said multi-cost requirement to said link least-criterion-costs, and if said multi-cost requirement is greater than or equal to said link least-criterion-costs for each individual cost component, determining that there is a path from said source node to said destination node which satisfies said multi-cost requirement.

Claim 13

The method according to claim 11, wherein said step of comparing said multi-cost requirement to said link lease-criterion-costs further includes, if at least one element of said multi-cost requirement is less than a corresponding one of said link least-criterion-costs for each path, but there is at least one path wherein said multi-cost requirement is greater than or equal to said one of said link composite-constraint-costs for each individual cost function, then there may or may not be a path which satisfies said multi-cost requirement for said at least one element while still satisfying all other elements of the multi-cost requirement.

Claim 14

The method according to claim 12, wherein said step of comparing said multi-cost requirement to said link least-criterion-costs further includes, if said multicost requirement is less than one of said link composite-constraint-costs for at least one individual element for each path, then there is no successful path for satisfying said multi-cost requirement between said source node and said destination node.

Claim 15

The method of claim 9, wherein said step of routing includes routing over the lowest priority secondary path which satisfies said multi-cost requirement.

Claim 16

The method according to claim 1, wherein the nodes are interconnected by links; each node and/or link may or may not support one or more service types generally available to the network; said step of defining cost functions includes defining a cost function which is an ordering of said service types with respect to each one of said service types between each said pair of nodes; and said step of defining a connectivity matrix includes defining a plurality of connectivity matrices, each corresponding to a desired one of said service types, each n-tuple of said connectivity matrix including an element indicative of service type available between each said pair of nodes.

Claim 17

The method according to claim 15, wherein said step of defining a cost function which is an ordering of said service types with respect to each one of said service types includes assigning a value the magnitude of which is directly related to the desirability of said service types with respect to said one service type; said step of defining a generally additive operator includes assigning an operator MAX for said service type cost function; and said step of deriving said shortest path matrix includes deriving said summation n-tuples such that each summation n-tuple includes an element indicative of the most desirable one of said service types with respect to said one of said service types available over said shortest path between each said pair of nodes.

Claim 18

The method of claim 16, wherein: said step of defining cost functions further includes defining a cost function which is indicative of the number of links traversed between a pair of nodes; said step of defining a connectivity matrix includes defining a plurality of connectivity matrices, each corresponding to one of said service types, where m is the number of service types, each n-tuple of said connectivity matrix including an element indicative of the number of links traversed with respect to each service type between each said pair of nodes, where each of said links traversed is assigned a weighted service-related value of 1, H+1, (H+1) 2 , . . . , (H+1) m-1 , with respect to said ordering of said service types, where H is the maximum allowed number of links traversed of all types between a source node and a destination node.

Claim 19

The method according to claim 1, wherein the nodes are interconnected by links; each node and/or link may or may not be part of a virtual private network; said step of defining cost functions includes defining a cost function which is indicative of the ability to route traffic associated with said virtual private network; and each n-tuple of said connectivity matrix includes an element indicative of the ability to route traffic associated with said virtual private network directly between each said pair of nodes.

Claim 20

The method of claim 18, wherein said step of deriving said shortest path matrix includes deriving said summation n-tuples such that each summation n-tuple includes an element indicative of the ability to route traffic associated with said virtual private network over said shortest path between each said pair of nodes.

Claim 21

The method of claim 9, wherein said step of routing includes routing over said at least one primary path or a highest priority secondary path which satisfies said multi-cost requirement.