Automatic traffic and quality of service control system for communications networks

The present invention is directed to a system for controlling the quality of service and availability in a communications network. The system includes a processor which samples queue state information from selected intermediate nodes in the network and processes the queue state information to produce a traffic intensity map. The processor includes memory for storing said traffic intensity throughout the network as a traffic intensity surface and is configured to use the traffic intensity surface to control traffic in the network.

BRIEF DESCRIPTION OF THE INVENTION

This invention relates generally to the automatic monitoring and control of performance and quality of service variables including response time, throughput, and utilization as well as availability variables including reliability and maintainability in distributed parameter discrete event systems such as communication networks and more particularly to the modeling of traffic intensity and describing its temporal-spatial dynamics.

BACKGROUND OF THE INVENTION

A computer communications network is a composite discrete event system (DES) made up of two classes of servers: links, which effect the actual transportation of data between source and destination end nodes; and intermediate nodes, which relay data between links, thereby effecting the concatenation of links to provide end-to-end transport of data. Other terms of art for an intermediate node include intermediate system and relay. This concatenation, which is generally referred to as routing or forwarding, may be static or dynamic. Static routing relies on pre-computed routing or forwarding tables that do not change even if there are changes in the state of the network's available links or intermediate nodes. Dynamic routing, in contrast, alters the routing or forwarding tables as feedback is received about changes in the state or topology of the network, possibly including information on the maximum available bandwidth or service rate of the network's links. When a network has been designed with redundant links, a principal advantage of dynamic routing is that it allows recovery from faults that might otherwise disable end-to-end transport of data.

The operation of dynamic routing is typically based on the exchange of routing tables and/or topology state-information among the intermediate nodes. The mechanism used to exchange this information is generally called a routing protocol. A routing protocol enables each intermediate node to construct a topology model, either implicit or explicit, of the network. When the routing protocol exchanges routing tables the topology model is implicit. With topology state routing, on the other hand, each intermediate node constructs, using the topology state information received from other intermediate nodes via the routing protocol, an explicit model of the current topology of the network. With either approach, it is through this exchange of feedback that each intermediate node synchronizes its topology state model, implicit or explicit, with its peers, i.e., the other intermediate nodes. The synchronization attempts to prevent concatenation faults such as forwarding loops by ensuring that each intermediate node has the same topology model.

Using its topology model, each intermediate node then calculates, typically using some form of dynamic programming optimization, the shortest paths to all the other intermediate nodes. The result of this calculation is a shortest path first (SPF) spanning tree from which each intermediate node derives its forwarding or routing table. Because each intermediate node's topology model is the same as its peers, the shortest path first (SPF) spanning trees, and hence the respective forwarding tables thus calculated, are consistent. A consequence, however, of employing spanning tree algorithms is that generally, in a network where the number of intermediate nodes is N and the number of links is L, only N−1 out of the L links are used to carry traffic. Any other links in the network are idled, and used only in the event that one of the N−1 links selected to carry traffic suffers a fault that causes the SPF spanning tree to be recalculated. A direct consequence of the use of a spanning tree to determine the forwarding or routing tables is that highly robust networks, with many redundant links, are necessarily highly inefficient; and that highly efficient networks, with few if any unused links, are necessarily fragile and subject to interruption of service by faults.

By design, topology-adaptive routing protocols only maintain connectivity, leaving routing tables unchanged unless there is a fault or other change that affects the bandwidth or service rate of a component intermediate node or link. In particular, topology-adaptive routing protocols will continue routing traffic through congested, heavily loaded parts of the network, even if idle links are available, so long as the bandwidth of the links in the SPF spanning tree remain unchanged. In fact, topology adaptive routing protocols that rely on implicit or explicit spanning trees of necessity create bottlenecks. This may be acceptable as long as computer networks transport only time-insensitive traffic such as bulk file transfers, email or most web-pages. However, computer networks are increasingly carrying large amounts of time sensitive traffic such as voice or video, both of which require highly consistent and predictable service from the network. Widely varying delays or latencies (also known as jitter) militate against the transportation over packet-switched networks of multimedia and other jitter-intolerant traffic.

The challenge of controlling performance variables such as response time, jitter, and throughput—generally referred to collectively as Quality of Service (QoS)—is that knowledge of topology alone is inadequate. As is well-known from queueing theory, bandwidth or service rate is just one of several variables that determine the performance of a discrete event system (DES), i.e., queueing system. Other variables include the traffic arrival rate(s), the storage available for queued traffic, and the scheduling discipline(s) used to determine the sequencing for execution of incoming requests for service, i.e., the forwarding of packets. Topology-adaptive routing protocols deliberately ignore these other variables when calculating the forwarding tables to be used by the intermediate nodes in a computer network. The forwarding tables that are calculated as part of the routing process are optimized with respect to topology and/or bandwidth but no attempt is made to include traffic state information or similar data about congestion in the network.

Part of the reason why routing protocols in use today do not include traffic or queueing state information is because of the negative experiences that occurred with several early routing protocols that attempted to do so by enhancing the state information exchanged by intermediate nodes with traffic-related data, most notably the ARPANET's Gateway to Gateway Protocol (GGP). The GGP used as the optimality metric in its routing process the estimated delay as measured by the queue length on outgoing links, which each intermediate node included in its routing updates. But the inclusion of such traffic state information in the routing caused major difficulties with instabilities due to rapidly changing state information generated by volatile queue dynamics. The result was large oscillations in routing as attempts to route traffic away from regions of congestion toward less utilized links suffered from overshoot, resulting in traffic bouncing between regions of the network as each region alternatively went from idle to congested and back again. Because of this phenomenon, subsequent routing protocols have avoided using dynamic traffic or queueing state information in their routing.

Another of the disadvantages of the prior art traffic-enhanced routing protocol approach has been the very substantial amounts of the network's total bandwidth consumed by the routing protocol's state updates, the frequency of which is determined by the volatility of the state information they are carrying. The frequency of topology changes (due to links and/or intermediate nodes suffering faults) is many orders of magnitude less than the frequency with which a link's queue changes size. Exacerbating this is the fact that, as is well-known from estimation theory, to adequately represent the dynamics of a varying signal requires sampling at twice the rate of the highest frequency component. Because queue sizes change with each arrival and/or each departure, the frequency of change can be arbitrarily high. Adequate sampling rates to capture the queueing dynamics generate vastly larger amounts of routing protocol update traffic than purely topology-adaptive routing protocols.

Because of these disadvantages, attempts to generate traffic-adaptive paths are today largely limited to manual efforts, where human operators or network engineers estimate traffic patterns and lay out routes that will avoid congested regions. It is widely recognized that this approach is neither accurate nor scalable: large networks will require tens of thousands of paths active at any given time, and generating these is simply beyond the capabilities of current or future network staffing.

Accordingly, a need exists for a method and system for automatically, without manual effort, controlling quality of service parameters including response time, jitter, throughput, and utilization and which is independent of topology. A further need exists for a method and system which meets the above need and which automatically, without manual effort, generates paths that minimize delay by avoiding congestion to the greatest extent possible without incurring unstable routing dynamics, especially large oscillations in routing. A further need exists for a method and system which meets the above need which is independent of the mix of traffic and protocols used in the computer communications network. A further need exists for a method and system which meets the above need without requiring modification of the hardware and software in the intermediate nodes in computer networks. A further need exists for a method and system which meets the above need without requiring proprietary protocols. A further need exists for a method and system which meets the above need without consuming excessive amounts of the network's bandwidth. A further need exists for a method and system which meets the above need without excessive computation and is therefore tractable to real-time, on-line optimization. A further need exists for a method and system which meets the above need and which utilizes a large percentage of the links in the network. A further need exists for a method and system which meets the above need and which can be used by content-caching applications to determine the optimal locations for content-caches to which web or similar requests can be redirected. A further need exists for a method and system which meets the above need and which can be used to provide input on traffic and utilization patterns and trends to capacity planning tools. A further need exists for a method and system which meets the above need and which can be used to identify links and/or intermediate nodes of a computer communications network that at certain times have either a deficit or surplus of bandwidth to a bandwidth trading tool which will either buy additional bandwidth or make available the surplus capacity for resale to carry third party traffic.

OBJECTS AND SUMMARY OF THE INVENTION

It is a general object of the present invention to provide a method and system for automatically controlling quality of service variables including response time, jitter, throughput, and utilization and availability variables including reliability and maintainability that overcomes the aforementioned short comings of the prior art.

It is another object of the present invention to actuate quality of service variables by automatically generating paths that route traffic around congestion and regions of high utilization in transport and in particular computer communication networks.

It is another object of the present invention to actuate quality of service variables by automatically generating paths that route traffic over a large percentage available links in transport and in particular computer communication networks.

It is a further object of the present invention to actuate quality of service variables by automatically determining the optimal locations at which cached replicated data may be located to avoid congested regions of a computer network, and to specify the optimal times when requests should be redirected to given locations.

It is a further object of the present invention to actuate quality of service variables by enabling the realization of self-tuning computer networks through the provision of traffic intensity and utilization state information to capacity planning tools that seek to adjust traffic and bandwidth.

It is a further object of the present invention to actuate quality of service variables by determining when certain links and/or intermediate nodes of a computer communications network have a deficit or surplus of bandwidth and to make this information available to a bandwidth trading tool which will either buy additional bandwidth or make the surplus bandwidth available for resale to carry third party traffic.

The foregoing and other objects of the invention are achieved by modeling the spatial traffic intensity distribution in a computer network and its spatial dynamics and temporal behavior. This is achieved by providing a population or traffic intensity map, similar to weather maps, for the discrete event system composed of the computer communications network and its traffic load. The plot of such a map over time describes the temporal and spatial dynamics of the discrete event system composed of the computer communications network and its traffic load. This provides information for controlling the quality of service variables. The control is achieved by a combination of (1) routing that minimizes transit through congested regions of the network, (2) by determining where content caches should be located in a computer communications network and when traffic should be directed to which cache location, (3) by determining when the network's topology and/or bandwidth should be changed to improve performance, and (4) by identifying local bandwidth surpluses or deficits as well as their persistence to enable bandwidth trading and/or network redesign.

DESCRIPTION OF PREFERRED EMBODIMENTS

A general description of the traffic intensity surface and maps and how they are constructed with the present invention can be illustrated by examining how weather maps are constructed. A weather map is a graphical depiction of the state of the atmosphere over a certain geographical region at a given time. To produce weather maps and weather predictions requires two systems: a monitoring system consisting of a number of instrumentation points where sensors are located to collect state information about the weather, including such variables as temperature, barometric pressure, etc.; and a meteorological modeling system that receives the state information thereby collected and which uses this information in conjunction with a mathematical model of the atmosphere's dynamics to predict the weather. The model, generally speaking, is implemented in the form of a software program that is stored on digital computer, although analogue computers can also be used in some circumstances to model the atmospheric dynamics. The weather model is then used to produce weather maps that interpolate between the instrumentation points and/or extrapolate forward into time to predict future weather dynamics and patterns.

Similarly, with the present invention an ATCC is a modeling system that constructs the traffic intensity surface and corresponding traffic intensity aka population density maps for a computer communications network. A major difference with weather modeling, however, is that the ATCC uses the state estimates derived from the traffic intensity model to determine how to best actuate changes in the quality of service of the discrete event system composed of the computer communications network and its traffic load. The ATCC, generally speaking, is a stored-program digital computer and the traffic intensity model it executes is a software program, although as with the meteorological modeling above analogue computers may be used in some circumstances to model the traffic intensity dynamics. The ATCC collects, generally via the same network for which it is managing traffic intensity and quality of service, queue state information from a sample or subset of the intermediate nodes in the computer network; the queue instrumentation will likely be present in most if not all intermediate nodes in the network.

The ATCC then uses this queue state information in conjunction with the mathematical model it is executing to construct the traffic intensity surface and traffic intensity maps to interpolate between the instrumentation points and/or extrapolate forward into time to predict future traffic intensity and QoS dynamics and patterns. The traffic intensity surface and traffic intensity maps are then fed as input to the ATCC's decision making as how to best control the spatial traffic dynamics using the actuation methods outlined below.

A further similarity exists between weather and traffic intensity modeling, namely the nature of the mathematical models used with each. A crucial characteristic of both transport networks, including computer communications networks, and weather is spatial variability: in the case of the former, one region of the network may be lightly utilized while another region is heavily utilized, while in the case of the latter one area may be receiving rain while another is not. So-called lumped-parameter models, in which the only independent variable is time and which rely on ordinary differential equations or their equivalents, are unable to represent such systems. Any mathematical model of traffic and/or utilization must therefore be in the form of a distributed parameter model described by partial differential equations or their equivalents. Modeling the quality of service dynamics as a spatial/temporal function rather than simply a temporal one just acknowledges one of the most obvious facts about real-world transport networks: congestion and performance are non-uniformly distributed, since one region of a network may be congested, with a local bandwidth deficit, while another region may be idle, with a local bandwidth surplus.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present invention, discussions utilizing terms such as “storing”, “downloading”, “prompting”, “running” or the like, refer to the actions and processes of a computer system, or similar electronic computing device. The computer system or similar electronic computing device manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission, or display devices. The present invention is also well suited to the use of other computer systems such as, for example, optical, mechanical, and analogue computers.

Portions of the present method and system are comprised of computer-readable and computer-executable instructions which reside, for example, in computer-usable media of a computer system.FIG. 1illustrates an exemplary computer system100used to perform the present invention. It is appreciated that system100is exemplary only and that the present invention can operate within a number of different computer systems including general purpose networked computer systems, embedded computer systems, and stand alone computer systems. Furthermore, as will be described in detail, the components of computer100reside, for example, in an intermediate device (e.g., automatic traffic control computer) of the present system and method. Additionally, computer system100is well adapted having computer readable media such as, for example, a floppy disk, a compact disc, and the like coupled thereto. Such computer readable media are not shown coupled to computer system100for purposes of clarity.

System100includes an address/data bus101for communicating information, and a central processor unit102coupled to bus101for processing information and instructions. Central processor unit102may be an 80×86-family microprocessor or any other type of processor. Computer system100also includes data storage features such as a computer usable volatile RAM103, e.g., random access memory (RAM), coupled to bus101for storing information and instructions for central processor unit102, computer usable non-volatile memory104, e.g., read only memory (ROM), coupled to bus101for storing static information and instructions for the central processor unit102, and a data storage unit105(e.g., a magnetic or optical disk and disk drive) coupled to bus101for storing information and instructions. System100of the present invention also includes an optional alphanumeric input device106, which includes alphanumeric and function keys, is coupled to bus101for communicating information and command selections to central processing unit102. System100also includes an optional display device108coupled to bus101for displaying information. Additionally, computer system100includes feature109for connecting computer system100to a network, e.g., a local area network (LAN) or a wide area network (WAN).

Referring still toFIG. 1, optional display device108may be a liquid crystal device, cathode ray tube, or other display device suitable for creating graphic images and alphanumeric characters recognizable to a user. Optional cursor control device107allows the computer user to dynamically signal the two dimensional movement of a visible symbol (cursor) on a display screen of display device108. Many implementations of cursor control device107are known in the art including a mouse, trackball, touch pad, joystick or special keys on alphanumeric input device106capable of signaling movement of a given direction or manner of displacement. Alternatively, it is appreciated that a cursor can be directed and/or activated via input from alphanumeric input device106using special keys and key sequence commands. The present invention is also well suited to directing a cursor by other means such as, for example, voice commands. A more detailed discussion of the method and system embodiments are found below.

FIG. 2is a schematic representation of a system for monitoring and controlling the quality of service of a network200where the number N of intermediate nodes201is six and the number L of links202is six; these are arranged in what is known as the “fish” topology. The intermediate nodes201may be MPLS label-switched routers (LSRs), ATM switches, layer 2 bridges, etc. Each intermediate node201(IN) has associated with it a set of queues203. Also shown is a spanning tree204used to forward traffic between INs; the spanning tree is stored in memory of the INs201. The network includes an Automatic Traffic Control Computer205(ATCC), that collects queue state information from the intermediate nodes in the communications network. The ATCC205may contain, for example, the features of computer system100described above in detail in conjunction withFIG. 1. The ATCC is connected via feature109to either a WAN or LAN link, which is connected either directly or indirectly to computer communications network200.

The ATCC205may receive quality of service targets206from a user such as a network operator using an input device106. These targets are specified in terms of the response time, throughput, jitter, etc. The ATCC205attempts to attain these by actuating the network's traffic flows (following the steps outlined below in flowchart400). For purposes of illustration only one ATCC205is depicted but nothing in this invention precludes a distributed implementation, where multiple ATCCs would have either disjoint or overlapping regions of the network that they each monitor and control with inter-ATCC coordination.

FIG. 2also includes a content cache207and content cache manager208in two end nodes (ENs) attached via links202to INs201. The content cache manager208is responsible for determining to which content cache207user requests for cached data will be sent. The bandwidth manager209attached via a link202to an IN201is responsible for actuating the bandwidth of the network200, either by permanently adding or deleting bandwidth in the form of links202and/or INs201or by temporarily renting additional bandwidth from or to 3rdparty networks.

With reference now to the flowchart300ofFIG. 3, the steps performed by the present invention to achieve quality of service is described. Flowchart300includes processes of the present invention which, in one embodiment, are carried out by a processor or processors under the control of computer readable and computer executable instructions. The computer readable and computer executable instructions reside, for example, in data storage features such as computer usable volatile memory103and/or computer usable non-volatile memory104ofFIG. 1. The computer readable and computer executable instructions are used to control or operate in conjunction with, for example, central processing unit102. Although specific steps are disclosed in flowchart300ofFIG. 3, such steps are exemplary. That is, the present invention is well suited to performing various other steps or variations of the steps inFIG. 3.

In step301the shape and/or dimensions of the domain, which constitutes the area of definition and solution for the partial differential equation that will model the distributed parameter discrete event system, are determined to best fit the network and its traffic load. Step301may be executed by the ATCC205or by human operators. Once the shape and/or dimensions of the domainhave been determined, this information is stored in the memory of the ATCC205.

In step302the ATCC205selects a set of random sample points (intermediate nodes) in the communications network that shall be sampled and determines how frequently the sampling will occur. As with other forms of sampling, the choice of the initial number and location of sample points should be random but is nonetheless subject to constraints of spatial and statistical representativeness; techniques for ensuring that random spatial sample points are representative include stratified sampling and multistage sampling. This invention does not depend on which technique is used. The exact number and location of spatial sample points necessary to adequately estimate the partial differential equation (PDE) parameters will vary depending on the nature of a given DES's dynamics—some traffic and/or network dynamics will necessitate more sample points, while other traffic and/or network dynamics will allow fewer.

In step303ofFIG. 3the ATCC205retrieves queue state information from the intermediate nodes (INs) that ATCC205decided to sample in step302and the queue state information is stored in memory. The communication between the ATCC205and the intermediate nodes201is effected either by connecting the ATCC205directly to the computer communications network for which it is controlling the quality of service or by having the ATCC205connect remotely over 3rdparty private network(s) or the Internet itself. In so doing, the ATCC205and the intermediate nodes201are able to communicate with each other.

The ATCC205may use a variety of protocols in the collection of queue state information in step303. These include the Simple Network Management Protocol (SNMP) and the ISO Common Management Information Protocol (CMIP). Other alternatives to using SNMP, for example, include the TELNET protocol that most intermediate nodes implement to allow remote management by a distant operator.

But almost all intermediate nodes (routers, switches, etc.) implement SNMP and maintain state information in the form of standardized SNMP management information bases (MIBs). Many SNMP MIBs contain queue state information that can be retrieved by the ATCC205. An example of an SNMP MIB that contains queue state information including measurements of the current size of outbound queues is the if (interfaces) group, which defines for every interface in an intermediate node a table, called the ifTable, that includes the MIB state variable called ifOutQLen, which maintains measurements of the number of packets in the output queue for the interface. Those intermediate nodes that do not maintain queue size counters obviously can not be monitored directly but indirect queue state information may nonetheless be inferred from other system state information such as measurements of free memory and allocated memory: by monitoring the ebb and flow of memory usage, it is possible to infer changes in queue sizes and other queue state information for the aggregate of all the interfaces in an intermediate node. In addition, the influence a given intermediate node on traffic intensity dynamics can be inferred from the neighboring nodes that do maintain queue state information. This invention does not depend on which type of queue state information is used.

The present invention does not require that queue state information be smoothed before being used to estimate the PDE parameters, using for example techniques such as autoregressive moving averages (ARMA), Kalman filtering, etc., to reduce noise in queue state information, but this may be optionally employed by the ATCC205.

The ATCC205in step304estimates from the data sets thereby collected and stored in memory the parameters of the partial differential equation that best models the traffic intensity of the computer network and its traffic load. In most cases the PDE model will be the parabolic 2ndorder PDE known as the heat, diffusion or transport equation; but this invention encompasses using other types of PDEs when circumstances warrant, such as elliptic PDEs when the network and its traffic comprising the discrete event system are in steady state. The decision as to which type of PDE will be employed may be made by the user or by the ATCC205. The model chosen is stored in memory by the ATCC205.

For the purpose of this disclosure the focus in step304will be on the heat equation, one form of which is:

The PDE parameters to be estimated in step304include the temporal and spatial dependence of the coefficients for the advective/convective velocity V and its components V1and V2, the random diffusion D, the exogenous forcing function f of general sink/source terms such as lateral boundary and death/birth flux, initial conditions and other terms. Generally speaking, these will be functions of the spatial variables, time, and possibly the population density u itself.

This process of parameter estimation where the aim is to “fit” an equation to a set of empirical data is often called an inverse problem, also sometimes known as model building. A variety of methods can be employed in step304for solving the inverse problem, including but not limited to cubic splines, modal or quasimodal approximations, least-squares, operator factorization, nonlinear variation of constants, and Galerkin methods. This invention does not depend on which technique is used.

If the combination of traffic arrival and service rates is isotropic then there will be no spatial dependence in the coefficients. However, most if not all distributed parameter discrete event systems (networks and traffic loads) will exhibit anisotropy, that is spatial dependence of the various coefficients. The anisotropy is determined by the topology of the network and its pattern of interconnections, by the bandwidth of the links and intermediate nodes, and by the traffic arrival rates. In addition, most traffic patterns will not be static: they will exhibit temporal variations, i.e. vary over time. For example, most networks have at least two strong periodic components to their traffic loads: a 24 hour period corresponding to the work day and a 7 day period corresponding to the week. A secular or non-periodic trend will also be present in the traffic loads for most networks, with either decline or, as is more likely, growth in traffic as demand from end users increases and internally generated management traffic increases as well as the network grows.

In step305the ATCC205optionally repeats the task of retrieving queue state information (step303) with the queue state information stored in memory by the ATCC205. It is possible to estimate the PDE parameters and coefficients once and then leave them unchanged; more useful, however, is to periodically resample the queue state information at the intermediate nodes that have been chosen as sample points and to recursively or iteratively update the model. This process of continuous improvement is sometimes called calibrating or tuning the model. The model calibration can be made more efficient by using an estimate of queue volatility—for example, the standard deviation of the queue sizes—in each region of the network to adjust the sample frequency on a region by region basis so that those regions of the network that are exhibiting volatility (large standard deviations of queue sizes) can be sampled more frequently while those regions that are exhibiting stability (small standard deviations of queue sizes) can be sampled less often. This invention does not depend on which technique is used.

In step306the ATCC205optionally extends the task of calibrating or tuning the model to include modifying the number and/or location of the spatial sampling that was decided in step302. The estimation process the ATCC205executes in step304may itself indicate that more or fewer sample points are needed to adequately estimate the PDE's parameters. Alternatively, the ATCC205may regularly or periodically execute step302to decide fresh where to sample the queue state information in the computer communications network.

In step307ofFIG. 3the ATCC205, once it has estimated the PDE's parameters using one of the aforementioned techniques, optionally alters the shape and/or dimensions of the domainto better fit the network and its traffic load. Such techniques as separation of variables, model-order reduction and conformal mapping may be used to significantly reduce the computational requirements of estimating the PDE's parameters.

Once the PDE's parameters have been estimated using one of the aforementioned techniques, the ATCC205in step308solves the PDE or one of its equivalents such as integral, functional and delay differential, and/or finite difference equations, to yield a population density function u that can be used to predict the quality of service in the network at any given location and time. A variety of methods can be employed in step308for solving the PDE or its equivalents, including perturbation methods, similarity methods, characteristic methods, transformations, numerical methods, and ad hoc methods. This invention does not depend on which technique is used. The population density function u is stored in memory by the ATCC205.

The population density is an approximation to the queue population in the computer network: expansion and contraction of the individual queues may vary from that predicted by u but the approximation accurately tracks and predicts the overall ebb and flow of the traffic intensity in the discrete event system. The population density function u found in step308reflects traffic intensity or utilization ρ(x,y,t) rather than traffic levels alone: from queueing theory it is well-known that the size of any given queue is determined by not just the traffic arrival rate(s) but by the service rate of the outbound link, the ratio of which is the traffic intensity ρ. Plotting the population density function u yields a surface, here designated the traffic intensity surface, where the height of the surface approximates the size the queues in the intermediate nodes in the network being modeled. Running time forward with the model allows the present method to predict the future state of the discrete event system. The traffic intensity surface is stored in memory by the ATCC205. In addition, the traffic intensity surface may be presented for visual inspection using feature108.

This population density/traffic intensity approach has the further advantage that it is independent of the actual bandwidth of the network's links and intermediate nodes: a region of low traffic but also with low bandwidth will have the same population density/traffic intensity value as a region of high bandwidth but with correspondingly higher traffic. Both such regions constitute performance bottlenecks that should be bypassed when actuating traffic to improve the quality of service variables for the discrete event system composed of the network and its traffic.

This population density/traffic intensity approach has the further advantage that it is independent of the actual protocols used in the network: the queued packets may be of any protocol or mix of protocols. The queues that are being measured can even be heterogeneous with respect to the level in the protocol stack: in one intermediate system the queue measurements can be of the number of layer 2 protocol data units (also known as frames) while in another intermediate system the queue measurements can be of the number of layer 3 protocol data units (also known as packets). The only requirement is consistency: the level in the protocol stack at which queue measurements are made can not be changed without recalibrating the PDE model starting with step301.

An immediate consequence of the fact that protocol level is irrelevant to the measurement of queue sizes is that every type of intermediate node, including intermediate nodes that make layer 2 forwarding decisions, generally speaking called switches or bridges, as well as intermediate nodes that make layer 3 forwarding decisions, generally speaking called routers or layer 3 switches, can be monitored and controlled by the use of traffic intensity geodesics. A further advantage of using traffic intensity geodesics is that it reduces the need for fine-detail bandwidth state information to be collected and disseminated via the (topology-adaptive) routing protocol(s) used in the network. What is absolutely needed is the status (operative vs. inoperative) of the network's links and intermediate nodes.

The flowchart400FIG. 4shows the steps performed in accordance with one embodiment of the present invention to actuate traffic and/or network topology and/or bandwidth to automatically control quality of service and availability variables. Three principal techniques for actuating traffic and/or network topology/bandwidth are included in flowchart400. Flowchart400includes process of the present invention which, in one embodiment, are carried out by a process or processors under the control of computer readable and computer executable instructions. The computer readable and computer executable instructions reside, for example, in data storage features such as computer usable volatile memory103and/or computer usable non-volatile memory104ofFIG. 1. The computer readable and computer executable instructions are used to control or operate in conjunction with, for example, central processing unit102. Although specific steps are disclosed in flowchart400ofFIG. 4, such steps are exemplary. That is, the present invention is well suited to performing various other steps or variations of the steps inFIG. 4.

All three actuation techniques in flowchart400start with the population density function u found by the ATCC205in step308ofFIG. 3and which was stored in memory of the ATCC205. As a region of the network becomes more congested due to increased traffic flowing through it and/or a reduction in the network's bandwidth in that region, the height of the traffic intensity surface will increase in that region. Similarly, as a region of the network becomes less congested due to reduced traffic flowing through it and/or an increase in the network's bandwidth in that region, the height of the traffic intensity surface will decrease in that region.

In step401paths are created by the ATCC205to actuate the quality of service and availability variables of the traffic/network discrete event system. The ATCC205may create paths in response to a request from an intermediate node201for a new or modified route, or the request may come from a network operator using feature106or from an automated program running in memory of ATCC205. A benefit to using a traffic intensity surface to approximate the population of queues in a network is that many powerful optimization techniques and methods can be applied to the task of finding optimal paths, most notably the techniques of differential geometry and the calculus of variations, including solving the Euler-Lagrange equation by dynamic programming, shooting methods, direct methods, numerical methods, etc. This invention does not depend on which technique is used. The ATCC205stores in memory the paths created in step401.

Finding the shortest path between two points on a surface is a well-known problem in the calculus of variations, where such paths are called geodesics. The paths found in step401are referred to as traffic intensity geodesics since they are shortest paths found on the traffic intensity surface found by plotting the population density function u. A traffic intensity geodesic by definition is the least-congested path between two nodes connected by the communication network. The larger problem of finding the minimal surface is also solved by the techniques of the calculus of variations, where it is sometimes known as Plateau's problem.

In addition, the process of finding geodesics in step401can be extended to provide differentiated services (generally known as DiffServ) by the ATCC205selecting non-geodesic paths, that is paths that lack the optimality of geodesics, and/or by altering the cost functional used in the optimization. These suboptimal trajectories will result in lower quality of service and performance since they will not avoid as much of the congestion in the network. Users of the computer communications network can specify a QoS profile (in terms of response time, throughput, utilization, etc.) they desire and for which level of quality they are willing to pay.

In step402the paths found as traffic intensity geodesics in step401are projected by the ATCC205on to a map of the actual links of the computer communications network200, the topology of which may have been obtained from the topology-adaptive routing protocol used in network200, from human operators, or other sources such as network management applications. The topology of network200is stored in memory by the ATCC205. A variety of techniques can be employed in step402for projecting the traffic intensity geodesics on to the actual links of the computer communications network, including least-squares minimization, linear programming, etc. Whichever technique is used, in step402the ATCC205finds the network links “closest” to the traffic intensity geodesics. The ordered sequence of these links constitutes a route and is stored in memory by the ATCC205.

The routes created by the ATCC205may differ significantly from the shortest-paths found by the prior art topology-adaptive routing protocols precisely because the latter ignore performance and quality of service factors in their optimization of routes. Routing traffic through a lightly loaded region of the network will result in improved performance, even if the path chosen is longer than an alternate path that nonetheless passes through a heavily congested region.

Once the paths have been mapped or projected on to the actual links and intermediate nodes of the network in step402, there are numerous mechanisms that can be used by the ATCC205to set-up the forwarding tables in the intermediate nodes201in the network200. For example, when the communication network200employs MultiProtocol Label Switching (MPLS) and the intermediate nodes201are label-switched routers (LSRs) then ATCC205can download forwarding table changes by sending the ReSerVation Protocol (RSVP) messages to establish and/or modify label-switched paths (LSPs). When the communication network200employs Asynchronous Transfer Mode (ATM) then the ATCC205can download forwarding table changes by sending Signaling System 7 (SS7) or Network to Network Interface (NNI) messages to establish and/or modify ATM virtual paths and virtual channels. Even in standard IP networks the source-route option can be used to direct traffic along the traffic geodesic. In each of the above examples the ATCC205uses the computer communications network200to send route information to intermediate nodes201so that they can alter their respective forwarding tables. In step403the intermediate nodes201modify their forwarding tables to actuate the traffic intensity.

In step404the traffic intensity surface is used to determine if any imbalances of traffic load and network bandwidth exist in the discrete event system and if so where and when these occur. A given network can simultaneously have some regions in balance while other regions are unbalanced, with simultaneous bandwidth deficits and surpluses to be expected. An imbalance is simple to detect from the traffic intensity surface: where queue sizes are above some threshold there exists a bandwidth deficit while where queue sizes are below some threshold there exists a bandwidth surplus. In step404these thresholds are determined from the quality of service target values that the ATCC205uses as its target(s) for controlling the discrete event system's quality of service and performance.

In step405the ATCC205determines whether a given imbalance is persistent or not. If the imbalance is not persistent then the optimal actuation of quality of service variables is to either buy or sell temporary bandwidth on the “spot” to actuate the imbalance(s). If the imbalance is persistent the optimal actuation of quality of service variables is to either buy or sell permanent bandwidth.

This is effected by the ATCC205in step406. The ATCC205's determination of whether an imbalance is persistent and what level of persistence qualifies will depend on the “rent vs. buy” cost tradeoff: it is less expensive to “rent” temporary bandwidth if the bandwidth deficit does not last for long whereas if the bandwidth deficit lasts longer then the optimal actuation is to actuate the bandwidth and/or topology of the computer communications network in step407. The ATCC205uses the traffic intensity surface, found in step308and stored in memory, and the past “history” of the traffic intensity surface similarly stored in memory, to determine the persistence of the imbalance for each region of the computer communications network200. This information is sent to the bandwidth manager209. The ATCC205may display the imbalances graphically using feature108.

In step408the ATCC205uses the traffic intensity surface to determine the optimal locations of content caches207. This is similar to steps406and407with respect to determining which regions, if any, of the network have a surplus or deficit of bandwidth. Content caching involves replicating frequently requested content such as web pages and placing copies of the content at multiple locations in the computer communications network. Requests for cached content from either end users or internal to the network200are redirected by the caching system's manager208to the cache that is nearest to the end user.

In step409the ATCC205determines the locations of the content caches and/or the times when each cache should be active, thereby actuating the traffic load in the network. The ATCC205effects the changes to the content caches207by sending this information via communication network200to the cache-content manager208responsible for the actuation of cache locations and for redirection of content requests to the optimal content cache207. If a content cache207that is active, meaning end user requests are directed to it by the cache redirection mechanisms, in a region of the computer communications network that is congested, meaning it suffers from a bandwidth deficit, then by moving the content cache and/or redirecting content requests to replicated caches207located in regions of the network that are not congested the result is to have actuated the quality of service variables since traffic will be redirected away from the congested region(s) of the network and toward regions that have more idle transport bandwidth.

InFIG. 5the network depicted inFIG. 2is shown along with one possible traffic intensity surface. The height of the traffic intensity surface at various points is indicated using isoclines501to show the depth or size of the queues in that region of the network. The darker the shading, the higher the traffic intensity surface is at that point. It is important to emphasize that this is a “snapshot” which would evolve over time as the traffic and/or bandwidth and/or topology of the computer communications network change. In addition, three traffic geodesics502are shown for the discrete event system composed of the network and its traffic load. The height under a geodesic502at a given location represents the estimated queue size there.