Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-05-22
2001-10-16
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S441000, C345S442000, C345S111000, C345S111000
Reexamination Certificate
active
06304273
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of the graphical representation of networks, and more precisely to a process for depicting, within such a representation, a set of paths which are available in order to undertake a routing between two nodes of the network.
The networks represented may be of very diverse kinds. The example more particularly envisaged by the Applicant concerns telecommunication networks. Other examples would be energy transport or fluid distribution networks, etc.
In a natural way, the graphical representation of such a network comprises symbols designating nodes of the network (for example, switches in the case of a telecommunication network), which are connected together by arcs designating elementary links existing between nodes of the network (for example, bundles of cables, optical or radio-relay fibers, etc.).
When the network comprises many nodes and many links, this very frequently being the case, its representation becomes complex and difficult to read. In particular, the depicting of the paths available to transport a stream (of information, of signals, of energy, of fluid etc.) from one node to another is a problem which is difficult to solve in a clear and unambiguous manner.
It is just such a set of paths available for transporting a stream from a first node to a second node of the network which it is proposed to depict according to the invention. This set of paths obeys the following topological rules:
each path of the set includes, between the first node and the second node, an elementary link or a succession of elementary links each having a respective departure node and a respective arrival node,
the first node constitutes the departure node of an elementary link of each path,
the second node constitutes the arrival node of an elementary link of each path, and
each arrival node of an elementary link of a path of the set other than said second node constitutes the departure node of another elementary link of said path.
Moreover, it may be necessary to display certain routing rules on the depiction of the set of paths, these rules applying within this set. Among these rules may be mentioned load sharing as well as the modes of behavior to be adopted in the event of an overflow on a link.
FIG. 1
illustrates a conventional way of representing a set of paths between a node A and a node B together with such rules. In this example, the normal route between nodes A and B consists in taking the direct link AB. However, in the event of an overflow of capacity on this direct link, the streams to be routed from node A to node B may take either the path AT
1
B, or the path AT
2
B. The sharing of the overflow load between the elementary links AT
1
and AT
2
is represented by the ellipse e drawn around the arcs designating these two elementary links, and the arrow f emanating from the arc AB is an overflow indicator which makes it possible to depict the appropriate behavior in the event of an overflow on the link AB.
The depiction technique illustrated by
FIG. 1
has several practical limitations. For certain arrangements of the nodes within the representation, the route is incomprehensible. For example, in
FIG. 1
, if node B is placed between nodes T
1
and T
2
, the representation of the route is no longer comprehensible. However, the option of modifying the position of the nodes in order to avoid such ambiguities is not always available: such is the case, in particular, when the position of the nodes reflects the geography of the sites of the network. Furthermore, this depiction technique does not bind a choice of route to the node on exit from which this choice is made, but to the arcs representing the links concerned. This makes it difficult to track the paths taken by the stream from end to end. Another limitation is that it is not possible to display clearly the fact that a choice of route on exiting a node can be conditioned by the link via which the stream has reached this node.
An object of the present invention is to improve the techniques for depicting paths within graphical representations of networks by simultaneously endowing them with greater visibility and larger richness of representation.
SUMMARY OF THE INVENTION
The invention thus proposes a process, as defined above, for depicting a set of paths, comprising the following steps: surrounding each symbol designating a departure node with at least one respective perimeter; and placing a respective flag at the intersection between each arc designating an elementary link of the set of paths and a perimeter surrounding the symbol designating the departure node of said elementary link.
Each perimeter surrounding a departure node manifests a choice of route on exit from this node. For example, a sharing of the load between two elementary links having this node as departure node will be readily depicted by the presence of a flag at the intersections between this perimeter and the arcs designating these elementary links.
The routing priorities and the overflow indicators can be depicted by placing several concentric perimeters around the nodes concerned. A preferred mode of execution of the process according to the invention thus allows the depiction of a set of paths such that at least one node of the network constitutes a departure node common to several elementary links among which at least one main link has priority over at least one auxiliary link, with the aid of the following operations: surrounding the symbol designating said common departure node with two concentric perimeters; placing the flag relating to each main link having said common departure node at the intersection between the arc designating said main link and one of the concentric perimeters; and placing the flag relating to each auxiliary link having said common departure node at the intersection between the arc designating said auxiliary link and the other concentric perimeter.
This procedure is easily generalized to any number of levels of priority on exit from the common departure node. It is sufficient to draw as many concentric perimeters as there are levels of priority, for example circles whose diameter increases (or decreases) with the priority. An overflow of capacity is then shown by the transition from one circle to that of immediately greater (or lesser) diameter. Hence, this gives great flexibility in the representation of priorities and overflows of capacity. The clarity of this representation is achieved by means of graphical elements which are very simple to use and to depict, and it is not affected by the relative positions of the nodes concerned, unlike the depiction technique illustrated by FIG.
1
.
Advantageously, the invention also allows the representation of routing constraints such as upstream constraints. It is thus possible to prevent the depicting of a set of paths from being automatically accompanied by the depicting of other paths which do not belong to this set.
A node is said to be the subject of an upstream constraint if a choice of route on exit from this node is conditioned by the elementary link via which the stream has reached this node. In terms of defining the set of paths to be depicted, an upstream constraint condition corresponds to the fact that the set of paths comprises at least first and second paths passing through the same constrained node and each including a respective elementary arrival link whose said constrained node constitutes the arrival node and a respective elementary departure link whose said constrained node constitutes the departure node, and no path of the set to be depicted simultaneously includes the elementary arrival link of the first path and the elementary departure link of the second path.
A flag of another type is now placed on a perimeter surrounding the symbol designating the constrained node and having a flag at the intersection with the arc designating the elementary departure link of the second path, at the intersection with the arc designating the elementary arrival link of the second path, and no flag of the oth
Chung Daniel J
France Telecom
Luu Matthew
Marshall Gerstein & Borun
LandOfFree
Process for depicting paths within a graphical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for depicting paths within a graphical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for depicting paths within a graphical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2608679