Complex node representations in PNNI systems

Details Complex node representations in PNNI systems Complex node representations in PNNI systems

2001-01-30

2004-05-04

Pezzlo, John (Department: 2662)

Multiplex communications

Network configuration determination

Using a particular learning algorithm or technique

C370S252000, C370S463000

Reexamination Certificate

active

06731608

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to complex node representations in PNNI network systems. Particular embodiments of the invention provide methods and apparatus for generating complex node representations of PNNI peer groups.
BACKGROUND OF THE INVENTION
PNNI (Private Network-to-Network Interface) is a hierarchical, dynamic link-state routing protocol defined by the ATM (Asynchronous Transfer Mode) Forum for use in ATM networks. The hierarchy extension and the use of a single routing protocol at all levels of the hierarchy allow the support for large-scale ATM networks. Among the major characteristics of the protocol are signaling for switched virtual circuits (SVCs), dynamic routing capabilities, and support for quality of service (QoS) parameters. A key feature of the protocol is the ability to cluster network nodes into manageable groups called “peer groups”. One node in each peer group serves as the “peer group leader” and represents that peer group as a single logical node (a “logical group node”) in the next layer up of the hierarchy. This concept is illustrated schematically in
FIG. 1
of the accompanying drawings. In the figure, a peer group A in PNNI layer k consists of four nodes A
1
, A
2
, A
3
and A
4
. Three of these nodes, nodes A
1
, A
2
and A
3
, are border nodes. Each border node has a link connecting peer group A to another peer group (not explicitly shown in layer k), here peer groups B, C and D respectively. The topology in layer k is abstracted in the next layer up of the hierarchy, ie. layer k+1, such that each layer k peer group is represented as a single logical node in layer k+1. Thus peer group A is represented by node A in layer k+1, peer group B is represented by node B in layer k+1, and so on. In the figure, nodes A, B, C and D themselves form a peer group in layer k+1.
ATM is a source routing technology. To enable source route computation and to support end-to-end QoS (for example the required bandwidth), the nodes must maintain information about the network topology. PNNI thus defines a system for the creation and distribution of topology data within a network. Topology data is exchanged automatically by network nodes on a regular basis or upon significant changes to network topology so that each node maintains an up-to-date view of the network. The topology data is defined by PNNI Topology State Elements PTSE's) which are created and distributed by nodes so that each node can maintain a topology database which defines its view of the network. This allows nodes to select paths for routing calls through the network, and to perform alternative routing in the case of link failure. PTSE's include data defining topology characteristics derived from link or node state parameters. PTSE's are flooded among nodes in a peer group so that each peer group node has the same topology database and thus the same view of the network. In the next level up of the hierarchy, however, the peer group topology is abstracted as described above, so that only the abstracted topology is seen by nodes sharing a peer group at this level. It is this topology abstraction that reduces the resources required to define very large networks.
The topology data required for path selection and routing may include not only details of the layout of nodes and links but also QoS parameters as mentioned above. For example, a call to be routed over the network may require a certain bandwidth. In this case, knowledge of the bandwidth of links in the network is required to determine if a call can be connected successfully. To allow such parameters to be taken into account, “costs” can be associated with links and paths in the network. The cost of a link is expressed as an arbitrary value determined as some function of the parameter, eg. bandwidth, about which knowledge is required. Whatever the particular function employed, according to convention it is usual for the cost to be defined such that the lower the cost the better the link. In the case of bandwidth, for example, the cost C of a link may be defined as C=1/bandwidth. A path in the network, involving multiple links, can be measured by a “restrictive cost”. According to the definition of restrictive cost, the weakest link in a path defines the restrictive cost of the path. Thus, when convention is followed such that a higher cost corresponds to a weaker link, the restrictive cost of a path will be determined by the maximum of the costs of the constituent links.
To allow such costs to be taken into account in the path selection process in spite of the hierarchical topology abstraction described above, PNNI provides a way to represent a peer group as a logical group node which has a more sophisticated structure than a single node. The two ways of representing a PNNI peer group in a higher layer are illustrated in
FIG. 2
of the accompanying drawings. The left-hand side of the figure shows an example of the “simple node” representation, and the right-hand side shows an example of the “complex node” representation. The simple node representation shows the peer group as a single node A having ports P
1
, P
2
and P
3
connecting the node to external links, ie. links to neighboring peer groups. The simple node representation is simple to construct and use but does not give information about the cost of traversing the peer group. As discussed further below, a peer group can be modeled by an orientated graph in which a node of the peer group is referenced as a vertex of the graph, and a link between nodes is referenced as an edge between two vertices of the graph. The principle of the complex node representation is to map the simple node to a representation where:
the nucleus
1
is a vertex representing the node itself;
the nucleus
1
is connected via spokes
2
to a set of vertices P
1
, P
2
and P
3
each representing a port in the simple node representation; and
optionally, vertices representing ports can be directly connected by “exception bypasses”
3
.
The complex node representation is derived using a set of restrictive costs for the peer group which is usually presented in the form of a cost matrix known as the “transition matrix” for the peer group. The transition matrix defines the restrictive costs of paths between all pairs of border nodes in the peer group. Where there is more than one path between a given pair of border nodes, then ideally the optimal (lowest-cost) path determines the entry in the transition matrix. The complex node representation, derived on the basis of the transition matrix, indicates the cost of traversing the peer group, and therefore allows such costs to be taken onto account for path selection and other purposes.
The drawback of using the complex node representation is the increased processing complexity involved in generating the complex node representation and using this representation when computing routes (since there are more vertices and edges in the graph representing the network as a whole than in the case of the simple node representation). It is therefore desirable to provide an efficient method for generating the complex node representation and for the resulting complex node representation itself to be optimized as far as possible. In particular, there may be many possible complex node representations corresponding to a given transition matrix and hence a given peer group. In general it will be desirable to minimize the number of exception bypasses in the representation since these represent normal edges in the network graph and thus complicate the network topology seen by nodes. However, it is also important to ensure that the optimal paths of the resulting representation have the same cost as the optimal paths of the original peer group, ie. that the resulting representation accurately reflects the transition matrix.
Copending U.S. patent application Ser. No. 09/385,951, filed 30 Aug. 1999 and assigned to the Assignee of the present application, discloses one method for generating optimal complex node representations. T

Affiliated with

Also associated with

Rating

Complex node representations in PNNI 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 Complex node representations in PNNI systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complex node representations in PNNI systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3193707