Method for path selection in a network

A method of finding a path in a network comprising:

• creating a path table, wherein:
• said path table comprises a first number of rows and a second number of columns,
• said network comprises a plurality of nodes and a plurality of links,
• each one of said plurality of nodes is coupled to at least one other of said plurality of nodes by at least one of said plurality of links, and
• said path begins at a root node of said plurality of nodes;
• processing each row in a first column of said second number of columns, wherein said processing said each row in said first column of said second number of columns comprises:
• for said each row in said first column of said second number of columns, wherein a selected node of said plurality of nodes corresponds to said row in said first column,
• if said selected node is a neighbor of said root node,
• storing a first link cost in a first cost entry, wherein
• said first link cost is a link cost of a first one of said plurality of links,
• said first one of said plurality of links is between said root node and said selected node, and
• said first cost entry is a cost entry of said row in said first column,
• storing a root node identifier in a first previous node entry, wherein said root node identifier represents said root node and said first previous node entry is a previous node entry of said row in said first column, and
• storing a node identifier representing said selected node in a storage area, else,
• storing a maximum cost value in said first cost entry, and
• storing a null value in said first previous node entry
• said processing each row in said first column of said second number of columns resulting in said first column containing corresponding first connectivity information;
• and
• processing each remaining column, wherein
• said each remaining column is a one of said second number of columns other than said first column, and
• said processing each remaining column resulting in said first column containing corresponding subsequent connectivity information.

A method of finding a path in a network comprising:

• creating a path vector, wherein:
• said path vector comprises a first number of rows,
• said network comprises a plurality of nodes and a plurality of links,
• each one of said plurality of nodes is coupled to at least one other of said plurality of nodes by at least one of said plurality of links, and
• said path begins at a root node of said plurality of nodes;
• for a first hop of a maximum number of hops, processing each row in said first number of rows for said first hop, a selected node of said plurality of nodes corresponding to said row wherein said processing each row in said first number of rows for said first hop comprises:
• for said first hop of said maximum number of hops,
• for each row in said first number of rows, a selected node of said plurality of nodes corresponding to said row,
• if said selected node is a neighbor of said root node,
• storing a first link cost in a first cost entry, wherein
• said first link cost is a link cost of a first one of said plurality of links,
• said first one of said plurality of links is between said root node and said selected node, and
• said first cost entry is a cost entry of said row, and
• storing a node identifier representing said selected node in a
• storage area,
• else
• storing a maximum cost value in said first cost entry, and
• for each remaining hop of said maximum number of hops, processing said each row in said first number of rows for said each remaining hop.

A computer system comprising:

• a processor coupled to a network, wherein said network comprises a plurality of nodes and a plurality of links and each one of said plurality of nodes is coupled to at least one other of said plurality of nodes by at least one of said plurality of links;
• computer readable medium coupled to said processor;
• and
• computer code, encoded in said computer readable medium, configured to cause said processor to find a path in said network by virtue of being configured to cause said processor to:
• generate at least one path cost data set, said path cost data set representing a path cost between a root node of said nodes and destination node of said nodes, wherein said path begins at said root node and ends at said destination node;
• and
• access said at least one path cost data set wherein
• said generating and said accessing are performed in such a manner that a minimum-hop path and a minimum-cost path can be determined from said at least one path cost data set,
• said minimum-hop path represents a path between said root node and said destination node having a minimum number of hops, and
• said minimum-cost path represents a path between said root node and said destination node having a minimum cost and at least a requested bandwidth and
• said minimum cost comprises a cost of a bandwidth along at least a portion of said path.

A computer program product for finding a path in said network, wherein said network comprises a plurality of nodes and a plurality of links and each one of said plurality of nodes is coupled to at least one other of said plurality of nodes by at least one of said plurality of links and said computer program product is encoded in computer readable media and comprising:

• a first set of instructions, executable on a computer system, configured to generate at least one path cost data set, said path cost data set representing a path cost between a root node of said nodes and destination node of said nodes, wherein said path begins at said root node and ends at said destination node;
• and
• a second set of instructions, executable on said computer system, configured to access
• said at least one path cost data set wherein said generation and said access are performed in such a manner that a minimum-hop path and a minimum-cost path can be determined from said at least one path cost data set,
• said minimum-hop path represents a path between said root node and said destination node having a minimum number of hops and at least a requested bandwidth,
• said minimum-cost path represents a path between said root node and said destination node having a minimum cost, and at least a requested bandwidth, and
• said minimum cost comprises a cost of a bandwidth along at least a portion of said path.

A method comprising:

• generating at least one path cost data set, wherein,
• said path cost data set stores a path cost of a path between a root node and destination node,
• said path is in a network,
• said network comprises a plurality of nodes and a plurality of links,
• each one of said plurality of nodes is coupled to at least one other of said plurality of nodes by at least one of said plurality of links, and
• said nodes comprise said root node and said destination node;
• storing said at least one path cost data set in a data structure, wherein
• a first attribute of said data structure represents a hop count of said path, and
• a second attribute of said data structure represents each node of said path;
• and
• accessing said at least one path cost data set, wherein,
• said generating and said accessing are performed in such a manner that a minimum-hop path and a minimum-cost path can be determined from said at least one path cost data set,
• said minimum-hop path represents a path between said root node and said destination node having a minimum number of hops, and at least a requested bandwidth, and
• said minimum-cost path represents a path between said root node and said destination node having a minimum cost and at least a requested bandwidth, and
• said minimum cost comprises a cost of a bandwidth along at least a portion of said path.