Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-08-30
2004-06-01
Rao, Seema S. (Department: 2739)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S252000, C370S254000
Reexamination Certificate
active
06744734
ABSTRACT:
TECHNICAL FIELD
The invention concerns the computation of PNNI complex node representations and in particular the computation of the set of optimal PNNI complex node representations.
BACKGROUND OF THE INVENTION
For asynchronous transfer mode (ATM) switches to communicate, a standards-based signaling and routing protocol called Private Network-to-Network Interface (PNNI) is used. PNNI is a comprehensive signaling protocol for use in an ATM network and is a comprehensive routing and signaling standard. Among the major characteristics are signaling for switched virtual circuits (SVCs) and dynamic routing capabilities. It also supports the Quality of Service (QoS) parameters. PNNI was approved by the ATM Forum in 1996 and is found in many ATM systems.
PNNI supports a dynamic information exchange to allow switches to update routing paths and to form alternate routes in case of link failure. In order to support bandwidth request and QoS, a local PNNI switch has to know the network topology. Knowing whether the network can support end-to-end QoS (for example the required bandwidth) and whether the path is available are the only ways the local switch can accept a call without compromising the call integrity. Such information can be established manually when the network is formed. However, having to inform every switch on the network when a new switch is added or when the topology changes is very labor intensive and increases the probability of errors. The only effective process is to have the switches exchange information with one another on a regular basis. PNNI requires such an exchange of information as discussed in the next section.
Topology information is exchanged automatically on a regular basis or upon significant changes to ensure that every switch in the network has the most updated view. Switches form peer groups under common ATM prefix. A peer-group-leader (PGL) is elected in each peer group to represent the peer group at the higher layer. The PGL does not have to be the connecting node between two peer groups. An efficient procedure governs the frequency and the scope of information being exchanged so that bandwidth is conserved.
If update information is received by a switch, it is compared with the existing topology information and changes are automatically made. The effect of the information exchange is to increase the ability to reach the destination. By providing rerouting if a commonly used path fails, an alternate path, if available, will be used to reach the destination. Only by having updated topology information can switches be relied on to make such distributed intelligent decisions. To reduce the overall complexity, the amount of needed memory, and the path selection complexity in particular, PNNI uses the hierarchical model for topology aggregation, as indicated above. At various levels of this hierarchy, a PNNI peer group is represented one level up by a single node as for example illustrated in FIG.
1
.
PNNI is a hierarchical, link-state routing protocol that organizes switching systems into logical collections called peer groups. Neighboring call establishment in PNNI consists of two operations: the nodes form a peer group by exchanging their peer group identifiers (PGIDs) via Hello packets using a protocol that makes nodes known to each other. If the nodes have the same PGID, they are assumed to belong to the peer group defined by that particular PGID; if their PGIDs are different, they are assumed to belong to different peer groups. A border node has at least one link that crosses the peer group boundary. Hello protocol exchanges occur, over logical links called SVCC-based routing control channels (SVCC-RCC). PNNI defines the creation and distribution of a topology database that describes the elements of the routing domain as seen by a node. This topology database provides all the information required to compute a route from the node to any address that is reachable in or through that routing domain. Nodes exchange database information using PTSEs (PNNI Topology State Elements). PTSEs contain topology characteristics derived from link or node state parameter information. The state parameter information could be either metrics or attributes. PTSEs are grouped to form PTSPs (PNNI Topology State Packets) which are flooded throughout the peer group so that every node in one peer group will have an identical topology database. As mentioned already, every peer group has a node called PGL. There is at most one active PGL per peer group. The PGL will represent the current peer group in the parent peer group as a single node called Logical Group Node (LGN). The LGN will also flood the PTSEs in the parent peer group down to the current peer group. Apart from its specific role in aggregation and distribution of information for maintaining the PNNI hierarchy, the PGL does not have any special role in the peer group.
Call establishment in PNNI consists of two operations: the selection of an optimal path and the setup of the connection state at each point along that path. To provide good accuracy in choosing optimal paths in a PNNI network, the PNNI standard provides a way to represent a peer group with a structure which is more sophisticated than the single node. This representation is called “complex node representation” (see right hand side of FIG.
2
). It allows advertisement of the cost of traversing this node and therefore the cost of traversing the whole peer group summarized it by the respective complex node representation.
The computation of complex node representations and the aggregation and distribution of information for maintaining identical databases within a peer group and between peer groups is very complex and time consuming in particular when dealing with large networks. In other words, the path calculation becomes slower with increasing size of a network and as topology updates use up more and more of the node's and link's capacity.
It is an object of the present invention to provide a fast and reliable method for calculating complex node representations using the minimum possible number of exception bypasses.
It is another object of the present invention to provide method for path computation based on a fast and reliable calculation of complex node representations using the minimum possible number of exception bypasses.
It is a further object to provide improved PNNI nodes and PNNI networks.
SUMMARY OF THE INVENTION
The present invention concerns a scheme to construct the set of optimal complex node representations of a PNNI peer group based on a restrictive cost database (e.g. a cost matrix) associated with the border nodes. The resulting set of complex node representations is the optimal in that it contains all the possible complex node representations that use the minimum possible number of exception bypasses.
The present scheme can be employed in any kind of network devices, such a routers for example. The scheme can also be used for routing a packet or frame through a PNNI network using an optimal path. It can also be used for the computation of the optimal path between border nodes of a PNNI peer group.
The advantages of the present invention are addressed in the detailed description.
REFERENCES:
patent: 5831982 (1998-11-01), Hummel
patent: 6115753 (2000-09-01), Joens
patent: 6141325 (2000-10-01), Gerstel
patent: 6256295 (2001-07-01), Callon
patent: 6370119 (2002-04-01), Basso et al.
patent: 6385201 (2002-05-01), Iwata
patent: 6456600 (2002-09-01), Rochberger et al.
patent: 0674459 (1995-09-01), None
patent: 0781007 (1997-06-01), None
Veeraghavan M et al: “Mobile Location Management in ATM Networks” IEEE Journal on Selected Areas in Communications vol. 15, No. 8, Oct. 1997, pp. 1437-1454, XP000721276.
Iwata A et al: “PNNI Routing Algorithms For Multimedia ATM Internet” NEC Research an Development, vol. 38, No. 1, Jan. 1997, pp. 60-73, XP000694589.
Venkateswaran R. et al: Hierarchical Multicast Routing in ATM Networks: 1996 IEEE International Conference on communications (1CC), Converging Technologies for Tomorrow's Applica
Iliadis Ilias
Scotton Paolo
Grosser George E.
International Business Machines - Corporation
McConnell Daniel E.
Mehra Inder Pal
Rao Seema S.
LandOfFree
Method for generating the optimal PNNI complex node... 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 for generating the optimal PNNI complex node..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating the optimal PNNI complex node... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302911