A network planning tool performs capacity planning at a systems level of traffic on a network, such as a fiber optic network, and a capacity management router performs network capacity management. For example, an Internet services communications company such as UUNET® may request to purchase use of a certain amount of network bandwidth on a fiber optic network for a period of time, such as use of an OC12 line from Fairfax, Va. to New York City for a one-year period beginning three months in the future. A network planning tool analyzes the network capacity already scheduled for that time period and finds the best path through the network that meets the request. Typically, the network planning tool attempts to find the path which meets the customer's demands but uses as little network resources as possible. A capacity planning router plans for future expansion of the network based on anticipated future usage. If the capacity planning router determines that future bandwidth demand Will overburden a particular part of the existing network, the network managers can consider adding new equipment to the network or “lighting” a fiber that is currently “dark.”
A communication network contains a set of network structures with different topologies, such as mesh, closed ring, open ring (also known as linear chain), and point-to-point. Typically, a network structure contains a set of nodes each of which are connected by links to one or more of the other nodes. A link may contain, for example, one or more fiber-optic cables. In a fiber optic system, a node may be a cross-connect system, which can route signals, and may also be an add-drop multiplexer (ADM), which provides a network multiplexing function and is used to add/drop signals for the links. A network structure is a set of ADM nodes that are connected with each other through one or more links. A link may carry multiple channel signals. Network structures are inter-connected with each other through a cross-connect node or switching node. For example, the Synchronous Optical Network (SONET) and Synchronous Digital Hierarchy (SDH) network contain a set of SONET network structures such as SONET ADM rings and SONET point-to-point systems. SONET network structures may be connected with each other through a SONET cross-connect system (SONET DCS). Another example of a communication network is an optical network containing a set of optical network structures. Each optical structure could be an optical ADM ring or optical point-to-point system. Optical network structures may be connected through an optical cross-connect system or optical switching system.
Each link in a network structure may be able to simultaneously carry different signals over different channels. In a network using time division multiplexing, several low-speed signals may be combined to form a single high-speed signal by dividing the high-speed signal up into different time slots. A SONET/SDH network is an example of a time division multiplexing network. Such a low-speed signal satisfies a Time Slot Assignment (TSA) constraint in the ADM node when the signal traverses the network structure in the same slot. If a single slot is unavailable throughout the entire route within that structure, the low-speed signal needs to change from one slot to another by dropping out of the high-speed signal, leaving the ADM node (as well as this structure), entering a slot exchange terminal (such as the cross-connect node), and adding back into a new slot of the high-speed signal at the ADM terminal. Due to the time slot assignment constraint, such a slot change external to an ADM node is considered an expensive “hair pin” solution for transmitting a signal through different slots within a structure. In a system that uses dense wavelength division multiplexing (DWDM), a number of signals each using a different wavelength may be sent though the same optical cable at the same time. Such a signal may be sent at the same wavelength across all fibers that it traverses within that optical structure, in which case it satisfies a wavelength continuity constraint, or it may switch wavelengths. Optical cross-connect nodes are equipped with wavelength conversion equipment and may be used to connect these optical structures.
A network may contain, for example, more than ten thousand nodes and twenty thousand links. Because there can be millions of possible paths through such a network, it may be difficult to find the shortest path from a source node to a destination node. This problem is made more complicated because, as discussed above, each link in the network may have multiple channels and there are additional cost and equipment availability issues involved where network traffic changes from one channel to another channel. Thus, finding the best path through a network requires taking into account the availability of the different channels in the network.
Previous network planning tools and capacity management routers used techniques such as linear programming or mixed integer programming to determine the least cost path through the network. Such planning and management tools used a two step approach to planning a least cost path that involved initially determining a path through the network without regard to the availability of the corresponding channels in the links selected. Only after choosing a candidate route from a source to a destination would these systems consider whether corresponding channels were available in the links chosen. Such systems did not consider channel availability when performing the first step (i.e., when determining a candidate route) because such a consideration would make the determination too complex.
It would be advantageous to have a network planning and management tool that efficiently considers the availability of channels and the cost of channel interchange when determining the best path through the network, thereby performing routing and channel assignment at the same time.