Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
2000-03-10
2003-11-04
El-Hady, Nabil (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S223000, C709S224000, C709S227000, C709S238000, C709S239000, C709S240000, C709S241000, C709S242000, C370S237000, C370S238000, C370S255000, C370S351000
Reexamination Certificate
active
06643699
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method which facilitates reasoning about route selection in circuit- and packet-switched communication networks, and more particularly to networks represented by a blocking island (“BI”) abstraction.
Blocking Island abstractions facilitate reasoning concerning the different routes that a transmittable data stream might take. The BI is a part of a communication network in which routing demands on limited resources (which are sometimes referred to herein as bandwidths or bandwidth levels, the use of such specific terms hereinafter being intended as interchangeable with the more general term “restrictive costs”) not larger than Beta (“&bgr;”) is possible. Using the BI abstraction, it is possible to construct a hierarchy of simplified network graphs, called a Blocking Island Hierarchy (“BIH”). Each of these graphs, called Blocking Island Graphs (“BIGs”), is defined by the set of BIs for a particular &bgr;. In other words, a BI defines an equivalence class of potential paths with a bandwidth of up to &bgr;. B, an input parameter for a method of constructing a BIH, denotes the finite set of possible values for &bgr;. B is an ordered set. Consequently, the resulting BIH is a discrete abstraction of a communication network.
The usefulness of BIs (and the concepts built upon them) results from their fundamental properties, such as unicity, partitioning, bottleneck identification, route existence, route location and inclusion. However, the applicability of discrete BIHs is limited because of their limited precision due to the BIHs' discretization. For instance, networks like ATM and IP that provide circuits in an almost continuous range (due to a small cell or packet size) would require either discretization or a large set of B. The latter is impractical, as most &bgr;-BIGs would consume memory without providing insight—defeating the very purpose of constructing such an abstraction. Further ore, the routing method presented by Christian Frei and Boi Faltings in “A Dynamic Hierarchy of Intelligent Agents for Network Management”, Proceedings of the Second International Workshop on intelligent Agents for Telecom Applications (IATA '98), Paris, France, 1998, the content of which is incorporated by reference, is only applicable for demands with bandwidth requirements within the set B.
Resource management (including routing and connection admission control) in general plays an important role in network planning and control, as well as fault and performance management. These tasks take place at different time scales. Humans carry out a large share of long-term tasks, whereas computers execute usually real-time tasks. However, human intervention is also often necessary in the latter case to resolve failures and other difficult problems. These tasks involve often large amounts of data. For instance, a relatively static TDM network with 20 nodes and 40 links has already up to 1000 circuits. Short-lived circuits result in even more data. This large amount of data and their interdependencies guarantee that understanding a particular situation is a difficult and time consuming task (for both humans and computers).
Therefore, what is needed and is an object of the present invention is a means of creating and using an abstract, aggregated network-representation that suppresses irrelevant information and highlights the important information, thus reducing thinking time and search spaces of methods.
In addition, it is an object of the invention to make collaborative problem solving, involving humans and computers, feasible in more situations, which can be used to improve the quality of decisions.
Yet another object of the invention is to provide a means which generalizes the BIH abstraction, which overcomes the above-mentioned problems, and which can be applied to display the network status, to monitor the network, to determine routes, and to cost and price network usage.
Still another object of the invention is to provide a means of selecting routes which minimizes time and increases efficiency through the use of an abstract, aggregated network representation that suppresses irrelevant information and highlights important information, thus reducing thinking time and search spaces of methods.
Another object of the invention is to provide a concise graphical display of the possible routes or paths for different amounts of bandwidth &bgr;, or some other restrictive cost measure, between the vertices of a network.
SUMMARY OF THE INVENTION
A computerized method facilitates reasoning about path selection in communication networks represented by a blocking island (“BI”) abstraction. The method takes a network graph as an input and computes a data structure of a Blocking Island Contour Map (“BICM”) by performing the following two actions. In a first action, links are ordered according to their free capacity. In a second action, in order to produce a hierarchy of abstract nodes and links, the links are processed as ordered, by performing the following four acts. In a first act, if a currently-processed link (the current link) is connected to a currently-processed abstract node (the current node) at the same free capacity level, the current link is added to the currently-processed abstract node. If the currently-processed link is no connected then a new abstract node that includes the current link is constructed, to which the current abstract node is set. In a second act, the network-graph-level end-points of the current link that are not already contained in an abstract node are included in the current abstract node. In a third act, the abstract nodes that contain an endpoint of the current link (and are at a higher free-capacity level) are included in the current abstract node. In a fourth act, the links which are connected to the current abstract node and which share the other abstract endpoint are aggregated, wherein, if such a set of links already contains abstract links at the free-capacity level of the current abstract node, these abstract links are merged and the yet-to-be aggregated links are included into the merged abstract link; otherwise, a new abstract link at the free-capacity level of the current abstract node and containing the yet-to-be aggregated abstract links is created. Finally, the BICM data structure is returned and can either be displayed by the method described below or utilized for applications like routing.
In another feature of the invention, the BICM may be computed for visual display by traversing the blocking island hierarchy from the leaves to the roots and drawing a closed line around the nodes contained in the current abstract node if (1) the current abstract node contains one or more network graph nodes or (2) the current abstract node contains more than one abstract node. If the drawn closed line encloses nodes that do not belong to the current abstract node, the display submethod draws one or more closed lines (of the same kind as the above one) around these nodes.
In another feature of the method of the invention, an incremental submethod takes a BICM data structure, a network link and a new free capacity value and uses these as inputs to update the BICM data structure by performing four actions. In a first action, the modified link is moved to an abstract node at the new free capacity level wherein the abstract node is an existing abstract node if there exists a link connected to the endpoints of the modified link at the new level, wherein, if there are multiple such abstract nodes, they are merged and the abstract nodes that contain these abstract nodes are merged recursively; wherein, if there is a single abstract node at a higher capacity level than the new capacity value, this abstract node is split into two new abstract nodes, this process continuing with the father of the split abstract node recursively; and wherein, if there is no existing abstract node, a new abstract node is created and included in the abstract node tree at the appropriate position. In a second action, each of the endpoints of the
Cameron Douglas W.
Dougherty Anne V.
El-Hady Nabil
LandOfFree
Computerized method for computing the overall splitting cost... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computerized method for computing the overall splitting cost..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computerized method for computing the overall splitting cost... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3135161