Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Timing
Reexamination Certificate
2000-11-13
2004-12-28
Paladini, Albert W. (Department: 2125)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Timing
C370S242000, C714S004110
Reexamination Certificate
active
06836756
ABSTRACT:
FIELD OF INVENTION
The invention is in the area of communications network analysis. In particular, it is directed to simulation techniques for analyzing the availability or unavailability of end-to-end network connections or services.
BACKGROUND OF THE INVENTION
Capacity planning is an important function in designing and provisioning, communication networks. While network link and node capacities have been estimated for years, there has been relatively little study of availability, especially for large mesh network. Large mesh networks with multiple nodes and links and with arbitrary topology, are not very attainable to an exact analysis, especially for multiple failures. The multiple failure case means that by the time another failure occurs, repair processes for at least one previous failure have not completed, so that there may be more than one failure to deal with at any one time. Simple structured point-to-point or ring networks, for example, may have 1+1 or ring protection mechanisms for single failures, e.g., a single fiber cut at a time. The single failure case means that by the time a second failure occurs, repair processes for the first failure have completed so that there is no more than one failure to deal with at any one time. In typically route or geographically constrained networks of this kind, analytical and approximate techniques can give insight and understanding of service availability for each of any possible single failure. If, however, the network is unstructured like a mesh, if the number of nodes is large, and if multiple failures ate considered, the calculations, even if approximate, quickly become very complicated.
An article entitled “Computational and Design Studies on the Unavailability of Mesh-restorable Networks.” by Matthieu Cloqueuer and Wayne D. Grover on Proceedings of DRCN '2000, April 2000, Munich describes computational techniques of unavailability of a mesh network for single and multiple (mainly two) failures
As mentioned the above article, network availability generally refers to the ability of specific paths (also called connections) and not that of a whole network. Networks as a whole are never entirely up nor entirely down. “Network availability” can be defined as the average availability of all connections in a network but this gives less insight and comparative value than working with individual paths, or perhaps a selection of characteristic reference paths. Therefore, service availability between source and sink nodes is more meaningful to communications users who pay for such services.
For a quantitative study of network availability,
FIG. 1
illustrates service on a specific path as down (unavailable) in durations U
1
, U
2
, U
3
, . . . Un along the time axis. On the vertical axis (U-unavailability), ‘u’ indicates the service as unavailable, and ‘a’ as available. Service availability over a period T is the fraction of this period during which the service is up. The availability and unavailability of the network (or service) therefore are defined as follows:
Availability=lim ((T−&Sgr;UI)/T)=MTTF/(MTTR+MTTF)
Unavailability=1−Availabity−MTTR/(MTTR+MTTF)
Where, MTTR is the mean time to recover or repair, and MTTF is the mean time to failure. Recovery is by relatively fast means of network protection (in tens of milliseconds) or restoration (perhaps within a second) capabilities, whereas repair is much longer (typically hours).
The above referenced article discusses computational approaches for analyzing availability under a two-failure scenario. Such approaches are quite complex.
There is need for faster and easier techniques to determine service availability, especially in large mesh networks. Simulation provides tractability for large networks, and is also a good check on accuracy of simple, approximate or analytical methods. Thus, the time simulation technique is a relatively easier and faster process that complements more insightful analytical approaches to availability.
SUMMARY OF INVENTION
According to the basic concept, the present invention is a time simulation technique for determining the service availability (or unavailability) of end-to-end network connections (or paths) between source and sink nodes. In accordance with one aspect, the invention is directed to a simulation technique to determine either the network availability or unavailability.
In accordance with one aspect, the invention is directed to a time simulation method of determining service availability of a communications network having a plurality of nodes and a plurality of links. The same principles can be applied to mesh networks or to other networks, such as ring networks. The method includes steps of: (a) selecting a link between two network nodes; (b) performing a simulated link failure on the selected link; (c) selecting a connection between two network source and sink nodes; and (d) determining the unavailability and availability of the connection under the simulated link failure condition. The method further includes (e) of repeating (c) and (a) and (b); and (f) of summing the unavailability and availability of connections after each repeatedly until a predetermined number of connections have been selected, and until a simulated link failure has been performed on all links or until the summed unavailability and availability has been determined to converse, whichever is earlier, (A convergence process may be used, for example, if an operator deems there to be too many failure scenarios to consider exhaustively, or it is too time consuming to consider all failure scenarios exhaustively.) The predetermined number of connections of step (f) may be all connection or a predetermined subset of connections.
In accordance with a further aspect, of the invention is directed to a time simulation apparatus for determining service availability of a mesh or other communications network. The apparatus includes a network having a plurality of nodes and a plurality of links; the links having attributes relating to their failure, recovery and repair mechanisms. The apparatus further includes a mechanism for selecting one of the plurality of links based on the attributes; a failure/repair module for performing a simulated failure and repair on the selected link; a mechanism for selecting a connection between source and sink nodes; and an arithmetic mechanism for calculating availability of the selected connection.
Other aspects and advantages of the invention, as well as the structure and operation of various embodiments of the invention will become apparent to those ordinarily skilled in the art upon review of the following description of the invention in conjunction with the accompanying drawings.
REFERENCES:
patent: 5699403 (1997-12-01), Ronnen
patent: 6003090 (1999-12-01), Puranik et al.
patent: 6009079 (1999-12-01), Boye et al.
patent: 6327669 (2001-12-01), Croslin
patent: 234722 (2000-04-01), None
Nortel Networks Limited
Paladini Albert W.
LandOfFree
Time simulation techniques to determine network availability does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Time simulation techniques to determine network availability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Time simulation techniques to determine network availability will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3310470