Method and system for quality of service provisioning for IP virtual private networks

CROSS REFERENCE TO RELATED APPLICATION

00002This application claims the benefit of U.S. Provisional Application No. 60/245,597, filed Nov. 3, 2000, the contents of which are hereby incorporated by reference.

BACKGROUND OF THE INVENTION

00003The present invention relates generally to communications networks, and more particularly, to a method and system for facilitating provisioning of networks to support different classes of traffic.

00004Packet networks, such as the Internet, are increasingly used to transport voice as well as data. Although using a common network infrastructure to transport both voice and data potentially offers significant cost advantages, network providers have not been able to provide a consistent quality of service (QoS) for voice communications over the Internet.

00005Unlike data communications, voice communications require timely reception of packets at a receiver in a network to achieve an acceptable QoS. This requires consistent low packet delays and losses in the network. Existing Internet Protocol (IP) networks including the Internet, however, generally do not provide consistent low packet delays and losses because they maximize the use of network resources through a statistical multiplexing method, which is suitable for best effort traffic, but not for real-time applications, such as voice.

00006The Internet Engineering Task Force (IETF) has attempted to solve this problem by implementing the Resource Reservation Protocol (RSVP) and Integrated Services. However, the RSVP and Integrated Services have failed to gain widespread acceptance because they require networks to maintain a per-flow state in network routers. Currently, IETF is considering a Differentiated Services effort to provide individual mechanisms for enabling different classes of traffic in a network. This method, however, does not provide an enabling methodology for use by Internet Service Providers (ISPs) in provisioning their networks to achieve a consistent QoS when transporting voice over their networks.

SUMMARY OF THE INVENTION

00007To overcome the above and other disadvantages of the prior art, methods and systems are provided for provisioning a network to support different classes of traffic, characterized, for example, by their respective QoS criteria.

00008Such methods and systems provision a network by identifying the classes of traffic to be transported in the network as well as the QoS criteria of the identified classes of traffic. By simulating the classes of traffic, one or more QoS mechanisms and their associated parameters may be determined. The statistical multiplexing gains of the classes of traffic may also be determined based on the simulation. Then, one or more resources in the network may be allocated based on the QoS mechanisms and parameters as well as the multiplexing gains.

00009In one embodiment, traffic classes and their associated QoS criteria may be characterized by, for example, one or more of packet loss, one-way time delay, packet jitter, loss distribution, or other similar factors.

00010In another embodiment, a request to establish a flow between two nodes in the network may be received. The request may include a desired bandwidth. A path between the two nodes may be identified and the available bandwidth along that path may be determined. If the available bandwidth along that path is sufficient to satisfy the request, the flow may be established. One or more nodes in the network through which the flow is established may be configured based on the QoS mechanisms and parameters.

00011In another embodiment, available bandwidth along a path in the network may be updated as follows: The path may be compared to a previous path to identify if links have been added or deleted. For every added link, the requested bandwidth may be subtracted from the available bandwidth on that link. For every deleted link, the requested bandwidth may be added to the available bandwidth for that link. Any link that has an available bandwidth of less than zero may then be identified as congested.

00012The summary of the invention and the following description for carrying out the best mode of the invention should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the description for carrying out the best mode of the invention, show several embodiments of the invention, and together with the description, explain the principles of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

00013In the Figures:

00014<figref idref="DRAWINGS">FIG. 1</figref> illustrates an exemplary network, in accordance with methods and systems consistent with the present invention;

00015<figref idref="DRAWINGS">FIG. 2</figref> is a flow chart of the steps for provisioning a network to support different traffic classes, in accordance with methods and systems consistent with the present invention;

00016<figref idref="DRAWINGS">FIG. 3</figref> is an block diagram illustrating a simulator for provisioning a network, in accordance with methods and systems consistent with the present invention; and

00017<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart of the steps for simulating traffic in a network, in accordance with methods and systems consistent with the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

00018Reference will now be made in detail to the preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like parts.

00019<figref idref="DRAWINGS">FIG. 1</figref> illustrates a network <b>100</b> and a system <b>150</b>, in accordance with methods and systems consistent with the present invention. The network <b>100</b>, which may be owned and/or operated by an Internet Service Provider (ISP), may include a plurality of core routers <b>110</b> and edge routers <b>120</b>, which may be connected to each other via links <b>115</b>. The edge routers may also be on either the ISP's premises or the customer's premises. Edge routers <b>120</b> may each include one or more conditioning mechanisms, such as marking, shaping, and policing. A network operator may use marking mechanisms to configure an edge router to tag traffic to a specific traffic class. Shaping mechanisms may permit a network operator to configure an edge router to change the characteristics of traffic, such as reducing traffic rate. A network operator may use policing mechanisms to configure an edge router to drop traffic that violates preset thresholds.

00020Core routers <b>110</b> may include QoS or minimum bandwidth assurance mechanisms, such as Weighted Fair Queuing (WFQ) and Deficit Round Robin (DRR). Core routers <b>110</b> and edge routers <b>120</b> may be interconnected by a plurality of links <b>115</b>. Customer sites <b>130</b>, which may be also managed by the ISP and interface with edge routers <b>120</b>, may communicate with each other through network <b>100</b>.

00021Network <b>100</b> may interface with other ISP networks through one or more edge routers <b>120</b>. In addition to core routers <b>110</b> and edge routers <b>120</b>, network <b>100</b> may also include a number of monitor nodes <b>140</b>. A monitor node <b>140</b> may gather information about the traffic transported through network <b>100</b>, such as packet loss and one-way time delay on links <b>115</b> and provide that information to system <b>150</b>.

00022System <b>150</b> may include an input device <b>155</b>, a simulator <b>160</b>, and a network operation center (NOC) <b>165</b>. Input device <b>155</b> may include a direct data entry device, such as a keyboard, a device for indirect data entry, such as a floppy disk drive or CD-ROM, or a communication device, such as a modem, for receiving data from network <b>100</b>. Data entered or received may include traffic classes and their respective source models, topology information about network <b>100</b> and one or more QoS criteria for applications, as selected by the ISP administrator. Applications may be running on customer sites <b>130</b>. Data entered or received by input device <b>155</b> may be provided to simulator <b>160</b>, which then simulates the traffic transported through network <b>100</b> based on the provided data. The output of simulator <b>160</b> may include QoS mechanisms and parameter values for provisioning network <b>100</b>. This output may be provided to NOC <b>165</b> via a floppy disk or over a data link (not shown). Simulator <b>160</b> may include, for example, a personal computer or a workstation.

00023NOC <b>165</b> may include an admission controller <b>170</b>, a data storage device <b>175</b>, and a performance feedback component <b>180</b>. NOC <b>165</b> may include, for example, a personal computer or a workstation. Admission controller <b>170</b> may receive requests to establish one or more services between a pair of edge routers <b>120</b> and determine if sufficient network resources exist to establish the requested services. Data storage device <b>175</b> may include data about the topology of network <b>100</b>, the available bandwidth on each link <b>115</b> in network <b>100</b>, a set of paths each including one or more links <b>115</b>, and QoS data, such as QoS mechanisms and associated parameters. Performance feedback component <b>180</b> may receive information from monitors <b>140</b> as well as data storage device <b>175</b>, and may function in conjunction with admission controller <b>170</b> to update available bandwidth on each link <b>115</b> and the set of paths stored in data storage device <b>175</b>.

00024<figref idref="DRAWINGS">FIG. 2</figref> is a flow chart of the steps for provisioning the network <b>100</b> to support different IP traffic classes. First, the ISP administrator may identify the desired classes of traffic to be transported by network <b>100</b>, source models for each class of traffic, and the respective QoS criteria for each class of traffic (step <b>200</b>). A class of traffic may be characterized by one or more QoS criteria, such as a certain level of packet loss and/or one-way time delay that may be tolerated by the class of traffic. Other characterizations may include packet jitter and loss distribution. Source models may include information such as the packet size of the class of traffic as well as the amount of time the traffic is on or off. For example, in a voice-over IP application, there may be a distribution of talk time versus pause time, where packets are generated only during the talk time.

00025After identifying the classes of traffic and associated QoS criteria, the ISP may identify a set of applications to support and map each application to a class of traffic based on the QoS criteria of the application. While each application may be mapped to only one traffic class, each class of traffic may support one or more applications. Exemplary applications may include voice-over IP, Web TCP, and Best Effort. For example, voice-over IP may require a consistently low packet loss and delay. The ISP administrator may provide the identified classes of traffic, source models and QoS criteria, along with information about the topology of network <b>100</b>, to the simulator <b>160</b> using input device <b>155</b>.

00026Next, simulator <b>160</b> may simulate the classes of traffic and determine QoS mechanisms based on the simulation (step <b>210</b>). For example, based on the bandwidth information on links <b>115</b>, the traffic source models and the QoS criteria provided by the ISP administrator, simulator <b>160</b> may iteratively simulate traffic flow using various permutations of available QoS mechanisms to determine one or more QoS mechanisms that satisfy the QoS criteria of the classes of traffic. Exemplary mechanisms may include Token Bucket, Random Early Discard, Weighted Fair Queuing, and Deficit Round Robin.

00027Simulator <b>160</b> may then provide information about the iterations to facilitate the determination of QoS mechanisms for use in the core routers <b>110</b> and edge routers <b>120</b>. Once the ISP administrator, based on the results of the simulation, determines a set of QoS mechanisms, simulator <b>160</b> may then determine the associated parameters of each of the QoS mechanisms satisfying the QoS criteria of the classes of traffic (step <b>220</b>). This process may be similar to the simulation done to determine the appropriate QoS mechanisms.

00028Simulator <b>160</b> may also calculate the statistical multiplexing gains of the traffic classes based the QoS criteria (step <b>230</b>). After the ISP administrator determines the appropriate QoS mechanisms and their associated parameters, the administrator may allocate one or more resources in the network <b>100</b> based on the determined QoS mechanisms and associated parameters and the calculated statistical multiplexing gain (step <b>240</b>). For example, the ISP administrator may allocate resources by provisioning one or more routers in the network <b>100</b>. The traffic classes and QoS criteria may be identified and network <b>100</b> may be provisioned, for example, off line.

00029Once network <b>100</b> is provisioned, the admission controller <b>170</b> may provide admission control for network <b>100</b>. When a first customer site <b>130</b> wishes to communicate with another customer site <b>130</b>, the first customer site <b>130</b> may send to the admission controller <b>170</b> a request for a connection (step <b>250</b>). The customer request may also include the desired bandwidth for the communication. Admission controller <b>170</b> may then determine if there is sufficient bandwidth available to establish the requested flow (step <b>260</b>). In one embodiment, the admission controller <b>170</b> may include a database of information about network <b>100</b>, including information about a set of links <b>115</b> for each IP path as defined by edge router <b>120</b> pairs and the provisioned and available bandwidth for each IP-level link <b>115</b> in the network <b>100</b> for each traffic class. Alternatively, this information may be stored in data storage device <b>175</b>.

00030Admission controller <b>170</b> may determine a path including one or more links <b>115</b> between the two customer sites <b>130</b> and further determine the available bandwidth on the links <b>115</b> in the determined path. If the available bandwidth is greater than or equal to the requested bandwidth, admission controller <b>170</b> may accept the request.

00031If admission controller <b>170</b> determines there is sufficient bandwidth available and the request is accepted, admission controller <b>170</b> may establish the communication flow between the customer sites <b>130</b> (step <b>270</b>). Further, based on the determined QoS mechanisms, their associated parameters, and the determined multiplexing gain, the admission controller <b>170</b> may configure one or more of the nodes (including edge routers <b>120</b> and core routers <b>110</b>) through which the flow is established.

00032Additional admission control features and embodiments consistent with the present invention may also be implemented using the methods and systems described in K. Kim, P. Mouchtaris, S. Samtani, R. Talpade, and L. Wong, “A Simple Admission Control Algorithm for IP Networks”, in Proceedings of International Conference on Networking, 2001, which is incorporated herein in its entirety by reference.

00033Finally, performance feedback component <b>180</b> may dynamically update information about network <b>100</b> to provide better service, based on network information stored in data storage device <b>175</b> or admission controller <b>170</b> and data received from monitors <b>140</b> (step <b>280</b>). To update the available bandwidth information, first performance feedback component may compare each path stored in data storage device <b>175</b> (or admission controller <b>170</b>) to the current path to determine any changes, such as the addition or deletion of links <b>115</b>. For every new or added link, performance feedback component <b>180</b> may subtract the requested bandwidth from the available bandwidth for the link. For each deleted link, performance feedback component may add the requested bandwidth to the available bandwidth for the link. Congested links may then be identified as those links with an available bandwidth of less than zero. In a network with a MultiProtocol Label Switching (MPLS) capability, alternative paths may be established to avoid bad and congested links.

00034<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram illustrating the step of simulating and provisioning of the network <b>100</b> (shown as step <b>210</b> in FIG. <b>2</b>). Input to the simulator <b>160</b> may include the bandwidth of the links <b>115</b>, traffic source models, and the QoS criteria associated with each traffic class. Traffic source models may include information about the size of the packets in each traffic class and how frequently packets are generated. Simulator <b>160</b> then may simulate each class of traffic according to the traffic source model and apply to one or more core routers <b>110</b> and/or edge routers <b>120</b> different conditioning mechanisms, such as Token Bucket, and scheduling mechanisms, such as Weighted Fair Queuing and Deficit Round Robin. Simulator <b>160</b> may provide information about which conditioning and/or scheduling mechanisms satisfy the QoS criteria for each class of traffic as well as the parameters for configuring these mechanisms. An ISP administrator may then determine a set of edge and core router QoS mechanisms and the associated parameters and provision the edge routers <b>120</b> and core routers <b>110</b> based on the simulation results.

00035<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart of the steps for simulating traffic transported through network <b>100</b>, in accordance with methods and systems consistent with the present invention. First, an ISP administrator may determine a model for network <b>100</b> (step <b>400</b>). For example, the model of network <b>100</b> may be represented by a directed graph consisting of a set of nodes, including core routers <b>110</b> and edge routers <b>120</b>, and a set of links <b>115</b> connecting the nodes. Each link <b>115</b> may include an associated bandwidth and/or an associated latency.

00036Next, the ISP administrator may determine a source model for each class of traffic transported through the network <b>100</b> (step <b>410</b>). For each traffic class, the source model may include the size of the packets in the traffic class as well as the frequency with which the packets are generated. For example, a source model for voice traffic may reflect that a person's speech includes pause times. Therefore, the model for voice traffic may include a distribution of on periods (talking) and off periods (pause). Additionally, the model for voice traffic may include a packet size of, for example, 200-bytes.

00037After the network model and the source models are determined, the ISP administrator may configure the simulation environment in simulator <b>160</b> (step <b>420</b>). In one embodiment, an LBNL Network Simulator 2 environment (available at http://www.isi.edu/snam/ns/) may be used to establish the simulation environment and represent network <b>100</b> based on the network model and source models. The ISP administrator may also select one or more simulation variables for each simulation run. Further, the simulation variables may be varied as part of the simulation, including the number of connections for each class of traffic, the link capacities, or the buffer size. Additionally, the configurations of the conditioning mechanisms may also be varied. For example, if the Token Bucket mechanism is included in edge routers <b>120</b>, the simulation variables may then include the token rate or the token bucket depth.

00038For each choice of simulation variables, simulator <b>160</b> may be invoked to simulate network <b>100</b> (step <b>430</b>). The simulation environment in simulator <b>160</b> may be configured based on the network model, the source models, and the chosen simulation variables. The simulation may run for a desired length of time, for example, <b>150</b> simulation seconds, may run until a number of packets have been sent, or may run until other criteria are met. Additionally, the simulation may run multiple times, such as three times, using the same simulation variables to obtain statistically significant results. During the simulation, simulator <b>160</b> may determine data, such as queuing delays, delay distribution, packet loss rates, and link utilization rates, based on which the ISP administrator may configure network <b>100</b>. Following each run of the simulation, the simulation variables may be altered and the simulation may be repeated (step <b>440</b>).

00039Once the simulation runs are completed, the ISP administrator may allocate one or more resources in network <b>100</b> as follows: For example, consider a first simulation using a Token Bucket mechanism in edge routers <b>120</b>, with a token rate of 1.5 Mbps and a bucket depth of 20 packets. In a second simulation, a token rate of 1.5 Mbps and a bucket depth of 100 packets may be used instead. Finally, in a third simulation, a token rate of 10.0 Mbps and a bucket depth of 133 packets may be used. The data determined during these three simulations may indicate that the multiplexing gain associated with the token rate of 10.0 Mbps is the greatest. Thus, in configuring the Token Bucket mechanism in network <b>100</b>, a token rate parameter of 10.0 may prove desirable.

00040Additional provisioning and simulation features and embodiments consistent with the present invention may also be implemented using the methods and systems described in G. Kim, P. Mouchtaris, S. Samtani, R. Talpade, and L. Wong, “QoS Provisioning for VolP in Bandwidth Broker Architecture: A Simulation Approach”, in Proceedings of Communication Networks and Distributed Systems Modeling and Simulation Conference, 2001; and O. Altintas, K. Kim, S. Samtani, R. Talpade, and L. Wong, “A Methodology for Provisioning Quality of Service in IP Networks”, International Workshop on Quality of Service, 2001, both of which are incorporated herein in their entireties by reference.

00041While it has been illustrated and described what are at present considered to be preferred embodiments and methods of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made, and equivalents may be substituted for elements thereof without departing from the true scope of the invention.

00042In addition, many modifications may be made to adapt a particular element, technique, or implementation to the teachings of the present invention without departing from the central scope of the invention. Therefore, it is intended that this invention not be limited to the particular embodiments and methods disclosed herein, but that the invention include all embodiments falling within the scope of the appended claims.