Method and device in a packet switched network

Details Method and device in a packet switched network Method and device in a packet switched network

1998-12-18

2003-08-12

Vu, Huy D. (Department: 2665)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S252000, C709S241000

Reexamination Certificate

active

06606303

ABSTRACT:

TECHNICAL FIELD
The present invention relates to the routing of connections in a telecommunications network, and especially to routing in packet switched networks.
BACKGROUND
A common type of packet switched network today is the Asynchronous Transfer Mode (ATM) network. The ATM technology is connection-oriented, that is, resources are allocated in the network during to the establishment of a connection between two or more users of the network.
Each ATM connection has a traffic contract specifying the capacity, behaviour and quality of service of the connection. The traffic contract is specified when a connection is requested by a calling user and is maintained for the lifetime of the connection. Thus, the consequences of an inefficient routing decision will affect a connection for as long as the connection remains open. Thus, the path through the network should be selected carefully to ensure that the tic contract can be met as long as the connection exists.
In a private Asynchronous Transfer Mode (ATM) network the PNNI function, as specified by the ATM Forum will probably become the chosen function for resource management with respect to routing and signalling, and other functions. A part of the PNNI is a so called dynamic routing protocol meaning that a node in the network will announce and update information regarding its own identity, the resources on its outgoing links and in the node, and address reachability, to all neighboring nodes. This way, in the end all nodes in the network will have a complete hierarchical view of the topology of the network, including its available resources.
The PNNI protocol is defined for use between private ATM switches and between private ATM networks. The abbreviation PNNI stands for either Private Network Node Interface or Private Network-to-Network Interface, reflecting these two areas of use. PNNI routing is used in a private network of ATM switching systems. PNNI includes a routing protocol for distribution of topology information between switches and groups of switches. The functions of the PNNI routing protocol include, among other things:
discovery of neighbours and link and node status,
synchronization of topology databases,
construction of the routing hierarchy,
transmission of PNNI topology state elements from each node to all other nodes.
A topology state parameter is a generic term that refers to either a link state parameter or a nodal state parameter. Topology state parameters fall into two categories: topology metric and topology attribute. A topology metric is a topology state parameter that requires the values of the state parameters of all links and node along a given path to be combined in an additive manner to determine whether the path is acceptable and/or desirable for carrying a given connection. A topology attribute is a topology state parameter that is considered individually to determine whether a given link or node is acceptable and/or desirable for carrying a given connection. In this document the word parameter is used to cover both metrics and attributes.
Two basic routing techniques are used in networking: source routing and hop-by-hop routing. In source routing, the originating switching system selects the path to the destination based on its local knowledge of the network topology. Other systems along the path obey the routing instructions from the source.
In hop-by-hop routing each system independently selects the next hop, which results in a progress toward the destination provided the decisions made at each hop are sufficiently consistent. This technique has some serious disadvantages in a packet switched network. Routing loops may be created, and the processing cost associated with path selection increases for each hop.
To avoid the problems of hop-by-hop routing PNNI uses source routing for all connection setup requests. The first node in a peer group selects the entire path across that peer group and across all other peer groups for the purpose of reaching the destination. The path is encoded as a set of Designated Transit Lists (DTLs) explicitly included in the connection setup request. The DTLs specify every node used in transit across the peer group and may also specify the logical links to be used between the nodes. If a node along the path is unable to follow the DTL for a specific connection setup request the node must perform a so called crankback, that is, return the connection setup request to the node in which the DTL was created.
In general, all links between nodes and all nodes have available resources assigned to them. The available resources in a node are specified for every pair of ports in the node. This is normally done by specifying a default resource for the node and deviations from the default resource for each pair of ports. An exception to the above is the simple node, in which infinite resources are available, and which is therefore not associated with any costs.
A least-cost route is the route with the highest resource margin requiring the minimum allocation of resources compared to other routes, considering both the links between the nodes and the links within the nodes. The resources of the network are nodes and links with their associated available relative capacity and quality of service. As resources are allocated along the least-cost route it may as a result cease to be the least cost route. Another route will then become the least cost route. To rebuild routing tables, the link cost function must be used first to be able to compute the least-cost route.
In this document, the word link is taken to mean either a link between nodes or a path through a node, between two ports of the node. There are two main types of links through nodes: spokes and bypasses. A spoke is a connection in a logical node representation between an interior reference point of the logical node referred to as the nucleus, and a port representing links to other nodes. A bypass is a connection between two ports that does not pass through the nucleus.
A routing algorithm should be able to adapt to a network operator's routing policy, which may change over time. A cost function can be made to match the operator's requirements, which will normally be for maximum call throughput combined with other specific requirements.
Normally routing is not carried out for each call setup request. Instead, a routing table is built, comprising information about possible routes to all destinations that may be reached through the network.
One known routing algorithm commonly used today is the Dijkstra algorithm. This and other known algorithms are capable of routing based on one constraint, for example, to minimize the number of hops or the delay. In other words: given a network topology and a single parameter associated with each link in the graph, Dijkstra's algorithm can quickly find the path between two points minimizing the sum of link parameters in the path. This method is not adequate for the ATM service category real time Variable Bit Rate (rt-VBR), in which multiple constraints must be considered.
Routing for connections with multiple performance constraints complicates the problem in two ways. First, each link must be described in terms of multiple parameters. Second, the ability of a link to participate in a path depends on the requirements of the connection being routed. Having fill topology information and status about actual network resources and capacity is necessary to be able to compare different link costs with each other in order to build least-cost routes to every other destination in the network. The PNNI distributes complete routing information to all nodes, making it desirable to use Dijkstra's algorithm, which, however can only optimize on one parameter. For example, the path for which the delay is minimized may very well have an unacceptably low bandwidth or high delay variation, or vice versa.
One solution to the problem could be to run Dijkstra once for each different type of parameter in the network. Then every parameter would be optimized separately. This would lead to a se

Affiliated with

Also associated with

Rating

Method and device in a packet switched network 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 and device in a packet switched network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device in a packet switched network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3088250