Multiplex communications – Network configuration determination
Reexamination Certificate
1999-08-27
2003-04-01
Vincent, David (Department: 2661)
Multiplex communications
Network configuration determination
C370S395310
Reexamination Certificate
active
06542473
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an arrangement and to a method for finding a route from a source node to a destination node in a transmission system at the lowest cost and in the quickest way possible.
BACKGROUND OF THE INVENTION
Various conceivable routes between a source node and a destination node can be compared in a routing procedure before the optimal route between said source node and destination node is determined in a transmission system. A number of such procedures are described in the literature.
EP-A 1 637 152 describes a method and an arrangement for speeding-up route selection in a packet switching network. The method comprises selecting certain network nodes as so-called backbone nodes, with the remaining nodes being so-called local nodes. The nodes chosen as backbone nodes are those nodes that have the most connections to other nodes in the network. The local nodes are coupled to at least one backbone node.
The backbone nodes and the local nodes are chosen at the time of configuring the network. The intention of this concept is to convert a normal network to an abstract hierarchical network having two levels, a backbone level and a local level, when calculating conceivable routes between two nodes.
One problem with this solution is that the choice of backbone nodes is critical for the speed at which routes are selected in the network. The subset in which the backbone nodes are located must be selected correctly in order for the choice of route to be effected as quickly and as effectively as possible.
SUMMARY OF THE INVENTION
In accordance with the Private Network-Network Interface (PNNI) specification, an ATM-network topology can be described with the aid of nodes and links. A Peer Group (PG) is a collection of nodes on a common level. A node that is located on level[i], where I>0, represents a PG on level[i−1].
A route in an ATM-network is defined as starting at a start node, a so-called source node, on level[
0
], and then either passing no nodes or several nodes via links between said nodes, and finally terminating at an end node, a so-called destination node. All nodes in the route may be on any level whatsoever, with the exception of the start node which is always on level[
0
]. Links from a node that is on level[i] to a node that is on level[j], where i>j≧0 is not permitted, because the link between two nodes must either be between two nodes on the same level or from a node that is on a lower level to a node that is on a higher level. Neither is it permitted for a route to pass a node more than once.
The possible routes from the source node to all destination nodes in the network are normally pre-calculated. These routes are saved in a data structure in order to reduce the time taken to establish a connection. In the event of a call, the source node shall chose an appropriate route from among all possible routes to the destination node in the data structure. The number of possible routes from a source node to a destination node can vary from one to any number whatsoever.
The present invention addresses a problem concerning the quickest and most effective manner in which possible routes from a start node to a destination node can be calculated.
The inventive method comprises two principle method steps. One or more so-called local routes are generated in a first main step, while one or more so-called global routes are generated in a second main step. In order to be able to generate the local routes and the global routes, it is necessary for the start node to have access to the topology of the network as seen outside itself. The generated local and global routes are saved in tables on different levels and said levels are coupled to the hierarchical levels in the network.
A local route on level[
0
] always starts at the start node or so-called source node and terminates at another node in the same Peer Group, PG. A local route on level[i], where i>0, always starts from a so-called ancestor node and terminates at another ancestor node in the same PG. All conceivable local routes can be generated separately for each level in the network and are saved in local routing tables. These local routing tables can be generated in any desired order, that is the local routing table for level[i] can be generated before level [j] irrespective of whether i>j or i<j. It is also conceivable for the local routing tables to be generated in parallel with respect to level.
A global route to a node on level[
0
] is the same as a local route to the same node on level[
0
], that is the route starts from the source node and terminates at an arbitrary node on level[
0
]. A global route to a node on level[i], where i>0, always starts at the source node on level[
0
] and terminates at said node on level[i]. The global route to a node on a level[i], where i>0 passes different levels in the network hierarchy.
Global routes to nodes on different levels in the network must be generated from a lower level in the network to a higher level therein, i.e. must begin from level[
0
] and then level[
1
], level[
2
] and so on. The reason why routes must be generated in this order is because when generating a global route to a node on level[i], where i>0, at least two routes are combined, a local route on level[i] and at least one global route on level[j], where j<i. The local route can be conceived as describing the route from the ancestor node to the destination node, whereas the global route can be conceived as describing the route within said ancestor node, i.e. the route from the source node to a boarder node. A boarder node is characterized by including a link to another Peer Group.
The generation of a global routing table[i], where i>0, always requires, on the one hand, information from the local routing table on level[i] and, on the other hand, information from one or more global routing tables[j], where i>j≧0. In other words, the generation of a global routing table[
2
] requires information from the local routing table[
2
], the global routing table[
0
] and the global routing table[
1
], or from the local routing table[
2
] and the global routing table[
1
], or from the local routing table[
2
], and from the global routing table[
0
].
A number of different methods can be conceivably applied for generating the local and global routing tables. The Dijkstra algorithm may be one such method. Different methods may be used to generate different routing tables. For instance, it is conceivable to use one method for generating a local routing table[i] and another method for generating a local table[j], where i≠j.
Accordingly, the present invention is aimed towards speeding-up the choice of route in a transmissions system, and then particularly in a telecommunications network, more particularly an ATM-network.
One advantage afforded by the present invention is that it gives a small overhead. This is because all local routes are generated only once and saved in local routing tables. Global routes can be generated with the aid of pointers to the local routes, in order to eliminate the risk of duplicate copies.
Another advantage afforded by the present invention is that the local routing tables can be generated in parallel.
Another advantage afforded by the present invention is that different methods can be used to generate local routing tables on different levels.
Still another advantage afforded by the present invention is that the model solely requires small modifications to the network structure, i.e. only a few routing tables will be affected by changes in the network.?
The invention will now be described in more detail with reference to preferred exemplifying embodi
Telefonaktiebolaget LM Ericsson (publ)
Vincent David
LandOfFree
Arrangement and a method relating to transmission systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arrangement and a method relating to transmission systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arrangement and a method relating to transmission systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3113409