Method of forming routing data

Details Method of forming routing data Method of forming routing data

1999-04-08

2001-12-25

Hsu, Alpus H. (Department: 2662)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S255000, C370S400000, C709S238000

Reexamination Certificate

active

06333918

ABSTRACT:

BACKGROUND OF THE INVENTION
When links are routed in communications networks such as narrowband or ATM networks (ATM=Asynchronous Transfer Mode), for example, there are basically two alternative approaches, namely the “hop-by-hop routing method”, in which each transit node itself decides how to the forward the connection set-up request, and source routing in which the source node S (to which the subscriber initiating the connection request is connected) adds a route description to the connection set-up message, which description has to be followed by the transit nodes in order to arrive at the destination node D (to which the requested terminating subscriber is connected). This route description information is also referred to as routing information or source routing information or, specifically in the case of ATM-PNNI networks, is referred to as DTL stack (=stack of Designated Transit List information elements).
Said ATM communications networks can be organized into numerous subnetworks (“peer groups”), comprising physical switching nodes and physical connecting lines (“physical links”). According to the PNNI protocol, the nodes of a (hierarchically lowest) peer group determine from among them a so-called representative node (“peer group leader”) which represents the entire peer group in the form of a single, logical, model-like node (referred to as “logical group node” or else “parent node”) in a peer group which is of a hierarchically higher level.
A hierarchically higher peer group is formed, comprising a plurality of such parent nodes and the connecting lines which interconnect these in a model-like fashion, in which case a model-like connecting line (also referred to as “higher-level logical link”) between two such parent nodes thus represents all those physical connecting lines which connect in each case two physical boundary nodes from the hierarchy region of the two adjacent parent nodes and, in doing so, have assigned to them, thanks to administrative specifications and an agreement algorithm, the same code in each case, referred to as aggregation token.
The hierarchy can continue recursively in further hierarchy levels: a peer group leader selection can also take place again in the hierarchically higher peer group. The peer group leader which is selected here represents again the entire hierarchy region established under it in a peer group which is hierarchically at the next highest level, as if this hierarchy region were a single node. In this peer group there are also logical, model-like connecting lines which are formed repeatedly, as described above.
A hierarchical model-like network in accordance with the PNNI protocol (for illustration purposes: 3-dimensional grid) is completed by adding further, purely logical connecting lines, the so-called “uplinks” which each connect, in accordance with the PNNI protocol, two nodes to one another (physically—if the node at the lower end of the uplink is a physical node—or logically) from peer groups which are at hierarchically different levels.
Thus, an uplink (also referred to as “initial uplink”) leads from the boundary node of a hierarchically lowest peer group, which node is connected to a boundary node in an adjacent peer group, to a representative node, the so-called “upnode”, i.e. to that representative node “ancestor node” (i.e. parent node, grandparent node or great . . . grandparent node) of the adjacent boundary node which is a directly neighboring node of precisely one specific ancestor node of the boundary node on this side in a common peer group of a hierarchically higher level. Such an (initial) uplink results in all the ancestor nodes (of the boundary node on this side) which however each belong to a hierarchically lower peer group than the aforesaid common hierarchically higher peer group, also each contribute an uplink (also referred to as “induced uplink”) to the aforesaid upnode [lacuna] the hierarchy pattern.
The hierarchical structure, which is ultimately based on corresponding configuration data of the individual nodes, can be handled very flexibly here. In particular, the individual nodes of a great . . . grandparent peer group can have different numbers of subhierarchy levels together with the relevant peer groups.
The exchange, in accordance with PNNI protocol, of data packets, “hello packets” and PNNI topology status data packets (“PNNI topology state packets”—PTSPs) via so-called routing control channels ensures that each physical switching node of a hierarchically lowest peer group acquires the same knowledge of the topology of this group and of all the peer groups, including all the uplinks, which are located at a hierarchically higher level than it in the hierarchy, and also the same knowledge of the usage factor of all the nodes and connecting lines contained in it as well as the same knowledge of its properties (accessibility, capabilities, features, costs).
The knowledge of the topology which is acquired can be stored in a node in the form of a graph G
1
. In it, the respective current switching node (which has produced this graph G
1
for itself) is not marked in particular as the source node S.
If a terminal which is connected to the source node then requests to be connected to the terminal of a specific destination address, the data in the graph G
1
which are exchanged per PNNI routing protocol make it possible to determine that destination node D which indicates the accessibility of the destination terminal and at the same time belongs to the hierarchically lowest possible peer group. On the basis of the graph G
1
it is possible to determine, in terms of a suitable minimization criterion, the best route from the starting node S to the destination node D.
The ATM Forum Technical Committee Private Network Node Interface (PNNI) in the specification, version 1.0, Annex H does not, however, provide the possibility of also including in the route search advantageous bypasses via one or more peer groups with a return to the peer group which has already been passed through, and as a result it is in the meantime not possible to fulfill a switching request appropriately.
These problems also occur in other communications networks, for example narrowband networks with source routing for implementing a PSTN (Public Switched Telephone Network). The topology information is evaluated only to the extent that routes are determined with the avoidance of bypasses.
SUMMARY OF THE INVENTION
The object of the method according to the invention consists in determining a route, while taking into account the topology information and the communications conditions relating to the nodes and connecting lines, and converting the route into routing information in such a way that the largest possible variety of routes can be taken into account.
The switching nodes are assigned to subnetworks and interconnected to one another as desired. The subnetworks here can be individual local communications networks of different service providers or groups of switching nodes of a superordinate communications network. In a source switching node there is topology information available on the node's own subnetwork and on the inter-connection with the subnetworks which are stored in the node or in a routing server. In addition, the communications conditions which are required for the communications connection to be set up are available to the source switching node.
By referring to the topology information, a subset of switching nodes and connecting lines which satisfies the communications conditions is selected and a route to the destination switching node is determined. Included in this process is a route which, in the direction from the source switching node to the destination switching node, leaves at least one subnetwork once and returns to said subnetwork in the further course of the route. The routing information is then formed from the route which is determined. The formation of the routing information is carried out either in the switching node itself or in external devices, for example routing s

Affiliated with

Also associated with

Rating

Method of forming routing data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of forming routing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of forming routing data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2602072