Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-02-28
2003-12-09
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C709S240000
Reexamination Certificate
active
06661797
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to the field of telecommunications and in particular to a more efficient method for selecting a transmission path in a connection-oriented network.
BACKGROUND OF THE INVENTION
It is apparent that connection-oriented networks will play an increasing role in data networking. Connection-oriented networking offers important advantages over connectionless networks, including the advantage of providing Quality of Service (QoS) guarantees, which facilitate new classes of applications such as multimedia, voice over internet protocol, and other real-time services.
A connection-oriented network includes of a set of switches interconnected by point-to-point links or interfaces. The switches support two kinds of interfaces: user-network interfaces (UNI) and network-to-network or network-node interfaces (NNI). A UNI connects end-systems (hosts, routers, and so on) to a switch, while an NNI may be imprecisely defined as an interface connecting two switches together. More precisely, however, an NNI is any physical or logical link across which two switches exchange the NNI protocol. Various NNI protocols, such as the Private Network-Network Interface (PNNI) protocols designed for asynchronous-transfer-mode networks, include a routing protocol that exchanges metrics, such as available and maximum bandwidth, cell loss ratio (CLR), cell delay variation (CDV), and cell transfer delay (CTD), related to Quality of Service (QoS). Routes are then computed using the data collected by the routing protocol. Most commonly-used route determination algorithms (such as Dijkstra shortest path algorithm) use a single, cumulative metric such as link weightings (i.e., administrative weight, hereinafter AW) or costs that relate to the efficient use of the network.
For example, cell loss ratio (CLR) is one of the metrics, or measurements, that can used to determine whether a given network cell, consisting of a link or node or concatenation of links and nodes, can meet the requested quality of service (QoS). Cell delay variation (CDV) and cell transfer delay (CTD) are other such metrics or measurements. In contrast, administrative weight (AW) is a measurement of cost that relates to the efficient use of the network.
Other path selection algorithms, as the one proposed in the PNNI v1.0 standard, use a simple Generic Connection Admission Control (SGCAC) procedure to account for bandwidth. However, neither the SGCAC nor the complex GCAC proposed in PNNI v1.0 is effective in providing the QoS guarantees expected by many data networking customers.
In more detail, the problems in connection-oriented data networking arise out of the following typical existing situations.
As an example of routing and signaling in a connection-oriented network, the PNNI signaling protocol is used to set up asynchronous-transfer-mode switch connections between the source end-system and the destination end-system. The UNI signaling request is mapped into PNNI signaling at the ingress switch. The PNNI signaling is remapped back into UNI signaling at the egress switch. The PNNI signaling protocol is an extension of the UNI signaling and incorporates additional Information Elements (IEs) for PNNI related parameters such as the Designated Transit List (DTL). The PNNI routing protocol is used to disseminate topology, loading conditions and reachability data. For scalability reasons, the notion of hierarchical peer groups is created with Peer Group Leaders (PGLs) elected for each peer group. The PNNI routing protocol is used for hierarchical aggregation and propagation of information. Data about a peer group is aggregated by the peer group leader, which then distributes this data to all the nodes in the higher-level peer group in PNNI Topology State Packets (PTSPs). Thus, aggregated data is passed “up” the hierarchy by peer group leaders. Nodes in a peer group receiving data sent by one of their peer nodes at the higher levels of hierarchy distribute the received data “down” the hierarchy. This allows a switch to maintain a view of the “global” topology with reachability information for endpoints.
The PNNI routing protocol supports a large number of link and node state parameters that are advertised by the switches to indicate their current state at regular intervals which enables QoS-sensitive routing. This includes two types of parameters: attributes, such as Available Cell Rate, Cell Rate Margin, Variance Factor, used to determine whether a given network link or node can meet requested QoS; and metrics, such as maxCDV, CTD, CLR, AW, that are used to determine whether a given path, consisting of a set of concatenated links and nodes (with summed link metrics), can meet the requested QoS. The link metrics and attributes are per port per service category. Individual nodes (physical or logical) will need to determine and then advertise the values of these parameters for themselves.
As a result of these exchanges, a topology database is created, which has reachability information for all the network nodes and the available resources on the network links and nodes. All network nodes can obtain an estimate of the current state of the entire network. Unlike most current link state protocols, the PNNI routing protocol advertises not only link metrics but also nodal information.
When a switch receives a connection setup request, a number of steps are executed. Among these are Connection Admission Control (CAC), Generic Connection Admission Control (GCAC) and shortest path computation. CAC is used to determine if the requested connection can be admitted without violating QoS guarantees of established connections. CAC is a local switch function, and is, dependent on the architecture of the switch and local decisions on the strictness of QoS guarantees required by the switch. The other two algorithms, GCAC and shortest-path computation, are used by the ingress node receiving a connection setup request to determine a shortest-path hierarchical route for the connection while ensuring that all the links on the path have the available cell rate (bandwidth) requested for the connection. This form of routing, where the ingress node determines the shortest-path for the connection, is referred to as source routing. The PNNI v1.0 standard specifies two GCAC algorithms: simple GCAC and complex GCAC. Either of these algorithms can be used to determine if each link on a selected path has the requisite available cell rate (bandwidth) for the connection. The shortest path computation is essentially an execution of a shortest-path algorithm, such as Dijkstra's or Bellman-Ford's, with the link and node weights set to those of the metrics advertised in the received topology information.
Since PNNI networks are hierarchical, the shortest-path computed by the ingress node (after applying Dijkstra's algorithm and the GCAC available cell rate check algorithm) does not specify the exact set of switches through which the connection must be routed. Instead, it specifies a stack of Designated Transit Lists (DTLs), one identifying the physical switches in its peer group, and others identifying logical switches in higher-level peer groups. The DTLs are passed as parameters in the SETUP message. This eliminates the need for intermediate nodes (except border nodes of peer groups) to perform route selection. The border node of each peer group is involved in route selection since nodes outside a peer group P do not have a detailed picture of the topology and loading conditions of the peer group P. The border node through which the connection setup enters the peer group computes a DTL for its peer group and places this on the stack of DTLs as it propagates the PNNI SETUP message.
Once a path has been selected for the connection, each node on the path executes CAC (Connection Admission Control) to ascertain that it can admit the connection without violating guarantees for existing connections. Each node in the path needs to perform its own connection admission control because its own state may have changed since it last adver
Goel Ashish
Kataria Deepak
Logothetis Dimitris
Ramakrishnan Kajamalai Gopalaswamy
Kizou Hassan
Levitan Dmitri
Lucent Technologies - Inc.
LandOfFree
Quality of service based path selection for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quality of service based path selection for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quality of service based path selection for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179412