Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-08-09
2004-04-13
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S252000, C370S395530, C709S224000, C709S240000
Reexamination Certificate
active
06721270
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods for distributing traffic among routes in packetized communication networks.
ART BACKGROUND
Communication networks transport information between terminal communication devices such as computer terminals, telephones, facsimile machines, and computer file servers. A typical network includes switching nodes such as nodes
10
.
1
-
10
.
8
of
FIG. 1
, interconnected by links, such as links
15
.
1
-
15
.
10
of the figure. Generally, each terminal device (not shown) is associated with one of the nodes.
In many modern networks, the information to be transported from a source node to a destination node is divided into packets or cells. In accordance, for example, with Asynchronous Transfer Mode protocols (ATM) or Internet Protocol (IP), these, e.g., packets stream independently through the network from the source node to the destination node. At each node encountered along the way, a packet is directed into one link or another according to header information borne by that packet. We will refer to any such network as a “packetized” network.
Some communicative transactions, such as telephone calls, are highly sensitive to the timing of the packet arrivals at the destination. If there are significant absolute or relative delays, or if the packets arrive out of order, the quality of the call may be deemed unacceptable. To preserve the quality of transactions of this kind, it is desirable to maintain a complete route from the source to the destination for the entire duration of the transaction. (We will refer to communicative transactions, generally, as “calls,” even if they involve the transmission of fax images, data, etc.)
In all but the simplest networks, more than one route will generally be available from a given source to a given destination. For example, it will be apparent from
FIG. 1
that there are five potential routes from node
10
.
3
to node
10
.
4
. However, it is not always desirable to make available every potential route for a given source-destination pair. For example, some routes may pass through an excessive number of links (i.e., they have many “hops”), which add an unacceptable cumulative delay. The problem is compounded by the fact that each link has a limited amount of bandwidth. Therefore, routing a call between nearby nodes through a far distant link may exclude some traffic between nodes that are situated close to that link. The result may be to force some of that traffic onto undesirably long routes as well.
The discipline referred to as “traffic engineering” deals, inter alia, with the problem of how to distribute traffic among permissible routes. This distribution is desirably made in a manner directed toward a desired level of network performance. Traffic engineering problems are further complicated when the network is required to carry more than one class of service. For example, the same network may be required to carry voice, video, fax, and e-mail transmissions. Each of these services has its own bandwidth requirements, and each has its own requirements as to how much delay can be tolerated. Each may also have its own requirements as to how much call blocking can be tolerated. A network that carries more than one class of service is here referred to as a “multiservice network.”
Network traffic can be broadly divided into two categories: Quality-of-Service (QoS) traffic, and Best-Effort (BE) traffic.
QoS traffic is traffic which must satisfy critical requirements in order to be acceptable to customers. Such requirements typically relate to the maximum acceptable delay. However, they may involve other performance parameters. For example, parameters related to blocking could be important. Parameters of that type include the call-loss ratio and the packet-loss ratio. It often happens that in order to satisfy QoS requirements, the pertinent traffic must be limited to certain sets of admissible routes. This notion of admissible route sets makes it convenient, within QoS methodologies, to define admissible route sets that are limited so as to comply with policy constraints of various kinds.
QoS traffic can be further subdivided into real-time traffic, and non-real-time traffic. Real-time traffic, which includes, e.g., voice and video traffic, is meant to be utilized by the customer as it arrives. Any delays which the customer perceives as disrupting the smooth flow of received data will generally be unacceptable. Non-real-time traffic, which includes, e.g., traffic to and from facsimile machines, is more tolerant of delay, but it still must meet customer expectations of prompt and relatively smooth delivery. In particular, premium data traffic might have critical limitations on the call-loss ratio and packet-loss ratio.
BE traffic, which includes, e.g., World Wide Web traffic, e-mail, and FTP, is still more tolerant of delay as well as call blocking. The user is generally satisfied to wait minutes, or in some cases, even hours, to receive a complete message. Therefore, the network service provider is not expected to guarantee any particular limits on the maximum delay. Instead, it is generally sufficient for the network to use bandwidth, as it becomes available, that can be spared without blocking more lucrative QoS traffic.
In order for network service providers to most fully exploit their multiservice networks, it is desirable for them to offer guarantees to their customers that limits on, e.g., the amount of delay, specified variously for different service classes, will be met. However, it is difficult to design a network that will honor such guarantees without blocking an undue amount of traffic. For example, if voice traffic is concentrated on certain links because they are essential for the shortest routing of voice calls, facsimile transmissions may be excluded from these links. If these links are necessary for the routing of facsimile transmissions, the result will be a busy signal whenever an attempt is made to send a facsimile.
One approach to traffic engineering in multiservice networks is described in D. Mitra, et al., “ATM Network Design and Optimization: A Multirate Loss Network Framework,”
IEEE/ACM Transactions on Networking
4 (August 1996) 531-543. This paper describes a software package referred to as TALISMAN. Among other things, TALISMAN solves a joint routing problem in multiservice ATM networks so as to maximize a performance measure that may be characterized as the long-run average revenue for the network. (A joint routing problem is one that jointly treats all pertinent source-destination pairs.) In the TALISMAN model, a revenue figure is obtained for each service route (i.e., a route in association with a given service class) as the product of a service-route revenue parameter, times the intensity of accepted traffic on that service route. Traffic intensity is defined as the arrival rate of calls, times the mean holding time per call. These revenue figures are summed over all streams and, for each stream, over all service routes, to obtain the total network revenue. A stream is defined as a source-destination pair in association with a given service class.
There is a growing demand for multiservice networks in which the route sets available to different service classes must satisfy distinct policy requirements. In addition to traditional requirements related, e.g., to bandwidth and delay, there are further requirements related to virtual private network services, which are also in growing demand.
Generally, as the size and complexity of networks increases, the time required to solve traffic engineering problems also increases. In order to make the most efficient use of a network in the face of changing traffic patterns, it is desirable to carry out on-line solutions of traffic engineering problems; that is, solutions that are responsive to actual conditions as they occur. Even with the help of tools such as TALISMAN, this is not always feasible for networks that are large or complex.
SUMMARY OF THE INVENTION
We have invented a method for solving traffic engineering problem
Mitra Debasis
Ramakrishnan Kajamalai Gopalaswamy
Elallam Ahmed
Finston Martin A.
Kizou Hassan
Lucent Technologies - Inc.
LandOfFree
Multicommodity flow method for designing traffic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicommodity flow method for designing traffic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicommodity flow method for designing traffic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207716