Determining and provisioning paths within a network of communication elements

• US 7,289,456 B2
• Filed: 04/08/2002
• Issued: 10/30/2007
• Est. Priority Date: 04/08/2002
• Status: Expired

• Current Assignee: CommWorks Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Ferrer, Richard, Gupta, Sanyogita, Raheja, Raj C.
• Primary Examiner(s): Patel; Ajit
• Application Number:
  US10/118,187
• Publication Number:
  US 20030189919A1
• Time in Patent Office: 2,031 Days
• Field of Search: 370/401, 370/351, 370/352, 370/357, 370/345.1, 370/403, 370/404, 370/405, 370/252, 370/254, 370/241, 370/389, 370/386, 370/392
• US Class Current: 370/254
• CPC Class Codes: H04L 41/044 comprising hierarchical management structures
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play
• CPC Class Codes: H04L 41/0856 by backing up or archiving configuration information
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A graph of a network is created by efficiently modeling the network elements, and the network links and virtual trunks that interconnect these elements. The network elements are model as one or more routing nodes wherein each routing node represents part of an element or a set of one or more elements, and has the characteristic that any ingress and egress ports of the network element or network elements associated with the routing node can be interconnected. The network links and virtual trunks are both modeled as routing links, wherein routing links interconnect the routing nodes to create the graph of the network. The graph is subsequently used for determining routing paths through the network for the provisioning of virtual trunks and circuits.

Claims

1. A provisioning system for establishing a path within a network, said network being comprised of network links and network elements, said system comprising:

an inventory subsystem for modeling the network as a graph of nodes and links that interconnect the nodes;

a routing engine that uses the graph for determining the path between points in the network; and

a service activation system for invoking the routing engine to determine the path between the network points and for determining from the determined path and the network model a set of network element cross-connections to establish a virtual connection over said path;

wherein the links of said graph represent network links, wherein each node of said graph represents a partial network element, a single network element, or a group of network elements, wherein each partial network element, a single network element, or group of network elements represented by a given node has edge ports, and wherein any combination of edge ports that are associated with a given node and that are capable of being interconnected can be interconnected.

2. The system of claim 1 wherein the virtual connection is a virtual trunk and wherein the inventory subsystem further models the virtual trunk as a link of the graph.

3. The system of claim 1 further comprising an element adapter for translating the set of cross-connections determined by the service activation system to commands for establishing the virtual connection within the network.

4. The system of claim 1 further comprising a database for maintaining a status for each of the individual cross-connections of the virtual connection, and wherein the service activation subsystem determines from the database which individual cross-connections, needed in order to reestablish the virtual connection, have already been established.

5. A provisioning system for establishing a path within a network, said network being comprised of network links and network elements, said system comprising:

an inventory subsystem for modeling the network as a graph of nodes and links that interconnect the nodes;

a routing engine that uses the graph for determining the path between points in the network; and

a service activation system for invoking the routing engine, wherein the path determined by the routing engine is an initial path, wherein the routing engine additionally determines one or more secondary paths upon being invoked by the service activation system, wherein the service activation system chooses from among the initial and secondary paths a preferred path, and wherein the service activation system determines a set of network element cross-connections to establish a virtual connection over said preferred path;

wherein the links of said graph represent network links, wherein each node of said graph represents a partial network element, a single network element, or a group of network elements, wherein each partial network element, single network element, or group of network elements represented by a given node has edge ports, and wherein any combination of edge ports that are associated with a given node and that are capable of being interconnected can be interconnected.

6. The system of claim 5 wherein if the preferred path cannot be established, the service activation system chooses from among the initial path and the one or more secondary paths another path to establish the virtual connection.

7. The system of claim 5 wherein the service activation system considers bandwidth of the initial and secondary paths when choosing the preferred path.

8. The system of claim 5 wherein the initial path between points in the network is between a source node and a destination node, and wherein the one or more secondary paths are determined by determining paths from the source node to the destination node'"'"'s neighboring nodes.

9. A method for creating a graph of a network used for network routing, said network comprising network elements and network links, said method comprising the steps of:

determining a routing model associated with the network element, wherein the routing model indicates how ports of the network element can be interconnected among themselves and other network elements;

based on the determined routing model, determining for the network element whether the element should be associated with a plurality of network elements and represented collectively as a routing node, wherein routing nodes represent a partial network element or one or more network elements and have the characteristic that any edge ports of the represented partial network element or one or more network elements that are capable of being interconnected can be interconnected;

if the network element should be associated with a plurality of network elements, determining if a routing node has been created for the plurality of network elements, and if no routing node has been created, determining, based on the network element and its corresponding routing model, if a routing node should be created;

if the network element should not be associated with a plurality of network elements, determining, based on the network element'"'"'s routing model, whether the network element should be represented as one routing node or a plurality of routing nodes, and creating the one or the plurality of routing nodes;

representing each network link as a routing link, wherein a routing link interconnects routing nodes; and

associating each routing link with two routing nodes, thereby creating the graph of the network, wherein the two associated routing nodes represent the two network elements interconnected by the network link represented by the muting link.

10. The method of claim 9, wherein the network further comprises one or mare virtual trunks, said method further comprising the steps of:

representing each virtual trunk as a routing link; and

associating each muting link representing a virtual trunk with two routing nodes.

11. A method for determining a path between points within a network, said network comprising a plurality of elements and a plurality of network links, said method comprising the steps of:

modeling the plurality of elements as one or more routing nodes wherein each routing node represents a partial element, a single element, or a set of elements, wherein each partial element, single element, or a set of elements represented by a given routing node has edge ports, and wherein any combination of edge ports that are associated with a given routing node and that are capable of being interconnected can be interconnected;

modeling each physical link as a routing link, wherein routing links interconnect routing nodes; and

determining the path by determining a set of routing nodes and routing links that interconnect the points.

12. The method of claim 11 wherein the network further comprises one or more virtual connections, said method further comprising the step of modeling each virtual connection as a routing link.

13. The method of claim 11 wherein said partial elements, single element, or set of elements represented by a given routing node is managed by a common management entity.

14. The method of claim 11 wherein the element modeling step models an element comprising a plurality of interconnected chassis as one routing node.

15. The method of claim 11 wherein the element modeling step models a set of elements interconnected in a daisy chain as one routing node.

16. The method of claim 11 wherein the element modeling step models an element comprising a plurality of independent chassis as a plurality of routing nodes, each routing node corresponding to a chassis.

17. The method of claim 11 further comprising the step of determining from the determined set of routing nodes and routing links a set of network element cross-connections to provision a virtual connection over said path.

18. The method of claim 17 wherein the provisioned virtual connection is a virtual trunk, said method further comprising the step of modeling the provisioned virtual trunk as a routing link.

19. The method of claim 11, when,in the determined path is an initial path, said method further comprising the steps of:

determining one or more secondary paths; and

choosing from among the initial and secondary paths a preferred path.

20. The method of claim 19 wherein bandwidth is considered when choosing the preferred path.

21. The method of claim 19 wherein the initial path between points in the network is between a source muting node and a destination routing node, and wherein the one or more secondary paths are determined by determining paths from the source node to the destination node'"'"'s neighboring nodes.

22. A method for determining a path between points within a network, said network comprising a plurality of elements and a plurality of network links, said method comprising the steps of:

modeling the plurality of elements as one or more routing nodes wherein each routing node represents a partial element, a single element, or a set of elements, wherein each partial element, single element, or a set of elements represented by a given routing node has edge ports, and wherein any combination of edge ports that are associated with a given routing node and that are capable of being interconnected can be interconnected;

modeling each physical link as a routing link, wherein routing links interconnect routing nodes;

determining the path by determining a set of routing nodes and routing links that interconnect the points;

determining from the determined set of routing nodes and routing links a set of network element cross-connections to provision a virtual connection over said path;

provisioning the cross-connections of the virtual connection;

maintaining the status of each cross-connection, said status indicating whether the cross-connection was successfully or unsuccessfully provisioned; and

if the virtual connection is not successfully provisioned because one or more cross-connections failed, attempting to provision the failed cross-connections in order to re-provision the virtual connection.

23. A provisioning system for establishing a path within a network, said network being comprised of network links and network elements, said system comprising:

an inventory subsystem for modeling the network as a graph of nodes and links that interconnect the nodes; and

a routing engine that uses the graph for determining the path between points in the network;

wherein the links of said graph represent network links, wherein each node of said graph represents a partial network element, a single network element, or a group of network elements, wherein each partial network element, single network element, or group of network elements represented by a given node has edge ports, and wherein any combination of edge ports that are associated with a given node and that are capable of being interconnected can be interconnected.

24. The system of claim 23 wherein the network further comprises virtual connections and wherein the links of the graph further represent said virtual connections.

25. The system of claim 23 wherein said partial network element, single network element, or group of network elements represented by a given node is managed by a common management entity.

26. The system of claim 23 wherein a network element comprising a plurality of interconnected chassis is represented as one node.

27. The system of claim 23 wherein a set of network elements interconnected in a daisy chain is represented as one node.

28. The system of claim 23 wherein a network element comprising a plurality of independent chassis is represented as a plurality of nodes, each node corresponding to a chassis.