Multiplex communications – Communication techniques for information carried in plural... – Adaptive
Reexamination Certificate
1998-04-24
2001-12-18
Chin, Wellington (Department: 2664)
Multiplex communications
Communication techniques for information carried in plural...
Adaptive
C370S238000, C370S232000, C370S252000
Reexamination Certificate
active
06331986
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the design and management of communication networks of the kind that carry traffic corresponding to more than one kind of service. More particularly, the invention relates to methods for distributing traffic among available routes and allocating bandwidth resources to such routes in communication networks of that kind.
BACKGROUND OF THE INVENTION
Networks are commonly used for exchanging or transferring information between terminal communication devices such as computer terminals, telephones, facsimile machines, and computer file servers.
FIG. 1
depicts an illustrative network. A typical network includes switching nodes such as nodes
10
.
1
-
10
.
8
of the figure, interconnected by links, such as links
20
.
1
-
20
.
10
of the figure. Each terminal communication device (not shown in the figure) is generally associated with one of the nodes.
Each link has a certain capacity, usually characterized as a bandwidth for that link. Networks may carry information in various forms. However, the information is often formatted into packets or cells, according to appropriate networking protocols.
One such networking protocol is Asynchronous Transfer Mode (ATM). ATM is a networking protocol designed to efficiently support high-speed digital voice and data communications.
When information is to be exchanged between a pair of terminal communication devices, the network establishes a path between the nodes associated with those devices. In the discussion that follows, the originating node will often be referred to as the “source”, and the destination node will often be referred to as the “destination”. The flow of information of a given service type s through such an established path will often be referred to as a communication “stream” from the source to the destination.
We will use the term “physical path” to denote the source and destination for a given communication stream, together with intermediate nodes (if there are any), and the links that connect them. In networks of practical size and complexity, there will often be a set of multiple physical paths, each able to carry the given stream.
It should be noted that although a physical path may exist between a source S and a destination D, the full bandwidth of the links along that physical path may be unavailable to carry communication streams between S and D. That is, the network manager may specify a predetermined bandwidth for streams between S and D along each of the possible physical paths. The specified bandwidth may equal the full bandwidth, or some quantity less than the full bandwidth, or no bandwidth at all. The last case, of course, is equivalent to denying certain physical paths between S and D.
We use the term “logical path” or “virtual path” to denote a path between a given source and a given destination as defined by such bandwidth specifications. The use of these terms signifies that these paths are not determined purely by physical considerations, but instead that they are partly defined by parameters that can be specified and can be changed.
It will be clear from the foregoing discussion that individual virtual paths will often take up less than the full bandwidth physically available on the links that they occupy. Thus, it will often be the case that several virtual paths co-exist along part or all of a physical path. Stated another way, each link of the network may simultaneously support several virtual paths.
An important advantage of virtual paths is that they can be arranged into subnetworks for serving the various users of the network, and that these subnetworks can be redimensioned (i.e., the bandwidth specifications along the various virtual paths can be revised) from time to time to serve changing traffic requirements.
The problem of allocating bandwidth to all of the virtual paths in the network, according to source-destination pair, subnetwork, and class of service, is referred to as logical network design. One important element of logical network design is the problem of selecting a set of physical paths through the network having sufficient capacity for carrying the estimated traffic of a communication stream. The process that carries out solutions to this problem may take into account such factors as the network topology, the currently available buffer space at the nodes, and the currently available link capacities.
Significantly, the network operator may have quality-of-service commitments with its customers, such as guaranteed bandwidth or maximum cell-loss probability. The path-selection process may also take into account such commitments.
As noted, certain networks, particularly high-speed networks, may support the networking protocol known as ATM. Such high-speed networks will typically carry multiple services having different traffic characteristics, including both constant bit rate traffic and variable bit rate traffic. An important simplification in dealing with variable bit rate traffic in ATM networks is provided by the concept of effective bandwidth, which is described in detail in U.S. patent application Ser. No. 08/506160, “A Method for Admission Control and Routing by Allocating Network Resources in Network Nodes.”
Although buffering capacity plays an important role in ATM networks as a complement to bandwidth, this model subsumes the considerations related to buffering into the effective bandwidth. As a consequence, when variable bit rate traffic is characterized in terms of its effective bandwidth, any ATM network may be viewed (for call-handling purposes) as a multirate, circuit-switched, loss network in which the description of each service includes a characteristic bandwidth requirement (or rate) for each link that carries the service.
In a simple circuit-switched loss network model that is useful for our purposes, each service route (or “virtual path”) is treated as a communication channel spanning a relatively large bandwidth, and that can be subdivided into many smaller-bandwidth subchannels. Many calls are multiplexed on the virtual path. Each call occupies one or more of the subchannels. For our model, it is convenient to assume that this occupation is exclusive throughout the duration of the call. A subchannel carrying a call is referred to as a “switched virtual circuit” or “switched virtual connection.” Bits are assumed to be emitted by each source at a constant rate (corresponding to the effective bandwidth for the pertinent service). Those familiar with Internet Protocol (IP) communications will appreciate that the traffic entities known as “flow” and “connection” refer to the IP counterpart of the switched virtual circuit. (In regard to IP, the protocol known as RSVP is invoked for reserving resources in source-destination paths, and thus it brings the IP concept of “flows” nearer the ATM concept of switched virtual circuits.)
Even when the conveniences afforded by the effective bandwidth model are applied to network analysis, the problems of bandwidth allocation and routing can be very difficult. One source of difficulty is the fact that in contrast to permanent virtual circuits, virtual circuits arrive, hold network resources for some time, and then depart. As a consequence, it is necessary to take into account the randomness of call arrivals and call holding times. A second source of difficulty is the large potential link capacity in these networks, which may reach thousands, or even tens of thousands, of circuits in the near future. Yet a third source of difficulty is the large potential number of different services that these networks may carry. This number is expected to reach several hundreds of services in the near future, and even more thereafter.
There are well-known techniques for analyzing single-rate circuit switched networks. With the help of such techniques, bandwidth allocation and routing can be usefully performed, at least in the simpler networks. However, when multiple rates are introduced, the sources of difficulty mentioned above, among others, conspire to reduce the computational tractability of probl
Mitra Debasis
Morrison John A.
Ramakrishnan Kajamalai Gopalaswamy
Chin Wellington
Finston Martin I.
Lucent Technologies - Inc.
Nguyen Steven
LandOfFree
Method for resource allocation and routing in multi-service... 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 resource allocation and routing in multi-service..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for resource allocation and routing in multi-service... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2559032