Restrictive costs in network systems

• US 7,042,846 B2
• Filed: 01/27/2001
• Issued: 05/09/2006
• Est. Priority Date: 01/27/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bauer, Daniel
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Nguyen, Van Kim T.
• Application Number:
  US09/771,091
• Publication Number:
  US 20010017845A1
• Time in Patent Office: 1,928 Days
• Field of Search: 370/218, 370238-2381, 370256-299, 370351-357, 370/360, 370/367, 370/382, 370/389, 370/392, 370/397, 370/395.31, 370/395.52, 370/400, 370/408, 709238-242, 455/455, 379272-273
• US Class Current: 370/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation

Abstract

Methods and apparatus are provided for generating a set of restrictive costs associated with directional paths between selected nodes in a group of nodes of a network system wherein each node in the group is connected by a link to at least one other node in the group, and each link has a pair of directional costs associated therewith such that each link can be considered as a pair of oppositely-directed, unidirectional links each of which extends from a source node to a destination node and has a said directional cost associated therewith. The method allows asymmetric costs, rather than merely symmetric costs, to be considered, and can be applied, for example, to generate the transition matrix for a PNNI peer group.

Claims

1. A method of generating a set of restrictive costs associated with directional paths between selected nodes in a group of nodes of a network system wherein each of said nodes in said group of nodes is connected by a link to at least one other of said nodes in said group, and each link has a pair of directional costs associated therewith such that said link can be considered as a pair of oppositely-directed, unidirectional links each of which extends from a source node to a destination node and has a said directional cost associated therewith, the method comprising:

(a) assigning a unique identifier to each of said selected nodes;

(b) selecting said unidirectional links in order of cost;

(c) for each of said unidirectional links selected, if a said identifier has previously been assigned to said source node for a said link and a said identifier has not previously been assigned to said destination node for a said link, assigning a said identifier to said destination node and any further nodes, which are reachable from said destination node by traversing said unidirectional links selected thus far, to which a said identifier has not previously been assigned;

(d) if said step (c) results in assignment to a said selected node of a said identifier not previously assigned to said selected node, storing said directional cost of the last-selected said unidirectional link as said restrictive cost for said directional path to said selected node from a said selected node to which said identifier was initially assigned in said step (a); and

(e) repeating said steps (b) to (d) at least until said restrictive cost has been stored for said directional paths between predetermined pairs of said selected nodes.

2. A method according to claim 1 wherein, in said step (a), said unidirectional links are selected in order of increasing cost.

3. A method according to claim 1 wherein, in said step (e), said predetermined pairs of selected nodes are all pairs of said selected nodes.

4. A method according to claim 1 wherein, in said step (c), any said identifier previously assigned to said source node and not said destination node is assigned to said destination node and said further nodes.

5. A method according to claim 1 wherein, in said step (c), said identifier previously assigned to said source node is assigned to said destination node and said further nodes only if said identifier has not previously been assigned to said destination node, and then only to said destination node and said further nodes.

6. A method according to claim 1 including generating a list of said unidirectional links sorted by order of cost, wherein said step (b) comprises selecting successive entries from said list.

7. A method according to claim 1 wherein said selected nodes are border nodes of said group, each of said border nodes which is connected to another of said nodes of said network system outside said group.

8. A method according to claim 7 wherein said group of nodes is a peer group of a PNNI hierarchical network.

9. A method of distributing topology data in a network system including a group of nodes which comprises a plurality of border nodes, each of said border nodes being connected to another of said nodes of said network system outside said group, and in which each of said nodes in said group is connected by a link to at least one other of said nodes in said group, and each of said links has a pair of directional costs associated therewith such that each of said links can be considered as a pair of oppositely-directed, unidirectional links each of which extends from a source node to a destination node and has a said directional cost associated therewith, the method comprising:

generating a set of restrictive costs associated with directional paths between said border nodes; and

transmitting said topology data indicative of said set of restrictive costs to at least one of said nodes of said network system outside said group;

wherein said set of restrictive costs is generated by;

(a) assigning a unique identifier to each of said border nodes;

(b) selecting said unidirectional links in order of cost;

(c) for each of said unidirectional links selected, if a said identifier has previously been assigned to said source node for said link and said identifier has not previously been assigned to said destination node for said link, assigning said identifier to said destination node and any further of said nodes, which are reachable from said destination node by traversing said unidirectional links selected thus far, to which said identifier has not previously been assigned;

(d) if said step (c) results in assignment to a said border node of a said identifier not previously assigned to said border node, storing said directional cost of the last-selected of said unidirectional links as said restrictive cost for said directional path to said border node from one of said border nodes to which said identifier was initially assigned in said step (a); and

(e) repeating said steps (b) to (d) at least until said restrictive cost has been stored for said directional paths between predetermined pairs of said border nodes.

10. A method according to claim 9 wherein said network system comprises a PNNI hierarchical network and said group of nodes comprises a PNNI peer group, wherein said method includes generating a complex node representation of said peer group from said set of restrictive costs, and wherein said topology data is indicative of said complex node representation.

11. A method of selecting a path for routing a call across a group of nodes in a network system wherein said group of nodes comprises a plurality of border nodes, each of said border nodes being connected to another of said nodes of said network system outside said group, each of said nodes in said group is connected by a link to at least one other of said nodes in said group, and each of said links has a pair of directional costs associated therewith such that each of said links can be considered as a pair of oppositely-directed, unidirectional links extending from a source node to a destination node having a said directional cost associated therewith, the method comprising:

generating a set of restrictive costs associated with directional paths between said border nodes; and

selecting a path for routing of said call via a pair of said border nodes in dependence on said set of restrictive costs;

wherein said set of restrictive costs is generated by;

(a) assigning a unique identifier to each of said border nodes;

(b) selecting said unidirectional links in order of cost;

(c) for each of said unidirectional links selected, if a said identifier has previously been assigned to said source node for said link and said identifier has not previously been assigned to a said destination node for said link, assigning said identifier to said destination node and any further of said nodes, which are reachable from said destination node by traversing said unidirectional links selected thus far, to which said identifier has not previously been assigned;

(d) if said step (c) results in assignment to one of said border nodes of a said identifier not previously assigned to one of said border nodes, storing said directional cost of the last-selected unidirectional link as said restrictive cost for said directional path to said border node from one other of said border nodes to which said identifier was initially assigned in said step (a); and

(e) repeating said steps (b) to (d) at least until said restrictive cost has been stored for said directional paths between predetermined pairs of said border nodes.

12. An apparatus for generating a set of restrictive costs associated with directional paths between selected nodes in a group of nodes of a network system wherein each of said nodes in said group is connected by a link to at least one other of said nodes in said group, and said link has a pair of directional costs associated therewith such that each of said links can be considered as a pair of oppositely-directed, unidirectional links each of which extends from a source node to a destination node and has a said directional cost associated therewith, said apparatus comprising memory for storing restrictive costs, and control logic configured to:

(a) assign a unique identifier to each of said selected nodes;

(b) select said unidirectional links in order of cost;

(c) for each of said unidirectional links selected, if a said identifier has previously been assigned to a said source node for a said link and said identifier has not previously been assigned to a said destination node for a said link, to assign said identifier to said destination node and any other of said nodes, which are reachable from said destination node by traversing said unidirectional links selected thus far, to which said identifier has not previously been assigned;

(d) if said step (c) results in assignment to a said selected node of a said identifier not previously assigned to said selected node, to store in said memory said directional cost of the last-selected of said unidirectional link as said restrictive cost for said directional path to said selected node from said selected nodes to which said identifier was initially assigned in said step (a); and

(e) to repeat said steps (b) to (d) at least until said restrictive cost has been stored for said directional paths between said predetermined pairs of said selected nodes.

13. An apparatus according to claim 12 wherein, in said step (a), said unidirectional links are selected in order of increasing cost.

14. An apparatus according to claim 12 wherein, in said step (e), said predetermined pairs of said selected nodes are all pairs of said selected nodes.

15. An apparatus according to claim 12 wherein said control logic is configured such that, in said step (c), any said identifier previously assigned to said source node and not said destination node is assigned to said destination node and said further nodes.

16. An apparatus according to claim 12 wherein said control logic is configured such that, in said step (c), said identifier previously assigned to said source node is assigned to said destination node and said further nodes only if said identifier has not previously been assigned to said destination node, and then only to said destination node and said further nodes.

17. An apparatus according to claim 12 wherein the said control logic is further configured to generate a list of said unidirectional links sorted by order of cost, and wherein, in said step (b), said control logic selects successive entries from said list.

18. An apparatus according to claim 12 wherein said selected nodes are border nodes of said group, each of which is connected to another of said nodes of said network system outside said group.

19. An apparatus according to claim 18 wherein said group of nodes is a peer group of a PNNI hierarchical network.

20. A said network system including said apparatus according to claim 12.

21. A device for connection in a network system as one node in a group of nodes of said system such that each of said nodes in said group is connected by a link to at least one other of said nodes in said group, and a said link has a pair of directional costs associated therewith such that each of said links can be considered as a pair of oppositely-directed, unidirectional links each of which extends from a source node to a destination node and has a said directional cost associated therewith, said device comprising:

control logic for generating a set of restrictive costs associated with directional paths between said selected nodes of said group; and

memory for storing said restrictive costs;

wherein said control logic is configured to generate said set of restrictive costs by;

(a) assigning a unique identifier to each of said selected nodes;

(b) selecting said unidirectional links in order of cost;

(c) for each of said unidirectional links selected, if a said identifier has previously been assigned to a said source node for a said link and said identifier has not previously been assigned to a said destination node for said link, assigning said identifier to said destination node and any further of said nodes, which are reachable from said destination node by traversing said unidirectional links selected thus far, to which said identifier has not previously been assigned;

(d) if said step (c) results in assignment to a said selected node of a said identifier not previously assigned to said selected node, storing said directional cost of the last-selected of said unidirectional links as said restrictive cost for said directional path to said selected node from a said selected node to which said identifier was initially assigned in said step (a); and

(e) repeating said steps (b) to (d) at least until said restrictive cost has been stored for said directional paths between said predetermined pairs of said selected nodes.

22. A network system comprising a plurality of said nodes, at least one of said nodes comprising said device according to claim 21.

23. A computer program product, readable by a processor of a device for connection in a network system as one node in a group of nodes of said system such that each of said nodes in said group is connected by a link to at least one other of said nodes in said group, and a said link has a pair of directional costs associated therewith such that each of said links can be considered as a pair of oppositely-directed, unidirectional links each of which extends from a source node to a destination node and has a said directional cost associated therewith, said product comprising a computer program code means executable by said processor to generate a set of restrictive costs associated with directional paths between a selection of said nodes of said group by performing the steps of:

(a) assigning a unique identifier to each of said selected nodes;

(b) selecting said unidirectional links in order of costs;

(c) for a said unidirectional link selected, if a said identifier has previously been assigned to a said source node for said link and said identifier has not previously been assigned to said destination node for said link, assigning said identifier to said destination node and any further of said nodes, which are reachable from said destination node by traversing said unidirectional links selected thus far, to which said identifier has not previously been assigned;

(d) if said step (c) results in assignment to a said selected node of a said identifier not previously assigned to said selected node, storing said directional cost of the last-selected of said unidirectional links as said restrictive cost for said directional path to a said-selected node from a said-selected node to which said identifier was initially assigned in said step (a); and

(e) repeating said steps (b) to (d) at least until said restrictive cost has been stored for said directional paths between said predetermined pairs of said selected nodes.